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

[Jeff King <peff@peff.net>]

On Thu, May 24, 2012 at 06:17:45PM -0600, Martin Fick wrote:

> On Monday, May 21, 2012 04:14:17 pm Jeff King wrote:
> > On Mon, May 21, 2012 at 01:45:25PM -0400, Jeff King wrote:
> > Martin, let me know if this improves things for your
> > many-ref cases (and if you are still seeing slowness in
> > your repos with many refs, let me know which operations
> > cause it).
> 
> I have not been ignoring you, I am sorry that I have not 
> replied yet.  Unfortunately, I am having a very hard time 
> getting conclusive tests with my large repo.  I making
> plenty of mistakes in what I think I am testing I believe,
> but also I am having a hard time getting reproducible 
> results so far.  And some tests take quite a while, so it is 
> not always obvious what I might be doing wrong.

No worries. I am pretty confident that the patches I supplied so far are
a good thing whether they help your case or not. So if you come back in
a month and show that they solved all your problems, then great. And if
they don't, then it will just show us what new problems we have to work
on. :)

> Were your tests mostly warm cache tests?

Yes, exclusively warm. And all of the refs were packed, which makes the
warm/cold difference less interesting (it's one 30MB or so file).  I
don't think there's much point in thinking about the performance of 400K
loose refs (which would be absolutely horrific cold-cache on most
traditional filesystems). If you have that many, you would want to keep
the bulk of them packed.

-Peff