Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)

[Michael Haggerty <mhagger@alum.mit.edu>]

On 05/22/2012 09:37 AM, Jeff King wrote:
> On Tue, May 22, 2012 at 09:15:55AM +0200, Michael Haggerty wrote:
>
>> If it is not too much trouble, please let me know where I can obtain
>> your test repo and what commands you used to get your result.  (Was
>> the local repo already a full clone of the remote, including all 400k
>> references?  How was the remote set up--sharing data or not, local or
>> remote?  Warm or cold disk cache?)
>
> I've put the repo up at:
>
>    https://gist.github.com/raw/2767328/603926240fabb4d3e3abc3c93a1913d91852cc7e/rails.tar.gz
>
> You can reproduce the slow-down with:
>
>    cd rails.git&&
>    git fetch . refs/*:refs/*
>
> which should be a no-op, as we already have all of the refs. I don't
> know if the problem is actually specific to fetch; that was just how I
> noticed it.
>
> When I try it with both 'next' and v1.7.10, I see that the latter is
> much faster.  I did my tests with a warm cache, but the interesting
> number is the CPU time, which is quite different.

I cannot reproduce anything as big as the performance regression that 
you see.  I did find a regression 9.5 s -> 10.1 s caused by

5fa044184 find_containing_dir(): use strbuf in implementation of this 
function

It is fixed by the patch that I just sent to the mailing list [1], which 
sizes the strbuf in that function to strlen(refname) instead of 
PATH_MAX.  Since your experiments suggest that the performance 
regression is related to the size of the repository contents, it could 
be that the same test produces more memory pressure on your system and 
therefore a larger effect.  Please try the patch and tell me if it fixes 
the problem for you.

[1] http://article.gmane.org/gmane.comp.version-control.git/198197

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/