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

[Nguyen Thai Ngoc Duy <pclouds@gmail.com>]

On Wed, May 23, 2012 at 12:01 AM, Jeff King <peff@peff.net> wrote:
> On Tue, May 22, 2012 at 07:18:00PM +0700, Nguyen Thai Ngoc Duy wrote:
>
>> On Tue, May 22, 2012 at 12:45 AM, Jeff King <peff@peff.net> wrote:
>> > The rails/rails network repository at GitHub (i.e., a master repo with
>> > all of the objects and refs for all of the forks) has about 400K refs,
>> > and has been the usual impetus for me finding and fixing these sorts of
>> > quadratic problems.
>>
>> Off topic and pure speculation. With 400k refs, each one 20 byte in
>> length, the pathname part only can take 7MB. Perhaps packed-refs
>> should learn prefix compressing too, like index v4, to reduce size
>> (and hopefully improve startup speed). Compressing refs/heads/ and
>> refs/tags/ only could gain quite a bit already.
>
> In this case, the packed-refs file is 30MB. Even just gzipping it takes
> it down to 2MB. As far as I know, we don't ever do random access on the
> file, but instead just stream it into memory.

I did not think really hard when I wrote what I wrote. File size is
not really a problem here. In index case, we do expensive sha-1 on the
entire file so size matters. We don't do anything that expensive in
packed-refs (, I think. Should we protect it with some sort of
checksum btw?). gzip can add more computation cost at startup. 30MB is
probably still ok.

Though sending 2MB on the wire is way better than 30MB when we
advertise refs at cloning/fetching.
-- 
Duy