/
rizz
/
llvm-project
GigaCode
beta
ОбзорЦентр заботыВойти

llvm-project

Форк
0
Ветки: 518Коммиты: 504434Теги: 268
llvm-project
/libcxx
/benchmarks
/
unordered_set_operations.bench.cpp 
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


14
using namespace ContainerBenchmarks;
15


16
constexpr std::size_t TestNumInputs = 1024;
17


18
template <class _Size>
19
inline TEST_ALWAYS_INLINE _Size loadword(const void* __p) {
20
  _Size __r;
21
  std::memcpy(&__r, __p, sizeof(__r));
22
  return __r;
23
}
24


25
inline TEST_ALWAYS_INLINE std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
26
  return (__val >> __shift) | (__val << (64 - __shift));
27
}
28


29
inline TEST_ALWAYS_INLINE std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
30
  const std::size_t __mul = 0x9ddfea08eb382d69ULL;
31
  std::size_t __a         = (__u ^ __v) * __mul;
32
  __a ^= (__a >> 47);
33
  std::size_t __b = (__v ^ __a) * __mul;
34
  __b ^= (__b >> 47);
35
  __b *= __mul;
36
  return __b;
37
}
38


39
template <std::size_t _Len>
40
inline TEST_ALWAYS_INLINE std::size_t hash_len_0_to_8(const char* __s) {
41
  static_assert(_Len == 4 || _Len == 8, "");
42
  const uint64_t __a = loadword<uint32_t>(__s);
43
  const uint64_t __b = loadword<uint32_t>(__s + _Len - 4);
44
  return hash_len_16(_Len + (__a << 3), __b);
45
}
46


47
struct UInt32Hash {
48
  UInt32Hash() = default;
49
  inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const {
50
    return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
51
  }
52
};
53


54
struct UInt64Hash {
55
  UInt64Hash() = default;
56
  inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const {
57
    return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
58
  }
59
};
60


61
struct UInt128Hash {
62
  UInt128Hash() = default;
63
  inline TEST_ALWAYS_INLINE std::size_t operator()(__uint128_t data) const {
64
    const __uint128_t __mask = static_cast<std::size_t>(-1);
65
    const std::size_t __a    = (std::size_t)(data & __mask);
66
    const std::size_t __b    = (std::size_t)((data & (__mask << 64)) >> 64);
67
    return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b;
68
  }
69
};
70


71
struct UInt32Hash2 {
72
  UInt32Hash2() = default;
73
  inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const {
74
    const uint32_t __m = 0x5bd1e995;
75
    const uint32_t __r = 24;
76
    uint32_t __h       = 4;
77
    uint32_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;
86
    return __h;
87
  }
88
};
89


90
struct UInt64Hash2 {
91
  UInt64Hash2() = default;
92
  inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const {
93
    return 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.
104
struct SlowStringEq {
105
  SlowStringEq() = default;
106
  inline TEST_ALWAYS_INLINE bool operator()(const std::string& lhs, const std::string& rhs) const {
107
    if (lhs.size() != rhs.size())
108
      return false;
109


110
    bool eq = true;
111
    for (size_t i = 0; i < lhs.size(); ++i) {
112
      eq &= lhs[i] == rhs[i];
113
    }
114
    return eq;
115
  }
116
};
117


118
//----------------------------------------------------------------------------//
119
//                               BM_Hash
120
// ---------------------------------------------------------------------------//
121


122
template <class HashFn, class GenInputs>
123
void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
124
  auto in               = gen(st.range(0));
125
  const auto end        = in.data() + in.size();
126
  std::size_t last_hash = 0;
127
  benchmark::DoNotOptimize(&last_hash);
128
  while (st.KeepRunning()) {
129
    for (auto it = in.data(); it != end; ++it) {
130
      benchmark::DoNotOptimize(last_hash += fn(*it));
131
    }
132
    benchmark::ClobberMemory();
133
  }
134
}
135


136
BENCHMARK_CAPTURE(BM_Hash, uint32_random_std_hash, std::hash<uint32_t>{}, getRandomIntegerInputs<uint32_t>)
137
    ->Arg(TestNumInputs);
138


139
BENCHMARK_CAPTURE(BM_Hash, uint32_random_custom_hash, UInt32Hash{}, getRandomIntegerInputs<uint32_t>)
140
    ->Arg(TestNumInputs);
141


142
BENCHMARK_CAPTURE(BM_Hash, uint32_top_std_hash, std::hash<uint32_t>{}, getSortedTopBitsIntegerInputs<uint32_t>)
143
    ->Arg(TestNumInputs);
144


145
BENCHMARK_CAPTURE(BM_Hash, uint32_top_custom_hash, UInt32Hash{}, getSortedTopBitsIntegerInputs<uint32_t>)
146
    ->Arg(TestNumInputs);
147


148
//----------------------------------------------------------------------------//
149
//                       BM_InsertValue
150
// ---------------------------------------------------------------------------//
151


152
// Sorted Ascending //
153
BENCHMARK_CAPTURE(
154
    BM_InsertValue, unordered_set_uint32, std::unordered_set<uint32_t>{}, getRandomIntegerInputs<uint32_t>)
155
    ->Arg(TestNumInputs);
156


157
BENCHMARK_CAPTURE(
158
    BM_InsertValue, unordered_set_uint32_sorted, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
159
    ->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>)
166
    ->Arg(TestNumInputs);
167


168
BENCHMARK_CAPTURE(BM_InsertValueRehash,
169
                  unordered_set_top_bits_uint32,
170
                  std::unordered_set<uint32_t, UInt32Hash>{},
171
                  getSortedTopBitsIntegerInputs<uint32_t>)
172
    ->Arg(TestNumInputs);
173


174
// String //
175
BENCHMARK_CAPTURE(BM_InsertValue, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
176
    ->Arg(TestNumInputs);
177


178
BENCHMARK_CAPTURE(BM_InsertValueRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
179
    ->Arg(TestNumInputs);
180


181
// Prefixed String //
182
BENCHMARK_CAPTURE(
183
    BM_InsertValue, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
184
    ->Arg(TestNumInputs);
185


186
BENCHMARK_CAPTURE(BM_InsertValueRehash,
187
                  unordered_set_prefixed_string,
188
                  std::unordered_set<std::string>{},
189
                  getPrefixedRandomStringInputs)
190
    ->Arg(TestNumInputs);
191


192
//----------------------------------------------------------------------------//
193
//                         BM_Find
194
// ---------------------------------------------------------------------------//
195


196
// Random //
197
BENCHMARK_CAPTURE(
198
    BM_Find, unordered_set_random_uint64, std::unordered_set<uint64_t>{}, getRandomIntegerInputs<uint64_t>)
199
    ->Arg(TestNumInputs);
200


201
BENCHMARK_CAPTURE(BM_FindRehash,
202
                  unordered_set_random_uint64,
203
                  std::unordered_set<uint64_t, UInt64Hash>{},
204
                  getRandomIntegerInputs<uint64_t>)
205
    ->Arg(TestNumInputs);
206


207
// Sorted //
208
BENCHMARK_CAPTURE(
209
    BM_Find, unordered_set_sorted_uint64, std::unordered_set<uint64_t>{}, getSortedIntegerInputs<uint64_t>)
210
    ->Arg(TestNumInputs);
211


212
BENCHMARK_CAPTURE(BM_FindRehash,
213
                  unordered_set_sorted_uint64,
214
                  std::unordered_set<uint64_t, UInt64Hash>{},
215
                  getSortedIntegerInputs<uint64_t>)
216
    ->Arg(TestNumInputs);
217


218
// Sorted //
219
BENCHMARK_CAPTURE(BM_Find,
220
                  unordered_set_sorted_uint128,
221
                  std::unordered_set<__uint128_t, UInt128Hash>{},
222
                  getSortedTopBitsIntegerInputs<__uint128_t>)
223
    ->Arg(TestNumInputs);
224


225
BENCHMARK_CAPTURE(BM_FindRehash,
226
                  unordered_set_sorted_uint128,
227
                  std::unordered_set<__uint128_t, UInt128Hash>{},
228
                  getSortedTopBitsIntegerInputs<__uint128_t>)
229
    ->Arg(TestNumInputs);
230


231
// Sorted //
232
BENCHMARK_CAPTURE(
233
    BM_Find, unordered_set_sorted_uint32, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
234
    ->Arg(TestNumInputs);
235


236
BENCHMARK_CAPTURE(BM_FindRehash,
237
                  unordered_set_sorted_uint32,
238
                  std::unordered_set<uint32_t, UInt32Hash2>{},
239
                  getSortedIntegerInputs<uint32_t>)
240
    ->Arg(TestNumInputs);
241


242
// Sorted Ascending //
243
BENCHMARK_CAPTURE(
244
    BM_Find, unordered_set_sorted_large_uint64, std::unordered_set<uint64_t>{}, getSortedLargeIntegerInputs<uint64_t>)
245
    ->Arg(TestNumInputs);
246


247
BENCHMARK_CAPTURE(BM_FindRehash,
248
                  unordered_set_sorted_large_uint64,
249
                  std::unordered_set<uint64_t, UInt64Hash>{},
250
                  getSortedLargeIntegerInputs<uint64_t>)
251
    ->Arg(TestNumInputs);
252


253
// Top Bits //
254
BENCHMARK_CAPTURE(
255
    BM_Find, unordered_set_top_bits_uint64, std::unordered_set<uint64_t>{}, getSortedTopBitsIntegerInputs<uint64_t>)
256
    ->Arg(TestNumInputs);
257


258
BENCHMARK_CAPTURE(BM_FindRehash,
259
                  unordered_set_top_bits_uint64,
260
                  std::unordered_set<uint64_t, UInt64Hash>{},
261
                  getSortedTopBitsIntegerInputs<uint64_t>)
262
    ->Arg(TestNumInputs);
263


264
// String //
265
BENCHMARK_CAPTURE(BM_Find, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
266
    ->Arg(TestNumInputs);
267


268
BENCHMARK_CAPTURE(BM_FindRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
269
    ->Arg(TestNumInputs);
270


271
// Prefixed String //
272
BENCHMARK_CAPTURE(
273
    BM_Find, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
274
    ->Arg(TestNumInputs);
275


276
BENCHMARK_CAPTURE(
277
    BM_FindRehash, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
278
    ->Arg(TestNumInputs);
279


280
//----------------------------------------------------------------------------//
281
//                         BM_Rehash
282
// ---------------------------------------------------------------------------//
283


284
BENCHMARK_CAPTURE(BM_Rehash,
285
                  unordered_set_string_arg,
286
                  std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
287
                  getRandomStringInputs)
288
    ->Arg(TestNumInputs);
289


290
BENCHMARK_CAPTURE(BM_Rehash, unordered_set_int_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
291
    ->Arg(TestNumInputs);
292


293
//----------------------------------------------------------------------------//
294
//                         BM_Compare
295
// ---------------------------------------------------------------------------//
296


297
BENCHMARK_CAPTURE(
298
    BM_Compare_same_container, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
299
    ->Arg(TestNumInputs);
300


301
BENCHMARK_CAPTURE(BM_Compare_same_container, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
302
    ->Arg(TestNumInputs);
303


304
BENCHMARK_CAPTURE(
305
    BM_Compare_different_containers, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
306
    ->Arg(TestNumInputs);
307


308
BENCHMARK_CAPTURE(
309
    BM_Compare_different_containers, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
310
    ->Arg(TestNumInputs);
311


312
///////////////////////////////////////////////////////////////////////////////
313
BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
314
    ->Arg(TestNumInputs);
315
BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
316
    ->Arg(TestNumInputs);
317


318
BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
319
    ->Arg(TestNumInputs);
320
BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
321
    ->Arg(TestNumInputs);
322


323
BENCHMARK_CAPTURE(
324
    BM_InsertDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
325
    ->Arg(TestNumInputs);
326
BENCHMARK_CAPTURE(
327
    BM_InsertDuplicate, unordered_set_string_insert_arg, std::unordered_set<std::string>{}, getRandomStringInputs)
328
    ->Arg(TestNumInputs);
329


330
BENCHMARK_CAPTURE(
331
    BM_EmplaceDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<unsigned>)
332
    ->Arg(TestNumInputs);
333


334
BENCHMARK_CAPTURE(
335
    BM_EmplaceDuplicate, unordered_set_string_arg, std::unordered_set<std::string>{}, getRandomCStringInputs)
336
    ->Arg(TestNumInputs);
337


338
BENCHMARK_MAIN();
339

Использование cookies

Мы используем файлы cookie в соответствии с Политикой конфиденциальности и Политикой использования cookies.

Нажимая кнопку «Принимаю», Вы даете АО «СберТех» согласие на обработку Ваших персональных данных в целях совершенствования нашего веб-сайта и Сервиса GitVerse, а также повышения удобства их использования.

Запретить использование cookies Вы можете самостоятельно в настройках Вашего браузера.