Re: [BUG] fast-import producing very deep tree deltas

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Nov 12, 2007, 20:26 UTC
Message-ID: <alpine.LFD.0.9999.0711121221040.3062@woody.linux-foundation.org>
In-Reply-To: <20071112110354.GP6212@lavos.net>

On Mon, 12 Nov 2007, Brian Downing wrote:

Show 6 quoted lines

> 
>     depths: count 135970 total 120567366 min 0 max 6035 mean 886.72 median 3 std_dev 1653.48
> 
> Needless to say the pack that resulted was just about useless.  Trying to
> repack it resulted in the "counting objects" phase running at about five
> objects per second.

Hmm. Quick hack: increase the delta cache window. The reason (I think) why performance turns glacial with really deep delta chains is that it turns into an O(n^2) thing when you don't hit in the delta cache, and your delta depth is so deep that following a *single* delta chain will flush the cache.

So I bet that making the delta cache bigger will "fix" it. You probably don't have to make it 6000+ entries, but with the *median* being that deep, making it 2k entries should improve it for most cases.

Obviously fastimport should be fixed to not do those insanely deep chains too, but it might be a good idea to at least make the delta cache a bit bigger by default, and perhaps have some config option for setting it.

		Linus