[WIP] Better string tests benchmarks

[OndÅej BÃlka <neleai at seznam dot cz>]

Hi, 
I am now writting better string test/benchmarks. I would like to have
dryrun commented to have same logic everywhere.

I divided benchmark in several components that will be separated to
separate programs. 

Now for comments I put everything as example strlen test/benchmark.

1) First component is input generation. It could be done by random
generator, from dryrun or crafted file.

2) Then we randomly select implementations and benchmark them.
A systemwide profiler can combine steps 1 and 2.

2b) We can use same framework to run tests. For it we also unmap pages
before and after string to detect illegal access.

When I wrote functions testsuite was relatively unhelpful. It took long
time to run and finding what exactly went wrong is time consuming.
I added simple reporting tool that tells how many steps are needed for
gdb to position where error happened. This needs exact command how run
gdb which will vary.

3) Analyze results. I put now only text report for simplicity.


Where should I put these files?

Comments?

diff --git a/string/Makefile b/string/Makefile
index 0237edd..5539db9 100644
--- a/string/Makefile
+++ b/string/Makefile
@@ -71,6 +71,7 @@ CFLAGS-tst-strlen.c = -fno-builtin
 CFLAGS-stratcliff.c = -fno-builtin
 CFLAGS-test-ffs.c = -fno-builtin
 CFLAGS-tst-inlcall.c = -fno-builtin
+CFLAGS-test-strlen.c = -lrt
 
 ifeq ($(run-built-tests),yes)
 tests: $(objpfx)tst-svc.out
diff --git a/string/bench-output.h b/string/bench-output.h
new file mode 100644
index 0000000..c0c54bd
--- /dev/null
+++ b/string/bench-output.h
@@ -0,0 +1,90 @@
+/* Display output from benchmark or profiler.
+   Copyright (C) 2013 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdint.h>
+#include <stdio.h>
+#include <math.h>
+typedef struct 
+{
+  double mean;
+  double M2;
+  long no;
+} data;
+data ds[100][5][10];
+
+void
+replay(rec *r, int size)
+{
+  int i;
+  int magnitude,ms;
+  for (i = 0; i < size; i++)
+    {
+      uint64_t time = r[i].common.time_end - r[i].common.time_start;
+      uint64_t choice = r[i].common.choice;
+      for (magnitude = 0 ,ms = 1 ; magnitude < 5 ; magnitude++)
+        { 
+          if (r[i].SORT_BY < 10 * ms)
+            { 
+              data *d = &(ds[choice][magnitude][r[i].SORT_BY / ms]);
+
+              d->no++;
+              double delta = time - d->mean;
+              d->mean = d->mean + delta / d->no;
+              d->M2 = d->M2 + delta * (time - d->mean); 
+            }
+          ms *= 10;
+        }
+    }
+}
+
+void replay_end()
+{
+  int i;
+  int choice;
+  int magnitude,ms=1;
+  for (magnitude = 0, ms = 1; magnitude < 5 ; magnitude++)
+    {
+      printf("\n\nMEAN\n\n");
+      printf("IMPLEMENTATION ");
+      for (i = 0 ; i < 10 ; i++)
+        printf("%10d",i*ms);
+      printf("\n");
+
+      for (choice = 0 ; choice < function_no ; choice++)
+        {
+          printf("%10s    :",function_name[choice]);
+          for (i = 0 ; i < 10 ; i++)
+            printf("%10.1f", ds[choice][magnitude][i].mean);
+        }
+
+      printf("\n\nSTANDARD DEVIATION\n\n");
+      printf("IMPLEMENTATION ");
+      for (i = 0 ; i < 10 ; i++)
+        printf("%10d",i*ms);
+      printf("\n");
+
+      for (choice = 0 ; choice < function_no;choice++)
+        {
+          printf("%10s    :",function_name[choice]);
+          for (i = 0 ; i < 10 ; i++)
+            printf("%10.1f", sqrt(ds[choice][magnitude][i].M2/ds[choice][magnitude][i].no));
+        }
+	ms*=10;
+    }
+  printf("\n");
+}
diff --git a/string/bench_common.h b/string/bench_common.h
new file mode 100644
index 0000000..e534f7d
--- /dev/null
+++ b/string/bench_common.h
@@ -0,0 +1,7 @@
+#include <stdint.h>
+typedef struct 
+{
+  uint64_t time_start;
+  uint64_t time_end;
+  uint64_t choice;
+} common_s;
diff --git a/string/string-input.h b/string/string-input.h
new file mode 100644
index 0000000..6488b56
--- /dev/null
+++ b/string/string-input.h
@@ -0,0 +1,84 @@
+/* String input generator - generates string inputs for number of tests.
+   Copyright (C) 2013 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+
+#include <stdlib.h>
+
+static long capacity;
+
+static char *dest, *src;
+static void 
+gen_init (long _capacity)
+{
+  long i;
+
+  capacity = _capacity;
+
+  dest = malloc (2 * capacity + 1);
+  src  = malloc (2 * capacity + 1);
+  for(i = 0; i < 2 * capacity; i++)
+    {
+      dest[i] = (rand_r (&seed) % 128) + 1;
+      src[i] = (rand_r (&seed) % 128) + 1;
+    }
+}
+
+static void
+gen (long dest_offset, long dest_size ,long src_offset, long src_size)
+{
+  long i;
+  char *dest2 = dest + dest_offset % capacity;
+  char *src2 = src + src_offset % capacity;
+  if (dest_size > capacity)
+    dest_size = capacity;
+  if (src_size > capacity)
+    src_size = capacity;
+
+  /* It is faster to have pregenerated random data and just temporarily place
+     zero markers at end.  */
+  char dc = dest2[dest_size], sc = src2[src_size];
+  src2[src_size] = 0;
+  dest2[dest_size] = 0;
+
+#ifdef DIRTY_CACHE
+  /* As we wrote to writeback cache we are dealing with dirty cache lines.  */
+#else
+  for(i = 0; i <= dest_size + 64; i += 64)
+    __builtin_prefetch (dest);
+  for(i = 0; i <= src_size + 64; i += 64)
+    __builtin_prefetch (src);      
+#endif
+#ifdef NO_CACHE
+  __builtin___clear_cache (dest, dest + dest_size);
+  __builtin___clear_cache (src, src + src_size);
+#endif
+
+#ifdef HARDEN
+  /* mmap page before and end of strings unreadable.  */
+#endif
+
+  test(dest2, dest_size, src2, src_size);
+
+#ifdef HARDEN
+  /* Put it back.  */
+#endif
+
+  dest2[dest_size] = dc;
+  src2[src_size] = sc;
+}
+
diff --git a/string/test-string.h b/string/test-string.h
index 47659d0..d66094e 100644
--- a/string/test-string.h
+++ b/string/test-string.h
@@ -210,4 +210,25 @@ test_init (void)
   memset (buf2, 0x5a, page_size);
 }
 
+
+
+static int ignore;
+
+static char *program;
+void test_failed ()
+{
+  printf ("Test failed. To replicate run\ngdb %s\nignore test %i\nb test\nr\n",
+          program, ignore);
+  exit (-1);
+}
+
+void test_start (char *_program)
+{
+  program = _program;
+  int i;
+  ignore = 0;
+  /* We want also replicate SIGSEGVs et al.  */
+  for (i = 0 ; i < 32 ; i++)
+    signal (i, test_failed);
+}
 #endif
diff --git a/string/test-strlen.c b/string/test-strlen.c
index be2a7f9..b12d873 100644
--- a/string/test-strlen.c
+++ b/string/test-strlen.c
@@ -61,131 +61,87 @@ IMPL (simple_STRLEN, 0)
 IMPL (STRLEN, 1)
 
 
-static void
-do_one_test (impl_t *impl, const CHAR *s, size_t exp_len)
-{
-  size_t len = CALL (impl, s);
-  if (len != exp_len)
-    {
-      error (0, 0, "Wrong result in function %s %zd %zd", impl->name,
-	     len, exp_len);
-      ret = 1;
-      return;
-    }
 
-  if (HP_TIMING_AVAIL)
-    {
-      hp_timing_t start __attribute ((unused));
-      hp_timing_t stop __attribute ((unused));
-      hp_timing_t best_time = ~ (hp_timing_t) 0;
-      size_t i;
-
-      for (i = 0; i < 32; ++i)
-	{
-	  HP_TIMING_NOW (start);
-	  CALL (impl, s);
-	  HP_TIMING_NOW (stop);
-	  HP_TIMING_BEST (best_time, start, stop);
-	}
-
-      printf ("\t%zd", (size_t) best_time);
-    }
-}
+#include <stdlib.h>
+#include <string.h>
+int function_no;
+char* function_name[100];
+void* functions[100];
 
-static void
-do_test (size_t align, size_t len)
-{
-  size_t i;
+unsigned int seed;
 
-  align &= 63;
-  if (align + sizeof(CHAR) * len >= page_size)
-    return;
+#include "bench_common.h"
+#include "test-strlen/layout.h"
 
-  CHAR *buf = (CHAR *) (buf1);
+rec *generate (int n, int seed);
+void test (char *dest, int destsize, char *src, int srcsize);
 
-  for (i = 0; i < len; ++i)
-    buf[align + i] = 1 + 11111 * i % MAX_CHAR;
-  buf[align + len] = 0;
+#include "test-strlen/generate.h"
 
-  if (HP_TIMING_AVAIL)
-    printf ("Length %4zd, alignment %2zd:", len, align);
+#include <time.h>
+uint64_t get_ticks()
+{
+  struct timespec start;
+  clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &start);
+  return ((uint64_t)1000000000)*start.tv_sec+start.tv_nsec;
+}
 
-  FOR_EACH_IMPL (impl, 0)
-    do_one_test (impl, (CHAR *) (buf + align), len);
+rec *record;
+int record_no;
+void test
+(char *dest, int destsize, char *src, int srcsize)
+{
+  int choice = rand_r(&seed)%function_no;
+  proto_t fn = (proto_t) functions[choice];
+  record[record_no].common.choice    = choice;
+  record[record_no].common.time_start= get_ticks();
+  size_t ret=fn(dest);
+  record[record_no].common.time_end  = get_ticks();
+  if (ret != destsize)
+    test_failed();
+  ignore++;
+}
 
-  if (HP_TIMING_AVAIL)
-    putchar ('\n');
+#include "string-input.h"
+volatile double dontoptimize;
+void benchmark_init(){
+  int k;
+  for(k = 0; k < 1000000; k++)
+     dontoptimize += exp(k);
 }
 
-static void
-do_random_tests (void)
+void
+benchmark(rec *r, int no)
 {
-  size_t i, j, n, align, len;
-  CHAR *p = (CHAR *) (buf1 + page_size - 512 * sizeof(CHAR));
-
-  for (n = 0; n < ITERATIONS; n++)
+  benchmark_init();
+  gen_init(1<<20);
+  record = r;
+  for (record_no = 0 ; record_no < no ; record_no++)
     {
-      align = random () & 15;
-      len = random () & 511;
-      if (len + align > 510)
-	len = 511 - align - (random () & 7);
-      j = len + align + 64;
-      if (j > 512)
-	j = 512;
-
-      for (i = 0; i < j; i++)
-	{
-	  if (i == len + align)
-	    p[i] = 0;
-	  else
-	    {
-	      p[i] = random () & 255;
-	      if (i >= align && i < len + align && !p[i])
-		p[i] = (random () & 127) + 1;
-	    }
-	}
-
-      FOR_EACH_IMPL (impl, 1)
-	if (CALL (impl, (CHAR *) (p + align)) != len)
-	  {
-	    error (0, 0, "Iteration %zd - wrong result in function %s (%zd) %zd != %zd, p %p",
-		   n, impl->name, align, CALL (impl, (CHAR *) (p + align)),
-		   len, p);
-	    ret = 1;
-	  }
+      gen(record[record_no].dest,record[record_no].destsize,0,0);
     }
 }
 
+#define SORT_BY destsize
+#include "bench-output.h"
+
 int
-test_main (void)
+main()
 {
-  size_t i;
-
-  test_init ();
-
-  printf ("%20s", "");
+  test_start("xxx");
+  function_no = 0;
+  ignore = 0;
   FOR_EACH_IMPL (impl, 0)
-    printf ("\t%s", impl->name);
-  putchar ('\n');
-
-  /* Checking with only 4 * N alignments for wcslen, other alignments are wrong for wchar_t type arrays*/
-
-  for (i = 1; i < 8; ++i)
-  {
-    do_test (sizeof(CHAR) * i, i);
-    do_test (0, i);
-  }
-
-  for (i = 2; i <= 12; ++i)
     {
-      do_test (0, 1 << i);
-      do_test (sizeof(CHAR) * 7, 1 << i);
-      do_test (sizeof(CHAR) * i, 1 << i);
-      do_test (sizeof(CHAR) * i, (size_t)((1 << i) / 1.5));
+      functions[function_no] = impl->fn;
+      function_name[function_no] = impl->name;
+      function_no++;
     }
-
-  do_random_tests ();
-  return ret;
+  seed = 42;
+  int tests = 1000000;
+  gen_init(1<<20);
+  rec *r = generate(tests,seed);
+  benchmark(r,tests);
+  replay(r,tests);
+  replay_end();
 }
-
-#include "../test-skeleton.c"