[Intel-gfx] [PATCH i-g-t 1/4] lib: Add a tiny utility function to compute averages

[Chris Wilson]

On Thu, Jun 25, 2015 at 04:21:40PM +0100, Damien Lespiau wrote:
> The master plan would be to get a bit more stats in it, at least the
> standard deviation and confidence interval. Just need the average for
> now.

Definitely, I wouldn't even print the average without the std.dev and
how normal the distribution is. (Otherwise the information can be very
misleading.) Without them, I'd rather have the median than the mean.

> +void igt_stats_push(igt_stats_t *stats, uint64_t value)
> +{
> +	igt_assert(stats->n_values < stats->capacity);

Might as well make this a realloced array from the start.

> +	stats->values[stats->n_values++] = value;
> +}
> +
> +double igt_stats_get_average(igt_stats_t *stats)
> +{
> +	unsigned int i;
> +	double a = 0.0;
> +
> +	for (i = 0; i < stats->n_values; i++)
> +		a += (double)stats->values[i] / stats->n_values;

For fun, we could write numerically more stable versions. Welcome to the
bikeshed.

static double kahan_summation(igt_stats_t *stats)
{
	double sum = 0;
	double error = 0;
	unsigned i;

	for (i = 0; i < stats->n_values; i++) {
		double x = stats->values[i] - error;
		double tmp = sum + x;
		error = (tmp - sum) - x;
		sum = tmp;
	}

	return sum;
}

double igt_stats_get_average(igt_stats_t *stats)
{
	return kahan_summation(stats) / stats->n_values;
}

or

static knuth_avergae(igt_stats_t *stats)
{
	double mean = 0;
	unsigned i;

	for (i = 0; i < stats->n_values; i++)
		mean += (stats->values[i] - mean) / (i + 1);

	return mean;
}

double igt_stats_get_average(igt_stats_t *stats)
{
	return knuth_average(stats);
}

or if we are sorting to get the median anyway, doing a pairwise
summation would also reduce the numerical errors...
-Chris

-- 
Chris Wilson, Intel Open Source Technology Centre