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

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 [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.

-Peff