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
14using namespace ContainerBenchmarks;
15
16constexpr std::size_t TestNumInputs = 1024;
17
18template <class _Size>
19inline TEST_ALWAYS_INLINE
20_Size loadword(const void* __p) {
21    _Size __r;
22    std::memcpy(&__r, __p, sizeof(__r));
23    return __r;
24}
25
26inline TEST_ALWAYS_INLINE
27std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
28    return (__val >> __shift) | (__val << (64 - __shift));
29}
30
31inline TEST_ALWAYS_INLINE
32std::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
43template <std::size_t _Len>
44inline TEST_ALWAYS_INLINE
45std::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
52struct UInt32Hash {
53  UInt32Hash() = default;
54  inline TEST_ALWAYS_INLINE
55  std::size_t operator()(uint32_t data) const {
56      return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
57  }
58};
59
60struct UInt64Hash {
61  UInt64Hash() = default;
62  inline TEST_ALWAYS_INLINE
63  std::size_t operator()(uint64_t data) const {
64      return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
65  }
66};
67
68struct UInt128Hash {
69  UInt128Hash() = default;
70  inline TEST_ALWAYS_INLINE
71  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
79struct UInt32Hash2 {
80  UInt32Hash2() = default;
81  inline TEST_ALWAYS_INLINE
82  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
99struct UInt64Hash2 {
100  UInt64Hash2() = default;
101  inline TEST_ALWAYS_INLINE
102  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.
114struct SlowStringEq {
115  SlowStringEq() = default;
116  inline TEST_ALWAYS_INLINE
117  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
132template <class HashFn, class GenInputs>
133void 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
146BENCHMARK_CAPTURE(BM_Hash,
147    uint32_random_std_hash,
148    std::hash<uint32_t>{},
149    getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
150
151BENCHMARK_CAPTURE(BM_Hash,
152    uint32_random_custom_hash,
153    UInt32Hash{},
154    getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
155
156BENCHMARK_CAPTURE(BM_Hash,
157    uint32_top_std_hash,
158    std::hash<uint32_t>{},
159    getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
160
161BENCHMARK_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 //
173BENCHMARK_CAPTURE(BM_InsertValue,
174    unordered_set_uint32,
175    std::unordered_set<uint32_t>{},
176    getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
177
178BENCHMARK_CAPTURE(BM_InsertValue,
179    unordered_set_uint32_sorted,
180    std::unordered_set<uint32_t>{},
181    getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
182
183// Top Bytes //
184BENCHMARK_CAPTURE(BM_InsertValue,
185    unordered_set_top_bits_uint32,
186    std::unordered_set<uint32_t>{},
187    getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
188
189BENCHMARK_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 //
195BENCHMARK_CAPTURE(BM_InsertValue,
196    unordered_set_string,
197    std::unordered_set<std::string>{},
198    getRandomStringInputs)->Arg(TestNumInputs);
199
200BENCHMARK_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 //
210BENCHMARK_CAPTURE(BM_Find,
211    unordered_set_random_uint64,
212    std::unordered_set<uint64_t>{},
213    getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
214
215BENCHMARK_CAPTURE(BM_FindRehash,
216    unordered_set_random_uint64,
217    std::unordered_set<uint64_t, UInt64Hash>{},
218    getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
219
220// Sorted //
221BENCHMARK_CAPTURE(BM_Find,
222    unordered_set_sorted_uint64,
223    std::unordered_set<uint64_t>{},
224    getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
225
226BENCHMARK_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
234BENCHMARK_CAPTURE(BM_Find,
235    unordered_set_sorted_uint128,
236    std::unordered_set<__uint128_t, UInt128Hash>{},
237    getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
238
239BENCHMARK_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 //
246BENCHMARK_CAPTURE(BM_Find,
247    unordered_set_sorted_uint32,
248    std::unordered_set<uint32_t>{},
249    getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
250
251BENCHMARK_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 //
257BENCHMARK_CAPTURE(BM_Find,
258    unordered_set_sorted_large_uint64,
259    std::unordered_set<uint64_t>{},
260    getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
261
262BENCHMARK_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 //
269BENCHMARK_CAPTURE(BM_Find,
270    unordered_set_top_bits_uint64,
271    std::unordered_set<uint64_t>{},
272    getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
273
274BENCHMARK_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 //
280BENCHMARK_CAPTURE(BM_Find,
281    unordered_set_string,
282    std::unordered_set<std::string>{},
283    getRandomStringInputs)->Arg(TestNumInputs);
284
285BENCHMARK_CAPTURE(BM_FindRehash,
286    unordered_set_string,
287    std::unordered_set<std::string>{},
288    getRandomStringInputs)->Arg(TestNumInputs);
289
290//----------------------------------------------------------------------------//
291//                         BM_Rehash
292// ---------------------------------------------------------------------------//
293
294BENCHMARK_CAPTURE(BM_Rehash,
295    unordered_set_string_arg,
296    std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
297    getRandomStringInputs)->Arg(TestNumInputs);
298
299BENCHMARK_CAPTURE(BM_Rehash,
300    unordered_set_int_arg,
301    std::unordered_set<int>{},
302    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
303
304///////////////////////////////////////////////////////////////////////////////
305BENCHMARK_CAPTURE(BM_InsertDuplicate,
306    unordered_set_int,
307    std::unordered_set<int>{},
308    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
309BENCHMARK_CAPTURE(BM_InsertDuplicate,
310    unordered_set_string,
311    std::unordered_set<std::string>{},
312    getRandomStringInputs)->Arg(TestNumInputs);
313
314BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
315    unordered_set_int,
316    std::unordered_set<int>{},
317    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
318BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
319    unordered_set_string,
320    std::unordered_set<std::string>{},
321    getRandomStringInputs)->Arg(TestNumInputs);
322
323BENCHMARK_CAPTURE(BM_InsertDuplicate,
324    unordered_set_int_insert_arg,
325    std::unordered_set<int>{},
326    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
327BENCHMARK_CAPTURE(BM_InsertDuplicate,
328    unordered_set_string_insert_arg,
329    std::unordered_set<std::string>{},
330    getRandomStringInputs)->Arg(TestNumInputs);
331
332BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
333    unordered_set_int_insert_arg,
334    std::unordered_set<int>{},
335    getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
336
337BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
338    unordered_set_string_arg,
339    std::unordered_set<std::string>{},
340    getRandomCStringInputs)->Arg(TestNumInputs);
341
342BENCHMARK_MAIN();
343