Re: Git is not scalable with too many refs/*

[Martin Fick <mfick@codeaurora.org>]

On Wednesday, September 28, 2011 08:19:16 pm Julian Phillips 
wrote:
> On Wed, 28 Sep 2011 19:37:18 -0600, Martin Fick wrote:
> > On Wednesday 28 September 2011 18:59:09 Martin Fick 
wrote:
> >> Julian Phillips <julian@quantumfyre.co.uk> wrote:
> -- snip --
> 
> >> I've created a test repo with ~100k refs/changes/...
> >> style refs, and ~40000 refs/heads/... style refs, and
> >> checkout can walk the list of ~140k refs seven times
> >> in 85ms user time including doing whatever other
> >> processing is needed for checkout. The real time is
> >> only 114ms - but then my test repo has no real data
> >> in.
> > 
> > If I understand what you are saying, it sounds like you
> > do not have a very good test case. The amount of time
> > it takes for checkout depends on how long it takes to
> > find a ref with the sha1 that you are on. If that sha1
> > is so early in the list of refs that it only took you
> > 7 traversals to find it, then that is not a very good
> > testcase. I think that you should probably try making
> > an orphaned ref (checkout a detached head, commit to
> > it), that is probably the worst testcase since it
> > should then have to search all 140K refs to eventually
> > give up.
> > 
> > Again, if I understand what you are saying, if it took
> > 85ms for 7 traversals, then it takes approximately
> > 10ms per traversal, that's only 100/s! If you have to
> > traverse it 140K times, that should work out to 1400s
> > ~ 23mins.
> 
> Well, it's no more than 10ms per traversal - since the
> rest of the work presumably takes some time too ...
> 
> However, I had forgotten to make the orphaned commit as
> you suggest - and then _bang_ 7N^2, it tries seven
> different variants of each ref (which is silly as they
> are all fully qualified), and with packed refs it has to
> search for them each time, all to turn names into hashes
> that we already know to start with.
> 
> So, yes - it is that list traversal.
> 
> Does the following help?
> 
> diff --git a/builtin/checkout.c b/builtin/checkout.c
> index 5e356a6..f0f4ca1 100644
> --- a/builtin/checkout.c
> +++ b/builtin/checkout.c
> @@ -605,7 +605,7 @@ static int
> add_one_ref_to_rev_list_arg(const char *refname,
>                                         int flags,
>                                         void *cb_data)
>   {
> -       add_one_rev_list_arg(cb_data, refname);
> +       add_one_rev_list_arg(cb_data,
> strdup(sha1_to_hex(sha1))); return 0;
>   }


Yes, but in some strange ways. :)

First, let me clarify that all the tests here involve your 
"sort fix" from 2 days ago applied first.

In the packed ref repo, it brings the time down to about 
~10s (from > 5 mins).  In the unpacked ref repo, it brings 
it down to about the same thing ~10s, but it was only 
starting at about ~20s.

So, I have to ask, what does that change do, I don't quite 
understand it?  Does it just do only one lookup per ref by 
normalizing it?  Is the list still being traversed, just 
about 7 time less now?  Should the packed_ref list simply be 
put in an array which could be binary searched instead, it 
is a fixed list once loaded, no?  

I prototyped a packed_ref implementation using the hash.c 
provided in the git sources and it seemed to speed a 
checkout up to almost instantaneous, but I was getting a few 
collisions so the implementation was not good enough.  That 
is when I started to wonder if an array wouldn't be better 
in this case?



Now I also decided to go back and test a noop fetch (a 
refetch) of all the changes (since this use case is still 
taking way longer than I think it should, even with the 
submodule fix posted earlier).  Up until this point, even 
the sorting fix did not help.  So I tried it with this fix.  
In the unpackref case, it did not seem to change (2~4mins).  
However, in the packed ref change (which was previously also 
about 2-4mins), this now only takes about 10-15s!

Any clues as to why the unpacked refs would still be so slow 
on noop fetches and not be sped up by this?


-Martin


-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum