pub struct InvocationCounter { /* private fields */ }Expand description
A structure for tracking invocation counts over sliding time windows.
InvocationCounter implements a ring buffer-based algorithm that efficiently answers the question:
“How many times has a function been called in the last X time units?” The structure divides time
into fixed-size intervals and uses a circular array of slots to track counts within each interval.
§Time Units
Time units are abstract and can represent any consistent time measurement (milliseconds, seconds, ticks, etc.). The counter treats time as unsigned 64-bit integers, where larger values represent later points in time.
§Count Approximation
The counter provides an approximate count due to its interval-based design:
- Invocations are grouped into discrete time intervals (slots)
- The sliding window moves in interval-sized steps, not continuously
- Recent invocations may be counted even if they fall slightly outside the exact window
- Very old invocations may be excluded if their slots have been reused
This approximation trades perfect accuracy for significant performance and memory efficiency.
§Architecture
The counter uses a ring buffer with 2^slot_count_exp slots, where each slot represents a time
interval of 2^slot_size_exp time units. The total sliding window size is therefore:
2^slot_count_exp × 2^slot_size_exp time units.
Each slot contains:
interval_start: The start timestamp of the time interval this slot representscounter: The number of invocations registered in this interval
As time progresses, slots are reused in a circular fashion. When a new time interval begins that maps to an already-occupied slot, the slot is reset and begins tracking the new interval.
§Example
// Create counter: 8 slots × 16 time units = 128 time unit sliding window
let counter = InvocationCounter::new(3, 4); // 2^3 slots, 2^4 time units per slot
counter.register(10); // Register invocation at time 10
counter.register(25); // Register invocation at time 25
assert_eq!(counter.count_in(0, 26), 2); // both in range [0, 26)
assert_eq!(counter.count_in(0, 16), 1); // only first (slot 0: times 0-15)
assert_eq!(counter.count_in(16, 32), 1); // only second (slot 1: times 16-31)
assert_eq!(counter.count_in(50, 60), 0); // out of range
counter.register(200);
assert_eq!(counter.count_in(200 - 128, 201), 1); // Only the last in 128-unit windowImplementations§
Source§impl InvocationCounter
impl InvocationCounter
Sourcepub fn new(slot_count_exp: u8, slot_size_exp: u8) -> Self
pub fn new(slot_count_exp: u8, slot_size_exp: u8) -> Self
Creates a new InvocationCounter with the specified configuration.
§Arguments
slot_count_exp- Exponent for the number of slots (2^slot_count_exp slots total)slot_size_exp- Exponent for the size of each time interval (2^slot_size_exp time units per slot)
The total sliding window size will be: 2^slot_count_exp × 2^slot_size_exp time units.
§Examples
// Create a counter with 8 slots (2^3), each covering 16 time units (2^4)
// Total window: 8 × 16 = 128 time units
let counter = InvocationCounter::new(3, 4);Sourcepub fn register(&self, current_time: u64)
pub fn register(&self, current_time: u64)
Registers an invocation at the specified time.
This method is thread-safe. Multiple threads can call this method concurrently without external synchronization.
§Arguments
current_time- The timestamp when the invocation occurred
§Examples
let counter = InvocationCounter::new(3, 4); // 8 slots × 16 units = 128-unit window
counter.register(10);
counter.register(10); // Same interval, increments counter
counter.register(25); // Different interval, uses different slotSourcepub fn slot_count_exp(&self) -> u8
pub fn slot_count_exp(&self) -> u8
Returns the slot count exponent used to create this counter.
The actual number of slots is 2^slot_count_exp().
§Examples
let counter = InvocationCounter::new(3, 4); // 8 slots, each covering 16 time units
assert_eq!(counter.slot_count_exp(), 3);
assert_eq!(1 << counter.slot_count_exp(), 8); // 2^3 = 8 slotsSourcepub fn slot_size_exp(&self) -> u8
pub fn slot_size_exp(&self) -> u8
Returns the slot size exponent used to create this counter.
The actual size of each time interval is 2^slot_size_exp() time units.
§Examples
let counter = InvocationCounter::new(3, 4); // 8 slots, each covering 16 time units
assert_eq!(counter.slot_size_exp(), 4);
assert_eq!(1 << counter.slot_size_exp(), 16); // 2^4 = 16 time units per slotSourcepub fn count_in(&self, start_time: u64, end_time: u64) -> u32
pub fn count_in(&self, start_time: u64, end_time: u64) -> u32
Returns the total number of invocations within the specified time range.
Unlike count() which uses a fixed sliding window, this method allows querying
invocations within any arbitrary time range defined by start_time and end_time.
The method still respects the ring buffer’s current valid data range.
§Arguments
start_time- The start time of the range to query (inclusive)end_time- The end time of the range to query (exclusive)
§Returns
The total number of invocations that occurred within the specified time range, limited by the data currently available in the ring buffer.
§Examples
let counter = InvocationCounter::new(3, 4); // 8 slots × 16 units = 128-unit window
counter.register(10);
counter.register(25);
counter.register(100);
assert_eq!(counter.count_in(0, 50), 2); // First two invocations
assert_eq!(counter.count_in(20, 120), 2); // Second and third invocations
assert_eq!(counter.count_in(0, 200), 3); // All invocations (if within ring buffer range)