Message ID | 20220519221803.57957-6-goldstein.w.n@gmail.com |
---|---|
State | New |
Headers | show |
Series | [v11,1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked | expand |
On 20/05/2022 03:48, Noah Goldstein via Libc-alpha wrote: > Unroll slightly and enforce good instruction scheduling. This improves > performance on out-of-order machines. The unrolling allows for > pipelined multiplies. > > As well, as an optional sysdep, reorder the operations and prevent > reassosiation for better scheduling and higher ILP. This commit > only adds the barrier for x86, although it should be either no > change or a win for any architecture. > > Unrolling further started to induce slowdowns for sizes [0, 4] > but can help the loop so if larger sizes are the target further > unrolling can be beneficial. > > Results for _dl_new_hash > Benchmarked on Tigerlake: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz > > Time as Geometric Mean of N=30 runs > Geometric of all benchmark New / Old: 0.674 > type, length, New Time, Old Time, New Time / Old Time > fixed, 0, 2.865, 2.72, 1.053 > fixed, 1, 3.567, 2.489, 1.433 > fixed, 2, 2.577, 3.649, 0.706 > fixed, 3, 3.644, 5.983, 0.609 > fixed, 4, 4.211, 6.833, 0.616 > fixed, 5, 4.741, 9.372, 0.506 > fixed, 6, 5.415, 9.561, 0.566 > fixed, 7, 6.649, 10.789, 0.616 > fixed, 8, 8.081, 11.808, 0.684 > fixed, 9, 8.427, 12.935, 0.651 > fixed, 10, 8.673, 14.134, 0.614 > fixed, 11, 10.69, 15.408, 0.694 > fixed, 12, 10.789, 16.982, 0.635 > fixed, 13, 12.169, 18.411, 0.661 > fixed, 14, 12.659, 19.914, 0.636 > fixed, 15, 13.526, 21.541, 0.628 > fixed, 16, 14.211, 23.088, 0.616 > fixed, 32, 29.412, 52.722, 0.558 > fixed, 64, 65.41, 142.351, 0.459 > fixed, 128, 138.505, 295.625, 0.469 > fixed, 256, 291.707, 601.983, 0.485 > random, 2, 12.698, 12.849, 0.988 > random, 4, 16.065, 15.857, 1.013 > random, 8, 19.564, 21.105, 0.927 > random, 16, 23.919, 26.823, 0.892 > random, 32, 31.987, 39.591, 0.808 > random, 64, 49.282, 71.487, 0.689 > random, 128, 82.23, 145.364, 0.566 > random, 256, 152.209, 298.434, 0.51 > > Co-authored-by: Alexander Monakov <amonakov@ispras.ru> > --- > benchtests/bench-dl-new-hash.c | 3 +- > elf/{dl-new-hash.h => simple-dl-new-hash.h} | 20 ++-- > elf/tst-dl-hash.c | 1 + > sysdeps/generic/dl-new-hash.h | 109 ++++++++++++++++++++ > sysdeps/x86/dl-new-hash.h | 24 +++++ > 5 files changed, 144 insertions(+), 13 deletions(-) > rename elf/{dl-new-hash.h => simple-dl-new-hash.h} (75%) > create mode 100644 sysdeps/generic/dl-new-hash.h > create mode 100644 sysdeps/x86/dl-new-hash.h OK. Reviewed-by: Siddhesh Poyarekar <siddhesh@sourceware.org> > > diff --git a/benchtests/bench-dl-new-hash.c b/benchtests/bench-dl-new-hash.c > index 3c8a1d5a82..040fa7ce01 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 > similarity index 75% > rename from elf/dl-new-hash.h > rename to elf/simple-dl-new-hash.h > index 8641bb4196..1437b1bd36 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 8697eb73a0..b21766c63d 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 0000000000..59bfb0e1de > --- /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 0000000000..ce8fb5a838 > --- /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>
diff --git a/benchtests/bench-dl-new-hash.c b/benchtests/bench-dl-new-hash.c index 3c8a1d5a82..040fa7ce01 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 similarity index 75% rename from elf/dl-new-hash.h rename to elf/simple-dl-new-hash.h index 8641bb4196..1437b1bd36 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 8697eb73a0..b21766c63d 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 0000000000..59bfb0e1de --- /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 0000000000..ce8fb5a838 --- /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>