unordered_set_operations.bench.cpp (9200B)
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 #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 20 _Size loadword(const void* __p) { 21 _Size __r; 22 std::memcpy(&__r, __p, sizeof(__r)); 23 return __r; 24 } 25 26 inline TEST_ALWAYS_INLINE 27 std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) { 28 return (__val >> __shift) | (__val << (64 - __shift)); 29 } 30 31 inline TEST_ALWAYS_INLINE 32 std::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 43 template <std::size_t _Len> 44 inline TEST_ALWAYS_INLINE 45 std::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 52 struct 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 60 struct 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 68 struct 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 79 struct 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 99 struct 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 //----------------------------------------------------------------------------// 108 // BM_Hash 109 // ---------------------------------------------------------------------------// 110 111 template <class HashFn, class GenInputs> 112 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) { 113 auto in = gen(st.range(0)); 114 const auto end = in.data() + in.size(); 115 std::size_t last_hash = 0; 116 benchmark::DoNotOptimize(&last_hash); 117 while (st.KeepRunning()) { 118 for (auto it = in.data(); it != end; ++it) { 119 benchmark::DoNotOptimize(last_hash += fn(*it)); 120 } 121 benchmark::ClobberMemory(); 122 } 123 } 124 125 BENCHMARK_CAPTURE(BM_Hash, 126 uint32_random_std_hash, 127 std::hash<uint32_t>{}, 128 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 129 130 BENCHMARK_CAPTURE(BM_Hash, 131 uint32_random_custom_hash, 132 UInt32Hash{}, 133 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 134 135 BENCHMARK_CAPTURE(BM_Hash, 136 uint32_top_std_hash, 137 std::hash<uint32_t>{}, 138 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 139 140 BENCHMARK_CAPTURE(BM_Hash, 141 uint32_top_custom_hash, 142 UInt32Hash{}, 143 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 144 145 146 //----------------------------------------------------------------------------// 147 // BM_InsertValue 148 // ---------------------------------------------------------------------------// 149 150 151 // Sorted Assending // 152 BENCHMARK_CAPTURE(BM_InsertValue, 153 unordered_set_uint32, 154 std::unordered_set<uint32_t>{}, 155 getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs); 156 157 BENCHMARK_CAPTURE(BM_InsertValue, 158 unordered_set_uint32_sorted, 159 std::unordered_set<uint32_t>{}, 160 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 161 162 // Top Bytes // 163 BENCHMARK_CAPTURE(BM_InsertValue, 164 unordered_set_top_bits_uint32, 165 std::unordered_set<uint32_t>{}, 166 getSortedTopBitsIntegerInputs<uint32_t>)->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>)->Arg(TestNumInputs); 172 173 // String // 174 BENCHMARK_CAPTURE(BM_InsertValue, 175 unordered_set_string, 176 std::unordered_set<std::string>{}, 177 getRandomStringInputs)->Arg(TestNumInputs); 178 179 BENCHMARK_CAPTURE(BM_InsertValueRehash, 180 unordered_set_string, 181 std::unordered_set<std::string>{}, 182 getRandomStringInputs)->Arg(TestNumInputs); 183 184 //----------------------------------------------------------------------------// 185 // BM_Find 186 // ---------------------------------------------------------------------------// 187 188 // Random // 189 BENCHMARK_CAPTURE(BM_Find, 190 unordered_set_random_uint64, 191 std::unordered_set<uint64_t>{}, 192 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 193 194 BENCHMARK_CAPTURE(BM_FindRehash, 195 unordered_set_random_uint64, 196 std::unordered_set<uint64_t, UInt64Hash>{}, 197 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 198 199 // Sorted // 200 BENCHMARK_CAPTURE(BM_Find, 201 unordered_set_sorted_uint64, 202 std::unordered_set<uint64_t>{}, 203 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs); 204 205 BENCHMARK_CAPTURE(BM_FindRehash, 206 unordered_set_sorted_uint64, 207 std::unordered_set<uint64_t, UInt64Hash>{}, 208 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs); 209 210 211 // Sorted // 212 #if 1 213 BENCHMARK_CAPTURE(BM_Find, 214 unordered_set_sorted_uint128, 215 std::unordered_set<__uint128_t, UInt128Hash>{}, 216 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs); 217 218 BENCHMARK_CAPTURE(BM_FindRehash, 219 unordered_set_sorted_uint128, 220 std::unordered_set<__uint128_t, UInt128Hash>{}, 221 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs); 222 #endif 223 224 // Sorted // 225 BENCHMARK_CAPTURE(BM_Find, 226 unordered_set_sorted_uint32, 227 std::unordered_set<uint32_t>{}, 228 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 229 230 BENCHMARK_CAPTURE(BM_FindRehash, 231 unordered_set_sorted_uint32, 232 std::unordered_set<uint32_t, UInt32Hash2>{}, 233 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 234 235 // Sorted Ascending // 236 BENCHMARK_CAPTURE(BM_Find, 237 unordered_set_sorted_large_uint64, 238 std::unordered_set<uint64_t>{}, 239 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs); 240 241 BENCHMARK_CAPTURE(BM_FindRehash, 242 unordered_set_sorted_large_uint64, 243 std::unordered_set<uint64_t, UInt64Hash>{}, 244 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs); 245 246 247 // Top Bits // 248 BENCHMARK_CAPTURE(BM_Find, 249 unordered_set_top_bits_uint64, 250 std::unordered_set<uint64_t>{}, 251 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs); 252 253 BENCHMARK_CAPTURE(BM_FindRehash, 254 unordered_set_top_bits_uint64, 255 std::unordered_set<uint64_t, UInt64Hash>{}, 256 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs); 257 258 // String // 259 BENCHMARK_CAPTURE(BM_Find, 260 unordered_set_string, 261 std::unordered_set<std::string>{}, 262 getRandomStringInputs)->Arg(TestNumInputs); 263 264 BENCHMARK_CAPTURE(BM_FindRehash, 265 unordered_set_string, 266 std::unordered_set<std::string>{}, 267 getRandomStringInputs)->Arg(TestNumInputs); 268 269 /////////////////////////////////////////////////////////////////////////////// 270 BENCHMARK_CAPTURE(BM_InsertDuplicate, 271 unordered_set_int, 272 std::unordered_set<int>{}, 273 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 274 BENCHMARK_CAPTURE(BM_InsertDuplicate, 275 unordered_set_string, 276 std::unordered_set<std::string>{}, 277 getRandomStringInputs)->Arg(TestNumInputs); 278 279 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 280 unordered_set_int, 281 std::unordered_set<int>{}, 282 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 283 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 284 unordered_set_string, 285 std::unordered_set<std::string>{}, 286 getRandomStringInputs)->Arg(TestNumInputs); 287 288 BENCHMARK_CAPTURE(BM_InsertDuplicate, 289 unordered_set_int_insert_arg, 290 std::unordered_set<int>{}, 291 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 292 BENCHMARK_CAPTURE(BM_InsertDuplicate, 293 unordered_set_string_insert_arg, 294 std::unordered_set<std::string>{}, 295 getRandomStringInputs)->Arg(TestNumInputs); 296 297 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 298 unordered_set_int_insert_arg, 299 std::unordered_set<int>{}, 300 getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs); 301 302 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 303 unordered_set_string_arg, 304 std::unordered_set<std::string>{}, 305 getRandomCStringInputs)->Arg(TestNumInputs); 306 307 BENCHMARK_MAIN();