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

On Wed, May 23, 2012 at 12:01 AM, Jeff King [off-list ref] wrote:

On Tue, May 22, 2012 at 07:18:00PM +0700, Nguyen Thai Ngoc Duy wrote:

quoted

On Tue, May 22, 2012 at 12:45 AM, Jeff King [off-list ref] wrote:

quoted

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