Export of internal Abseil changes

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

Roll forward of btree_iterator refactoring.

PiperOrigin-RevId: 346116047

--
17984679f16e3e2139b0f14fa76f4a6ca16a3ef9 by Chris Kennelly <ckennelly@google.com>:

Extend absl::StrContains to accept single character needles.

Single characters are more efficient to search for.  Extending this API allows
the abseil-string-find-str-contains Clang Tidy to include this pattern.

The C++ committee has adopted http://wg21.link/P1679 for inclusion in C++23.

PiperOrigin-RevId: 346095060

--
ef20b31c501b1dcaa25e244fd8f8aa43dec09bd6 by Jorg Brown <jorg@google.com>:

Internal change for cord ring

PiperOrigin-RevId: 346087545

--
b70f2c1cb77fc9e733a126e790967d45c5fd1dc7 by Derek Mauro <dmauro@google.com>:

Release layout_benchmark

PiperOrigin-RevId: 345968909

--
3a0eda337ee43622f92cfe14c2aa06f72dc71ee5 by Derek Mauro <dmauro@google.com>:

Release raw_hash_set_probe_benchmark

PiperOrigin-RevId: 345965969

--
abffdb4bb241a2264cb4e73a6262b660bb10447d by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 345733599

--
7c9e24a71188df945be17fe98f700bdb51f81b16 by Derek Mauro <dmauro@google.com>:

Release hash_benchmark

PiperOrigin-RevId: 345721635

--
d68f33f17f9a8cd3f6da8eee3870bdb46402cdc8 by Derek Mauro <dmauro@google.com>:

Release raw_hash_set_benchmark

PiperOrigin-RevId: 345708384

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

Updates the implementation of InlinedVector to accurately express the value-initialization semantics of the default constructor

PiperOrigin-RevId: 345548260

--
1532424deda97d468444c217cc0fa4614099c7c1 by Evan Brown <ezb@google.com>:

Rollback btree_iterator refactoring.

PiperOrigin-RevId: 345543900
GitOrigin-RevId: ff793052bd01e1e4fcf639f94d7c30c4855a9372
Change-Id: I719831981fd056de41939f9addfee3d85e3b49b2

1 files changed, 590 insertions, 0 deletions

diff --git a/absl/container/internal/raw_hash_set_probe_benchmark.cc b/absl/container/internal/raw_hash_set_probe_benchmark.cc
new file mode 100644
index 00000000..7169a2e2
--- /dev/null
+++ b/absl/container/internal/raw_hash_set_probe_benchmark.cc
@@ -0,0 +1,590 @@
+// 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.
+//
+// Generates probe length statistics for many combinations of key types and key
+// distributions, all using the default hash function for swisstable.
+
+#include <memory>
+#include <regex>  // NOLINT
+#include <vector>
+
+#include "absl/container/flat_hash_map.h"
+#include "absl/container/internal/hash_function_defaults.h"
+#include "absl/container/internal/hashtable_debug.h"
+#include "absl/container/internal/raw_hash_set.h"
+#include "absl/random/distributions.h"
+#include "absl/random/random.h"
+#include "absl/strings/str_cat.h"
+#include "absl/strings/str_format.h"
+#include "absl/strings/string_view.h"
+#include "absl/strings/strip.h"
+
+namespace {
+
+enum class OutputStyle { kRegular, kBenchmark };
+
+// The --benchmark command line flag.
+// This is populated from main().
+// When run in "benchmark" mode, we have different output. This allows
+// A/B comparisons with tools like `benchy`.
+absl::string_view benchmarks;
+
+OutputStyle output() {
+  return !benchmarks.empty() ? OutputStyle::kBenchmark : OutputStyle::kRegular;
+}
+
+template <class T>
+struct Policy {
+  using slot_type = T;
+  using key_type = T;
+  using init_type = T;
+
+  template <class allocator_type, class Arg>
+  static void construct(allocator_type* alloc, slot_type* slot,
+                        const Arg& arg) {
+    std::allocator_traits<allocator_type>::construct(*alloc, slot, arg);
+  }
+
+  template <class allocator_type>
+  static void destroy(allocator_type* alloc, slot_type* slot) {
+    std::allocator_traits<allocator_type>::destroy(*alloc, slot);
+  }
+
+  static slot_type& element(slot_type* slot) { return *slot; }
+
+  template <class F, class... Args>
+  static auto apply(F&& f, const slot_type& arg)
+      -> decltype(std::forward<F>(f)(arg, arg)) {
+    return std::forward<F>(f)(arg, arg);
+  }
+};
+
+absl::BitGen& GlobalBitGen() {
+  static auto* value = new absl::BitGen;
+  return *value;
+}
+
+// Keeps a pool of allocations and randomly gives one out.
+// This introduces more randomization to the addresses given to swisstable and
+// should help smooth out this factor from probe length calculation.
+template <class T>
+class RandomizedAllocator {
+ public:
+  using value_type = T;
+
+  RandomizedAllocator() = default;
+  template <typename U>
+  RandomizedAllocator(RandomizedAllocator<U>) {}  // NOLINT
+
+  static T* allocate(size_t n) {
+    auto& pointers = GetPointers(n);
+    // Fill the pool
+    while (pointers.size() < kRandomPool) {
+      pointers.push_back(std::allocator<T>{}.allocate(n));
+    }
+
+    // Choose a random one.
+    size_t i = absl::Uniform<size_t>(GlobalBitGen(), 0, pointers.size());
+    T* result = pointers[i];
+    pointers[i] = pointers.back();
+    pointers.pop_back();
+    return result;
+  }
+
+  static void deallocate(T* p, size_t n) {
+    // Just put it back on the pool. No need to release the memory.
+    GetPointers(n).push_back(p);
+  }
+
+ private:
+  // We keep at least kRandomPool allocations for each size.
+  static constexpr size_t kRandomPool = 20;
+
+  static std::vector<T*>& GetPointers(size_t n) {
+    static auto* m = new absl::flat_hash_map<size_t, std::vector<T*>>();
+    return (*m)[n];
+  }
+};
+
+template <class T>
+struct DefaultHash {
+  using type = absl::container_internal::hash_default_hash<T>;
+};
+
+template <class T>
+using DefaultHashT = typename DefaultHash<T>::type;
+
+template <class T>
+struct Table : absl::container_internal::raw_hash_set<
+                   Policy<T>, DefaultHashT<T>,
+                   absl::container_internal::hash_default_eq<T>,
+                   RandomizedAllocator<T>> {};
+
+struct LoadSizes {
+  size_t min_load;
+  size_t max_load;
+};
+
+LoadSizes GetMinMaxLoadSizes() {
+  static const auto sizes = [] {
+    Table<int> t;
+
+    // First, fill enough to have a good distribution.
+    constexpr size_t kMinSize = 10000;
+    while (t.size() < kMinSize) t.insert(t.size());
+
+    const auto reach_min_load_factor = [&] {
+      const double lf = t.load_factor();
+      while (lf <= t.load_factor()) t.insert(t.size());
+    };
+
+    // Then, insert until we reach min load factor.
+    reach_min_load_factor();
+    const size_t min_load_size = t.size();
+
+    // Keep going until we hit min load factor again, then go back one.
+    t.insert(t.size());
+    reach_min_load_factor();
+
+    return LoadSizes{min_load_size, t.size() - 1};
+  }();
+  return sizes;
+}
+
+struct Ratios {
+  double min_load;
+  double avg_load;
+  double max_load;
+};
+
+// See absl/container/internal/hashtable_debug.h for details on
+// probe length calculation.
+template <class ElemFn>
+Ratios CollectMeanProbeLengths() {
+  const auto min_max_sizes = GetMinMaxLoadSizes();
+
+  ElemFn elem;
+  using Key = decltype(elem());
+  Table<Key> t;
+
+  Ratios result;
+  while (t.size() < min_max_sizes.min_load) t.insert(elem());
+  result.min_load =
+      absl::container_internal::GetHashtableDebugProbeSummary(t).mean;
+
+  while (t.size() < (min_max_sizes.min_load + min_max_sizes.max_load) / 2)
+    t.insert(elem());
+  result.avg_load =
+      absl::container_internal::GetHashtableDebugProbeSummary(t).mean;
+
+  while (t.size() < min_max_sizes.max_load) t.insert(elem());
+  result.max_load =
+      absl::container_internal::GetHashtableDebugProbeSummary(t).mean;
+
+  return result;
+}
+
+template <int Align>
+uintptr_t PointerForAlignment() {
+  alignas(Align) static constexpr uintptr_t kInitPointer = 0;
+  return reinterpret_cast<uintptr_t>(&kInitPointer);
+}
+
+// This incomplete type is used for testing hash of pointers of different
+// alignments.
+// NOTE: We are generating invalid pointer values on the fly with
+// reinterpret_cast. There are not "safely derived" pointers so using them is
+// technically UB. It is unlikely to be a problem, though.
+template <int Align>
+struct Ptr;
+
+template <int Align>
+Ptr<Align>* MakePtr(uintptr_t v) {
+  if (sizeof(v) == 8) {
+    constexpr int kCopyBits = 16;
+    // Ensure high bits are all the same.
+    v = static_cast<uintptr_t>(static_cast<intptr_t>(v << kCopyBits) >>
+                               kCopyBits);
+  }
+  return reinterpret_cast<Ptr<Align>*>(v);
+}
+
+struct IntIdentity {
+  uint64_t i;
+  friend bool operator==(IntIdentity a, IntIdentity b) { return a.i == b.i; }
+  IntIdentity operator++(int) { return IntIdentity{i++}; }
+};
+
+template <int Align>
+struct PtrIdentity {
+  explicit PtrIdentity(uintptr_t val = PointerForAlignment<Align>()) : i(val) {}
+  uintptr_t i;
+  friend bool operator==(PtrIdentity a, PtrIdentity b) { return a.i == b.i; }
+  PtrIdentity operator++(int) {
+    PtrIdentity p(i);
+    i += Align;
+    return p;
+  }
+};
+
+constexpr char kStringFormat[] = "/path/to/file/name-%07d-of-9999999.txt";
+
+template <bool small>
+struct String {
+  std::string value;
+  static std::string Make(uint32_t v) {
+    return {small ? absl::StrCat(v) : absl::StrFormat(kStringFormat, v)};
+  }
+};
+
+template <>
+struct DefaultHash<IntIdentity> {
+  struct type {
+    size_t operator()(IntIdentity t) const { return t.i; }
+  };
+};
+
+template <int Align>
+struct DefaultHash<PtrIdentity<Align>> {
+  struct type {
+    size_t operator()(PtrIdentity<Align> t) const { return t.i; }
+  };
+};
+
+template <class T>
+struct Sequential {
+  T operator()() const { return current++; }
+  mutable T current{};
+};
+
+template <int Align>
+struct Sequential<Ptr<Align>*> {
+  Ptr<Align>* operator()() const {
+    auto* result = MakePtr<Align>(current);
+    current += Align;
+    return result;
+  }
+  mutable uintptr_t current = PointerForAlignment<Align>();
+};
+
+
+template <bool small>
+struct Sequential<String<small>> {
+  std::string operator()() const { return String<small>::Make(current++); }
+  mutable uint32_t current = 0;
+};
+
+template <class T, class U>
+struct Sequential<std::pair<T, U>> {
+  mutable Sequential<T> tseq;
+  mutable Sequential<U> useq;
+
+  using RealT = decltype(tseq());
+  using RealU = decltype(useq());
+
+  mutable std::vector<RealT> ts;
+  mutable std::vector<RealU> us;
+  mutable size_t ti = 0, ui = 0;
+
+  std::pair<RealT, RealU> operator()() const {
+    std::pair<RealT, RealU> value{get_t(), get_u()};
+    if (ti == 0) {
+      ti = ui + 1;
+      ui = 0;
+    } else {
+      --ti;
+      ++ui;
+    }
+    return value;
+  }
+
+  RealT get_t() const {
+    while (ti >= ts.size()) ts.push_back(tseq());
+    return ts[ti];
+  }
+
+  RealU get_u() const {
+    while (ui >= us.size()) us.push_back(useq());
+    return us[ui];
+  }
+};
+
+template <class T, int percent_skip>
+struct AlmostSequential {
+  mutable Sequential<T> current;
+
+  auto operator()() const -> decltype(current()) {
+    while (absl::Uniform(GlobalBitGen(), 0.0, 1.0) <= percent_skip / 100.)
+      current();
+    return current();
+  }
+};
+
+struct Uniform {
+  template <typename T>
+  T operator()(T) const {
+    return absl::Uniform<T>(absl::IntervalClosed, GlobalBitGen(), T{0}, ~T{0});
+  }
+};
+
+struct Gaussian {
+  template <typename T>
+  T operator()(T) const {
+    double d;
+    do {
+      d = absl::Gaussian<double>(GlobalBitGen(), 1e6, 1e4);
+    } while (d <= 0 || d > std::numeric_limits<T>::max() / 2);
+    return static_cast<T>(d);
+  }
+};
+
+struct Zipf {
+  template <typename T>
+  T operator()(T) const {
+    return absl::Zipf<T>(GlobalBitGen(), std::numeric_limits<T>::max(), 1.6);
+  }
+};
+
+template <class T, class Dist>
+struct Random {
+  T operator()() const { return Dist{}(T{}); }
+};
+
+template <class Dist, int Align>
+struct Random<Ptr<Align>*, Dist> {
+  Ptr<Align>* operator()() const {
+    return MakePtr<Align>(Random<uintptr_t, Dist>{}() * Align);
+  }
+};
+
+template <class Dist>
+struct Random<IntIdentity, Dist> {
+  IntIdentity operator()() const {
+    return IntIdentity{Random<uint64_t, Dist>{}()};
+  }
+};
+
+template <class Dist, int Align>
+struct Random<PtrIdentity<Align>, Dist> {
+  PtrIdentity<Align> operator()() const {
+    return PtrIdentity<Align>{Random<uintptr_t, Dist>{}() * Align};
+  }
+};
+
+template <class Dist, bool small>
+struct Random<String<small>, Dist> {
+  std::string operator()() const {
+    return String<small>::Make(Random<uint32_t, Dist>{}());
+  }
+};
+
+template <class T, class U, class Dist>
+struct Random<std::pair<T, U>, Dist> {
+  auto operator()() const
+      -> decltype(std::make_pair(Random<T, Dist>{}(), Random<U, Dist>{}())) {
+    return std::make_pair(Random<T, Dist>{}(), Random<U, Dist>{}());
+  }
+};
+
+template <typename>
+std::string Name();
+
+std::string Name(uint32_t*) { return "u32"; }
+std::string Name(uint64_t*) { return "u64"; }
+std::string Name(IntIdentity*) { return "IntIdentity"; }
+
+template <int Align>
+std::string Name(Ptr<Align>**) {
+  return absl::StrCat("Ptr", Align);
+}
+
+template <int Align>
+std::string Name(PtrIdentity<Align>*) {
+  return absl::StrCat("PtrIdentity", Align);
+}
+
+template <bool small>
+std::string Name(String<small>*) {
+  return small ? "StrS" : "StrL";
+}
+
+template <class T, class U>
+std::string Name(std::pair<T, U>*) {
+  if (output() == OutputStyle::kBenchmark)
+    return absl::StrCat("P_", Name<T>(), "_", Name<U>());
+  return absl::StrCat("P<", Name<T>(), ",", Name<U>(), ">");
+}
+
+template <class T>
+std::string Name(Sequential<T>*) {
+  return "Sequential";
+}
+
+template <class T, int P>
+std::string Name(AlmostSequential<T, P>*) {
+  return absl::StrCat("AlmostSeq_", P);
+}
+
+template <class T>
+std::string Name(Random<T, Uniform>*) {
+  return "UnifRand";
+}
+
+template <class T>
+std::string Name(Random<T, Gaussian>*) {
+  return "GausRand";
+}
+
+template <class T>
+std::string Name(Random<T, Zipf>*) {
+  return "ZipfRand";
+}
+
+template <typename T>
+std::string Name() {
+  return Name(static_cast<T*>(nullptr));
+}
+
+constexpr int kNameWidth = 15;
+constexpr int kDistWidth = 16;
+
+bool CanRunBenchmark(absl::string_view name) {
+  static std::regex* const filter = []() -> std::regex* {
+    return benchmarks.empty() || benchmarks == "all"
+               ? nullptr
+               : new std::regex(std::string(benchmarks));
+  }();
+  return filter == nullptr || std::regex_search(std::string(name), *filter);
+}
+
+struct Result {
+  std::string name;
+  std::string dist_name;
+  Ratios ratios;
+};
+
+template <typename T, typename Dist>
+void RunForTypeAndDistribution(std::vector<Result>& results) {
+  std::string name = absl::StrCat(Name<T>(), "/", Name<Dist>());
+  // We have to check against all three names (min/avg/max) before we run it.
+  // If any of them is enabled, we run it.
+  if (!CanRunBenchmark(absl::StrCat(name, "/min")) &&
+      !CanRunBenchmark(absl::StrCat(name, "/avg")) &&
+      !CanRunBenchmark(absl::StrCat(name, "/max"))) {
+    return;
+  }
+  results.push_back({Name<T>(), Name<Dist>(), CollectMeanProbeLengths<Dist>()});
+}
+
+template <class T>
+void RunForType(std::vector<Result>& results) {
+  RunForTypeAndDistribution<T, Sequential<T>>(results);
+  RunForTypeAndDistribution<T, AlmostSequential<T, 20>>(results);
+  RunForTypeAndDistribution<T, AlmostSequential<T, 50>>(results);
+  RunForTypeAndDistribution<T, Random<T, Uniform>>(results);
+#ifdef NDEBUG
+  // Disable these in non-opt mode because they take too long.
+  RunForTypeAndDistribution<T, Random<T, Gaussian>>(results);
+  RunForTypeAndDistribution<T, Random<T, Zipf>>(results);
+#endif  // NDEBUG
+}
+
+}  // namespace
+
+int main(int argc, char** argv) {
+  // Parse the benchmark flags. Ignore all of them except the regex pattern.
+  for (int i = 1; i < argc; ++i) {
+    absl::string_view arg = argv[i];
+    const auto next = [&] { return argv[std::min(i + 1, argc - 1)]; };
+
+    if (absl::ConsumePrefix(&arg, "--benchmark_filter")) {
+      if (arg == "") {
+        // --benchmark_filter X
+        benchmarks = next();
+      } else if (absl::ConsumePrefix(&arg, "=")) {
+        // --benchmark_filter=X
+        benchmarks = arg;
+      }
+    }
+
+    // Any --benchmark flag turns on the mode.
+    if (absl::ConsumePrefix(&arg, "--benchmark")) {
+      if (benchmarks.empty()) benchmarks="all";
+    }
+  }
+
+  std::vector<Result> results;
+  RunForType<uint64_t>(results);
+  RunForType<IntIdentity>(results);
+  RunForType<Ptr<8>*>(results);
+  RunForType<Ptr<16>*>(results);
+  RunForType<Ptr<32>*>(results);
+  RunForType<Ptr<64>*>(results);
+  RunForType<PtrIdentity<8>>(results);
+  RunForType<PtrIdentity<16>>(results);
+  RunForType<PtrIdentity<32>>(results);
+  RunForType<PtrIdentity<64>>(results);
+  RunForType<std::pair<uint32_t, uint32_t>>(results);
+  RunForType<String<true>>(results);
+  RunForType<String<false>>(results);
+  RunForType<std::pair<uint64_t, String<true>>>(results);
+  RunForType<std::pair<String<true>, uint64_t>>(results);
+  RunForType<std::pair<uint64_t, String<false>>>(results);
+  RunForType<std::pair<String<false>, uint64_t>>(results);
+
+  switch (output()) {
+    case OutputStyle::kRegular:
+      absl::PrintF("%-*s%-*s       Min       Avg       Max\n%s\n", kNameWidth,
+                   "Type", kDistWidth, "Distribution",
+                   std::string(kNameWidth + kDistWidth + 10 * 3, '-'));
+      for (const auto& result : results) {
+        absl::PrintF("%-*s%-*s  %8.4f  %8.4f  %8.4f\n", kNameWidth, result.name,
+                     kDistWidth, result.dist_name, result.ratios.min_load,
+                     result.ratios.avg_load, result.ratios.max_load);
+      }
+      break;
+    case OutputStyle::kBenchmark: {
+      absl::PrintF("{\n");
+      absl::PrintF("  \"benchmarks\": [\n");
+      absl::string_view comma;
+      for (const auto& result : results) {
+        auto print = [&](absl::string_view stat, double Ratios::*val) {
+          std::string name =
+              absl::StrCat(result.name, "/", result.dist_name, "/", stat);
+          // Check the regex again. We might had have enabled only one of the
+          // stats for the benchmark.
+          if (!CanRunBenchmark(name)) return;
+          absl::PrintF("    %s{\n", comma);
+          absl::PrintF("      \"cpu_time\": %f,\n", 1e9 * result.ratios.*val);
+          absl::PrintF("      \"real_time\": %f,\n", 1e9 * result.ratios.*val);
+          absl::PrintF("      \"iterations\": 1,\n");
+          absl::PrintF("      \"name\": \"%s\",\n", name);
+          absl::PrintF("      \"time_unit\": \"ns\"\n");
+          absl::PrintF("    }\n");
+          comma = ",";
+        };
+        print("min", &Ratios::min_load);
+        print("avg", &Ratios::avg_load);
+        print("max", &Ratios::max_load);
+      }
+      absl::PrintF("  ],\n");
+      absl::PrintF("  \"context\": {\n");
+      absl::PrintF("  }\n");
+      absl::PrintF("}\n");
+      break;
+    }
+  }
+
+  return 0;
+}