llvm-project
338 строк · 12.1 Кб
1#include <cstdint>
2#include <cstdlib>
3#include <cstring>
4#include <functional>
5#include <unordered_set>
6#include <vector>
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 _Size loadword(const void* __p) {
20_Size __r;
21std::memcpy(&__r, __p, sizeof(__r));
22return __r;
23}
24
25inline TEST_ALWAYS_INLINE std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
26return (__val >> __shift) | (__val << (64 - __shift));
27}
28
29inline TEST_ALWAYS_INLINE std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
30const std::size_t __mul = 0x9ddfea08eb382d69ULL;
31std::size_t __a = (__u ^ __v) * __mul;
32__a ^= (__a >> 47);
33std::size_t __b = (__v ^ __a) * __mul;
34__b ^= (__b >> 47);
35__b *= __mul;
36return __b;
37}
38
39template <std::size_t _Len>
40inline TEST_ALWAYS_INLINE std::size_t hash_len_0_to_8(const char* __s) {
41static_assert(_Len == 4 || _Len == 8, "");
42const uint64_t __a = loadword<uint32_t>(__s);
43const uint64_t __b = loadword<uint32_t>(__s + _Len - 4);
44return hash_len_16(_Len + (__a << 3), __b);
45}
46
47struct UInt32Hash {
48UInt32Hash() = default;
49inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const {
50return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
51}
52};
53
54struct UInt64Hash {
55UInt64Hash() = default;
56inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const {
57return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
58}
59};
60
61struct UInt128Hash {
62UInt128Hash() = default;
63inline TEST_ALWAYS_INLINE std::size_t operator()(__uint128_t data) const {
64const __uint128_t __mask = static_cast<std::size_t>(-1);
65const std::size_t __a = (std::size_t)(data & __mask);
66const std::size_t __b = (std::size_t)((data & (__mask << 64)) >> 64);
67return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b;
68}
69};
70
71struct UInt32Hash2 {
72UInt32Hash2() = default;
73inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const {
74const uint32_t __m = 0x5bd1e995;
75const uint32_t __r = 24;
76uint32_t __h = 4;
77uint32_t __k = data;
78__k *= __m;
79__k ^= __k >> __r;
80__k *= __m;
81__h *= __m;
82__h ^= __k;
83__h ^= __h >> 13;
84__h *= __m;
85__h ^= __h >> 15;
86return __h;
87}
88};
89
90struct UInt64Hash2 {
91UInt64Hash2() = default;
92inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const {
93return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
94}
95};
96
97// The sole purpose of this comparator is to be used in BM_Rehash, where
98// we need something slow enough to be easily noticable in benchmark results.
99// The default implementation of operator== for strings seems to be a little
100// too fast for that specific benchmark to reliably show a noticeable
101// improvement, but unoptimized bytewise comparison fits just right.
102// Early return is there just for convenience, since we only compare strings
103// of equal length in BM_Rehash.
104struct SlowStringEq {
105SlowStringEq() = default;
106inline TEST_ALWAYS_INLINE bool operator()(const std::string& lhs, const std::string& rhs) const {
107if (lhs.size() != rhs.size())
108return false;
109
110bool eq = true;
111for (size_t i = 0; i < lhs.size(); ++i) {
112eq &= lhs[i] == rhs[i];
113}
114return eq;
115}
116};
117
118//----------------------------------------------------------------------------//
119// BM_Hash
120// ---------------------------------------------------------------------------//
121
122template <class HashFn, class GenInputs>
123void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
124auto in = gen(st.range(0));
125const auto end = in.data() + in.size();
126std::size_t last_hash = 0;
127benchmark::DoNotOptimize(&last_hash);
128while (st.KeepRunning()) {
129for (auto it = in.data(); it != end; ++it) {
130benchmark::DoNotOptimize(last_hash += fn(*it));
131}
132benchmark::ClobberMemory();
133}
134}
135
136BENCHMARK_CAPTURE(BM_Hash, uint32_random_std_hash, std::hash<uint32_t>{}, getRandomIntegerInputs<uint32_t>)
137->Arg(TestNumInputs);
138
139BENCHMARK_CAPTURE(BM_Hash, uint32_random_custom_hash, UInt32Hash{}, getRandomIntegerInputs<uint32_t>)
140->Arg(TestNumInputs);
141
142BENCHMARK_CAPTURE(BM_Hash, uint32_top_std_hash, std::hash<uint32_t>{}, getSortedTopBitsIntegerInputs<uint32_t>)
143->Arg(TestNumInputs);
144
145BENCHMARK_CAPTURE(BM_Hash, uint32_top_custom_hash, UInt32Hash{}, getSortedTopBitsIntegerInputs<uint32_t>)
146->Arg(TestNumInputs);
147
148//----------------------------------------------------------------------------//
149// BM_InsertValue
150// ---------------------------------------------------------------------------//
151
152// Sorted Ascending //
153BENCHMARK_CAPTURE(
154BM_InsertValue, unordered_set_uint32, std::unordered_set<uint32_t>{}, getRandomIntegerInputs<uint32_t>)
155->Arg(TestNumInputs);
156
157BENCHMARK_CAPTURE(
158BM_InsertValue, unordered_set_uint32_sorted, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
159->Arg(TestNumInputs);
160
161// Top Bytes //
162BENCHMARK_CAPTURE(BM_InsertValue,
163unordered_set_top_bits_uint32,
164std::unordered_set<uint32_t>{},
165getSortedTopBitsIntegerInputs<uint32_t>)
166->Arg(TestNumInputs);
167
168BENCHMARK_CAPTURE(BM_InsertValueRehash,
169unordered_set_top_bits_uint32,
170std::unordered_set<uint32_t, UInt32Hash>{},
171getSortedTopBitsIntegerInputs<uint32_t>)
172->Arg(TestNumInputs);
173
174// String //
175BENCHMARK_CAPTURE(BM_InsertValue, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
176->Arg(TestNumInputs);
177
178BENCHMARK_CAPTURE(BM_InsertValueRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
179->Arg(TestNumInputs);
180
181// Prefixed String //
182BENCHMARK_CAPTURE(
183BM_InsertValue, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
184->Arg(TestNumInputs);
185
186BENCHMARK_CAPTURE(BM_InsertValueRehash,
187unordered_set_prefixed_string,
188std::unordered_set<std::string>{},
189getPrefixedRandomStringInputs)
190->Arg(TestNumInputs);
191
192//----------------------------------------------------------------------------//
193// BM_Find
194// ---------------------------------------------------------------------------//
195
196// Random //
197BENCHMARK_CAPTURE(
198BM_Find, unordered_set_random_uint64, std::unordered_set<uint64_t>{}, getRandomIntegerInputs<uint64_t>)
199->Arg(TestNumInputs);
200
201BENCHMARK_CAPTURE(BM_FindRehash,
202unordered_set_random_uint64,
203std::unordered_set<uint64_t, UInt64Hash>{},
204getRandomIntegerInputs<uint64_t>)
205->Arg(TestNumInputs);
206
207// Sorted //
208BENCHMARK_CAPTURE(
209BM_Find, unordered_set_sorted_uint64, std::unordered_set<uint64_t>{}, getSortedIntegerInputs<uint64_t>)
210->Arg(TestNumInputs);
211
212BENCHMARK_CAPTURE(BM_FindRehash,
213unordered_set_sorted_uint64,
214std::unordered_set<uint64_t, UInt64Hash>{},
215getSortedIntegerInputs<uint64_t>)
216->Arg(TestNumInputs);
217
218// Sorted //
219BENCHMARK_CAPTURE(BM_Find,
220unordered_set_sorted_uint128,
221std::unordered_set<__uint128_t, UInt128Hash>{},
222getSortedTopBitsIntegerInputs<__uint128_t>)
223->Arg(TestNumInputs);
224
225BENCHMARK_CAPTURE(BM_FindRehash,
226unordered_set_sorted_uint128,
227std::unordered_set<__uint128_t, UInt128Hash>{},
228getSortedTopBitsIntegerInputs<__uint128_t>)
229->Arg(TestNumInputs);
230
231// Sorted //
232BENCHMARK_CAPTURE(
233BM_Find, unordered_set_sorted_uint32, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
234->Arg(TestNumInputs);
235
236BENCHMARK_CAPTURE(BM_FindRehash,
237unordered_set_sorted_uint32,
238std::unordered_set<uint32_t, UInt32Hash2>{},
239getSortedIntegerInputs<uint32_t>)
240->Arg(TestNumInputs);
241
242// Sorted Ascending //
243BENCHMARK_CAPTURE(
244BM_Find, unordered_set_sorted_large_uint64, std::unordered_set<uint64_t>{}, getSortedLargeIntegerInputs<uint64_t>)
245->Arg(TestNumInputs);
246
247BENCHMARK_CAPTURE(BM_FindRehash,
248unordered_set_sorted_large_uint64,
249std::unordered_set<uint64_t, UInt64Hash>{},
250getSortedLargeIntegerInputs<uint64_t>)
251->Arg(TestNumInputs);
252
253// Top Bits //
254BENCHMARK_CAPTURE(
255BM_Find, unordered_set_top_bits_uint64, std::unordered_set<uint64_t>{}, getSortedTopBitsIntegerInputs<uint64_t>)
256->Arg(TestNumInputs);
257
258BENCHMARK_CAPTURE(BM_FindRehash,
259unordered_set_top_bits_uint64,
260std::unordered_set<uint64_t, UInt64Hash>{},
261getSortedTopBitsIntegerInputs<uint64_t>)
262->Arg(TestNumInputs);
263
264// String //
265BENCHMARK_CAPTURE(BM_Find, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
266->Arg(TestNumInputs);
267
268BENCHMARK_CAPTURE(BM_FindRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
269->Arg(TestNumInputs);
270
271// Prefixed String //
272BENCHMARK_CAPTURE(
273BM_Find, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
274->Arg(TestNumInputs);
275
276BENCHMARK_CAPTURE(
277BM_FindRehash, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
278->Arg(TestNumInputs);
279
280//----------------------------------------------------------------------------//
281// BM_Rehash
282// ---------------------------------------------------------------------------//
283
284BENCHMARK_CAPTURE(BM_Rehash,
285unordered_set_string_arg,
286std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
287getRandomStringInputs)
288->Arg(TestNumInputs);
289
290BENCHMARK_CAPTURE(BM_Rehash, unordered_set_int_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
291->Arg(TestNumInputs);
292
293//----------------------------------------------------------------------------//
294// BM_Compare
295// ---------------------------------------------------------------------------//
296
297BENCHMARK_CAPTURE(
298BM_Compare_same_container, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
299->Arg(TestNumInputs);
300
301BENCHMARK_CAPTURE(BM_Compare_same_container, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
302->Arg(TestNumInputs);
303
304BENCHMARK_CAPTURE(
305BM_Compare_different_containers, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
306->Arg(TestNumInputs);
307
308BENCHMARK_CAPTURE(
309BM_Compare_different_containers, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
310->Arg(TestNumInputs);
311
312///////////////////////////////////////////////////////////////////////////////
313BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
314->Arg(TestNumInputs);
315BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
316->Arg(TestNumInputs);
317
318BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
319->Arg(TestNumInputs);
320BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
321->Arg(TestNumInputs);
322
323BENCHMARK_CAPTURE(
324BM_InsertDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
325->Arg(TestNumInputs);
326BENCHMARK_CAPTURE(
327BM_InsertDuplicate, unordered_set_string_insert_arg, std::unordered_set<std::string>{}, getRandomStringInputs)
328->Arg(TestNumInputs);
329
330BENCHMARK_CAPTURE(
331BM_EmplaceDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<unsigned>)
332->Arg(TestNumInputs);
333
334BENCHMARK_CAPTURE(
335BM_EmplaceDuplicate, unordered_set_string_arg, std::unordered_set<std::string>{}, getRandomCStringInputs)
336->Arg(TestNumInputs);
337
338BENCHMARK_MAIN();
339