From patchwork Thu Jun 25 23:26:57 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Lespiau, Damien" X-Patchwork-Id: 6677891 Return-Path: X-Original-To: patchwork-intel-gfx@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork1.web.kernel.org (Postfix) with ESMTP id F0ED49F40A for ; Thu, 25 Jun 2015 23:27:23 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 1D74420702 for ; Thu, 25 Jun 2015 23:27:23 +0000 (UTC) Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) by mail.kernel.org (Postfix) with ESMTP id 3874620703 for ; Thu, 25 Jun 2015 23:27:19 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 93E2B4A034; Thu, 25 Jun 2015 16:27:18 -0700 (PDT) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mga02.intel.com (mga02.intel.com [134.134.136.20]) by gabe.freedesktop.org (Postfix) with ESMTP id 4B7494A034 for ; Thu, 25 Jun 2015 16:27:17 -0700 (PDT) Received: from orsmga003.jf.intel.com ([10.7.209.27]) by orsmga101.jf.intel.com with ESMTP; 25 Jun 2015 16:27:17 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,680,1427785200"; d="scan'208";a="594940230" Received: from mpaszkie-mobl1.ger.corp.intel.com (HELO strange.ger.corp.intel.com) ([10.252.33.58]) by orsmga003.jf.intel.com with ESMTP; 25 Jun 2015 16:27:06 -0700 From: Damien Lespiau To: intel-gfx@lists.freedesktop.org Date: Fri, 26 Jun 2015 00:26:57 +0100 Message-Id: <1435274819-2777-3-git-send-email-damien.lespiau@intel.com> X-Mailer: git-send-email 2.1.0 In-Reply-To: <1435274819-2777-1-git-send-email-damien.lespiau@intel.com> References: <1435274819-2777-1-git-send-email-damien.lespiau@intel.com> Subject: [Intel-gfx] [PATCH i-g-t 3/5] stats: Use an algorithm popularised by Knuth to compute mean and variance X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: intel-gfx-bounces@lists.freedesktop.org Sender: "Intel-gfx" X-Spam-Status: No, score=-5.6 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Suggested-by: Chris Wilson Signed-off-by: Damien Lespiau --- lib/igt_stats.c | 42 +++++++++++++++++++++++++++++++++++++----- lib/igt_stats.h | 3 +++ 2 files changed, 40 insertions(+), 5 deletions(-) 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);