xref: /openbsd-src/gnu/llvm/libcxx/benchmarks/unordered_set_operations.bench.cpp (revision 4bdff4bed0e3d54e55670334c7d0077db4170f86)
146035553Spatrick #include <unordered_set>
246035553Spatrick #include <vector>
346035553Spatrick #include <functional>
446035553Spatrick #include <cstdint>
546035553Spatrick #include <cstdlib>
646035553Spatrick #include <cstring>
746035553Spatrick 
846035553Spatrick #include "benchmark/benchmark.h"
946035553Spatrick 
1046035553Spatrick #include "ContainerBenchmarks.h"
1146035553Spatrick #include "GenerateInput.h"
1246035553Spatrick #include "test_macros.h"
1346035553Spatrick 
1446035553Spatrick using namespace ContainerBenchmarks;
1546035553Spatrick 
1646035553Spatrick constexpr std::size_t TestNumInputs = 1024;
1746035553Spatrick 
1846035553Spatrick template <class _Size>
1946035553Spatrick inline TEST_ALWAYS_INLINE
loadword(const void * __p)2046035553Spatrick _Size loadword(const void* __p) {
2146035553Spatrick     _Size __r;
2246035553Spatrick     std::memcpy(&__r, __p, sizeof(__r));
2346035553Spatrick     return __r;
2446035553Spatrick }
2546035553Spatrick 
2646035553Spatrick inline TEST_ALWAYS_INLINE
rotate_by_at_least_1(std::size_t __val,int __shift)2746035553Spatrick std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
2846035553Spatrick     return (__val >> __shift) | (__val << (64 - __shift));
2946035553Spatrick }
3046035553Spatrick 
3146035553Spatrick inline TEST_ALWAYS_INLINE
hash_len_16(std::size_t __u,std::size_t __v)3246035553Spatrick std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
3346035553Spatrick     const  std::size_t __mul = 0x9ddfea08eb382d69ULL;
3446035553Spatrick     std::size_t __a = (__u ^ __v) * __mul;
3546035553Spatrick     __a ^= (__a >> 47);
3646035553Spatrick     std::size_t __b = (__v ^ __a) * __mul;
3746035553Spatrick     __b ^= (__b >> 47);
3846035553Spatrick     __b *= __mul;
3946035553Spatrick     return __b;
4046035553Spatrick }
4146035553Spatrick 
4246035553Spatrick 
4346035553Spatrick template <std::size_t _Len>
4446035553Spatrick inline TEST_ALWAYS_INLINE
hash_len_0_to_8(const char * __s)4546035553Spatrick std::size_t hash_len_0_to_8(const char* __s) {
4646035553Spatrick     static_assert(_Len == 4 || _Len == 8, "");
4746035553Spatrick     const uint64_t __a = loadword<uint32_t>(__s);
4846035553Spatrick     const uint64_t __b = loadword<uint32_t>(__s + _Len - 4);
4946035553Spatrick     return hash_len_16(_Len + (__a << 3), __b);
5046035553Spatrick }
5146035553Spatrick 
5246035553Spatrick struct UInt32Hash {
5346035553Spatrick   UInt32Hash() = default;
5446035553Spatrick   inline TEST_ALWAYS_INLINE
operator ()UInt32Hash5546035553Spatrick   std::size_t operator()(uint32_t data) const {
5646035553Spatrick       return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
5746035553Spatrick   }
5846035553Spatrick };
5946035553Spatrick 
6046035553Spatrick struct UInt64Hash {
6146035553Spatrick   UInt64Hash() = default;
6246035553Spatrick   inline TEST_ALWAYS_INLINE
operator ()UInt64Hash6346035553Spatrick   std::size_t operator()(uint64_t data) const {
6446035553Spatrick       return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
6546035553Spatrick   }
6646035553Spatrick };
6746035553Spatrick 
6846035553Spatrick struct UInt128Hash {
6946035553Spatrick   UInt128Hash() = default;
7046035553Spatrick   inline TEST_ALWAYS_INLINE
operator ()UInt128Hash7146035553Spatrick   std::size_t operator()(__uint128_t data) const {
7246035553Spatrick       const __uint128_t __mask = static_cast<std::size_t>(-1);
7346035553Spatrick       const std::size_t __a = (std::size_t)(data & __mask);
7446035553Spatrick       const std::size_t __b = (std::size_t)((data & (__mask << 64)) >> 64);
7546035553Spatrick       return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b;
7646035553Spatrick   }
7746035553Spatrick };
7846035553Spatrick 
7946035553Spatrick struct UInt32Hash2 {
8046035553Spatrick   UInt32Hash2() = default;
8146035553Spatrick   inline TEST_ALWAYS_INLINE
operator ()UInt32Hash28246035553Spatrick   std::size_t operator()(uint32_t data) const {
8346035553Spatrick       const uint32_t __m = 0x5bd1e995;
8446035553Spatrick       const uint32_t __r = 24;
8546035553Spatrick       uint32_t __h = 4;
8646035553Spatrick       uint32_t __k = data;
8746035553Spatrick         __k *= __m;
8846035553Spatrick         __k ^= __k >> __r;
8946035553Spatrick         __k *= __m;
9046035553Spatrick         __h *= __m;
9146035553Spatrick         __h ^= __k;
9246035553Spatrick         __h ^= __h >> 13;
9346035553Spatrick         __h *= __m;
9446035553Spatrick         __h ^= __h >> 15;
9546035553Spatrick     return __h;
9646035553Spatrick   }
9746035553Spatrick };
9846035553Spatrick 
9946035553Spatrick struct UInt64Hash2 {
10046035553Spatrick   UInt64Hash2() = default;
10146035553Spatrick   inline TEST_ALWAYS_INLINE
operator ()UInt64Hash210246035553Spatrick   std::size_t operator()(uint64_t data) const {
10346035553Spatrick       return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
10446035553Spatrick   }
10546035553Spatrick };
10646035553Spatrick 
107*4bdff4beSrobert // The sole purpose of this comparator is to be used in BM_Rehash, where
108*4bdff4beSrobert // we need something slow enough to be easily noticable in benchmark results.
109*4bdff4beSrobert // The default implementation of operator== for strings seems to be a little
110*4bdff4beSrobert // too fast for that specific benchmark to reliably show a noticeable
111*4bdff4beSrobert // improvement, but unoptimized bytewise comparison fits just right.
112*4bdff4beSrobert // Early return is there just for convenience, since we only compare strings
113*4bdff4beSrobert // of equal length in BM_Rehash.
114*4bdff4beSrobert struct SlowStringEq {
115*4bdff4beSrobert   SlowStringEq() = default;
116*4bdff4beSrobert   inline TEST_ALWAYS_INLINE
operator ()SlowStringEq117*4bdff4beSrobert   bool operator()(const std::string& lhs, const std::string& rhs) const {
118*4bdff4beSrobert       if (lhs.size() != rhs.size()) return false;
119*4bdff4beSrobert 
120*4bdff4beSrobert       bool eq = true;
121*4bdff4beSrobert       for (size_t i = 0; i < lhs.size(); ++i) {
122*4bdff4beSrobert           eq &= lhs[i] == rhs[i];
123*4bdff4beSrobert       }
124*4bdff4beSrobert       return eq;
125*4bdff4beSrobert   }
126*4bdff4beSrobert };
127*4bdff4beSrobert 
12846035553Spatrick //----------------------------------------------------------------------------//
12946035553Spatrick //                               BM_Hash
13046035553Spatrick // ---------------------------------------------------------------------------//
13146035553Spatrick 
13246035553Spatrick template <class HashFn, class GenInputs>
BM_Hash(benchmark::State & st,HashFn fn,GenInputs gen)13346035553Spatrick void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
13446035553Spatrick     auto in = gen(st.range(0));
13546035553Spatrick     const auto end = in.data() + in.size();
13646035553Spatrick     std::size_t last_hash = 0;
13746035553Spatrick     benchmark::DoNotOptimize(&last_hash);
13846035553Spatrick     while (st.KeepRunning()) {
13946035553Spatrick         for (auto it = in.data(); it != end; ++it) {
14046035553Spatrick             benchmark::DoNotOptimize(last_hash += fn(*it));
14146035553Spatrick         }
14246035553Spatrick         benchmark::ClobberMemory();
14346035553Spatrick     }
14446035553Spatrick }
14546035553Spatrick 
14646035553Spatrick BENCHMARK_CAPTURE(BM_Hash,
14746035553Spatrick     uint32_random_std_hash,
14846035553Spatrick     std::hash<uint32_t>{},
14946035553Spatrick     getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
15046035553Spatrick 
15146035553Spatrick BENCHMARK_CAPTURE(BM_Hash,
15246035553Spatrick     uint32_random_custom_hash,
15346035553Spatrick     UInt32Hash{},
15446035553Spatrick     getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
15546035553Spatrick 
15646035553Spatrick BENCHMARK_CAPTURE(BM_Hash,
15746035553Spatrick     uint32_top_std_hash,
15846035553Spatrick     std::hash<uint32_t>{},
15946035553Spatrick     getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
16046035553Spatrick 
16146035553Spatrick BENCHMARK_CAPTURE(BM_Hash,
16246035553Spatrick     uint32_top_custom_hash,
16346035553Spatrick     UInt32Hash{},
16446035553Spatrick     getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs);
16546035553Spatrick 
16646035553Spatrick 
16746035553Spatrick //----------------------------------------------------------------------------//
16846035553Spatrick //                       BM_InsertValue
16946035553Spatrick // ---------------------------------------------------------------------------//
17046035553Spatrick 
17146035553Spatrick 
17246035553Spatrick // Sorted Ascending //
17346035553Spatrick BENCHMARK_CAPTURE(BM_InsertValue,
17446035553Spatrick     unordered_set_uint32,
17546035553Spatrick     std::unordered_set<uint32_t>{},
17646035553Spatrick     getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs);
17746035553Spatrick 
17846035553Spatrick BENCHMARK_CAPTURE(BM_InsertValue,
17946035553Spatrick     unordered_set_uint32_sorted,
18046035553Spatrick     std::unordered_set<uint32_t>{},
18146035553Spatrick     getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
18246035553Spatrick 
18346035553Spatrick // Top Bytes //
18446035553Spatrick BENCHMARK_CAPTURE(BM_InsertValue,
18546035553Spatrick     unordered_set_top_bits_uint32,
18646035553Spatrick     std::unordered_set<uint32_t>{},
18746035553Spatrick     getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
18846035553Spatrick 
18946035553Spatrick BENCHMARK_CAPTURE(BM_InsertValueRehash,
19046035553Spatrick     unordered_set_top_bits_uint32,
19146035553Spatrick     std::unordered_set<uint32_t, UInt32Hash>{},
19246035553Spatrick     getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs);
19346035553Spatrick 
19446035553Spatrick // String //
19546035553Spatrick BENCHMARK_CAPTURE(BM_InsertValue,
19646035553Spatrick     unordered_set_string,
19746035553Spatrick     std::unordered_set<std::string>{},
19846035553Spatrick     getRandomStringInputs)->Arg(TestNumInputs);
19946035553Spatrick 
20046035553Spatrick BENCHMARK_CAPTURE(BM_InsertValueRehash,
20146035553Spatrick     unordered_set_string,
20246035553Spatrick     std::unordered_set<std::string>{},
20346035553Spatrick     getRandomStringInputs)->Arg(TestNumInputs);
20446035553Spatrick 
20546035553Spatrick //----------------------------------------------------------------------------//
20646035553Spatrick //                         BM_Find
20746035553Spatrick // ---------------------------------------------------------------------------//
20846035553Spatrick 
20946035553Spatrick // Random //
21046035553Spatrick BENCHMARK_CAPTURE(BM_Find,
21146035553Spatrick     unordered_set_random_uint64,
21246035553Spatrick     std::unordered_set<uint64_t>{},
21346035553Spatrick     getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
21446035553Spatrick 
21546035553Spatrick BENCHMARK_CAPTURE(BM_FindRehash,
21646035553Spatrick     unordered_set_random_uint64,
21746035553Spatrick     std::unordered_set<uint64_t, UInt64Hash>{},
21846035553Spatrick     getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs);
21946035553Spatrick 
22046035553Spatrick // Sorted //
22146035553Spatrick BENCHMARK_CAPTURE(BM_Find,
22246035553Spatrick     unordered_set_sorted_uint64,
22346035553Spatrick     std::unordered_set<uint64_t>{},
22446035553Spatrick     getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
22546035553Spatrick 
22646035553Spatrick BENCHMARK_CAPTURE(BM_FindRehash,
22746035553Spatrick     unordered_set_sorted_uint64,
22846035553Spatrick     std::unordered_set<uint64_t, UInt64Hash>{},
22946035553Spatrick     getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs);
23046035553Spatrick 
23146035553Spatrick 
23246035553Spatrick // Sorted //
23346035553Spatrick #if 1
23446035553Spatrick BENCHMARK_CAPTURE(BM_Find,
23546035553Spatrick     unordered_set_sorted_uint128,
23646035553Spatrick     std::unordered_set<__uint128_t, UInt128Hash>{},
23746035553Spatrick     getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
23846035553Spatrick 
23946035553Spatrick BENCHMARK_CAPTURE(BM_FindRehash,
24046035553Spatrick     unordered_set_sorted_uint128,
24146035553Spatrick     std::unordered_set<__uint128_t, UInt128Hash>{},
24246035553Spatrick     getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs);
24346035553Spatrick #endif
24446035553Spatrick 
24546035553Spatrick // Sorted //
24646035553Spatrick BENCHMARK_CAPTURE(BM_Find,
24746035553Spatrick     unordered_set_sorted_uint32,
24846035553Spatrick     std::unordered_set<uint32_t>{},
24946035553Spatrick     getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
25046035553Spatrick 
25146035553Spatrick BENCHMARK_CAPTURE(BM_FindRehash,
25246035553Spatrick     unordered_set_sorted_uint32,
25346035553Spatrick     std::unordered_set<uint32_t, UInt32Hash2>{},
25446035553Spatrick     getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs);
25546035553Spatrick 
25646035553Spatrick // Sorted Ascending //
25746035553Spatrick BENCHMARK_CAPTURE(BM_Find,
25846035553Spatrick     unordered_set_sorted_large_uint64,
25946035553Spatrick     std::unordered_set<uint64_t>{},
26046035553Spatrick     getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
26146035553Spatrick 
26246035553Spatrick BENCHMARK_CAPTURE(BM_FindRehash,
26346035553Spatrick     unordered_set_sorted_large_uint64,
26446035553Spatrick     std::unordered_set<uint64_t, UInt64Hash>{},
26546035553Spatrick     getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs);
26646035553Spatrick 
26746035553Spatrick 
26846035553Spatrick // Top Bits //
26946035553Spatrick BENCHMARK_CAPTURE(BM_Find,
27046035553Spatrick     unordered_set_top_bits_uint64,
27146035553Spatrick     std::unordered_set<uint64_t>{},
27246035553Spatrick     getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
27346035553Spatrick 
27446035553Spatrick BENCHMARK_CAPTURE(BM_FindRehash,
27546035553Spatrick     unordered_set_top_bits_uint64,
27646035553Spatrick     std::unordered_set<uint64_t, UInt64Hash>{},
27746035553Spatrick     getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs);
27846035553Spatrick 
27946035553Spatrick // String //
28046035553Spatrick BENCHMARK_CAPTURE(BM_Find,
28146035553Spatrick     unordered_set_string,
28246035553Spatrick     std::unordered_set<std::string>{},
28346035553Spatrick     getRandomStringInputs)->Arg(TestNumInputs);
28446035553Spatrick 
28546035553Spatrick BENCHMARK_CAPTURE(BM_FindRehash,
28646035553Spatrick     unordered_set_string,
28746035553Spatrick     std::unordered_set<std::string>{},
28846035553Spatrick     getRandomStringInputs)->Arg(TestNumInputs);
28946035553Spatrick 
290*4bdff4beSrobert //----------------------------------------------------------------------------//
291*4bdff4beSrobert //                         BM_Rehash
292*4bdff4beSrobert // ---------------------------------------------------------------------------//
293*4bdff4beSrobert 
294*4bdff4beSrobert BENCHMARK_CAPTURE(BM_Rehash,
295*4bdff4beSrobert     unordered_set_string_arg,
296*4bdff4beSrobert     std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
297*4bdff4beSrobert     getRandomStringInputs)->Arg(TestNumInputs);
298*4bdff4beSrobert 
299*4bdff4beSrobert BENCHMARK_CAPTURE(BM_Rehash,
300*4bdff4beSrobert     unordered_set_int_arg,
301*4bdff4beSrobert     std::unordered_set<int>{},
302*4bdff4beSrobert     getRandomIntegerInputs<int>)->Arg(TestNumInputs);
303*4bdff4beSrobert 
30446035553Spatrick ///////////////////////////////////////////////////////////////////////////////
30546035553Spatrick BENCHMARK_CAPTURE(BM_InsertDuplicate,
30646035553Spatrick     unordered_set_int,
30746035553Spatrick     std::unordered_set<int>{},
30846035553Spatrick     getRandomIntegerInputs<int>)->Arg(TestNumInputs);
30946035553Spatrick BENCHMARK_CAPTURE(BM_InsertDuplicate,
31046035553Spatrick     unordered_set_string,
31146035553Spatrick     std::unordered_set<std::string>{},
31246035553Spatrick     getRandomStringInputs)->Arg(TestNumInputs);
31346035553Spatrick 
31446035553Spatrick BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
31546035553Spatrick     unordered_set_int,
31646035553Spatrick     std::unordered_set<int>{},
31746035553Spatrick     getRandomIntegerInputs<int>)->Arg(TestNumInputs);
31846035553Spatrick BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
31946035553Spatrick     unordered_set_string,
32046035553Spatrick     std::unordered_set<std::string>{},
32146035553Spatrick     getRandomStringInputs)->Arg(TestNumInputs);
32246035553Spatrick 
32346035553Spatrick BENCHMARK_CAPTURE(BM_InsertDuplicate,
32446035553Spatrick     unordered_set_int_insert_arg,
32546035553Spatrick     std::unordered_set<int>{},
32646035553Spatrick     getRandomIntegerInputs<int>)->Arg(TestNumInputs);
32746035553Spatrick BENCHMARK_CAPTURE(BM_InsertDuplicate,
32846035553Spatrick     unordered_set_string_insert_arg,
32946035553Spatrick     std::unordered_set<std::string>{},
33046035553Spatrick     getRandomStringInputs)->Arg(TestNumInputs);
33146035553Spatrick 
33246035553Spatrick BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
33346035553Spatrick     unordered_set_int_insert_arg,
33446035553Spatrick     std::unordered_set<int>{},
33546035553Spatrick     getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
33646035553Spatrick 
33746035553Spatrick BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
33846035553Spatrick     unordered_set_string_arg,
33946035553Spatrick     std::unordered_set<std::string>{},
34046035553Spatrick     getRandomCStringInputs)->Arg(TestNumInputs);
34146035553Spatrick 
34246035553Spatrick BENCHMARK_MAIN();
343