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 Tue, May 22, 2012 at 03:28:32PM +0200, Michael Haggerty wrote:

> >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.

That patch drops about a second off of the slow case, but the main
problem still remains. Just to be sure we are both doing the exact same
thing, here is a complete reproduction recipe:


  cd $GIT &&
  git checkout 432ad41e60cedb87ceec446ab034d46a53f5f9d8^ &&
  make &&

  cd $RAILS &&
  time $GIT/bin-wrappers/git fetch . refs/*:refs/* &&

  cd $GIT &&
  git checkout 432ad41e60cedb87ceec446ab034d46a53f5f9d8 &&
  make &&

  cd $RAILS &&
  time $GIT/bin-wrappers/git fetch . refs/*:refs/*


  real    0m9.128s
  user    0m9.369s
  sys     0m0.976s

  real    0m15.926s
  user    0m16.181s
  sys     0m0.984s

I don't think memory pressure is involved. The git process maxes out at
~300M, and this machine has 7.5G available.

I wonder why we are getting different results. Could it be compilation
options? As I mentioned, I compile with -O0, but I got similar results
with -O3.

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at

[Newbies FAQ]     [Linux Kernel Development]     [Free Online Dating]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Free Online Dating]     [Photo]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]     [Linux Resources]

Add to Google