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

[Duy Nguyen <pclouds@gmail.com>]

On Tue, Oct 15, 2013 at 7:19 AM, Jeff King <peff@peff.net> 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.

I see this as pack-objects peformance improvements only. If we could
make pack-objects run like 10% faster (even only with -adf), then it
may be worth trying. The 10% is a total guess though as I haven't
checked how much time we spend in searching deltas.
-- 
Duy