[PATCH] refs.c: get_ref_cache: use a bucket hash
- From
Andreas Krey <a.krey@gmx.de>
- Date
- Mar 16, 2015, 14:20 UTC
- Message-ID
- <20150316142026.GJ7847@inner.h.apk.li>
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 <a.krey@gmx.de> ---
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