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

[Martin Fick <mfick@codeaurora.org>]

On Thursday, May 24, 2012 06:39:20 pm Jeff King wrote:
> On Thu, May 24, 2012 at 06:17:45PM -0600, Martin Fick 
wrote:
> > 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.

Mostly true, except for one strange case still I think?

When cloning a gerrit repo, users to not get the changes 
since they are not under refs/heads but refs/changes.  So 
later, if they choose to fetch refs/changes/*, all of those
new incoming refs are loose.  Yes, someone should pack those 
refs right away, but I think it actually churns the hell out 
of my disk and takes a significant amount of time during the 
initial fetch.  I am not certain about this, and the 
behavior may depend on the filesystem in use, but I think 
that this time might even be asynchronous (journals and 
all), it feels like my disk keeps churning for a while even 
after this is over.  I believe that this might still be the 
worst case left with refs, and it can be pretty bad,

-Martin

-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum