tor-browser

raw_hash_set_probe_benchmark.cc (17008B)

---

// 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/base/no_destructor.h"
#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"
#include "absl/types/optional.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);
 }

 template <class Hash>
 static constexpr auto get_hash_slot_fn() {
   return nullptr;
 }
};

absl::BitGen& GlobalBitGen() {
 static absl::NoDestructor<absl::BitGen> value;
 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 absl::NoDestructor<absl::flat_hash_map<size_t, std::vector<T*>>> m;
   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 const absl::NoDestructor<absl::optional<std::regex>> filter([] {
   return benchmarks.empty() || benchmarks == "all"
              ? absl::nullopt
              : absl::make_optional(std::regex(std::string(benchmarks)));
 }());
 return !filter->has_value() || 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;
}