[gegl] perf: compute median instead of mean, and abort iteration when converged

[Øyvind Kolås <ok src gnome org>]

commit 6e8c2c02ee67b5d5e6ed3cd2e776a1f57de87ada
Author: Øyvind Kolås <pippin gimp org>
Date:   Tue Jan 9 01:34:03 2018 +0100

    perf: compute median instead of mean, and abort iteration when converged
    
    Stabler numbers much quicker than the global averaging used earlier.

 perf/Makefile-tests            |    2 +-
 perf/test-common.h             |   69 +++++++++++++++++++++++++++++++++++++--
 perf/test-gegl-buffer-access.c |   27 ++++++++++------
 perf/test-samplers.c           |   58 +++++++++++++++++++++++++---------
 4 files changed, 126 insertions(+), 30 deletions(-)
---
diff --git a/perf/Makefile-tests b/perf/Makefile-tests
index b02eafd..aa9b53e 100644
--- a/perf/Makefile-tests
+++ b/perf/Makefile-tests
@@ -1,5 +1,5 @@
 #CFILES = $(wildcard *.c)
-CFILES = test-rotate.c test-scale.c test-unsharpmask.c test-gegl-buffer-access.c
+CFILES = test-rotate.c test-scale.c test-unsharpmask.c test-samplers.c test-gegl-buffer-access.c
 bins   = $(subst ,,$(CFILES:.c=))
 
 all: $(bins)
diff --git a/perf/test-common.h b/perf/test-common.h
index 4eaa6eb..0328d51 100644
--- a/perf/test-common.h
+++ b/perf/test-common.h
@@ -3,6 +3,14 @@
 #include "gegl.h"
 #include "opencl/gegl-cl-init.h"
 
+#define ITERATIONS 200
+#define PERCENTILE 0.8  /* if we want to bias to the better results with
+                           more noise, increase this number towards 1.0,
+                           like 0.8 */
+#define BAIL_THRESHOLD 0.01
+#define BAIL_COUNT     10
+#define MIN_ITER       16
+
 static long ticks_start;
 
 typedef void (*t_run_perf)(GeglBuffer *buffer);
@@ -27,18 +35,70 @@ void bench(const gchar *id,
            GeglBuffer  *buffer,
            t_run_perf   test_func );
 
+
+int  converged = 0;
+long ticks_iter_start = 0;
+long iter_db[ITERATIONS];
+int iter_no = 0;
+
 void test_start (void)
 {
   ticks_start = babl_ticks ();
+  iter_no = 0;
+  converged = 0;
+}
+
+float prev_median = 0.0;
+
+static void test_start_iter (void)
+{
+  ticks_iter_start = babl_ticks ();
+  prev_median = -1.0;
+}
+
+
+static int compare_long (const void * a, const void * b)
+{
+  return ( *(long*)a - *(long*)b );
+}
+static float compute_median (void)
+{
+  qsort(iter_db,iter_no,sizeof(long),compare_long);
+  return iter_db[(int)(iter_no * (1.0-PERCENTILE))];
+}
+
+#include <math.h>
+#include <stdio.h>
+
+static void test_end_iter (void)
+{
+  long ticks = babl_ticks ()-ticks_iter_start;
+  float median;
+  iter_db[iter_no] = ticks;
+  iter_no++;
+
+  median = compute_median ();
+  if (iter_no > MIN_ITER && fabs(1.0-fabs(median - prev_median * 1.0)/median) < BAIL_THRESHOLD) /// median < 
0.05)
+   {
+     /* we've converged */
+     converged++;
+   }
+  else
+   {
+     converged = 0;
+   }
+  prev_median = median;
 }
 
 void test_end_suffix (const gchar *id,
                       const gchar *suffix,
                       gdouble      bytes)
 {
-  long ticks = babl_ticks ()-ticks_start;
+//  long ticks = babl_ticks ()-ticks_start;
   g_print ("@ %s%s: %.2f megabytes/second\n",
-       id, suffix, (bytes / 1024.0 / 1024.0)  / (ticks / 1000000.0));
+       id, suffix,
+        (bytes / 1024.0 / ITERATIONS/ 1024.0)  / (compute_median()/1000000.0));
+  //     (bytes / 1024.0 / 1024.0)  / (ticks / 1000000.0));
 }
 
 void test_end (const gchar *id,
@@ -87,11 +147,12 @@ void do_bench (const gchar *id,
   // warm up
   test_func(buffer);
 
-#define ITERATIONS 32
   test_start ();
-  for (int i=0; i<ITERATIONS; ++i)
+  for (int i=0; i<ITERATIONS && converged<4; ++i)
     {
+      test_start_iter();
       test_func(buffer);
+      test_end_iter();
     }
   test_end_suffix (id, suffix, ((double)gegl_buffer_get_pixel_count (buffer)) * 16 * ITERATIONS);
 #undef ITERATIONS
diff --git a/perf/test-gegl-buffer-access.c b/perf/test-gegl-buffer-access.c
index d4a5ebc..d6f4b10 100644
--- a/perf/test-gegl-buffer-access.c
+++ b/perf/test-gegl-buffer-access.c
@@ -1,6 +1,7 @@
 #include "test-common.h"
 
 #define BPP 16
+#define ITERATIONS 200
 
 gint
 main (gint    argc,
@@ -17,31 +18,31 @@ main (gint    argc,
   buffer = gegl_buffer_new (&bound, format);
   buf = g_malloc0 (bound.width * bound.height * BPP);
 
-#define ITERATIONS 64
-
   /* pre-initialize */
   gegl_buffer_set (buffer, &bound, 0, NULL, buf, GEGL_AUTO_ROWSTRIDE);
 
   test_start ();
-  for (i=0;i<ITERATIONS;i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
     {
+      test_start_iter ();
       gegl_buffer_get (buffer, &bound, 1.0, NULL, buf, GEGL_AUTO_ROWSTRIDE, GEGL_ABYSS_NONE);
+      test_end_iter ();
      }
   test_end ("gegl_buffer_get", 1.0 * bound.width * bound.height * ITERATIONS * BPP);
 
 
   test_start ();
-  for (i=0;i<ITERATIONS;i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
     {
+      test_start_iter ();
       gegl_buffer_set (buffer, &bound, 0, NULL, buf, GEGL_AUTO_ROWSTRIDE);
+      test_end_iter ();
      }
   test_end ("gegl_buffer_set", 1.0 * bound.width * bound.height * ITERATIONS * BPP);
 
 
   format = babl_format ("RGBA float");
 
-#undef ITERATIONS
-#define ITERATIONS 128
 
   {
 #define SAMPLES 150000
@@ -56,9 +57,10 @@ main (gint    argc,
   }
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
+    test_start_iter ();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
@@ -71,14 +73,16 @@ main (gint    argc,
       gegl_buffer_set_pixel (buffer, x, y, format, (void*)&px[0], 3);
 #endif
     }
+    test_end_iter ();
   }
   test_end ("gegl_buffer_set 1x1", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
+    test_start_iter ();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
@@ -87,21 +91,24 @@ main (gint    argc,
       gegl_buffer_get (buffer, &rect, 1.0, format, (void*)&px[0],
                        GEGL_AUTO_ROWSTRIDE, GEGL_ABYSS_NONE);
     }
+    test_end_iter ();
   }
   test_end ("gegl_buffer_get 1x1", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
+    test_start_iter ();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       gegl_buffer_sample (buffer, x, y, NULL, (void*)&px[0], format,
-                          GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE); 
+                          GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE);
     }
+    test_end_iter ();
   }
   test_end ("gegl_buffer_sample nearest", SAMPLES * ITERATIONS * BPP);
 
diff --git a/perf/test-samplers.c b/perf/test-samplers.c
index dc98da0..76fd96c 100644
--- a/perf/test-samplers.c
+++ b/perf/test-samplers.c
@@ -1,7 +1,7 @@
 #include "test-common.h"
 
 #define BPP 16
-#define ITERATIONS 12
+#define ITERATIONS 100
 
 gint
 main (gint    argc,
@@ -37,10 +37,11 @@ main (gint    argc,
   }
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
@@ -49,14 +50,16 @@ main (gint    argc,
       gegl_buffer_get (buffer, &rect, 1.0, format2, (void*)&px[0],
                        GEGL_AUTO_ROWSTRIDE, GEGL_ABYSS_NONE);
     }
+    test_end_iter();
   }
   test_end ("gegl_buffer_get 1x1 + babl", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
@@ -64,14 +67,16 @@ main (gint    argc,
       gegl_buffer_sample (buffer, x, y, NULL, (void*)&px[0], format,
                           GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE); 
     }
+    test_end_iter();
   }
   test_end ("gegl_buffer_sample nearest", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
@@ -79,16 +84,18 @@ main (gint    argc,
       gegl_buffer_sample (buffer, x, y, NULL, (void*)&px[0], format,
                           GEGL_SAMPLER_NEAREST, GEGL_ABYSS_NONE); 
     }
+    test_end_iter();
   }
   test_end ("gegl_buffer_sample near+ba", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
     GeglSampler *sampler = gegl_buffer_sampler_new (buffer, format,
                                                     GEGL_SAMPLER_NEAREST);
+    test_start_iter();
 
     for (j = 0; j < SAMPLES; j ++)
     {
@@ -97,12 +104,13 @@ main (gint    argc,
       gegl_sampler_get (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
 
+    test_end_iter();
     g_object_unref (sampler);
   }
   test_end ("gegl_sampler_get nearest", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
@@ -110,12 +118,14 @@ main (gint    argc,
                                                     GEGL_SAMPLER_NEAREST);
     GeglSamplerGetFun sampler_get_fun = gegl_sampler_get_fun (sampler);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       sampler_get_fun (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }
@@ -123,7 +133,7 @@ main (gint    argc,
 
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
@@ -131,12 +141,14 @@ main (gint    argc,
                                                     GEGL_SAMPLER_NEAREST);
     GeglSamplerGetFun sampler_get_fun = gegl_sampler_get_fun (sampler);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       sampler_get_fun (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }
@@ -144,10 +156,11 @@ main (gint    argc,
 
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
@@ -155,30 +168,33 @@ main (gint    argc,
       gegl_buffer_sample (buffer, x, y, NULL, (void*)&px[0], format,
                           GEGL_SAMPLER_LINEAR, GEGL_ABYSS_NONE); 
     }
+    test_end_iter();
   }
   test_end ("gegl_buffer_sample linear", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
     GeglSampler *sampler = gegl_buffer_sampler_new (buffer, format, 
                                                     GEGL_SAMPLER_LINEAR);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       gegl_sampler_get (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }
   test_end ("gegl_sampler_get linear", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
@@ -186,22 +202,25 @@ main (gint    argc,
                                                     GEGL_SAMPLER_LINEAR);
     GeglSamplerGetFun sampler_get_fun = gegl_sampler_get_fun (sampler);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       sampler_get_fun (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }
   test_end ("sampler_get_fun linear", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
@@ -209,30 +228,33 @@ main (gint    argc,
       gegl_buffer_sample (buffer, x, y, NULL, (void*)&px[0], format,
                           GEGL_SAMPLER_CUBIC, GEGL_ABYSS_NONE); 
     }
+    test_end_iter();
   }
   test_end ("gegl_buffer_sample cubic", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
     GeglSampler *sampler = gegl_buffer_sampler_new (buffer, format, 
                                                     GEGL_SAMPLER_CUBIC);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       gegl_sampler_get (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }
   test_end ("gegl_sampler_get cubic", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
@@ -240,50 +262,56 @@ main (gint    argc,
                                                     GEGL_SAMPLER_CUBIC);
     GeglSamplerGetFun sampler_get_fun = gegl_sampler_get_fun (sampler);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       sampler_get_fun (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }
   test_end ("sampler_get_fun cubic", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
     GeglSampler *sampler = gegl_buffer_sampler_new (buffer, format, 
                                                     GEGL_SAMPLER_NOHALO);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       gegl_sampler_get (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }
   test_end ("gegl_sampler_get nohalo", SAMPLES * ITERATIONS * BPP);
 
   test_start ();
-  for (i = 0; i < ITERATIONS; i++)
+  for (i=0;i<ITERATIONS && converged < BAIL_COUNT;i++)
   {
     int j;
     float px[4] = {0.2, 0.4, 0.1, 0.5};
     GeglSampler *sampler = gegl_buffer_sampler_new (buffer, format, 
                                                     GEGL_SAMPLER_LOHALO);
 
+    test_start_iter();
     for (j = 0; j < SAMPLES; j ++)
     {
       int x = rands[j*2];
       int y = rands[j*2+1];
       gegl_sampler_get (sampler, x, y, NULL, (void*)&px[0], GEGL_ABYSS_NONE);
     }
+    test_end_iter();
 
     g_object_unref (sampler);
   }