From: Jakub Narebski Date: Mon, 18 Jul 2011 08:59:19 GMT Subject: Re: Strange O(N^3) behavior in "git filter-branch" Message-ID: In-Reply-To: <1310909091.21563.23.camel@drew-northup.unet.maine.edu> Drew Northup 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. 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 > > If this were done, then it would be possible to populate the cache > > lazily, only crawling the part of the refs tree that is needed for a > > particular call of for_each_ref() and reusing any part of the cache that > > is already in memory. > > Is this the argument for directory structure mirroring? -- Jakub Narębski