1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <stdint.h>
18
19 #include <map>
20 #include <unordered_map>
21
22 #include "benchmark/benchmark.h"
23
24 namespace android {
25
26 template <class Map = std::unordered_map<uint32_t, std::vector<uint32_t>>>
prepare_map()27 static Map prepare_map() {
28 Map map;
29 std::vector<uint32_t> vec;
30 for (int i = 0; i < 1000; ++i) {
31 map.emplace(i, vec);
32 }
33 return map;
34 }
35
BM_hashmap_emplace_same(benchmark::State & state)36 static void BM_hashmap_emplace_same(benchmark::State& state) {
37 auto map = prepare_map<>();
38 auto val = map.size() - 1;
39 std::vector<uint32_t> vec;
40 for (auto&& _ : state) {
41 benchmark::DoNotOptimize(map.emplace(val, vec));
42 }
43 }
44 BENCHMARK(BM_hashmap_emplace_same);
BM_hashmap_try_emplace_same(benchmark::State & state)45 static void BM_hashmap_try_emplace_same(benchmark::State& state) {
46 auto map = prepare_map();
47 auto val = map.size() - 1;
48 for (auto&& _ : state) {
49 benchmark::DoNotOptimize(map.try_emplace(val));
50 }
51 }
52 BENCHMARK(BM_hashmap_try_emplace_same);
BM_hashmap_find(benchmark::State & state)53 static void BM_hashmap_find(benchmark::State& state) {
54 auto map = prepare_map<>();
55 auto val = map.size() - 1;
56 for (auto&& _ : state) {
57 benchmark::DoNotOptimize(map.find(val));
58 }
59 }
60 BENCHMARK(BM_hashmap_find);
61
BM_hashmap_emplace_diff(benchmark::State & state)62 static void BM_hashmap_emplace_diff(benchmark::State& state) {
63 auto map = prepare_map<>();
64 std::vector<uint32_t> vec;
65 auto i = map.size();
66 for (auto&& _ : state) {
67 map.emplace(i++, vec);
68 }
69 }
70 BENCHMARK(BM_hashmap_emplace_diff);
BM_hashmap_try_emplace_diff(benchmark::State & state)71 static void BM_hashmap_try_emplace_diff(benchmark::State& state) {
72 auto map = prepare_map();
73 auto i = map.size();
74 for (auto&& _ : state) {
75 map.try_emplace(i++);
76 }
77 }
78 BENCHMARK(BM_hashmap_try_emplace_diff);
BM_hashmap_find_emplace_diff(benchmark::State & state)79 static void BM_hashmap_find_emplace_diff(benchmark::State& state) {
80 auto map = prepare_map<>();
81 std::vector<uint32_t> vec;
82 auto i = map.size();
83 for (auto&& _ : state) {
84 if (map.find(i++) == map.end()) {
85 map.emplace(i - 1, vec);
86 }
87 }
88 }
89 BENCHMARK(BM_hashmap_find_emplace_diff);
90
BM_treemap_emplace_same(benchmark::State & state)91 static void BM_treemap_emplace_same(benchmark::State& state) {
92 auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
93 auto val = map.size() - 1;
94 std::vector<uint32_t> vec;
95 for (auto&& _ : state) {
96 benchmark::DoNotOptimize(map.emplace(val, vec));
97 }
98 }
99 BENCHMARK(BM_treemap_emplace_same);
BM_treemap_try_emplace_same(benchmark::State & state)100 static void BM_treemap_try_emplace_same(benchmark::State& state) {
101 auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
102 auto val = map.size() - 1;
103 for (auto&& _ : state) {
104 benchmark::DoNotOptimize(map.try_emplace(val));
105 }
106 }
107 BENCHMARK(BM_treemap_try_emplace_same);
BM_treemap_find(benchmark::State & state)108 static void BM_treemap_find(benchmark::State& state) {
109 auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
110 auto val = map.size() - 1;
111 for (auto&& _ : state) {
112 benchmark::DoNotOptimize(map.find(val));
113 }
114 }
115 BENCHMARK(BM_treemap_find);
116
BM_treemap_emplace_diff(benchmark::State & state)117 static void BM_treemap_emplace_diff(benchmark::State& state) {
118 auto map = prepare_map<std::map<uint32_t, std::vector<uint32_t>>>();
119 std::vector<uint32_t> vec;
120 auto i = map.size();
121 for (auto&& _ : state) {
122 map.emplace(i++, vec);
123 }
124 }
125 BENCHMARK(BM_treemap_emplace_diff);
BM_treemap_try_emplace_diff(benchmark::State & state)126 static void BM_treemap_try_emplace_diff(benchmark::State& state) {
127 auto map = prepare_map();
128 auto i = map.size();
129 for (auto&& _ : state) {
130 map.try_emplace(i++);
131 }
132 }
133 BENCHMARK(BM_treemap_try_emplace_diff);
BM_treemap_find_emplace_diff(benchmark::State & state)134 static void BM_treemap_find_emplace_diff(benchmark::State& state) {
135 auto map = prepare_map();
136 std::vector<uint32_t> vec;
137 auto i = map.size();
138 for (auto&& _ : state) {
139 if (map.find(i++) == map.end()) {
140 map.emplace(i - 1, vec);
141 }
142 }
143 }
144 BENCHMARK(BM_treemap_find_emplace_diff);
145
146 } // namespace android