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

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 [off-list ref]
Inspired-by: Julian Phillips [off-list ref]
Acked-by: Martin Fick <redacted>
Signed-off-by: David Barr <redacted>
---
 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