On Mon, 2011-07-18 at 01:59 -0700, Jakub Narebski wrote: > Drew Northup <drew.northup@xxxxxxxxx> writes: > > > On Sat, 2011-07-16 at 07:26 +0200, Michael Haggerty wrote: > > > > > Currently, the loose ref cache is stored as a single linked list, so > > > there is no easy way to populate part of it now and part of it later. > > > So with the current data structure, the loose refs cache is > > > all-or-nothing. It would be possible to avoid filling it if there are > > > not replace references, but if there is even one loose replace reference > > > then the whole refs tree would have to be crawled. Implementing this > > > variation is alternative 4 from the early email. > > > > > > More flexible would be to change the way the loose ref cache is stored > > > from a linked list into a tree (probably mirroring the directory tree). > > > > Given the potential for high performance inherent with trees, why mix > > metaphors like this? What would the gain be? > > Did you mean: "why linked list"? I _guess_ that it is most probably > because linked list is simpler and better known data structure than > non-binary tree. No, that I can compute. I was asking why mix tree metaphors (pure binary, R/B, and 234 being probably the most common kinds for the data structure; and filesystem "trees"). In my mind I was thinking of SHA1sums as the keys (for some reason that doesn't occur to me right now) and thought perhaps it was worth becoming enlightened (or something). Perhaps I should have looked harder in my mail queue for the patch referenced. > > What is needed I think is something like trie[1], but with path > components and not letters stored in trie nodes. > > [1]: http://en.wikipedia.org/wiki/Trie Obviously, there are other "tree" structures. That's one I probably should have thought of earlier. -- -Drew Northup ________________________________________________ "As opposed to vegetable or mineral error?" -John Pescatore, SANS NewsBites Vol. 12 Num. 59 -- 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