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.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 20_Size loadword(const void* __p) { 21 _Size __r; 22 std::memcpy(&__r, __p, sizeof(__r)); 23 return __r; 24} 25 26inline TEST_ALWAYS_INLINE 27std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) { 28 return (__val >> __shift) | (__val << (64 - __shift)); 29} 30 31inline TEST_ALWAYS_INLINE 32std::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 43template <std::size_t _Len> 44inline TEST_ALWAYS_INLINE 45std::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 52struct 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 60struct 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 68struct 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 79struct 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 99struct 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// The sole purpose of this comparator is to be used in BM_Rehash, where 108// we need something slow enough to be easily noticable in benchmark results. 109// The default implementation of operator== for strings seems to be a little 110// too fast for that specific benchmark to reliably show a noticeable 111// improvement, but unoptimized bytewise comparison fits just right. 112// Early return is there just for convenience, since we only compare strings 113// of equal length in BM_Rehash. 114struct SlowStringEq { 115 SlowStringEq() = default; 116 inline TEST_ALWAYS_INLINE 117 bool operator()(const std::string& lhs, const std::string& rhs) const { 118 if (lhs.size() != rhs.size()) return false; 119 120 bool eq = true; 121 for (size_t i = 0; i < lhs.size(); ++i) { 122 eq &= lhs[i] == rhs[i]; 123 } 124 return eq; 125 } 126}; 127 128//----------------------------------------------------------------------------// 129// BM_Hash 130// ---------------------------------------------------------------------------// 131 132template <class HashFn, class GenInputs> 133void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) { 134 auto in = gen(st.range(0)); 135 const auto end = in.data() + in.size(); 136 std::size_t last_hash = 0; 137 benchmark::DoNotOptimize(&last_hash); 138 while (st.KeepRunning()) { 139 for (auto it = in.data(); it != end; ++it) { 140 benchmark::DoNotOptimize(last_hash += fn(*it)); 141 } 142 benchmark::ClobberMemory(); 143 } 144} 145 146BENCHMARK_CAPTURE(BM_Hash, 147 uint32_random_std_hash, 148 std::hash<uint32_t>{}, 149 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 150 151BENCHMARK_CAPTURE(BM_Hash, 152 uint32_random_custom_hash, 153 UInt32Hash{}, 154 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 155 156BENCHMARK_CAPTURE(BM_Hash, 157 uint32_top_std_hash, 158 std::hash<uint32_t>{}, 159 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 160 161BENCHMARK_CAPTURE(BM_Hash, 162 uint32_top_custom_hash, 163 UInt32Hash{}, 164 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 165 166 167//----------------------------------------------------------------------------// 168// BM_InsertValue 169// ---------------------------------------------------------------------------// 170 171 172// Sorted Ascending // 173BENCHMARK_CAPTURE(BM_InsertValue, 174 unordered_set_uint32, 175 std::unordered_set<uint32_t>{}, 176 getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs); 177 178BENCHMARK_CAPTURE(BM_InsertValue, 179 unordered_set_uint32_sorted, 180 std::unordered_set<uint32_t>{}, 181 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 182 183// Top Bytes // 184BENCHMARK_CAPTURE(BM_InsertValue, 185 unordered_set_top_bits_uint32, 186 std::unordered_set<uint32_t>{}, 187 getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs); 188 189BENCHMARK_CAPTURE(BM_InsertValueRehash, 190 unordered_set_top_bits_uint32, 191 std::unordered_set<uint32_t, UInt32Hash>{}, 192 getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs); 193 194// String // 195BENCHMARK_CAPTURE(BM_InsertValue, 196 unordered_set_string, 197 std::unordered_set<std::string>{}, 198 getRandomStringInputs)->Arg(TestNumInputs); 199 200BENCHMARK_CAPTURE(BM_InsertValueRehash, 201 unordered_set_string, 202 std::unordered_set<std::string>{}, 203 getRandomStringInputs)->Arg(TestNumInputs); 204 205//----------------------------------------------------------------------------// 206// BM_Find 207// ---------------------------------------------------------------------------// 208 209// Random // 210BENCHMARK_CAPTURE(BM_Find, 211 unordered_set_random_uint64, 212 std::unordered_set<uint64_t>{}, 213 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 214 215BENCHMARK_CAPTURE(BM_FindRehash, 216 unordered_set_random_uint64, 217 std::unordered_set<uint64_t, UInt64Hash>{}, 218 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 219 220// Sorted // 221BENCHMARK_CAPTURE(BM_Find, 222 unordered_set_sorted_uint64, 223 std::unordered_set<uint64_t>{}, 224 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs); 225 226BENCHMARK_CAPTURE(BM_FindRehash, 227 unordered_set_sorted_uint64, 228 std::unordered_set<uint64_t, UInt64Hash>{}, 229 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs); 230 231 232// Sorted // 233#if 1 234BENCHMARK_CAPTURE(BM_Find, 235 unordered_set_sorted_uint128, 236 std::unordered_set<__uint128_t, UInt128Hash>{}, 237 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs); 238 239BENCHMARK_CAPTURE(BM_FindRehash, 240 unordered_set_sorted_uint128, 241 std::unordered_set<__uint128_t, UInt128Hash>{}, 242 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs); 243#endif 244 245// Sorted // 246BENCHMARK_CAPTURE(BM_Find, 247 unordered_set_sorted_uint32, 248 std::unordered_set<uint32_t>{}, 249 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 250 251BENCHMARK_CAPTURE(BM_FindRehash, 252 unordered_set_sorted_uint32, 253 std::unordered_set<uint32_t, UInt32Hash2>{}, 254 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 255 256// Sorted Ascending // 257BENCHMARK_CAPTURE(BM_Find, 258 unordered_set_sorted_large_uint64, 259 std::unordered_set<uint64_t>{}, 260 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs); 261 262BENCHMARK_CAPTURE(BM_FindRehash, 263 unordered_set_sorted_large_uint64, 264 std::unordered_set<uint64_t, UInt64Hash>{}, 265 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs); 266 267 268// Top Bits // 269BENCHMARK_CAPTURE(BM_Find, 270 unordered_set_top_bits_uint64, 271 std::unordered_set<uint64_t>{}, 272 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs); 273 274BENCHMARK_CAPTURE(BM_FindRehash, 275 unordered_set_top_bits_uint64, 276 std::unordered_set<uint64_t, UInt64Hash>{}, 277 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs); 278 279// String // 280BENCHMARK_CAPTURE(BM_Find, 281 unordered_set_string, 282 std::unordered_set<std::string>{}, 283 getRandomStringInputs)->Arg(TestNumInputs); 284 285BENCHMARK_CAPTURE(BM_FindRehash, 286 unordered_set_string, 287 std::unordered_set<std::string>{}, 288 getRandomStringInputs)->Arg(TestNumInputs); 289 290//----------------------------------------------------------------------------// 291// BM_Rehash 292// ---------------------------------------------------------------------------// 293 294BENCHMARK_CAPTURE(BM_Rehash, 295 unordered_set_string_arg, 296 std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{}, 297 getRandomStringInputs)->Arg(TestNumInputs); 298 299BENCHMARK_CAPTURE(BM_Rehash, 300 unordered_set_int_arg, 301 std::unordered_set<int>{}, 302 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 303 304/////////////////////////////////////////////////////////////////////////////// 305BENCHMARK_CAPTURE(BM_InsertDuplicate, 306 unordered_set_int, 307 std::unordered_set<int>{}, 308 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 309BENCHMARK_CAPTURE(BM_InsertDuplicate, 310 unordered_set_string, 311 std::unordered_set<std::string>{}, 312 getRandomStringInputs)->Arg(TestNumInputs); 313 314BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 315 unordered_set_int, 316 std::unordered_set<int>{}, 317 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 318BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 319 unordered_set_string, 320 std::unordered_set<std::string>{}, 321 getRandomStringInputs)->Arg(TestNumInputs); 322 323BENCHMARK_CAPTURE(BM_InsertDuplicate, 324 unordered_set_int_insert_arg, 325 std::unordered_set<int>{}, 326 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 327BENCHMARK_CAPTURE(BM_InsertDuplicate, 328 unordered_set_string_insert_arg, 329 std::unordered_set<std::string>{}, 330 getRandomStringInputs)->Arg(TestNumInputs); 331 332BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 333 unordered_set_int_insert_arg, 334 std::unordered_set<int>{}, 335 getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs); 336 337BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 338 unordered_set_string_arg, 339 std::unordered_set<std::string>{}, 340 getRandomCStringInputs)->Arg(TestNumInputs); 341 342BENCHMARK_MAIN(); 343