// 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 #include // NOLINT #include #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 struct Policy { using slot_type = T; using key_type = T; using init_type = T; template static void construct(allocator_type* alloc, slot_type* slot, const Arg& arg) { std::allocator_traits::construct(*alloc, slot, arg); } template static void destroy(allocator_type* alloc, slot_type* slot) { std::allocator_traits::destroy(*alloc, slot); } static slot_type& element(slot_type* slot) { return *slot; } template static auto apply(F&& f, const slot_type& arg) -> decltype(std::forward(f)(arg, arg)) { return std::forward(f)(arg, arg); } }; absl::BitGen& GlobalBitGen() { static absl::NoDestructor 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 RandomizedAllocator { public: using value_type = T; RandomizedAllocator() = default; template RandomizedAllocator(RandomizedAllocator) {} // NOLINT static T* allocate(size_t n) { auto& pointers = GetPointers(n); // Fill the pool while (pointers.size() < kRandomPool) { pointers.push_back(std::allocator{}.allocate(n)); } // Choose a random one. size_t i = absl::Uniform(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& GetPointers(size_t n) { static absl::NoDestructor>> m; return (*m)[n]; } }; template struct DefaultHash { using type = absl::container_internal::hash_default_hash; }; template using DefaultHashT = typename DefaultHash::type; template struct Table : absl::container_internal::raw_hash_set< Policy, DefaultHashT, absl::container_internal::hash_default_eq, RandomizedAllocator> {}; struct LoadSizes { size_t min_load; size_t max_load; }; LoadSizes GetMinMaxLoadSizes() { static const auto sizes = [] { Table 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 Ratios CollectMeanProbeLengths() { const auto min_max_sizes = GetMinMaxLoadSizes(); ElemFn elem; using Key = decltype(elem()); Table 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 uintptr_t PointerForAlignment() { alignas(Align) static constexpr uintptr_t kInitPointer = 0; return reinterpret_cast(&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 struct Ptr; template Ptr* MakePtr(uintptr_t v) { if (sizeof(v) == 8) { constexpr int kCopyBits = 16; // Ensure high bits are all the same. v = static_cast(static_cast(v << kCopyBits) >> kCopyBits); } return reinterpret_cast*>(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 struct PtrIdentity { explicit PtrIdentity(uintptr_t val = PointerForAlignment()) : 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 struct String { std::string value; static std::string Make(uint32_t v) { return {small ? absl::StrCat(v) : absl::StrFormat(kStringFormat, v)}; } }; template <> struct DefaultHash { struct type { size_t operator()(IntIdentity t) const { return t.i; } }; }; template struct DefaultHash> { struct type { size_t operator()(PtrIdentity t) const { return t.i; } }; }; template struct Sequential { T operator()() const { return current++; } mutable T current{}; }; template struct Sequential*> { Ptr* operator()() const { auto* result = MakePtr(current); current += Align; return result; } mutable uintptr_t current = PointerForAlignment(); }; template struct Sequential> { std::string operator()() const { return String::Make(current++); } mutable uint32_t current = 0; }; template struct Sequential> { mutable Sequential tseq; mutable Sequential useq; using RealT = decltype(tseq()); using RealU = decltype(useq()); mutable std::vector ts; mutable std::vector us; mutable size_t ti = 0, ui = 0; std::pair operator()() const { std::pair 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 struct AlmostSequential { mutable Sequential current; auto operator()() const -> decltype(current()) { while (absl::Uniform(GlobalBitGen(), 0.0, 1.0) <= percent_skip / 100.) current(); return current(); } }; struct Uniform { template T operator()(T) const { return absl::Uniform(absl::IntervalClosed, GlobalBitGen(), T{0}, ~T{0}); } }; struct Gaussian { template T operator()(T) const { double d; do { d = absl::Gaussian(GlobalBitGen(), 1e6, 1e4); } while (d <= 0 || d > std::numeric_limits::max() / 2); return static_cast(d); } }; struct Zipf { template T operator()(T) const { return absl::Zipf(GlobalBitGen(), std::numeric_limits::max(), 1.6); } }; template struct Random { T operator()() const { return Dist{}(T{}); } }; template struct Random*, Dist> { Ptr* operator()() const { return MakePtr(Random{}() * Align); } }; template struct Random { IntIdentity operator()() const { return IntIdentity{Random{}()}; } }; template struct Random, Dist> { PtrIdentity operator()() const { return PtrIdentity{Random{}() * Align}; } }; template struct Random, Dist> { std::string operator()() const { return String::Make(Random{}()); } }; template struct Random, Dist> { auto operator()() const -> decltype(std::make_pair(Random{}(), Random{}())) { return std::make_pair(Random{}(), Random{}()); } }; template std::string Name(); std::string Name(uint32_t*) { return "u32"; } std::string Name(uint64_t*) { return "u64"; } std::string Name(IntIdentity*) { return "IntIdentity"; } template std::string Name(Ptr**) { return absl::StrCat("Ptr", Align); } template std::string Name(PtrIdentity*) { return absl::StrCat("PtrIdentity", Align); } template std::string Name(String*) { return small ? "StrS" : "StrL"; } template std::string Name(std::pair*) { if (output() == OutputStyle::kBenchmark) return absl::StrCat("P_", Name(), "_", Name()); return absl::StrCat("P<", Name(), ",", Name(), ">"); } template std::string Name(Sequential*) { return "Sequential"; } template std::string Name(AlmostSequential*) { return absl::StrCat("AlmostSeq_", P); } template std::string Name(Random*) { return "UnifRand"; } template std::string Name(Random*) { return "GausRand"; } template std::string Name(Random*) { return "ZipfRand"; } template std::string Name() { return Name(static_cast(nullptr)); } constexpr int kNameWidth = 15; constexpr int kDistWidth = 16; bool CanRunBenchmark(absl::string_view name) { static const absl::NoDestructor> 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 void RunForTypeAndDistribution(std::vector& results) { std::string name = absl::StrCat(Name(), "/", Name()); // 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(), Name(), CollectMeanProbeLengths()}); } template void RunForType(std::vector& results) { RunForTypeAndDistribution>(results); RunForTypeAndDistribution>(results); RunForTypeAndDistribution>(results); RunForTypeAndDistribution>(results); #ifdef NDEBUG // Disable these in non-opt mode because they take too long. RunForTypeAndDistribution>(results); RunForTypeAndDistribution>(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 results; RunForType(results); RunForType(results); RunForType*>(results); RunForType*>(results); RunForType*>(results); RunForType*>(results); RunForType>(results); RunForType>(results); RunForType>(results); RunForType>(results); RunForType>(results); RunForType>(results); RunForType>(results); RunForType>>(results); RunForType, uint64_t>>(results); RunForType>>(results); RunForType, 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; }