Struct metrics_util::StreamingIntegers

pub struct StreamingIntegers { /* fields omitted */ }

A compressed set of integers.

For some workloads, working with a large set of integers can require an outsized amount of memory for numbers that are very similar. This data structure takes chunks of integers and compresses then by using delta encoding and variable-byte encoding.

Delta encoding tracks the difference between successive integers: if you have 1000000 and 1000001, the difference between the two is only 1. Coupled with variable-byte encoding, we can compress those two numbers within 4 bytes, where normally they would require a minimum of 8 bytes if they were 32-bit integers, or 16 bytes if they were 64-bit integers. Over large runs of integers where the delta is relatively small compared to the original value, the compression savings add up quickly.

The original integers can be decompressed and collected, or can be decompressed on-the-fly while passing them to a given function, allowing callers to observe the integers without allocating the entire size of the decompressed set.

Performance

As this is a scalar implementation, performance depends heavily on not only the input size, but also the delta between values, as well as whether or not the decompressed values are being collected or used on-the-fly.

Bigger deltas between values means longer variable-byte sizes which is hard for the CPU to predict. As the linear benchemarks show, things are much faster when the delta between values is minimal.

These figures were generated on a 2015 Macbook Pro (Core i7, 2.2GHz base/3.7GHz turbo).

	compress (1)	decompress (2)	decompress/sum (3)	decompress_with/sum (4)
normal, 100 values	94 Melem/s	76 Melem/s	71 Melem/s	126 Melem/s
normal, 10000 values	92 Melem/s	85 Melem/s	109 Melem/s	109 Melem/s
normal, 1000000 values	86 Melem/s	79 Melem/s	68 Melem/s	110 Melem/s
linear, 100 values	334 Melem/s	109 Melem/s	110 Melem/s	297 Melem/s
linear, 10000 values	654 Melem/s	174 Melem/s	374 Melem/s	390 Melem/s
linear, 1000000 values	703 Melem/s	180 Melem/s	132 Melem/s	392 Melem/s

The normal values consistent of an approximation of real nanosecond-based timing measurements of a web service. The linear values are simply sequential integers ranging from 0 to the configured size of the test run.

Operations:

1. simply compress the input set, no decompression
2. decompress the entire compressed set into a single vector
3. same as #2 but sum all of the original values at the end
4. use decompress_with to sum the numbers incrementally

Methods

impl StreamingIntegers

pub fn new() -> Self

Creates a new, empty streaming set.

pub fn len(&self) -> usize

Returns the number of elements in the set, also referred to as its 'length'.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

pub fn compress(&mut self, src: &[u64])

Compresses a slice of integers, and adds them to the set.

pub fn decompress(&self) -> Vec<u64>

Decompresses all of the integers written to the set.

Returns a vector with all of the original values. For larger sets of integers, this can be slow due to the allocation required. Consider decompress_with to incrementally iterate the decompresset set in smaller chunks.

pub fn decompress_with<F>(&self, f: F) where
    F: FnMut(&[u64]), 

Decompresses all of the integers written to the set, invoking f for each batch.

During decompression, values are batched internally until a limit is reached, and then f is called with a reference to the batch. This leads to minimal allocation to decompress the entire set, for use cases where the values can be observed incrementally without issue.

Trait Implementations

impl Default for StreamingIntegers

fn default() -> StreamingIntegers

Returns the "default value" for a type.

impl Clone for StreamingIntegers

fn clone(&self) -> StreamingIntegers

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for StreamingIntegers

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.