1 files changed, 114 insertions, 3 deletions
diff --git a/absl/container/internal/raw_hash_set_benchmark.cc b/absl/container/internal/raw_hash_set_benchmark.cc
index 88b07373..424b72cf 100644
--- a/absl/container/internal/raw_hash_set_benchmark.cc
+++ b/absl/container/internal/raw_hash_set_benchmark.cc
@@ -12,19 +12,24 @@
 // See the License for the specific language governing permissions and
 // limitations under the License.
 
+#include <algorithm>
 #include <array>
 #include <cmath>
 #include <cstddef>
 #include <cstdint>
+#include <limits>
 #include <numeric>
 #include <random>
+#include <string>
 #include <tuple>
 #include <utility>
 #include <vector>
 
 #include "absl/base/internal/raw_logging.h"
+#include "absl/container/internal/container_memory.h"
 #include "absl/container/internal/hash_function_defaults.h"
 #include "absl/container/internal/raw_hash_set.h"
+#include "absl/random/random.h"
 #include "absl/strings/str_format.h"
 #include "benchmark/benchmark.h"
 
@@ -58,6 +63,11 @@ struct IntPolicy {
   static auto apply(F&& f, int64_t x) -> decltype(std::forward<F>(f)(x, x)) {
     return std::forward<F>(f)(x, x);
   }
+
+  template <class Hash>
+  static constexpr HashSlotFn get_hash_slot_fn() {
+    return nullptr;
+  }
 };
 
 class StringPolicy {
@@ -116,6 +126,11 @@ class StringPolicy {
     return apply_impl(std::forward<F>(f),
                       PairArgs(std::forward<Args>(args)...));
   }
+
+  template <class Hash>
+  static constexpr HashSlotFn get_hash_slot_fn() {
+    return nullptr;
+  }
 };
 
 struct StringHash : container_internal::hash_default_hash<absl::string_view> {
@@ -294,7 +309,7 @@ void BM_CopyCtorSparseInt(benchmark::State& state) {
     benchmark::DoNotOptimize(t2);
   }
 }
-BENCHMARK(BM_CopyCtorSparseInt)->Range(128, 4096);
+BENCHMARK(BM_CopyCtorSparseInt)->Range(1, 4096);
 
 void BM_CopyCtorInt(benchmark::State& state) {
   std::random_device rd;
@@ -312,7 +327,7 @@ void BM_CopyCtorInt(benchmark::State& state) {
     benchmark::DoNotOptimize(t2);
   }
 }
-BENCHMARK(BM_CopyCtorInt)->Range(128, 4096);
+BENCHMARK(BM_CopyCtorInt)->Range(0, 4096);
 
 void BM_CopyCtorString(benchmark::State& state) {
   std::random_device rd;
@@ -330,7 +345,7 @@ void BM_CopyCtorString(benchmark::State& state) {
     benchmark::DoNotOptimize(t2);
   }
 }
-BENCHMARK(BM_CopyCtorString)->Range(128, 4096);
+BENCHMARK(BM_CopyCtorString)->Range(0, 4096);
 
 void BM_CopyAssign(benchmark::State& state) {
   std::random_device rd;
@@ -445,6 +460,19 @@ void BM_Group_Match(benchmark::State& state) {
 }
 BENCHMARK(BM_Group_Match);
 
+void BM_GroupPortable_Match(benchmark::State& state) {
+  std::array<ctrl_t, GroupPortableImpl::kWidth> group;
+  Iota(group.begin(), group.end(), -4);
+  GroupPortableImpl g{group.data()};
+  h2_t h = 1;
+  for (auto _ : state) {
+    ::benchmark::DoNotOptimize(h);
+    ::benchmark::DoNotOptimize(g);
+    ::benchmark::DoNotOptimize(g.Match(h));
+  }
+}
+BENCHMARK(BM_GroupPortable_Match);
+
 void BM_Group_MaskEmpty(benchmark::State& state) {
   std::array<ctrl_t, Group::kWidth> group;
   Iota(group.begin(), group.end(), -4);
@@ -467,6 +495,17 @@ void BM_Group_MaskEmptyOrDeleted(benchmark::State& state) {
 }
 BENCHMARK(BM_Group_MaskEmptyOrDeleted);
 
+void BM_Group_MaskNonFull(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);
+    ::benchmark::DoNotOptimize(g.MaskNonFull());
+  }
+}
+BENCHMARK(BM_Group_MaskNonFull);
+
 void BM_Group_CountLeadingEmptyOrDeleted(benchmark::State& state) {
   std::array<ctrl_t, Group::kWidth> group;
   Iota(group.begin(), group.end(), -2);
@@ -489,6 +528,17 @@ void BM_Group_MatchFirstEmptyOrDeleted(benchmark::State& state) {
 }
 BENCHMARK(BM_Group_MatchFirstEmptyOrDeleted);
 
+void BM_Group_MatchFirstNonFull(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);
+    ::benchmark::DoNotOptimize(g.MaskNonFull().LowestBitSet());
+  }
+}
+BENCHMARK(BM_Group_MatchFirstNonFull);
+
 void BM_DropDeletes(benchmark::State& state) {
   constexpr size_t capacity = (1 << 20) - 1;
   std::vector<ctrl_t> ctrl(capacity + 1 + Group::kWidth);
@@ -528,6 +578,67 @@ void BM_Resize(benchmark::State& state) {
 }
 BENCHMARK(BM_Resize);
 
+void BM_EraseIf(benchmark::State& state) {
+  int64_t num_elements = state.range(0);
+  size_t num_erased = static_cast<size_t>(state.range(1));
+
+  constexpr size_t kRepetitions = 64;
+
+  absl::BitGen rng;
+
+  std::vector<std::vector<int64_t>> keys(kRepetitions);
+  std::vector<IntTable> tables;
+  std::vector<int64_t> threshold;
+  for (auto& k : keys) {
+    tables.push_back(IntTable());
+    auto& table = tables.back();
+    for (int64_t i = 0; i < num_elements; i++) {
+      // We use random keys to reduce noise.
+      k.push_back(
+          absl::Uniform<int64_t>(rng, 0, std::numeric_limits<int64_t>::max()));
+      if (!table.insert(k.back()).second) {
+        k.pop_back();
+        --i;  // duplicated value, retrying
+      }
+    }
+    std::sort(k.begin(), k.end());
+    threshold.push_back(static_cast<int64_t>(num_erased) < num_elements
+                            ? k[num_erased]
+                            : std::numeric_limits<int64_t>::max());
+  }
+
+  while (state.KeepRunningBatch(static_cast<int64_t>(kRepetitions) *
+                                std::max(num_elements, int64_t{1}))) {
+    benchmark::DoNotOptimize(tables);
+    for (size_t t_id = 0; t_id < kRepetitions; t_id++) {
+      auto& table = tables[t_id];
+      benchmark::DoNotOptimize(num_erased);
+      auto pred = [t = threshold[t_id]](int64_t key) { return key < t; };
+      benchmark::DoNotOptimize(pred);
+      benchmark::DoNotOptimize(table);
+      absl::container_internal::EraseIf(pred, &table);
+    }
+    state.PauseTiming();
+    for (size_t t_id = 0; t_id < kRepetitions; t_id++) {
+      auto& k = keys[t_id];
+      auto& table = tables[t_id];
+      for (size_t i = 0; i < num_erased; i++) {
+        table.insert(k[i]);
+      }
+    }
+    state.ResumeTiming();
+  }
+}
+
+BENCHMARK(BM_EraseIf)
+    ->ArgNames({"num_elements", "num_erased"})
+    ->ArgPair(10, 0)
+    ->ArgPair(1000, 0)
+    ->ArgPair(10, 5)
+    ->ArgPair(1000, 500)
+    ->ArgPair(10, 10)
+    ->ArgPair(1000, 1000);
+
 }  // namespace
 }  // namespace container_internal
 ABSL_NAMESPACE_END