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

Jeff King [off-list ref] wrote:

On Mon, May 21, 2012 at 12:15:13PM -0600, Martin Fick wrote:

quoted

Of course, we use Gerrit, so features tend to be called 
changes and each change may get many revisions (patchsets), 
so all of these get refs, but I think that it might be wrong 
to consider that out of the ordinary anymore.  After all, 
should a version control system such as git not support 100K 
revisions of features developed independently on separate 
branches (within Gerrit or not)?  100K is not really that 
many when you consider a large project.  Even without 
Gerrit, if someone wanted to track that many features 
(likely over a few years), they will probably use up tons of 
refs.  

...

Anyway, my point is that we don't even have to talk about "reasonable"
or "absurd". Git should be fast even on absurd cases, because 99% of
the work has already been done, and the last 1% is easy.

I hope you are right, but I don't quite completely share your optimism.  Some of that last 1% is perhaps last exactly because it is hard.  More specificaly, I am talking about the git protocol's ref advertisement on connection.  This has been considered a known issue for many years, yet it has not been fixed because it is hard to fix since it requires breaking the protocol in a non backwards compatible way.  I would be delighted if you had an easy fix for this rather fundamental ref scaling issue? We talked with Junio and Shawn and they agreed that it would be reasonable to put forward a proposal which does break backwards compatibility. So if there is a chance that there still may be another way, I hope it is found before this gets underway (no, I don't really expect that to happen),

-Martin

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