Re: Git is not scalable with too many refs/*

From: Jeff King <peff@peff.net>
Date: Jun 10, 2011, 20:35 UTC
Message-ID: <20110610203545.GA2564@sigill.intra.peff.net>
In-Reply-To: <BANLkTi=4zfO5jKKzbncJk7ihcoHX7Rst4Q@mail.gmail.com>

On Fri, Jun 10, 2011 at 12:41:39PM -0700, Shawn O. Pearce wrote:

Show 10 quoted lines

> Not really.
> 
> The queue isn't sorting by SHA-1. Its sorting by commit timestamp,
> descending. Those aren't pre-hashed. The O(N^2) insertion is because
> the code is trying to find where this commit belongs in the list of
> commits as sorted by commit timestamp.
> 
> There are some priority queue datastructures designed for this sort of
> work, e.g. a calendar queue might help. But its not as simple as a 1
> byte trie.

All you really need is a heap-based priority queue, which gives O(lg n) insertion and popping (and O(1) peeking at the top). I even wrote one and posted it recently (I won't dig up the reference, but I posted it elsewhere in this thread, I think).

The problem is that many parts of the code assume that commit_list is a linked list and do fast iterations, or even splicing. It's nothing you couldn't get around with some work, but it turns out to involve a lot of code changes.

-Peff