diff mbox

Add random memcpy test

Message ID AM5PR0802MB261046901181DD5E4348ADFA83430@AM5PR0802MB2610.eurprd08.prod.outlook.com
State Superseded
Headers show

Commit Message

Wilco Dijkstra Feb. 7, 2017, 1:06 p.m. UTC
ping

Comments

Siddhesh Poyarekar Feb. 7, 2017, 1:12 p.m. UTC | #1
I see that I had made this comment in the thread before:

> To begin with, please add more comments in the test on why you have
> chosen the distribution you have and also some comments on the effects
> you think the distribution may have on other key factors such as cache
> locality.  If you have come across this distribution in some workload,
> it might give more relevance to this test since then we know that
> improving on this benchmark gives a decent likelihood of improving
> performance on a known and perhaps useful workload.

Can you please add these comments to your test?  Also as I had mentioned
back then, we need to think deeper about the kinds of tests we want to
have for string performance in glibc, including adding some
representative tests for workloads that people may care about.

Siddhesh

On Tuesday 07 February 2017 06:36 PM, Wilco Dijkstra wrote:
> 
> 
> ping
> 
> ________________________________________
> From: Wilco Dijkstra
> Sent: 11 May 2016 11:23
> To: 'GNU C Library'
> Cc: nd
> Subject: [PATCH] Add random memcpy test
> 
> 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"
>     
>
Wainer dos Santos Moschetta Feb. 7, 2017, 6:05 p.m. UTC | #2
<snip>
> +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"
>     

Perhaps you should use the new #include <support/test-driver.c> instead.
diff mbox

Patch

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"