Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 1 | #include <unordered_set> |
| 2 | #include <vector> |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 3 | #include <functional> |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 4 | #include <cstdint> |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 5 | #include <cstdlib> |
| 6 | #include <cstring> |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 7 | |
Eric Fiselier | fd2e3e9 | 2018-01-18 04:23:01 +0000 | [diff] [blame] | 8 | #include "benchmark/benchmark.h" |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 9 | |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 10 | #include "ContainerBenchmarks.hpp" |
| 11 | #include "GenerateInput.hpp" |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 12 | #include "test_macros.h" |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 13 | |
| 14 | using namespace ContainerBenchmarks; |
| 15 | |
| 16 | constexpr std::size_t TestNumInputs = 1024; |
| 17 | |
| 18 | template <class _Size> |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 19 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 20 | _Size loadword(const void* __p) { |
| 21 | _Size __r; |
| 22 | std::memcpy(&__r, __p, sizeof(__r)); |
| 23 | return __r; |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 24 | } |
| 25 | |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 26 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 27 | std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) { |
| 28 | return (__val >> __shift) | (__val << (64 - __shift)); |
| 29 | } |
| 30 | |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 31 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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> |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 44 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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; |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 54 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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; |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 62 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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; |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 70 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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; |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 81 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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; |
Eric Fiselier | 697faed | 2018-10-10 18:22:23 +0000 | [diff] [blame] | 101 | inline TEST_ALWAYS_INLINE |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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) { |
Eric Fiselier | 30b48cb | 2016-08-09 18:56:48 +0000 | [diff] [blame] | 113 | auto in = gen(st.range(0)); |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 114 | const auto end = in.data() + in.size(); |
| 115 | std::size_t last_hash = 0; |
| 116 | benchmark::DoNotOptimize(&last_hash); |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 117 | while (st.KeepRunning()) { |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 118 | for (auto it = in.data(); it != end; ++it) { |
| 119 | benchmark::DoNotOptimize(last_hash += fn(*it)); |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 120 | } |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 121 | benchmark::ClobberMemory(); |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 122 | } |
| 123 | } |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 124 | |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 125 | BENCHMARK_CAPTURE(BM_Hash, |
| 126 | uint32_random_std_hash, |
| 127 | std::hash<uint32_t>{}, |
| 128 | getRandomIntegerInputs<uint32_t>) -> Arg(TestNumInputs); |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 129 | |
Eric Fiselier | d9b9ef7 | 2016-07-19 23:07:03 +0000 | [diff] [blame] | 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); |
Eric Fiselier | 56a7614 | 2016-07-02 05:30:54 +0000 | [diff] [blame] | 268 | |
Eric Fiselier | d757090 | 2016-07-24 06:22:25 +0000 | [diff] [blame] | 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 | |
Eric Fiselier | fd2e3e9 | 2018-01-18 04:23:01 +0000 | [diff] [blame] | 307 | BENCHMARK_MAIN(); |