Re: pack-object's try_delta fast path for v2 trees?

[Nicolas Pitre <nico@fluxnic.net>]

On Mon, 14 Oct 2013, Jeff King wrote:

> On Sat, Oct 12, 2013 at 10:42:17AM +0700, Nguyen Thai Ngoc Duy wrote:
> 
> > Just wondering if this has been considered and dropped before.
> > Currently we use try_delta() for every object including trees. But
> > trees are special. All tree entries must be unique and sorted. That
> > helps simplify diff algorithm, as demonstrated by diff_tree() and
> > pv4_encode_tree(). A quick and dirty test with test-delta shows that
> > tree_diff only needs half the time of diff_delta(). As trees account
> > for like half the objects in a repo, speeding up delta search might
> > help performance, I think.
> 
> No, as far as I know, it is a novel idea. When we were discussing commit
> caching a while back, Shawn suggested slicing trees on boundaries and
> store delta instructions that were pure "change this entry", "add this
> entry", and "delete this entry" chunks. The deltas might end up a little
> bigger, but if the reader knew the writer had sliced in this way, it
> could get a packv4-style cheap tree-diff, while remaining backwards
> compatible with implementations that just blindly reassemble the buffer
> from delta instructions.
> 
> I didn't get far enough to try it, but doing what you propose would be
> the first step. Now that packv4 is more of a reality, it may not be
> worth pursuing, though.

The "easy" way to produce pack v2 tree objects from a pack v4 would be 
exactly that: take the pack v4 tree encoding and do a straight 
translation into delta encoding using the base from which the most 
entries are copied from.


Nicolas