Re: git rebase chokes on directory -> symlink -> directory

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: May 11, 2007, 15:56 UTC
Message-ID: <alpine.LFD.0.98.0705110835230.3986@woody.linux-foundation.org>
In-Reply-To: <7v8xbvew16.fsf@assigned-by-dhcp.cox.net>

On Thu, 10 May 2007, Junio C Hamano wrote:

> 
> And what is wrong in this case is that the unpack-trees tree
> merging code, which is used everywhere in git to do branch
> switching and merges, is way too inefficient.

Yes, it certainly could be speeded up, but on the other hand:

 - it's certainly not really "horribly bad" in most normal operations.

   In merging, it tends to be fast enough, and in checkouts the real 
   expense is checking out the tree, and the unpack-trees part really 
   isn't a big deal.

 - the only case it shows up is really just when you script things, and 
   compare it to just applying a patch, which is fundamnetally easier.

So I think the reason smarter tree merging hasn't gotten the love and attention to make it really a *lot* faster is simply that it's already quite fast enough for most people, and the "rebase using proper merges" is probably the only case where you can really see the difference.

I'd certainly love for the tree unpacking to handle all the "hey, whole sub-tree is identical" cases, but I can also see why it's not getting a lot of traction. It just hasn't been painful enough, and we're already too damn fast.

Fixing the tree unpacking to do the trees in parallel (so that you don't have to shuffle the arrays and take a huge performance hit there) was enough to basically make all normal issues go away.

That said, wouldn't it potentially be quite easy in "unpack_trees_rec()" to just notice when all the trees are identical, and just not recurse at all in that case (or - alternatively - recurse, but on entry, just exit quickly?)

		Linus