From: Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Date: Tue, 22 May 2012 12:18:00 GMT
Subject: Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)
Message-ID: <CACsJy8Dw+mbP+ttTP6gAfX9o4q4NyZgPYpbhS=tket=5fvBXwg@mail.gmail.com>
In-Reply-To: <20120521174525.GA22643@sigill.intra.peff.net>

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