Re: Strange O(N^3) behavior in "git filter-branch"

[Jakub Narebski <jnareb@gmail.com>]

Drew Northup <drew.northup@maine.edu> 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