From 65bc41090720cdc249c1b0b9b9b8a8f062b41268 Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Thu, 25 May 2023 22:22:25 -0400 Subject: mean and variance: More tests Add some more tests that test conventional and weighted mean simultaneously, and with a table of values that represents events that we'll be using this to look for so we can verify-by-eyeball that the output looks sane. Signed-off-by: Kent Overstreet --- fs/bcachefs/mean_and_variance.h | 14 +++-- fs/bcachefs/mean_and_variance_test.c | 101 ++++++++++++++++++++++++++++++++--- fs/bcachefs/util.c | 4 +- 3 files changed, 102 insertions(+), 17 deletions(-) (limited to 'fs') diff --git a/fs/bcachefs/mean_and_variance.h b/fs/bcachefs/mean_and_variance.h index 880e9501c614..6dd4c050e78a 100644 --- a/fs/bcachefs/mean_and_variance.h +++ b/fs/bcachefs/mean_and_variance.h @@ -176,14 +176,12 @@ static inline s64 fast_divpow2(s64 n, u8 d) * * see linked pdf equation 12. */ -static inline struct mean_and_variance -mean_and_variance_update(struct mean_and_variance s, s64 v) -{ - return (struct mean_and_variance) { - .n = s.n + 1, - .sum = s.sum + v, - .sum_squares = u128_add(s.sum_squares, u128_square(abs(v))), - }; +static inline void +mean_and_variance_update(struct mean_and_variance *s, s64 v) +{ + s->n++; + s->sum += v; + s->sum_squares = u128_add(s->sum_squares, u128_square(abs(v))); } s64 mean_and_variance_get_mean(struct mean_and_variance s); diff --git a/fs/bcachefs/mean_and_variance_test.c b/fs/bcachefs/mean_and_variance_test.c index 2b4cf9b1781b..019583c3ca0e 100644 --- a/fs/bcachefs/mean_and_variance_test.c +++ b/fs/bcachefs/mean_and_variance_test.c @@ -9,15 +9,15 @@ static void mean_and_variance_basic_test(struct kunit *test) { struct mean_and_variance s = {}; - s = mean_and_variance_update(s, 2); - s = mean_and_variance_update(s, 2); + mean_and_variance_update(&s, 2); + mean_and_variance_update(&s, 2); KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(s), 2); KUNIT_EXPECT_EQ(test, mean_and_variance_get_variance(s), 0); KUNIT_EXPECT_EQ(test, s.n, 2); - s = mean_and_variance_update(s, 4); - s = mean_and_variance_update(s, 4); + mean_and_variance_update(&s, 4); + mean_and_variance_update(&s, 4); KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(s), 3); KUNIT_EXPECT_EQ(test, mean_and_variance_get_variance(s), 1); @@ -33,8 +33,6 @@ static void mean_and_variance_weighted_test(struct kunit *test) { struct mean_and_variance_weighted s = { .weight = 2 }; - s.weight = 2; - mean_and_variance_weighted_update(&s, 10); KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s), 10); KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s), 0); @@ -60,7 +58,6 @@ static void mean_and_variance_weighted_test(struct kunit *test) mean_and_variance_weighted_update(&s, -30); KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s), -16); KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s), 72); - } static void mean_and_variance_weighted_advanced_test(struct kunit *test) @@ -81,7 +78,93 @@ static void mean_and_variance_weighted_advanced_test(struct kunit *test) KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s), -11); KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s), 107); +} + +static void do_mean_and_variance_test(struct kunit *test, + s64 initial_value, + s64 initial_n, + s64 n, + unsigned weight, + s64 *data, + s64 *mean, + s64 *stddev, + s64 *weighted_mean, + s64 *weighted_stddev) +{ + struct mean_and_variance mv = {}; + struct mean_and_variance_weighted vw = { .weight = weight }; + + for (unsigned i = 0; i < initial_n; i++) { + mean_and_variance_update(&mv, initial_value); + mean_and_variance_weighted_update(&vw, initial_value); + KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(mv), initial_value); + KUNIT_EXPECT_EQ(test, mean_and_variance_get_stddev(mv), 0); + KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(vw), initial_value); + KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_stddev(vw),0); + } + + for (unsigned i = 0; i < n; i++) { + mean_and_variance_update(&mv, data[i]); + mean_and_variance_weighted_update(&vw, data[i]); + + KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(mv), mean[i]); + KUNIT_EXPECT_EQ(test, mean_and_variance_get_stddev(mv), stddev[i]); + KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(vw), weighted_mean[i]); + KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_stddev(vw),weighted_stddev[i]); + } + + KUNIT_EXPECT_EQ(test, mv.n, initial_n + n); +} + +/* Test behaviour with a single outlier, then back to steady state: */ +static void mean_and_variance_test_1(struct kunit *test) +{ + s64 d[] = { 100, 10, 10, 10, 10, 10, 10 }; + s64 mean[] = { 22, 21, 20, 19, 18, 17, 16 }; + s64 stddev[] = { 32, 29, 28, 27, 26, 25, 24 }; + s64 weighted_mean[] = { 32, 27, 22, 19, 17, 15, 14 }; + s64 weighted_stddev[] = { 38, 35, 31, 27, 24, 21, 18 }; + + do_mean_and_variance_test(test, 10, 6, ARRAY_SIZE(d), 2, + d, mean, stddev, weighted_mean, weighted_stddev); +} + +static void mean_and_variance_test_2(struct kunit *test) +{ + s64 d[] = { 100, 10, 10, 10, 10, 10, 10 }; + s64 mean[] = { 10, 10, 10, 10, 10, 10, 10 }; + s64 stddev[] = { 9, 9, 9, 9, 9, 9, 9 }; + s64 weighted_mean[] = { 32, 27, 22, 19, 17, 15, 14 }; + s64 weighted_stddev[] = { 38, 35, 31, 27, 24, 21, 18 }; + + do_mean_and_variance_test(test, 10, 6, ARRAY_SIZE(d), 2, + d, mean, stddev, weighted_mean, weighted_stddev); +} + +/* Test behaviour where we switch from one steady state to another: */ +static void mean_and_variance_test_3(struct kunit *test) +{ + s64 d[] = { 100, 100, 100, 100, 100 }; + s64 mean[] = { 22, 32, 40, 46, 50 }; + s64 stddev[] = { 32, 39, 42, 44, 45 }; + s64 weighted_mean[] = { 32, 49, 61, 71, 78 }; + s64 weighted_stddev[] = { 38, 44, 44, 41, 38 }; + + do_mean_and_variance_test(test, 10, 6, ARRAY_SIZE(d), 2, + d, mean, stddev, weighted_mean, weighted_stddev); +} + +static void mean_and_variance_test_4(struct kunit *test) +{ + s64 d[] = { 100, 100, 100, 100, 100 }; + s64 mean[] = { 10, 11, 12, 13, 14 }; + s64 stddev[] = { 9, 13, 15, 17, 19 }; + s64 weighted_mean[] = { 32, 49, 61, 71, 78 }; + s64 weighted_stddev[] = { 38, 44, 44, 41, 38 }; + + do_mean_and_variance_test(test, 10, 6, ARRAY_SIZE(d), 2, + d, mean, stddev, weighted_mean, weighted_stddev); } static void mean_and_variance_fast_divpow2(struct kunit *test) @@ -139,6 +222,10 @@ static struct kunit_case mean_and_variance_test_cases[] = { KUNIT_CASE(mean_and_variance_basic_test), KUNIT_CASE(mean_and_variance_weighted_test), KUNIT_CASE(mean_and_variance_weighted_advanced_test), + KUNIT_CASE(mean_and_variance_test_1), + KUNIT_CASE(mean_and_variance_test_2), + KUNIT_CASE(mean_and_variance_test_3), + KUNIT_CASE(mean_and_variance_test_4), {} }; diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index e0c93da2523f..6374d8aa9afc 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -350,7 +350,7 @@ static inline void bch2_time_stats_update_one(struct bch2_time_stats *stats, if (time_after64(end, start)) { duration = end - start; - stats->duration_stats = mean_and_variance_update(stats->duration_stats, duration); + mean_and_variance_update(&stats->duration_stats, duration); mean_and_variance_weighted_update(&stats->duration_stats_weighted, duration); stats->max_duration = max(stats->max_duration, duration); stats->min_duration = min(stats->min_duration, duration); @@ -359,7 +359,7 @@ static inline void bch2_time_stats_update_one(struct bch2_time_stats *stats, if (time_after64(end, stats->last_event)) { freq = end - stats->last_event; - stats->freq_stats = mean_and_variance_update(stats->freq_stats, freq); + mean_and_variance_update(&stats->freq_stats, freq); mean_and_variance_weighted_update(&stats->freq_stats_weighted, freq); stats->max_freq = max(stats->max_freq, freq); stats->min_freq = min(stats->min_freq, freq); -- cgit