stats-dist.c revision 5f08b0309190ec818d46bfe0e497468b30714a93
1516N/A/* Copyright (c) 2015-2017 Dovecot authors, see the included COPYING file */
49N/A
49N/A#include "lib.h"
49N/A#include "stats-dist.h"
49N/A#include "sort.h"
49N/A
49N/A/* In order to have a vaguely accurate 95th percentile, you need way
49N/A more than 20 in your subsample. */
49N/A#define TIMING_DEFAULT_SUBSAMPLING_BUFFER (20*24) /* 20*24 fits in a page */
49N/A
49N/Astruct stats_dist {
49N/A unsigned int sample_count;
49N/A unsigned int count;
49N/A bool sorted;
49N/A uint64_t min;
49N/A uint64_t max;
49N/A uint64_t sum;
49N/A uint64_t samples[];
49N/A};
49N/A
49N/Astruct stats_dist *stats_dist_init(void)
49N/A{
49N/A return stats_dist_init_with_size(TIMING_DEFAULT_SUBSAMPLING_BUFFER);
1685N/A}
49N/A
49N/Astruct stats_dist *stats_dist_init_with_size(unsigned int sample_count)
49N/A{
49N/A i_assert(sample_count > 0);
49N/A
49N/A struct stats_dist *stats =
49N/A i_malloc(sizeof(struct stats_dist) +
49N/A sizeof(uint64_t) * sample_count);
1050N/A stats->sample_count = sample_count;
1507N/A return stats;
96N/A}
1281N/A
1050N/Avoid stats_dist_deinit(struct stats_dist **_stats)
1507N/A{
1050N/A i_free_and_null(*_stats);
1507N/A}
49N/A
49N/Avoid stats_dist_reset(struct stats_dist *stats)
49N/A{
49N/A unsigned int sample_count = stats->sample_count;
51N/A i_zero(stats);
51N/A stats->sample_count = sample_count;
49N/A}
49N/A
96N/Avoid stats_dist_add(struct stats_dist *stats, uint64_t value)
237N/A{
237N/A if (stats->count < stats->sample_count) {
1507N/A stats->samples[stats->count] = value;
237N/A if (stats->count == 0)
237N/A stats->min = stats->max = value;
462N/A } else {
462N/A unsigned int idx = i_rand_limit(stats->count);
462N/A if (idx < stats->sample_count)
237N/A stats->samples[idx] = value;
237N/A }
462N/A
237N/A stats->count++;
237N/A stats->sum += value;
237N/A if (stats->max < value)
237N/A stats->max = value;
237N/A if (stats->min > value)
237N/A stats->min = value;
583N/A stats->sorted = FALSE;
136N/A}
96N/A
96N/Aunsigned int stats_dist_get_count(const struct stats_dist *stats)
96N/A{
237N/A return stats->count;
96N/A}
96N/A
136N/Auint64_t stats_dist_get_sum(const struct stats_dist *stats)
96N/A{
462N/A return stats->sum;
1507N/A}
1507N/A
462N/Auint64_t stats_dist_get_min(const struct stats_dist *stats)
96N/A{
96N/A return stats->min;
1050N/A}
462N/A
96N/Auint64_t stats_dist_get_max(const struct stats_dist *stats)
1050N/A{
1050N/A return stats->max;
1050N/A}
1050N/A
1050N/Auint64_t stats_dist_get_avg(const struct stats_dist *stats)
1050N/A{
1050N/A if (stats->count == 0)
1050N/A return 0;
222N/A
237N/A return (stats->sum + stats->count/2) / stats->count;
1685N/A}
1685N/A
1685N/Astatic void stats_dist_ensure_sorted(struct stats_dist *stats)
1281N/A{
1281N/A if (stats->sorted)
1281N/A return;
1281N/A
1281N/A unsigned int count = (stats->count < stats->sample_count)
1685N/A ? stats->count
1281N/A : stats->sample_count;
1281N/A i_qsort(stats->samples, count, sizeof(*stats->samples),
1281N/A uint64_cmp);
1685N/A stats->sorted = TRUE;
1281N/A}
237N/A
222N/Auint64_t stats_dist_get_median(const struct stats_dist *stats)
1281N/A{
462N/A if (stats->count == 0)
462N/A return 0;
237N/A /* cast-away const - reading requires sorting */
237N/A stats_dist_ensure_sorted((struct stats_dist *)stats);
1685N/A unsigned int count = (stats->count < stats->sample_count)
583N/A ? stats->count
583N/A : stats->sample_count;
1281N/A unsigned int idx1 = (count-1)/2, idx2 = count/2;
583N/A return (stats->samples[idx1] + stats->samples[idx2]) / 2;
1685N/A}
222N/A
237N/A/* This is independent of the stats framework, useful for any selection task */
1281N/Astatic unsigned int stats_dist_get_index(unsigned int range, double fraction)
1685N/A{
1685N/A /* With out of range fractions, we can give the caller what
583N/A they probably want rather than just crashing. */
1685N/A if (fraction >= 1.)
1685N/A return range - 1;
222N/A if (fraction <= 0.)
1685N/A return 0;
double idx_float = range * fraction;
unsigned int idx = idx_float; /* C defaults to rounding down */
idx_float -= idx;
/* Exact boundaries belong to the open range below them.
As FP isn't exact, and ratios may be specified inexactly,
include a small amount of fuzz around the exact boundary. */
if (idx_float < 1e-8*range)
idx--;
return idx;
}
uint64_t stats_dist_get_percentile(const struct stats_dist *stats, double fraction)
{
if (stats->count == 0)
return 0;
/* cast-away const - reading requires sorting */
stats_dist_ensure_sorted((struct stats_dist *)stats);
unsigned int count = (stats->count < stats->sample_count)
? stats->count
: stats->sample_count;
unsigned int idx = stats_dist_get_index(count, fraction);
return stats->samples[idx];
}