summaryrefslogtreecommitdiffstats
path: root/src/rocksdb/util/ribbon_config.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/rocksdb/util/ribbon_config.cc506
1 files changed, 506 insertions, 0 deletions
diff --git a/src/rocksdb/util/ribbon_config.cc b/src/rocksdb/util/ribbon_config.cc
new file mode 100644
index 000000000..c1046f4aa
--- /dev/null
+++ b/src/rocksdb/util/ribbon_config.cc
@@ -0,0 +1,506 @@
+// Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
+// This source code is licensed under both the GPLv2 (found in the
+// COPYING file in the root directory) and Apache 2.0 License
+// (found in the LICENSE.Apache file in the root directory).
+
+#include "util/ribbon_config.h"
+
+namespace ROCKSDB_NAMESPACE {
+
+namespace ribbon {
+
+namespace detail {
+
+// Each instantiation of this struct is sufficiently unique for configuration
+// purposes, and is only instantiated for settings where we support the
+// configuration API. An application might only reference one instantiation,
+// meaning the rest could be pruned at link time.
+template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash>
+struct BandingConfigHelperData {
+ static constexpr size_t kKnownSize = 18U;
+
+ // Because of complexity in the data, for smaller numbers of slots
+ // (powers of two up to 2^17), we record known numbers that can be added
+ // with kCfc chance of construction failure and settings in template
+ // parameters. Zero means "unsupported (too small) number of slots".
+ // (GetNumToAdd below will use interpolation for numbers of slots
+ // between powers of two; double rather than integer values here make
+ // that more accurate.)
+ static const std::array<double, kKnownSize> kKnownToAddByPow2;
+
+ // For sufficiently large number of slots, doubling the number of
+ // slots will increase the expected overhead (slots over number added)
+ // by approximately this constant.
+ // (This is roughly constant regardless of ConstructionFailureChance and
+ // smash setting.)
+ // (Would be a constant if we had partial template specialization for
+ // static const members.)
+ static inline double GetFactorPerPow2() {
+ if (kCoeffBits == 128U) {
+ return 0.0038;
+ } else {
+ assert(kCoeffBits == 64U);
+ return 0.0083;
+ }
+ }
+
+ // Overhead factor for 2^(kKnownSize-1) slots
+ // (Would be a constant if we had partial template specialization for
+ // static const members.)
+ static inline double GetFinalKnownFactor() {
+ return 1.0 * (uint32_t{1} << (kKnownSize - 1)) /
+ kKnownToAddByPow2[kKnownSize - 1];
+ }
+
+ // GetFinalKnownFactor() - (kKnownSize-1) * GetFactorPerPow2()
+ // (Would be a constant if we had partial template specialization for
+ // static const members.)
+ static inline double GetBaseFactor() {
+ return GetFinalKnownFactor() - (kKnownSize - 1) * GetFactorPerPow2();
+ }
+
+ // Get overhead factor (slots over number to add) for sufficiently large
+ // number of slots (by log base 2)
+ static inline double GetFactorForLarge(double log2_num_slots) {
+ return GetBaseFactor() + log2_num_slots * GetFactorPerPow2();
+ }
+
+ // For a given power of two number of slots (specified by whole number
+ // log base 2), implements GetNumToAdd for such limited case, returning
+ // double for better interpolation in GetNumToAdd and GetNumSlots.
+ static inline double GetNumToAddForPow2(uint32_t log2_num_slots) {
+ assert(log2_num_slots <= 32); // help clang-analyze
+ if (log2_num_slots < kKnownSize) {
+ return kKnownToAddByPow2[log2_num_slots];
+ } else {
+ return 1.0 * (uint64_t{1} << log2_num_slots) /
+ GetFactorForLarge(1.0 * log2_num_slots);
+ }
+ }
+};
+
+// Based on data from FindOccupancy in ribbon_test
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn2, 128U, false>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 252.984,
+ 506.109,
+ 1013.71,
+ 2029.47,
+ 4060.43,
+ 8115.63,
+ 16202.2,
+ 32305.1,
+ 64383.5,
+ 128274,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn2, 128U, /*smash*/ true>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 126.274,
+ 254.279,
+ 510.27,
+ 1022.24,
+ 2046.02,
+ 4091.99,
+ 8154.98,
+ 16244.3,
+ 32349.7,
+ 64426.6,
+ 128307,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn2, 64U, false>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 124.94,
+ 249.968,
+ 501.234,
+ 1004.06,
+ 2006.15,
+ 3997.89,
+ 7946.99,
+ 15778.4,
+ 31306.9,
+ 62115.3,
+ 123284,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn2, 64U, /*smash*/ true>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 62.2683,
+ 126.259,
+ 254.268,
+ 509.975,
+ 1019.98,
+ 2026.16,
+ 4019.75,
+ 7969.8,
+ 15798.2,
+ 31330.3,
+ 62134.2,
+ 123255,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn20, 128U, false>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 248.851,
+ 499.532,
+ 1001.26,
+ 2003.97,
+ 4005.59,
+ 8000.39,
+ 15966.6,
+ 31828.1,
+ 63447.3,
+ 126506,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn20, 128U, /*smash*/ true>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 122.637,
+ 250.651,
+ 506.625,
+ 1018.54,
+ 2036.43,
+ 4041.6,
+ 8039.25,
+ 16005,
+ 31869.6,
+ 63492.8,
+ 126537,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn20, 64U, false>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 120.659,
+ 243.346,
+ 488.168,
+ 976.373,
+ 1948.86,
+ 3875.85,
+ 7704.97,
+ 15312.4,
+ 30395.1,
+ 60321.8,
+ 119813,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn20, 64U, /*smash*/ true>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 58.6016,
+ 122.619,
+ 250.641,
+ 503.595,
+ 994.165,
+ 1967.36,
+ 3898.17,
+ 7727.21,
+ 15331.5,
+ 30405.8,
+ 60376.2,
+ 119836,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn1000, 128U, false>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 242.61,
+ 491.887,
+ 983.603,
+ 1968.21,
+ 3926.98,
+ 7833.99,
+ 15629,
+ 31199.9,
+ 62307.8,
+ 123870,
+ }};
+
+template <>
+const std::array<double, 18> BandingConfigHelperData<
+ kOneIn1000, 128U, /*smash*/ true>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 117.19,
+ 245.105,
+ 500.748,
+ 1010.67,
+ 1993.4,
+ 3950.01,
+ 7863.31,
+ 15652,
+ 31262.1,
+ 62462.8,
+ 124095,
+}};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn1000, 64U, false>::kKnownToAddByPow2{{
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 114,
+ 234.8,
+ 471.498,
+ 940.165,
+ 1874,
+ 3721.5,
+ 7387.5,
+ 14592,
+ 29160,
+ 57745,
+ 115082,
+ }};
+
+template <>
+const std::array<double, 18>
+ BandingConfigHelperData<kOneIn1000, 64U, /*smash*/ true>::kKnownToAddByPow2{
+ {
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0, // unsupported
+ 53.0434,
+ 117,
+ 245.312,
+ 483.571,
+ 950.251,
+ 1878,
+ 3736.34,
+ 7387.97,
+ 14618,
+ 29142.9,
+ 57838.8,
+ 114932,
+ }};
+
+// We hide these implementation details from the .h file with explicit
+// instantiations below these partial specializations.
+
+template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash,
+ bool kHomogeneous>
+uint32_t BandingConfigHelper1MaybeSupported<
+ kCfc, kCoeffBits, kUseSmash, kHomogeneous,
+ true /* kIsSupported */>::GetNumToAdd(uint32_t num_slots) {
+ using Data = detail::BandingConfigHelperData<kCfc, kCoeffBits, kUseSmash>;
+ if (num_slots == 0) {
+ return 0;
+ }
+ uint32_t num_to_add;
+ double log2_num_slots = std::log(num_slots) * 1.4426950409;
+ uint32_t floor_log2 = static_cast<uint32_t>(log2_num_slots);
+ if (floor_log2 + 1 < Data::kKnownSize) {
+ double ceil_portion = 1.0 * num_slots / (uint32_t{1} << floor_log2) - 1.0;
+ // Must be a supported number of slots
+ assert(Data::kKnownToAddByPow2[floor_log2] > 0.0);
+ // Weighted average of two nearest known data points
+ num_to_add = static_cast<uint32_t>(
+ ceil_portion * Data::kKnownToAddByPow2[floor_log2 + 1] +
+ (1.0 - ceil_portion) * Data::kKnownToAddByPow2[floor_log2]);
+ } else {
+ // Use formula for large values
+ double factor = Data::GetFactorForLarge(log2_num_slots);
+ assert(factor >= 1.0);
+ num_to_add = static_cast<uint32_t>(num_slots / factor);
+ }
+ if (kHomogeneous) {
+ // Even when standard filter construction would succeed, we might
+ // have loaded things up too much for Homogeneous filter. (Complete
+ // explanation not known but observed empirically.) This seems to
+ // correct for that, mostly affecting small filter configurations.
+ if (num_to_add >= 8) {
+ num_to_add -= 8;
+ } else {
+ assert(false);
+ }
+ }
+ return num_to_add;
+}
+
+template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash,
+ bool kHomogeneous>
+uint32_t BandingConfigHelper1MaybeSupported<
+ kCfc, kCoeffBits, kUseSmash, kHomogeneous,
+ true /* kIsSupported */>::GetNumSlots(uint32_t num_to_add) {
+ using Data = detail::BandingConfigHelperData<kCfc, kCoeffBits, kUseSmash>;
+
+ if (num_to_add == 0) {
+ return 0;
+ }
+ if (kHomogeneous) {
+ // Reverse of above in GetNumToAdd
+ num_to_add += 8;
+ }
+ double log2_num_to_add = std::log(num_to_add) * 1.4426950409;
+ uint32_t approx_log2_slots = static_cast<uint32_t>(log2_num_to_add + 0.5);
+ assert(approx_log2_slots <= 32); // help clang-analyze
+
+ double lower_num_to_add = Data::GetNumToAddForPow2(approx_log2_slots);
+ double upper_num_to_add;
+ if (approx_log2_slots == 0 || lower_num_to_add == /* unsupported */ 0) {
+ // Return minimum non-zero slots in standard implementation
+ return kUseSmash ? kCoeffBits : 2 * kCoeffBits;
+ } else if (num_to_add < lower_num_to_add) {
+ upper_num_to_add = lower_num_to_add;
+ --approx_log2_slots;
+ lower_num_to_add = Data::GetNumToAddForPow2(approx_log2_slots);
+ } else {
+ upper_num_to_add = Data::GetNumToAddForPow2(approx_log2_slots + 1);
+ }
+
+ assert(num_to_add >= lower_num_to_add);
+ assert(num_to_add < upper_num_to_add);
+
+ double upper_portion =
+ (num_to_add - lower_num_to_add) / (upper_num_to_add - lower_num_to_add);
+
+ double lower_num_slots = 1.0 * (uint64_t{1} << approx_log2_slots);
+
+ // Interpolation, round up
+ return static_cast<uint32_t>(upper_portion * lower_num_slots +
+ lower_num_slots + 0.999999999);
+}
+
+// These explicit instantiations enable us to hide most of the
+// implementation details from the .h file. (The .h file currently
+// needs to determine whether settings are "supported" or not.)
+
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ false,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ true,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ false,
+ /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ true,
+ /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ false,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ true,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ false,
+ /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ true,
+ /*hm*/ true, /*sup*/ true>;
+
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ false,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ true,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ false,
+ /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ true,
+ /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ false,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ true,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ false,
+ /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ true,
+ /*hm*/ true, /*sup*/ true>;
+
+template struct BandingConfigHelper1MaybeSupported<
+ kOneIn1000, 128U, /*sm*/ false, /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<
+ kOneIn1000, 128U, /*sm*/ true, /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<
+ kOneIn1000, 128U, /*sm*/ false, /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<
+ kOneIn1000, 128U, /*sm*/ true, /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<
+ kOneIn1000, 64U, /*sm*/ false, /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn1000, 64U, /*sm*/ true,
+ /*hm*/ false, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<
+ kOneIn1000, 64U, /*sm*/ false, /*hm*/ true, /*sup*/ true>;
+template struct BandingConfigHelper1MaybeSupported<kOneIn1000, 64U, /*sm*/ true,
+ /*hm*/ true, /*sup*/ true>;
+
+} // namespace detail
+
+} // namespace ribbon
+
+} // namespace ROCKSDB_NAMESPACE
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-16 13:51:36 +0000