[−][src]Struct metrics_util::StreamingIntegers
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:
- simply compress the input set, no decompression
- decompress the entire compressed set into a single vector
- same as #2 but sum all of the original values at the end
- use
decompress_with
to sum the numbers incrementally
Methods
impl StreamingIntegers
[src]
pub fn new() -> Self
[src]
Creates a new, empty streaming set.
pub fn len(&self) -> usize
[src]
Returns the number of elements in the set, also referred to as its 'length'.
pub fn is_empty(&self) -> bool
[src]
Returns true
if the set contains no elements.
pub fn compress(&mut self, src: &[u64])
[src]
Compresses a slice of integers, and adds them to the set.
pub fn decompress(&self) -> Vec<u64>
[src]
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]),
[src]
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 Clone for StreamingIntegers
[src]
fn clone(&self) -> StreamingIntegers
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl Default for StreamingIntegers
[src]
fn default() -> StreamingIntegers
[src]
impl Debug for StreamingIntegers
[src]
Auto Trait Implementations
impl Send for StreamingIntegers
impl Sync for StreamingIntegers
Blanket Implementations
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,