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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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@xxxxxxxxxxxx
http://softwareswirl.blogspot.com/
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html


[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]