1 #include <unordered_set> 2 #include <vector> 3 #include <functional> 4 #include <cstdint> 5 #include <cstdlib> 6 #include <cstring> 7 8 #include "benchmark/benchmark_api.h" 9 10 #include "ContainerBenchmarks.hpp" 11 #include "GenerateInput.hpp" 12 13 using namespace ContainerBenchmarks; 14 15 constexpr std::size_t TestNumInputs = 1024; 16 17 template <class _Size> 18 inline __attribute__((__always_inline__)) 19 _Size loadword(const void* __p) { 20 _Size __r; 21 std::memcpy(&__r, __p, sizeof(__r)); 22 return __r; 23 } 24 25 inline __attribute__((__always_inline__)) 26 std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) { 27 return (__val >> __shift) | (__val << (64 - __shift)); 28 } 29 30 inline __attribute__((__always_inline__)) 31 std::size_t hash_len_16(std::size_t __u, std::size_t __v) { 32 const std::size_t __mul = 0x9ddfea08eb382d69ULL; 33 std::size_t __a = (__u ^ __v) * __mul; 34 __a ^= (__a >> 47); 35 std::size_t __b = (__v ^ __a) * __mul; 36 __b ^= (__b >> 47); 37 __b *= __mul; 38 return __b; 39 } 40 41 42 template <std::size_t _Len> 43 inline __attribute__((__always_inline__)) 44 std::size_t hash_len_0_to_8(const char* __s) { 45 static_assert(_Len == 4 || _Len == 8, ""); 46 const uint64_t __a = loadword<uint32_t>(__s); 47 const uint64_t __b = loadword<uint32_t>(__s + _Len - 4); 48 return hash_len_16(_Len + (__a << 3), __b); 49 } 50 51 struct UInt32Hash { 52 UInt32Hash() = default; 53 inline __attribute__((__always_inline__)) 54 std::size_t operator()(uint32_t data) const { 55 return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data)); 56 } 57 }; 58 59 struct UInt64Hash { 60 UInt64Hash() = default; 61 inline __attribute__((__always_inline__)) 62 std::size_t operator()(uint64_t data) const { 63 return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data)); 64 } 65 }; 66 67 struct UInt128Hash { 68 UInt128Hash() = default; 69 inline __attribute__((__always_inline__)) 70 std::size_t operator()(__uint128_t data) const { 71 const __uint128_t __mask = static_cast<std::size_t>(-1); 72 const std::size_t __a = (std::size_t)(data & __mask); 73 const std::size_t __b = (std::size_t)((data & (__mask << 64)) >> 64); 74 return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b; 75 } 76 }; 77 78 struct UInt32Hash2 { 79 UInt32Hash2() = default; 80 inline __attribute__((__always_inline__)) 81 std::size_t operator()(uint32_t data) const { 82 const uint32_t __m = 0x5bd1e995; 83 const uint32_t __r = 24; 84 uint32_t __h = 4; 85 uint32_t __k = data; 86 __k *= __m; 87 __k ^= __k >> __r; 88 __k *= __m; 89 __h *= __m; 90 __h ^= __k; 91 __h ^= __h >> 13; 92 __h *= __m; 93 __h ^= __h >> 15; 94 return __h; 95 } 96 }; 97 98 struct UInt64Hash2 { 99 UInt64Hash2() = default; 100 inline __attribute__((__always_inline__)) 101 std::size_t operator()(uint64_t data) const { 102 return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data)); 103 } 104 }; 105 106 //----------------------------------------------------------------------------// 107 // BM_Hash 108 // ---------------------------------------------------------------------------// 109 110 template <class HashFn, class GenInputs> 111 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) { 112 auto in = gen(st.range(0)); 113 const auto end = in.data() + in.size(); 114 std::size_t last_hash = 0; 115 benchmark::DoNotOptimize(&last_hash); 116 while (st.KeepRunning()) { 117 for (auto it = in.data(); it != end; ++it) { 118 benchmark::DoNotOptimize(last_hash += fn(*it)); 119 } 120 benchmark::ClobberMemory(); 121 } 122 } 123 124 BENCHMARK_CAPTURE(BM_Hash, 125 uint32_random_std_hash, 126 std::hash<uint32_t>{}, 127 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 128 129 BENCHMARK_CAPTURE(BM_Hash, 130 uint32_random_custom_hash, 131 UInt32Hash{}, 132 getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 133 134 BENCHMARK_CAPTURE(BM_Hash, 135 uint32_top_std_hash, 136 std::hash<uint32_t>{}, 137 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 138 139 BENCHMARK_CAPTURE(BM_Hash, 140 uint32_top_custom_hash, 141 UInt32Hash{}, 142 getSortedTopBitsIntegerInputs<uint32_t>) -> Arg(TestNumInputs); 143 144 145 //----------------------------------------------------------------------------// 146 // BM_InsertValue 147 // ---------------------------------------------------------------------------// 148 149 150 // Sorted Assending // 151 BENCHMARK_CAPTURE(BM_InsertValue, 152 unordered_set_uint32, 153 std::unordered_set<uint32_t>{}, 154 getRandomIntegerInputs<uint32_t>)->Arg(TestNumInputs); 155 156 BENCHMARK_CAPTURE(BM_InsertValue, 157 unordered_set_uint32_sorted, 158 std::unordered_set<uint32_t>{}, 159 getSortedIntegerInputs<uint32_t>)->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>)->Arg(TestNumInputs); 166 167 BENCHMARK_CAPTURE(BM_InsertValueRehash, 168 unordered_set_top_bits_uint32, 169 std::unordered_set<uint32_t, UInt32Hash>{}, 170 getSortedTopBitsIntegerInputs<uint32_t>)->Arg(TestNumInputs); 171 172 // String // 173 BENCHMARK_CAPTURE(BM_InsertValue, 174 unordered_set_string, 175 std::unordered_set<std::string>{}, 176 getRandomStringInputs)->Arg(TestNumInputs); 177 178 BENCHMARK_CAPTURE(BM_InsertValueRehash, 179 unordered_set_string, 180 std::unordered_set<std::string>{}, 181 getRandomStringInputs)->Arg(TestNumInputs); 182 183 //----------------------------------------------------------------------------// 184 // BM_Find 185 // ---------------------------------------------------------------------------// 186 187 // Random // 188 BENCHMARK_CAPTURE(BM_Find, 189 unordered_set_random_uint64, 190 std::unordered_set<uint64_t>{}, 191 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 192 193 BENCHMARK_CAPTURE(BM_FindRehash, 194 unordered_set_random_uint64, 195 std::unordered_set<uint64_t, UInt64Hash>{}, 196 getRandomIntegerInputs<uint64_t>)->Arg(TestNumInputs); 197 198 // Sorted // 199 BENCHMARK_CAPTURE(BM_Find, 200 unordered_set_sorted_uint64, 201 std::unordered_set<uint64_t>{}, 202 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs); 203 204 BENCHMARK_CAPTURE(BM_FindRehash, 205 unordered_set_sorted_uint64, 206 std::unordered_set<uint64_t, UInt64Hash>{}, 207 getSortedIntegerInputs<uint64_t>)->Arg(TestNumInputs); 208 209 210 // Sorted // 211 #if 1 212 BENCHMARK_CAPTURE(BM_Find, 213 unordered_set_sorted_uint128, 214 std::unordered_set<__uint128_t, UInt128Hash>{}, 215 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs); 216 217 BENCHMARK_CAPTURE(BM_FindRehash, 218 unordered_set_sorted_uint128, 219 std::unordered_set<__uint128_t, UInt128Hash>{}, 220 getSortedTopBitsIntegerInputs<__uint128_t>)->Arg(TestNumInputs); 221 #endif 222 223 // Sorted // 224 BENCHMARK_CAPTURE(BM_Find, 225 unordered_set_sorted_uint32, 226 std::unordered_set<uint32_t>{}, 227 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 228 229 BENCHMARK_CAPTURE(BM_FindRehash, 230 unordered_set_sorted_uint32, 231 std::unordered_set<uint32_t, UInt32Hash2>{}, 232 getSortedIntegerInputs<uint32_t>)->Arg(TestNumInputs); 233 234 // Sorted Ascending // 235 BENCHMARK_CAPTURE(BM_Find, 236 unordered_set_sorted_large_uint64, 237 std::unordered_set<uint64_t>{}, 238 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs); 239 240 BENCHMARK_CAPTURE(BM_FindRehash, 241 unordered_set_sorted_large_uint64, 242 std::unordered_set<uint64_t, UInt64Hash>{}, 243 getSortedLargeIntegerInputs<uint64_t>)->Arg(TestNumInputs); 244 245 246 // Top Bits // 247 BENCHMARK_CAPTURE(BM_Find, 248 unordered_set_top_bits_uint64, 249 std::unordered_set<uint64_t>{}, 250 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs); 251 252 BENCHMARK_CAPTURE(BM_FindRehash, 253 unordered_set_top_bits_uint64, 254 std::unordered_set<uint64_t, UInt64Hash>{}, 255 getSortedTopBitsIntegerInputs<uint64_t>)->Arg(TestNumInputs); 256 257 // String // 258 BENCHMARK_CAPTURE(BM_Find, 259 unordered_set_string, 260 std::unordered_set<std::string>{}, 261 getRandomStringInputs)->Arg(TestNumInputs); 262 263 BENCHMARK_CAPTURE(BM_FindRehash, 264 unordered_set_string, 265 std::unordered_set<std::string>{}, 266 getRandomStringInputs)->Arg(TestNumInputs); 267 268 /////////////////////////////////////////////////////////////////////////////// 269 BENCHMARK_CAPTURE(BM_InsertDuplicate, 270 unordered_set_int, 271 std::unordered_set<int>{}, 272 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 273 BENCHMARK_CAPTURE(BM_InsertDuplicate, 274 unordered_set_string, 275 std::unordered_set<std::string>{}, 276 getRandomStringInputs)->Arg(TestNumInputs); 277 278 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 279 unordered_set_int, 280 std::unordered_set<int>{}, 281 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 282 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 283 unordered_set_string, 284 std::unordered_set<std::string>{}, 285 getRandomStringInputs)->Arg(TestNumInputs); 286 287 BENCHMARK_CAPTURE(BM_InsertDuplicate, 288 unordered_set_int_insert_arg, 289 std::unordered_set<int>{}, 290 getRandomIntegerInputs<int>)->Arg(TestNumInputs); 291 BENCHMARK_CAPTURE(BM_InsertDuplicate, 292 unordered_set_string_insert_arg, 293 std::unordered_set<std::string>{}, 294 getRandomStringInputs)->Arg(TestNumInputs); 295 296 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 297 unordered_set_int_insert_arg, 298 std::unordered_set<int>{}, 299 getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs); 300 301 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, 302 unordered_set_string_arg, 303 std::unordered_set<std::string>{}, 304 getRandomCStringInputs)->Arg(TestNumInputs); 305 306 BENCHMARK_MAIN() 307
