libcxx/benchmarks/unordered_set_operations.bench.cpp

   1 #include <cstdint>
   2 #include <cstdlib>
   3 #include <cstring>
   4 #include <functional>
   5 #include <unordered_set>
   6 #include <vector>
   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 _Size loadword(const void* __p) {
  20   _Size __r;
  21   std::memcpy(&__r, __p, sizeof(__r));
  22   return __r;
  23 }
  24
  25 inline TEST_ALWAYS_INLINE std::size_t rotate_by_at_least_1(std::size_t __val, int __shift) {
  26   return (__val >> __shift) | (__val << (64 - __shift));
  27 }
  28
  29 inline TEST_ALWAYS_INLINE std::size_t hash_len_16(std::size_t __u, std::size_t __v) {
  30   const std::size_t __mul = 0x9ddfea08eb382d69ULL;
  31   std::size_t __a         = (__u ^ __v) * __mul;
  32   __a ^= (__a >> 47);
  33   std::size_t __b = (__v ^ __a) * __mul;
  34   __b ^= (__b >> 47);
  35   __b *= __mul;
  36   return __b;
  37 }
  38
  39 template <std::size_t _Len>
  40 inline TEST_ALWAYS_INLINE std::size_t hash_len_0_to_8(const char* __s) {
  41   static_assert(_Len == 4 || _Len == 8, "");
  42   const uint64_t __a = loadword<uint32_t>(__s);
  43   const uint64_t __b = loadword<uint32_t>(__s + _Len - 4);
  44   return hash_len_16(_Len + (__a << 3), __b);
  45 }
  46
  47 struct UInt32Hash {
  48   UInt32Hash() = default;
  49   inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const {
  50     return hash_len_0_to_8<4>(reinterpret_cast<const char*>(&data));
  51   }
  52 };
  53
  54 struct UInt64Hash {
  55   UInt64Hash() = default;
  56   inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const {
  57     return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
  58   }
  59 };
  60
  61 struct UInt128Hash {
  62   UInt128Hash() = default;
  63   inline TEST_ALWAYS_INLINE std::size_t operator()(__uint128_t data) const {
  64     const __uint128_t __mask = static_cast<std::size_t>(-1);
  65     const std::size_t __a    = (std::size_t)(data & __mask);
  66     const std::size_t __b    = (std::size_t)((data & (__mask << 64)) >> 64);
  67     return hash_len_16(__a, rotate_by_at_least_1(__b + 16, 16)) ^ __b;
  68   }
  69 };
  70
  71 struct UInt32Hash2 {
  72   UInt32Hash2() = default;
  73   inline TEST_ALWAYS_INLINE std::size_t operator()(uint32_t data) const {
  74     const uint32_t __m = 0x5bd1e995;
  75     const uint32_t __r = 24;
  76     uint32_t __h       = 4;
  77     uint32_t __k       = data;
  78     __k *= __m;
  79     __k ^= __k >> __r;
  80     __k *= __m;
  81     __h *= __m;
  82     __h ^= __k;
  83     __h ^= __h >> 13;
  84     __h *= __m;
  85     __h ^= __h >> 15;
  86     return __h;
  87   }
  88 };
  89
  90 struct UInt64Hash2 {
  91   UInt64Hash2() = default;
  92   inline TEST_ALWAYS_INLINE std::size_t operator()(uint64_t data) const {
  93     return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
  94   }
  95 };
  96
  97 // The sole purpose of this comparator is to be used in BM_Rehash, where
  98 // we need something slow enough to be easily noticable in benchmark results.
  99 // The default implementation of operator== for strings seems to be a little
 100 // too fast for that specific benchmark to reliably show a noticeable
 101 // improvement, but unoptimized bytewise comparison fits just right.
 102 // Early return is there just for convenience, since we only compare strings
 103 // of equal length in BM_Rehash.
 104 struct SlowStringEq {
 105   SlowStringEq() = default;
 106   inline TEST_ALWAYS_INLINE bool operator()(const std::string& lhs, const std::string& rhs) const {
 107     if (lhs.size() != rhs.size())
 108       return false;
 109
 110     bool eq = true;
 111     for (size_t i = 0; i < lhs.size(); ++i) {
 112       eq &= lhs[i] == rhs[i];
 113     }
 114     return eq;
 115   }
 116 };
 117
 118 //----------------------------------------------------------------------------//
 119 //                               BM_Hash
 120 // ---------------------------------------------------------------------------//
 121
 122 template <class HashFn, class GenInputs>
 123 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
 124   auto in               = gen(st.range(0));
 125   const auto end        = in.data() + in.size();
 126   std::size_t last_hash = 0;
 127   benchmark::DoNotOptimize(&last_hash);
 128   while (st.KeepRunning()) {
 129     for (auto it = in.data(); it != end; ++it) {
 130       benchmark::DoNotOptimize(last_hash += fn(*it));
 131     }
 132     benchmark::ClobberMemory();
 133   }
 134 }
 135
 136 BENCHMARK_CAPTURE(BM_Hash, uint32_random_std_hash, std::hash<uint32_t>{}, getRandomIntegerInputs<uint32_t>)
 137     ->Arg(TestNumInputs);
 138
 139 BENCHMARK_CAPTURE(BM_Hash, uint32_random_custom_hash, UInt32Hash{}, getRandomIntegerInputs<uint32_t>)
 140     ->Arg(TestNumInputs);
 141
 142 BENCHMARK_CAPTURE(BM_Hash, uint32_top_std_hash, std::hash<uint32_t>{}, getSortedTopBitsIntegerInputs<uint32_t>)
 143     ->Arg(TestNumInputs);
 144
 145 BENCHMARK_CAPTURE(BM_Hash, uint32_top_custom_hash, UInt32Hash{}, getSortedTopBitsIntegerInputs<uint32_t>)
 146     ->Arg(TestNumInputs);
 147
 148 //----------------------------------------------------------------------------//
 149 //                       BM_InsertValue
 150 // ---------------------------------------------------------------------------//
 151
 152 // Sorted Ascending //
 153 BENCHMARK_CAPTURE(
 154     BM_InsertValue, unordered_set_uint32, std::unordered_set<uint32_t>{}, getRandomIntegerInputs<uint32_t>)
 155     ->Arg(TestNumInputs);
 156
 157 BENCHMARK_CAPTURE(
 158     BM_InsertValue, unordered_set_uint32_sorted, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
 159     ->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>)
 166     ->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>)
 172     ->Arg(TestNumInputs);
 173
 174 // String //
 175 BENCHMARK_CAPTURE(BM_InsertValue, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 176     ->Arg(TestNumInputs);
 177
 178 BENCHMARK_CAPTURE(BM_InsertValueRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 179     ->Arg(TestNumInputs);
 180
 181 // Prefixed String //
 182 BENCHMARK_CAPTURE(
 183     BM_InsertValue, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
 184     ->Arg(TestNumInputs);
 185
 186 BENCHMARK_CAPTURE(BM_InsertValueRehash,
 187                   unordered_set_prefixed_string,
 188                   std::unordered_set<std::string>{},
 189                   getPrefixedRandomStringInputs)
 190     ->Arg(TestNumInputs);
 191
 192 //----------------------------------------------------------------------------//
 193 //                         BM_Find
 194 // ---------------------------------------------------------------------------//
 195
 196 // Random //
 197 BENCHMARK_CAPTURE(
 198     BM_Find, unordered_set_random_uint64, std::unordered_set<uint64_t>{}, getRandomIntegerInputs<uint64_t>)
 199     ->Arg(TestNumInputs);
 200
 201 BENCHMARK_CAPTURE(BM_FindRehash,
 202                   unordered_set_random_uint64,
 203                   std::unordered_set<uint64_t, UInt64Hash>{},
 204                   getRandomIntegerInputs<uint64_t>)
 205     ->Arg(TestNumInputs);
 206
 207 // Sorted //
 208 BENCHMARK_CAPTURE(
 209     BM_Find, unordered_set_sorted_uint64, std::unordered_set<uint64_t>{}, getSortedIntegerInputs<uint64_t>)
 210     ->Arg(TestNumInputs);
 211
 212 BENCHMARK_CAPTURE(BM_FindRehash,
 213                   unordered_set_sorted_uint64,
 214                   std::unordered_set<uint64_t, UInt64Hash>{},
 215                   getSortedIntegerInputs<uint64_t>)
 216     ->Arg(TestNumInputs);
 217
 218 // Sorted //
 219 BENCHMARK_CAPTURE(BM_Find,
 220                   unordered_set_sorted_uint128,
 221                   std::unordered_set<__uint128_t, UInt128Hash>{},
 222                   getSortedTopBitsIntegerInputs<__uint128_t>)
 223     ->Arg(TestNumInputs);
 224
 225 BENCHMARK_CAPTURE(BM_FindRehash,
 226                   unordered_set_sorted_uint128,
 227                   std::unordered_set<__uint128_t, UInt128Hash>{},
 228                   getSortedTopBitsIntegerInputs<__uint128_t>)
 229     ->Arg(TestNumInputs);
 230
 231 // Sorted //
 232 BENCHMARK_CAPTURE(
 233     BM_Find, unordered_set_sorted_uint32, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
 234     ->Arg(TestNumInputs);
 235
 236 BENCHMARK_CAPTURE(BM_FindRehash,
 237                   unordered_set_sorted_uint32,
 238                   std::unordered_set<uint32_t, UInt32Hash2>{},
 239                   getSortedIntegerInputs<uint32_t>)
 240     ->Arg(TestNumInputs);
 241
 242 // Sorted Ascending //
 243 BENCHMARK_CAPTURE(
 244     BM_Find, unordered_set_sorted_large_uint64, std::unordered_set<uint64_t>{}, getSortedLargeIntegerInputs<uint64_t>)
 245     ->Arg(TestNumInputs);
 246
 247 BENCHMARK_CAPTURE(BM_FindRehash,
 248                   unordered_set_sorted_large_uint64,
 249                   std::unordered_set<uint64_t, UInt64Hash>{},
 250                   getSortedLargeIntegerInputs<uint64_t>)
 251     ->Arg(TestNumInputs);
 252
 253 // Top Bits //
 254 BENCHMARK_CAPTURE(
 255     BM_Find, unordered_set_top_bits_uint64, std::unordered_set<uint64_t>{}, getSortedTopBitsIntegerInputs<uint64_t>)
 256     ->Arg(TestNumInputs);
 257
 258 BENCHMARK_CAPTURE(BM_FindRehash,
 259                   unordered_set_top_bits_uint64,
 260                   std::unordered_set<uint64_t, UInt64Hash>{},
 261                   getSortedTopBitsIntegerInputs<uint64_t>)
 262     ->Arg(TestNumInputs);
 263
 264 // String //
 265 BENCHMARK_CAPTURE(BM_Find, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 266     ->Arg(TestNumInputs);
 267
 268 BENCHMARK_CAPTURE(BM_FindRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 269     ->Arg(TestNumInputs);
 270
 271 // Prefixed String //
 272 BENCHMARK_CAPTURE(
 273     BM_Find, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
 274     ->Arg(TestNumInputs);
 275
 276 BENCHMARK_CAPTURE(
 277     BM_FindRehash, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
 278     ->Arg(TestNumInputs);
 279
 280 //----------------------------------------------------------------------------//
 281 //                         BM_Rehash
 282 // ---------------------------------------------------------------------------//
 283
 284 BENCHMARK_CAPTURE(BM_Rehash,
 285                   unordered_set_string_arg,
 286                   std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
 287                   getRandomStringInputs)
 288     ->Arg(TestNumInputs);
 289
 290 BENCHMARK_CAPTURE(BM_Rehash, unordered_set_int_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 291     ->Arg(TestNumInputs);
 292
 293 //----------------------------------------------------------------------------//
 294 //                         BM_Compare
 295 // ---------------------------------------------------------------------------//
 296
 297 BENCHMARK_CAPTURE(
 298     BM_Compare_same_container, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 299     ->Arg(TestNumInputs);
 300
 301 BENCHMARK_CAPTURE(BM_Compare_same_container, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 302     ->Arg(TestNumInputs);
 303
 304 BENCHMARK_CAPTURE(
 305     BM_Compare_different_containers, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 306     ->Arg(TestNumInputs);
 307
 308 BENCHMARK_CAPTURE(
 309     BM_Compare_different_containers, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 310     ->Arg(TestNumInputs);
 311
 312 ///////////////////////////////////////////////////////////////////////////////
 313 BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 314     ->Arg(TestNumInputs);
 315 BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 316     ->Arg(TestNumInputs);
 317
 318 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 319     ->Arg(TestNumInputs);
 320 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 321     ->Arg(TestNumInputs);
 322
 323 BENCHMARK_CAPTURE(
 324     BM_InsertDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 325     ->Arg(TestNumInputs);
 326 BENCHMARK_CAPTURE(
 327     BM_InsertDuplicate, unordered_set_string_insert_arg, std::unordered_set<std::string>{}, getRandomStringInputs)
 328     ->Arg(TestNumInputs);
 329
 330 BENCHMARK_CAPTURE(
 331     BM_EmplaceDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<unsigned>)
 332     ->Arg(TestNumInputs);
 333
 334 BENCHMARK_CAPTURE(
 335     BM_EmplaceDuplicate, unordered_set_string_arg, std::unordered_set<std::string>{}, getRandomCStringInputs)
 336     ->Arg(TestNumInputs);
 337
 338 BENCHMARK_MAIN();