[PATCH] refs.c: get_ref_cache: use a bucket hash
From: Andreas Krey <hidden>
Date: 2016-06-15 23:04:10
Subsystem:
the rest · Maintainer:
Linus Torvalds
get_ref_cache used a linear list, which obviously is O(n^2). Use a fixed bucket hash which just takes a factor of 100000 (~ 317^2) out of the n^2 - which is enough. Signed-off-by: Andreas Krey <redacted> --- This brings 'git clean -ndx' times down from 17 minutes to 11 seconds on one of our workspaces (which accumulated a lot of ignored directories). Actuallly using adaptive hashing or other structures seems overkill. refs.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-)
diff --git a/refs.c b/refs.c
index e23542b..8198d9e 100644
--- a/refs.c
+++ b/refs.c@@ -982,6 +982,8 @@ struct packed_ref_cache { struct stat_validity validity; }; +#define REF_CACHE_HASH 317 + /* * Future: need to be in "struct repository" * when doing a full libification.
@@ -996,7 +998,7 @@ static struct ref_cache { * is initialized correctly. */ char name[1]; -} ref_cache, *submodule_ref_caches; +} ref_cache, *submodule_ref_caches[REF_CACHE_HASH]; /* Lock used for the main packed-refs file: */ static struct lock_file packlock;
@@ -1065,18 +1067,19 @@ static struct ref_cache *create_ref_cache(const char *submodule) */ static struct ref_cache *get_ref_cache(const char *submodule) { - struct ref_cache *refs; + struct ref_cache *refs, **bucketp; + bucketp = submodule_ref_caches + strhash(submodule) % REF_CACHE_HASH; if (!submodule || !*submodule) return &ref_cache; - for (refs = submodule_ref_caches; refs; refs = refs->next) + for (refs = *bucketp; refs; refs = refs->next) if (!strcmp(submodule, refs->name)) return refs; refs = create_ref_cache(submodule); - refs->next = submodule_ref_caches; - submodule_ref_caches = refs; + refs->next = *bucketp; + *bucketp = refs; return refs; }
--
2.3.2.223.g7a9409c