Re: pack-object's try_delta fast path for v2 trees?
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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: pack-object's try_delta fast path for v2 trees?
On Tue, Oct 15, 2013 at 7:19 AM, Jeff King p...@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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: pack-object's try_delta fast path for v2 trees?
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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: pack-object's try_delta fast path for v2 trees?
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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: pack-object's try_delta fast path for v2 trees?
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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: pack-object's try_delta fast path for v2 trees?
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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: pack-object's try_delta fast path for v2 trees?
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 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
