# [PATCH] blame.c: don't drop origin blobs as eagerly 8 messages from 2019-04-02 to 2019-04-03. Participants: David Kastrup, Junio C Hamano, Duy Nguyen, Jeff King. Thread: https://gitlist.dev/t/50862 ## David Kastrup, 2019-04-02 11:56 Subject: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: <20190402115625.21427-1-dak@gnu.org> URL: https://gitlist.dev/e/20190402115625.21427-1-dak%40gnu.org ``` When a parent blob already has chunks queued up for blaming, dropping the blob at the end of one blame step will cause it to get reloaded right away, doubling the amount of I/O and unpacking when processing a linear history. Keeping such parent blobs in memory seems like a reasonable optimization that should incur additional memory pressure mostly when processing the merges from old branches. Signed-off-by: David Kastrup --- blame.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/blame.c b/blame.c index 5c07dec190..c11c516921 100644 --- a/blame.c +++ b/blame.c @@ -1562,7 +1562,8 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, } for (i = 0; i < num_sg; i++) { if (sg_origin[i]) { - drop_origin_blob(sg_origin[i]); + if (!sg_origin[i]->suspects) + drop_origin_blob(sg_origin[i]); blame_origin_decref(sg_origin[i]); } } -- 2.20.1 ``` ## Junio C Hamano, 2019-04-03 07:45 Subject: Re: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: URL: https://gitlist.dev/e/xmqqv9zvsfay.fsf%40gitster-ct.c.googlers.com In-Reply-To: <20190402115625.21427-1-dak@gnu.org> ``` David Kastrup writes: > When a parent blob already has chunks queued up for blaming, dropping > the blob at the end of one blame step will cause it to get reloaded > right away, doubling the amount of I/O and unpacking when processing a > linear history. > > Keeping such parent blobs in memory seems like a reasonable optimization > that should incur additional memory pressure mostly when processing the > merges from old branches. Thanks for finding an age-old one that dates back to 7c3c7962 ("blame: drop blob data after passing blame to the parent", 2007-12-11). Interestingly, the said commit claims: When passing blame from a parent to its parent (i.e. the grandparent), the blob data for the parent may need to be read again, but it should be relatively cheap, thanks to delta-base cache. but perhaps you found a case where the delta-base cache is not all that effective in the benchmark? Will queue. Thanks. > > Signed-off-by: David Kastrup > --- > blame.c | 3 ++- > 1 file changed, 2 insertions(+), 1 deletion(-) > > diff --git a/blame.c b/blame.c > index 5c07dec190..c11c516921 100644 > --- a/blame.c > +++ b/blame.c > @@ -1562,7 +1562,8 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, > } > for (i = 0; i < num_sg; i++) { > if (sg_origin[i]) { > - drop_origin_blob(sg_origin[i]); > + if (!sg_origin[i]->suspects) > + drop_origin_blob(sg_origin[i]); > blame_origin_decref(sg_origin[i]); > } > } ``` ## Duy Nguyen, 2019-04-03 09:32 Subject: Re: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: URL: https://gitlist.dev/e/CACsJy8AbkmJ69ucCfGMdXHGvfko89SxH%3DDKjra6Ltwf7wpy-Og%40mail.gmail.com In-Reply-To: ``` On Wed, Apr 3, 2019 at 2:45 PM Junio C Hamano wrote: > > David Kastrup writes: > > > When a parent blob already has chunks queued up for blaming, dropping > > the blob at the end of one blame step will cause it to get reloaded > > right away, doubling the amount of I/O and unpacking when processing a > > linear history. > > > > Keeping such parent blobs in memory seems like a reasonable optimization > > that should incur additional memory pressure mostly when processing the > > merges from old branches. > > Thanks for finding an age-old one that dates back to 7c3c7962 > ("blame: drop blob data after passing blame to the parent", > 2007-12-11). > > Interestingly, the said commit claims: > > When passing blame from a parent to its parent (i.e. the > grandparent), the blob data for the parent may need to be read > again, but it should be relatively cheap, thanks to delta-base > cache. > > but perhaps you found a case where the delta-base cache is not all > that effective in the benchmark? Interesting. For some reason I keep remembering the delta-base cache is for caching base objects, not all packed objects. That might explain why I could not see significant gain when blaming linux.git's MAINTAINERS file (0.5s was shaved out of 13s) even though the number of objects read was cut by half (8424 vs 15083). I just tried again. The number of actual pack reading is slightly reduced with the patch (498260 vs 502140). Not by a large margin. But I imagine if the cache is under pressure (MAINTAINERS file is quite small, 426k), we may get more eviction and misses from delta-base cache. It might still help when we need to read loose objects though. But I guess this matters even less. And I don't know how lazy clones behave in this case. If we get new objects and store as loose, then it helps a bit more. > Will queue. Thanks. > > > > > > > > Signed-off-by: David Kastrup > > --- > > blame.c | 3 ++- > > 1 file changed, 2 insertions(+), 1 deletion(-) > > > > diff --git a/blame.c b/blame.c > > index 5c07dec190..c11c516921 100644 > > --- a/blame.c > > +++ b/blame.c > > @@ -1562,7 +1562,8 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, > > } > > for (i = 0; i < num_sg; i++) { > > if (sg_origin[i]) { > > - drop_origin_blob(sg_origin[i]); > > + if (!sg_origin[i]->suspects) > > + drop_origin_blob(sg_origin[i]); > > blame_origin_decref(sg_origin[i]); > > } > > } -- Duy ``` ## David Kastrup, 2019-04-03 11:08 Subject: Re: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: <87ftqz5osx.fsf@fencepost.gnu.org> URL: https://gitlist.dev/e/87ftqz5osx.fsf%40fencepost.gnu.org In-Reply-To: ``` Junio C Hamano writes: > David Kastrup writes: > >> When a parent blob already has chunks queued up for blaming, dropping >> the blob at the end of one blame step will cause it to get reloaded >> right away, doubling the amount of I/O and unpacking when processing a >> linear history. >> >> Keeping such parent blobs in memory seems like a reasonable optimization >> that should incur additional memory pressure mostly when processing the >> merges from old branches. > > Thanks for finding an age-old one that dates back to 7c3c7962 > ("blame: drop blob data after passing blame to the parent", > 2007-12-11). > > Interestingly, the said commit claims: > > When passing blame from a parent to its parent (i.e. the > grandparent), the blob data for the parent may need to be read > again, but it should be relatively cheap, thanks to delta-base > cache. > > but perhaps you found a case where the delta-base cache is not all > that effective in the benchmark? The most relevant contribution is in a linear history where the diff between commit and parent is followed by the diff between parent and grandparent. It seems wasteful to recreate the blobs in this case. Of course this is also the case where any close cache layers are more likely to still be warm, so the savings may be less apparent. They are likely more for deep delta chains in long histories where the delta-chain cache is more thoroughly exercised. -- David Kastrup ``` ## Jeff King, 2019-04-03 11:36 Subject: Re: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: <20190403113604.GA2941@sigill.intra.peff.net> URL: https://gitlist.dev/e/20190403113604.GA2941%40sigill.intra.peff.net In-Reply-To: ``` On Wed, Apr 03, 2019 at 04:32:30PM +0700, Duy Nguyen wrote: > That might explain why I could not see significant gain when blaming > linux.git's MAINTAINERS file (0.5s was shaved out of 13s) even though > the number of objects read was cut by half (8424 vs 15083). I did a few timings, too, and managed to come up with similar improvements (only a small fraction, and only for large files). I think the main thing is simply that loading the blob from the object database is a fraction of the total work done. We still have to actually diff the blobs, which is at least as expensive as loading them from disk. We also have to load commits and trees from disk as we traverse. Enabling the commit-graph would shrink that portion (and make improvements in the blob loading proportionally more impressive). All that said, this seems like an easy and obvious win, and worth doing. 0.5s is still something. I suspect we could do even better by storing and reusing not just the original blob between diffs, but the intermediate diff state (i.e., the hashes produced by xdl_prepare(), which should be usable between multiple diffs). That's quite a bit more complex, though, and I imagine would require some surgery to xdiff. -Peff ``` ## Duy Nguyen, 2019-04-03 12:06 Subject: Re: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: URL: https://gitlist.dev/e/CACsJy8BCGHqjO5fKG7TO5X239z_7Gzdo80jF0rx939X501yVnA%40mail.gmail.com In-Reply-To: <20190403113604.GA2941@sigill.intra.peff.net> ``` On Wed, Apr 3, 2019 at 6:36 PM Jeff King wrote: > I suspect we could do even better by storing and reusing not just the > original blob between diffs, but the intermediate diff state (i.e., the > hashes produced by xdl_prepare(), which should be usable between > multiple diffs). That's quite a bit more complex, though, and I imagine > would require some surgery to xdiff. Amazing. xdl_prepare_ctx and xdl_hash_record (called inside xdl_prepare_ctx) account for 36% according to 'perf report'. Please tell me you just did not get this on your first guess. I tracked and dumped all the hashes that are sent to xdl_prepare() and it looks like the amount of duplicates is quite high. There are only about 1000 one-time hashes out of 7000 (didn't really draw a histogram to examine closer). So yeah this looks really promising, assuming somebody is going to do something about it. -- Duy ``` ## Jeff King, 2019-04-03 12:19 Subject: Re: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: <20190403121919.GA6818@sigill.intra.peff.net> URL: https://gitlist.dev/e/20190403121919.GA6818%40sigill.intra.peff.net In-Reply-To: ``` On Wed, Apr 03, 2019 at 07:06:02PM +0700, Duy Nguyen wrote: > On Wed, Apr 3, 2019 at 6:36 PM Jeff King wrote: > > I suspect we could do even better by storing and reusing not just the > > original blob between diffs, but the intermediate diff state (i.e., the > > hashes produced by xdl_prepare(), which should be usable between > > multiple diffs). That's quite a bit more complex, though, and I imagine > > would require some surgery to xdiff. > > Amazing. xdl_prepare_ctx and xdl_hash_record (called inside > xdl_prepare_ctx) account for 36% according to 'perf report'. Please > tell me you just did not get this on your first guess. Sorry, it was a guess. ;) But an educated one, based on previous experiments with speeding up "log -p". Remember XDL_FAST_HASH, which produced speedups there (but unfortunately had some pathological slowdowns, because it produced too many collisions). I've also played around with using other hashes like murmur or siphash, but was never able to get anything remarkably faster than what we have now. > I tracked and dumped all the hashes that are sent to xdl_prepare() and > it looks like the amount of duplicates is quite high. There are only > about 1000 one-time hashes out of 7000 (didn't really draw a histogram > to examine closer). So yeah this looks really promising, assuming > somebody is going to do something about it. I don't think counting the unique hash outputs tells you much about what can be sped up. After all, two related blobs are likely to overlap quite a bit in their hashes (i.e., all of their non-unique lines). The trick is finding in each blob those ones that _are_ unique. :) But if we spend 36% of our time in hashing the blobs, then that implies that we could gain back 18% by caching and reusing the work from a previous diff (as David notes, a simple keep-the-last-parent cache only yields 100% cache hits in a linear history, but it's probably good enough for our purposes). This should likewise make "git log -p -- file" faster, though with more files you'd need a bigger cache. So I do think it's a promising lead. I don't have immediate plans to work on it, though. Maybe it would be a good GSoC project. ;) -Peff ``` ## David Kastrup, 2019-04-03 12:32 Subject: Re: [PATCH] blame.c: don't drop origin blobs as eagerly Message-ID: <878swr5kx8.fsf@fencepost.gnu.org> URL: https://gitlist.dev/e/878swr5kx8.fsf%40fencepost.gnu.org In-Reply-To: <20190403121919.GA6818@sigill.intra.peff.net> ``` Jeff King writes: > On Wed, Apr 03, 2019 at 07:06:02PM +0700, Duy Nguyen wrote: > >> On Wed, Apr 3, 2019 at 6:36 PM Jeff King wrote: >> > I suspect we could do even better by storing and reusing not just the >> > original blob between diffs, but the intermediate diff state (i.e., the >> > hashes produced by xdl_prepare(), which should be usable between >> > multiple diffs). That's quite a bit more complex, though, and I imagine >> > would require some surgery to xdiff. >> >> Amazing. xdl_prepare_ctx and xdl_hash_record (called inside >> xdl_prepare_ctx) account for 36% according to 'perf report'. Please >> tell me you just did not get this on your first guess. > > Sorry, it was a guess. ;) > > But an educated one, based on previous experiments with speeding up "log > -p". Remember XDL_FAST_HASH, which produced speedups there (but > unfortunately had some pathological slowdowns, because it produced too > many collisions). I've also played around with using other hashes like > murmur or siphash, but was never able to get anything remarkably faster > than what we have now. > >> I tracked and dumped all the hashes that are sent to xdl_prepare() and >> it looks like the amount of duplicates is quite high. There are only >> about 1000 one-time hashes out of 7000 (didn't really draw a histogram >> to examine closer). So yeah this looks really promising, assuming >> somebody is going to do something about it. > > I don't think counting the unique hash outputs tells you much about what > can be sped up. After all, two related blobs are likely to overlap quite > a bit in their hashes (i.e., all of their non-unique lines). The trick > is finding in each blob those ones that _are_ unique. :) > > But if we spend 36% of our time in hashing the blobs, then that implies > that we could gain back 18% by caching and reusing the work from a > previous diff (as David notes, a simple keep-the-last-parent cache only > yields 100% cache hits in a linear history, but it's probably good > enough for our purposes). Of course, if you really want to get tricky, you'll not even compare stuff that is expanded from the same delta-chain location. Basically, there are a number of separate layers that are doing rather similar work with rather similar data, but intermingling the layers' work is not going to be good for maintainability. Caching at the various layers can keep their separation while still reducing some of the redundancy costs. -- David Kastrup ```