[cairo-commit] 3 commits - perf/cairo-perf.c perf/cairo-perf-diff perf/cairo-perf-diff-files.c perf/cairo-perf.h perf/Makefile.am perf/pattern_create_radial.c

Carl Worth cworth at kemper.freedesktop.org
Thu Nov 2 12:21:44 PST 2006


 perf/Makefile.am             |    1 
 perf/cairo-perf-diff         |   22 ++-------
 perf/cairo-perf-diff-files.c |   43 ++++++++----------
 perf/cairo-perf.c            |   93 ++++++++++++++++++++++++++++++++--------
 perf/cairo-perf.h            |    1 
 perf/pattern_create_radial.c |   98 +++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 201 insertions(+), 57 deletions(-)

New commits:
diff-tree b717e987776d60cbc37434f7c918ad438e29b1a4 (from d2d0d11bdefa012d65364b24477bb86c8475ca86)
Author: Carl Worth <cworth at cworth.org>
Date:   Thu Nov 2 12:21:26 2006 -0800

    cairo-perf: Change outlier elimination and report minimum times.
    
    Instead of just discarding the worst 15% of the results, we now
    do IQR-based detection and elimination of outliers. Also, instead
    of reporting mean times we now report minimum and median times.
    We still do compute the mean and standard deviation for the
    detection of when results seem stable for early bailout. And we
    do still report the standard deviation.
    
    A statistician might complain that it looks funny to report the
    median and the standard deviation together, (instead of median
    and average absolute deviation from the median, say), but I liked
    the standard deviation since it is always larger, so it might
    ensure better separatation if we use it to determine when two
    sets of results are sufficiently different to be interesting.

diff --git a/perf/cairo-perf-diff-files.c b/perf/cairo-perf-diff-files.c
index eb2ef9f..8dbe49b 100644
--- a/perf/cairo-perf-diff-files.c
+++ b/perf/cairo-perf-diff-files.c
@@ -44,8 +44,9 @@ typedef struct _test_report {
     char *content;
     char *name;
     int size;
-    double ticks;
-    double time;
+    double min_ticks;
+    double min_time;
+    double median_time;
     double std_dev;
     int iterations;
 } test_report_t;
@@ -150,11 +151,15 @@ test_report_parse (test_report_t *report
 
     skip_space ();
 
-    parse_double (report->ticks);
+    parse_double (report->min_ticks);
 
     skip_space ();
 
-    parse_double (report->time);
+    parse_double (report->min_time);
+
+    skip_space ();
+
+    parse_double (report->median_time);
 
     skip_space ();
 
@@ -330,7 +335,6 @@ cairo_perf_report_diff (cairo_perf_repor
 {
     int i, i_old, i_new;
     test_report_t *o, *n;
-    double o_min, o_max, n_min, n_max;
     int cmp;
     test_diff_t *diff, *diffs;
     int num_diffs = 0;
@@ -363,22 +367,10 @@ cairo_perf_report_diff (cairo_perf_repor
 	    continue;
 	}
 
-	/* Discard as uninteresting a change which doesn't separate
-	 * the means by a few standard deviations in each direction,
-	 * (that is, require the bulk of each curve to be
-	 * non-overlapping). */
-	o_min = o->ticks * (1 - 3 * o->std_dev);
-	o_max = o->ticks * (1 + 3 * o->std_dev);
-	n_min = n->ticks * (1 - 3 * n->std_dev);
-	n_max = n->ticks * (1 + 3 * n->std_dev);
-	if (n_min > o_max ||
-	    n_max < o_min)
-	{
-	    diffs[num_diffs].old = o;
-	    diffs[num_diffs].new = n;
-	    diffs[num_diffs].speedup = o->ticks / n->ticks;
-	    num_diffs++;
-	}
+	diffs[num_diffs].old = o;
+	diffs[num_diffs].new = n;
+	diffs[num_diffs].speedup = o->min_ticks / n->min_ticks;
+	num_diffs++;
 
 	i_old++;
 	i_new++;
@@ -408,6 +400,11 @@ cairo_perf_report_diff (cairo_perf_repor
 	if (change - 1.0 < min_change)
 	    continue;
 
+	/* Also discard as uninteresting if the change is less than
+	 * the sum each of the standard deviations. */
+	if (change - 1.0 < diff->old->std_dev + diff->new->std_dev)
+	    continue;
+
 	if (diff->speedup > 1.0 && ! printed_speedup) {
 	    printf ("Speedups\n"
 		    "========\n");
@@ -422,8 +419,8 @@ cairo_perf_report_diff (cairo_perf_repor
 	printf ("%5s-%-4s %26s-%-3d  %6.2f %4.2f%% -> %6.2f %4.2f%%: %5.2fx ",
 		diff->old->backend, diff->old->content,
 		diff->old->name, diff->old->size,
-		diff->old->time, diff->old->std_dev * 100,
-		diff->new->time, diff->new->std_dev * 100,
+		diff->old->min_time, diff->old->std_dev * 100,
+		diff->new->min_time, diff->new->std_dev * 100,
 		change);
 
 	if (diff->speedup > 1.0)
diff --git a/perf/cairo-perf.c b/perf/cairo-perf.c
index 0707433..412ce82 100644
--- a/perf/cairo-perf.c
+++ b/perf/cairo-perf.c
@@ -32,6 +32,8 @@
 #define CAIRO_PERF_LOW_STD_DEV		0.03
 #define CAIRO_PERF_STABLE_STD_DEV_COUNT	5
 
+#define CAIRO_STATS_MIN_VALID_SAMPLES	20
+
 typedef struct _cairo_perf_case {
     CAIRO_PERF_DECL (*run);
     unsigned int min_size;
@@ -94,6 +96,8 @@ _content_to_string (cairo_content_t cont
 
 typedef struct _stats
 {
+    double min;
+    double median;
     double mean;
     double std_dev;
 } stats_t;
@@ -111,27 +115,76 @@ compare_cairo_perf_ticks (const void *_a
     return 0;
 }
 
-static void
+typedef enum {
+    CAIRO_STATS_STATUS_SUCCESS,
+    CAIRO_STATS_STATUS_NEED_MORE_DATA
+} cairo_stats_status_t;
+
+static cairo_stats_status_t
 _compute_stats (cairo_perf_ticks_t *values, int num_values, stats_t *stats)
 {
     int i;
-    double sum, delta;
+    double sum, delta, q1, q3, iqr;
+    double outlier_min, outlier_max;
+    int min_valid, num_valid;
+
+    /* First, identify any outliers, using the definition of "mild
+     * outliers" from:
+     *
+     *		http://en.wikipedia.org/wiki/Outliers
+     *
+     * Which is that outliers are any values less than Q1 - 1.5 * IQR
+     * or greater than Q3 + 1.5 * IQR where Q1 and Q3 are the first
+     * and third quartiles and IQR is the inter-quartile range (Q3 -
+     * Q1).
+     */
+    qsort (values, num_values,
+	   sizeof (cairo_perf_ticks_t), compare_cairo_perf_ticks);
+
+    q1	 	= values[(1*num_values)/4];
+    stats->mean = values[(2*num_values)/4];
+    q3		= values[(3*num_values)/4];
+
+    iqr = q3 - q1;
+
+    outlier_min = q1 - 1.5 * iqr;
+    outlier_max = q3 + 1.5 * iqr;
+
+    min_valid = 0;
+    while (min_valid < num_values && values[min_valid] < outlier_min)
+	min_valid++;
+
+    i = min_valid;
+    num_valid = 0;
+    while (i + num_valid < num_values && values[i+num_valid] < outlier_max)
+	num_valid++;
+
+    if (num_valid < CAIRO_STATS_MIN_VALID_SAMPLES)
+	return CAIRO_STATS_STATUS_NEED_MORE_DATA;
+
+    stats->min = values[min_valid];
 
     sum = 0.0;
-    for (i = 0; i < num_values; i++)
+    for (i = min_valid; i < min_valid + num_valid; i++) {
 	sum += values[i];
+	if (values[i] < stats->min)
+	    stats->min = values[i];
+    }
 
-    stats->mean = sum / num_values;
+    stats->mean = sum / num_valid;
+    stats->median = values[min_valid + num_valid / 2];
 
     sum = 0.0;
-    for (i = 0; i <  num_values; i++) {
+    for (i = min_valid; i < num_valid; i++) {
 	delta = values[i] - stats->mean;
 	sum += delta * delta;
     }
 
     /* Let's use a std. deviation normalized to the mean for easier
      * comparison. */
-    stats->std_dev = sqrt(sum / num_values) / stats->mean;
+    stats->std_dev = sqrt(sum / num_valid) / stats->mean;
+
+    return CAIRO_STATS_STATUS_SUCCESS;
 }
 
 void
@@ -140,7 +193,7 @@ cairo_perf_run (cairo_perf_t		*perf,
 		cairo_perf_func_t	 perf_func)
 {
     static cairo_bool_t first_run = TRUE;
-
+    cairo_stats_status_t status;
     unsigned int i;
     cairo_perf_ticks_t *times;
     stats_t stats = {0.0, 0.0};
@@ -148,17 +201,19 @@ cairo_perf_run (cairo_perf_t		*perf,
 
     times = xmalloc (perf->iterations * sizeof (cairo_perf_ticks_t));
 
+    /* We run one iteration in advance to warm caches, etc. */
+    cairo_perf_yield ();
+    (perf_func) (perf->cr, perf->size, perf->size);
+
     low_std_dev_count = 0;
     for (i =0; i < perf->iterations; i++) {
 	cairo_perf_yield ();
 	times[i] = (perf_func) (perf->cr, perf->size, perf->size);
 
-	if (i > 0) {
-	    qsort (times, i+1,
-		   sizeof (cairo_perf_ticks_t), compare_cairo_perf_ticks);
-
-	    /* Assume the slowest 15% are outliers, and ignore */
-	    _compute_stats (times, .85 * (i+1), &stats);
+	if (i >= CAIRO_STATS_MIN_VALID_SAMPLES) {
+	    status = _compute_stats (times, i+1, &stats);
+	    if (status == CAIRO_STATS_STATUS_NEED_MORE_DATA)
+		continue;
 
 	    if (stats.std_dev <= CAIRO_PERF_LOW_STD_DEV) {
 		low_std_dev_count++;
@@ -171,8 +226,8 @@ cairo_perf_run (cairo_perf_t		*perf,
     }
 
     if (first_run) {
-	printf ("[ # ] %8s-%-4s %28s %10s %8s %5s %s\n",
-		"backend", "content", "test-size", "mean(ticks)", "mean(ms)",
+	printf ("[ # ] %8s-%-4s %28s %10s %8s %5s %5s %s\n",
+		"backend", "content", "test-size", "min(ticks)", "min(ms)", "median(ms)",
 		"stddev.", "iterations");
 	first_run = FALSE;
     }
@@ -182,9 +237,10 @@ cairo_perf_run (cairo_perf_t		*perf,
 	    _content_to_string (perf->target->content),
 	    name, perf->size);
 
-    printf ("%12.2f %#8.3f %#5.2f%% %3d\n",
-	    stats.mean,
-	    (stats.mean * 1000.0) / cairo_perf_ticks_per_second (),
+    printf ("%12.2f %#8.3f %#8.3f %#5.2f%% %3d\n",
+	    stats.min,
+	    (stats.min * 1000.0) / cairo_perf_ticks_per_second (),
+	    (stats.median * 1000.0) / cairo_perf_ticks_per_second (),
 	    stats.std_dev * 100.0, i);
 
     perf->test_number++;
diff-tree d2d0d11bdefa012d65364b24477bb86c8475ca86 (from a618fd2cf90575ac7695b614328f1123db86b372)
Author: Dan Amelang <dan at amelang.net>
Date:   Tue Oct 31 23:47:35 2006 -0800

    Add new perf test "pattern_create_radial"
    
    This test is really just for hammering the double to fixed-point conversion
    (in _cairo_fixed_from_double) that happens as doubles from API calls gets
    translated into internal cairo fixed-point numbers.

diff --git a/perf/Makefile.am b/perf/Makefile.am
index 419a998..e1cfdc7 100644
--- a/perf/Makefile.am
+++ b/perf/Makefile.am
@@ -21,6 +21,7 @@ cairo_perf_SOURCES =		\
 	stroke.c		\
 	subimage_copy.c		\
 	tessellate.c		\
+	pattern_create_radial.c \
 	text.c
 
 if CAIRO_HAS_WIN32_SURFACE
diff --git a/perf/cairo-perf.c b/perf/cairo-perf.c
index d9734c4..0707433 100644
--- a/perf/cairo-perf.c
+++ b/perf/cairo-perf.c
@@ -256,5 +256,6 @@ cairo_perf_case_t perf_cases[] = {
     { text,   64, 256},
     { tessellate, 100, 100},
     { subimage_copy, 16, 512},
+    { pattern_create_radial, 16, 16},
     { NULL }
 };
diff --git a/perf/cairo-perf.h b/perf/cairo-perf.h
index 560ba64..faacff9 100644
--- a/perf/cairo-perf.h
+++ b/perf/cairo-perf.h
@@ -88,5 +88,6 @@ CAIRO_PERF_DECL (stroke);
 CAIRO_PERF_DECL (subimage_copy);
 CAIRO_PERF_DECL (tessellate);
 CAIRO_PERF_DECL (text);
+CAIRO_PERF_DECL (pattern_create_radial);
 
 #endif
diff --git a/perf/pattern_create_radial.c b/perf/pattern_create_radial.c
new file mode 100644
index 0000000..09f15a8
--- /dev/null
+++ b/perf/pattern_create_radial.c
@@ -0,0 +1,98 @@
+/*
+ * Copyright © 2006 Dan Amelang
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of
+ * the authors not be used in advertising or publicity pertaining to
+ * distribution of the software without specific, written prior
+ * permission. The authors make no representations about the
+ * suitability of this software for any purpose.  It is provided "as
+ * is" without express or implied warranty.
+ *
+ * THE AUTHORS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS
+ * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+ * FITNESS, IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY SPECIAL,
+ * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
+ * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
+ * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Authors: Dan Amelang <dan at amelang.net>
+ *
+ * This test was originally created to test _cairo_fixed_from_double.
+ * cairo_pattern_create_radial was selected as the entry point into
+ * cairo as it makes several calls to _cairo_fixed_from_double and
+ * presents a somewhat realistic use-case (although the RADIALS_COUNT
+ * isn't very realistic).
+ */
+#include <time.h>
+#include "cairo-perf.h"
+
+#define RADIALS_COUNT (10000)
+
+static struct
+{
+    double cx0;
+    double cy0;
+    double radius0;
+    double cx1;
+    double cy1;
+    double radius1;
+} radials[RADIALS_COUNT];
+
+static double
+generate_double_in_range (double min, double max)
+{
+    double d;
+
+    d = rand () / (double) RAND_MAX;
+    d *= max - min;
+    d += min;
+
+    return d;
+}
+
+static cairo_perf_ticks_t
+do_pattern_create_radial (cairo_t *cr, int width, int height)
+{
+    int i;
+    cairo_pattern_t *pattern;
+
+    cairo_perf_timer_start ();
+
+    for (i = 0; i < RADIALS_COUNT; i++)
+    {
+        pattern = cairo_pattern_create_radial (radials[i].cx0, radials[i].cy0,
+                                               radials[i].radius0,
+                                               radials[i].cx1, radials[i].cy1,
+                                               radials[i].radius1);
+        cairo_pattern_destroy (pattern);
+    }
+
+    cairo_perf_timer_stop ();
+
+    return cairo_perf_timer_elapsed ();
+}
+
+void
+pattern_create_radial (cairo_perf_t *perf, cairo_t *cr, int width, int height)
+{
+    int i;
+
+    srand (time (0));
+    for (i = 0; i < RADIALS_COUNT; i++)
+    {
+        radials[i].cx0 = generate_double_in_range (-50000.0, 50000.0);
+        radials[i].cy0 = generate_double_in_range (-50000.0, 50000.0);
+        radials[i].radius0 = generate_double_in_range (0.0, 1000.0);
+        radials[i].cx1 = generate_double_in_range (-50000.0, 50000.0);
+        radials[i].cy1 = generate_double_in_range (-50000.0, 50000.0);
+        radials[i].radius1 = generate_double_in_range (0.0, 1000.0);
+    }
+
+    cairo_perf_run (perf, "pattern_create_radial",
+                          do_pattern_create_radial);
+}
diff-tree a618fd2cf90575ac7695b614328f1123db86b372 (from 504ea250f7c052525cf28536c767d4f9f57e7cc9)
Author: Carl Worth <cworth at cworth.org>
Date:   Fri Oct 27 00:51:24 2006 -0700

    cairo-perf-diff: Simplify git usage and just run cairo-perf that gets built with cairo revision
    
    Many thanks to Josh Triplett for help with theses fixes:
    
    1. Simplify the usage of git to eliminate the fragile and nasty
       stuff we were doing previously, (such as manually symlinking
       things under .git rather than just using git-clone -s).
    
    2. Don't try running latest cairo-perf with LD_LIBRARY_PATH
       pointing to built cairo version. Apparently stupid libtool
       and its use of rpath is foiling us here. Instead just run
       whatever cairo-perf gets built as part of the source that
       gets checked out.
    
    This second point means that cairo-perf-diff won't yet be useful
    for comparing the performance of old cairo revisions that pre-date
    cairo-perf. I've since been reasing and we might be able to use
    --disable-rpath to the configure script to get what we want.

diff --git a/perf/cairo-perf-diff b/perf/cairo-perf-diff
index 509a4e2..9864a31 100755
--- a/perf/cairo-perf-diff
+++ b/perf/cairo-perf-diff
@@ -43,7 +43,7 @@ git_setup() {
 
 rev2sha() {
     rev=$1
-    git rev-parse --verify $rev || ( echo "Cannot reolve $rev to a revision" && exit 1 )
+    git rev-parse --verify $rev || ( echo "Cannot resolve $rev to a revision" && exit 1 )
 }
 
 rev2perf() {
@@ -68,26 +68,16 @@ run_cairo_perf_if_not_cached() {
     fi
     cd $CAIRO_PERF_DIR
 
-    # XXX: OK, The symlink stuff here is really evil. What we really
-    # want is some sort of git-mirror as has been proposed before.
-
     if [ ! -d build ]; then
-	mkdir build
-	GIT_DIR=build/.git git init-db
-	rm -rf build/.git/objects
-	ln -s $GIT_DIR/objects build/.git/objects
-	rm -rf build/.git/refs
-	ln -s $GIT_DIR/refs build/.git/refs
-	cp $GIT_DIR/HEAD build/.git/HEAD
-	(cd build; git reset --hard; CFLAGS="-O2" ./autogen.sh)
+	git clone -s $CAIRO_DIR build
+	(cd build; git checkout -b tmp-cairo-perf-diff $sha; CFLAGS="-O2" ./autogen.sh)
     fi
     cd build
 
-    # XXX: This is painful too. Maybe using "git-branch -f" would be easier here
-    git checkout -b tmp-cairo-perf-diff $sha >/dev/null 2>&1 || (git checkout tmp-cairo-perf-diff && git reset --hard $sha)
-    git reset --hard
+    git checkout tmp-cairo-perf-diff
+    git reset --hard $sha
     make CFLAGS="-O2" || (rm config.cache && make CFLAGS="-O2")
-    LD_LIBRARY_PATH=$CAIRO_PERF_DIR/build/src/.libs $CAIRO_DIR/perf/.libs/cairo-perf > $perf
+    (make perf || echo "*** Performance test crashed") > $perf
     cd $owd
 }
 


More information about the cairo-commit mailing list