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

From: Drew Northup <drew.northup@maine.edu>
Date: Jul 17, 2011, 13:24 UTC
Message-ID: <1310909091.21563.23.camel@drew-northup.unet.maine.edu>
In-Reply-To: <4E212113.6000906@alum.mit.edu>

On Sat, 2011-07-16 at 07:26 +0200, Michael Haggerty wrote:

Show 10 quoted lines

> 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?

>  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?

-- 
-Drew Northup
________________________________________________
"As opposed to vegetable or mineral error?"
-John Pescatore, SANS NewsBites Vol. 12 Num. 59