Re: RFC: Flat directory for notes, or fan-out? Both!

From: Jeff King <peff@peff.net>
Date: Feb 10, 2009, 13:16 UTC
Message-ID: <20090210131600.GD17305@coredump.intra.peff.net>
In-Reply-To: <200902100158.46884.bss@iguanasuicide.net>

On Tue, Feb 10, 2009 at 01:58:41AM -0600, Boyd Stephen Smith Jr. wrote:

Show 7 quoted lines

> On Monday 09 February 2009 15:12:06 Johannes Schindelin wrote:
> > So I think it would be a sane plan to do the following when a commit note
> > is requested:
> 
> So, something like a Trie data structure?  I think that is a great way to 
> store fixed-length strings from a limited alphabet with arbitrary data 
> attached.

I don't think a Trie quite makes sense here. We still have to look linearly through each git tree (an artifact of the tree implementation).

You could organize the tree into a deeper, more complex data structure than just a simple fan-out. But remember that traditional data structures are usually trying to save expensive comparisons, and following a pointer is inexpensive. In the case of git trees, though, following a pointer into a subtree is _very_ expensive, since you have to lookup and decompress the object.

So what we do now is read the tree into an associative hash. You could replace the hash with a trie, but it is not really the performance-critical part here. The issue is that without fan-out you have to read the _whole_ tree into the hash. With a constant-sized fanout, you get to divide that work by a constant.

Or did you mean something else entirely?

-Peff