Skip to content

Commit 8af27e1

Browse files
Eric Dumazetmichal42
Eric Dumazet
authored and
michal42
committed
fixdep: use hash table instead of a single array
I noticed fixdep uses ~2% of cpu time in kernel build, in function use_config() fixdep spends a lot of cpu cycles in linear searches in its internal string array. With about 400 stored strings per dep file, this begins to be noticeable. Convert fixdep to use a hash table. kbuild results on my x86_64 allmodconfig Before patch : real 10m30.414s user 61m51.456s sys 8m28.200s real 10m12.334s user 61m50.236s sys 8m30.448s real 10m42.947s user 61m50.028s sys 8m32.380s After: real 10m8.180s user 61m22.506s sys 8m32.384s real 10m35.039s user 61m21.654s sys 8m32.212s real 10m14.487s user 61m23.498s sys 8m32.312s Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> Signed-off-by: Michal Marek <mmarek@suse.cz>
1 parent d63f6d1 commit 8af27e1

1 file changed

Lines changed: 61 additions & 48 deletions

File tree

‎scripts/basic/fixdep.c‎

Lines changed: 61 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -138,38 +138,36 @@ static void print_cmdline(void)
138138
printf("cmd_%s := %s\n\n", target, cmdline);
139139
}
140140

141-
char * str_config = NULL;
142-
int size_config = 0;
143-
int len_config = 0;
141+
struct item {
142+
struct item *next;
143+
unsigned int len;
144+
unsigned int hash;
145+
char name[0];
146+
};
144147

145-
/*
146-
* Grow the configuration string to a desired length.
147-
* Usually the first growth is plenty.
148-
*/
149-
static void grow_config(int len)
150-
{
151-
while (len_config + len > size_config) {
152-
if (size_config == 0)
153-
size_config = 2048;
154-
str_config = realloc(str_config, size_config *= 2);
155-
if (str_config == NULL)
156-
{ perror("fixdep:malloc"); exit(1); }
157-
}
158-
}
148+
#define HASHSZ 256
149+
static struct item *hashtab[HASHSZ];
159150

151+
static unsigned int strhash(const char *str, unsigned int sz)
152+
{
153+
/* fnv32 hash */
154+
unsigned int i, hash = 2166136261U;
160155

156+
for (i = 0; i < sz; i++)
157+
hash = (hash ^ str[i]) * 0x01000193;
158+
return hash;
159+
}
161160

162161
/*
163162
* Lookup a value in the configuration string.
164163
*/
165-
static int is_defined_config(const char * name, int len)
164+
static int is_defined_config(const char *name, int len, unsigned int hash)
166165
{
167-
const char * pconfig;
168-
const char * plast = str_config + len_config - len;
169-
for ( pconfig = str_config + 1; pconfig < plast; pconfig++ ) {
170-
if (pconfig[ -1] == '\n'
171-
&& pconfig[len] == '\n'
172-
&& !memcmp(pconfig, name, len))
166+
struct item *aux;
167+
168+
for (aux = hashtab[hash % HASHSZ]; aux; aux = aux->next) {
169+
if (aux->hash == hash && aux->len == len &&
170+
memcmp(aux->name, name, len) == 0)
173171
return 1;
174172
}
175173
return 0;
@@ -178,54 +176,69 @@ static int is_defined_config(const char * name, int len)
178176
/*
179177
* Add a new value to the configuration string.
180178
*/
181-
static void define_config(const char * name, int len)
179+
static void define_config(const char *name, int len, unsigned int hash)
182180
{
183-
grow_config(len + 1);
181+
struct item *aux = malloc(sizeof(*aux) + len);
184182

185-
memcpy(str_config+len_config, name, len);
186-
len_config += len;
187-
str_config[len_config++] = '\n';
183+
if (!aux) {
184+
perror("fixdep:malloc");
185+
exit(1);
186+
}
187+
memcpy(aux->name, name, len);
188+
aux->len = len;
189+
aux->hash = hash;
190+
aux->next = hashtab[hash % HASHSZ];
191+
hashtab[hash % HASHSZ] = aux;
188192
}
189193

190194
/*
191195
* Clear the set of configuration strings.
192196
*/
193197
static void clear_config(void)
194198
{
195-
len_config = 0;
196-
define_config("", 0);
199+
struct item *aux, *next;
200+
unsigned int i;
201+
202+
for (i = 0; i < HASHSZ; i++) {
203+
for (aux = hashtab[i]; aux; aux = next) {
204+
next = aux->next;
205+
free(aux);
206+
}
207+
hashtab[i] = NULL;
208+
}
197209
}
198210

199211
/*
200212
* Record the use of a CONFIG_* word.
201213
*/
202-
static void use_config(char *m, int slen)
214+
static void use_config(const char *m, int slen)
203215
{
204-
char s[PATH_MAX];
205-
char *p;
216+
unsigned int hash = strhash(m, slen);
217+
int c, i;
206218

207-
if (is_defined_config(m, slen))
219+
if (is_defined_config(m, slen, hash))
208220
return;
209221

210-
define_config(m, slen);
211-
212-
memcpy(s, m, slen); s[slen] = 0;
222+
define_config(m, slen, hash);
213223

214-
for (p = s; p < s + slen; p++) {
215-
if (*p == '_')
216-
*p = '/';
224+
printf(" $(wildcard include/config/");
225+
for (i = 0; i < slen; i++) {
226+
c = m[i];
227+
if (c == '_')
228+
c = '/';
217229
else
218-
*p = tolower((int)*p);
230+
c = tolower(c);
231+
putchar(c);
219232
}
220-
printf(" $(wildcard include/config/%s.h) \\\n", s);
233+
printf(".h) \\\n");
221234
}
222235

223-
static void parse_config_file(char *map, size_t len)
236+
static void parse_config_file(const char *map, size_t len)
224237
{
225-
int *end = (int *) (map + len);
238+
const int *end = (const int *) (map + len);
226239
/* start at +1, so that p can never be < map */
227-
int *m = (int *) map + 1;
228-
char *p, *q;
240+
const int *m = (const int *) map + 1;
241+
const char *p, *q;
229242

230243
for (; m < end; m++) {
231244
if (*m == INT_CONF) { p = (char *) m ; goto conf; }
@@ -265,7 +278,7 @@ static int strrcmp(char *s, char *sub)
265278
return memcmp(s + slen - sublen, sub, sublen);
266279
}
267280

268-
static void do_config_file(char *filename)
281+
static void do_config_file(const char *filename)
269282
{
270283
struct stat st;
271284
int fd;

0 commit comments

Comments
 (0)