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

From: Jeff King <peff@peff.net>
Date: May 22, 2012, 17:33 UTC
Message-ID: <20120522173355.GC11600@sigill.intra.peff.net>
In-Reply-To: <4FBB9480.4010407@alum.mit.edu>

On Tue, May 22, 2012 at 03:28:32PM +0200, Michael Haggerty wrote:

Show 17 quoted lines

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