cairo/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 static int
  29 _cairo_perf_ticks_cmp (const void *_a, const void *_b)
  30 {
  31     const cairo_perf_ticks_t *a = _a;
  32     const cairo_perf_ticks_t *b = _b;
  33
  34     if (*a > *b)
  35         return 1;
  36     if (*a < *b)
  37         return -1;
  38     return 0;
  39 }
  40
  41 void
  42 _cairo_stats_compute (cairo_stats_t             *stats,
  43                       cairo_perf_ticks_t        *values,
  44                       int                        num_values)
  45 {
  46     int i;
  47     double sum, mean, delta, q1, q3, iqr;
  48     double outlier_min, outlier_max;
  49     int min_valid, num_valid;
  50
  51     /* First, identify any outliers, using the definition of "mild
  52      * outliers" from:
  53      *
  54      *          http://en.wikipedia.org/wiki/Outliers
  55      *
  56      * Which is that outliers are any values less than Q1 - 1.5 * IQR
  57      * or greater than Q3 + 1.5 * IQR where Q1 and Q3 are the first
  58      * and third quartiles and IQR is the inter-quartile range (Q3 -
  59      * Q1).
  60      */
  61     qsort (values, num_values,
  62            sizeof (cairo_perf_ticks_t), _cairo_perf_ticks_cmp);
  63
  64     q1          = values[(1*num_values)/4];
  65     q3          = values[(3*num_values)/4];
  66
  67     iqr = q3 - q1;
  68
  69     outlier_min = q1 - 1.5 * iqr;
  70     outlier_max = q3 + 1.5 * iqr;
  71
  72     min_valid = 0;
  73     while (min_valid < num_values && values[min_valid] < outlier_min)
  74         min_valid++;
  75
  76     i = min_valid;
  77     num_valid = 0;
  78     while (i + num_valid < num_values && values[i+num_valid] <= outlier_max)
  79         num_valid++;
  80
  81     stats->iterations = num_valid;
  82     stats->min_ticks = values[min_valid];
  83
  84     sum = 0.0;
  85     for (i = min_valid; i < min_valid + num_valid; i++) {
  86         sum += values[i];
  87         if (values[i] < stats->min_ticks)
  88             stats->min_ticks = values[i];
  89     }
  90
  91     mean = sum / num_valid;
  92     stats->median_ticks = values[min_valid + num_valid / 2];
  93
  94     sum = 0.0;
  95     for (i = min_valid; i < min_valid + num_valid; i++) {
  96         delta = values[i] - mean;
  97         sum += delta * delta;
  98     }
  99
 100     /* Let's use a std. deviation normalized to the mean for easier
 101      * comparison. */
 102     stats->std_dev = sqrt(sum / num_valid) / mean;
 103 }