From: Jeff King <peff@peff.net>
Date: Tue, 22 May 2012 17:01:01 GMT
Subject: Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)
Message-ID: <20120522170101.GA11600@sigill.intra.peff.net>
In-Reply-To: <CACsJy8Dw+mbP+ttTP6gAfX9o4q4NyZgPYpbhS=tket=5fvBXwg@mail.gmail.com>

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.

-Peff