From: David Michael Barr <davidbarr@google.com>
Date: Tue, 27 Sep 2011 02:04:43 GMT
Subject: Re: [PATCH] refs.c: Fix slowness with numerous loose refs
Message-ID: <CAFfmPPMx9_nRE2Zfg2g0hwzybWDPJARc6LCHbSK8y-uZWQCZqQ@mail.gmail.com>
In-Reply-To: <1317085283-33943-1-git-send-email-davidbarr@google.com>

+cc Shawn O. Pearce

I used the following to generate a test repo shaped like
a gerrit mirror with unpacked refs (10k, because life is too short for
100k tests):

cd test.git
git init
touch empty
git add empty
git commit -m 'empty'
REV=`git rev-parse HEAD`
for ((d=0;d<100;++d)); do
 for ((n=0;n<100;++n)); do
  let r=n*100+d
  mkdir -p .git/refs/changes/$d/$r
  echo $REV > .git/refs/changes/$d/$r/1
 done
done
time git branch xyz

With warm caches...

Git 1.7.6.4:
real	0m8.232s
user	0m7.842s
sys	0m0.385s

Git 1.7.6.4, with patch below:
real	0m0.394s
user	0m0.069s
sys	0m0.324s

On Tue, Sep 27, 2011 at 11:01 AM, David Barr <davidbarr@google.com> wrote:
> 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
>
>



-- 

David Barr | Software Engineer | davidbarr@google.com | 614-3438-8348