[PATCH 1/3] modprobe: use hash table for module entry database
Timo Teräs
timo.teras at iki.fi
Sat Jun 18 15:56:46 UTC 2011
We get a lot of entries there, and lookups are done many, many
times. This gives a significant performance improvement.
Signed-off-by: Timo Teräs <timo.teras at iki.fi>
---
modutils/modprobe.c | 13 ++++++++++---
1 files changed, 10 insertions(+), 3 deletions(-)
diff --git a/modutils/modprobe.c b/modutils/modprobe.c
index 678f4be..b3767ac 100644
--- a/modutils/modprobe.c
+++ b/modutils/modprobe.c
@@ -157,8 +157,10 @@ struct module_entry { /* I'll call it ME. */
llist_t *deps; /* strings. modules we depend on */
};
+#define DB_HASH_SIZE 256
+
struct globals {
- llist_t *db; /* MEs of all modules ever seen (caching for speed) */
+ llist_t *db[DB_HASH_SIZE]; /* MEs of all modules ever seen (caching for speed) */
llist_t *probes; /* MEs of module(s) requested on cmdline */
char *cmdline_mopts; /* module options from cmdline */
int num_unresolved_deps;
@@ -195,9 +197,14 @@ static struct module_entry *helper_get_module(const char *module, int create)
char modname[MODULE_NAME_LEN];
struct module_entry *e;
llist_t *l;
+ unsigned int hash = 5381, i;
filename2modname(module, modname);
- for (l = G.db; l != NULL; l = l->link) {
+ for (i = 0; modname[i]; i++)
+ hash = ((hash << 5) + hash) + modname[i];
+ hash %= DB_HASH_SIZE;
+
+ for (l = G.db[hash]; l != NULL; l = l->link) {
e = (struct module_entry *) l->data;
if (strcmp(e->modname, modname) == 0)
return e;
@@ -207,7 +214,7 @@ static struct module_entry *helper_get_module(const char *module, int create)
e = xzalloc(sizeof(*e));
e->modname = xstrdup(modname);
- llist_add_to(&G.db, e);
+ llist_add_to(&G.db[hash], e);
return e;
}
--
1.7.1
More information about the busybox
mailing list