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
13 using namespace ContainerBenchmarks;
14
15 constexpr std::size_t TestNumInputs = 1024;
16
17 template <class _Size>
18 inline __attribute__((__always_inline__))
loadword(const void * __p)19 _Size loadword(const void* __p) {
20 _Size __r;
21 std::memcpy(&__r, __p, sizeof(__r));
22 return __r;
23 }
24
25 inline __attribute__((__always_inline__))
rotate_by_at_least_1(std::size_t __val,int __shift)26 std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
27 return (__val >> __shift) | (__val << (64 - __shift));
28 }
29
30 inline __attribute__((__always_inline__))
hash_len_16(std::size_t __u,std::size_t __v)31 std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
32 const std::size_t __mul = 0x9ddfea08eb382d69ULL;
33 std::size_t __a = (__u ^ __v) * __mul;
34 __a ^= (__a >> 47);
35 std::size_t __b = (__v ^ __a) * __mul;
36 __b ^= (__b >> 47);
37 __b *= __mul;
38 return __b;
39 }
40
41
42 template <std::size_t _Len>
43 inline __attribute__((__always_inline__))
hash_len_0_to_8(const char * __s)44 std::size_t hash_len_0_to_8(const char* __s) {
45 static_assert(_Len == 4 || _Len == 8, "");
46 const uint64_t __a = loadword<uint32_t>(__s);
47 const uint64_t __b = loadword<uint32_t>(__s + _Len - 4);
48 return hash_len_16(_Len + (__a << 3), __b);
49 }
50
51 struct UInt32Hash {
52 UInt32Hash() = default;
53 inline __attribute__((__always_inline__))
operator ()UInt32Hash54 std::size_t operator()(uint32_t data) const {
55 return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
56 }
57 };
58
59 struct UInt64Hash {
60 UInt64Hash() = default;
61 inline __attribute__((__always_inline__))
operator ()UInt64Hash62 std::size_t operator()(uint64_t data) const {
63 return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
64 }
65 };
66
67 struct UInt128Hash {
68 UInt128Hash() = default;
69 inline __attribute__((__always_inline__))
operator ()UInt128Hash70 std::size_t operator()(__uint128_t data) const {
71 const __uint128_t __mask = static_cast<std::size_t>(-1);
72 const std::size_t __a = (std::size_t)(data & __mask);
73 const std::size_t __b = (std::size_t)((data & (__mask << 64)) >> 64);
74 return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b;
75 }
76 };
77
78 struct UInt32Hash2 {
79 UInt32Hash2() = default;
80 inline __attribute__((__always_inline__))
operator ()UInt32Hash281 std::size_t operator()(uint32_t data) const {
82 const uint32_t __m = 0x5bd1e995;
83 const uint32_t __r = 24;
84 uint32_t __h = 4;
85 uint32_t __k = data;
86 __k *= __m;
87 __k ^= __k >> __r;
88 __k *= __m;
89 __h *= __m;
90 __h ^= __k;
91 __h ^= __h >> 13;
92 __h *= __m;
93 __h ^= __h >> 15;
94 return __h;
95 }
96 };
97
98 struct UInt64Hash2 {
99 UInt64Hash2() = default;
100 inline __attribute__((__always_inline__))
operator ()UInt64Hash2101 std::size_t operator()(uint64_t data) const {
102 return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
103 }
104 };
105
106 //----------------------------------------------------------------------------//
107 // BM_Hash
108 // ---------------------------------------------------------------------------//
109
110 template <class HashFn, class GenInputs>
BM_Hash(benchmark::State & st,HashFn fn,GenInputs gen)111 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
112 auto in = gen(st.range(0));
113 const auto end = in.data() + in.size();
114 std::size_t last_hash = 0;
115 benchmark::DoNotOptimize(&last_hash);
116 while (st.KeepRunning()) {
117 for (auto it = in.data(); it != end; ++it) {
118 benchmark::DoNotOptimize(last_hash += fn(*it));
119 }
120 benchmark::ClobberMemory();
121 }
122 }
123
124 BENCHMARK_CAPTURE(BM_Hash,
125 uint32_random_std_hash,
126 std::hash<uint32_t>{},
127 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
128
129 BENCHMARK_CAPTURE(BM_Hash,
130 uint32_random_custom_hash,
131 UInt32Hash{},
132 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
133
134 BENCHMARK_CAPTURE(BM_Hash,
135 uint32_top_std_hash,
136 std::hash<uint32_t>{},
137 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
138
139 BENCHMARK_CAPTURE(BM_Hash,
140 uint32_top_custom_hash,
141 UInt32Hash{},
142 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
143
144
145 //----------------------------------------------------------------------------//
146 // BM_InsertValue
147 // ---------------------------------------------------------------------------//
148
149
150 // Sorted Assending //
151 BENCHMARK_CAPTURE(BM_InsertValue,
152 unordered_set_uint32,
153 std::unordered_set<uint32_t>{},
154 getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
155
156 BENCHMARK_CAPTURE(BM_InsertValue,
157 unordered_set_uint32_sorted,
158 std::unordered_set<uint32_t>{},
159 getSortedIntegerInputs<uint32_t>)->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>)->Arg(TestNumInputs);
166
167 BENCHMARK_CAPTURE(BM_InsertValueRehash,
168 unordered_set_top_bits_uint32,
169 std::unordered_set<uint32_t, UInt32Hash>{},
170 getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
171
172 // String //
173 BENCHMARK_CAPTURE(BM_InsertValue,
174 unordered_set_string,
175 std::unordered_set<std::string>{},
176 getRandomStringInputs)->Arg(TestNumInputs);
177
178 BENCHMARK_CAPTURE(BM_InsertValueRehash,
179 unordered_set_string,
180 std::unordered_set<std::string>{},
181 getRandomStringInputs)->Arg(TestNumInputs);
182
183 //----------------------------------------------------------------------------//
184 // BM_Find
185 // ---------------------------------------------------------------------------//
186
187 // Random //
188 BENCHMARK_CAPTURE(BM_Find,
189 unordered_set_random_uint64,
190 std::unordered_set<uint64_t>{},
191 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
192
193 BENCHMARK_CAPTURE(BM_FindRehash,
194 unordered_set_random_uint64,
195 std::unordered_set<uint64_t, UInt64Hash>{},
196 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
197
198 // Sorted //
199 BENCHMARK_CAPTURE(BM_Find,
200 unordered_set_sorted_uint64,
201 std::unordered_set<uint64_t>{},
202 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
203
204 BENCHMARK_CAPTURE(BM_FindRehash,
205 unordered_set_sorted_uint64,
206 std::unordered_set<uint64_t, UInt64Hash>{},
207 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
208
209
210 // Sorted //
211 #if 1
212 BENCHMARK_CAPTURE(BM_Find,
213 unordered_set_sorted_uint128,
214 std::unordered_set<__uint128_t, UInt128Hash>{},
215 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
216
217 BENCHMARK_CAPTURE(BM_FindRehash,
218 unordered_set_sorted_uint128,
219 std::unordered_set<__uint128_t, UInt128Hash>{},
220 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
221 #endif
222
223 // Sorted //
224 BENCHMARK_CAPTURE(BM_Find,
225 unordered_set_sorted_uint32,
226 std::unordered_set<uint32_t>{},
227 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
228
229 BENCHMARK_CAPTURE(BM_FindRehash,
230 unordered_set_sorted_uint32,
231 std::unordered_set<uint32_t, UInt32Hash2>{},
232 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
233
234 // Sorted Ascending //
235 BENCHMARK_CAPTURE(BM_Find,
236 unordered_set_sorted_large_uint64,
237 std::unordered_set<uint64_t>{},
238 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
239
240 BENCHMARK_CAPTURE(BM_FindRehash,
241 unordered_set_sorted_large_uint64,
242 std::unordered_set<uint64_t, UInt64Hash>{},
243 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
244
245
246 // Top Bits //
247 BENCHMARK_CAPTURE(BM_Find,
248 unordered_set_top_bits_uint64,
249 std::unordered_set<uint64_t>{},
250 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
251
252 BENCHMARK_CAPTURE(BM_FindRehash,
253 unordered_set_top_bits_uint64,
254 std::unordered_set<uint64_t, UInt64Hash>{},
255 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
256
257 // String //
258 BENCHMARK_CAPTURE(BM_Find,
259 unordered_set_string,
260 std::unordered_set<std::string>{},
261 getRandomStringInputs)->Arg(TestNumInputs);
262
263 BENCHMARK_CAPTURE(BM_FindRehash,
264 unordered_set_string,
265 std::unordered_set<std::string>{},
266 getRandomStringInputs)->Arg(TestNumInputs);
267
268 ///////////////////////////////////////////////////////////////////////////////
269 BENCHMARK_CAPTURE(BM_InsertDuplicate,
270 unordered_set_int,
271 std::unordered_set<int>{},
272 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
273 BENCHMARK_CAPTURE(BM_InsertDuplicate,
274 unordered_set_string,
275 std::unordered_set<std::string>{},
276 getRandomStringInputs)->Arg(TestNumInputs);
277
278 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
279 unordered_set_int,
280 std::unordered_set<int>{},
281 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
282 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
283 unordered_set_string,
284 std::unordered_set<std::string>{},
285 getRandomStringInputs)->Arg(TestNumInputs);
286
287 BENCHMARK_CAPTURE(BM_InsertDuplicate,
288 unordered_set_int_insert_arg,
289 std::unordered_set<int>{},
290 getRandomIntegerInputs<int>)->Arg(TestNumInputs);
291 BENCHMARK_CAPTURE(BM_InsertDuplicate,
292 unordered_set_string_insert_arg,
293 std::unordered_set<std::string>{},
294 getRandomStringInputs)->Arg(TestNumInputs);
295
296 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
297 unordered_set_int_insert_arg,
298 std::unordered_set<int>{},
299 getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
300
301 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
302 unordered_set_string_arg,
303 std::unordered_set<std::string>{},
304 getRandomCStringInputs)->Arg(TestNumInputs);
305
306 BENCHMARK_MAIN();
307