Add 'third_party/abseil_cpp/' from commit '768eb2ca2857342673fcd462792ce04b8bac3fa3' r/781

git-subtree-dir: third_party/abseil_cpp
git-subtree-mainline: ffb2ae54beb5796cd408fbe15d2d2da09ff37adf
git-subtree-split: 768eb2ca2857342673fcd462792ce04b8bac3fa3

1 files changed, 735 insertions, 0 deletions

diff --git a/third_party/abseil_cpp/absl/container/btree_benchmark.cc b/third_party/abseil_cpp/absl/container/btree_benchmark.cc
new file mode 100644
index 000000000000..467986768aa1
--- /dev/null
+++ b/third_party/abseil_cpp/absl/container/btree_benchmark.cc
@@ -0,0 +1,735 @@
+// Copyright 2018 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <stdint.h>
+
+#include <algorithm>
+#include <functional>
+#include <map>
+#include <numeric>
+#include <random>
+#include <set>
+#include <string>
+#include <type_traits>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+#include "absl/base/internal/raw_logging.h"
+#include "absl/container/btree_map.h"
+#include "absl/container/btree_set.h"
+#include "absl/container/btree_test.h"
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/flat_hash_set.h"
+#include "absl/container/internal/hashtable_debug.h"
+#include "absl/flags/flag.h"
+#include "absl/hash/hash.h"
+#include "absl/memory/memory.h"
+#include "absl/strings/cord.h"
+#include "absl/strings/str_format.h"
+#include "absl/time/time.h"
+#include "benchmark/benchmark.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace container_internal {
+namespace {
+
+constexpr size_t kBenchmarkValues = 1 << 20;
+
+// How many times we add and remove sub-batches in one batch of *AddRem
+// benchmarks.
+constexpr size_t kAddRemBatchSize = 1 << 2;
+
+// Generates n values in the range [0, 4 * n].
+template <typename V>
+std::vector<V> GenerateValues(int n) {
+  constexpr int kSeed = 23;
+  return GenerateValuesWithSeed<V>(n, 4 * n, kSeed);
+}
+
+// Benchmark insertion of values into a container.
+template <typename T>
+void BM_InsertImpl(benchmark::State& state, bool sorted) {
+  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);
+  if (sorted) {
+    std::sort(values.begin(), values.end());
+  }
+  T container(values.begin(), values.end());
+
+  // Remove and re-insert 10% of the keys per batch.
+  const int batch_size = (kBenchmarkValues + 9) / 10;
+  while (state.KeepRunningBatch(batch_size)) {
+    state.PauseTiming();
+    const auto i = static_cast<int>(state.iterations());
+
+    for (int j = i; j < i + batch_size; j++) {
+      int x = j % kBenchmarkValues;
+      container.erase(key_of_value(values[x]));
+    }
+
+    state.ResumeTiming();
+
+    for (int j = i; j < i + batch_size; j++) {
+      int x = j % kBenchmarkValues;
+      container.insert(values[x]);
+    }
+  }
+}
+
+template <typename T>
+void BM_Insert(benchmark::State& state) {
+  BM_InsertImpl<T>(state, false);
+}
+
+template <typename T>
+void BM_InsertSorted(benchmark::State& state) {
+  BM_InsertImpl<T>(state, true);
+}
+
+// container::insert sometimes returns a pair<iterator, bool> and sometimes
+// returns an iterator (for multi- containers).
+template <typename Iter>
+Iter GetIterFromInsert(const std::pair<Iter, bool>& pair) {
+  return pair.first;
+}
+template <typename Iter>
+Iter GetIterFromInsert(const Iter iter) {
+  return iter;
+}
+
+// Benchmark insertion of values into a container at the end.
+template <typename T>
+void BM_InsertEnd(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;
+
+  T container;
+  const int kSize = 10000;
+  for (int i = 0; i < kSize; ++i) {
+    container.insert(Generator<V>(kSize)(i));
+  }
+  V v = Generator<V>(kSize)(kSize - 1);
+  typename T::key_type k = key_of_value(v);
+
+  auto it = container.find(k);
+  while (state.KeepRunning()) {
+    // Repeatedly removing then adding v.
+    container.erase(it);
+    it = GetIterFromInsert(container.insert(v));
+  }
+}
+
+// Benchmark inserting the first few elements in a container. In b-tree, this is
+// when the root node grows.
+template <typename T>
+void BM_InsertSmall(benchmark::State& state) {
+  using V = typename remove_pair_const<typename T::value_type>::type;
+
+  const int kSize = 8;
+  std::vector<V> values = GenerateValues<V>(kSize);
+  T container;
+
+  while (state.KeepRunningBatch(kSize)) {
+    for (int i = 0; i < kSize; ++i) {
+      benchmark::DoNotOptimize(container.insert(values[i]));
+    }
+    state.PauseTiming();
+    // Do not measure the time it takes to clear the container.
+    container.clear();
+    state.ResumeTiming();
+  }
+}
+
+template <typename T>
+void BM_LookupImpl(benchmark::State& state, bool sorted) {
+  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);
+  if (sorted) {
+    std::sort(values.begin(), values.end());
+  }
+  T container(values.begin(), values.end());
+
+  while (state.KeepRunning()) {
+    int idx = state.iterations() % kBenchmarkValues;
+    benchmark::DoNotOptimize(container.find(key_of_value(values[idx])));
+  }
+}
+
+// Benchmark lookup of values in a container.
+template <typename T>
+void BM_Lookup(benchmark::State& state) {
+  BM_LookupImpl<T>(state, false);
+}
+
+// Benchmark lookup of values in a full container, meaning that values
+// are inserted in-order to take advantage of biased insertion, which
+// yields a full tree.
+template <typename T>
+void BM_FullLookup(benchmark::State& state) {
+  BM_LookupImpl<T>(state, true);
+}
+
+// Benchmark deletion of values from a container.
+template <typename T>
+void BM_Delete(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);
+  T container(values.begin(), values.end());
+
+  // Remove and re-insert 10% of the keys per batch.
+  const int batch_size = (kBenchmarkValues + 9) / 10;
+  while (state.KeepRunningBatch(batch_size)) {
+    const int i = state.iterations();
+
+    for (int j = i; j < i + batch_size; j++) {
+      int x = j % kBenchmarkValues;
+      container.erase(key_of_value(values[x]));
+    }
+
+    state.PauseTiming();
+    for (int j = i; j < i + batch_size; j++) {
+      int x = j % kBenchmarkValues;
+      container.insert(values[x]);
+    }
+    state.ResumeTiming();
+  }
+}
+
+// Benchmark deletion of multiple values from a container.
+template <typename T>
+void BM_DeleteRange(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);
+  T container(values.begin(), values.end());
+
+  // Remove and re-insert 10% of the keys per batch.
+  const int batch_size = (kBenchmarkValues + 9) / 10;
+  while (state.KeepRunningBatch(batch_size)) {
+    const int i = state.iterations();
+
+    const int start_index = i % kBenchmarkValues;
+
+    state.PauseTiming();
+    {
+      std::vector<V> removed;
+      removed.reserve(batch_size);
+      auto itr = container.find(key_of_value(values[start_index]));
+      auto start = itr;
+      for (int j = 0; j < batch_size; j++) {
+        if (itr == container.end()) {
+          state.ResumeTiming();
+          container.erase(start, itr);
+          state.PauseTiming();
+          itr = container.begin();
+          start = itr;
+        }
+        removed.push_back(*itr++);
+      }
+
+      state.ResumeTiming();
+      container.erase(start, itr);
+      state.PauseTiming();
+
+      container.insert(removed.begin(), removed.end());
+    }
+    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
+// insertion and removal happen in the same region of the tree.  This benchmark
+// counts two value constructors.
+template <typename T>
+void BM_QueueAddRem(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;
+
+  ABSL_RAW_CHECK(kBenchmarkValues % 2 == 0, "for performance");
+
+  T container;
+
+  const size_t half = kBenchmarkValues / 2;
+  std::vector<int> remove_keys(half);
+  std::vector<int> add_keys(half);
+
+  // We want to do the exact same work repeatedly, and the benchmark can end
+  // after a different number of iterations depending on the speed of the
+  // individual run so we use a large batch size here and ensure that we do
+  // deterministic work every batch.
+  while (state.KeepRunningBatch(half * kAddRemBatchSize)) {
+    state.PauseTiming();
+
+    container.clear();
+
+    for (size_t i = 0; i < half; ++i) {
+      remove_keys[i] = i;
+      add_keys[i] = i;
+    }
+    constexpr int kSeed = 5;
+    std::mt19937_64 rand(kSeed);
+    std::shuffle(remove_keys.begin(), remove_keys.end(), rand);
+    std::shuffle(add_keys.begin(), add_keys.end(), rand);
+
+    // Note needs lazy generation of values.
+    Generator<V> g(kBenchmarkValues * kAddRemBatchSize);
+
+    for (size_t i = 0; i < half; ++i) {
+      container.insert(g(add_keys[i]));
+      container.insert(g(half + remove_keys[i]));
+    }
+
+    // There are three parts each of size "half":
+    // 1 is being deleted from  [offset - half, offset)
+    // 2 is standing            [offset, offset + half)
+    // 3 is being inserted into [offset + half, offset + 2 * half)
+    size_t offset = 0;
+
+    for (size_t i = 0; i < kAddRemBatchSize; ++i) {
+      std::shuffle(remove_keys.begin(), remove_keys.end(), rand);
+      std::shuffle(add_keys.begin(), add_keys.end(), rand);
+      offset += half;
+
+      state.ResumeTiming();
+      for (size_t idx = 0; idx < half; ++idx) {
+        container.erase(key_of_value(g(offset - half + remove_keys[idx])));
+        container.insert(g(offset + half + add_keys[idx]));
+      }
+      state.PauseTiming();
+    }
+    state.ResumeTiming();
+  }
+}
+
+// Mixed insertion and deletion in the same range using pre-constructed values.
+template <typename T>
+void BM_MixedAddRem(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;
+
+  ABSL_RAW_CHECK(kBenchmarkValues % 2 == 0, "for performance");
+
+  T container;
+
+  // Create two random shuffles
+  std::vector<int> remove_keys(kBenchmarkValues);
+  std::vector<int> add_keys(kBenchmarkValues);
+
+  // We want to do the exact same work repeatedly, and the benchmark can end
+  // after a different number of iterations depending on the speed of the
+  // individual run so we use a large batch size here and ensure that we do
+  // deterministic work every batch.
+  while (state.KeepRunningBatch(kBenchmarkValues * kAddRemBatchSize)) {
+    state.PauseTiming();
+
+    container.clear();
+
+    constexpr int kSeed = 7;
+    std::mt19937_64 rand(kSeed);
+
+    std::vector<V> values = GenerateValues<V>(kBenchmarkValues * 2);
+
+    // Insert the first half of the values (already in random order)
+    container.insert(values.begin(), values.begin() + kBenchmarkValues);
+
+    // Insert the first half of the values (already in random order)
+    for (size_t i = 0; i < kBenchmarkValues; ++i) {
+      // remove_keys and add_keys will be swapped before each round,
+      // therefore fill add_keys here w/ the keys being inserted, so
+      // they'll be the first to be removed.
+      remove_keys[i] = i + kBenchmarkValues;
+      add_keys[i] = i;
+    }
+
+    for (size_t i = 0; i < kAddRemBatchSize; ++i) {
+      remove_keys.swap(add_keys);
+      std::shuffle(remove_keys.begin(), remove_keys.end(), rand);
+      std::shuffle(add_keys.begin(), add_keys.end(), rand);
+
+      state.ResumeTiming();
+      for (size_t idx = 0; idx < kBenchmarkValues; ++idx) {
+        container.erase(key_of_value(values[remove_keys[idx]]));
+        container.insert(values[add_keys[idx]]);
+      }
+      state.PauseTiming();
+    }
+    state.ResumeTiming();
+  }
+}
+
+// Insertion at end, removal from the beginning.  This benchmark
+// counts two value constructors.
+// TODO(ezb): we could add a GenerateNext version of generator that could reduce
+// noise for string-like types.
+template <typename T>
+void BM_Fifo(benchmark::State& state) {
+  using V = typename remove_pair_const<typename T::value_type>::type;
+
+  T container;
+  // Need lazy generation of values as state.max_iterations is large.
+  Generator<V> g(kBenchmarkValues + state.max_iterations);
+
+  for (int i = 0; i < kBenchmarkValues; i++) {
+    container.insert(g(i));
+  }
+
+  while (state.KeepRunning()) {
+    container.erase(container.begin());
+    container.insert(container.end(), g(state.iterations() + kBenchmarkValues));
+  }
+}
+
+// Iteration (forward) through the tree
+template <typename T>
+void BM_FwdIter(benchmark::State& state) {
+  using V = typename remove_pair_const<typename T::value_type>::type;
+  using R = typename T::value_type const*;
+
+  std::vector<V> values = GenerateValues<V>(kBenchmarkValues);
+  T container(values.begin(), values.end());
+
+  auto iter = container.end();
+
+  R r = nullptr;
+
+  while (state.KeepRunning()) {
+    if (iter == container.end()) iter = container.begin();
+    r = &(*iter);
+    ++iter;
+  }
+
+  benchmark::DoNotOptimize(r);
+}
+
+// Benchmark random range-construction of a container.
+template <typename T>
+void BM_RangeConstructionImpl(benchmark::State& state, bool sorted) {
+  using V = typename remove_pair_const<typename T::value_type>::type;
+
+  std::vector<V> values = GenerateValues<V>(kBenchmarkValues);
+  if (sorted) {
+    std::sort(values.begin(), values.end());
+  }
+  {
+    T container(values.begin(), values.end());
+  }
+
+  while (state.KeepRunning()) {
+    T container(values.begin(), values.end());
+    benchmark::DoNotOptimize(container);
+  }
+}
+
+template <typename T>
+void BM_InsertRangeRandom(benchmark::State& state) {
+  BM_RangeConstructionImpl<T>(state, false);
+}
+
+template <typename T>
+void BM_InsertRangeSorted(benchmark::State& state) {
+  BM_RangeConstructionImpl<T>(state, true);
+}
+
+#define STL_ORDERED_TYPES(value)                     \
+  using stl_set_##value = std::set<value>;           \
+  using stl_map_##value = std::map<value, intptr_t>; \
+  using stl_multiset_##value = std::multiset<value>; \
+  using stl_multimap_##value = std::multimap<value, intptr_t>
+
+using StdString = std::string;
+STL_ORDERED_TYPES(int32_t);
+STL_ORDERED_TYPES(int64_t);
+STL_ORDERED_TYPES(StdString);
+STL_ORDERED_TYPES(Cord);
+STL_ORDERED_TYPES(Time);
+
+#define STL_UNORDERED_TYPES(value)                                       \
+  using stl_unordered_set_##value = std::unordered_set<value>;           \
+  using stl_unordered_map_##value = std::unordered_map<value, intptr_t>; \
+  using flat_hash_set_##value = flat_hash_set<value>;                    \
+  using flat_hash_map_##value = flat_hash_map<value, intptr_t>;          \
+  using stl_unordered_multiset_##value = std::unordered_multiset<value>; \
+  using stl_unordered_multimap_##value =                                 \
+      std::unordered_multimap<value, intptr_t>
+
+#define STL_UNORDERED_TYPES_CUSTOM_HASH(value, hash)                           \
+  using stl_unordered_set_##value = std::unordered_set<value, hash>;           \
+  using stl_unordered_map_##value = std::unordered_map<value, intptr_t, hash>; \
+  using flat_hash_set_##value = flat_hash_set<value, hash>;                    \
+  using flat_hash_map_##value = flat_hash_map<value, intptr_t, hash>;          \
+  using stl_unordered_multiset_##value = std::unordered_multiset<value, hash>; \
+  using stl_unordered_multimap_##value =                                       \
+      std::unordered_multimap<value, intptr_t, hash>
+
+STL_UNORDERED_TYPES_CUSTOM_HASH(Cord, absl::Hash<absl::Cord>);
+
+STL_UNORDERED_TYPES(int32_t);
+STL_UNORDERED_TYPES(int64_t);
+STL_UNORDERED_TYPES(StdString);
+STL_UNORDERED_TYPES_CUSTOM_HASH(Time, absl::Hash<absl::Time>);
+
+#define BTREE_TYPES(value)                                            \
+  using btree_256_set_##value =                                       \
+      btree_set<value, std::less<value>, std::allocator<value>>;      \
+  using btree_256_map_##value =                                       \
+      btree_map<value, intptr_t, std::less<value>,                    \
+                std::allocator<std::pair<const value, intptr_t>>>;    \
+  using btree_256_multiset_##value =                                  \
+      btree_multiset<value, std::less<value>, std::allocator<value>>; \
+  using btree_256_multimap_##value =                                  \
+      btree_multimap<value, intptr_t, std::less<value>,               \
+                     std::allocator<std::pair<const value, intptr_t>>>
+
+BTREE_TYPES(int32_t);
+BTREE_TYPES(int64_t);
+BTREE_TYPES(StdString);
+BTREE_TYPES(Cord);
+BTREE_TYPES(Time);
+
+#define MY_BENCHMARK4(type, func)                                              \
+  void BM_##type##_##func(benchmark::State& state) { BM_##func<type>(state); } \
+  BENCHMARK(BM_##type##_##func)
+
+#define MY_BENCHMARK3(type)               \
+  MY_BENCHMARK4(type, Insert);            \
+  MY_BENCHMARK4(type, InsertSorted);      \
+  MY_BENCHMARK4(type, InsertEnd);         \
+  MY_BENCHMARK4(type, InsertSmall);       \
+  MY_BENCHMARK4(type, Lookup);            \
+  MY_BENCHMARK4(type, FullLookup);        \
+  MY_BENCHMARK4(type, Delete);            \
+  MY_BENCHMARK4(type, DeleteRange);       \
+  MY_BENCHMARK4(type, QueueAddRem);       \
+  MY_BENCHMARK4(type, MixedAddRem);       \
+  MY_BENCHMARK4(type, Fifo);              \
+  MY_BENCHMARK4(type, FwdIter);           \
+  MY_BENCHMARK4(type, InsertRangeRandom); \
+  MY_BENCHMARK4(type, InsertRangeSorted)
+
+#define MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(type) \
+  MY_BENCHMARK3(stl_##type);                    \
+  MY_BENCHMARK3(stl_unordered_##type);          \
+  MY_BENCHMARK3(btree_256_##type)
+
+#define MY_BENCHMARK2(type)                \
+  MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(type); \
+  MY_BENCHMARK3(flat_hash_##type)
+
+// Define MULTI_TESTING to see benchmarks for multi-containers also.
+//
+// You can use --copt=-DMULTI_TESTING.
+#ifdef MULTI_TESTING
+#define MY_BENCHMARK(type)                            \
+  MY_BENCHMARK2(set_##type);                          \
+  MY_BENCHMARK2(map_##type);                          \
+  MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(multiset_##type); \
+  MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(multimap_##type)
+#else
+#define MY_BENCHMARK(type)   \
+  MY_BENCHMARK2(set_##type); \
+  MY_BENCHMARK2(map_##type)
+#endif
+
+MY_BENCHMARK(int32_t);
+MY_BENCHMARK(int64_t);
+MY_BENCHMARK(StdString);
+MY_BENCHMARK(Cord);
+MY_BENCHMARK(Time);
+
+// Define a type whose size and cost of moving are independently customizable.
+// When sizeof(value_type) increases, we expect btree to no longer have as much
+// cache-locality advantage over STL. When cost of moving increases, we expect
+// btree to actually do more work than STL because it has to move values around
+// and STL doesn't have to.
+template <int Size, int Copies>
+struct BigType {
+  BigType() : BigType(0) {}
+  explicit BigType(int x) { std::iota(values.begin(), values.end(), x); }
+
+  void Copy(const BigType& other) {
+    for (int i = 0; i < Size && i < Copies; ++i) values[i] = other.values[i];
+    // If Copies > Size, do extra copies.
+    for (int i = Size, idx = 0; i < Copies; ++i) {
+      int64_t tmp = other.values[idx];
+      benchmark::DoNotOptimize(tmp);
+      idx = idx + 1 == Size ? 0 : idx + 1;
+    }
+  }
+
+  BigType(const BigType& other) { Copy(other); }
+  BigType& operator=(const BigType& other) {
+    Copy(other);
+    return *this;
+  }
+
+  // Compare only the first Copies elements if Copies is less than Size.
+  bool operator<(const BigType& other) const {
+    return std::lexicographical_compare(
+        values.begin(), values.begin() + std::min(Size, Copies),
+        other.values.begin(), other.values.begin() + std::min(Size, Copies));
+  }
+  bool operator==(const BigType& other) const {
+    return std::equal(values.begin(), values.begin() + std::min(Size, Copies),
+                      other.values.begin());
+  }
+
+  // Support absl::Hash.
+  template <typename State>
+  friend State AbslHashValue(State h, const BigType& b) {
+    for (int i = 0; i < Size && i < Copies; ++i)
+      h = State::combine(std::move(h), b.values[i]);
+    return h;
+  }
+
+  std::array<int64_t, Size> values;
+};
+
+#define BIG_TYPE_BENCHMARKS(SIZE, COPIES)                                     \
+  using stl_set_size##SIZE##copies##COPIES = std::set<BigType<SIZE, COPIES>>; \
+  using stl_map_size##SIZE##copies##COPIES =                                  \
+      std::map<BigType<SIZE, COPIES>, intptr_t>;                              \
+  using stl_multiset_size##SIZE##copies##COPIES =                             \
+      std::multiset<BigType<SIZE, COPIES>>;                                   \
+  using stl_multimap_size##SIZE##copies##COPIES =                             \
+      std::multimap<BigType<SIZE, COPIES>, intptr_t>;                         \
+  using stl_unordered_set_size##SIZE##copies##COPIES =                        \
+      std::unordered_set<BigType<SIZE, COPIES>,                               \
+                         absl::Hash<BigType<SIZE, COPIES>>>;                  \
+  using stl_unordered_map_size##SIZE##copies##COPIES =                        \
+      std::unordered_map<BigType<SIZE, COPIES>, intptr_t,                     \
+                         absl::Hash<BigType<SIZE, COPIES>>>;                  \
+  using flat_hash_set_size##SIZE##copies##COPIES =                            \
+      flat_hash_set<BigType<SIZE, COPIES>>;                                   \
+  using flat_hash_map_size##SIZE##copies##COPIES =                            \
+      flat_hash_map<BigType<SIZE, COPIES>, intptr_t>;                         \
+  using stl_unordered_multiset_size##SIZE##copies##COPIES =                   \
+      std::unordered_multiset<BigType<SIZE, COPIES>,                          \
+                              absl::Hash<BigType<SIZE, COPIES>>>;             \
+  using stl_unordered_multimap_size##SIZE##copies##COPIES =                   \
+      std::unordered_multimap<BigType<SIZE, COPIES>, intptr_t,                \
+                              absl::Hash<BigType<SIZE, COPIES>>>;             \
+  using btree_256_set_size##SIZE##copies##COPIES =                            \
+      btree_set<BigType<SIZE, COPIES>>;                                       \
+  using btree_256_map_size##SIZE##copies##COPIES =                            \
+      btree_map<BigType<SIZE, COPIES>, intptr_t>;                             \
+  using btree_256_multiset_size##SIZE##copies##COPIES =                       \
+      btree_multiset<BigType<SIZE, COPIES>>;                                  \
+  using btree_256_multimap_size##SIZE##copies##COPIES =                       \
+      btree_multimap<BigType<SIZE, COPIES>, intptr_t>;                        \
+  MY_BENCHMARK(size##SIZE##copies##COPIES)
+
+// Define BIG_TYPE_TESTING to see benchmarks for more big types.
+//
+// You can use --copt=-DBIG_TYPE_TESTING.
+#ifndef NODESIZE_TESTING
+#ifdef BIG_TYPE_TESTING
+BIG_TYPE_BENCHMARKS(1, 4);
+BIG_TYPE_BENCHMARKS(4, 1);
+BIG_TYPE_BENCHMARKS(4, 4);
+BIG_TYPE_BENCHMARKS(1, 8);
+BIG_TYPE_BENCHMARKS(8, 1);
+BIG_TYPE_BENCHMARKS(8, 8);
+BIG_TYPE_BENCHMARKS(1, 16);
+BIG_TYPE_BENCHMARKS(16, 1);
+BIG_TYPE_BENCHMARKS(16, 16);
+BIG_TYPE_BENCHMARKS(1, 32);
+BIG_TYPE_BENCHMARKS(32, 1);
+BIG_TYPE_BENCHMARKS(32, 32);
+#else
+BIG_TYPE_BENCHMARKS(32, 32);
+#endif
+#endif
+
+// Benchmark using unique_ptrs to large value types. In order to be able to use
+// the same benchmark code as the other types, use a type that holds a
+// unique_ptr and has a copy constructor.
+template <int Size>
+struct BigTypePtr {
+  BigTypePtr() : BigTypePtr(0) {}
+  explicit BigTypePtr(int x) {
+    ptr = absl::make_unique<BigType<Size, Size>>(x);
+  }
+  BigTypePtr(const BigTypePtr& other) {
+    ptr = absl::make_unique<BigType<Size, Size>>(*other.ptr);
+  }
+  BigTypePtr(BigTypePtr&& other) noexcept = default;
+  BigTypePtr& operator=(const BigTypePtr& other) {
+    ptr = absl::make_unique<BigType<Size, Size>>(*other.ptr);
+  }
+  BigTypePtr& operator=(BigTypePtr&& other) noexcept = default;
+
+  bool operator<(const BigTypePtr& other) const { return *ptr < *other.ptr; }
+  bool operator==(const BigTypePtr& other) const { return *ptr == *other.ptr; }
+
+  std::unique_ptr<BigType<Size, Size>> ptr;
+};
+
+template <int Size>
+double ContainerInfo(const btree_set<BigTypePtr<Size>>& b) {
+  const double bytes_used =
+      b.bytes_used() + b.size() * sizeof(BigType<Size, Size>);
+  const double bytes_per_value = bytes_used / b.size();
+  BtreeContainerInfoLog(b, bytes_used, bytes_per_value);
+  return bytes_per_value;
+}
+template <int Size>
+double ContainerInfo(const btree_map<int, BigTypePtr<Size>>& b) {
+  const double bytes_used =
+      b.bytes_used() + b.size() * sizeof(BigType<Size, Size>);
+  const double bytes_per_value = bytes_used / b.size();
+  BtreeContainerInfoLog(b, bytes_used, bytes_per_value);
+  return bytes_per_value;
+}
+
+#define BIG_TYPE_PTR_BENCHMARKS(SIZE)                                          \
+  using stl_set_size##SIZE##copies##SIZE##ptr = std::set<BigType<SIZE, SIZE>>; \
+  using stl_map_size##SIZE##copies##SIZE##ptr =                                \
+      std::map<int, BigType<SIZE, SIZE>>;                                      \
+  using stl_unordered_set_size##SIZE##copies##SIZE##ptr =                      \
+      std::unordered_set<BigType<SIZE, SIZE>,                                  \
+                         absl::Hash<BigType<SIZE, SIZE>>>;                     \
+  using stl_unordered_map_size##SIZE##copies##SIZE##ptr =                      \
+      std::unordered_map<int, BigType<SIZE, SIZE>>;                            \
+  using flat_hash_set_size##SIZE##copies##SIZE##ptr =                          \
+      flat_hash_set<BigType<SIZE, SIZE>>;                                      \
+  using flat_hash_map_size##SIZE##copies##SIZE##ptr =                          \
+      flat_hash_map<int, BigTypePtr<SIZE>>;                                    \
+  using btree_256_set_size##SIZE##copies##SIZE##ptr =                          \
+      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(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(flat_hash_map_size##SIZE##copies##SIZE##ptr);                  \
+  MY_BENCHMARK3(btree_256_map_size##SIZE##copies##SIZE##ptr)
+
+BIG_TYPE_PTR_BENCHMARKS(32);
+
+}  // namespace
+}  // namespace container_internal
+ABSL_NAMESPACE_END
+}  // namespace absl