1 // Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved. 2 // This source code is licensed under both the GPLv2 (found in the 3 // COPYING file in the root directory) and Apache 2.0 License 4 // (found in the LICENSE.Apache file in the root directory). 5 6 #include "util/ribbon_config.h" 7 8 namespace ROCKSDB_NAMESPACE { 9 10 namespace ribbon { 11 12 namespace detail { 13 14 // Each instantiation of this struct is sufficiently unique for configuration 15 // purposes, and is only instantiated for settings where we support the 16 // configuration API. An application might only reference one instantiation, 17 // meaning the rest could be pruned at link time. 18 template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash> 19 struct BandingConfigHelperData { 20 static constexpr size_t kKnownSize = 18U; 21 22 // Because of complexity in the data, for smaller numbers of slots 23 // (powers of two up to 2^17), we record known numbers that can be added 24 // with kCfc chance of construction failure and settings in template 25 // parameters. Zero means "unsupported (too small) number of slots". 26 // (GetNumToAdd below will use interpolation for numbers of slots 27 // between powers of two; double rather than integer values here make 28 // that more accurate.) 29 static const std::array<double, kKnownSize> kKnownToAddByPow2; 30 31 // For sufficiently large number of slots, doubling the number of 32 // slots will increase the expected overhead (slots over number added) 33 // by approximately this constant. 34 // (This is roughly constant regardless of ConstructionFailureChance and 35 // smash setting.) 36 // (Would be a constant if we had partial template specialization for 37 // static const members.) GetFactorPerPow2ROCKSDB_NAMESPACE::ribbon::detail::BandingConfigHelperData38 static inline double GetFactorPerPow2() { 39 if (kCoeffBits == 128U) { 40 return 0.0038; 41 } else { 42 assert(kCoeffBits == 64U); 43 return 0.0083; 44 } 45 } 46 47 // Overhead factor for 2^(kKnownSize-1) slots 48 // (Would be a constant if we had partial template specialization for 49 // static const members.) GetFinalKnownFactorROCKSDB_NAMESPACE::ribbon::detail::BandingConfigHelperData50 static inline double GetFinalKnownFactor() { 51 return 1.0 * (uint32_t{1} << (kKnownSize - 1)) / 52 kKnownToAddByPow2[kKnownSize - 1]; 53 } 54 55 // GetFinalKnownFactor() - (kKnownSize-1) * GetFactorPerPow2() 56 // (Would be a constant if we had partial template specialization for 57 // static const members.) GetBaseFactorROCKSDB_NAMESPACE::ribbon::detail::BandingConfigHelperData58 static inline double GetBaseFactor() { 59 return GetFinalKnownFactor() - (kKnownSize - 1) * GetFactorPerPow2(); 60 } 61 62 // Get overhead factor (slots over number to add) for sufficiently large 63 // number of slots (by log base 2) GetFactorForLargeROCKSDB_NAMESPACE::ribbon::detail::BandingConfigHelperData64 static inline double GetFactorForLarge(double log2_num_slots) { 65 return GetBaseFactor() + log2_num_slots * GetFactorPerPow2(); 66 } 67 68 // For a given power of two number of slots (specified by whole number 69 // log base 2), implements GetNumToAdd for such limited case, returning 70 // double for better interpolation in GetNumToAdd and GetNumSlots. GetNumToAddForPow2ROCKSDB_NAMESPACE::ribbon::detail::BandingConfigHelperData71 static inline double GetNumToAddForPow2(uint32_t log2_num_slots) { 72 assert(log2_num_slots <= 32); // help clang-analyze 73 if (log2_num_slots < kKnownSize) { 74 return kKnownToAddByPow2[log2_num_slots]; 75 } else { 76 return 1.0 * (uint64_t{1} << log2_num_slots) / 77 GetFactorForLarge(1.0 * log2_num_slots); 78 } 79 } 80 }; 81 82 // Based on data from FindOccupancy in ribbon_test 83 template <> 84 const std::array<double, 18> 85 BandingConfigHelperData<kOneIn2, 128U, false>::kKnownToAddByPow2{{ 86 0, 87 0, 88 0, 89 0, 90 0, 91 0, 92 0, 93 0, // unsupported 94 252.984, 95 506.109, 96 1013.71, 97 2029.47, 98 4060.43, 99 8115.63, 100 16202.2, 101 32305.1, 102 64383.5, 103 128274, 104 }}; 105 106 template <> 107 const std::array<double, 18> 108 BandingConfigHelperData<kOneIn2, 128U, /*smash*/ true>::kKnownToAddByPow2{{ 109 0, 110 0, 111 0, 112 0, 113 0, 114 0, 115 0, // unsupported 116 126.274, 117 254.279, 118 510.27, 119 1022.24, 120 2046.02, 121 4091.99, 122 8154.98, 123 16244.3, 124 32349.7, 125 64426.6, 126 128307, 127 }}; 128 129 template <> 130 const std::array<double, 18> 131 BandingConfigHelperData<kOneIn2, 64U, false>::kKnownToAddByPow2{{ 132 0, 133 0, 134 0, 135 0, 136 0, 137 0, 138 0, // unsupported 139 124.94, 140 249.968, 141 501.234, 142 1004.06, 143 2006.15, 144 3997.89, 145 7946.99, 146 15778.4, 147 31306.9, 148 62115.3, 149 123284, 150 }}; 151 152 template <> 153 const std::array<double, 18> 154 BandingConfigHelperData<kOneIn2, 64U, /*smash*/ true>::kKnownToAddByPow2{{ 155 0, 156 0, 157 0, 158 0, 159 0, 160 0, // unsupported 161 62.2683, 162 126.259, 163 254.268, 164 509.975, 165 1019.98, 166 2026.16, 167 4019.75, 168 7969.8, 169 15798.2, 170 31330.3, 171 62134.2, 172 123255, 173 }}; 174 175 template <> 176 const std::array<double, 18> 177 BandingConfigHelperData<kOneIn20, 128U, false>::kKnownToAddByPow2{{ 178 0, 179 0, 180 0, 181 0, 182 0, 183 0, 184 0, 185 0, // unsupported 186 248.851, 187 499.532, 188 1001.26, 189 2003.97, 190 4005.59, 191 8000.39, 192 15966.6, 193 31828.1, 194 63447.3, 195 126506, 196 }}; 197 198 template <> 199 const std::array<double, 18> 200 BandingConfigHelperData<kOneIn20, 128U, /*smash*/ true>::kKnownToAddByPow2{{ 201 0, 202 0, 203 0, 204 0, 205 0, 206 0, 207 0, // unsupported 208 122.637, 209 250.651, 210 506.625, 211 1018.54, 212 2036.43, 213 4041.6, 214 8039.25, 215 16005, 216 31869.6, 217 63492.8, 218 126537, 219 }}; 220 221 template <> 222 const std::array<double, 18> 223 BandingConfigHelperData<kOneIn20, 64U, false>::kKnownToAddByPow2{{ 224 0, 225 0, 226 0, 227 0, 228 0, 229 0, 230 0, // unsupported 231 120.659, 232 243.346, 233 488.168, 234 976.373, 235 1948.86, 236 3875.85, 237 7704.97, 238 15312.4, 239 30395.1, 240 60321.8, 241 119813, 242 }}; 243 244 template <> 245 const std::array<double, 18> 246 BandingConfigHelperData<kOneIn20, 64U, /*smash*/ true>::kKnownToAddByPow2{{ 247 0, 248 0, 249 0, 250 0, 251 0, 252 0, // unsupported 253 58.6016, 254 122.619, 255 250.641, 256 503.595, 257 994.165, 258 1967.36, 259 3898.17, 260 7727.21, 261 15331.5, 262 30405.8, 263 60376.2, 264 119836, 265 }}; 266 267 template <> 268 const std::array<double, 18> 269 BandingConfigHelperData<kOneIn1000, 128U, false>::kKnownToAddByPow2{{ 270 0, 271 0, 272 0, 273 0, 274 0, 275 0, 276 0, 277 0, // unsupported 278 242.61, 279 491.887, 280 983.603, 281 1968.21, 282 3926.98, 283 7833.99, 284 15629, 285 31199.9, 286 62307.8, 287 123870, 288 }}; 289 290 template <> 291 const std::array<double, 18> BandingConfigHelperData< 292 kOneIn1000, 128U, /*smash*/ true>::kKnownToAddByPow2{{ 293 0, 294 0, 295 0, 296 0, 297 0, 298 0, 299 0, // unsupported 300 117.19, 301 245.105, 302 500.748, 303 1010.67, 304 1993.4, 305 3950.01, 306 7863.31, 307 15652, 308 31262.1, 309 62462.8, 310 124095, 311 }}; 312 313 template <> 314 const std::array<double, 18> 315 BandingConfigHelperData<kOneIn1000, 64U, false>::kKnownToAddByPow2{{ 316 0, 317 0, 318 0, 319 0, 320 0, 321 0, 322 0, // unsupported 323 114, 324 234.8, 325 471.498, 326 940.165, 327 1874, 328 3721.5, 329 7387.5, 330 14592, 331 29160, 332 57745, 333 115082, 334 }}; 335 336 template <> 337 const std::array<double, 18> 338 BandingConfigHelperData<kOneIn1000, 64U, /*smash*/ true>::kKnownToAddByPow2{ 339 { 340 0, 341 0, 342 0, 343 0, 344 0, 345 0, // unsupported 346 53.0434, 347 117, 348 245.312, 349 483.571, 350 950.251, 351 1878, 352 3736.34, 353 7387.97, 354 14618, 355 29142.9, 356 57838.8, 357 114932, 358 }}; 359 360 // We hide these implementation details from the .h file with explicit 361 // instantiations below these partial specializations. 362 363 template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash, 364 bool kHomogeneous> 365 uint32_t BandingConfigHelper1MaybeSupported< 366 kCfc, kCoeffBits, kUseSmash, kHomogeneous, GetNumToAdd(uint32_t num_slots)367 true /* kIsSupported */>::GetNumToAdd(uint32_t num_slots) { 368 using Data = detail::BandingConfigHelperData<kCfc, kCoeffBits, kUseSmash>; 369 if (num_slots == 0) { 370 return 0; 371 } 372 uint32_t num_to_add; 373 double log2_num_slots = std::log(num_slots) * 1.4426950409; 374 uint32_t floor_log2 = static_cast<uint32_t>(log2_num_slots); 375 if (floor_log2 + 1 < Data::kKnownSize) { 376 double ceil_portion = 1.0 * num_slots / (uint32_t{1} << floor_log2) - 1.0; 377 // Must be a supported number of slots 378 assert(Data::kKnownToAddByPow2[floor_log2] > 0.0); 379 // Weighted average of two nearest known data points 380 num_to_add = static_cast<uint32_t>( 381 ceil_portion * Data::kKnownToAddByPow2[floor_log2 + 1] + 382 (1.0 - ceil_portion) * Data::kKnownToAddByPow2[floor_log2]); 383 } else { 384 // Use formula for large values 385 double factor = Data::GetFactorForLarge(log2_num_slots); 386 assert(factor >= 1.0); 387 num_to_add = static_cast<uint32_t>(num_slots / factor); 388 } 389 if (kHomogeneous) { 390 // Even when standard filter construction would succeed, we might 391 // have loaded things up too much for Homogeneous filter. (Complete 392 // explanation not known but observed empirically.) This seems to 393 // correct for that, mostly affecting small filter configurations. 394 if (num_to_add >= 8) { 395 num_to_add -= 8; 396 } else { 397 assert(false); 398 } 399 } 400 return num_to_add; 401 } 402 403 template <ConstructionFailureChance kCfc, uint64_t kCoeffBits, bool kUseSmash, 404 bool kHomogeneous> 405 uint32_t BandingConfigHelper1MaybeSupported< 406 kCfc, kCoeffBits, kUseSmash, kHomogeneous, GetNumSlots(uint32_t num_to_add)407 true /* kIsSupported */>::GetNumSlots(uint32_t num_to_add) { 408 using Data = detail::BandingConfigHelperData<kCfc, kCoeffBits, kUseSmash>; 409 410 if (num_to_add == 0) { 411 return 0; 412 } 413 if (kHomogeneous) { 414 // Reverse of above in GetNumToAdd 415 num_to_add += 8; 416 } 417 double log2_num_to_add = std::log(num_to_add) * 1.4426950409; 418 uint32_t approx_log2_slots = static_cast<uint32_t>(log2_num_to_add + 0.5); 419 assert(approx_log2_slots <= 32); // help clang-analyze 420 421 double lower_num_to_add = Data::GetNumToAddForPow2(approx_log2_slots); 422 double upper_num_to_add; 423 if (approx_log2_slots == 0 || lower_num_to_add == /* unsupported */ 0) { 424 // Return minimum non-zero slots in standard implementation 425 return kUseSmash ? kCoeffBits : 2 * kCoeffBits; 426 } else if (num_to_add < lower_num_to_add) { 427 upper_num_to_add = lower_num_to_add; 428 --approx_log2_slots; 429 lower_num_to_add = Data::GetNumToAddForPow2(approx_log2_slots); 430 } else { 431 upper_num_to_add = Data::GetNumToAddForPow2(approx_log2_slots + 1); 432 } 433 434 assert(num_to_add >= lower_num_to_add); 435 assert(num_to_add < upper_num_to_add); 436 437 double upper_portion = 438 (num_to_add - lower_num_to_add) / (upper_num_to_add - lower_num_to_add); 439 440 double lower_num_slots = 1.0 * (uint64_t{1} << approx_log2_slots); 441 442 // Interpolation, round up 443 return static_cast<uint32_t>(upper_portion * lower_num_slots + 444 lower_num_slots + 0.999999999); 445 } 446 447 // These explicit instantiations enable us to hide most of the 448 // implementation details from the .h file. (The .h file currently 449 // needs to determine whether settings are "supported" or not.) 450 451 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ false, 452 /*hm*/ false, /*sup*/ true>; 453 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ true, 454 /*hm*/ false, /*sup*/ true>; 455 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ false, 456 /*hm*/ true, /*sup*/ true>; 457 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 128U, /*sm*/ true, 458 /*hm*/ true, /*sup*/ true>; 459 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ false, 460 /*hm*/ false, /*sup*/ true>; 461 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ true, 462 /*hm*/ false, /*sup*/ true>; 463 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ false, 464 /*hm*/ true, /*sup*/ true>; 465 template struct BandingConfigHelper1MaybeSupported<kOneIn2, 64U, /*sm*/ true, 466 /*hm*/ true, /*sup*/ true>; 467 468 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ false, 469 /*hm*/ false, /*sup*/ true>; 470 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ true, 471 /*hm*/ false, /*sup*/ true>; 472 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ false, 473 /*hm*/ true, /*sup*/ true>; 474 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 128U, /*sm*/ true, 475 /*hm*/ true, /*sup*/ true>; 476 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ false, 477 /*hm*/ false, /*sup*/ true>; 478 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ true, 479 /*hm*/ false, /*sup*/ true>; 480 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ false, 481 /*hm*/ true, /*sup*/ true>; 482 template struct BandingConfigHelper1MaybeSupported<kOneIn20, 64U, /*sm*/ true, 483 /*hm*/ true, /*sup*/ true>; 484 485 template struct BandingConfigHelper1MaybeSupported< 486 kOneIn1000, 128U, /*sm*/ false, /*hm*/ false, /*sup*/ true>; 487 template struct BandingConfigHelper1MaybeSupported< 488 kOneIn1000, 128U, /*sm*/ true, /*hm*/ false, /*sup*/ true>; 489 template struct BandingConfigHelper1MaybeSupported< 490 kOneIn1000, 128U, /*sm*/ false, /*hm*/ true, /*sup*/ true>; 491 template struct BandingConfigHelper1MaybeSupported< 492 kOneIn1000, 128U, /*sm*/ true, /*hm*/ true, /*sup*/ true>; 493 template struct BandingConfigHelper1MaybeSupported< 494 kOneIn1000, 64U, /*sm*/ false, /*hm*/ false, /*sup*/ true>; 495 template struct BandingConfigHelper1MaybeSupported<kOneIn1000, 64U, /*sm*/ true, 496 /*hm*/ false, /*sup*/ true>; 497 template struct BandingConfigHelper1MaybeSupported< 498 kOneIn1000, 64U, /*sm*/ false, /*hm*/ true, /*sup*/ true>; 499 template struct BandingConfigHelper1MaybeSupported<kOneIn1000, 64U, /*sm*/ true, 500 /*hm*/ true, /*sup*/ true>; 501 502 } // namespace detail 503 504 } // namespace ribbon 505 506 } // namespace ROCKSDB_NAMESPACE 507