More stats thingies

More stats thingies

[Damien Lespiau]

Added more metrics/estimators to analyze data. The next big step is really
being able to draw an histogram, nothing replaces visualization of the
distribution. eg. multi modal distribution: typical of cache hits (values
around a low mean) and caches miss (values around a high mean) in the same
data set.

-- 
Damien

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 01/18] stats: Zero the whole structure at init() time

[Damien Lespiau]

Because the structure started small, I initialized every member
directly, but that means that the new fields added weren't properly
initialized (sigh!). Zero the whole thing first then.

Also, the punishment for introducing a bug should be to write the
corresponding unit test. It's not a perfect one, but I'll take it.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c       |  4 +++-
 lib/tests/igt_stats.c | 11 +++++++++++
 2 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 65c0ac6..67ee947 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -23,16 +23,18 @@
  */
 
 #include <math.h>
+#include <string.h>
 
 #include "igt_core.h"
 #include "igt_stats.h"
 
 void igt_stats_init(igt_stats_t *stats, unsigned int capacity)
 {
+	memset(stats, 0, sizeof(*stats));
+
 	stats->values = calloc(capacity, sizeof(*stats->values));
 	igt_assert(stats->values);
 	stats->capacity = capacity;
-	stats->n_values = 0;
 }
 
 void igt_stats_fini(igt_stats_t *stats)
diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index f9081c7..f76d334 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -25,6 +25,16 @@
 #include "igt_core.h"
 #include "igt_stats.h"
 
+/* Make sure we zero igt_stats_t fields at init() time */
+static void test_init_zero(void)
+{
+	igt_stats_t stats;
+
+	stats.mean = 1.;
+	igt_stats_init(&stats, 2);
+	igt_assert(stats.mean == 0.);
+}
+
 static void test_mean(void)
 {
 	igt_stats_t stats;
@@ -103,6 +113,7 @@ static void test_std_deviation(void)
 
 igt_simple_main
 {
+	test_init_zero();
 	test_mean();
 	test_invalidate_mean();
 	test_std_deviation();
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 02/18] doc: Remove i-g-t/intel prefixes and capitalize section titles

[Damien Lespiau]

Looks better!

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_aux.c           | 2 +-
 lib/igt_core.c          | 2 +-
 lib/igt_debugfs.c       | 2 +-
 lib/igt_draw.c          | 2 +-
 lib/igt_fb.c            | 2 +-
 lib/igt_gt.c            | 2 +-
 lib/igt_kms.c           | 2 +-
 lib/intel_batchbuffer.c | 2 +-
 lib/intel_chipset.c     | 2 +-
 lib/intel_mmio.c        | 2 +-
 10 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/lib/igt_aux.c b/lib/igt_aux.c
index 5392e1a..cf13322 100644
--- a/lib/igt_aux.c
+++ b/lib/igt_aux.c
@@ -62,7 +62,7 @@
 /**
  * SECTION:igt_aux
  * @short_description: Auxiliary libraries and support functions
- * @title: i-g-t aux
+ * @title: aux
  * @include: igt_aux.h
  *
  * This library provides various auxiliary helper functions that don't really
diff --git a/lib/igt_core.c b/lib/igt_core.c
index 735b56d..fb6246c 100644
--- a/lib/igt_core.c
+++ b/lib/igt_core.c
@@ -74,7 +74,7 @@
 /**
  * SECTION:igt_core
  * @short_description: Core i-g-t testing support
- * @title: i-g-t core
+ * @title: Core
  * @include: igt_core.h
  *
  * This library implements the core of the i-g-t test support infrastructure.
diff --git a/lib/igt_debugfs.c b/lib/igt_debugfs.c
index 7319f2b..d4a48c5 100644
--- a/lib/igt_debugfs.c
+++ b/lib/igt_debugfs.c
@@ -42,7 +42,7 @@
 /**
  * SECTION:igt_debugfs
  * @short_description: Support code for debugfs features
- * @title: i-g-t debugfs
+ * @title: debugfs
  * @include: igt_debugfs.h
  *
  * This library provides helpers to access debugfs features. On top of some
diff --git a/lib/igt_draw.c b/lib/igt_draw.c
index fb9294d..2210f77 100644
--- a/lib/igt_draw.c
+++ b/lib/igt_draw.c
@@ -35,7 +35,7 @@
 /**
  * SECTION:igt_draw
  * @short_description: drawing helpers for tests
- * @title: i-g-t draw
+ * @title: Draw
  * @include: igt_draw.h
  *
  * This library contains some functions for drawing rectangles on buffers using
diff --git a/lib/igt_fb.c b/lib/igt_fb.c
index cc4b8ee..076f416 100644
--- a/lib/igt_fb.c
+++ b/lib/igt_fb.c
@@ -36,7 +36,7 @@
 /**
  * SECTION:igt_fb
  * @short_description: Framebuffer handling and drawing library
- * @title: i-g-t framebuffer
+ * @title: Framebuffer
  * @include: igt_fb.h
  *
  * This library contains helper functions for handling kms framebuffer objects
diff --git a/lib/igt_gt.c b/lib/igt_gt.c
index 1dcc3c3..8e5e076 100644
--- a/lib/igt_gt.c
+++ b/lib/igt_gt.c
@@ -40,7 +40,7 @@
 /**
  * SECTION:igt_gt
  * @short_description: GT support library
- * @title: i-g-t gt
+ * @title: GT
  * @include: igt_gt.h
  *
  * This library provides various auxiliary helper functions to handle general
diff --git a/lib/igt_kms.c b/lib/igt_kms.c
index f5670e0..ffacef1 100644
--- a/lib/igt_kms.c
+++ b/lib/igt_kms.c
@@ -177,7 +177,7 @@ const unsigned char* igt_kms_get_base_edid(void)
 /**
  * SECTION:igt_kms
  * @short_description: Kernel modesetting support library
- * @title: i-g-t kms
+ * @title: KMS
  * @include: igt_kms.h
  *
  * This library provides support to enumerate and set modeset configurations.
diff --git a/lib/intel_batchbuffer.c b/lib/intel_batchbuffer.c
index 8b68e52..a2e502f 100644
--- a/lib/intel_batchbuffer.c
+++ b/lib/intel_batchbuffer.c
@@ -47,7 +47,7 @@
 /**
  * SECTION:intel_batchbuffer
  * @short_description: Batchbuffer and blitter support
- * @title: intel batchbuffer
+ * @title: Batch Buffer
  * @include: intel_batchbuffer.h
  *
  * This library provides some basic support for batchbuffers and using the
diff --git a/lib/intel_chipset.c b/lib/intel_chipset.c
index 3b3e03b..c092628 100644
--- a/lib/intel_chipset.c
+++ b/lib/intel_chipset.c
@@ -44,7 +44,7 @@
 /**
  * SECTION:intel_chipset
  * @short_description: Feature macros and chipset helpers
- * @title: intel chipset
+ * @title: Chipset
  * @include: intel_chipset.h
  *
  * This library mostly provides feature macros which use raw pci device ids. It
diff --git a/lib/intel_mmio.c b/lib/intel_mmio.c
index b16a35d..45e9171 100644
--- a/lib/intel_mmio.c
+++ b/lib/intel_mmio.c
@@ -49,7 +49,7 @@
 /**
  * SECTION:intel_io
  * @short_description: Register access and sideband I/O libraray
- * @title: intel io
+ * @title: I/O
  * @include: intel_io.h
  *
  * This library provides register I/O helpers in both a basic version and a more
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 03/18] stats: Add header gards

[Damien Lespiau]

Sigh.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.h | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index 371def3..0d4669e 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -22,6 +22,9 @@
  *
  */
 
+#ifndef __IGT_STATS_H__
+#define __IGT_STATS_H__
+
 #include <stdint.h>
 
 typedef struct {
@@ -38,3 +41,5 @@ 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);
 double igt_stats_get_std_deviation(igt_stats_t *stats);
+
+#endif /* __IGT_STATS_H__ */
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 04/18] stats: Add gtkdoc section for igt_stats

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 .../intel-gpu-tools/intel-gpu-tools-docs.xml       |  1 +
 lib/igt_stats.c                                    | 74 ++++++++++++++++++++++
 lib/igt_stats.h                                    |  9 ++-
 3 files changed, 83 insertions(+), 1 deletion(-)

diff --git a/docs/reference/intel-gpu-tools/intel-gpu-tools-docs.xml b/docs/reference/intel-gpu-tools/intel-gpu-tools-docs.xml
index a6d1f89..7e481b8 100644
--- a/docs/reference/intel-gpu-tools/intel-gpu-tools-docs.xml
+++ b/docs/reference/intel-gpu-tools/intel-gpu-tools-docs.xml
@@ -17,6 +17,7 @@
     <title>API Reference</title>
     <xi:include href="xml/drmtest.xml"/>
     <xi:include href="xml/igt_core.xml"/>
+    <xi:include href="xml/igt_stats.xml"/>
     <xi:include href="xml/igt_debugfs.xml"/>
     <xi:include href="xml/igt_draw.xml"/>
     <xi:include href="xml/igt_kms.xml"/>
diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 67ee947..0bee138 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -28,6 +28,49 @@
 #include "igt_core.h"
 #include "igt_stats.h"
 
+/**
+ * SECTION:igt_stats
+ * @short_description: Tools for statistical analysis
+ * @title: Stats
+ * @include: igt_stats.h
+ *
+ * Various tools to make sense of data.
+ *
+ * #igt_stats_t is a container of data samples. igt_stats_push() is used to add
+ * new samples and various results (mean, variance, standard deviation, ...)
+ * can then be retrieved.
+ *
+ * |[
+ *	igt_stats_t stats;
+ *
+ *	igt_stats_init(&stats, 8);
+ *
+ *	igt_stats_push(&stats, 2);
+ *	igt_stats_push(&stats, 4);
+ *	igt_stats_push(&stats, 4);
+ *	igt_stats_push(&stats, 4);
+ *	igt_stats_push(&stats, 5);
+ *	igt_stats_push(&stats, 5);
+ *	igt_stats_push(&stats, 7);
+ *	igt_stats_push(&stats, 9);
+ *
+ *	printf("Mean: %lf\n", igt_stats_get_mean(&stats));
+ *
+ *	igt_stats_fini(&stats);
+ * ]|
+ */
+
+/**
+ * igt_stats_init:
+ * @stats: An #igt_stats_t instance
+ * @capacity: Number of data samples @stats can contain
+ *
+ * Initializes an #igt_stats_t instance to hold @capacity samples.
+ * igt_stats_fini() must be called once finished with @stats.
+ *
+ * We currently assume the user knows how many data samples upfront and there's
+ * no need to grow the array of values.
+ */
 void igt_stats_init(igt_stats_t *stats, unsigned int capacity)
 {
 	memset(stats, 0, sizeof(*stats));
@@ -37,11 +80,24 @@ void igt_stats_init(igt_stats_t *stats, unsigned int capacity)
 	stats->capacity = capacity;
 }
 
+/**
+ * igt_stats_fini:
+ * @stats: An #igt_stats_t instance
+ *
+ * Frees resources allocated in igt_stats_init().
+ */
 void igt_stats_fini(igt_stats_t *stats)
 {
 	free(stats->values);
 }
 
+/**
+ * igt_stats_push:
+ * @stats: An #igt_stats_t instance
+ * @value: An integer value
+ *
+ * Adds a new value to the @stats dataset.
+ */
 void igt_stats_push(igt_stats_t *stats, uint64_t value)
 {
 	igt_assert(stats->n_values < stats->capacity);
@@ -77,6 +133,12 @@ static void igt_stats_knuth_mean_variance(igt_stats_t *stats)
 	stats->mean_variance_valid = true;
 }
 
+/**
+ * igt_stats_get_mean:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the mean of the @stats dataset.
+ */
 double igt_stats_get_mean(igt_stats_t *stats)
 {
 	igt_stats_knuth_mean_variance(stats);
@@ -84,6 +146,12 @@ double igt_stats_get_mean(igt_stats_t *stats)
 	return stats->mean;
 }
 
+/**
+ * igt_stats_get_variance:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the variance of the @stats dataset.
+ */
 double igt_stats_get_variance(igt_stats_t *stats)
 {
 	igt_stats_knuth_mean_variance(stats);
@@ -91,6 +159,12 @@ double igt_stats_get_variance(igt_stats_t *stats)
 	return stats->variance;
 }
 
+/**
+ * igt_stats_get_std_deviation:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the standard deviation of the @stats dataset.
+ */
 double igt_stats_get_std_deviation(igt_stats_t *stats)
 {
 	igt_stats_knuth_mean_variance(stats);
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index 0d4669e..c45c819 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -27,10 +27,17 @@
 
 #include <stdint.h>
 
+/**
+ * igt_stats_t:
+ * @values: An array containing the pushed values
+ * @n_values: The number of pushed values
+ */
 typedef struct {
 	uint64_t *values;
-	unsigned int capacity;
 	unsigned int n_values;
+
+	/*< private >*/
+	unsigned int capacity;
 	unsigned int mean_variance_valid : 1;
 	double mean, variance;
 } igt_stats_t;
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 05/18] stats: Add a way to specify if the data set is a population or a sample

[Damien Lespiau]

This changes how we compute the variance. We want an unbiased variance
when reasoning about a sample.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c           | 35 ++++++++++++++++++++++++++++++++++-
 lib/igt_stats.h           |  2 ++
 lib/tests/igt_stats.c     |  1 +
 tools/skl_compute_wrpll.c |  1 +
 4 files changed, 38 insertions(+), 1 deletion(-)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 0bee138..c7d5fbd 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -92,6 +92,36 @@ void igt_stats_fini(igt_stats_t *stats)
 }
 
 /**
+ * igt_stats_set_population:
+ * @stats: An #igt_stats_t instance
+ * @full_population: Whether we're dealing with sample data or a full
+ *		     population
+ *
+ * In statistics, we usually deal with a subset of the full data (which may be
+ * a continuous or infinite set). Data analysis is then done on a sample of
+ * this population.
+ *
+ * This has some importance as only having a sample of the data leads to
+ * [biased estimators](https://en.wikipedia.org/wiki/Bias_of_an_estimator). We
+ * currently used the information given by this method to apply
+ * [Bessel's correction](https://en.wikipedia.org/wiki/Bessel%27s_correction)
+ * to the variance.
+ *
+ * When giving #true to this function, the data set in @stats is considered a
+ * full population. It's considered a sample of a bigger population otherwise.
+ *
+ * When newly created, @stats defaults to holding sample data.
+ */
+void igt_stats_set_population(igt_stats_t *stats, bool full_population)
+{
+	if (full_population == stats->is_population)
+		return;
+
+	stats->is_population = full_population;
+	stats->mean_variance_valid = false;
+}
+
+/**
  * igt_stats_push:
  * @stats: An #igt_stats_t instance
  * @value: An integer value
@@ -129,7 +159,10 @@ static void igt_stats_knuth_mean_variance(igt_stats_t *stats)
 	}
 
 	stats->mean = mean;
-	stats->variance = m2 / stats->n_values;
+	if (stats->n_values > 1 && !stats->is_population)
+		stats->variance = m2 / (stats->n_values - 1);
+	else
+		stats->variance = m2 / stats->n_values;
 	stats->mean_variance_valid = true;
 }
 
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index c45c819..d2c1cc7 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -38,12 +38,14 @@ typedef struct {
 
 	/*< private >*/
 	unsigned int capacity;
+	unsigned int is_population  : 1;
 	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_set_population(igt_stats_t *stats, bool full_population);
 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);
diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index f76d334..59097c8 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -89,6 +89,7 @@ static void test_std_deviation(void)
 	double mean, variance, std_deviation;
 
 	igt_stats_init(&stats, 8);
+	igt_stats_set_population(&stats, true);
 
 	igt_stats_push(&stats, 2);
 	igt_stats_push(&stats, 4);
diff --git a/tools/skl_compute_wrpll.c b/tools/skl_compute_wrpll.c
index cf808c7..8b6fcd3 100644
--- a/tools/skl_compute_wrpll.c
+++ b/tools/skl_compute_wrpll.c
@@ -867,6 +867,7 @@ static void test_run(struct test_ops *test)
 	igt_stats_t stats;
 
 	igt_stats_init(&stats, ARRAY_SIZE(modes));
+	igt_stats_set_population(&stats, true);
 
 	for (m = 0; m < ARRAY_SIZE(modes); m++) {
 		struct skl_wrpll_params params = {};
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 06/18] stats: Add a getter for the population property

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c       | 14 ++++++++++++++
 lib/igt_stats.h       |  2 ++
 lib/tests/igt_stats.c | 14 ++++++++++++++
 3 files changed, 30 insertions(+)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index c7d5fbd..12cabba 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -91,6 +91,20 @@ void igt_stats_fini(igt_stats_t *stats)
 	free(stats->values);
 }
 
+
+/**
+ * igt_stats_is_population:
+ * @stats: An #igt_stats_t instance
+ *
+ * Returns: #true if @stats represents a population, #false if only a sample.
+ *
+ * See igt_stats_set_population() for more details.
+ */
+bool igt_stats_is_population(igt_stats_t *stats)
+{
+	return stats->is_population;
+}
+
 /**
  * igt_stats_set_population:
  * @stats: An #igt_stats_t instance
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index d2c1cc7..ebc28ca 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -26,6 +26,7 @@
 #define __IGT_STATS_H__
 
 #include <stdint.h>
+#include <stdbool.h>
 
 /**
  * igt_stats_t:
@@ -45,6 +46,7 @@ typedef struct {
 
 void igt_stats_init(igt_stats_t *stats, unsigned int capacity);
 void igt_stats_fini(igt_stats_t *stats);
+bool igt_stats_is_population(igt_stats_t *stats);
 void igt_stats_set_population(igt_stats_t *stats, bool full_population);
 void igt_stats_push(igt_stats_t *stats, uint64_t value);
 double igt_stats_get_mean(igt_stats_t *stats);
diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index 59097c8..5c5e86a 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -35,6 +35,19 @@ static void test_init_zero(void)
 	igt_assert(stats.mean == 0.);
 }
 
+static void test_init(void)
+{
+	igt_stats_t stats;
+
+	igt_stats_init(&stats, 2);
+
+	/*
+	 * Make sure we default to representing only a sample of a bigger
+	 * population.
+	 */
+	igt_assert(igt_stats_is_population(&stats) == false);
+}
+
 static void test_mean(void)
 {
 	igt_stats_t stats;
@@ -115,6 +128,7 @@ static void test_std_deviation(void)
 igt_simple_main
 {
 	test_init_zero();
+	test_init();
 	test_mean();
 	test_invalidate_mean();
 	test_std_deviation();
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 07/18] stats: Add a note about the standard deviation derived from unbiased variance

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 12cabba..bd05550 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -121,6 +121,11 @@ bool igt_stats_is_population(igt_stats_t *stats)
  * [Bessel's correction](https://en.wikipedia.org/wiki/Bessel%27s_correction)
  * to the variance.
  *
+ * Note that even if we manage to have an unbiased variance by multiplying
+ * a sample variance by the Bessel's correction, n/(n - 1), the standard
+ * deviation derived from the unbiased variance isn't itself unbiased.
+ * Statisticians talk about a "corrected" standard deviation.
+ *
  * When giving #true to this function, the data set in @stats is considered a
  * full population. It's considered a sample of a bigger population otherwise.
  *
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 08/18] stats: Factor out a fixture to initialize stats

[Damien Lespiau]

We're going to use this simple fixture once more, might as well make a
function instead of copy/pasting code.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/tests/igt_stats.c | 24 +++++++++++-------------
 1 file changed, 11 insertions(+), 13 deletions(-)

diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index 5c5e86a..6916f25 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -25,6 +25,15 @@
 #include "igt_core.h"
 #include "igt_stats.h"
 
+static void push_fixture_1(igt_stats_t *stats)
+{
+	igt_stats_push(stats, 2);
+	igt_stats_push(stats, 4);
+	igt_stats_push(stats, 6);
+	igt_stats_push(stats, 8);
+	igt_stats_push(stats, 10);
+}
+
 /* Make sure we zero igt_stats_t fields at init() time */
 static void test_init_zero(void)
 {
@@ -54,15 +63,9 @@ static void test_mean(void)
 	double mean;
 
 	igt_stats_init(&stats, 5);
-
-	igt_stats_push(&stats, 2);
-	igt_stats_push(&stats, 4);
-	igt_stats_push(&stats, 6);
-	igt_stats_push(&stats, 8);
-	igt_stats_push(&stats, 10);
+	push_fixture_1(&stats);
 
 	mean = igt_stats_get_mean(&stats);
-
 	igt_assert(mean == (2 + 4 + 6 + 8 + 10) / 5.);
 
 	igt_stats_fini(&stats);
@@ -74,12 +77,7 @@ static void test_invalidate_mean(void)
 	double mean1, mean2;
 
 	igt_stats_init(&stats, 6);
-
-	igt_stats_push(&stats, 2);
-	igt_stats_push(&stats, 4);
-	igt_stats_push(&stats, 6);
-	igt_stats_push(&stats, 8);
-	igt_stats_push(&stats, 10);
+	push_fixture_1(&stats);
 
 	mean1 = igt_stats_get_mean(&stats);
 	igt_assert(mean1 == (2 + 4 + 6 + 8 + 10) / 5.);
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 09/18] stats: Add functions to retrieve min/max values of the dataset

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c       | 33 +++++++++++++++++++++++++++++++++
 lib/igt_stats.h       |  3 +++
 lib/tests/igt_stats.c | 12 ++++++++++++
 3 files changed, 48 insertions(+)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index bd05550..477d204 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -28,6 +28,8 @@
 #include "igt_core.h"
 #include "igt_stats.h"
 
+#define U64_MAX         ((uint64_t)~0ULL)
+
 /**
  * SECTION:igt_stats
  * @short_description: Tools for statistical analysis
@@ -78,6 +80,9 @@ void igt_stats_init(igt_stats_t *stats, unsigned int capacity)
 	stats->values = calloc(capacity, sizeof(*stats->values));
 	igt_assert(stats->values);
 	stats->capacity = capacity;
+
+	stats->min = U64_MAX;
+	stats->max = 0;
 }
 
 /**
@@ -151,7 +156,35 @@ 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;
+
+	if (value < stats->min)
+		stats->min = value;
+	if (value > stats->max)
+		stats->max = value;
+}
+
+/**
+ * igt_stats_get_min:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the minimal value in @stats
+ */
+uint64_t igt_stats_get_min(igt_stats_t *stats)
+{
+	return stats->min;
+}
+
+/**
+ * igt_stats_get_max:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the maximum value in @stats
+ */
+uint64_t igt_stats_get_max(igt_stats_t *stats)
+{
+	return stats->max;
 }
 
 /*
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index ebc28ca..145b77b 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -41,6 +41,7 @@ typedef struct {
 	unsigned int capacity;
 	unsigned int is_population  : 1;
 	unsigned int mean_variance_valid : 1;
+	uint64_t min, max;
 	double mean, variance;
 } igt_stats_t;
 
@@ -49,6 +50,8 @@ void igt_stats_fini(igt_stats_t *stats);
 bool igt_stats_is_population(igt_stats_t *stats);
 void igt_stats_set_population(igt_stats_t *stats, bool full_population);
 void igt_stats_push(igt_stats_t *stats, uint64_t value);
+uint64_t igt_stats_get_min(igt_stats_t *stats);
+uint64_t igt_stats_get_max(igt_stats_t *stats);
 double igt_stats_get_mean(igt_stats_t *stats);
 double igt_stats_get_variance(igt_stats_t *stats);
 double igt_stats_get_std_deviation(igt_stats_t *stats);
diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index 6916f25..dc5fe39 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -57,6 +57,17 @@ static void test_init(void)
 	igt_assert(igt_stats_is_population(&stats) == false);
 }
 
+static void test_min_max(void)
+{
+	igt_stats_t stats;
+
+	igt_stats_init(&stats, 5);
+	push_fixture_1(&stats);
+
+	igt_assert(igt_stats_get_min(&stats) == 2);
+	igt_assert(igt_stats_get_max(&stats) == 10);
+}
+
 static void test_mean(void)
 {
 	igt_stats_t stats;
@@ -127,6 +138,7 @@ igt_simple_main
 {
 	test_init_zero();
 	test_init();
+	test_min_max();
 	test_mean();
 	test_invalidate_mean();
 	test_std_deviation();
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 10/18] stats: Add igt_stats_get_range()

[Damien Lespiau]

Somewhat useful, for instance to size an histogram.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c       | 16 ++++++++++++++++
 lib/igt_stats.h       |  1 +
 lib/tests/igt_stats.c | 11 +++++++++++
 3 files changed, 28 insertions(+)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 477d204..26e4fbf 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -187,6 +187,22 @@ uint64_t igt_stats_get_max(igt_stats_t *stats)
 	return stats->max;
 }
 
+/**
+ * igt_stats_get_range:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the range of the values in @stats. The range is the difference
+ * between the highest and the lowest value.
+ *
+ * The range can be a deceiving characterization of the values, because there
+ * can be extreme minimal and maximum values that are just anomalies. Prefer
+ * the interquatile range or an histogram.
+ */
+uint64_t igt_stats_get_range(igt_stats_t *stats)
+{
+	return igt_stats_get_max(stats) - igt_stats_get_min(stats);
+}
+
 /*
  * Algorithm popularised by Knuth in:
  *
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index 145b77b..65e5a02 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -52,6 +52,7 @@ void igt_stats_set_population(igt_stats_t *stats, bool full_population);
 void igt_stats_push(igt_stats_t *stats, uint64_t value);
 uint64_t igt_stats_get_min(igt_stats_t *stats);
 uint64_t igt_stats_get_max(igt_stats_t *stats);
+uint64_t igt_stats_get_range(igt_stats_t *stats);
 double igt_stats_get_mean(igt_stats_t *stats);
 double igt_stats_get_variance(igt_stats_t *stats);
 double igt_stats_get_std_deviation(igt_stats_t *stats);
diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index dc5fe39..f09c079 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -68,6 +68,16 @@ static void test_min_max(void)
 	igt_assert(igt_stats_get_max(&stats) == 10);
 }
 
+static void test_range(void)
+{
+	igt_stats_t stats;
+
+	igt_stats_init(&stats, 5);
+	push_fixture_1(&stats);
+
+	igt_assert(igt_stats_get_range(&stats) == 8);
+}
+
 static void test_mean(void)
 {
 	igt_stats_t stats;
@@ -139,6 +149,7 @@ igt_simple_main
 	test_init_zero();
 	test_init();
 	test_min_max();
+	test_range();
 	test_mean();
 	test_invalidate_mean();
 	test_std_deviation();
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 11/18] docs: Fix a "libraray" typo

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/intel_mmio.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/intel_mmio.c b/lib/intel_mmio.c
index 45e9171..76b5e70 100644
--- a/lib/intel_mmio.c
+++ b/lib/intel_mmio.c
@@ -48,7 +48,7 @@
 
 /**
  * SECTION:intel_io
- * @short_description: Register access and sideband I/O libraray
+ * @short_description: Register access and sideband I/O library
  * @title: I/O
  * @include: intel_io.h
  *
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 12/18] docs: Add documentation for igt_assert_u32()

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_core.h | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/lib/igt_core.h b/lib/igt_core.h
index d79f6d2..f5c7194 100644
--- a/lib/igt_core.h
+++ b/lib/igt_core.h
@@ -367,6 +367,14 @@ void igt_exit(void) __attribute__((noreturn));
  * of simply printing the stringified expression.
  */
 #define igt_assert_eq(n1, n2) igt_assert_cmpint(n1, ==, !=, n2)
+
+/**
+ * igt_assert_eq_u32:
+ * @n1: first integer
+ * @n2: second integer
+ *
+ * Like igt_assert_eq(), but for uint32_t.
+ */
 #define igt_assert_eq_u32(n1, n2) igt_assert_cmpuint(n1, ==, !=, n2)
 
 /**
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 13/18] docs: Add documentation for igt_assert_cmpuint()

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_core.h | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/lib/igt_core.h b/lib/igt_core.h
index f5c7194..583a761 100644
--- a/lib/igt_core.h
+++ b/lib/igt_core.h
@@ -346,6 +346,15 @@ void igt_exit(void) __attribute__((noreturn));
 				  "error: %d " #ncmp " %d\n", __n1, __n2); \
 	} while (0)
 
+/**
+ * igt_assert_cmpuint:
+ * @n1: first value
+ * @cmp: compare operator
+ * @ncmp: negated version of @cmp
+ * @n2: second value
+ *
+ * Like igt_assert_cmpint(), but for unsigned ints;
+ */
 #define igt_assert_cmpuint(n1, cmp, ncmp, n2) \
 	do { \
 		uint32_t __n1 = (n1), __n2 = (n2); \
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 14/18] lib: Add double versions of igt_assert_cmp() and igt_assert_eq()

[Damien Lespiau]

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_core.h | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/lib/igt_core.h b/lib/igt_core.h
index 583a761..2b2b6e9 100644
--- a/lib/igt_core.h
+++ b/lib/igt_core.h
@@ -365,6 +365,24 @@ void igt_exit(void) __attribute__((noreturn));
 	} while (0)
 
 /**
+ * igt_assert_cmpdouble:
+ * @n1: first value
+ * @cmp: compare operator
+ * @ncmp: negated version of @cmp
+ * @n2: second value
+ *
+ * Like igt_assert_cmpint(), but for doubles;
+ */
+#define igt_assert_cmpdouble(n1, cmp, ncmp, n2) \
+	do { \
+		double __n1 = (n1), __n2 = (n2); \
+		if (__n1 cmp __n2) ; else \
+		__igt_fail_assert(IGT_LOG_DOMAIN, __FILE__, __LINE__, __func__, \
+				  #n1 " " #cmp " " #n2, \
+				  "error: %#lf " #ncmp " %#lf\n", __n1, __n2); \
+	} while (0)
+
+/**
  * igt_assert_eq:
  * @n1: first integer
  * @n2: second integer
@@ -387,6 +405,15 @@ void igt_exit(void) __attribute__((noreturn));
 #define igt_assert_eq_u32(n1, n2) igt_assert_cmpuint(n1, ==, !=, n2)
 
 /**
+ * igt_assert_eq_double:
+ * @n1: first double
+ * @n2: second double
+ *
+ * Like igt_assert_eq(), but for doubles.
+ */
+#define igt_assert_eq_double(n1, n2) igt_assert_cmpdouble(n1, ==, !=, n2)
+
+/**
  * igt_assert_neq:
  * @n1: first integer
  * @n2: second integer
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 15/18] stats: Use igt_assert_eq_double() when asserting on doubles

[Damien Lespiau]

Lucky enough to have exact values, == works!

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/tests/igt_stats.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index f09c079..468bba2 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -41,7 +41,7 @@ static void test_init_zero(void)
 
 	stats.mean = 1.;
 	igt_stats_init(&stats, 2);
-	igt_assert(stats.mean == 0.);
+	igt_assert_eq_double(stats.mean, 0.);
 }
 
 static void test_init(void)
@@ -87,7 +87,7 @@ static void test_mean(void)
 	push_fixture_1(&stats);
 
 	mean = igt_stats_get_mean(&stats);
-	igt_assert(mean == (2 + 4 + 6 + 8 + 10) / 5.);
+	igt_assert_eq_double(mean, (2 + 4 + 6 + 8 + 10) / 5.);
 
 	igt_stats_fini(&stats);
 }
@@ -101,7 +101,7 @@ static void test_invalidate_mean(void)
 	push_fixture_1(&stats);
 
 	mean1 = igt_stats_get_mean(&stats);
-	igt_assert(mean1 == (2 + 4 + 6 + 8 + 10) / 5.);
+	igt_assert_eq_double(mean1, (2 + 4 + 6 + 8 + 10) / 5.);
 
 	igt_stats_push(&stats, 100);
 
@@ -133,13 +133,13 @@ static void test_std_deviation(void)
 	igt_stats_push(&stats, 9);
 
 	mean = igt_stats_get_mean(&stats);
-	igt_assert(mean == (2 + 3 * 4 + 2 * 5 + 7 + 9) / 8.);
+	igt_assert_eq_double(mean, (2 + 3 * 4 + 2 * 5 + 7 + 9) / 8.);
 
 	variance = igt_stats_get_variance(&stats);
-	igt_assert(variance == 4);
+	igt_assert_eq_double(variance, 4);
 
 	std_deviation = igt_stats_get_std_deviation(&stats);
-	igt_assert(std_deviation == 2);
+	igt_assert_eq_double(std_deviation, 2);
 
 	igt_stats_fini(&stats);
 }
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 16/18] stats: Add a bulk version of _push()

[Damien Lespiau]

In case we want to push a bunch of values in one go.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c | 17 +++++++++++++++++
 lib/igt_stats.h |  2 ++
 2 files changed, 19 insertions(+)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 26e4fbf..5c1f23f 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -166,6 +166,23 @@ void igt_stats_push(igt_stats_t *stats, uint64_t value)
 }
 
 /**
+ * igt_stats_push_array:
+ * @stats: An #igt_stats_t instance
+ * @values: (array length=n_values): A pointer to an array of data points
+ * @n_values: The number of data points to add
+ *
+ * Adds an array of values to the @stats dataset.
+ */
+void igt_stats_push_array(igt_stats_t *stats,
+			  const uint64_t *values, unsigned int n_values)
+{
+	unsigned int i;
+
+	for (i = 0; i < n_values; i++)
+		igt_stats_push(stats, values[i]);
+}
+
+/**
  * igt_stats_get_min:
  * @stats: An #igt_stats_t instance
  *
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index 65e5a02..46437c4 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -50,6 +50,8 @@ void igt_stats_fini(igt_stats_t *stats);
 bool igt_stats_is_population(igt_stats_t *stats);
 void igt_stats_set_population(igt_stats_t *stats, bool full_population);
 void igt_stats_push(igt_stats_t *stats, uint64_t value);
+void igt_stats_push_array(igt_stats_t *stats,
+			  const uint64_t *values, unsigned int n_values);
 uint64_t igt_stats_get_min(igt_stats_t *stats);
 uint64_t igt_stats_get_max(igt_stats_t *stats);
 uint64_t igt_stats_get_range(igt_stats_t *stats);
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 17/18] stats: Add support for quartiles (and thus median)

[Damien Lespiau]

More stuff, quite useful characteristics of a dataset.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c       | 131 ++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/igt_stats.h       |   5 ++
 lib/tests/igt_stats.c |  41 ++++++++++++++++
 3 files changed, 177 insertions(+)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 5c1f23f..66fd563 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -23,6 +23,7 @@
  */
 
 #include <math.h>
+#include <stdlib.h>
 #include <string.h>
 
 #include "igt_core.h"
@@ -94,6 +95,7 @@ void igt_stats_init(igt_stats_t *stats, unsigned int capacity)
 void igt_stats_fini(igt_stats_t *stats)
 {
 	free(stats->values);
+	free(stats->sorted);
 }
 
 
@@ -158,6 +160,7 @@ void igt_stats_push(igt_stats_t *stats, uint64_t value)
 	stats->values[stats->n_values++] = value;
 
 	stats->mean_variance_valid = false;
+	stats->sorted_array_valid = false;
 
 	if (value < stats->min)
 		stats->min = value;
@@ -220,6 +223,134 @@ uint64_t igt_stats_get_range(igt_stats_t *stats)
 	return igt_stats_get_max(stats) - igt_stats_get_min(stats);
 }
 
+static int cmp_u64(const void *pa, const void *pb)
+{
+	const uint64_t *a = pa, *b = pb;
+
+	if (*a < *b)
+		return -1;
+	if (*a > *b)
+		return 1;
+	return 0;
+}
+
+static void igt_stats_ensure_sorted_values(igt_stats_t *stats)
+{
+	if (stats->sorted_array_valid)
+		return;
+
+	if (!stats->sorted) {
+		stats->sorted = calloc(stats->capacity, sizeof(*stats->values));
+		igt_assert(stats->sorted);
+	}
+
+	memcpy(stats->sorted, stats->values,
+	       sizeof(*stats->values) * stats->n_values);
+
+	qsort(stats->sorted, stats->n_values, sizeof(*stats->values), cmp_u64);
+
+	stats->sorted_array_valid = true;
+}
+
+/*
+ * We use Tukey's hinge for our quartiles determination.
+ * ends (end, lower_end) are exclusive.
+ */
+static double
+igt_stats_get_median_internal(igt_stats_t *stats,
+			      unsigned int start, unsigned int end,
+			      unsigned int *lower_end /* out */,
+			      unsigned int *upper_start /* out */)
+{
+	unsigned int mid, n_values = end - start;
+	double median;
+
+	igt_stats_ensure_sorted_values(stats);
+
+	/* odd number of data points */
+	if (n_values % 2 == 1) {
+		/* median is the value in the middle (actual datum) */
+		mid = start + n_values / 2;
+		median = stats->sorted[mid];
+
+		/* the two halves contain the median value */
+		if (lower_end)
+			*lower_end = mid + 1;
+		if (upper_start)
+			*upper_start = mid;
+
+	/* even number of data points */
+	} else {
+		/*
+		 * The middle is in between two indexes, 'mid' points at the
+		 * lower one. The median is then the average between those two
+		 * values.
+		 */
+		mid = start + n_values / 2 - 1;
+		median = (stats->sorted[mid] + stats->sorted[mid + 1]) / 2.;
+
+		if (lower_end)
+			*lower_end = mid + 1;
+		if (upper_start)
+			*upper_start = mid + 1;
+	}
+
+	return median;
+}
+
+/**
+ * igt_stats_get_quartiles:
+ * @stats: An #igt_stats_t instance
+ * @q1: (out): lower or 25th quartile
+ * @q2: (out): median or 50th quartile
+ * @q3: (out): upper or 75th quartile
+ *
+ * Retrieves the [quartiles](https://en.wikipedia.org/wiki/Quartile) of the
+ * @stats dataset.
+ */
+void igt_stats_get_quartiles(igt_stats_t *stats,
+			     double *q1, double *q2, double *q3)
+{
+	unsigned int lower_end, upper_start;
+	double ret;
+
+	if (stats->n_values < 3) {
+		if (q1)
+			*q1 = 0.;
+		if (q2)
+			*q2 = 0.;
+		if (q3)
+			*q3 = 0.;
+		return;
+	}
+
+	ret = igt_stats_get_median_internal(stats, 0, stats->n_values,
+					    &lower_end, &upper_start);
+	if (q2)
+		*q2 = ret;
+
+	ret = igt_stats_get_median_internal(stats, 0, lower_end, NULL, NULL);
+	if (q1)
+		*q1 = ret;
+
+	ret = igt_stats_get_median_internal(stats, upper_start, stats->n_values,
+					    NULL, NULL);
+	if (q3)
+		*q3 = ret;
+}
+
+/**
+ * igt_stats_get_median:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the median of the @stats dataset.
+ */
+double igt_stats_get_median(igt_stats_t *stats)
+{
+	return igt_stats_get_median_internal(stats, 0, stats->n_values,
+					     NULL, NULL);
+}
+
 /*
  * Algorithm popularised by Knuth in:
  *
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index 46437c4..887fa79 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -41,8 +41,10 @@ typedef struct {
 	unsigned int capacity;
 	unsigned int is_population  : 1;
 	unsigned int mean_variance_valid : 1;
+	unsigned int sorted_array_valid : 1;
 	uint64_t min, max;
 	double mean, variance;
+	uint64_t *sorted;
 } igt_stats_t;
 
 void igt_stats_init(igt_stats_t *stats, unsigned int capacity);
@@ -55,7 +57,10 @@ void igt_stats_push_array(igt_stats_t *stats,
 uint64_t igt_stats_get_min(igt_stats_t *stats);
 uint64_t igt_stats_get_max(igt_stats_t *stats);
 uint64_t igt_stats_get_range(igt_stats_t *stats);
+void igt_stats_get_quartiles(igt_stats_t *stats,
+			     double *q1, double *q2, double *q3);
 double igt_stats_get_mean(igt_stats_t *stats);
+double igt_stats_get_median(igt_stats_t *stats);
 double igt_stats_get_variance(igt_stats_t *stats);
 double igt_stats_get_std_deviation(igt_stats_t *stats);
 
diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index 468bba2..c4c6776 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -25,6 +25,8 @@
 #include "igt_core.h"
 #include "igt_stats.h"
 
+#define ARRAY_SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
+
 static void push_fixture_1(igt_stats_t *stats)
 {
 	igt_stats_push(stats, 2);
@@ -78,6 +80,44 @@ static void test_range(void)
 	igt_assert(igt_stats_get_range(&stats) == 8);
 }
 
+/*
+ * Examples taken from: https://en.wikipedia.org/wiki/Quartile
+ * The values are shifted a bit to test we do indeed start by sorting data
+ * set.
+ */
+static void test_quartiles(void)
+{
+	static const uint64_t s1[] =
+		{ 47, 49, 6, 7, 15, 36, 39, 40, 41, 42, 43 };
+	static const uint64_t s2[] = { 40, 41, 7, 15, 36, 39 };
+	igt_stats_t stats;
+	double q1, q2, q3;
+
+	/* s1, odd number of data points */
+	igt_stats_init(&stats, ARRAY_SIZE(s1));
+	igt_stats_push_array(&stats, s1, ARRAY_SIZE(s1));
+
+	igt_stats_get_quartiles(&stats, &q1, &q2, &q3);
+	igt_assert_eq_double(q1, 25.5);
+	igt_assert_eq_double(q2, 40);
+	igt_assert_eq_double(q3, 42.5);
+	igt_assert_eq_double(igt_stats_get_median(&stats), 40);
+
+	igt_stats_fini(&stats);
+
+	/* s1, even number of data points */
+	igt_stats_init(&stats, ARRAY_SIZE(s2));
+	igt_stats_push_array(&stats, s2, ARRAY_SIZE(s2));
+
+	igt_stats_get_quartiles(&stats, &q1, &q2, &q3);
+	igt_assert_eq_double(q1, 15);
+	igt_assert_eq_double(q2, 37.5);
+	igt_assert_eq_double(q3, 40);
+	igt_assert_eq_double(igt_stats_get_median(&stats), 37.5);
+
+	igt_stats_fini(&stats);
+}
+
 static void test_mean(void)
 {
 	igt_stats_t stats;
@@ -150,6 +190,7 @@ igt_simple_main
 	test_init();
 	test_min_max();
 	test_range();
+	test_quartiles();
 	test_mean();
 	test_invalidate_mean();
 	test_std_deviation();
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

Re: [PATCH i-g-t 17/18] stats: Add support for quartiles (and thus median)

[Chris Wilson]

On Sat, Jun 27, 2015 at 04:08:15PM +0100, Damien Lespiau wrote:
> More stuff, quite useful characteristics of a dataset.
> 
> Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
> ---
>  lib/igt_stats.c       | 131 ++++++++++++++++++++++++++++++++++++++++++++++++++
>  lib/igt_stats.h       |   5 ++
>  lib/tests/igt_stats.c |  41 ++++++++++++++++
>  3 files changed, 177 insertions(+)
> 
> diff --git a/lib/igt_stats.c b/lib/igt_stats.c
> index 5c1f23f..66fd563 100644
> --- a/lib/igt_stats.c
> +++ b/lib/igt_stats.c
> @@ -23,6 +23,7 @@
>   */
>  
>  #include <math.h>
> +#include <stdlib.h>
>  #include <string.h>
>  
>  #include "igt_core.h"
> @@ -94,6 +95,7 @@ void igt_stats_init(igt_stats_t *stats, unsigned int capacity)
>  void igt_stats_fini(igt_stats_t *stats)
>  {
>  	free(stats->values);
> +	free(stats->sorted);
>  }
>  
>  
> @@ -158,6 +160,7 @@ void igt_stats_push(igt_stats_t *stats, uint64_t value)
>  	stats->values[stats->n_values++] = value;
>  
>  	stats->mean_variance_valid = false;
> +	stats->sorted_array_valid = false;
>  
>  	if (value < stats->min)
>  		stats->min = value;
> @@ -220,6 +223,134 @@ uint64_t igt_stats_get_range(igt_stats_t *stats)
>  	return igt_stats_get_max(stats) - igt_stats_get_min(stats);
>  }
>  
> +static int cmp_u64(const void *pa, const void *pb)
> +{
> +	const uint64_t *a = pa, *b = pb;
> +
> +	if (*a < *b)
> +		return -1;
> +	if (*a > *b)
> +		return 1;
> +	return 0;
> +}
> +
> +static void igt_stats_ensure_sorted_values(igt_stats_t *stats)
> +{
> +	if (stats->sorted_array_valid)
> +		return;
> +
> +	if (!stats->sorted) {
> +		stats->sorted = calloc(stats->capacity, sizeof(*stats->values));
> +		igt_assert(stats->sorted);
> +	}

Since sorted_array_valid = false on igt_stats_push, but we only allocate
for the first call to sort, there's no safeguard against

  igt_stats_push();
  igt_stats_get_median();
  igt_stats_push();
  igt_stats_get_median();

exploding.
-Chris
> +
> +	memcpy(stats->sorted, stats->values,
> +	       sizeof(*stats->values) * stats->n_values);
> +
> +	qsort(stats->sorted, stats->n_values, sizeof(*stats->values), cmp_u64);
> +
> +	stats->sorted_array_valid = true;
> +}
> +
> +/*
> + * We use Tukey's hinge for our quartiles determination.
> + * ends (end, lower_end) are exclusive.
> + */
> +static double
> +igt_stats_get_median_internal(igt_stats_t *stats,
> +			      unsigned int start, unsigned int end,
> +			      unsigned int *lower_end /* out */,
> +			      unsigned int *upper_start /* out */)
> +{
> +	unsigned int mid, n_values = end - start;
> +	double median;
> +
> +	igt_stats_ensure_sorted_values(stats);
> +
> +	/* odd number of data points */
> +	if (n_values % 2 == 1) {
> +		/* median is the value in the middle (actual datum) */
> +		mid = start + n_values / 2;
> +		median = stats->sorted[mid];
> +
> +		/* the two halves contain the median value */
> +		if (lower_end)
> +			*lower_end = mid + 1;
> +		if (upper_start)
> +			*upper_start = mid;
> +
> +	/* even number of data points */
> +	} else {
> +		/*
> +		 * The middle is in between two indexes, 'mid' points at the
> +		 * lower one. The median is then the average between those two
> +		 * values.
> +		 */
> +		mid = start + n_values / 2 - 1;
> +		median = (stats->sorted[mid] + stats->sorted[mid + 1]) / 2.;
> +
> +		if (lower_end)
> +			*lower_end = mid + 1;
> +		if (upper_start)
> +			*upper_start = mid + 1;
> +	}
> +
> +	return median;
> +}
> +
> +/**
> + * igt_stats_get_quartiles:
> + * @stats: An #igt_stats_t instance
> + * @q1: (out): lower or 25th quartile
> + * @q2: (out): median or 50th quartile
> + * @q3: (out): upper or 75th quartile
> + *
> + * Retrieves the [quartiles](https://en.wikipedia.org/wiki/Quartile) of the
> + * @stats dataset.
> + */
> +void igt_stats_get_quartiles(igt_stats_t *stats,
> +			     double *q1, double *q2, double *q3)
> +{
> +	unsigned int lower_end, upper_start;
> +	double ret;
> +
> +	if (stats->n_values < 3) {
> +		if (q1)
> +			*q1 = 0.;
> +		if (q2)
> +			*q2 = 0.;
> +		if (q3)
> +			*q3 = 0.;
> +		return;
> +	}
> +
> +	ret = igt_stats_get_median_internal(stats, 0, stats->n_values,
> +					    &lower_end, &upper_start);
> +	if (q2)
> +		*q2 = ret;
> +
> +	ret = igt_stats_get_median_internal(stats, 0, lower_end, NULL, NULL);
> +	if (q1)
> +		*q1 = ret;
> +
> +	ret = igt_stats_get_median_internal(stats, upper_start, stats->n_values,
> +					    NULL, NULL);
> +	if (q3)
> +		*q3 = ret;

That's neat, I like that determination of the quartiles a lot.
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

Re: [PATCH i-g-t 17/18] stats: Add support for quartiles (and thus median)

[Damien Lespiau]

On Sat, Jun 27, 2015 at 04:15:41PM +0100, Chris Wilson wrote:
> > +static void igt_stats_ensure_sorted_values(igt_stats_t *stats)
> > +{
> > +	if (stats->sorted_array_valid)
> > +		return;
> > +
> > +	if (!stats->sorted) {
> > +		stats->sorted = calloc(stats->capacity, sizeof(*stats->values));
> > +		igt_assert(stats->sorted);
> > +	}
> 
> Since sorted_array_valid = false on igt_stats_push, but we only allocate
> for the first call to sort, there's no safeguard against
> 
>   igt_stats_push();
>   igt_stats_get_median();
>   igt_stats_push();
>   igt_stats_get_median();
> 
> exploding.

I believe it's fine (and I just sent a test telling the same story, but
well, overflowing an small heap allocated array can often be "fine" with
an overallocation from malloc() rounding up the size to git in a bin),
as the size of the dataset is an invariant (I didn't implement your
suggestion to grow the array at push() time). We allocate the full
capacity here, not just the current n_values.

I did have a think about a growing ->values array, but I think we know
the number of data points we want upfront most of the time (if not
always) when going to do some measurements?

-- 
Damien
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

Re: [PATCH i-g-t 17/18] stats: Add support for quartiles (and thus median)

[Chris Wilson]

On Sat, Jun 27, 2015 at 04:52:56PM +0100, Damien Lespiau wrote:
> On Sat, Jun 27, 2015 at 04:15:41PM +0100, Chris Wilson wrote:
> > > +static void igt_stats_ensure_sorted_values(igt_stats_t *stats)
> > > +{
> > > +	if (stats->sorted_array_valid)
> > > +		return;
> > > +
> > > +	if (!stats->sorted) {
> > > +		stats->sorted = calloc(stats->capacity, sizeof(*stats->values));
> > > +		igt_assert(stats->sorted);
> > > +	}
> > 
> > Since sorted_array_valid = false on igt_stats_push, but we only allocate
> > for the first call to sort, there's no safeguard against
> > 
> >   igt_stats_push();
> >   igt_stats_get_median();
> >   igt_stats_push();
> >   igt_stats_get_median();
> > 
> > exploding.
> 
> I believe it's fine (and I just sent a test telling the same story, but
> well, overflowing an small heap allocated array can often be "fine" with
> an overallocation from malloc() rounding up the size to git in a bin),
> as the size of the dataset is an invariant (I didn't implement your
> suggestion to grow the array at push() time). We allocate the full
> capacity here, not just the current n_values.

Ah, didn't realise that the capacity was fixed.
 
> I did have a think about a growing ->values array, but I think we know
> the number of data points we want upfront most of the time (if not
> always) when going to do some measurements?

No, often times I want to run a benchmark for x seconds and then look at
the spread of samples.
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

Re: [PATCH i-g-t 17/18] stats: Add support for quartiles (and thus median)

[Damien Lespiau]

On Sat, Jun 27, 2015 at 04:56:54PM +0100, Chris Wilson wrote:
> > I did have a think about a growing ->values array, but I think we know
> > the number of data points we want upfront most of the time (if not
> > always) when going to do some measurements?
> 
> No, often times I want to run a benchmark for x seconds and then look at
> the spread of samples.

Ah, fair enough, will make push() grow the array and corresponding
adjustments then.

-- 
Damien
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx

[PATCH i-g-t 18/18] stats: Add support for the interquartile range (IQR)

[Damien Lespiau]

IQR is a good measure of dispersion.

Signed-off-by: Damien Lespiau <damien.lespiau@intel.com>
---
 lib/igt_stats.c       | 18 +++++++++++++++++-
 lib/igt_stats.h       |  1 +
 lib/tests/igt_stats.c |  2 ++
 3 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/lib/igt_stats.c b/lib/igt_stats.c
index 66fd563..caf3f37 100644
--- a/lib/igt_stats.c
+++ b/lib/igt_stats.c
@@ -216,7 +216,7 @@ uint64_t igt_stats_get_max(igt_stats_t *stats)
  *
  * The range can be a deceiving characterization of the values, because there
  * can be extreme minimal and maximum values that are just anomalies. Prefer
- * the interquatile range or an histogram.
+ * the interquatile range (see igt_stats_get_iqr()) or an histogram.
  */
 uint64_t igt_stats_get_range(igt_stats_t *stats)
 {
@@ -340,6 +340,22 @@ void igt_stats_get_quartiles(igt_stats_t *stats,
 }
 
 /**
+ * igt_stats_get_iqr:
+ * @stats: An #igt_stats_t instance
+ *
+ * Retrieves the
+ * [interquartile range](https://en.wikipedia.org/wiki/Interquartile_range)
+ * (IQR) of the @stats dataset.
+ */
+double igt_stats_get_iqr(igt_stats_t *stats)
+{
+	double q1, q3;
+
+	igt_stats_get_quartiles(stats, &q1, NULL, &q3);
+	return (q3 - q1);
+}
+
+/**
  * igt_stats_get_median:
  * @stats: An #igt_stats_t instance
  *
diff --git a/lib/igt_stats.h b/lib/igt_stats.h
index 887fa79..6ee3ae6 100644
--- a/lib/igt_stats.h
+++ b/lib/igt_stats.h
@@ -59,6 +59,7 @@ uint64_t igt_stats_get_max(igt_stats_t *stats);
 uint64_t igt_stats_get_range(igt_stats_t *stats);
 void igt_stats_get_quartiles(igt_stats_t *stats,
 			     double *q1, double *q2, double *q3);
+double igt_stats_get_iqr(igt_stats_t *stats);
 double igt_stats_get_mean(igt_stats_t *stats);
 double igt_stats_get_median(igt_stats_t *stats);
 double igt_stats_get_variance(igt_stats_t *stats);
diff --git a/lib/tests/igt_stats.c b/lib/tests/igt_stats.c
index c4c6776..c0649f3 100644
--- a/lib/tests/igt_stats.c
+++ b/lib/tests/igt_stats.c
@@ -102,6 +102,7 @@ static void test_quartiles(void)
 	igt_assert_eq_double(q2, 40);
 	igt_assert_eq_double(q3, 42.5);
 	igt_assert_eq_double(igt_stats_get_median(&stats), 40);
+	igt_assert_eq_double(igt_stats_get_iqr(&stats), 42.5 - 25.5);
 
 	igt_stats_fini(&stats);
 
@@ -114,6 +115,7 @@ static void test_quartiles(void)
 	igt_assert_eq_double(q2, 37.5);
 	igt_assert_eq_double(q3, 40);
 	igt_assert_eq_double(igt_stats_get_median(&stats), 37.5);
+	igt_assert_eq_double(igt_stats_get_iqr(&stats), 40 - 15);
 
 	igt_stats_fini(&stats);
 }
-- 
2.1.0

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/intel-gfx