[i-g-t,3/5] stats: Use an algorithm popularised by Knuth to compute mean and variance

Commit Message

Lespiau, Damien June 25, 2015, 11:26 p.m. UTC

Suggested-by: Chris Wilson <[e-mail]>
Signed-off-by: Damien Lespiau <[e-mail]>
---
 lib/igt_stats.c | 42 +++++++++++++++++++++++++++++++++++++-----
 lib/igt_stats.h |  3 +++
 2 files changed, 40 insertions(+), 5 deletions(-)

Patch

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index e6babde..20db806 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;
 }
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index a46b399..acb86a6 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -28,9 +28,12 @@  typedef struct {
 	uint64_t *values;
 	unsigned int capacity;
 	unsigned int n_values;
+	unsigned int mean_variance_valid : 1;
+	double mean, variance;
 } igt_stats_t;
 
 void igt_stats_init(igt_stats_t *stats, unsigned int capacity);
 void igt_stats_fini(igt_stats_t *stats);
 void igt_stats_push(igt_stats_t *stats, uint64_t value);
 double igt_stats_get_mean(igt_stats_t *stats);
+double igt_stats_get_variance(igt_stats_t *stats);