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.hpp"
11 #include "GenerateInput.hpp"
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 //----------------------------------------------------------------------------//
108 // BM_Hash
109 // ---------------------------------------------------------------------------//
110
111 template <class HashFn, class GenInputs>
BM_Hash(benchmark::State & st,HashFn fn,GenInputs gen)112 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
113 auto in = gen(st.range(0));
114 const auto end = in.data() + in.size();
115 std::size_t last_hash = 0;
116 benchmark::DoNotOptimize(&last_hash);
117 while (st.KeepRunning()) {
118 for (auto it = in.data(); it != end; ++it) {
119 benchmark::DoNotOptimize(last_hash += fn(*it));
120 }
121 benchmark::ClobberMemory();
122 }
123 }
124
125 BENCHMARK_CAPTURE(BM_Hash,
126 uint32_random_std_hash,
127 std::hash<uint32_t>{},
128 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
129
130 BENCHMARK_CAPTURE(BM_Hash,
131 uint32_random_custom_hash,
132 UInt32Hash{},
133 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
134
135 BENCHMARK_CAPTURE(BM_Hash,
136 uint32_top_std_hash,
137 std::hash<uint32_t>{},
138 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
139
140 BENCHMARK_CAPTURE(BM_Hash,
141 uint32_top_custom_hash,
142 UInt32Hash{},
143 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
144
145
146 //----------------------------------------------------------------------------//
147 // BM_InsertValue
148 // ---------------------------------------------------------------------------//
149
150
151 // Sorted Assending //
152 BENCHMARK_CAPTURE(BM_InsertValue,
153 unordered_set_uint32,
154 std::unordered_set<uint32_t>{},
155 getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
156
157 BENCHMARK_CAPTURE(BM_InsertValue,
158 unordered_set_uint32_sorted,
159 std::unordered_set<uint32_t>{},
160 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
161
162 // Top Bytes //
163 BENCHMARK_CAPTURE(BM_InsertValue,
164 unordered_set_top_bits_uint32,
165 std::unordered_set<uint32_t>{},
166 getSortedTopBitsIntegerInputs<uint32_t>)->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>)->Arg(TestNumInputs);
172
173 // String //
174 BENCHMARK_CAPTURE(BM_InsertValue,
175 unordered_set_string,
176 std::unordered_set<std::string>{},
177 getRandomStringInputs)->Arg(TestNumInputs);
178
179 BENCHMARK_CAPTURE(BM_InsertValueRehash,
180 unordered_set_string,
181 std::unordered_set<std::string>{},
182 getRandomStringInputs)->Arg(TestNumInputs);
183
184 //----------------------------------------------------------------------------//
185 // BM_Find
186 // ---------------------------------------------------------------------------//
187
188 // Random //
189 BENCHMARK_CAPTURE(BM_Find,
190 unordered_set_random_uint64,
191 std::unordered_set<uint64_t>{},
192 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
193
194 BENCHMARK_CAPTURE(BM_FindRehash,
195 unordered_set_random_uint64,
196 std::unordered_set<uint64_t, UInt64Hash>{},
197 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
198
199 // Sorted //
200 BENCHMARK_CAPTURE(BM_Find,
201 unordered_set_sorted_uint64,
202 std::unordered_set<uint64_t>{},
203 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
204
205 BENCHMARK_CAPTURE(BM_FindRehash,
206 unordered_set_sorted_uint64,
207 std::unordered_set<uint64_t, UInt64Hash>{},
208 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
209
210
211 // Sorted //
212 #if 1
213 BENCHMARK_CAPTURE(BM_Find,
214 unordered_set_sorted_uint128,
215 std::unordered_set<__uint128_t, UInt128Hash>{},
216 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
217
218 BENCHMARK_CAPTURE(BM_FindRehash,
219 unordered_set_sorted_uint128,
220 std::unordered_set<__uint128_t, UInt128Hash>{},
221 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
222 #endif
223
224 // Sorted //
225 BENCHMARK_CAPTURE(BM_Find,
226 unordered_set_sorted_uint32,
227 std::unordered_set<uint32_t>{},
228 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
229
230 BENCHMARK_CAPTURE(BM_FindRehash,
231 unordered_set_sorted_uint32,
232 std::unordered_set<uint32_t, UInt32Hash2>{},
233 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
234
235 // Sorted Ascending //
236 BENCHMARK_CAPTURE(BM_Find,
237 unordered_set_sorted_large_uint64,
238 std::unordered_set<uint64_t>{},
239 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
240
241 BENCHMARK_CAPTURE(BM_FindRehash,
242 unordered_set_sorted_large_uint64,
243 std::unordered_set<uint64_t, UInt64Hash>{},
244 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
245
246
247 // Top Bits //
248 BENCHMARK_CAPTURE(BM_Find,
249 unordered_set_top_bits_uint64,
250 std::unordered_set<uint64_t>{},
251 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
252
253 BENCHMARK_CAPTURE(BM_FindRehash,
254 unordered_set_top_bits_uint64,
255 std::unordered_set<uint64_t, UInt64Hash>{},
256 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
257
258 // String //
259 BENCHMARK_CAPTURE(BM_Find,
260 unordered_set_string,
261 std::unordered_set<std::string>{},
262 getRandomStringInputs)->Arg(TestNumInputs);
263
264 BENCHMARK_CAPTURE(BM_FindRehash,
265 unordered_set_string,
266 std::unordered_set<std::string>{},
267 getRandomStringInputs)->Arg(TestNumInputs);
268
269 ///////////////////////////////////////////////////////////////////////////////
270 BENCHMARK_CAPTURE(BM_InsertDuplicate,
271 unordered_set_int,
272 std::unordered_set<int>{},
273 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
274 BENCHMARK_CAPTURE(BM_InsertDuplicate,
275 unordered_set_string,
276 std::unordered_set<std::string>{},
277 getRandomStringInputs)->Arg(TestNumInputs);
278
279 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
280 unordered_set_int,
281 std::unordered_set<int>{},
282 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
283 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
284 unordered_set_string,
285 std::unordered_set<std::string>{},
286 getRandomStringInputs)->Arg(TestNumInputs);
287
288 BENCHMARK_CAPTURE(BM_InsertDuplicate,
289 unordered_set_int_insert_arg,
290 std::unordered_set<int>{},
291 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
292 BENCHMARK_CAPTURE(BM_InsertDuplicate,
293 unordered_set_string_insert_arg,
294 std::unordered_set<std::string>{},
295 getRandomStringInputs)->Arg(TestNumInputs);
296
297 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
298 unordered_set_int_insert_arg,
299 std::unordered_set<int>{},
300 getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
301
302 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
303 unordered_set_string_arg,
304 std::unordered_set<std::string>{},
305 getRandomCStringInputs)->Arg(TestNumInputs);
306
307 BENCHMARK_MAIN();
308