Export of internal Abseil changes

--
e7f53dfbf809812e84770217777f81b6308a3084 by Abseil Team <absl-team@google.com>:

Add a parameter pack to absl profile to allow profiles to separate
dynamic data from static data that is available at constructor-time.

Background: `inline_element_size` is effectively constant, but there
is a data race between its initialization and its access. We had fixed that race by making
inline_element_size atomic.  This CL changes `inline_element_size`
back to a non-atomic integer, and provides a way for all profiles to
provide Register()-time values.
PiperOrigin-RevId: 413960559

--
70234c5943f8e37e17c1d9c54d8ed61d39880abf by Chris Kennelly <ckennelly@google.com>:

Document that absl::FunctionRef does not allocate.

PiperOrigin-RevId: 413946831

--
3308ae571412c4be3cc32d088c6edac98ff2d1ed by Samuel Benzaquen <sbenza@google.com>:

Internal change

PiperOrigin-RevId: 413933619

--
1617093a730d055edcf7bc04fdd6509783f5f75d by Martijn Vels <mvels@google.com>:

Internal Change

PiperOrigin-RevId: 413778735

--
03ad683f059c806a6c8b04f5b79b2662c3df8c73 by Evan Brown <ezb@google.com>:

Unify btree erase_if definitions and optimize them so that we only do rebalancing once per leaf node.

PiperOrigin-RevId: 413757280

--
5ba402f70801938178e486617063f01c7862525d by Martijn Vels <mvels@google.com>:

Cleanup up cord sampling internals

PiperOrigin-RevId: 413755011

--
522da8f9d3e0f11630d89fb41952004742bc335a by Evan Brown <ezb@google.com>:

Add b-tree benchmark for erase_if.

Since this benchmark doesn't work for std:: containers before C++20, disable it for them.

PiperOrigin-RevId: 413740844

--
a690ea42de8ed4a761d00235d8b2fb7548ba9732 by Andy Getzendanner <durandal@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 413735737
GitOrigin-RevId: e7f53dfbf809812e84770217777f81b6308a3084
Change-Id: I4f9f9039ba92831bc48971964aa063244c9fed72

1 files changed, 51 insertions, 13 deletions

diff --git a/absl/container/btree_benchmark.cc b/absl/container/btree_benchmark.cc
index 65b6790b..0ca497c8 100644
--- a/absl/container/btree_benchmark.cc
+++ b/absl/container/btree_benchmark.cc
@@ -153,9 +153,9 @@ void BM_FullLookup(benchmark::State& state) {
   BM_LookupImpl<T>(state, true);
 }
 
-// Benchmark deletion of values from a container.
+// Benchmark erasing values from a container.
 template <typename T>
-void BM_Delete(benchmark::State& state) {
+void BM_Erase(benchmark::State& state) {
   using V = typename remove_pair_const<typename T::value_type>::type;
   typename KeyOfValue<typename T::key_type, V>::type key_of_value;
   std::vector<V> values = GenerateValues<V>(kBenchmarkValues);
@@ -180,9 +180,9 @@ void BM_Delete(benchmark::State& state) {
   }
 }
 
-// Benchmark deletion of multiple values from a container.
+// Benchmark erasing multiple values from a container.
 template <typename T>
-void BM_DeleteRange(benchmark::State& state) {
+void BM_EraseRange(benchmark::State& state) {
   using V = typename remove_pair_const<typename T::value_type>::type;
   typename KeyOfValue<typename T::key_type, V>::type key_of_value;
   std::vector<V> values = GenerateValues<V>(kBenchmarkValues);
@@ -222,6 +222,40 @@ void BM_DeleteRange(benchmark::State& state) {
   }
 }
 
+// Predicate that erases every other element. We can't use a lambda because
+// C++11 doesn't support generic lambdas.
+// TODO(b/207389011): consider adding benchmarks that remove different fractions
+// of keys (e.g. 10%, 90%).
+struct EraseIfPred {
+  uint64_t i = 0;
+  template <typename T>
+  bool operator()(const T&) {
+    return ++i % 2;
+  }
+};
+
+// Benchmark erasing multiple values from a container with a predicate.
+template <typename T>
+void BM_EraseIf(benchmark::State& state) {
+  using V = typename remove_pair_const<typename T::value_type>::type;
+  std::vector<V> values = GenerateValues<V>(kBenchmarkValues);
+
+  // Removes half of the keys per batch.
+  const int batch_size = (kBenchmarkValues + 1) / 2;
+  EraseIfPred pred;
+  while (state.KeepRunningBatch(batch_size)) {
+    state.PauseTiming();
+    {
+      T container(values.begin(), values.end());
+      state.ResumeTiming();
+      erase_if(container, pred);
+      benchmark::DoNotOptimize(container);
+      state.PauseTiming();
+    }
+    state.ResumeTiming();
+  }
+}
+
 // Benchmark steady-state insert (into first half of range) and remove (from
 // second half of range), treating the container approximately like a queue with
 // log-time access for all elements. This benchmark does not test the case where
@@ -477,14 +511,14 @@ BTREE_TYPES(Time);
   void BM_##type##_##func(benchmark::State& state) { BM_##func<type>(state); } \
   BENCHMARK(BM_##type##_##func)
 
-#define MY_BENCHMARK3(type)               \
+#define MY_BENCHMARK3_STL(type)           \
   MY_BENCHMARK4(type, Insert);            \
   MY_BENCHMARK4(type, InsertSorted);      \
   MY_BENCHMARK4(type, InsertSmall);       \
   MY_BENCHMARK4(type, Lookup);            \
   MY_BENCHMARK4(type, FullLookup);        \
-  MY_BENCHMARK4(type, Delete);            \
-  MY_BENCHMARK4(type, DeleteRange);       \
+  MY_BENCHMARK4(type, Erase);             \
+  MY_BENCHMARK4(type, EraseRange);        \
   MY_BENCHMARK4(type, QueueAddRem);       \
   MY_BENCHMARK4(type, MixedAddRem);       \
   MY_BENCHMARK4(type, Fifo);              \
@@ -492,9 +526,13 @@ BTREE_TYPES(Time);
   MY_BENCHMARK4(type, InsertRangeRandom); \
   MY_BENCHMARK4(type, InsertRangeSorted)
 
+#define MY_BENCHMARK3(type)     \
+  MY_BENCHMARK4(type, EraseIf); \
+  MY_BENCHMARK3_STL(type)
+
 #define MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(type) \
-  MY_BENCHMARK3(stl_##type);                    \
-  MY_BENCHMARK3(stl_unordered_##type);          \
+  MY_BENCHMARK3_STL(stl_##type);                \
+  MY_BENCHMARK3_STL(stl_unordered_##type);      \
   MY_BENCHMARK3(btree_256_##type)
 
 #define MY_BENCHMARK2(type)                \
@@ -684,12 +722,12 @@ double ContainerInfo(const btree_map<int, BigTypePtr<Size>>& b) {
       btree_set<BigTypePtr<SIZE>>;                                             \
   using btree_256_map_size##SIZE##copies##SIZE##ptr =                          \
       btree_map<int, BigTypePtr<SIZE>>;                                        \
-  MY_BENCHMARK3(stl_set_size##SIZE##copies##SIZE##ptr);                        \
-  MY_BENCHMARK3(stl_unordered_set_size##SIZE##copies##SIZE##ptr);              \
+  MY_BENCHMARK3_STL(stl_set_size##SIZE##copies##SIZE##ptr);                    \
+  MY_BENCHMARK3_STL(stl_unordered_set_size##SIZE##copies##SIZE##ptr);          \
   MY_BENCHMARK3(flat_hash_set_size##SIZE##copies##SIZE##ptr);                  \
   MY_BENCHMARK3(btree_256_set_size##SIZE##copies##SIZE##ptr);                  \
-  MY_BENCHMARK3(stl_map_size##SIZE##copies##SIZE##ptr);                        \
-  MY_BENCHMARK3(stl_unordered_map_size##SIZE##copies##SIZE##ptr);              \
+  MY_BENCHMARK3_STL(stl_map_size##SIZE##copies##SIZE##ptr);                    \
+  MY_BENCHMARK3_STL(stl_unordered_map_size##SIZE##copies##SIZE##ptr);          \
   MY_BENCHMARK3(flat_hash_map_size##SIZE##copies##SIZE##ptr);                  \
   MY_BENCHMARK3(btree_256_map_size##SIZE##copies##SIZE##ptr)