Struct hdrsample::Histogram
[−]
[src]
pub struct Histogram<T: Num + ToPrimitive + Copy> { // some fields omitted }
Histogram
is the core data structure in HdrSample. It records values, and performs analytics.
At its heart, it keeps the count for recorded samples in "buckets" of values. The resolution and distribution of these buckets is tuned based on the desired highest trackable value, as well as the user-specified number of significant decimal digits to preserve. The values for the buckets are kept in a way that resembles floats and doubles: there is a mantissa and an exponent, and each bucket represents a different exponent. The "sub-buckets" within a bucket represent different values for the mantissa.
To a first approximation, the sub-buckets of the first
bucket would hold the values 0
, 1
, 2
, 3
, …, the sub-buckets of the second bucket would
hold 0
, 2
, 4
, 6
, …, the third would hold 0
, 4
, 8
, and so on. However, the low
half of each bucket (except bucket 0) is unnecessary, since those values are already covered by
the sub-buckets of all the preceeding buckets. Thus, Histogram
keeps the top half of every
such bucket.
For the purposes of explanation, consider a Histogram
with 2048 sub-buckets for every bucket,
and a lowest discernible value of 1:
The 0th bucket covers 0...2047 in multiples of 1, using all 2048 sub-buckets The 1st bucket covers 2048..4097 in multiples of 2, using only the top 1024 sub-buckets The 2nd bucket covers 4096..8191 in multiple of 4, using only the top 1024 sub-buckets ...
Bucket 0 is "special" here. It is the only one that has 2048 entries. All the rest have
1024 entries (because their bottom half overlaps with and is already covered by the all of
the previous buckets put together). In other words, the k
'th bucket could represent 0 * 2^k
to 2048 * 2^k
in 2048 buckets with 2^k
precision, but the midpoint of 1024 * 2^k = 2048 * 2^(k-1)
, which is the k-1'th bucket's end. So, we would use the previous bucket
for those lower values as it has better precision.
Methods
impl<T: Num + ToPrimitive + Copy> Histogram<T>
[src]
fn len(&self) -> usize
Get the current number of distinct counted values in the histogram.
fn low(&self) -> i64
Get the lowest discernible value for the histogram in its current configuration.
fn high(&self) -> i64
Get the highest trackable value for the histogram in its current configuration.
fn sigfig(&self) -> u32
Get the number of significant value digits kept by this histogram.
fn count(&self) -> i64
Get the total number of samples recorded.
fn last(&self) -> usize
Get the index of the last histogram bin.
fn buckets(&self) -> usize
Get the number of buckets used by the histogram to cover the highest trackable value.
This method differs from .len()
in that it does not count the sub buckets within each
bucket.
This method is probably only useful for testing purposes.
fn clone_correct(&self, interval: i64) -> Histogram<T>
Get a copy of this histogram, corrected for coordinated omission.
To compensate for the loss of sampled values when a recorded value is larger than the
expected interval between value samples, the new histogram will include an auto-generated
additional series of decreasingly-smaller (down to the interval
) value records for each
count found in the current histogram that is larger than the interval
.
Note: This is a post-correction method, as opposed to the at-recording correction method
provided by record_correct
. The two methods are mutually exclusive, and only one of the
two should be be used on a given data set to correct for the same coordinated omission
issue.
See notes in the description of the Histogram calls for an illustration of why this corrective behavior is important.
If interval
is larger than 0, add auto-generated value records as appropriate if value is
larger than interval
.
fn set_to<B: Borrow<Histogram<T>>>(&mut self, source: B) -> Result<(), &'static str>
Overwrite this histogram with the given histogram. All data and statistics in this histogram will be overwritten.
fn set_to_corrected<B: Borrow<Histogram<T>>>(&mut self, source: B, interval: i64) -> Result<(), ()>
Overwrite this histogram with the given histogram while correcting for coordinated
omission. All data and statistics in this histogram will be overwritten. See
clone_correct
for more detailed explanation about how correction is applied
fn add<B: Borrow<Histogram<T>>>(&mut self, source: B) -> Result<(), &'static str>
Add the contents of another histogram to this one.
May fail if values in the other histogram are higher than .high()
, and auto-resize is
disabled.
fn add_correct<B: Borrow<Histogram<T>>>(&mut self, source: B, interval: i64) -> Result<(), ()>
Add the contents of another histogram to this one, while correcting for coordinated omission.
To compensate for the loss of sampled values when a recorded value is larger than the
expected interval between value samples, the values added will include an auto-generated
additional series of decreasingly-smaller (down to the given interval
) value records for
each count found in the current histogram that is larger than interval
.
Note: This is a post-recording correction method, as opposed to the at-recording correction
method provided by record_correct
. The two methods are mutually exclusive, and only one
of the two should be be used on a given data set to correct for the same coordinated
omission issue.
See notes in the description of the Histogram
calls for an illustration of why this
corrective behavior is important.
May fail if values in the other histogram are higher than .high()
, and auto-resize is
disabled.
fn subtract<B: Borrow<Histogram<T>>>(&mut self, other: B) -> Result<(), &'static str>
Subtract the contents of another histogram from this one.
May fail if values in the other histogram are higher than .high()
, and auto-resize is
disabled. Or, if the count for a given value in the other histogram is higher than that of
this histogram. In the latter case, some of the counts may still have been updated, which
may cause data corruption.
fn clear(&mut self)
Clear the contents of this histogram while preserving its statistics and configuration.
fn reset(&mut self)
Reset the contents and statistics of this histogram, preserving only its configuration.
fn auto(&mut self, enabled: bool)
Control whether or not the histogram can auto-resize and auto-adjust it's highest trackable value as high-valued samples are recorded.
fn new(sigfig: u32) -> Result<Histogram<T>, &'static str>
Construct an auto-resizing Histogram
with a lowest discernible value of 1 and an
auto-adjusting highest trackable value. Can auto-resize up to track values up to
(i64::max_value() / 2)
.
sigfig
specifies the number of significant value digits to preserve in the recorded data.
This is the number of significant decimal digits to which the histogram will maintain value
resolution and separation. Must be a non-negative integer between 0 and 5.
fn new_with_max(high: i64, sigfig: u32) -> Result<Histogram<T>, &'static str>
Construct a Histogram
given a known maximum value to be tracked, and a number of
significant decimal digits. The histogram will be constructed to implicitly track
(distinguish from 0) values as low as 1. Auto-resizing will be disabled.
high
is the highest value to be tracked by the histogram, and must be a positive integer
that is >= 2. sigfig
specifies the number of significant figures to maintain. This is the
number of significant decimal digits to which the histogram will maintain value resolution
and separation. Must be a non-negative integer between 0 and 5.
fn new_with_bounds(low: i64, high: i64, sigfig: u32) -> Result<Histogram<T>, &'static str>
Construct a Histogram
with known upper and lower bounds for recorded sample values.
Providing a lowest discernible value (low
) is useful is situations where the units used
for the histogram's values are much smaller that the minimal accuracy required. E.g. when
tracking time values stated in nanosecond units, where the minimal accuracy required is a
microsecond, the proper value for low
would be 1000.
low
is the lowest value that can be discerned (distinguished from 0) by the histogram,
and must be a positive integer that is >= 1. It may be internally rounded down to nearest
power of 2. high
is the highest value to be tracked by the histogram, and must be a
positive integer that is >= (2 * low)
. sigfig
Specifies the number of significant
figures to maintain. This is the number of significant decimal digits to which the
histogram will maintain value resolution and separation. Must be a non-negative integer
between 0 and 5.
fn new_from<F: Num + ToPrimitive + Copy>(source: &Histogram<F>) -> Histogram<T>
Construct a Histogram
with the same range settings as a given source histogram,
duplicating the source's start/end timestamps (but NOT its contents).
fn record(&mut self, value: i64) -> Result<(), ()>
Record value
in the histogram.
Returns an error if value
exceeds the highest trackable value and auto-resize is
disabled.
fn record_n(&mut self, value: i64, count: T) -> Result<(), ()>
Record multiple samples for a value in the histogram, adding to the value's current count.
count
is the number of occurrences of this value to record. Returns an error if value
exceeds the highest trackable value and auto-resize is disabled.
fn record_correct(&mut self, value: i64, interval: i64) -> Result<(), ()>
Record a value in the histogram while correcting for coordinated omission.
See record_correct
for further documentation.
fn record_n_correct(&mut self, value: i64, count: T, interval: i64) -> Result<(), ()>
Record multiple values in the histogram while correcting for coordinated omission.
To compensate for the loss of sampled values when a recorded value is larger than the
expected interval between value samples, this method will auto-generate and record an
additional series of decreasingly-smaller (down to interval
) value records.
Note: This is a at-recording correction method, as opposed to the post-recording correction
method provided by correct_clone
. The two methods are mutually exclusive, and only one of
the two should be be used on a given data set to correct for the same coordinated omission
issue.
Returns an error if value
exceeds the highest trackable value and auto-resize is
disabled.
fn iter_percentiles<'a>(&'a self, percentileTicksPerHalfDistance: isize) -> HistogramIterator<'a, T, Iter<'a, T>>
Iterate through histogram values by percentile levels.
The iteration mechanic for this iterator may appear somewhat confusing, but it yields
fairly pleasing output. The iterator starts with a percentile step size of
100/halving_period
. For every iteration, it yields a value whose percentile is that much
greater than the previously emitted percentile (i.e., initially 0, 10, 20, etc.). Once
halving_period
values have been emitted, the percentile step size is halved, and the
iteration continues.
The iterator yields a four-value tuple with the following values (in order): the value at the current iterator step, the percentile of samples at or below that value, the number of samples recorded at this value, and the number of samples present between the last iterator value and the current one.
use hdrsample::Histogram; let mut hist = Histogram::<u64>::new_with_max(10000, 4).unwrap(); for i in 0..10000 { hist += i; } let mut perc = hist.iter_percentiles(1); println!("{:?}", hist.iter_percentiles(1).collect::<Vec<_>>()); assert_eq!(perc.next(), Some((hist.value_at_percentile(0.01), 0.01, 1, 1))); // step size = 50 assert_eq!(perc.next(), Some((hist.value_at_percentile(50.0), 50.0, 1, 5000 - 1))); // step size = 25 assert_eq!(perc.next(), Some((hist.value_at_percentile(75.0), 75.0, 1, 2500))); // step size = 12.5 assert_eq!(perc.next(), Some((hist.value_at_percentile(87.5), 87.5, 1, 1250))); // step size = 6.25 assert_eq!(perc.next(), Some((hist.value_at_percentile(93.75), 93.75, 1, 625))); // step size = 3.125 assert_eq!(perc.next(), Some((hist.value_at_percentile(96.88), 96.88, 1, 313))); // etc...
fn iter_linear<'a>(&'a self, step: i64) -> HistogramIterator<'a, T, Iter<'a, T>>
Iterates through histogram values using linear value steps. The iteration is performed in
steps of size step
, each one yielding the count for all values in the preceeding value
range of size step
. The iterator terminates when all recorded histogram values are
exhausted.
The iterator yields a four-value tuple with the following values (in order): the value at the current iterator step, the percentile of samples at or below that value, the number of samples recorded at this value, and the number of samples present between the last iterator value and the current one.
use hdrsample::Histogram; let mut hist = Histogram::<u64>::new_with_max(1000, 3).unwrap(); hist += 100; hist += 500; hist += 800; hist += 850; let mut perc = hist.iter_linear(100); assert_eq!(perc.next(), Some((99, hist.percentile_below(99), 0, 0))); assert_eq!(perc.next(), Some((199, hist.percentile_below(199), 0, 1))); assert_eq!(perc.next(), Some((299, hist.percentile_below(299), 0, 0))); assert_eq!(perc.next(), Some((399, hist.percentile_below(399), 0, 0))); assert_eq!(perc.next(), Some((499, hist.percentile_below(499), 0, 0))); assert_eq!(perc.next(), Some((599, hist.percentile_below(599), 0, 1))); assert_eq!(perc.next(), Some((699, hist.percentile_below(699), 0, 0))); assert_eq!(perc.next(), Some((799, hist.percentile_below(799), 0, 0))); assert_eq!(perc.next(), Some((899, hist.percentile_below(899), 0, 2))); assert_eq!(perc.next(), None);
fn iter_log<'a>(&'a self, start: i64, exp: f64) -> HistogramIterator<'a, T, Iter<'a, T>>
Iterates through histogram values at logarithmically increasing levels. The iteration is
performed in steps that start at start
and increase exponentially according to exp
. The
iterator terminates when all recorded histogram values are exhausted.
The iterator yields a four-value tuple with the following values (in order): the value at the current iterator step, the percentile of samples at or below that value, the number of samples recorded at this value, and the number of samples present between the last iterator value and the current one.
use hdrsample::Histogram; let mut hist = Histogram::<u64>::new_with_max(1000, 3).unwrap(); hist += 100; hist += 500; hist += 800; hist += 850; let mut perc = hist.iter_log(1, 10.0); assert_eq!(perc.next(), Some((0, hist.percentile_below(0), 0, 0))); assert_eq!(perc.next(), Some((9, hist.percentile_below(9), 0, 0))); assert_eq!(perc.next(), Some((99, hist.percentile_below(99), 0, 0))); assert_eq!(perc.next(), Some((999, hist.percentile_below(999), 0, 4))); assert_eq!(perc.next(), None);
fn iter_recorded<'a>(&'a self) -> HistogramIterator<'a, T, Iter<'a, T>>
Iterates through all recorded histogram values using the finest granularity steps supported by the underlying representation. The iteration steps through all non-zero recorded value counts, and terminates when all recorded histogram values are exhausted.
The iterator yields a four-value tuple with the following values (in order): the value at the current iterator step, the percentile of samples at or below that value, the number of samples recorded at this value, and the number of samples present between the last iterator value and the current one.
use hdrsample::Histogram; let mut hist = Histogram::<u64>::new_with_max(1000, 3).unwrap(); hist += 100; hist += 500; hist += 800; hist += 850; let mut perc = hist.iter_recorded(); assert_eq!(perc.next(), Some((100, hist.percentile_below(100), 1, 1))); assert_eq!(perc.next(), Some((500, hist.percentile_below(500), 1, 1))); assert_eq!(perc.next(), Some((800, hist.percentile_below(800), 1, 1))); assert_eq!(perc.next(), Some((850, hist.percentile_below(850), 1, 1))); assert_eq!(perc.next(), None);
fn iter_all<'a>(&'a self) -> HistogramIterator<'a, T, Iter>
Iterates through all histogram values using the finest granularity steps supported by the underlying representation. The iteration steps through all possible unit value levels, regardless of whether or not there were recorded values for that value level, and terminates when all recorded histogram values are exhausted.
The iterator yields a four-value tuple with the following values (in order): the value at the current iterator step, the percentile of samples at or below that value, the number of samples recorded at this value, and the number of samples present between the last iterator value and the current one.
use hdrsample::Histogram; let mut hist = Histogram::<u64>::new_with_max(10, 1).unwrap(); hist += 1; hist += 5; hist += 8; let mut perc = hist.iter_all(); assert_eq!(perc.next(), Some((0, 0.0, 0, 0))); assert_eq!(perc.next(), Some((1, hist.percentile_below(1), 1, 1))); assert_eq!(perc.next(), Some((2, hist.percentile_below(2), 0, 0))); assert_eq!(perc.next(), Some((3, hist.percentile_below(3), 0, 0))); assert_eq!(perc.next(), Some((4, hist.percentile_below(4), 0, 0))); assert_eq!(perc.next(), Some((5, hist.percentile_below(5), 1, 1))); assert_eq!(perc.next(), Some((6, hist.percentile_below(6), 0, 0))); assert_eq!(perc.next(), Some((7, hist.percentile_below(7), 0, 0))); assert_eq!(perc.next(), Some((8, hist.percentile_below(8), 1, 1))); assert_eq!(perc.next(), Some((9, hist.percentile_below(9), 0, 0))); assert_eq!(perc.next(), Some((10, 100.0, 0, 0)));
fn min(&self) -> i64
Get the lowest recorded value level in the histogram. If the histogram has no recorded values, the value returned will be 0.
fn max(&self) -> i64
Get the highest recorded value level in the histogram. If the histogram has no recorded values, the value returned is undefined.
fn min_nz(&self) -> i64
Get the lowest recorded non-zero value level in the histogram.
If the histogram has no recorded values, the value returned is i64::max_value()
.
fn equivalent(&self, value1: i64, value2: i64) -> bool
Determine if two values are equivalent with the histogram's resolution. Equivalent here means that value samples recorded for any two equivalent values are counted in a common total count.
fn mean(&self) -> f64
Get the computed mean value of all recorded values in the histogram.
fn stdev(&self) -> f64
Get the computed standard deviation of all recorded values in the histogram
fn value_at_percentile(&self, percentile: f64) -> i64
Get the value at a given percentile.
When the given percentile is > 0.0, the value returned is the value that the given percentage of the overall recorded value entries in the histogram are either smaller than or equivalent to. When the given percentile is 0.0, the value returned is the value that all value entries in the histogram are either larger than or equivalent to.
Two values are considered "equivalent" if self.equivalent
would return true.
fn percentile_below(&self, value: i64) -> f64
Get the percentile of samples at and below a given value.
The percentile returned is the percentile of values recorded in the histogram that are smaller than or equivalent to the given value.
Two values are considered "equivalent" if self.equivalent
would return true.
fn count_between(&self, low: i64, high: i64) -> Result<i64, ()>
Get the count of recorded values within a range of value levels (inclusive to within the histogram's resolution).
low
gives the lower value bound on the range for which to provide the recorded count.
Will be rounded down with lowest_equivalent
. Similarly, high
gives the higher value
bound on the range, and will be rounded up with highest_equivalent
. The function returns
the total count of values recorded in the histogram within the value range that is >= lowest_equivalent(low)
and <= highest_equivalent(high)
.
May fail if the given values are out of bounds.
fn count_at(&self, value: i64) -> Result<T, ()>
Get the count of recorded values at a specific value (to within the histogram resolution at the value level).
The count is cumputed across values recorded in the histogram that are within the value
range that is >= lowest_equivalent(value)
and <= highest_equivalent(value)
.
May fail if the given value is out of bounds.
fn value_for(&self, index: usize) -> i64
Computes the matching histogram value for the given histogram bin.
fn lowest_equivalent(&self, value: i64) -> i64
Get the lowest value that is equivalent to the given value within the histogram's resolution. Equivalent here means that value samples recorded for any two equivalent values are counted in a common total count.
fn highest_equivalent(&self, value: i64) -> i64
Get the highest value that is equivalent to the given value within the histogram's resolution. Equivalent here means that value samples recorded for any two equivalent values are counted in a common total count.
Note that the return value is capped at i64::max_value()
.
fn median_equivalent(&self, value: i64) -> i64
Get a value that lies in the middle (rounded up) of the range of values equivalent the given value. Equivalent here means that value samples recorded for any two equivalent values are counted in a common total count.
Note that the return value is capped at i64::max_value()
.
fn next_non_equivalent(&self, value: i64) -> i64
Get the next value that is not equivalent to the given value within the histogram's resolution. Equivalent means that value samples recorded for any two equivalent values are counted in a common total count.
Note that the return value is capped at i64::max_value()
.
fn equivalent_range(&self, value: i64) -> i64
Get the size (in value units) of the range of values that are equivalent to the given value within the histogram's resolution. Equivalent here means that value samples recorded for any two equivalent values are counted in a common total count.
Trait Implementations
impl<T: Num + ToPrimitive + Copy> Index<usize> for Histogram<T>
[src]
type Output = T
The returned type after indexing
fn index(&self, index: usize) -> &Self::Output
The method for the indexing (Foo[Bar]
) operation
impl<T: Num + ToPrimitive + Copy> IndexMut<usize> for Histogram<T>
[src]
fn index_mut(&mut self, index: usize) -> &mut Self::Output
The method for the indexing (Foo[Bar]
) operation
impl<T: Num + ToPrimitive + Copy> Clone for Histogram<T>
[src]
fn clone(&self) -> Self
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<'a, T: Num + ToPrimitive + Copy> AddAssign<&'a Histogram<T>> for Histogram<T>
[src]
fn add_assign(&mut self, source: &'a Histogram<T>)
The method for the +=
operator
impl<'a, T: Num + ToPrimitive + Copy> SubAssign<&'a Histogram<T>> for Histogram<T>
[src]
fn sub_assign(&mut self, other: &'a Histogram<T>)
The method for the -=
operator
impl<T: Num + ToPrimitive + Copy> AddAssign<i64> for Histogram<T>
[src]
fn add_assign(&mut self, value: i64)
The method for the +=
operator