On Tue, Feb 10, 2009 at 01:58:41AM -0600, Boyd Stephen Smith Jr. wrote: > 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@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
