A histogram class with controllable binning and range strategy. More...

#include <histogram.hpp>

Classes
struct	check_constraints
	Verify the constraints on the histogram template class template parameters, and generate better error messages when they are not met. More...

Public Types
typedef std::vector< counter_type >	counters
	The type used to store the bins. More...

type traits
typedef binning_strategy_t	binning_strategy

typedef binning_strategy::sample_type	sample_type

typedef counter_type_t	counter_type

Public Member Functions
	histogram (binning_strategy const &mapping=binning_strategy())
	Construct a histogram given a mapping strategy. More...

std::uint64_t	nsamples () const
	Return the number of samples observed to this point. More...

sample_type	observed_min () const
	Return the smallest sample value observed to this point. More...

sample_type	observed_max () const
	Return the largest sample value observed to this point. More...

sample_type	estimated_mean () const
	Estimate the mean of the sample distribution. More...

sample_type	estimated_quantile (double q) const
	Estimate a quantile of the sample distribution. More...

std::uint64_t	underflow_count () const
	Return the number of samples smaller than the histogram range. More...

std::uint64_t	overflow_count () const
	Return the number of samples larger than the histogram range. More...

histogram_summary	summary () const
	Return a simple summary. More...

void	sample (sample_type const &t)
	Record a new sample. More...

void	weighted_sample (sample_type const &t, counter_type weight)
	Record a new sample. More...

void	reset ()
	Reset all counters. More...

Private Member Functions
std::size_t	nbins () const
	Compute the maximum number of bins that might be needed. More...

sample_type	midpoint (sample_type const &a, sample_type const &b) const
	Estimate a midpoint. More...

Private Attributes
binning_strategy	binning_

std::uint64_t	underflow_count_

std::uint64_t	overflow_count_

sample_type	observed_min_

sample_type	observed_max_

std::uint64_t	nsamples_

counters	bins_

Detailed Description

template<typename binning_strategy_t, typename counter_type_t = unsigned int>
class jb::histogram< binning_strategy_t, counter_type_t >

A histogram class with controllable binning and range strategy.

We are interested in capturing histograms of latency, and of rate measurements, and other things. The challenge is that we need good precision, but we also need to keep thousands of these histograms in memory. To increase precision in histograms one must increase the number of bins, but that increases the memory requirements.

Consider, for example, a typical latency measurement that typically ranges from 1 to 400 microseconds, but sometimes can peak to seconds. Capturing the full range at microsecond precision would require MiB of memory. While this is not a problem for a single histogram, what if we want to keep this histogram per symbol?

As an alternative, we can keep this histogram at full resolution between 0 and 1,000 microseconds, drop to 10 microsecond bins from there to 10,000 microseconds, then increase to 100 microsecond bins and so forth. For values higher than a prescribed limit we simply record "overflow".

This class implements such a histogram, with a user-provided mapping strategy to define the bins.

Template Parameters

binning_strategy_t	Please see jb::binning_strategy_concept.
counter_type	The type used for the counters. In most applications using int is sufficient, but if you are counting really large numbers you might consider using std::uint64_t, or if you are memory constrained consider using std::int16_t.

Definition at line 46 of file histogram.hpp.

Member Typedef Documentation

◆ binning_strategy

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

typedef binning_strategy_t jb::histogram< binning_strategy_t, counter_type_t >::binning_strategy

Definition at line 54 of file histogram.hpp.

◆ counter_type

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

typedef counter_type_t jb::histogram< binning_strategy_t, counter_type_t >::counter_type

Definition at line 56 of file histogram.hpp.

◆ counters

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

typedef std::vector<counter_type> jb::histogram< binning_strategy_t, counter_type_t >::counters

The type used to store the bins.

Definition at line 230 of file histogram.hpp.

◆ sample_type

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

typedef binning_strategy::sample_type jb::histogram< binning_strategy_t, counter_type_t >::sample_type

Definition at line 55 of file histogram.hpp.

Constructor & Destructor Documentation

◆ histogram()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

jb::histogram< binning_strategy_t, counter_type_t >::histogram ( binning_strategy const & mapping = binning_strategy() )

inlineexplicit

Construct a histogram given a mapping strategy.

Most mapping strategies are likely to be stateless, so the default constructor is adequate.

Parameters

mapping Define how samples are mapped into bins.

Definition at line 67 of file histogram.hpp.

Member Function Documentation

◆ estimated_mean()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

sample_type jb::histogram< binning_strategy_t, counter_type_t >::estimated_mean ( ) const

inline

Estimate the mean of the sample distribution.

Estimating the mean is O(N) where N is the number of bins.

Definition at line 98 of file histogram.hpp.

Referenced by jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::last_rate().

◆ estimated_quantile()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

sample_type jb::histogram< binning_strategy_t, counter_type_t >::estimated_quantile ( double q ) const

inline

Estimate a quantile of the sample distribution.

The inverse of the accumulated density function. Find the smallest value Q such that at most q * nsamples of the samples are smaller than Q. If you prefer to think in percentiles make

q = percentile / 100.0

Estimating quantiles is O(N) where N is the number of bins.

Definition at line 136 of file histogram.hpp.

Referenced by jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::last_rate(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::summary().

◆ midpoint()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

sample_type jb::histogram< binning_strategy_t, counter_type_t >::midpoint	(	sample_type const &	a,
		sample_type const &	b
	)		const

inlineprivate

Estimate a midpoint.

Definition at line 241 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean().

◆ nbins()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

std::size_t jb::histogram< binning_strategy_t, counter_type_t >::nbins ( ) const

inlineprivate

Compute the maximum number of bins that might be needed.

Definition at line 234 of file histogram.hpp.

◆ nsamples()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

std::uint64_t jb::histogram< binning_strategy_t, counter_type_t >::nsamples ( ) const

inline

Return the number of samples observed to this point.

Definition at line 79 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::last_rate(), jb::offline_feed_statistics::log_progress(), jb::book_depth_statistics::print_csv(), jb::offline_feed_statistics::print_csv(), jb::offline_feed_statistics::record_sample(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::summary().

◆ observed_max()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

sample_type jb::histogram< binning_strategy_t, counter_type_t >::observed_max ( ) const

inline

Return the largest sample value observed to this point.

Definition at line 89 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::last_rate(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::summary().

◆ observed_min()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

sample_type jb::histogram< binning_strategy_t, counter_type_t >::observed_min ( ) const

inline

Return the smallest sample value observed to this point.

Definition at line 84 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::last_rate(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::summary().

◆ overflow_count()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

std::uint64_t jb::histogram< binning_strategy_t, counter_type_t >::overflow_count ( ) const

inline

Return the number of samples larger than the histogram range.

Definition at line 180 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), and jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::last_rate().

◆ reset()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

void jb::histogram< binning_strategy_t, counter_type_t >::reset ( )

inline

Reset all counters.

Definition at line 224 of file histogram.hpp.

◆ sample()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

void jb::histogram< binning_strategy_t, counter_type_t >::sample ( sample_type const & t )

inline

Record a new sample.

Definition at line 197 of file histogram.hpp.

Referenced by BOOST_AUTO_TEST_CASE(), jb::offline_feed_statistics::record_sample(), and jb::book_depth_statistics::sample().

◆ summary()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

histogram_summary jb::histogram< binning_strategy_t, counter_type_t >::summary ( ) const

inline

Return a simple summary.

Definition at line 185 of file histogram.hpp.

◆ underflow_count()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

std::uint64_t jb::histogram< binning_strategy_t, counter_type_t >::underflow_count ( ) const

inline

Return the number of samples smaller than the histogram range.

Definition at line 175 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), and jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::last_rate().

◆ weighted_sample()

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

void jb::histogram< binning_strategy_t, counter_type_t >::weighted_sample	(	sample_type const &	t,
		counter_type	weight
	)

inline

Record a new sample.

Definition at line 202 of file histogram.hpp.

Referenced by jb::event_rate_histogram< std::chrono::nanoseconds, std::int64_t >::sample(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::sample().

Member Data Documentation

◆ binning_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

binning_strategy jb::histogram< binning_strategy_t, counter_type_t >::binning_

private

Definition at line 246 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::nbins(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::reset(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::weighted_sample().

◆ bins_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

counters jb::histogram< binning_strategy_t, counter_type_t >::bins_

private

Definition at line 252 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::weighted_sample().

◆ nsamples_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

std::uint64_t jb::histogram< binning_strategy_t, counter_type_t >::nsamples_

private

Definition at line 251 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_mean(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::estimated_quantile(), jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::nsamples(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::weighted_sample().

◆ observed_max_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

sample_type jb::histogram< binning_strategy_t, counter_type_t >::observed_max_

private

Definition at line 250 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::observed_max(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::weighted_sample().

◆ observed_min_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

sample_type jb::histogram< binning_strategy_t, counter_type_t >::observed_min_

private

Definition at line 249 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::observed_min(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::weighted_sample().

◆ overflow_count_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

std::uint64_t jb::histogram< binning_strategy_t, counter_type_t >::overflow_count_

private

Definition at line 248 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::overflow_count(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::weighted_sample().

◆ underflow_count_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>

std::uint64_t jb::histogram< binning_strategy_t, counter_type_t >::underflow_count_

private

Definition at line 247 of file histogram.hpp.

Referenced by jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::underflow_count(), and jb::histogram< integer_range_binning< std::uint64_t >, counter_type >::weighted_sample().

The documentation for this class was generated from the following file:

jb/histogram.hpp

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename binning_strategy_t, typename counter_type_t = unsigned int> class jb::histogram< binning_strategy_t, counter_type_t >

Member Typedef Documentation

◆ binning_strategy

◆ counter_type

◆ counters

◆ sample_type

Constructor & Destructor Documentation

◆ histogram()

Member Function Documentation

◆ estimated_mean()

◆ estimated_quantile()

◆ midpoint()

◆ nbins()

◆ nsamples()

◆ observed_max()

◆ observed_min()

◆ overflow_count()

◆ reset()

◆ sample()

◆ summary()

◆ underflow_count()

◆ weighted_sample()

Member Data Documentation

◆ binning_

◆ bins_

◆ nsamples_

◆ observed_max_

◆ observed_min_

◆ overflow_count_

◆ underflow_count_

template<typename binning_strategy_t, typename counter_type_t = unsigned int>
class jb::histogram< binning_strategy_t, counter_type_t >