From: Drew Northup Date: Sun, 17 Jul 2011 13:24:51 GMT Subject: Re: Strange O(N^3) behavior in "git filter-branch" 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: > 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