[v9,6/6] elf: Optimize _dl_new_hash in dl-new-hash.h
Checks
| Context |
Check |
Description |
| dj/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
| dj/TryBot-32bit |
fail
|
Patch series failed to apply
|
Commit Message
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>
---
sysdeps/generic/dl-new-hash.h | 114 +++++++++++++++++++++++++++++
{elf => sysdeps/x86}/dl-new-hash.h | 16 +---
2 files changed, 117 insertions(+), 13 deletions(-)
create mode 100644 sysdeps/generic/dl-new-hash.h
rename {elf => sysdeps/x86}/dl-new-hash.h (77%)
Comments
Not sure why, but the series failed to apply on trybot. It's probably a
trybot bug because it applied just fine on my up to date copy.
On 17/05/2022 02:00, 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
reassociation. Later in the patch too.
> 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>
> ---
> sysdeps/generic/dl-new-hash.h | 114 +++++++++++++++++++++++++++++
> {elf => sysdeps/x86}/dl-new-hash.h | 16 +---
This breaks the benchmark build, but including just dl-new-hash.h in the
benchmark should fix it.
> 2 files changed, 117 insertions(+), 13 deletions(-)
> create mode 100644 sysdeps/generic/dl-new-hash.h
> rename {elf => sysdeps/x86}/dl-new-hash.h (77%)
>
> diff --git a/sysdeps/generic/dl-new-hash.h b/sysdeps/generic/dl-new-hash.h
> new file mode 100644
> index 0000000000..84aa7991a4
> --- /dev/null
> +++ b/sysdeps/generic/dl-new-hash.h
> @@ -0,0 +1,114 @@
> +/* _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. */
> +#include <sys/cdefs.h>
> +/* For __glibc_unlikely. */
> +#include <sys/cdefs.h>
Same header included twice.
> +
> +/* 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.
.. 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 specifying order of operations to prevent
to explicitly specify the order...
> + reassosiation 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 reassosiation barries are:
> + x86
> +
> + Note it is very unlikely the reassosiation barriers would
> + de-optimize performance on any archictecture and with an imperfect
architecture
> + compiler it may help performance, especially on out-of-order cpus,
> + so it is suggested that the respective maintainers add them. */
Suggest: "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 instruction scheduling is:
Suggest: "Ideal computation order is"
> + c0 += h;
> + h *= 32;
> + h += c0;
> +
> + The __asm_reassociation_barrier() macro is a sysdep optional asm
> + statements to prevents reassosiation that would result in more
> + instruction interdependencies and worse scheduling. */
This bit is redundant with the description at the top near
__asm_reassociation_barrier.
> + c0 += h;
> + __asm_reassociation_barrier("" : "+r"(h) : "r"(c0));
> + h = h * 32 + c0;
> + return h;
> + }
> +
> + /* Ideal instruction scheduling is:
Same: "Ideal computation order is"
> + c1 += c0;
> + h *= 33 * 33;
> + c0 *= 32;
> + c1 += c0;
> + h += c1;
> +
> + The __asm_reassociation_barrier() macro is a sysdep optional asm
> + statements to prevents reassosiation that would result in more
> + instruction interdependencies and worse scheduling. */
This too is redundant.
> + 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/elf/dl-new-hash.h b/sysdeps/x86/dl-new-hash.h
> similarity index 77%
> rename from elf/dl-new-hash.h
> rename to sysdeps/x86/dl-new-hash.h
> index b7a91ecc07..dd800265bf 100644
> --- a/elf/dl-new-hash.h
> +++ b/sysdeps/x86/dl-new-hash.h
> @@ -19,19 +19,9 @@
> #ifndef _DL_NEW_HASH_H
> #define _DL_NEW_HASH_H 1
No need to define this...
>
> -#include <stdint.h>
> -/* For __always_inline. */
> -#include <sys/cdefs.h>
> -
> -static __always_inline uint32_t
> -__attribute__ ((unused))
> -_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;
> -}
> +#define __asm_reassociation_barrier __asm__
>
> +#undef _DL_NEW_HASH_H
... if it is unconditionally undefined here.
> +#include <sysdeps/generic/dl-new-hash.h>
>
> #endif /* dl-new-hash.h */
On Tue, May 17, 2022 at 12:12 AM Siddhesh Poyarekar <siddhesh@gotplt.org> wrote:
>
> Not sure why, but the series failed to apply on trybot. It's probably a
> trybot bug because it applied just fine on my up to date copy.
I think it may be related to the fact that earlier versions deleted
elf/dl-new-hash.h.
>
> On 17/05/2022 02:00, 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
>
> reassociation. Later in the patch too.
Fixed throughout in V10.
>
> > 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>
> > ---
> > sysdeps/generic/dl-new-hash.h | 114 +++++++++++++++++++++++++++++
> > {elf => sysdeps/x86}/dl-new-hash.h | 16 +---
>
> This breaks the benchmark build, but including just dl-new-hash.h in the
> benchmark should fix it.
Fixed in V10.
>
> > 2 files changed, 117 insertions(+), 13 deletions(-)
> > create mode 100644 sysdeps/generic/dl-new-hash.h
> > rename {elf => sysdeps/x86}/dl-new-hash.h (77%)
> >
> > diff --git a/sysdeps/generic/dl-new-hash.h b/sysdeps/generic/dl-new-hash.h
> > new file mode 100644
> > index 0000000000..84aa7991a4
> > --- /dev/null
> > +++ b/sysdeps/generic/dl-new-hash.h
> > @@ -0,0 +1,114 @@
> > +/* _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. */
> > +#include <sys/cdefs.h>
> > +/* For __glibc_unlikely. */
> > +#include <sys/cdefs.h>
>
> Same header included twice.
Missed that in V10. Will wait for feedback on the rest of the changes
and update with V11.
>
> > +
> > +/* 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.
>
> .. 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 specifying order of operations to prevent
>
> to explicitly specify the order...
Fixed in V10.
>
> > + reassosiation 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 reassosiation barries are:
> > + x86
> > +
> > + Note it is very unlikely the reassosiation barriers would
> > + de-optimize performance on any archictecture and with an imperfect
>
> architecture
Fixed in V10.
>
> > + compiler it may help performance, especially on out-of-order cpus,
> > + so it is suggested that the respective maintainers add them. */
>
> Suggest: "architecture maintainers are encouraged to benchmark this with
> __asm_reassociation_barrier defined to __asm__ like it is in x86."
>
Took your suggestion in V10.
> > +
> > +
> > +#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 instruction scheduling is:
>
> Suggest: "Ideal computation order is"
Took your suggestion in V10.
>
> > + c0 += h;
> > + h *= 32;
> > + h += c0;
> > +
> > + The __asm_reassociation_barrier() macro is a sysdep optional asm
> > + statements to prevents reassosiation that would result in more
> > + instruction interdependencies and worse scheduling. */
>
> This bit is redundant with the description at the top near
> __asm_reassociation_barrier.
Dropped in V10.
>
> > + c0 += h;
> > + __asm_reassociation_barrier("" : "+r"(h) : "r"(c0));
> > + h = h * 32 + c0;
> > + return h;
> > + }
> > +
> > + /* Ideal instruction scheduling is:
>
> Same: "Ideal computation order is"
Took your suggestion in V10.
>
> > + c1 += c0;
> > + h *= 33 * 33;
> > + c0 *= 32;
> > + c1 += c0;
> > + h += c1;
> > +
> > + The __asm_reassociation_barrier() macro is a sysdep optional asm
> > + statements to prevents reassosiation that would result in more
> > + instruction interdependencies and worse scheduling. */
>
> This too is redundant.
Dropped in V10.
>
> > + 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/elf/dl-new-hash.h b/sysdeps/x86/dl-new-hash.h
> > similarity index 77%
> > rename from elf/dl-new-hash.h
> > rename to sysdeps/x86/dl-new-hash.h
> > index b7a91ecc07..dd800265bf 100644
> > --- a/elf/dl-new-hash.h
> > +++ b/sysdeps/x86/dl-new-hash.h
> > @@ -19,19 +19,9 @@
> > #ifndef _DL_NEW_HASH_H
> > #define _DL_NEW_HASH_H 1
>
> No need to define this...
Fixed in V10.
>
> >
> > -#include <stdint.h>
> > -/* For __always_inline. */
> > -#include <sys/cdefs.h>
> > -
> > -static __always_inline uint32_t
> > -__attribute__ ((unused))
> > -_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;
> > -}
> > +#define __asm_reassociation_barrier __asm__
> >
> > +#undef _DL_NEW_HASH_H
>
> ... if it is unconditionally undefined here.
>
> > +#include <sysdeps/generic/dl-new-hash.h>
> >
> > #endif /* dl-new-hash.h */
>
On 18/05/2022 23:08, Noah Goldstein wrote:
> On Tue, May 17, 2022 at 12:12 AM Siddhesh Poyarekar <siddhesh@gotplt.org> wrote:
>>
>> Not sure why, but the series failed to apply on trybot. It's probably a
>> trybot bug because it applied just fine on my up to date copy.
>
> I think it may be related to the fact that earlier versions deleted
> elf/dl-new-hash.h.
>
>
Yeah I think trybot is tripping on a git-style diff with renames, which
patch by itself may not be able to parse. DJ, is this something we
could fix in trybot?
Thanks,
Siddhesh
Siddhesh Poyarekar <siddhesh@gotplt.org> writes:
> Yeah I think trybot is tripping on a git-style diff with renames, which
> patch by itself may not be able to parse. DJ, is this something we
> could fix in trybot?
We changed the apply-patch trybot to use "git apply", we can do the same
for the 32bit trybot.
new file mode 100644
@@ -0,0 +1,114 @@
+/* _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. */
+#include <sys/cdefs.h>
+/* For __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.
+
+ As well, as an architecture specific option we add asm statements
+ to explicitly specifying order of operations to prevent
+ reassosiation 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 reassosiation barries are:
+ x86
+
+ Note it is very unlikely the reassosiation barriers would
+ de-optimize performance on any archictecture 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. */
+
+
+#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 instruction scheduling is:
+ c0 += h;
+ h *= 32;
+ h += c0;
+
+ The __asm_reassociation_barrier() macro is a sysdep optional asm
+ statements to prevents reassosiation that would result in more
+ instruction interdependencies and worse scheduling. */
+ c0 += h;
+ __asm_reassociation_barrier("" : "+r"(h) : "r"(c0));
+ h = h * 32 + c0;
+ return h;
+ }
+
+ /* Ideal instruction scheduling is:
+ c1 += c0;
+ h *= 33 * 33;
+ c0 *= 32;
+ c1 += c0;
+ h += c1;
+
+ The __asm_reassociation_barrier() macro is a sysdep optional asm
+ statements to prevents reassosiation that would result in more
+ instruction interdependencies and worse scheduling. */
+ 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 */
similarity index 77%
rename from elf/dl-new-hash.h
rename to sysdeps/x86/dl-new-hash.h
@@ -19,19 +19,9 @@
#ifndef _DL_NEW_HASH_H
#define _DL_NEW_HASH_H 1
-#include <stdint.h>
-/* For __always_inline. */
-#include <sys/cdefs.h>
-
-static __always_inline uint32_t
-__attribute__ ((unused))
-_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;
-}
+#define __asm_reassociation_barrier __asm__
+#undef _DL_NEW_HASH_H
+#include <sysdeps/generic/dl-new-hash.h>
#endif /* dl-new-hash.h */