Re: [PATCH] refs.c: Fix slowness with numerous loose refs
- From
David Michael Barr <davidbarr@google.com>
- Date
- Sep 27, 2011, 02:04 UTC
- 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:
Show 84 quoted lines
> 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