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