aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--benchtests/bench-dl-new-hash.c3
-rw-r--r--elf/simple-dl-new-hash.h (renamed from elf/dl-new-hash.h)20
-rw-r--r--elf/tst-dl-hash.c1
-rw-r--r--sysdeps/generic/dl-new-hash.h109
-rw-r--r--sysdeps/x86/dl-new-hash.h24
5 files changed, 144 insertions, 13 deletions
diff --git a/benchtests/bench-dl-new-hash.c b/benchtests/bench-dl-new-hash.c
index 3c8a1d5..040fa7c 100644
--- a/benchtests/bench-dl-new-hash.c
+++ b/benchtests/bench-dl-new-hash.c
@@ -16,7 +16,8 @@
License along with the GNU C Library; if not, see
<https://www.gnu.org/licenses/>. */
-#include <elf/dl-new-hash.h>
+#include <dl-new-hash.h>
+#include <elf/simple-dl-new-hash.h>
#define TEST_FUNC(x, y) _dl_new_hash (x)
#define SIMPLE_TEST_FUNC(x, y) __simple_dl_new_hash (x)
diff --git a/elf/dl-new-hash.h b/elf/simple-dl-new-hash.h
index 8641bb4..1437b1b 100644
--- a/elf/dl-new-hash.h
+++ b/elf/simple-dl-new-hash.h
@@ -1,4 +1,4 @@
-/* _dl_new_hash for elf symbol lookup
+/* __simple_dl_new_hash for testing true elf symbol lookup.
Copyright (C) 2022 Free Software Foundation, Inc.
This file is part of the GNU C Library.
@@ -16,16 +16,16 @@
License along with the GNU C Library; if not, see
<https://www.gnu.org/licenses/>. */
-#ifndef _DL_NEW_HASH_H
-#define _DL_NEW_HASH_H 1
+#ifndef _SIMPLE_DL_NEW_HASH_H
+#define _SIMPLE_DL_NEW_HASH_H 1
#include <stdint.h>
-/* For __always_inline. */
-#include <sys/cdefs.h>
-static __always_inline uint32_t
+/* For testing/benchmarking purposes. Real implementation in
+ sysdeps/generic/dl-new-hash.h. */
+static uint32_t
__attribute__ ((unused))
-_dl_new_hash (const char *s)
+__simple_dl_new_hash (const char *s)
{
uint32_t h = 5381;
for (unsigned char c = *s; c != '\0'; c = *++s)
@@ -33,8 +33,4 @@ _dl_new_hash (const char *s)
return h;
}
-/* For testing/benchmarking purposes. */
-#define __simple_dl_new_hash _dl_new_hash
-
-
-#endif /* dl-new-hash.h */
+#endif /* simple-dl-new-hash.h */
diff --git a/elf/tst-dl-hash.c b/elf/tst-dl-hash.c
index 8697eb7..b21766c 100644
--- a/elf/tst-dl-hash.c
+++ b/elf/tst-dl-hash.c
@@ -18,6 +18,7 @@
#include <simple-dl-hash.h>
+#include <simple-dl-new-hash.h>
#include <dl-hash.h>
#include <dl-new-hash.h>
#include <support/support.h>
diff --git a/sysdeps/generic/dl-new-hash.h b/sysdeps/generic/dl-new-hash.h
new file mode 100644
index 0000000..59bfb0e
--- /dev/null
+++ b/sysdeps/generic/dl-new-hash.h
@@ -0,0 +1,109 @@
+/* _dl_new_hash for elf symbol lookup
+ 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/>. */
+
+#ifndef _DL_NEW_HASH_H
+#define _DL_NEW_HASH_H 1
+
+#include <stdint.h>
+/* For __always_inline and __glibc_unlikely. */
+#include <sys/cdefs.h>
+
+/* The simplest implementation of _dl_new_hash is:
+
+ _dl_new_hash (const char *s)
+ {
+ uint32_t h = 5381;
+ for (unsigned char c = *s; c != '\0'; c = *++s)
+ h = h * 33 + c;
+ return h;
+ }
+
+ We can get better performance by slightly unrolling the loop to
+ pipeline the multiples, which gcc cannot easily do due to
+ dependencies across iterations.
+
+ As well, as an architecture specific option we add asm statements
+ to explicitly specify order of operations and prevent reassociation
+ of instructions that lengthens the loop carried dependency. This
+ may have no affect as the compiler may have ordered instructions
+ the same way without it but in testing this has not been the case
+ for GCC. Improving GCC to reliably schedule instructions ideally
+ cannot be easily done.
+
+ Architecture(s) that use the reassociation barriers are:
+ x86
+
+ Note it is very unlikely the reassociation barriers would
+ de-optimize performance on any architecture and with an imperfect
+ compiler it may help performance, especially on out-of-order cpus,
+ so it is suggested that the respective maintainers add them.
+
+ Architecture maintainers are encouraged to benchmark this with
+ __asm_reassociation_barrier defined to __asm__ like it is in x86.
+*/
+
+
+#ifndef __asm_reassociation_barrier
+# define __asm_reassociation_barrier(...)
+#endif
+
+static __always_inline uint32_t
+__attribute__ ((unused))
+_dl_new_hash (const char *str)
+{
+ const unsigned char *s = (const unsigned char *) str;
+ unsigned int h = 5381;
+ unsigned int c0, c1;
+ for (;;)
+ {
+ c0 = s[0];
+ /* Since hashed string is normally not empty, this is unlikely on the
+ first iteration of the loop. */
+ if (__glibc_unlikely (c0 == 0))
+ return h;
+
+ c1 = s[1];
+ if (c1 == 0)
+ {
+ /* Ideal computational order is:
+ c0 += h;
+ h *= 32;
+ h += c0; */
+ c0 += h;
+ __asm_reassociation_barrier("" : "+r"(h) : "r"(c0));
+ h = h * 32 + c0;
+ return h;
+ }
+
+ /* Ideal computational order is:
+ c1 += c0;
+ h *= 33 * 33;
+ c0 *= 32;
+ c1 += c0;
+ h += c1; */
+ c1 += c0;
+ __asm_reassociation_barrier("" : "+r"(c1), "+r"(c0));
+ h *= 33 * 33;
+ c1 += c0 * 32;
+ __asm_reassociation_barrier("" : "+r"(c1));
+ h += c1;
+ s += 2;
+ }
+}
+
+#endif /* dl-new-hash.h */
diff --git a/sysdeps/x86/dl-new-hash.h b/sysdeps/x86/dl-new-hash.h
new file mode 100644
index 0000000..ce8fb5a
--- /dev/null
+++ b/sysdeps/x86/dl-new-hash.h
@@ -0,0 +1,24 @@
+/* _dl_new_hash for elf symbol lookup
+ 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/>. */
+
+#ifdef __asm_reassociation_barrier
+# error "__asm_reassociation_barrier should never already be defined."
+#endif
+
+#define __asm_reassociation_barrier __asm__
+#include <sysdeps/generic/dl-new-hash.h>