libcxx/test/benchmarks/unordered_set_operations.bench.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 // UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
  10
  11 #include <cstdint>
  12 #include <cstdlib>
  13 #include <cstring>
  14 #include <functional>
  15 #include <unordered_set>
  16 #include <vector>
  17
  18 #include "benchmark/benchmark.h"
  19
  20 #include "ContainerBenchmarks.h"
  21 #include "GenerateInput.h"
  22 #include "test_macros.h"
  23
  24 using namespace ContainerBenchmarks;
  25
  26 constexpr std::size_t TestNumInputs = 1024;
  27
  28 // The purpose of this hash function is to NOT be implemented as the identity function,
  29 // which is how std::hash is implemented for smaller integral types.
  30 struct NonIdentityScalarHash : std::hash<unsigned long long> {};
  31
  32 // The sole purpose of this comparator is to be used in BM_Rehash, where
  33 // we need something slow enough to be easily noticable in benchmark results.
  34 // The default implementation of operator== for strings seems to be a little
  35 // too fast for that specific benchmark to reliably show a noticeable
  36 // improvement, but unoptimized bytewise comparison fits just right.
  37 // Early return is there just for convenience, since we only compare strings
  38 // of equal length in BM_Rehash.
  39 struct SlowStringEq {
  40   SlowStringEq() = default;
  41   inline TEST_ALWAYS_INLINE bool operator()(const std::string& lhs, const std::string& rhs) const {
  42     if (lhs.size() != rhs.size())
  43       return false;
  44
  45     bool eq = true;
  46     for (size_t i = 0; i < lhs.size(); ++i) {
  47       eq &= lhs[i] == rhs[i];
  48     }
  49     return eq;
  50   }
  51 };
  52
  53 //----------------------------------------------------------------------------//
  54 //                       BM_InsertValue
  55 // ---------------------------------------------------------------------------//
  56
  57 // Sorted Ascending //
  58 BENCHMARK_CAPTURE(
  59     BM_InsertValue, unordered_set_uint32, std::unordered_set<uint32_t>{}, getRandomIntegerInputs<uint32_t>)
  60     ->Arg(TestNumInputs);
  61
  62 BENCHMARK_CAPTURE(
  63     BM_InsertValue, unordered_set_uint32_sorted, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
  64     ->Arg(TestNumInputs);
  65
  66 // Top Bytes //
  67 BENCHMARK_CAPTURE(BM_InsertValue,
  68                   unordered_set_top_bits_uint32,
  69                   std::unordered_set<uint32_t>{},
  70                   getSortedTopBitsIntegerInputs<uint32_t>)
  71     ->Arg(TestNumInputs);
  72
  73 BENCHMARK_CAPTURE(BM_InsertValueRehash,
  74                   unordered_set_top_bits_uint32,
  75                   std::unordered_set<uint32_t, NonIdentityScalarHash>{},
  76                   getSortedTopBitsIntegerInputs<uint32_t>)
  77     ->Arg(TestNumInputs);
  78
  79 // String //
  80 BENCHMARK_CAPTURE(BM_InsertValue, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
  81     ->Arg(TestNumInputs);
  82
  83 BENCHMARK_CAPTURE(BM_InsertValueRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
  84     ->Arg(TestNumInputs);
  85
  86 // Prefixed String //
  87 BENCHMARK_CAPTURE(
  88     BM_InsertValue, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
  89     ->Arg(TestNumInputs);
  90
  91 BENCHMARK_CAPTURE(BM_InsertValueRehash,
  92                   unordered_set_prefixed_string,
  93                   std::unordered_set<std::string>{},
  94                   getPrefixedRandomStringInputs)
  95     ->Arg(TestNumInputs);
  96
  97 //----------------------------------------------------------------------------//
  98 //                         BM_Find
  99 // ---------------------------------------------------------------------------//
 100
 101 // Random //
 102 BENCHMARK_CAPTURE(
 103     BM_Find, unordered_set_random_uint64, std::unordered_set<uint64_t>{}, getRandomIntegerInputs<uint64_t>)
 104     ->Arg(TestNumInputs);
 105
 106 BENCHMARK_CAPTURE(BM_FindRehash,
 107                   unordered_set_random_uint64,
 108                   std::unordered_set<uint64_t, NonIdentityScalarHash>{},
 109                   getRandomIntegerInputs<uint64_t>)
 110     ->Arg(TestNumInputs);
 111
 112 // Sorted //
 113 BENCHMARK_CAPTURE(
 114     BM_Find, unordered_set_sorted_uint64, std::unordered_set<uint64_t>{}, getSortedIntegerInputs<uint64_t>)
 115     ->Arg(TestNumInputs);
 116
 117 BENCHMARK_CAPTURE(BM_FindRehash,
 118                   unordered_set_sorted_uint64,
 119                   std::unordered_set<uint64_t, NonIdentityScalarHash>{},
 120                   getSortedIntegerInputs<uint64_t>)
 121     ->Arg(TestNumInputs);
 122
 123 // Sorted //
 124 #ifndef TEST_HAS_NO_INT128
 125 BENCHMARK_CAPTURE(BM_Find,
 126                   unordered_set_sorted_uint128,
 127                   std::unordered_set<__uint128_t>{},
 128                   getSortedTopBitsIntegerInputs<__uint128_t>)
 129     ->Arg(TestNumInputs);
 130
 131 BENCHMARK_CAPTURE(BM_FindRehash,
 132                   unordered_set_sorted_uint128,
 133                   std::unordered_set<__uint128_t>{},
 134                   getSortedTopBitsIntegerInputs<__uint128_t>)
 135     ->Arg(TestNumInputs);
 136 #endif
 137
 138 // Sorted //
 139 BENCHMARK_CAPTURE(
 140     BM_Find, unordered_set_sorted_uint32, std::unordered_set<uint32_t>{}, getSortedIntegerInputs<uint32_t>)
 141     ->Arg(TestNumInputs);
 142
 143 BENCHMARK_CAPTURE(BM_FindRehash,
 144                   unordered_set_sorted_uint32,
 145                   std::unordered_set<uint32_t, NonIdentityScalarHash>{},
 146                   getSortedIntegerInputs<uint32_t>)
 147     ->Arg(TestNumInputs);
 148
 149 // Sorted Ascending //
 150 BENCHMARK_CAPTURE(
 151     BM_Find, unordered_set_sorted_large_uint64, std::unordered_set<uint64_t>{}, getSortedLargeIntegerInputs<uint64_t>)
 152     ->Arg(TestNumInputs);
 153
 154 BENCHMARK_CAPTURE(BM_FindRehash,
 155                   unordered_set_sorted_large_uint64,
 156                   std::unordered_set<uint64_t, NonIdentityScalarHash>{},
 157                   getSortedLargeIntegerInputs<uint64_t>)
 158     ->Arg(TestNumInputs);
 159
 160 // Top Bits //
 161 BENCHMARK_CAPTURE(
 162     BM_Find, unordered_set_top_bits_uint64, std::unordered_set<uint64_t>{}, getSortedTopBitsIntegerInputs<uint64_t>)
 163     ->Arg(TestNumInputs);
 164
 165 BENCHMARK_CAPTURE(BM_FindRehash,
 166                   unordered_set_top_bits_uint64,
 167                   std::unordered_set<uint64_t, NonIdentityScalarHash>{},
 168                   getSortedTopBitsIntegerInputs<uint64_t>)
 169     ->Arg(TestNumInputs);
 170
 171 // String //
 172 BENCHMARK_CAPTURE(BM_Find, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 173     ->Arg(TestNumInputs);
 174
 175 BENCHMARK_CAPTURE(BM_FindRehash, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 176     ->Arg(TestNumInputs);
 177
 178 // Prefixed String //
 179 BENCHMARK_CAPTURE(
 180     BM_Find, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
 181     ->Arg(TestNumInputs);
 182
 183 BENCHMARK_CAPTURE(
 184     BM_FindRehash, unordered_set_prefixed_string, std::unordered_set<std::string>{}, getPrefixedRandomStringInputs)
 185     ->Arg(TestNumInputs);
 186
 187 //----------------------------------------------------------------------------//
 188 //                         BM_Rehash
 189 // ---------------------------------------------------------------------------//
 190
 191 BENCHMARK_CAPTURE(BM_Rehash,
 192                   unordered_set_string_arg,
 193                   std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
 194                   getRandomStringInputs)
 195     ->Arg(TestNumInputs);
 196
 197 BENCHMARK_CAPTURE(BM_Rehash, unordered_set_int_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 198     ->Arg(TestNumInputs);
 199
 200 //----------------------------------------------------------------------------//
 201 //                         BM_Compare
 202 // ---------------------------------------------------------------------------//
 203
 204 BENCHMARK_CAPTURE(
 205     BM_Compare_same_container, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 206     ->Arg(TestNumInputs);
 207
 208 BENCHMARK_CAPTURE(BM_Compare_same_container, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 209     ->Arg(TestNumInputs);
 210
 211 BENCHMARK_CAPTURE(
 212     BM_Compare_different_containers, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 213     ->Arg(TestNumInputs);
 214
 215 BENCHMARK_CAPTURE(
 216     BM_Compare_different_containers, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 217     ->Arg(TestNumInputs);
 218
 219 ///////////////////////////////////////////////////////////////////////////////
 220 BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 221     ->Arg(TestNumInputs);
 222 BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 223     ->Arg(TestNumInputs);
 224
 225 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_int, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 226     ->Arg(TestNumInputs);
 227 BENCHMARK_CAPTURE(BM_EmplaceDuplicate, unordered_set_string, std::unordered_set<std::string>{}, getRandomStringInputs)
 228     ->Arg(TestNumInputs);
 229
 230 BENCHMARK_CAPTURE(
 231     BM_InsertDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<int>)
 232     ->Arg(TestNumInputs);
 233 BENCHMARK_CAPTURE(
 234     BM_InsertDuplicate, unordered_set_string_insert_arg, std::unordered_set<std::string>{}, getRandomStringInputs)
 235     ->Arg(TestNumInputs);
 236
 237 BENCHMARK_CAPTURE(
 238     BM_EmplaceDuplicate, unordered_set_int_insert_arg, std::unordered_set<int>{}, getRandomIntegerInputs<unsigned>)
 239     ->Arg(TestNumInputs);
 240
 241 BENCHMARK_CAPTURE(
 242     BM_EmplaceDuplicate, unordered_set_string_arg, std::unordered_set<std::string>{}, getRandomCStringInputs)
 243     ->Arg(TestNumInputs);
 244
 245 BENCHMARK_MAIN();