benchtests: Add benchtests for dl_elf_hash, dl_new_hash and nss_hash

Benchtests are for throughput and include random / fixed size
benchmarks.
Reviewed-by: Siddhesh Poyarekar <siddhesh@sourceware.org>

7 files changed, 335 insertions, 8 deletions

diff --git a/benchtests/Makefile b/benchtests/Makefile
index de9de5c..c279041 100644
--- a/benchtests/Makefile
+++ b/benchtests/Makefile
@@ -227,6 +227,12 @@ LOCALES := \
 include ../gen-locales.mk
 endif
 
+hash-benchset := \
+  dl-elf-hash \
+  dl-new-hash \
+  nss-hash \
+# hash-benchset
+
 stdlib-benchset := strtod
 
 stdio-common-benchset := sprintf
@@ -235,7 +241,7 @@ math-benchset := math-inlines
 
 ifeq (${BENCHSET},)
 benchset := $(string-benchset-all) $(stdlib-benchset) $(stdio-common-benchset) \
-	    $(math-benchset)
+	    $(math-benchset) $(hash-benchset)
 else
 benchset := $(foreach B,$(filter %-benchset,${BENCHSET}), ${${B}})
 endif
@@ -363,9 +369,20 @@ bench-clean:
 
 # Validate the passed in BENCHSET
 ifneq ($(strip ${BENCHSET}),)
-VALIDBENCHSETNAMES := bench-pthread bench-math bench-string string-benchset \
-   wcsmbs-benchset stdlib-benchset stdio-common-benchset math-benchset \
-   malloc-thread malloc-simple
+VALIDBENCHSETNAMES := \
+  bench-math \
+  bench-pthread \
+  bench-string \
+  hash-benchset \
+  malloc-simple \
+  malloc-thread \
+  math-benchset \
+  stdio-common-benchset \
+  stdlib-benchset \
+  string-benchset \
+  wcsmbs-benchset \
+# VALIDBENCHSETNAMES
+
 INVALIDBENCHSETNAMES := $(filter-out ${VALIDBENCHSETNAMES},${BENCHSET})
 ifneq (${INVALIDBENCHSETNAMES},)
 $(info The following values in BENCHSET are invalid: ${INVALIDBENCHSETNAMES})
diff --git a/benchtests/README b/benchtests/README
index 4d83a05..998ba9b 100644
--- a/benchtests/README
+++ b/benchtests/README
@@ -84,12 +84,13 @@ where BENCHSET may be a space-separated list of the following values:
     bench-math
     bench-pthread
     bench-string
+    hash-benchset
+    malloc-thread
+    math-benchset
+    stdio-common-benchset
+    stdlib-benchset
     string-benchset
     wcsmbs-benchset
-    stdlib-benchset
-    stdio-common-benchset
-    math-benchset
-    malloc-thread
 
 Adding a function to benchtests:
 ===============================
diff --git a/benchtests/bench-dl-elf-hash.c b/benchtests/bench-dl-elf-hash.c
new file mode 100644
index 0000000..067de9f
--- /dev/null
+++ b/benchtests/bench-dl-elf-hash.c
@@ -0,0 +1,27 @@
+/* Measure __dl_new_hash runtime
+   Copyright (C) 2022 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
+   <https://www.gnu.org/licenses/>.  */
+
+#include <dl-hash.h>
+#include <elf/simple-dl-hash.h>
+#define TEST_FUNC(x, y) _dl_elf_hash (x)
+#define SIMPLE_TEST_FUNC(x, y) __simple_dl_elf_hash (x)
+
+#define TEST_NAME "_dl_elf_hash"
+
+
+#include "bench-hash-funcs.c"
diff --git a/benchtests/bench-dl-new-hash.c b/benchtests/bench-dl-new-hash.c
new file mode 100644
index 0000000..3c8a1d5
--- /dev/null
+++ b/benchtests/bench-dl-new-hash.c
@@ -0,0 +1,25 @@
+/* Measure __dl_new_hash runtime
+   Copyright (C) 2022 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
+   <https://www.gnu.org/licenses/>.  */
+
+#include <elf/dl-new-hash.h>
+#define TEST_FUNC(x, y) _dl_new_hash (x)
+#define SIMPLE_TEST_FUNC(x, y) __simple_dl_new_hash (x)
+
+#define TEST_NAME "_dl_new_hash"
+
+#include "bench-hash-funcs.c"
diff --git a/benchtests/bench-hash-funcs-kernel.h b/benchtests/bench-hash-funcs-kernel.h
new file mode 100644
index 0000000..83995cc
--- /dev/null
+++ b/benchtests/bench-hash-funcs-kernel.h
@@ -0,0 +1,86 @@
+/* Actual benchmark kernels used by bench-hash-funcs.h
+   Copyright (C) 2022 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
+   <https://www.gnu.org/licenses/>.  */
+
+
+
+/* We go through the trouble of using macros here because many of the
+   hash functions are meant to be inlined so its not fair to benchmark
+   them with a function pointer where they won't be inlinable. */
+#undef RUN_FUNC
+#undef POSTFIX
+#ifdef SIMPLE
+# define RUN_FUNC SIMPLE_TEST_FUNC
+# define POSTFIX _simple
+#else
+# define RUN_FUNC TEST_FUNC
+# define POSTFIX _optimized
+#endif
+
+#define PRIMITIVE_CAT(x, y) x ## y
+#define CAT(x, y) PRIMITIVE_CAT (x, y)
+
+static double __attribute__ ((noinline, noclone))
+CAT (do_one_test_kernel, POSTFIX) (const char *s, size_t len)
+{
+
+  unsigned int iters;
+  timing_t start, stop, cur;
+
+  /* Warmup.  */
+  for (iters = NFIXED_ITERS / 32; iters; --iters)
+    DO_NOT_OPTIMIZE_OUT (RUN_FUNC (s, len));
+
+  TIMING_NOW (start);
+  for (iters = NFIXED_ITERS; iters; --iters)
+    DO_NOT_OPTIMIZE_OUT (RUN_FUNC (s, len));
+
+  TIMING_NOW (stop);
+
+  TIMING_DIFF (cur, start, stop);
+
+  (void) (len);
+  return (double) cur / (double) NFIXED_ITERS;
+}
+
+static double __attribute__ ((noinline, noclone))
+CAT (do_rand_test_kernel, POSTFIX) (char const *bufs,
+				    unsigned int const *sizes)
+{
+  unsigned int i, iters;
+  size_t offset;
+  timing_t start, stop, cur;
+
+  /* Warmup.  */
+  for (i = 0, offset = 0; i < NRAND_BUFS; ++i, offset += RAND_BENCH_MAX_LEN)
+    DO_NOT_OPTIMIZE_OUT (RUN_FUNC (bufs + offset, sizes[i]));
+
+  TIMING_NOW (start);
+  for (iters = NRAND_ITERS; iters; --iters)
+    {
+      for (i = 0, offset = 0; i < NRAND_BUFS;
+	   ++i, offset += RAND_BENCH_MAX_LEN)
+	DO_NOT_OPTIMIZE_OUT (RUN_FUNC (bufs + offset, sizes[i]));
+
+    }
+  TIMING_NOW (stop);
+
+  TIMING_DIFF (cur, start, stop);
+
+  (void) (sizes);
+  return (double) cur / (double) (NRAND_ITERS * NRAND_BUFS);
+}
diff --git a/benchtests/bench-hash-funcs.c b/benchtests/bench-hash-funcs.c
new file mode 100644
index 0000000..578c5cb
--- /dev/null
+++ b/benchtests/bench-hash-funcs.c
@@ -0,0 +1,145 @@
+/* Measure hash functions runtime.
+   Copyright (C) 2022 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
+   <https://www.gnu.org/licenses/>.  */
+
+#define TEST_MAIN
+#ifndef TEST_FUNC
+# error "No TEST_FUNC provided!"
+#endif
+#ifndef SIMPLE_TEST_FUNC
+# error "No SIMPLE_TEST_FUNC provided!"
+#endif
+
+#ifndef TEST_NAME
+# define STRINGIFY_PRIMITIVE(x) #  x
+# define STRINGIFY(x) STRINGIFY_PRIMITIVE (x)
+
+# define TEST_NAME STRINGIFY (TEST_FUNC)
+#endif
+
+#include "json-lib.h"
+#include "bench-timing.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define DO_NOT_OPTIMIZE_OUT(x) __asm__ volatile("" : : "r,m"(x) : "memory")
+
+enum
+{
+  NFIXED_ITERS = 1048576,
+  NRAND_BUFS = 16384,
+  NRAND_ITERS = 2048,
+  RAND_BENCH_MAX_LEN = 128
+};
+
+#include "bench-hash-funcs-kernel.h"
+#define SIMPLE
+#include "bench-hash-funcs-kernel.h"
+
+static void
+do_one_test (json_ctx_t *json_ctx, size_t len)
+{
+  char buf[len + 1];
+  memset (buf, -1, len);
+  buf[len] = '\0';
+
+  json_element_object_begin (json_ctx);
+
+  json_attr_string (json_ctx, "type", "fixed");
+  json_attr_uint (json_ctx, "length", len);
+  json_attr_double (json_ctx, "time_simple", do_one_test_kernel_simple (buf, len));
+  json_attr_double (json_ctx, "time_optimized", do_one_test_kernel_optimized (buf, len));
+
+  json_element_object_end (json_ctx);
+}
+
+static void __attribute__ ((noinline, noclone))
+do_rand_test (json_ctx_t *json_ctx)
+{
+  size_t i, sz, offset;
+  char *bufs;
+  unsigned int *sizes;
+
+  bufs = (char *) calloc (NRAND_BUFS, RAND_BENCH_MAX_LEN);
+  sizes = (unsigned int *) calloc (NRAND_BUFS, sizeof (unsigned int));
+  if (bufs == NULL || sizes == NULL)
+    {
+      fprintf (stderr, "Failed to allocate bufs for random test\n");
+      goto done;
+    }
+
+  for (sz = 2; sz <= RAND_BENCH_MAX_LEN; sz += sz)
+    {
+      json_element_object_begin (json_ctx);
+      json_attr_string (json_ctx, "type", "random");
+      json_attr_uint (json_ctx, "length", sz);
+
+      for (i = 0, offset = 0; i < NRAND_BUFS;
+	   ++i, offset += RAND_BENCH_MAX_LEN)
+	{
+	  sizes[i] = random () % sz;
+	  memset (bufs + offset, -1, sizes[i]);
+	  bufs[offset + sizes[i]] = '\0';
+	}
+
+      json_attr_double (json_ctx, "time_simple",
+			do_rand_test_kernel_simple (bufs, sizes));
+      json_attr_double (json_ctx, "time_optimized",
+			do_rand_test_kernel_optimized (bufs, sizes));
+      json_element_object_end (json_ctx);
+    }
+
+done:
+  if (bufs)
+    free (bufs);
+
+  if (sizes)
+    free (sizes);
+}
+
+static int
+do_test (void)
+{
+  int i;
+  json_ctx_t json_ctx;
+
+  json_init (&json_ctx, 0, stdout);
+  json_document_begin (&json_ctx);
+  json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
+  json_attr_object_begin (&json_ctx, "functions");
+  json_attr_object_begin (&json_ctx, TEST_NAME);
+  json_array_begin (&json_ctx, "results");
+
+  for (i = 0; i < 16; ++i)
+    do_one_test (&json_ctx, i);
+
+  for (i = 16; i <= 256; i += i)
+    do_one_test (&json_ctx, i);
+
+  do_rand_test (&json_ctx);
+
+  json_array_end (&json_ctx);
+  json_attr_object_end (&json_ctx);
+  json_attr_object_end (&json_ctx);
+  json_document_end (&json_ctx);
+
+  return 0;
+}
+
+#include <support/test-driver.c>
diff --git a/benchtests/bench-nss-hash.c b/benchtests/bench-nss-hash.c
new file mode 100644
index 0000000..7e36942
--- /dev/null
+++ b/benchtests/bench-nss-hash.c
@@ -0,0 +1,26 @@
+/* Measure __nss_hash runtime
+   Copyright (C) 2022 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
+   <https://www.gnu.org/licenses/>.  */
+
+#include <nss.h>
+#include <nss/simple-nss-hash.h>
+#define TEST_FUNC __nss_hash
+#define SIMPLE_TEST_FUNC __simple_nss_hash
+
+uint32_t __nss_hash (const void *__key, size_t __length);
+
+#include "bench-hash-funcs.c"