Skip to contentSkip to conversation

Make igt_stats_t able to grow dynamically

PATCH In review Damien Lespiau 2 participants 6 messages Jun 27, 2015 Library code

lore
Share & tools
lore
#0 lore raw

Turns out, we don't always know how many data points we'll have upfront: Chris wants to take as many measurements for 5 secs and store them in igt_stats_t.

That makes the overall API easier to use as well, so all is good in the world again.

Signature · 6 lines
Damien

_______________________________________________
Intel-gfx mailing list
[email protected]
http://lists.freedesktop.org/mailman/listinfo/intel-gfx
#1 lore raw

PATCH 1/3 stats: Allow the underlying arrays to grow at will

Chris mentioned he wanted to be able to measure a variable "for one second" and use igt_stats to store them. That's one case where we don't know the number of data points upfront.

We should really support that, so here it is.

---
 lib/igt_stats.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 48 insertions(+), 4 deletions(-)
lib/igt_stats.c +48 -4
index caf3f37..cd97ab0 100644
@@ -63,6 +63,41 @@
  * ]|
  */
 
+static unsigned int get_new_capacity(int need)
+{
+	unsigned int new_capacity;
+
+	/* taken from Python's list */
+	new_capacity = (need >> 6) + (need < 9 ? 3 : 6);
+	new_capacity += need;
+
+	return new_capacity;
+}
+
+static void igt_stats_ensure_capacity(igt_stats_t *stats,
+				      unsigned int n_additional_values)
+{
+	unsigned int new_n_values = stats->n_values + n_additional_values;
+	unsigned int new_capacity;
+
+	if (new_n_values <= stats->capacity)
+		return;
+
+	new_capacity = get_new_capacity(new_n_values);
+	stats->values = realloc(stats->values,
+				sizeof(*stats->values) * new_capacity);
+	igt_assert(stats->values);
+
+	stats->capacity = new_capacity;
+
+	if (!stats->sorted)
+		return;
+
+	stats->sorted = realloc(stats->sorted,
+				sizeof(*stats->values) * new_capacity);
+	igt_assert(stats->sorted);
+}
+
 /**
  * igt_stats_init:
  * @stats: An #igt_stats_t instance
@@ -78,9 +113,7 @@ 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;
+	igt_stats_ensure_capacity(stats, capacity);
 
 	stats->min = U64_MAX;
 	stats->max = 0;
@@ -156,7 +189,8 @@ void igt_stats_set_population(igt_stats_t *stats, bool full_population)
  */
 void igt_stats_push(igt_stats_t *stats, uint64_t value)
 {
-	igt_assert(stats->n_values < stats->capacity);
+	igt_stats_ensure_capacity(stats, 1);
+
 	stats->values[stats->n_values++] = value;
 
 	stats->mean_variance_valid = false;
@@ -181,6 +215,8 @@ void igt_stats_push_array(igt_stats_t *stats,
 {
 	unsigned int i;
 
+	igt_stats_ensure_capacity(stats, n_values);
+
 	for (i = 0; i < n_values; i++)
 		igt_stats_push(stats, values[i]);
 }
@@ -240,6 +276,14 @@ static void igt_stats_ensure_sorted_values(igt_stats_t *stats)
 		return;
 
 	if (!stats->sorted) {
+		/*
+		 * We could always allocate sorted, but doing it lazily will
+		 * consume a bit less memory if the user doesn't use any of the
+		 * functions needing to sort the data points.
+		 *
+		 * igt_stats_ensure_capacity() will take care of reallocating
+		 * sorted when needed after this initial allocation.
+		 */
 		stats->sorted = calloc(stats->capacity, sizeof(*stats->values));
 		igt_assert(stats->sorted);
 	}
Signature · 6 lines
2.1.0

_______________________________________________
Intel-gfx mailing list
[email protected]
http://lists.freedesktop.org/mailman/listinfo/intel-gfx
#2 lore raw

Re: [PATCH i-g-t 1/3] stats: Allow the underlying arrays to grow at will

Quoted 42 lines · Damien Lespiau

Chris mentioned he wanted to be able to measure a variable "for one second" and use igt_stats to store them. That's one case where we don't know the number of data points upfront.

We should really support that, so here it is.

---
 lib/igt_stats.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 48 insertions(+), 4 deletions(-)
lib/igt_stats.c +23 -0
index caf3f37..cd97ab0 100644
@@ -63,6 +63,41 @@
  * ]|
  */
 
+static unsigned int get_new_capacity(int need)
+{
+	unsigned int new_capacity;
+
+	/* taken from Python's list */
+	new_capacity = (need >> 6) + (need < 9 ? 3 : 6);
+	new_capacity += need;
+
+	return new_capacity;
+}
+
+static void igt_stats_ensure_capacity(igt_stats_t *stats,
+				      unsigned int n_additional_values)
+{
+	unsigned int new_n_values = stats->n_values + n_additional_values;
+	unsigned int new_capacity;
+
+	if (new_n_values <= stats->capacity)
+		return;
+
+	new_capacity = get_new_capacity(new_n_values);
+	stats->values = realloc(stats->values,
+				sizeof(*stats->values) * new_capacity);

lib/igt_stats.c line 98

Quoted 10 lines
lib/igt_stats.c +10 -0
+	igt_assert(stats->values);
+
+	stats->capacity = new_capacity;
+
+	if (!stats->sorted)
+		return;
+
+	stats->sorted = realloc(stats->sorted,
+				sizeof(*stats->values) * new_capacity);
+	igt_assert(stats->sorted);

There isn't any point in preserving the sorted array when pushing new values. Might as well just free here and allocate again when required. -Chris

Signature · 5 lines
Chris Wilson, Intel Open Source Technology Centre
_______________________________________________
Intel-gfx mailing list
[email protected]
http://lists.freedesktop.org/mailman/listinfo/intel-gfx
#3 lore raw

Re: [PATCH i-g-t 1/3] stats: Allow the underlying arrays to grow at will

Quoted 17 lines · Chris Wilson
Quoted 17 lines
lib/igt_stats.c +17 -0
+static void igt_stats_ensure_capacity(igt_stats_t *stats,
+				      unsigned int n_additional_values)
+{
+	unsigned int new_n_values = stats->n_values + n_additional_values;
+	unsigned int new_capacity;
+
+	if (new_n_values <= stats->capacity)
+		return;
+
+	new_capacity = get_new_capacity(new_n_values);
+	stats->values = realloc(stats->values,
+				sizeof(*stats->values) * new_capacity);
+	igt_assert(stats->values);
+
+	stats->capacity = new_capacity;
+
+	if (!stats->sorted)
Quoted 8 lines

lib/igt_stats.c line 98

Quoted 5 lines
lib/igt_stats.c +5 -0
+		return;
+
+	stats->sorted = realloc(stats->sorted,
+				sizeof(*stats->values) * new_capacity);
+	igt_assert(stats->sorted);

There isn't any point in preserving the sorted array when pushing new values. Might as well just free here and allocate again when required.

Indeed, push the whole thing so far with this change.

Signature · 5 lines
Damien
_______________________________________________
Intel-gfx mailing list
[email protected]
http://lists.freedesktop.org/mailman/listinfo/intel-gfx
#4 lore raw

PATCH 2/3 stats: Spwan igt_init_with_size() from igt_init()

In reply to Damien Lespiau

It's all about good looking APIs.

---
 lib/igt_stats.c           | 27 ++++++++++++++++++++++-----
 lib/igt_stats.h           |  3 ++-
 lib/tests/igt_stats.c     | 20 ++++++++++----------
 tools/skl_compute_wrpll.c |  2 +-
 4 files changed, 35 insertions(+), 17 deletions(-)
lib/igt_stats.c +22 -5
index cd97ab0..6b867e3 100644
@@ -101,15 +101,32 @@ static void igt_stats_ensure_capacity(igt_stats_t *stats,
 /**
  * igt_stats_init:
  * @stats: An #igt_stats_t instance
+ *
+ * Initializes an #igt_stats_t instance. igt_stats_fini() must be called once
+ * finished with @stats.
+ */
+void igt_stats_init(igt_stats_t *stats)
+{
+	memset(stats, 0, sizeof(*stats));
+
+	igt_stats_ensure_capacity(stats, 128);
+
+	stats->min = U64_MAX;
+	stats->max = 0;
+}
+
+/**
+ * igt_stats_init_with_size:
+ * @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.
+ * Like igt_stats_init() but with a size to avoid reallocating the underlying
+ * array(s) when pushing new values. Useful if we have a good idea of the
+ * number of data points we want @stats to hold.
  *
- * We currently assume the user knows how many data samples upfront and there's
- * no need to grow the array of values.
+ * igt_stats_fini() must be called once finished with @stats.
  */
-void igt_stats_init(igt_stats_t *stats, unsigned int capacity)
+void igt_stats_init_with_size(igt_stats_t *stats, unsigned int capacity)
 {
 	memset(stats, 0, sizeof(*stats));
 
lib/igt_stats.h +2 -1
index 6ee3ae6..dd04097 100644
@@ -47,7 +47,8 @@ typedef struct {
 	uint64_t *sorted;
 } igt_stats_t;
 
-void igt_stats_init(igt_stats_t *stats, unsigned int capacity);
+void igt_stats_init(igt_stats_t *stats);
+void igt_stats_init_with_size(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);
lib/tests/igt_stats.c +10 -10
index dfdc507..6e4b233 100644
@@ -42,7 +42,7 @@ static void test_init_zero(void)
 	igt_stats_t stats;
 
 	stats.mean = 1.;
-	igt_stats_init(&stats, 2);
+	igt_stats_init(&stats);
 	igt_assert_eq_double(stats.mean, 0.);
 }
 
@@ -50,7 +50,7 @@ static void test_init(void)
 {
 	igt_stats_t stats;
 
-	igt_stats_init(&stats, 2);
+	igt_stats_init(&stats);
 
 	/*
 	 * Make sure we default to representing only a sample of a bigger
@@ -63,7 +63,7 @@ static void test_min_max(void)
 {
 	igt_stats_t stats;
 
-	igt_stats_init(&stats, 5);
+	igt_stats_init(&stats);
 	push_fixture_1(&stats);
 
 	igt_assert(igt_stats_get_min(&stats) == 2);
@@ -74,7 +74,7 @@ static void test_range(void)
 {
 	igt_stats_t stats;
 
-	igt_stats_init(&stats, 5);
+	igt_stats_init(&stats);
 	push_fixture_1(&stats);
 
 	igt_assert(igt_stats_get_range(&stats) == 8);
@@ -94,7 +94,7 @@ static void test_quartiles(void)
 	double q1, q2, q3;
 
 	/* s1, odd number of data points */
-	igt_stats_init(&stats, ARRAY_SIZE(s1));
+	igt_stats_init(&stats);
 	igt_stats_push_array(&stats, s1, ARRAY_SIZE(s1));
 
 	igt_stats_get_quartiles(&stats, &q1, &q2, &q3);
@@ -107,7 +107,7 @@ static void test_quartiles(void)
 	igt_stats_fini(&stats);
 
 	/* s1, even number of data points */
-	igt_stats_init(&stats, ARRAY_SIZE(s2));
+	igt_stats_init(&stats);
 	igt_stats_push_array(&stats, s2, ARRAY_SIZE(s2));
 
 	igt_stats_get_quartiles(&stats, &q1, &q2, &q3);
@@ -127,7 +127,7 @@ static void test_invalidate_sorted(void)
 		{ 47, 49, 6, 7, 15, 36, 39, 40, 41, 42};
 	double median1, median2;
 
-	igt_stats_init(&stats, ARRAY_SIZE(s1_truncated) + 1);
+	igt_stats_init(&stats);
 	igt_stats_push_array(&stats, s1_truncated, ARRAY_SIZE(s1_truncated));
 	median1 = igt_stats_get_median(&stats);
 
@@ -143,7 +143,7 @@ static void test_mean(void)
 	igt_stats_t stats;
 	double mean;
 
-	igt_stats_init(&stats, 5);
+	igt_stats_init(&stats);
 	push_fixture_1(&stats);
 
 	mean = igt_stats_get_mean(&stats);
@@ -157,7 +157,7 @@ static void test_invalidate_mean(void)
 	igt_stats_t stats;
 	double mean1, mean2;
 
-	igt_stats_init(&stats, 6);
+	igt_stats_init(&stats);
 	push_fixture_1(&stats);
 
 	mean1 = igt_stats_get_mean(&stats);
@@ -180,7 +180,7 @@ static void test_std_deviation(void)
 	igt_stats_t stats;
 	double mean, variance, std_deviation;
 
-	igt_stats_init(&stats, 8);
+	igt_stats_init(&stats);
 	igt_stats_set_population(&stats, true);
 
 	igt_stats_push(&stats, 2);
tools/skl_compute_wrpll.c +1 -1
index 8b6fcd3..0e5965c 100644
@@ -866,7 +866,7 @@ static void test_run(struct test_ops *test)
 	unsigned p_odd_even[2] = { 0, 0 };
 	igt_stats_t stats;
 
-	igt_stats_init(&stats, ARRAY_SIZE(modes));
+	igt_stats_init_with_size(&stats, ARRAY_SIZE(modes));
 	igt_stats_set_population(&stats, true);
 
 	for (m = 0; m < ARRAY_SIZE(modes); m++) {
Signature · 6 lines
2.1.0

_______________________________________________
Intel-gfx mailing list
[email protected]
http://lists.freedesktop.org/mailman/listinfo/intel-gfx
#5 lore raw

PATCH 3/3 stats: Exercise the reallocation paths

In reply to Damien Lespiau
---
 lib/tests/igt_stats.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
lib/tests/igt_stats.c +24 -0
index 6e4b233..12778e2 100644
@@ -204,6 +204,29 @@ static void test_std_deviation(void)
 	igt_stats_fini(&stats);
 }
 
+static void test_reallocation(void)
+{
+	igt_stats_t stats;
+	unsigned int i;
+
+	igt_stats_init_with_size(&stats, 1);
+
+	for (i = 0; i < 101; i++) {
+		igt_stats_push(&stats, i);
+		/* also triggers ->sorted reallocations */
+		if (i > 10)
+			igt_stats_get_median(&stats);
+	}
+
+	igt_assert_eq(stats.n_values, 101);
+	for (i = 0; i < 101; i++)
+		igt_assert_eq(stats.values[i], i);
+	igt_assert_eq_double(igt_stats_get_mean(&stats), 50.0);
+	igt_assert_eq_double(igt_stats_get_median(&stats), 50.0);
+
+	igt_stats_fini(&stats);
+}
+
 igt_simple_main
 {
 	test_init_zero();
@@ -215,4 +238,5 @@ igt_simple_main
 	test_mean();
 	test_invalidate_mean();
 	test_std_deviation();
+	test_reallocation();
 }
Signature · 6 lines
2.1.0

_______________________________________________
Intel-gfx mailing list
[email protected]
http://lists.freedesktop.org/mailman/listinfo/intel-gfx