Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)
Jeff King <peff@peff.net> wrote:
Show 13 quoted lines
>On Mon, May 21, 2012 at 12:15:13PM -0600, Martin Fick wrote:
>
>> 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