From 8c61dbce195987d352034663204d5df32776e9cb Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Tue, 11 Oct 2016 17:25:58 +0200 Subject: [PATCH] src/utils_latency.[ch]: Improve accuracy, update unit test. --- src/utils_latency.c | 53 +++++-------- src/utils_latency.h | 15 ++++ src/utils_latency_test.c | 194 ++++++++++++++++++++++++----------------------- 3 files changed, 134 insertions(+), 128 deletions(-) diff --git a/src/utils_latency.c b/src/utils_latency.c index 30f13c70..1a82eab6 100644 --- a/src/utils_latency.c +++ b/src/utils_latency.c @@ -37,10 +37,6 @@ # define LLONG_MAX 9223372036854775807LL #endif -#ifndef HISTOGRAM_NUM_BINS -# define HISTOGRAM_NUM_BINS 1000 -#endif - #ifndef HISTOGRAM_DEFAULT_BIN_WIDTH /* 1048576 = 2^20 ^= 1/1024 s */ # define HISTOGRAM_DEFAULT_BIN_WIDTH 1048576 @@ -302,15 +298,6 @@ cdtime_t latency_counter_get_start_time (const latency_counter_t *lc) /* {{{ */ return lc->start_time; } /* }}} cdtime_t latency_counter_get_start_time */ -/* - * NAME - * latency_counter_get_rate(counter,lower,upper,now) - * - * DESCRIPTION - * Calculates rate of latency values fall within requested interval. - * Interval specified as [lower,upper] (including boundaries). - * When upper value is equal to 0 then interval is [lower, infinity). - */ double latency_counter_get_rate (const latency_counter_t *lc, /* {{{ */ cdtime_t lower, cdtime_t upper, const cdtime_t now) @@ -322,17 +309,16 @@ double latency_counter_get_rate (const latency_counter_t *lc, /* {{{ */ if ((lc == NULL) || (lc->num == 0)) return (0); - if (lower < 1) { - //sum += lc->zero; - //lower = 1; - return (0); - } - if (upper && (upper < lower)) return (0); - /* A latency of _exactly_ 1.0 ms is stored in the buffer 0 */ - lower_bin = (lower - 1) / lc->bin_width; + /* Buckets have an exclusive lower bound and an inclusive upper bound. That + * means that the first bucket, index 0, represents (0-bin_width]. That means + * that lower==bin_width needs to result in lower_bin=0, hence the -1. */ + if (lower) + lower_bin = (lower - 1) / lc->bin_width; + else + lower_bin = 0; if (upper) upper_bin = (upper - 1) / lc->bin_width; @@ -353,22 +339,21 @@ double latency_counter_get_rate (const latency_counter_t *lc, /* {{{ */ sum += lc->histogram[i]; } - /* Approximate ratio of requests below "lower" */ - cdtime_t lower_bin_boundary = lower_bin * lc->bin_width; - - /* When bin width is 0.125 (for example), then bin 0 stores - * values for interval [0, 0.124) (excluding). - * With lower = 0.100, the ratio should be 0.099 / 0.125. - * I.e. ratio = 0.100 - 0.000 - 0.001 - */ - double ratio = (double)(lower - lower_bin_boundary - DOUBLE_TO_CDTIME_T(0.001)) - / (double)lc->bin_width; - sum -= ratio * lc->histogram[lower_bin]; + if (lower) { + /* Approximate ratio of requests in lower_bin, that fall between + * lower_bin_boundary and lower. This ratio is then subtracted from sum to + * increase accuracy. */ + cdtime_t lower_bin_boundary = lower_bin * lc->bin_width; + assert (lower > lower_bin_boundary); + double lower_ratio = (double)(lower - lower_bin_boundary - 1) / ((double) lc->bin_width); + sum -= lower_ratio * lc->histogram[lower_bin]; + } - /* Approximate ratio of requests above "upper" */ - cdtime_t upper_bin_boundary = (upper_bin + 1) * lc->bin_width; if (upper) { + /* As above: approximate ratio of requests in upper_bin, that fall between + * upper and upper_bin_boundary. */ + cdtime_t upper_bin_boundary = (upper_bin + 1) * lc->bin_width; assert (upper <= upper_bin_boundary); double ratio = (double)(upper_bin_boundary - upper) / (double)lc->bin_width; sum -= ratio * lc->histogram[upper_bin]; diff --git a/src/utils_latency.h b/src/utils_latency.h index bb456f51..add71842 100644 --- a/src/utils_latency.h +++ b/src/utils_latency.h @@ -28,6 +28,10 @@ #include "utils_time.h" +#ifndef HISTOGRAM_NUM_BINS +# define HISTOGRAM_NUM_BINS 1000 +#endif + struct latency_counter_s; typedef struct latency_counter_s latency_counter_t; @@ -45,6 +49,17 @@ cdtime_t latency_counter_get_average (latency_counter_t *lc); cdtime_t latency_counter_get_percentile (latency_counter_t *lc, double percent); cdtime_t latency_counter_get_start_time (const latency_counter_t *lc); + +/* + * NAME + * latency_counter_get_rate(counter,lower,upper,now) + * + * DESCRIPTION + * Calculates rate of latency values fall within requested interval. + * Interval specified as [lower,upper], i.e. boundaries are inclusive. + * When lower is zero, then the interval is (0, upper]. + * When upper is zero, then the interval is [lower, infinity). + */ double latency_counter_get_rate (const latency_counter_t *lc, cdtime_t lower, cdtime_t upper, const cdtime_t now); diff --git a/src/utils_latency_test.c b/src/utils_latency_test.c index 29750959..fe871710 100644 --- a/src/utils_latency_test.c +++ b/src/utils_latency_test.c @@ -96,108 +96,114 @@ DEF_TEST(percentile) return 0; } -DEF_TEST (rate) { - size_t i; +DEF_TEST (get_rate) { + /* We re-declare the struct here so we can inspect its content. */ + struct { + cdtime_t start_time; + cdtime_t sum; + size_t num; + cdtime_t min; + cdtime_t max; + cdtime_t bin_width; + int histogram[HISTOGRAM_NUM_BINS]; + } *peek; latency_counter_t *l; CHECK_NOT_NULL (l = latency_counter_create ()); + peek = (void *) l; - for (i = 0; i < 125; i++) { - latency_counter_add (l, TIME_T_TO_CDTIME_T (((time_t) i) + 1)); + for (time_t i = 1; i <= 125; i++) { + latency_counter_add (l, TIME_T_TO_CDTIME_T(i)); + } + + /* We expect a bucket width of 125ms. */ + EXPECT_EQ_UINT64 (DOUBLE_TO_CDTIME_T(0.125), peek->bin_width); + + struct { + size_t index; + int want; + } bucket_cases[] = { + { 0, 0}, /* (0.000-0.125] */ + { 1, 0}, /* (0.125-0.250] */ + { 2, 0}, /* (0.250-0.375] */ + { 3, 0}, /* (0.375-0.500] */ + { 4, 0}, /* (0.500-0.625] */ + { 5, 0}, /* (0.625-0.750] */ + { 6, 0}, /* (0.750-0.875] */ + { 7, 1}, /* (0.875-1.000] */ + { 8, 0}, /* (1.000-1.125] */ + { 9, 0}, /* (1.125-1.250] */ + {10, 0}, /* (1.250-1.375] */ + {11, 0}, /* (1.375-1.500] */ + {12, 0}, /* (1.500-1.625] */ + {13, 0}, /* (1.625-1.750] */ + {14, 0}, /* (1.750-1.875] */ + {15, 1}, /* (1.875-2.000] */ + {16, 0}, /* (2.000-2.125] */ + }; + + for (size_t i = 0; i < STATIC_ARRAY_SIZE(bucket_cases); i++) { + size_t index = bucket_cases[i].index; + EXPECT_EQ_INT(bucket_cases[i].want, peek->histogram[index]); } - //Test expects bin width will be equal to 0.125s - - EXPECT_EQ_DOUBLE (1/125, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(10), - DOUBLE_TO_CDTIME_T(10), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - EXPECT_EQ_DOUBLE (0, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(10.001), - DOUBLE_TO_CDTIME_T(10.125), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - EXPECT_EQ_DOUBLE (1/125, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(10.001), - DOUBLE_TO_CDTIME_T(10.876), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - EXPECT_EQ_DOUBLE (2/125, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(10.000), - DOUBLE_TO_CDTIME_T(10.876), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - //Range - EXPECT_EQ_DOUBLE (10.000 + 1.000/125, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(10), - DOUBLE_TO_CDTIME_T(20), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - //Range w/o interpolations - EXPECT_EQ_DOUBLE (100, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(0.001), - DOUBLE_TO_CDTIME_T(100.0), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - //Full range - EXPECT_EQ_DOUBLE (125.0, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(0.001), + + struct { + cdtime_t lower_bound; + cdtime_t upper_bound; + double want; + } cases[] = { + { // bucket 6 is zero + DOUBLE_TO_CDTIME_T(0.750), + DOUBLE_TO_CDTIME_T(0.875), + 0.00, + }, + { // bucket 7 contains the t=1 update + DOUBLE_TO_CDTIME_T(0.875), + DOUBLE_TO_CDTIME_T(1.000), + 1.00, + }, + { // range: bucket 7 - bucket 15; contains the t=1 and t=2 updates + DOUBLE_TO_CDTIME_T(0.875), + DOUBLE_TO_CDTIME_T(2.000), + 2.00, + }, + { // lower bucket is only partially applied + DOUBLE_TO_CDTIME_T(0.875 + (0.125 / 4)), + DOUBLE_TO_CDTIME_T(2.000), + 1.75, + }, + { // upper bucket is only partially applied + DOUBLE_TO_CDTIME_T(0.875), + DOUBLE_TO_CDTIME_T(2.000 - (0.125 / 4)), + 1.75, + }, + { // both buckets are only partially applied + DOUBLE_TO_CDTIME_T(0.875 + (0.125 / 4)), + DOUBLE_TO_CDTIME_T(2.000 - (0.125 / 4)), + 1.50, + }, + { // lower bound is unspecified + 0, + DOUBLE_TO_CDTIME_T(2.000), + 2.00, + }, + { // upper bound is unspecified + DOUBLE_TO_CDTIME_T(125.000 - 0.125), 0, - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - //Overflow test - EXPECT_EQ_DOUBLE (125.0, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(0.001), - DOUBLE_TO_CDTIME_T(100000), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - - //Split range to two parts - EXPECT_EQ_DOUBLE (92.0, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(0.001), - DOUBLE_TO_CDTIME_T(92.00), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - EXPECT_EQ_DOUBLE (8, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(92.001), - DOUBLE_TO_CDTIME_T(100.00), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - - //Sum of rates for latencies [0.876, 1.000] - EXPECT_EQ_DOUBLE (1, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(0.876), + 1.00, + }, + { // overflow test DOUBLE_TO_CDTIME_T(1.000), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); - double sum = 0; - for (i = 875 ; i < 1000 ; i += 5) { - sum += latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T((double)(i+1)/1000), - DOUBLE_TO_CDTIME_T((double)(i+5)/1000), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ); - printf("b: %.15g\n",sum); + DOUBLE_TO_CDTIME_T(999999), + 124.00, + }, }; - EXPECT_EQ_DOUBLE (1.000, sum); - EXPECT_EQ_DOUBLE (100/125, latency_counter_get_rate (l, - DOUBLE_TO_CDTIME_T(99.875), - DOUBLE_TO_CDTIME_T(99.975), - latency_counter_get_start_time(l) + TIME_T_TO_CDTIME_T(1) - ) - ); + for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) { + cdtime_t now = peek->start_time + TIME_T_TO_CDTIME_T(1); + EXPECT_EQ_DOUBLE (cases[i].want, + latency_counter_get_rate (l, cases[i].lower_bound, cases[i].upper_bound, now)); + } latency_counter_destroy (l); return 0; @@ -207,7 +213,7 @@ int main (void) { RUN_TEST(simple); RUN_TEST(percentile); - RUN_TEST(rate); + RUN_TEST(get_rate); END_TEST; } -- 2.11.0