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
13using namespace ContainerBenchmarks;
14
15constexpr std::size_t TestNumInputs = 1024;
16
17template <class _Size>
18inline __attribute__((__always_inline__))
19_Size loadword(const void* __p) {
20    _Size __r;
21    std::memcpy(&__r, __p, sizeof(__r));
22    return __r;
23}
24
25inline __attribute__((__always_inline__))
26std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
27    return (__val >> __shift) | (__val << (64 - __shift));
28}
29
30inline __attribute__((__always_inline__))
31std::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
42template <std::size_t _Len>
43inline __attribute__((__always_inline__))
44std::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
51struct UInt32Hash {
52  UInt32Hash() = default;
53  inline __attribute__((__always_inline__))
54  std::size_t operator()(uint32_t data) const {
55      return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
56  }
57};
58
59struct UInt64Hash {
60  UInt64Hash() = default;
61  inline __attribute__((__always_inline__))
62  std::size_t operator()(uint64_t data) const {
63      return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
64  }
65};
66
67struct UInt128Hash {
68  UInt128Hash() = default;
69  inline __attribute__((__always_inline__))
70  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
78struct UInt32Hash2 {
79  UInt32Hash2() = default;
80  inline __attribute__((__always_inline__))
81  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
98struct UInt64Hash2 {
99  UInt64Hash2() = default;
100  inline __attribute__((__always_inline__))
101  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
110template <class HashFn, class GenInputs>
111void 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
124BENCHMARK_CAPTURE(BM_Hash,
125    uint32_random_std_hash,
126    std::hash<uint32_t>{},
127    getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
128
129BENCHMARK_CAPTURE(BM_Hash,
130    uint32_random_custom_hash,
131    UInt32Hash{},
132    getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
133
134BENCHMARK_CAPTURE(BM_Hash,
135    uint32_top_std_hash,
136    std::hash<uint32_t>{},
137    getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
138
139BENCHMARK_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 //
151BENCHMARK_CAPTURE(BM_InsertValue,
152    unordered_set_uint32,
153    std::unordered_set<uint32_t>{},
154    getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
155
156BENCHMARK_CAPTURE(BM_InsertValue,
157    unordered_set_uint32_sorted,
158    std::unordered_set<uint32_t>{},
159    getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
160
161// Top Bytes //
162BENCHMARK_CAPTURE(BM_InsertValue,
163    unordered_set_top_bits_uint32,
164    std::unordered_set<uint32_t>{},
165    getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
166
167BENCHMARK_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 //
173BENCHMARK_CAPTURE(BM_InsertValue,
174    unordered_set_string,
175    std::unordered_set<std::string>{},
176    getRandomStringInputs)->Arg(TestNumInputs);
177
178BENCHMARK_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 //
188BENCHMARK_CAPTURE(BM_Find,
189    unordered_set_random_uint64,
190    std::unordered_set<uint64_t>{},
191    getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
192
193BENCHMARK_CAPTURE(BM_FindRehash,
194    unordered_set_random_uint64,
195    std::unordered_set<uint64_t, UInt64Hash>{},
196    getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
197
198// Sorted //
199BENCHMARK_CAPTURE(BM_Find,
200    unordered_set_sorted_uint64,
201    std::unordered_set<uint64_t>{},
202    getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
203
204BENCHMARK_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
212BENCHMARK_CAPTURE(BM_Find,
213    unordered_set_sorted_uint128,
214    std::unordered_set<__uint128_t, UInt128Hash>{},
215    getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
216
217BENCHMARK_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 //
224BENCHMARK_CAPTURE(BM_Find,
225    unordered_set_sorted_uint32,
226    std::unordered_set<uint32_t>{},
227    getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
228
229BENCHMARK_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 //
235BENCHMARK_CAPTURE(BM_Find,
236    unordered_set_sorted_large_uint64,
237    std::unordered_set<uint64_t>{},
238    getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
239
240BENCHMARK_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 //
247BENCHMARK_CAPTURE(BM_Find,
248    unordered_set_top_bits_uint64,
249    std::unordered_set<uint64_t>{},
250    getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
251
252BENCHMARK_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 //
258BENCHMARK_CAPTURE(BM_Find,
259    unordered_set_string,
260    std::unordered_set<std::string>{},
261    getRandomStringInputs)->Arg(TestNumInputs);
262
263BENCHMARK_CAPTURE(BM_FindRehash,
264    unordered_set_string,
265    std::unordered_set<std::string>{},
266    getRandomStringInputs)->Arg(TestNumInputs);
267
268///////////////////////////////////////////////////////////////////////////////
269BENCHMARK_CAPTURE(BM_InsertDuplicate,
270    unordered_set_int,
271    std::unordered_set<int>{},
272    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
273BENCHMARK_CAPTURE(BM_InsertDuplicate,
274    unordered_set_string,
275    std::unordered_set<std::string>{},
276    getRandomStringInputs)->Arg(TestNumInputs);
277
278BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
279    unordered_set_int,
280    std::unordered_set<int>{},
281    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
282BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
283    unordered_set_string,
284    std::unordered_set<std::string>{},
285    getRandomStringInputs)->Arg(TestNumInputs);
286
287BENCHMARK_CAPTURE(BM_InsertDuplicate,
288    unordered_set_int_insert_arg,
289    std::unordered_set<int>{},
290    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
291BENCHMARK_CAPTURE(BM_InsertDuplicate,
292    unordered_set_string_insert_arg,
293    std::unordered_set<std::string>{},
294    getRandomStringInputs)->Arg(TestNumInputs);
295
296BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
297    unordered_set_int_insert_arg,
298    std::unordered_set<int>{},
299    getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
300
301BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
302    unordered_set_string_arg,
303    std::unordered_set<std::string>{},
304    getRandomCStringInputs)->Arg(TestNumInputs);
305
306BENCHMARK_MAIN();
307