1 files changed, 109 insertions, 22 deletions

diff --git a/third_party/abseil-cpp/absl/container/internal/raw_hash_set_benchmark.cc b/third_party/abseil-cpp/absl/container/internal/raw_hash_set_benchmark.cc
index c886d3ad43..e17ba9b43f 100644
--- a/third_party/abseil-cpp/absl/container/internal/raw_hash_set_benchmark.cc
+++ b/third_party/abseil-cpp/absl/container/internal/raw_hash_set_benchmark.cc
@@ -12,13 +12,16 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
-#include "absl/container/internal/raw_hash_set.h"
-
+#include <array>
+#include <cmath>
 #include <numeric>
 #include <random>
+#include <utility>
+#include <vector>
 
 #include "absl/base/internal/raw_logging.h"
 #include "absl/container/internal/hash_function_defaults.h"
+#include "absl/container/internal/raw_hash_set.h"
 #include "absl/strings/str_format.h"
 #include "benchmark/benchmark.h"
 
@@ -202,40 +205,113 @@ void CacheInSteadyStateArgs(Benchmark* bm) {
 BENCHMARK(BM_CacheInSteadyState)->Apply(CacheInSteadyStateArgs);
 
 void BM_EndComparison(benchmark::State& state) {
+  StringTable t = {{"a", "a"}, {"b", "b"}};
+  auto it = t.begin();
+  for (auto i : state) {
+    benchmark::DoNotOptimize(t);
+    benchmark::DoNotOptimize(it);
+    benchmark::DoNotOptimize(it != t.end());
+  }
+}
+BENCHMARK(BM_EndComparison);
+
+void BM_Iteration(benchmark::State& state) {
   std::random_device rd;
   std::mt19937 rng(rd());
   string_generator gen{12};
   StringTable t;
-  while (t.size() < state.range(0)) {
+
+  size_t capacity = state.range(0);
+  size_t size = state.range(1);
+  t.reserve(capacity);
+
+  while (t.size() < size) {
     t.emplace(gen(rng), gen(rng));
   }
 
-  for (auto _ : state) {
+  for (auto i : state) {
+    benchmark::DoNotOptimize(t);
     for (auto it = t.begin(); it != t.end(); ++it) {
-      benchmark::DoNotOptimize(it);
-      benchmark::DoNotOptimize(t);
-      benchmark::DoNotOptimize(it != t.end());
+      benchmark::DoNotOptimize(*it);
     }
   }
 }
-BENCHMARK(BM_EndComparison)->Arg(400);
 
-void BM_CopyCtor(benchmark::State& state) {
+BENCHMARK(BM_Iteration)
+    ->ArgPair(1, 1)
+    ->ArgPair(2, 2)
+    ->ArgPair(4, 4)
+    ->ArgPair(7, 7)
+    ->ArgPair(10, 10)
+    ->ArgPair(15, 15)
+    ->ArgPair(16, 16)
+    ->ArgPair(54, 54)
+    ->ArgPair(100, 100)
+    ->ArgPair(400, 400)
+    // empty
+    ->ArgPair(0, 0)
+    ->ArgPair(10, 0)
+    ->ArgPair(100, 0)
+    ->ArgPair(1000, 0)
+    ->ArgPair(10000, 0)
+    // sparse
+    ->ArgPair(100, 1)
+    ->ArgPair(1000, 10);
+
+void BM_CopyCtorSparseInt(benchmark::State& state) {
   std::random_device rd;
   std::mt19937 rng(rd());
   IntTable t;
   std::uniform_int_distribution<uint64_t> dist(0, ~uint64_t{});
 
-  while (t.size() < state.range(0)) {
+  size_t size = state.range(0);
+  t.reserve(size * 10);
+  while (t.size() < size) {
     t.emplace(dist(rng));
   }
 
-  for (auto _ : state) {
+  for (auto i : state) {
+    IntTable t2 = t;
+    benchmark::DoNotOptimize(t2);
+  }
+}
+BENCHMARK(BM_CopyCtorSparseInt)->Range(128, 4096);
+
+void BM_CopyCtorInt(benchmark::State& state) {
+  std::random_device rd;
+  std::mt19937 rng(rd());
+  IntTable t;
+  std::uniform_int_distribution<uint64_t> dist(0, ~uint64_t{});
+
+  size_t size = state.range(0);
+  while (t.size() < size) {
+    t.emplace(dist(rng));
+  }
+
+  for (auto i : state) {
     IntTable t2 = t;
     benchmark::DoNotOptimize(t2);
   }
 }
-BENCHMARK(BM_CopyCtor)->Range(128, 4096);
+BENCHMARK(BM_CopyCtorInt)->Range(128, 4096);
+
+void BM_CopyCtorString(benchmark::State& state) {
+  std::random_device rd;
+  std::mt19937 rng(rd());
+  StringTable t;
+  std::uniform_int_distribution<uint64_t> dist(0, ~uint64_t{});
+
+  size_t size = state.range(0);
+  while (t.size() < size) {
+    t.emplace(std::to_string(dist(rng)), std::to_string(dist(rng)));
+  }
+
+  for (auto i : state) {
+    StringTable t2 = t;
+    benchmark::DoNotOptimize(t2);
+  }
+}
+BENCHMARK(BM_CopyCtorString)->Range(128, 4096);
 
 void BM_CopyAssign(benchmark::State& state) {
   std::random_device rd;
@@ -330,33 +406,42 @@ void BM_Group_Match(benchmark::State& state) {
   h2_t h = 1;
   for (auto _ : state) {
     ::benchmark::DoNotOptimize(h);
+    ::benchmark::DoNotOptimize(g);
     ::benchmark::DoNotOptimize(g.Match(h));
   }
 }
 BENCHMARK(BM_Group_Match);
 
-void BM_Group_MatchEmpty(benchmark::State& state) {
+void BM_Group_MaskEmpty(benchmark::State& state) {
   std::array<ctrl_t, Group::kWidth> group;
   Iota(group.begin(), group.end(), -4);
   Group g{group.data()};
-  for (auto _ : state) ::benchmark::DoNotOptimize(g.MatchEmpty());
+  for (auto _ : state) {
+    ::benchmark::DoNotOptimize(g);
+    ::benchmark::DoNotOptimize(g.MaskEmpty());
+  }
 }
-BENCHMARK(BM_Group_MatchEmpty);
+BENCHMARK(BM_Group_MaskEmpty);
 
-void BM_Group_MatchEmptyOrDeleted(benchmark::State& state) {
+void BM_Group_MaskEmptyOrDeleted(benchmark::State& state) {
   std::array<ctrl_t, Group::kWidth> group;
   Iota(group.begin(), group.end(), -4);
   Group g{group.data()};
-  for (auto _ : state) ::benchmark::DoNotOptimize(g.MatchEmptyOrDeleted());
+  for (auto _ : state) {
+    ::benchmark::DoNotOptimize(g);
+    ::benchmark::DoNotOptimize(g.MaskEmptyOrDeleted());
+  }
 }
-BENCHMARK(BM_Group_MatchEmptyOrDeleted);
+BENCHMARK(BM_Group_MaskEmptyOrDeleted);
 
 void BM_Group_CountLeadingEmptyOrDeleted(benchmark::State& state) {
   std::array<ctrl_t, Group::kWidth> group;
   Iota(group.begin(), group.end(), -2);
   Group g{group.data()};
-  for (auto _ : state)
+  for (auto _ : state) {
+    ::benchmark::DoNotOptimize(g);
     ::benchmark::DoNotOptimize(g.CountLeadingEmptyOrDeleted());
+  }
 }
 BENCHMARK(BM_Group_CountLeadingEmptyOrDeleted);
 
@@ -364,7 +449,10 @@ void BM_Group_MatchFirstEmptyOrDeleted(benchmark::State& state) {
   std::array<ctrl_t, Group::kWidth> group;
   Iota(group.begin(), group.end(), -2);
   Group g{group.data()};
-  for (auto _ : state) ::benchmark::DoNotOptimize(*g.MatchEmptyOrDeleted());
+  for (auto _ : state) {
+    ::benchmark::DoNotOptimize(g);
+    ::benchmark::DoNotOptimize(g.MaskEmptyOrDeleted().LowestBitSet());
+  }
 }
 BENCHMARK(BM_Group_MatchFirstEmptyOrDeleted);
 
@@ -425,7 +513,6 @@ void CodegenAbslRawHashSetInt64Iterate(
 int odr =
     (::benchmark::DoNotOptimize(std::make_tuple(
          &CodegenAbslRawHashSetInt64Find, &CodegenAbslRawHashSetInt64FindNeEnd,
-         &CodegenAbslRawHashSetInt64Insert,
-         &CodegenAbslRawHashSetInt64Contains,
+         &CodegenAbslRawHashSetInt64Insert, &CodegenAbslRawHashSetInt64Contains,
          &CodegenAbslRawHashSetInt64Iterate)),
      1);