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

From: "Shawn O. Pearce" <[email-masked]>
Date: Tue, 13 Nov 2007 03:53:07 -0500

Brian Downing <[email-masked]> wrote:
> I've happened upon a case where fast-import produces deep tree deltas.
> How deep?  Really deep.  6035 entries deep to be precise for this case:
> 
>     depths: count 135970 total 120567366 min 0 max 6035 mean 886.72 median 3 std_dev 1653.48
> 
>     27b8a20bdf39fecd917e8401d3499013e49449d0 tree   32 99609547 6035 0000000000000000000000000000000000000000
> 
> This was with git-fast-import from 'next' as of a couple days ago,
> run with the default options (no --depth passed in).
> 
> 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.

Heh.

I think what's happening here is your active branch cache isn't
big enough.  We're swapping out the branch and thus recycling the
tree information (struct tree_content) back into the free pool.
When we later reload the tree we set the delta_depth to 0 but we
kept the tree we just reloaded as a delta base.

So if the tree we reloaded was already at the maximum we wouldn't
know it and make the new tree a delta.  Multiply the number of times
the branch cache has to swap out the tree times max_depth (10) and
you get the maximum delta depth of a tree created by fast-import.
Given your above data of 6035 I'm guessing your active branch cache
had to swap the branch out 603/604 times during this import.

I think the fix is going to involve caching the depth within struct
object_entry so we can restore it when the tree is reloaded.

-- 
Shawn.