1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/// Configuration for logarithmic bucket boundaries.
///
/// The `width` parameter determines bucket granularity:
/// - width=3: 4 buckets per group, 252 total buckets, ~12.5% max error
/// - width=4: 8 buckets per group, 504 total buckets, ~6.25% max error
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct LogScaleConfig {
/// The width of the bit pattern used for bucketing (most significant bits).
///
/// Each bucket group uses WIDTH bits: 1 MSB + (WIDTH-1) offset bits.
width: usize,
/// Number of buckets per group: `1 << (width - 1)`.
///
/// Also serves as the MSB bit pattern for bucket groups.
/// For width=3: `1 << 2 = 4` buckets per group.
group_size: usize,
/// Mask for extracting the offset within a bucket group.
///
/// Extracts the (width-1) bits after the MSB: `group_size - 1 = 0b11` for width=3.
mask: u64,
/// The exact number of buckets needed to cover all u64 values with logarithmic precision.
///
/// Calculated as: `group_size * (66 - width)`
/// For width=3: 4 * (66 - 3) = 4 * 63 = 252
buckets: usize,
/// Cache size for small value bucket lookups.
///
/// Values 0-4095 map to bucket indices 0-44, fitting in u8.
small_value_cache_size: usize,
}
impl LogScaleConfig {
/// Creates a config for the given bit-width.
pub fn new(width: usize) -> Self {
let group_size = 1 << (width - 1);
let mask = (group_size - 1) as u64;
let buckets = group_size * (66 - width);
Self {
width,
group_size,
mask,
buckets,
small_value_cache_size: 4096,
}
}
/// Bit-width parameter.
pub fn width(&self) -> usize {
self.width
}
/// Number of buckets per group: `2^(width-1)`.
pub fn group_size(&self) -> usize {
self.group_size
}
/// Bitmask for extracting the offset within a bucket group.
pub fn mask(&self) -> u64 {
self.mask
}
/// Total number of buckets covering the full u64 range.
pub fn buckets(&self) -> usize {
self.buckets
}
/// Number of values eligible for the small-value lookup cache.
pub fn small_value_cache_size(&self) -> usize {
self.small_value_cache_size
}
}