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

[Jeff King <peff@peff.net>]

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.

-Peff