stats: Use an algorithm popularised by Knuth to compute mean and variance

Suggested-by: Chris Wilson <chris@chris-wilson.co.uk>
Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>

1 files changed, 37 insertions, 5 deletions

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index e6babde6..20db806d 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -42,15 +42,47 @@ void igt_stats_push(igt_stats_t *stats, uint64_t value)
 {
 	igt_assert(stats->n_values < stats->capacity);
 	stats->values[stats->n_values++] = value;
+	stats->mean_variance_valid = false;
 }
 
-double igt_stats_get_mean(igt_stats_t *stats)
+/*
+ * Algorithm popularised by Knuth in:
+ *
+ * The Art of Computer Programming, volume 2: Seminumerical Algorithms,
+ * 3rd edn., p. 232. Boston: Addison-Wesley
+ *
+ * Source: https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
+ */
+static void igt_stats_knuth_mean_variance(igt_stats_t *stats)
 {
+	double mean = 0., m2 = 0.;
 	unsigned int i;
-	double a = 0.0;
 
-	for (i = 0; i < stats->n_values; i++)
-		a += (double)stats->values[i] / stats->n_values;
+	if (stats->mean_variance_valid)
+		return;
+
+	for (i = 0; i < stats->n_values; i++) {
+		double delta = stats->values[i] - mean;
+
+		mean += delta / (i + 1);
+		m2 += delta * (stats->values[i] - mean);
+	}
+
+	stats->mean = mean;
+	stats->variance = m2 / stats->n_values;
+	stats->mean_variance_valid = true;
+}
+
+double igt_stats_get_mean(igt_stats_t *stats)
+{
+	igt_stats_knuth_mean_variance(stats);
+
+	return stats->mean;
+}
+
+double igt_stats_get_variance(igt_stats_t *stats)
+{
+	igt_stats_knuth_mean_variance(stats);
 
-	return a;
+	return stats->variance;
 }