blob: 29774c8b26f4aec56115be98f087e46258777ee2 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
/* _dl_new_hash for elf symbol lookup
Copyright (C) 2022-2023 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 */
|
