* pack-object's try_delta fast path for v2 trees? @ 2013-10-12 3:42 Duy Nguyen 2013-10-12 14:52 ` Nicolas Pitre 2013-10-15 0:19 ` Jeff King 0 siblings, 2 replies; 8+ messages in thread From: Duy Nguyen @ 2013-10-12 3:42 UTC (permalink / raw) To: Nicolas Pitre; +Cc: Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pack-object's try_delta fast path for v2 trees? 2013-10-12 3:42 pack-object's try_delta fast path for v2 trees? Duy Nguyen @ 2013-10-12 14:52 ` Nicolas Pitre 2013-10-15 0:19 ` Jeff King 1 sibling, 0 replies; 8+ messages in thread From: Nicolas Pitre @ 2013-10-12 14:52 UTC (permalink / raw) To: Duy Nguyen; +Cc: Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pack-object's try_delta fast path for v2 trees? 2013-10-12 3:42 pack-object's try_delta fast path for v2 trees? Duy Nguyen 2013-10-12 14:52 ` Nicolas Pitre @ 2013-10-15 0:19 ` Jeff King 2013-10-15 0:49 ` Duy Nguyen 2013-10-15 1:45 ` Nicolas Pitre 1 sibling, 2 replies; 8+ messages in thread From: Jeff King @ 2013-10-15 0:19 UTC (permalink / raw) To: Duy Nguyen; +Cc: Nicolas Pitre, Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pack-object's try_delta fast path for v2 trees? 2013-10-15 0:19 ` Jeff King @ 2013-10-15 0:49 ` Duy Nguyen 2013-10-15 0:54 ` Jeff King 2013-10-15 1:45 ` Nicolas Pitre 1 sibling, 1 reply; 8+ messages in thread From: Duy Nguyen @ 2013-10-15 0:49 UTC (permalink / raw) To: Jeff King; +Cc: Nicolas Pitre, Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pack-object's try_delta fast path for v2 trees? 2013-10-15 0:49 ` Duy Nguyen @ 2013-10-15 0:54 ` Jeff King 0 siblings, 0 replies; 8+ messages in thread From: Jeff King @ 2013-10-15 0:54 UTC (permalink / raw) To: Duy Nguyen; +Cc: Nicolas Pitre, Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pack-object's try_delta fast path for v2 trees? 2013-10-15 0:19 ` Jeff King 2013-10-15 0:49 ` Duy Nguyen @ 2013-10-15 1:45 ` Nicolas Pitre 2013-10-15 1:51 ` Jeff King 1 sibling, 1 reply; 8+ messages in thread From: Nicolas Pitre @ 2013-10-15 1:45 UTC (permalink / raw) To: Jeff King; +Cc: Duy Nguyen, Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pack-object's try_delta fast path for v2 trees? 2013-10-15 1:45 ` Nicolas Pitre @ 2013-10-15 1:51 ` Jeff King 2013-10-15 2:13 ` Nicolas Pitre 0 siblings, 1 reply; 8+ messages in thread From: Jeff King @ 2013-10-15 1:51 UTC (permalink / raw) To: Nicolas Pitre; +Cc: Duy Nguyen, Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: pack-object's try_delta fast path for v2 trees? 2013-10-15 1:51 ` Jeff King @ 2013-10-15 2:13 ` Nicolas Pitre 0 siblings, 0 replies; 8+ messages in thread From: Nicolas Pitre @ 2013-10-15 2:13 UTC (permalink / raw) To: Jeff King; +Cc: Duy Nguyen, Git Mailing List 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 ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2013-10-15 2:13 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-10-12 3:42 pack-object's try_delta fast path for v2 trees? Duy Nguyen 2013-10-12 14:52 ` Nicolas Pitre 2013-10-15 0:19 ` Jeff King 2013-10-15 0:49 ` Duy Nguyen 2013-10-15 0:54 ` Jeff King 2013-10-15 1:45 ` Nicolas Pitre 2013-10-15 1:51 ` Jeff King 2013-10-15 2:13 ` Nicolas Pitre
Code repositories for project(s) associated with this public inbox https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).