libcxx/benchmarks/unordered_set_operations.bench.cpp

   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 //----------------------------------------------------------------------------//
 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 Ascending //
 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();