threads / patch / 50862

patchblame.c: don't drop origin blobs as eagerly

Subject: [PATCH] blame.c: don't drop origin blobs as eagerly

## tl;dr

8 messages between Apr 2, 2019 and Apr 3, 2019. Diffs are folded; open one to read it.

replies: 7people: 4as markdown or json

David Kastrup· Apr 2, 2019, 11:56 UTC · lore

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 <dak@gnu.org>
---
 blame.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
Show changes to blame.c +2 −1
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· Apr 3, 2019, 07:45 UTC · re: David Kastrup · lore

Re: [PATCH] blame.c: don't drop origin blobs as eagerly

David Kastrup <dak@gnu.org> writes:
Show 8 quoted lines
> 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.
Show 20 quoted lines
>
> Signed-off-by: David Kastrup <dak@gnu.org>
> ---
>  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· Apr 3, 2019, 09:32 UTC · re: Junio C Hamano · lore

Re: [PATCH] blame.c: don't drop origin blobs as eagerly

On Wed, Apr 3, 2019 at 2:45 PM Junio C Hamano <gitster@pobox.com> wrote:
Show 25 quoted lines
>
> David Kastrup <dak@gnu.org> 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.

Show 25 quoted lines
> Will queue.  Thanks.
>
>
>
>
> >
> > Signed-off-by: David Kastrup <dak@gnu.org>
> > ---
> >  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
Jeff King· Apr 3, 2019, 11:36 UTC · re: Duy Nguyen · lore

Re: [PATCH] blame.c: don't drop origin blobs as eagerly

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· Apr 3, 2019, 12:06 UTC · re: Jeff King · lore

Re: [PATCH] blame.c: don't drop origin blobs as eagerly

On Wed, Apr 3, 2019 at 6:36 PM Jeff King <peff@peff.net> wrote:
Show 5 quoted lines
> 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· Apr 3, 2019, 12:19 UTC · re: Duy Nguyen · lore

Re: [PATCH] blame.c: don't drop origin blobs as eagerly

On Wed, Apr 03, 2019 at 07:06:02PM +0700, Duy Nguyen wrote:
Show 10 quoted lines
> On Wed, Apr 3, 2019 at 6:36 PM Jeff King <peff@peff.net> 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.

Show 5 quoted lines
> 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· Apr 3, 2019, 12:32 UTC · re: Jeff King · lore

Re: [PATCH] blame.c: don't drop origin blobs as eagerly

Jeff King <peff@peff.net> writes:
Show 38 quoted lines
> On Wed, Apr 03, 2019 at 07:06:02PM +0700, Duy Nguyen wrote:
>
>> On Wed, Apr 3, 2019 at 6:36 PM Jeff King <peff@peff.net> 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
David Kastrup· Apr 3, 2019, 11:08 UTC · re: Junio C Hamano · lore

Re: [PATCH] blame.c: don't drop origin blobs as eagerly

Junio C Hamano <gitster@pobox.com> writes:
Show 24 quoted lines
> David Kastrup <dak@gnu.org> 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

← back to recent threads