[PATCH] Add random memcpy test

[Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>]

This patch adds a new memcpy test that uses small copy sizes using random alignment
and size. The copy size is based on a preset distribution that favors smaller sizes and multiples
of 4, 8 and 16.  Instead of repeating the same copy over and over again like the existing
tests, it times several thousand different copies to more accurately estimate the overhead
of branch prediction.

OK for commit?

ChangeLog:
2016-05-11  Wilco Dijkstra  <wdijkstr@arm.com>

	* benchtests/Makefile (string-benchset): Add memcpy-random.
	* benchtests/bench-memcpy-random.c: New file.

---

diff --git a/benchtests/Makefile b/benchtests/Makefile
index 61077ea9b6f7d4c342192429a8d90ecdf9bdaea7..03311dd72856bf0e595a759b817cb772f0fd3a6f 100644
--- a/benchtests/Makefile
+++ b/benchtests/Makefile
@@ -38,7 +38,7 @@ string-benchset := bcopy bzero memccpy memchr memcmp memcpy memmem memmove \
 		   strcat strchr strchrnul strcmp strcpy strcspn strlen \
 		   strncasecmp strncat strncmp strncpy strnlen strpbrk strrchr \
 		   strspn strstr strcpy_chk stpcpy_chk memrchr strsep strtok \
-		   strcoll memcpy-large memmove-large memset-large
+		   strcoll memcpy-large memcpy-random memmove-large memset-large
 wcsmbs-benchset := wcslen wcsnlen wcscpy wcpcpy wcsncpy wcpncpy wcscat wcsncat \
 		   wcscmp wcsncmp wcschr wcschrnul wcsrchr wcsspn wcspbrk wcscspn \
 		   wmemchr wmemset wmemcmp
diff --git a/benchtests/bench-memcpy-random.c b/benchtests/bench-memcpy-random.c
new file mode 100644
index 0000000000000000000000000000000000000000..668d6a1d35074f4227be4e1ff424da556a377cef
--- /dev/null
+++ b/benchtests/bench-memcpy-random.c
@@ -0,0 +1,130 @@
+/* Measure memcpy functions.
+   Copyright (C) 2016 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/>.  */
+
+#define MIN_PAGE_SIZE 131072
+#define TEST_MAIN
+#define TEST_NAME "memcpy-random"
+#include "bench-string.h"
+
+IMPL (memcpy, 0)
+
+#define NUM_COPIES 2048
+#define NUM_DISTR  1024
+
+typedef struct
+{
+  uint16_t src;
+  uint16_t dst;
+  uint16_t len;
+} copy_t;
+
+static copy_t copy[NUM_COPIES];
+static uint8_t copy_distribution[NUM_DISTR];
+
+typedef char *(*proto_t) (char *, const char *, size_t);
+
+
+static void
+init_copy_distribution (void)
+{
+  int i, n, pos = 0;
+  for (i = 0; i < 256; i++)
+    {
+      if (i < 8)
+	n = 1;
+      else if (i < 16)
+	n = 8;
+      else if (i < 32)
+	n = 6;
+      else if (i < 64)
+	n = 4;
+      else if (i < 128)
+	n = 2;
+      else
+	n = 1;
+
+      if ((i & 15) == 0)
+	n = n * 7;
+      else if ((i & 7) == 0)
+	n = n * 5;
+      else if ((i & 3) == 0)
+	n = n * 3;
+
+      for ( ; n > 0 && pos < NUM_DISTR; n--)
+	copy_distribution[pos++] = i;
+    }
+  for ( ; pos < NUM_DISTR; pos++)
+    copy_distribution[pos] = 255;
+}
+
+static void
+do_one_test (impl_t *impl, char *dst, char *src, copy_t *copy, size_t n)
+{
+  timing_t start, stop, cur;
+  size_t iters = INNER_LOOP_ITERS * 20;
+
+  TIMING_NOW (start);
+  for (int i = 0; i < iters; ++i)
+    for (int j = 0; j < n; j++)
+      CALL (impl, dst + copy[j].dst, src + copy[j].src, copy[j].len);
+  TIMING_NOW (stop);
+
+  TIMING_DIFF (cur, start, stop);
+
+  TIMING_PRINT_MEAN ((double) cur, (double) iters);
+}
+
+static void
+do_test (size_t max_size)
+{
+  for (int i = 0; i < max_size; i++)
+    buf1[i] = i * 3;
+
+  for (int i = 0; i < NUM_COPIES; i++)
+    {
+      copy[i].dst = rand () & (max_size - 1);
+      copy[i].src = rand () & (max_size - 1);
+      copy[i].len = copy_distribution[rand () & (NUM_DISTR - 1)];
+    }
+
+  printf ("Memory size %6zd:", max_size);
+
+  FOR_EACH_IMPL (impl, 0)
+    do_one_test (impl, (char *) buf2, (char *) buf1, copy, NUM_COPIES);
+
+  putchar ('\n');
+}
+
+int
+test_main (void)
+{
+  test_init ();
+  init_copy_distribution ();
+
+  printf ("%23s", "");
+  FOR_EACH_IMPL (impl, 0)
+    printf ("\t%s", impl->name);
+  putchar ('\n');
+
+  for (int i = 4; i <= 64; i = i * 2)
+    do_test (i * 1024);
+
+  return ret;
+}
+
+#include "../test-skeleton.c"