1 #include <unordered_set>
2 #include <vector>
3 #include <functional>
4 #include <cstdint>
5 #include <cstdlib>
6 #include <cstring>
7
8 #include "benchmark/benchmark.h"
9
10 #include "ContainerBenchmarks.h"
11 #include "GenerateInput.h"
12 #include "test_macros.h"
13
14 using namespace ContainerBenchmarks;
15
16 constexpr std::size_t TestNumInputs = 1024;
17
18 template <class _Size>
19 inline TEST_ALWAYS_INLINE
loadword(const void * __p)20 _Size loadword(const void* __p) {
21 _Size __r;
22 std::memcpy(&__r, __p, sizeof(__r));
23 return __r;
24 }
25
26 inline TEST_ALWAYS_INLINE
rotate_by_at_least_1(std::size_t __val,int __shift)27 std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
28 return (__val >> __shift) | (__val << (64 - __shift));
29 }
30
31 inline TEST_ALWAYS_INLINE
hash_len_16(std::size_t __u,std::size_t __v)32 std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
33 const std::size_t __mul = 0x9ddfea08eb382d69ULL;
34 std::size_t __a = (__u ^ __v) * __mul;
35 __a ^= (__a >> 47);
36 std::size_t __b = (__v ^ __a) * __mul;
37 __b ^= (__b >> 47);
38 __b *= __mul;
39 return __b;
40 }
41
42
43 template <std::size_t _Len>
44 inline TEST_ALWAYS_INLINE
hash_len_0_to_8(const char * __s)45 std::size_t hash_len_0_to_8(const char* __s) {
46 static_assert(_Len == 4 || _Len == 8, "");
47 const uint64_t __a = loadword<uint32_t>(__s);
48 const uint64_t __b = loadword<uint32_t>(__s + _Len - 4);
49 return hash_len_16(_Len + (__a << 3), __b);
50 }
51
52 struct UInt32Hash {
53 UInt32Hash() = default;
54 inline TEST_ALWAYS_INLINE
operator ()UInt32Hash55 std::size_t operator()(uint32_t data) const {
56 return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
57 }
58 };
59
60 struct UInt64Hash {
61 UInt64Hash() = default;
62 inline TEST_ALWAYS_INLINE
operator ()UInt64Hash63 std::size_t operator()(uint64_t data) const {
64 return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
65 }
66 };
67
68 struct UInt128Hash {
69 UInt128Hash() = default;
70 inline TEST_ALWAYS_INLINE
operator ()UInt128Hash71 std::size_t operator()(__uint128_t data) const {
72 const __uint128_t __mask = static_cast<std::size_t>(-1);
73 const std::size_t __a = (std::size_t)(data & __mask);
74 const std::size_t __b = (std::size_t)((data & (__mask << 64)) >> 64);
75 return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b;
76 }
77 };
78
79 struct UInt32Hash2 {
80 UInt32Hash2() = default;
81 inline TEST_ALWAYS_INLINE
operator ()UInt32Hash282 std::size_t operator()(uint32_t data) const {
83 const uint32_t __m = 0x5bd1e995;
84 const uint32_t __r = 24;
85 uint32_t __h = 4;
86 uint32_t __k = data;
87 __k *= __m;
88 __k ^= __k >> __r;
89 __k *= __m;
90 __h *= __m;
91 __h ^= __k;
92 __h ^= __h >> 13;
93 __h *= __m;
94 __h ^= __h >> 15;
95 return __h;
96 }
97 };
98
99 struct UInt64Hash2 {
100 UInt64Hash2() = default;
101 inline TEST_ALWAYS_INLINE
operator ()UInt64Hash2102 std::size_t operator()(uint64_t data) const {
103 return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
104 }
105 };
106
107 // The sole purpose of this comparator is to be used in BM_Rehash, where
108 // we need something slow enough to be easily noticable in benchmark results.
109 // The default implementation of operator== for strings seems to be a little
110 // too fast for that specific benchmark to reliably show a noticeable
111 // improvement, but unoptimized bytewise comparison fits just right.
112 // Early return is there just for convenience, since we only compare strings
113 // of equal length in BM_Rehash.
114 struct SlowStringEq {
115 SlowStringEq() = default;
116 inline TEST_ALWAYS_INLINE
operator ()SlowStringEq117 bool operator()(const std::string& lhs, const std::string& rhs) const {
118 if (lhs.size() != rhs.size()) return false;
119
120 bool eq = true;
121 for (size_t i = 0; i < lhs.size(); ++i) {
122 eq &= lhs[i] == rhs[i];
123 }
124 return eq;
125 }
126 };
127
128 //----------------------------------------------------------------------------//
129 // BM_Hash
130 // ---------------------------------------------------------------------------//
131
132 template <class HashFn, class GenInputs>
BM_Hash(benchmark::State & st,HashFn fn,GenInputs gen)133 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
134 auto in = gen(st.range(0));
135 const auto end = in.data() + in.size();
136 std::size_t last_hash = 0;
137 benchmark::DoNotOptimize(&last_hash);
138 while (st.KeepRunning()) {
139 for (auto it = in.data(); it != end; ++it) {
140 benchmark::DoNotOptimize(last_hash += fn(*it));
141 }
142 benchmark::ClobberMemory();
143 }
144 }
145
146 BENCHMARK_CAPTURE(BM_Hash,
147 uint32_random_std_hash,
148 std::hash<uint32_t>{},
149 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
150
151 BENCHMARK_CAPTURE(BM_Hash,
152 uint32_random_custom_hash,
153 UInt32Hash{},
154 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
155
156 BENCHMARK_CAPTURE(BM_Hash,
157 uint32_top_std_hash,
158 std::hash<uint32_t>{},
159 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
160
161 BENCHMARK_CAPTURE(BM_Hash,
162 uint32_top_custom_hash,
163 UInt32Hash{},
164 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
165
166
167 //----------------------------------------------------------------------------//
168 // BM_InsertValue
169 // ---------------------------------------------------------------------------//
170
171
172 // Sorted Ascending //
173 BENCHMARK_CAPTURE(BM_InsertValue,
174 unordered_set_uint32,
175 std::unordered_set<uint32_t>{},
176 getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
177
178 BENCHMARK_CAPTURE(BM_InsertValue,
179 unordered_set_uint32_sorted,
180 std::unordered_set<uint32_t>{},
181 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
182
183 // Top Bytes //
184 BENCHMARK_CAPTURE(BM_InsertValue,
185 unordered_set_top_bits_uint32,
186 std::unordered_set<uint32_t>{},
187 getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
188
189 BENCHMARK_CAPTURE(BM_InsertValueRehash,
190 unordered_set_top_bits_uint32,
191 std::unordered_set<uint32_t, UInt32Hash>{},
192 getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
193
194 // String //
195 BENCHMARK_CAPTURE(BM_InsertValue,
196 unordered_set_string,
197 std::unordered_set<std::string>{},
198 getRandomStringInputs)->Arg(TestNumInputs);
199
200 BENCHMARK_CAPTURE(BM_InsertValueRehash,
201 unordered_set_string,
202 std::unordered_set<std::string>{},
203 getRandomStringInputs)->Arg(TestNumInputs);
204
205 //----------------------------------------------------------------------------//
206 // BM_Find
207 // ---------------------------------------------------------------------------//
208
209 // Random //
210 BENCHMARK_CAPTURE(BM_Find,
211 unordered_set_random_uint64,
212 std::unordered_set<uint64_t>{},
213 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
214
215 BENCHMARK_CAPTURE(BM_FindRehash,
216 unordered_set_random_uint64,
217 std::unordered_set<uint64_t, UInt64Hash>{},
218 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
219
220 // Sorted //
221 BENCHMARK_CAPTURE(BM_Find,
222 unordered_set_sorted_uint64,
223 std::unordered_set<uint64_t>{},
224 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
225
226 BENCHMARK_CAPTURE(BM_FindRehash,
227 unordered_set_sorted_uint64,
228 std::unordered_set<uint64_t, UInt64Hash>{},
229 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
230
231
232 // Sorted //
233 #if 1
234 BENCHMARK_CAPTURE(BM_Find,
235 unordered_set_sorted_uint128,
236 std::unordered_set<__uint128_t, UInt128Hash>{},
237 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
238
239 BENCHMARK_CAPTURE(BM_FindRehash,
240 unordered_set_sorted_uint128,
241 std::unordered_set<__uint128_t, UInt128Hash>{},
242 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
243 #endif
244
245 // Sorted //
246 BENCHMARK_CAPTURE(BM_Find,
247 unordered_set_sorted_uint32,
248 std::unordered_set<uint32_t>{},
249 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
250
251 BENCHMARK_CAPTURE(BM_FindRehash,
252 unordered_set_sorted_uint32,
253 std::unordered_set<uint32_t, UInt32Hash2>{},
254 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
255
256 // Sorted Ascending //
257 BENCHMARK_CAPTURE(BM_Find,
258 unordered_set_sorted_large_uint64,
259 std::unordered_set<uint64_t>{},
260 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
261
262 BENCHMARK_CAPTURE(BM_FindRehash,
263 unordered_set_sorted_large_uint64,
264 std::unordered_set<uint64_t, UInt64Hash>{},
265 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
266
267
268 // Top Bits //
269 BENCHMARK_CAPTURE(BM_Find,
270 unordered_set_top_bits_uint64,
271 std::unordered_set<uint64_t>{},
272 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
273
274 BENCHMARK_CAPTURE(BM_FindRehash,
275 unordered_set_top_bits_uint64,
276 std::unordered_set<uint64_t, UInt64Hash>{},
277 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
278
279 // String //
280 BENCHMARK_CAPTURE(BM_Find,
281 unordered_set_string,
282 std::unordered_set<std::string>{},
283 getRandomStringInputs)->Arg(TestNumInputs);
284
285 BENCHMARK_CAPTURE(BM_FindRehash,
286 unordered_set_string,
287 std::unordered_set<std::string>{},
288 getRandomStringInputs)->Arg(TestNumInputs);
289
290 //----------------------------------------------------------------------------//
291 // BM_Rehash
292 // ---------------------------------------------------------------------------//
293
294 BENCHMARK_CAPTURE(BM_Rehash,
295 unordered_set_string_arg,
296 std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
297 getRandomStringInputs)->Arg(TestNumInputs);
298
299 BENCHMARK_CAPTURE(BM_Rehash,
300 unordered_set_int_arg,
301 std::unordered_set<int>{},
302 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
303
304 ///////////////////////////////////////////////////////////////////////////////
305 BENCHMARK_CAPTURE(BM_InsertDuplicate,
306 unordered_set_int,
307 std::unordered_set<int>{},
308 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
309 BENCHMARK_CAPTURE(BM_InsertDuplicate,
310 unordered_set_string,
311 std::unordered_set<std::string>{},
312 getRandomStringInputs)->Arg(TestNumInputs);
313
314 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
315 unordered_set_int,
316 std::unordered_set<int>{},
317 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
318 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
319 unordered_set_string,
320 std::unordered_set<std::string>{},
321 getRandomStringInputs)->Arg(TestNumInputs);
322
323 BENCHMARK_CAPTURE(BM_InsertDuplicate,
324 unordered_set_int_insert_arg,
325 std::unordered_set<int>{},
326 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
327 BENCHMARK_CAPTURE(BM_InsertDuplicate,
328 unordered_set_string_insert_arg,
329 std::unordered_set<std::string>{},
330 getRandomStringInputs)->Arg(TestNumInputs);
331
332 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
333 unordered_set_int_insert_arg,
334 std::unordered_set<int>{},
335 getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
336
337 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
338 unordered_set_string_arg,
339 std::unordered_set<std::string>{},
340 getRandomCStringInputs)->Arg(TestNumInputs);
341
342 BENCHMARK_MAIN();
343