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

quoted text
> 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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html