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:

  GIT=/path/to/your/git/checkout
  RAILS=/path/to/unpacked/rails.git

  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/*

produces:

  [before]
  real    0m9.128s
  user    0m9.369s
  sys     0m0.976s

  [after]
  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.

-Peff
--
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]