diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-21 11:54:28 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-21 11:54:28 +0000 |
commit | e6918187568dbd01842d8d1d2c808ce16a894239 (patch) | |
tree | 64f88b554b444a49f656b6c656111a145cbbaa28 /src/rocksdb/util/ribbon_config.cc | |
parent | Initial commit. (diff) | |
download | ceph-e6918187568dbd01842d8d1d2c808ce16a894239.tar.xz ceph-e6918187568dbd01842d8d1d2c808ce16a894239.zip |
Adding upstream version 18.2.2.upstream/18.2.2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/rocksdb/util/ribbon_config.cc')
-rw-r--r-- | src/rocksdb/util/ribbon_config.cc | 506 |
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 |