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

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

[Duy Nguyen]

Hi,

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.
-- 
Duy

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

[Nicolas Pitre]

On Sat, 12 Oct 2013, Duy Nguyen wrote:

> Hi,
> 
> 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.

Fortaking advantage of the sorted nature of tree objects, you need to 
actually parse those objects to determine tree entry boundaries.  The 
delta diff code doesn't parse anything and simply do a search into a 
binary buffer which may or may not end up slicing that buffer on actual 
tree entry boundaries.

So this could help somewhat, however the need for pre-parsing those tree 
objects is probably going to counter-balance all the performance gain 
you might get.

I think the potential for improvements would be greater by moving to 
pack v4 (when the right algorithm is in place that is).  Eventually the 
proper pack v4 tree delta diffing code could be made to serve the pack 
v2 case as well.


Nicolas

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

[Jeff King]

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

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

[Duy Nguyen]

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

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

[Jeff King]

On Tue, Oct 15, 2013 at 07:49:57AM +0700, Nguyen Thai Ngoc Duy wrote:

> 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.

For "repack -ad", generally we don't spend that much time on deltas. It
depends what your pre-repack state is, of course, but I find that most
of the time goes to "counting objects". With "-adf", I would guess that
we easily spend something like 95% of the time on compressing for a
large repository (just try "repack -adf" on the kernel; even with 8
cores it's a half hour or more on my machine, versus about 25 seconds to
count the objects).

So I think you could potentially get a lot of speedup for the "-adf"
case (and likewise "git gc --aggressive").

-Peff

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

[Nicolas Pitre]

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

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

[Jeff King]

On Mon, Oct 14, 2013 at 09:45:12PM -0400, Nicolas Pitre wrote:

> > 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.

Yeah, that makes a lot of sense.

By the way, I'm sorry I haven't looked more carefully at the packv4
patches yet. I am excited about it, but I've just got a long queue of
other things (and because it's big and challenging, it's easy to put
off).

One of the things that makes me most nervous about switching to it on
the server side is that we'll have packv2-only clients for a while, and
I worry that converting to v2 on the fly is going to end up costing a
lot (even with clever tricks like this, you still have to pay the cost
to zlib deflate each item). But even if it is slow, the sooner we have
packv4 readers, the sooner the clocks start ticking for it being a
reasonable decision for a big server provider to switch.

-Peff

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

[Nicolas Pitre]

On Mon, 14 Oct 2013, Jeff King wrote:

> By the way, I'm sorry I haven't looked more carefully at the packv4
> patches yet. I am excited about it, but I've just got a long queue of
> other things (and because it's big and challenging, it's easy to put
> off).

;-)

While I consider the format pretty much established at this point, it 
still has some way to go on the algorithmic side of things.  So there is 
certainly room for more people toying with the code.

> One of the things that makes me most nervous about switching to it on
> the server side is that we'll have packv2-only clients for a while, and
> I worry that converting to v2 on the fly is going to end up costing a
> lot (even with clever tricks like this, you still have to pay the cost
> to zlib deflate each item). But even if it is slow, the sooner we have
> packv4 readers, the sooner the clocks start ticking for it being a
> reasonable decision for a big server provider to switch.

Well... of course this depends.  What pack v4 brings is super fast tree 
walking and object enumeration.  We're not there yet with the current 
code, but in theory this is conceptually cheaper with pack v4.  
Therefore operations such as partial clones or updates are meant to be 
much faster in the preparation phase which should compensate for the 
deflate cost.

Yet a big server could store both v2 and v4 in parallel if disk space is 
not an issue, and a modified git could lookup the alternate version of 
an object before transcoding it.


Nicolas