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