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