[PATCH] refs.c: Fix slowness with numerous loose refs

[David Barr <davidbarr@google.com>]

Martin Fick reported:
 OK, I have found what I believe is another performance
 regression for large ref counts (~100K).

 When I run git br on my repo which only has one branch, but
 has ~100K refs under ref/changes (a gerrit repo), it takes
 normally 3-6mins depending on whether my caches are fresh or
 not.  After bisecting some older changes, I noticed that
 this ref seems to be where things start to get slow:
 v1.5.2-rc0~21^2 (refs.c: add a function to sort a ref list,
 rather then sorting on add) (Julian Phillips, Apr 17, 2007)

Martin Fick observed that sort_refs_lists() was called almost
as many times as there were loose refs.

Julian Phillips commented:
 Back when I made that change, I failed to notice that get_ref_dir
 was recursive for subdirectories ... sorry ...

 Hopefully this should speed things up. My test repo went from
 ~17m user time, to ~2.5s.
 Packing still make things much faster of course.

Martin Fick acked:
 Excellent!  This works (almost, in my refs.c it is called
 sort_ref_list, not sort_refs_list).  So, on the non garbage
 collected repo, git branch now takes ~.5s, and in the
 garbage collected one it takes only ~.05s!

[db: summarised transcript, rewrote patch to fix callee not callers]

[attn jch: patch applies to maint]

Analyzed-by: Martin Fick <mfick@codeaurora.org>
Inspired-by: Julian Phillips <julian@quantumfyre.co.uk>
Acked-by: Martin Fick <mfick@codeaurora.org>
Signed-off-by: David Barr <davidbarr@google.com>
---
 refs.c |   14 ++++++++++----
 1 files changed, 10 insertions(+), 4 deletions(-)

diff --git a/refs.c b/refs.c
index 4c1fd47..e40a09c 100644
--- a/refs.c
+++ b/refs.c
@@ -255,8 +255,8 @@ static struct ref_list *get_packed_refs(const char *submodule)
 	return refs->packed;
 }
 
-static struct ref_list *get_ref_dir(const char *submodule, const char *base,
-				    struct ref_list *list)
+static struct ref_list *walk_ref_dir(const char *submodule, const char *base,
+				     struct ref_list *list)
 {
 	DIR *dir;
 	const char *path;
@@ -299,7 +299,7 @@ static struct ref_list *get_ref_dir(const char *submodule, const char *base,
 			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
-				list = get_ref_dir(submodule, ref, list);
+				list = walk_ref_dir(submodule, ref, list);
 				continue;
 			}
 			if (submodule) {
@@ -319,7 +319,13 @@ static struct ref_list *get_ref_dir(const char *submodule, const char *base,
 		free(ref);
 		closedir(dir);
 	}
-	return sort_ref_list(list);
+	return list;
+}
+
+static struct ref_list *get_ref_dir(const char *submodule, const char *base,
+				    struct ref_list *list)
+{
+	return sort_ref_list(walk_ref_dir(submodule, base, list));
 }
 
 struct warn_if_dangling_data {
-- 
1.7.5.75.g69330