[libc++] Don't call key_eq in unordered_map/set rehashing routine
As of now containers key_eq might get called when rehashing happens, which is redundant for unique keys containers.
Reviewed By: #libc, philnik, Mordante
Differential Revision: https://reviews.llvm.org/D128021
NOKEYCHECK=True
GitOrigin-RevId: 3085e42f80ac09e53864380ea1c71f3adb643d7c
diff --git a/benchmarks/ContainerBenchmarks.h b/benchmarks/ContainerBenchmarks.h
index d2061f2..f64869a 100644
--- a/benchmarks/ContainerBenchmarks.h
+++ b/benchmarks/ContainerBenchmarks.h
@@ -135,6 +135,20 @@
}
}
+template <class Container, class GenInputs>
+static void BM_Rehash(benchmark::State& st, Container c, GenInputs gen) {
+ auto in = gen(st.range(0));
+ c.max_load_factor(3.0);
+ c.insert(in.begin(), in.end());
+ benchmark::DoNotOptimize(c);
+ const auto bucket_count = c.bucket_count();
+ while (st.KeepRunning()) {
+ c.rehash(bucket_count + 1);
+ c.rehash(bucket_count);
+ benchmark::ClobberMemory();
+ }
+}
+
} // end namespace ContainerBenchmarks
#endif // BENCHMARK_CONTAINER_BENCHMARKS_H
diff --git a/benchmarks/unordered_set_operations.bench.cpp b/benchmarks/unordered_set_operations.bench.cpp
index e0030d6..acabc73 100644
--- a/benchmarks/unordered_set_operations.bench.cpp
+++ b/benchmarks/unordered_set_operations.bench.cpp
@@ -104,6 +104,27 @@
}
};
+// The sole purpose of this comparator is to be used in BM_Rehash, where
+// we need something slow enough to be easily noticable in benchmark results.
+// The default implementation of operator== for strings seems to be a little
+// too fast for that specific benchmark to reliably show a noticeable
+// improvement, but unoptimized bytewise comparison fits just right.
+// Early return is there just for convenience, since we only compare strings
+// of equal length in BM_Rehash.
+struct SlowStringEq {
+ SlowStringEq() = default;
+ inline TEST_ALWAYS_INLINE
+ bool operator()(const std::string& lhs, const std::string& rhs) const {
+ if (lhs.size() != rhs.size()) return false;
+
+ bool eq = true;
+ for (size_t i = 0; i < lhs.size(); ++i) {
+ eq &= lhs[i] == rhs[i];
+ }
+ return eq;
+ }
+};
+
//----------------------------------------------------------------------------//
// BM_Hash
// ---------------------------------------------------------------------------//
@@ -266,6 +287,20 @@
std::unordered_set<std::string>{},
getRandomStringInputs)->Arg(TestNumInputs);
+//----------------------------------------------------------------------------//
+// BM_Rehash
+// ---------------------------------------------------------------------------//
+
+BENCHMARK_CAPTURE(BM_Rehash,
+ unordered_set_string_arg,
+ std::unordered_set<std::string, std::hash<std::string>, SlowStringEq>{},
+ getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Rehash,
+ unordered_set_int_arg,
+ std::unordered_set<int>{},
+ getRandomIntegerInputs<int>)->Arg(TestNumInputs);
+
///////////////////////////////////////////////////////////////////////////////
BENCHMARK_CAPTURE(BM_InsertDuplicate,
unordered_set_int,