Re: [PATCH/RFC] reverse the pack-objects delta window logic

From: Junio C Hamano <junkio@cox.net>
Date: Apr 27, 2006, 05:04 UTC
Message-ID: <7vejzjmwwr.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <Pine.LNX.4.64.0604262210120.18520@localhost.localdomain>

Nicolas Pitre <nico@cam.org> writes:

Show 7 quoted lines

>> And actually I'm not sure how to solve that without walking the tree 
>> up to the top each time, which I want to avoid as much as possible.
>
> Well, that seems to be unavoidable.
>
> Reversing the window logic isn't that much of a good idea after all.
> ...

Show 8 quoted lines

> Then there is the possibility of having a delta "branch" with maximum 
> depth meaning that the trunk for that branch may not be deltified. But 
> if a later objects to come does constitute a better delta base for the 
> object in the middle of that branch then the branch will be broken in 
> the middle to be transplanted onto the new base as explained previously.  
> Which means that the initial trunk no longer has a maximum depth and some
> objects that were skipped because of the depth limit could now have been
> tested, leading to suboptimal delta matching.

Good analysis, and I tend to agree with your conclusion.

BTW, Geert mentioned on the #git channel that about half the filepair git-pack-objects asks diff_delta() to try have long sequences of matching bytes at the beginning and at the end. It might be worthwhile if we can take an advantage of it, whichever delta algorithm we would use.