timing.c revision 814bf67459ad405a157af0b8940602024d7fadfe
/* Copyright (c) 2015 Dovecot authors, see the included COPYING file */
#include "lib.h"
#include "timing.h"
#include "sort.h"
/* In order to have a vaguely accurate 95th percentile, you need way
more than 20 in your subsample. */
#define TIMING_SUBSAMPLING_BUFFER (20*24) /* 20*24 fits in a page */
struct timing {
unsigned int count;
bool sorted;
uint64_t min;
uint64_t samples[TIMING_SUBSAMPLING_BUFFER];
uint64_t max;
uint64_t sum;
};
struct timing *timing_init(void)
{
return i_new(struct timing, 1);
}
void timing_deinit(struct timing **_timing)
{
i_free_and_null(*_timing);
}
void timing_add_usecs(struct timing *timing, uint64_t usecs)
{
if (timing->count < TIMING_SUBSAMPLING_BUFFER) {
timing->samples[timing->count] = usecs;
if (timing->count == 0)
timing->min = timing->max = usecs;
} else {
unsigned int count = timing->count;
unsigned int idx;
if (count > RAND_MAX >> 6)
idx = (rand()*((uint64_t)RAND_MAX+1) + rand()) % count;
else
idx = rand() % count;
if (idx < TIMING_SUBSAMPLING_BUFFER)
timing->samples[idx] = usecs;
}
timing->count++;
timing->sum += usecs;
if (timing->max < usecs)
timing->max = usecs;
if (timing->min > usecs)
timing->min = usecs;
timing->sorted = FALSE;
}
unsigned int timing_get_count(const struct timing *timing)
{
return timing->count;
}
uint64_t timing_get_sum(const struct timing *timing)
{
return timing->sum;
}
uint64_t timing_get_min(const struct timing *timing)
{
return timing->min;
}
uint64_t timing_get_max(const struct timing *timing)
{
return timing->max;
}
uint64_t timing_get_avg(const struct timing *timing)
{
if (timing->count == 0)
return 0;
return (timing->sum + timing->count/2) / timing->count;
}
static void timing_ensure_sorted(struct timing *timing)
{
if (timing->sorted)
return;
i_qsort(timing->samples, timing->count, sizeof(*timing->samples),
uint64_cmp);
timing->sorted = TRUE;
}
uint64_t timing_get_median(const struct timing *timing)
{
if (timing->count == 0)
return 0;
/* cast-away const - reading requires sorting */
timing_ensure_sorted((struct timing *)timing);
unsigned int count = (timing->count < TIMING_SUBSAMPLING_BUFFER)
? timing->count
: TIMING_SUBSAMPLING_BUFFER;
unsigned int idx1 = (count-1)/2, idx2 = count/2;
return (timing->samples[idx1] + timing->samples[idx2]) / 2;
}
uint64_t timing_get_95th(const struct timing *timing)
{
if (timing->count == 0)
return 0;
/* cast-away const - reading requires sorting */
timing_ensure_sorted((struct timing *)timing);
unsigned int count = (timing->count < TIMING_SUBSAMPLING_BUFFER)
? timing->count
: TIMING_SUBSAMPLING_BUFFER;
unsigned int idx = count - count/20 - 1;
return timing->samples[idx];
}