diff options
Diffstat (limited to 'sysdeps')
| -rw-r--r-- | sysdeps/generic/dl-new-hash.h | 109 | ||||
| -rw-r--r-- | sysdeps/x86/dl-new-hash.h | 24 |
2 files changed, 133 insertions, 0 deletions
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> |