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 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 // 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. 114 struct 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 132 template <class HashFn, class GenInputs> 133 void 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 146 BENCHMARK_CAPTURE(BM_Hash, 147 uint32_random_std_hash, 148 std::hash<uint32_t>{}, 149 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 150 151 BENCHMARK_CAPTURE(BM_Hash, 152 uint32_random_custom_hash, 153 UInt32Hash{}, 154 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 155 156 BENCHMARK_CAPTURE(BM_Hash, 157 uint32_top_std_hash, 158 std::hash<uint32_t>{}, 159 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 160 161 BENCHMARK_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 // 173 BENCHMARK_CAPTURE(BM_InsertValue, 174 unordered_set_uint32, 175 std::unordered_set<uint32_t>{}, 176 getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs); 177 178 BENCHMARK_CAPTURE(BM_InsertValue, 179 unordered_set_uint32_sorted, 180 std::unordered_set<uint32_t>{}, 181 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 182 183 // Top Bytes // 184 BENCHMARK_CAPTURE(BM_InsertValue, 185 unordered_set_top_bits_uint32, 186 std::unordered_set<uint32_t>{}, 187 getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs); 188 189 BENCHMARK_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 // 195 BENCHMARK_CAPTURE(BM_InsertValue, 196 unordered_set_string, 197 std::unordered_set<std::string>{}, 198 getRandomStringInputs)->Arg(TestNumInputs); 199 200 BENCHMARK_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 // 210 BENCHMARK_CAPTURE(BM_Find, 211 unordered_set_random_uint64, 212 std::unordered_set<uint64_t>{}, 213 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 214 215 BENCHMARK_CAPTURE(BM_FindRehash, 216 unordered_set_random_uint64, 217 std::unordered_set<uint64_t, UInt64Hash>{}, 218 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 219 220 // Sorted // 221 BENCHMARK_CAPTURE(BM_Find, 222 unordered_set_sorted_uint64, 223 std::unordered_set<uint64_t>{}, 224 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs); 225 226 BENCHMARK_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 234 BENCHMARK_CAPTURE(BM_Find, 235 unordered_set_sorted_uint128, 236 std::unordered_set<__uint128_t, UInt128Hash>{}, 237 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs); 238 239 BENCHMARK_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 // 246 BENCHMARK_CAPTURE(BM_Find, 247 unordered_set_sorted_uint32, 248 std::unordered_set<uint32_t>{}, 249 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 250 251 BENCHMARK_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 // 257 BENCHMARK_CAPTURE(BM_Find, 258 unordered_set_sorted_large_uint64, 259 std::unordered_set<uint64_t>{}, 260 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs); 261 262 BENCHMARK_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 // 269 BENCHMARK_CAPTURE(BM_Find, 270 unordered_set_top_bits_uint64, 271 std::unordered_set<uint64_t>{}, 272 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs); 273 274 BENCHMARK_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 // 280 BENCHMARK_CAPTURE(BM_Find, 281 unordered_set_string, 282 std::unordered_set<std::string>{}, 283 getRandomStringInputs)->Arg(TestNumInputs); 284 285 BENCHMARK_CAPTURE(BM_FindRehash, 286 unordered_set_string, 287 std::unordered_set<std::string>{}, 288 getRandomStringInputs)->Arg(TestNumInputs); 289 290 //----------------------------------------------------------------------------// 291 // BM_Rehash 292 // ---------------------------------------------------------------------------// 293 294 BENCHMARK_CAPTURE(BM_Rehash, 295 unordered_set_string_arg, 296 std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{}, 297 getRandomStringInputs)->Arg(TestNumInputs); 298 299 BENCHMARK_CAPTURE(BM_Rehash, 300 unordered_set_int_arg, 301 std::unordered_set<int>{}, 302 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 303 304 /////////////////////////////////////////////////////////////////////////////// 305 BENCHMARK_CAPTURE(BM_InsertDuplicate, 306 unordered_set_int, 307 std::unordered_set<int>{}, 308 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 309 BENCHMARK_CAPTURE(BM_InsertDuplicate, 310 unordered_set_string, 311 std::unordered_set<std::string>{}, 312 getRandomStringInputs)->Arg(TestNumInputs); 313 314 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 315 unordered_set_int, 316 std::unordered_set<int>{}, 317 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 318 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 319 unordered_set_string, 320 std::unordered_set<std::string>{}, 321 getRandomStringInputs)->Arg(TestNumInputs); 322 323 BENCHMARK_CAPTURE(BM_InsertDuplicate, 324 unordered_set_int_insert_arg, 325 std::unordered_set<int>{}, 326 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 327 BENCHMARK_CAPTURE(BM_InsertDuplicate, 328 unordered_set_string_insert_arg, 329 std::unordered_set<std::string>{}, 330 getRandomStringInputs)->Arg(TestNumInputs); 331 332 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 333 unordered_set_int_insert_arg, 334 std::unordered_set<int>{}, 335 getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs); 336 337 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 338 unordered_set_string_arg, 339 std::unordered_set<std::string>{}, 340 getRandomCStringInputs)->Arg(TestNumInputs); 341 342 BENCHMARK_MAIN(); 343