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

On Tue, May 22, 2012 at 12:45 AM, Jeff King [off-list ref] 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.
-- 
Duy