perf/cairo-stats.c

   1 /*
   2  * Copyright © 2006 Red Hat, Inc.
   3  *
   4  * Permission to use, copy, modify, distribute, and sell this software
   5  * and its documentation for any purpose is hereby granted without
   6  * fee, provided that the above copyright notice appear in all copies
   7  * and that both that copyright notice and this permission notice
   8  * appear in supporting documentation, and that the name of
   9  * the authors not be used in advertising or publicity pertaining to
  10  * distribution of the software without specific, written prior
  11  * permission. The authors make no representations about the
  12  * suitability of this software for any purpose.  It is provided "as
  13  * is" without express or implied warranty.
  14  *
  15  * THE AUTHORS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
  16  * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17  * FITNESS, IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY SPECIAL,
  18  * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
  19  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
  20  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
  21  * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22  *
  23  * Authors: Carl Worth <cworth@cworth.org>
  24  */
  25
  26 #include "cairo-stats.h"
  27
  28 #include <assert.h>
  29
  30 void
  31 _cairo_stats_compute (cairo_stats_t *stats,
  32                       cairo_time_t  *values,
  33                       int            num_values)
  34 {
  35     cairo_time_t sum, mean, q1, q3, iqr;
  36     cairo_time_t outlier_min, outlier_max;
  37     int i, min_valid, num_valid;
  38     double s;
  39
  40     assert (num_values > 0);
  41
  42     if (num_values == 1) {
  43         stats->min_ticks = stats->median_ticks = values[0];
  44         stats->std_dev = 0;
  45         stats->iterations = 1;
  46         return;
  47     }
  48
  49     /* First, identify any outliers, using the definition of "mild
  50      * outliers" from:
  51      *
  52      *          http://en.wikipedia.org/wiki/Outliers
  53      *
  54      * Which is that outliers are any values less than Q1 - 1.5 * IQR
  55      * or greater than Q3 + 1.5 * IQR where Q1 and Q3 are the first
  56      * and third quartiles and IQR is the inter-quartile range (Q3 -
  57      * Q1).
  58      */
  59     qsort (values, num_values, sizeof (cairo_time_t), _cairo_time_cmp);
  60
  61     q1 = values[1*num_values/4];
  62     q3 = values[3*num_values/4];
  63
  64     /* XXX assumes we have native uint64_t */
  65     iqr = q3 - q1;
  66     outlier_min = q1 - 3 * iqr / 2;
  67     outlier_max = q3 + 3 * iqr / 2;
  68
  69     for (i = 0; i < num_values && values[i] < outlier_min; i++)
  70         ;
  71     min_valid = i;
  72
  73     for (i = 0; i < num_values && values[i] <= outlier_max; i++)
  74         ;
  75     num_valid = i - min_valid;
  76     assert(num_valid);
  77
  78     stats->iterations = num_valid;
  79     stats->min_ticks = values[min_valid];
  80     stats->median_ticks = values[min_valid + num_valid / 2];
  81
  82     sum = 0;
  83     for (i = min_valid; i < min_valid + num_valid; i++)
  84         sum = _cairo_time_add (sum, values[i]);
  85     mean = sum / num_valid;
  86
  87     /* Let's use a normalized std. deviation for easier comparison. */
  88     s = 0;
  89     for (i = min_valid; i < min_valid + num_valid; i++) {
  90         double delta = (values[i] - mean) / (double)mean;
  91         s += delta * delta;
  92     }
  93     stats->std_dev = sqrt(s / num_valid);
  94 }