{"thread":{"id":"50862","subject":"[PATCH] blame.c: don't drop origin blobs as eagerly","startedAt":"2019-04-02T11:57:15Z","lastAt":"2019-04-03T12:32:35Z","messageCount":8,"participants":["David Kastrup","Junio C Hamano","Duy Nguyen","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"372977","messageId":"20190402115625.21427-1-dak@gnu.org","threadId":"50862","inReplyTo":null,"subject":"[PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2019-04-02T11:56:25Z","receivedAt":"2019-04-02T11:57:15Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"When a parent blob already has chunks queued up for blaming, dropping\nthe blob at the end of one blame step will cause it to get reloaded\nright away, doubling the amount of I/O and unpacking when processing a\nlinear history.\n\nKeeping such parent blobs in memory seems like a reasonable optimization\nthat should incur additional memory pressure mostly when processing the\nmerges from old branches.\n\nSigned-off-by: David Kastrup \n---\n blame.c | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/blame.c b/blame.c\nindex 5c07dec190..c11c516921 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -1562,7 +1562,8 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n \t}\n \tfor (i = 0; i < num_sg; i++) {\n \t\tif (sg_origin[i]) {\n-\t\t\tdrop_origin_blob(sg_origin[i]);\n+\t\t\tif (!sg_origin[i]->suspects)\n+\t\t\t\tdrop_origin_blob(sg_origin[i]);\n \t\t\tblame_origin_decref(sg_origin[i]);\n \t\t}\n \t}\n-- \n2.20.1\n\n"},{"id":"373005","messageId":"xmqqv9zvsfay.fsf@gitster-ct.c.googlers.com","threadId":"50862","inReplyTo":"20190402115625.21427-1-dak@gnu.org","subject":"Re: [PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-04-03T07:45:09Z","receivedAt":"2019-04-03T07:45:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Kastrup writes:\n\n> When a parent blob already has chunks queued up for blaming, dropping\n> the blob at the end of one blame step will cause it to get reloaded\n> right away, doubling the amount of I/O and unpacking when processing a\n> linear history.\n>\n> Keeping such parent blobs in memory seems like a reasonable optimization\n> that should incur additional memory pressure mostly when processing the\n> merges from old branches.\n\nThanks for finding an age-old one that dates back to 7c3c7962\n(\"blame: drop blob data after passing blame to the parent\",\n2007-12-11).\n\nInterestingly, the said commit claims:\n\n When passing blame from a parent to its parent (i.e. the\n grandparent), the blob data for the parent may need to be read\n again, but it should be relatively cheap, thanks to delta-base\n cache.\n \nbut perhaps you found a case where the delta-base cache is not all\nthat effective in the benchmark?\n\nWill queue. Thanks.\n\n\n\n\n>\n> Signed-off-by: David Kastrup \n> ---\n> blame.c | 3 ++-\n> 1 file changed, 2 insertions(+), 1 deletion(-)\n>\n> diff --git a/blame.c b/blame.c\n> index 5c07dec190..c11c516921 100644\n> --- a/blame.c\n> +++ b/blame.c\n> @@ -1562,7 +1562,8 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n> \t}\n> \tfor (i = 0; i < num_sg; i++) {\n> \t\tif (sg_origin[i]) {\n> -\t\t\tdrop_origin_blob(sg_origin[i]);\n> +\t\t\tif (!sg_origin[i]->suspects)\n> +\t\t\t\tdrop_origin_blob(sg_origin[i]);\n> \t\t\tblame_origin_decref(sg_origin[i]);\n> \t\t}\n> \t}\n"},{"id":"373013","messageId":"CACsJy8AbkmJ69ucCfGMdXHGvfko89SxH=DKjra6Ltwf7wpy-Og@mail.gmail.com","threadId":"50862","inReplyTo":"xmqqv9zvsfay.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-04-03T09:32:30Z","receivedAt":"2019-04-03T09:32:58Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Apr 3, 2019 at 2:45 PM Junio C Hamano wrote:\n>\n> David Kastrup writes:\n>\n> > When a parent blob already has chunks queued up for blaming, dropping\n> > the blob at the end of one blame step will cause it to get reloaded\n> > right away, doubling the amount of I/O and unpacking when processing a\n> > linear history.\n> >\n> > Keeping such parent blobs in memory seems like a reasonable optimization\n> > that should incur additional memory pressure mostly when processing the\n> > merges from old branches.\n>\n> Thanks for finding an age-old one that dates back to 7c3c7962\n> (\"blame: drop blob data after passing blame to the parent\",\n> 2007-12-11).\n>\n> Interestingly, the said commit claims:\n>\n> When passing blame from a parent to its parent (i.e. the\n> grandparent), the blob data for the parent may need to be read\n> again, but it should be relatively cheap, thanks to delta-base\n> cache.\n>\n> but perhaps you found a case where the delta-base cache is not all\n> that effective in the benchmark?\n\nInteresting. For some reason I keep remembering the delta-base cache\nis for caching base objects, not all packed objects.\n\nThat might explain why I could not see significant gain when blaming\nlinux.git's MAINTAINERS file (0.5s was shaved out of 13s) even though\nthe number of objects read was cut by half (8424 vs 15083).\n\nI just tried again. The number of actual pack reading is slightly\nreduced with the patch (498260 vs 502140). Not by a large margin. But\nI imagine if the cache is under pressure (MAINTAINERS file is quite\nsmall, 426k), we may get more eviction and misses from delta-base\ncache.\n\nIt might still help when we need to read loose objects though. But I\nguess this matters even less.\n\nAnd I don't know how lazy clones behave in this case. If we get new\nobjects and store as loose, then it helps a bit more.\n\n> Will queue. Thanks.\n>\n>\n>\n>\n> >\n> > Signed-off-by: David Kastrup \n> > ---\n> > blame.c | 3 ++-\n> > 1 file changed, 2 insertions(+), 1 deletion(-)\n> >\n> > diff --git a/blame.c b/blame.c\n> > index 5c07dec190..c11c516921 100644\n> > --- a/blame.c\n> > +++ b/blame.c\n> > @@ -1562,7 +1562,8 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n> > }\n> > for (i = 0; i < num_sg; i++) {\n> > if (sg_origin[i]) {\n> > - drop_origin_blob(sg_origin[i]);\n> > + if (!sg_origin[i]->suspects)\n> > + drop_origin_blob(sg_origin[i]);\n> > blame_origin_decref(sg_origin[i]);\n> > }\n> > }\n\n\n\n-- \nDuy\n"},{"id":"373014","messageId":"87ftqz5osx.fsf@fencepost.gnu.org","threadId":"50862","inReplyTo":"xmqqv9zvsfay.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2019-04-03T11:08:30Z","receivedAt":"2019-04-03T11:08:39Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Junio C Hamano writes:\n\n> David Kastrup writes:\n>\n>> When a parent blob already has chunks queued up for blaming, dropping\n>> the blob at the end of one blame step will cause it to get reloaded\n>> right away, doubling the amount of I/O and unpacking when processing a\n>> linear history.\n>>\n>> Keeping such parent blobs in memory seems like a reasonable optimization\n>> that should incur additional memory pressure mostly when processing the\n>> merges from old branches.\n>\n> Thanks for finding an age-old one that dates back to 7c3c7962\n> (\"blame: drop blob data after passing blame to the parent\",\n> 2007-12-11).\n>\n> Interestingly, the said commit claims:\n>\n> When passing blame from a parent to its parent (i.e. the\n> grandparent), the blob data for the parent may need to be read\n> again, but it should be relatively cheap, thanks to delta-base\n> cache.\n> \n> but perhaps you found a case where the delta-base cache is not all\n> that effective in the benchmark?\n\nThe most relevant contribution is in a linear history where the diff\nbetween commit and parent is followed by the diff between parent and\ngrandparent. It seems wasteful to recreate the blobs in this case. Of\ncourse this is also the case where any close cache layers are more\nlikely to still be warm, so the savings may be less apparent. They are\nlikely more for deep delta chains in long histories where the\ndelta-chain cache is more thoroughly exercised.\n\n-- \nDavid Kastrup\n"},{"id":"373027","messageId":"20190403113604.GA2941@sigill.intra.peff.net","threadId":"50862","inReplyTo":"CACsJy8AbkmJ69ucCfGMdXHGvfko89SxH=DKjra6Ltwf7wpy-Og@mail.gmail.com","subject":"Re: [PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-03T11:36:05Z","receivedAt":"2019-04-03T11:36:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 03, 2019 at 04:32:30PM +0700, Duy Nguyen wrote:\n\n> That might explain why I could not see significant gain when blaming\n> linux.git's MAINTAINERS file (0.5s was shaved out of 13s) even though\n> the number of objects read was cut by half (8424 vs 15083).\n\nI did a few timings, too, and managed to come up with similar\nimprovements (only a small fraction, and only for large files). I think\nthe main thing is simply that loading the blob from the object database\nis a fraction of the total work done. We still have to actually diff the\nblobs, which is at least as expensive as loading them from disk.\n\nWe also have to load commits and trees from disk as we traverse.\nEnabling the commit-graph would shrink that portion (and make\nimprovements in the blob loading proportionally more impressive).\n\nAll that said, this seems like an easy and obvious win, and worth doing.\n0.5s is still something.\n\nI suspect we could do even better by storing and reusing not just the\noriginal blob between diffs, but the intermediate diff state (i.e., the\nhashes produced by xdl_prepare(), which should be usable between\nmultiple diffs). That's quite a bit more complex, though, and I imagine\nwould require some surgery to xdiff.\n\n-Peff\n"},{"id":"373050","messageId":"CACsJy8BCGHqjO5fKG7TO5X239z_7Gzdo80jF0rx939X501yVnA@mail.gmail.com","threadId":"50862","inReplyTo":"20190403113604.GA2941@sigill.intra.peff.net","subject":"Re: [PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2019-04-03T12:06:02Z","receivedAt":"2019-04-03T12:06:31Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Apr 3, 2019 at 6:36 PM Jeff King wrote:\n> I suspect we could do even better by storing and reusing not just the\n> original blob between diffs, but the intermediate diff state (i.e., the\n> hashes produced by xdl_prepare(), which should be usable between\n> multiple diffs). That's quite a bit more complex, though, and I imagine\n> would require some surgery to xdiff.\n\nAmazing. xdl_prepare_ctx and xdl_hash_record (called inside\nxdl_prepare_ctx) account for 36% according to 'perf report'. Please\ntell me you just did not get this on your first guess.\n\nI tracked and dumped all the hashes that are sent to xdl_prepare() and\nit looks like the amount of duplicates is quite high. There are only\nabout 1000 one-time hashes out of 7000 (didn't really draw a histogram\nto examine closer). So yeah this looks really promising, assuming\nsomebody is going to do something about it.\n-- \nDuy\n"},{"id":"373051","messageId":"20190403121919.GA6818@sigill.intra.peff.net","threadId":"50862","inReplyTo":"CACsJy8BCGHqjO5fKG7TO5X239z_7Gzdo80jF0rx939X501yVnA@mail.gmail.com","subject":"Re: [PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-03T12:19:19Z","receivedAt":"2019-04-03T12:19:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 03, 2019 at 07:06:02PM +0700, Duy Nguyen wrote:\n\n> On Wed, Apr 3, 2019 at 6:36 PM Jeff King wrote:\n> > I suspect we could do even better by storing and reusing not just the\n> > original blob between diffs, but the intermediate diff state (i.e., the\n> > hashes produced by xdl_prepare(), which should be usable between\n> > multiple diffs). That's quite a bit more complex, though, and I imagine\n> > would require some surgery to xdiff.\n> \n> Amazing. xdl_prepare_ctx and xdl_hash_record (called inside\n> xdl_prepare_ctx) account for 36% according to 'perf report'. Please\n> tell me you just did not get this on your first guess.\n\nSorry, it was a guess. ;)\n\nBut an educated one, based on previous experiments with speeding up \"log\n-p\". Remember XDL_FAST_HASH, which produced speedups there (but\nunfortunately had some pathological slowdowns, because it produced too\nmany collisions). I've also played around with using other hashes like\nmurmur or siphash, but was never able to get anything remarkably faster\nthan what we have now.\n\n> I tracked and dumped all the hashes that are sent to xdl_prepare() and\n> it looks like the amount of duplicates is quite high. There are only\n> about 1000 one-time hashes out of 7000 (didn't really draw a histogram\n> to examine closer). So yeah this looks really promising, assuming\n> somebody is going to do something about it.\n\nI don't think counting the unique hash outputs tells you much about what\ncan be sped up. After all, two related blobs are likely to overlap quite\na bit in their hashes (i.e., all of their non-unique lines). The trick\nis finding in each blob those ones that _are_ unique. :)\n\nBut if we spend 36% of our time in hashing the blobs, then that implies\nthat we could gain back 18% by caching and reusing the work from a\nprevious diff (as David notes, a simple keep-the-last-parent cache only\nyields 100% cache hits in a linear history, but it's probably good\nenough for our purposes).\n\nThis should likewise make \"git log -p -- file\" faster, though with more\nfiles you'd need a bigger cache.\n\nSo I do think it's a promising lead. I don't have immediate plans to\nwork on it, though. Maybe it would be a good GSoC project. ;)\n\n-Peff\n"},{"id":"373052","messageId":"878swr5kx8.fsf@fencepost.gnu.org","threadId":"50862","inReplyTo":"20190403121919.GA6818@sigill.intra.peff.net","subject":"Re: [PATCH] blame.c: don't drop origin blobs as eagerly","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2019-04-03T12:32:19Z","receivedAt":"2019-04-03T12:32:35Z","isPatch":true,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Jeff King writes:\n\n> On Wed, Apr 03, 2019 at 07:06:02PM +0700, Duy Nguyen wrote:\n>\n>> On Wed, Apr 3, 2019 at 6:36 PM Jeff King wrote:\n>> > I suspect we could do even better by storing and reusing not just the\n>> > original blob between diffs, but the intermediate diff state (i.e., the\n>> > hashes produced by xdl_prepare(), which should be usable between\n>> > multiple diffs). That's quite a bit more complex, though, and I imagine\n>> > would require some surgery to xdiff.\n>> \n>> Amazing. xdl_prepare_ctx and xdl_hash_record (called inside\n>> xdl_prepare_ctx) account for 36% according to 'perf report'. Please\n>> tell me you just did not get this on your first guess.\n>\n> Sorry, it was a guess. ;)\n>\n> But an educated one, based on previous experiments with speeding up \"log\n> -p\". Remember XDL_FAST_HASH, which produced speedups there (but\n> unfortunately had some pathological slowdowns, because it produced too\n> many collisions). I've also played around with using other hashes like\n> murmur or siphash, but was never able to get anything remarkably faster\n> than what we have now.\n>\n>> I tracked and dumped all the hashes that are sent to xdl_prepare() and\n>> it looks like the amount of duplicates is quite high. There are only\n>> about 1000 one-time hashes out of 7000 (didn't really draw a histogram\n>> to examine closer). So yeah this looks really promising, assuming\n>> somebody is going to do something about it.\n>\n> I don't think counting the unique hash outputs tells you much about what\n> can be sped up. After all, two related blobs are likely to overlap quite\n> a bit in their hashes (i.e., all of their non-unique lines). The trick\n> is finding in each blob those ones that _are_ unique. :)\n>\n> But if we spend 36% of our time in hashing the blobs, then that implies\n> that we could gain back 18% by caching and reusing the work from a\n> previous diff (as David notes, a simple keep-the-last-parent cache only\n> yields 100% cache hits in a linear history, but it's probably good\n> enough for our purposes).\n\nOf course, if you really want to get tricky, you'll not even compare\nstuff that is expanded from the same delta-chain location. Basically,\nthere are a number of separate layers that are doing rather similar work\nwith rather similar data, but intermingling the layers' work is not\ngoing to be good for maintainability. Caching at the various layers can\nkeep their separation while still reducing some of the redundancy costs.\n\n-- \nDavid Kastrup\n"}]}