Subject: Re: [PATCH 15/23] pseudo-merge: fix leaking strmap keys

From: Patrick Steinhardt <[email-masked]>
Date: Wed, 9 Oct 2024 09:06:45 +0200

On Tue, Oct 08, 2024 at 04:54:23AM -0400, Jeff King wrote:
> On Mon, Oct 07, 2024 at 11:41:16AM +0200, Patrick Steinhardt wrote:
> 
> > > Hmm. I think I am probably splitting hairs, since a few xstrdup() calls
> > > between friends is unlikely to matter here, but... ;-)
> > > 
> > > It does seem wasteful if we can avoid it. We already allocated heap
> > > space for the matches via the underlying strbuf, and we really do want
> > > to hand ownership over if we can.
> > > 
> > > Would doing something like this on top of your previous patch do the
> > > trick?
> > > 
> > > --- >8 ---
> > > diff --git a/pseudo-merge.c b/pseudo-merge.c
> > > index 28782a31c6..6b6605d3dc 100644
> > > --- a/pseudo-merge.c
> > > +++ b/pseudo-merge.c
> > > @@ -110,6 +110,7 @@ void pseudo_merge_group_release(struct pseudo_merge_group *group)
> > >  		free(matches->stable);
> > >  		free(matches->unstable);
> > >  		free(matches);
> > > +		free((char*)e->key);
> > >  	}
> > >  	strmap_clear(&group->matches, 0);
> > > --- 8< ---
> > > 
> > > That introduces an ugly const-cast, but I think it's tolerable (and may
> > > be moreso with a comment explaining why it's safe).
> > 
> > Well, to me this is a tradeoff between complexity and performance. If
> > the performance benefit outweighs the additional complexity that this
> > shared ownership of keys brings along with it then I'm okay with the
> > code being intimate with each others lifetime requirements.
> > 
> > But as far as I can see the number of entries is determined by the group
> > pattern, and I expect that in most cases it's going to be quite limited.
> > So it does not feel like this should lead to all that many extra
> > allocations, and thus I tend to prefer the simpler solution.
> 
> I'd tend to agree with you that the allocations aren't a big deal here.
> But I think we've run into this kind of strbuf-detaching thing before,
> and there's another pattern that is efficient without getting too
> intimate between modules. Like this (plus your change to set the
> strmap's strdup_strings mode):
> 
> diff --git a/pseudo-merge.c b/pseudo-merge.c
> index 10ebd9a4e9..fb1164edfa 100644
> --- a/pseudo-merge.c
> +++ b/pseudo-merge.c
> @@ -210,6 +210,7 @@ static int find_pseudo_merge_group_for_ref(const char *refname,
>  	struct bitmap_writer *writer = _data;
>  	struct object_id peeled;
>  	struct commit *c;
> +	struct strbuf group_name = STRBUF_INIT;
>  	uint32_t i;
>  	int has_bitmap;
>  
> @@ -227,10 +228,11 @@ static int find_pseudo_merge_group_for_ref(const char *refname,
>  	for (i = 0; i < writer->pseudo_merge_groups.nr; i++) {
>  		struct pseudo_merge_group *group;
>  		struct pseudo_merge_matches *matches;
> -		struct strbuf group_name = STRBUF_INIT;
>  		regmatch_t captures[16];
>  		size_t j;
>  
> +		strbuf_reset(&group_name);
> +
>  		group = writer->pseudo_merge_groups.items[i].util;
>  		if (regexec(group->pattern, refname, ARRAY_SIZE(captures),
>  			    captures, 0))
> @@ -256,8 +258,7 @@ static int find_pseudo_merge_group_for_ref(const char *refname,
>  		matches = strmap_get(&group->matches, group_name.buf);
>  		if (!matches) {
>  			matches = xcalloc(1, sizeof(*matches));
> -			strmap_put(&group->matches, strbuf_detach(&group_name, NULL),
> -				   matches);
> +			strmap_put(&group->matches, group_name.buf, matches);
>  		}
>  
>  		if (c->date <= group->stable_threshold) {
> @@ -270,9 +271,9 @@ static int find_pseudo_merge_group_for_ref(const char *refname,
>  			matches->unstable[matches->unstable_nr++] = c;
>  		}
>  
> -		strbuf_release(&group_name);
>  	}
>  
> +	strbuf_release(&group_name);
>  	return 0;
>  }
>  
> 
> Now we skip the duplicate allocations because we are reusing the
> group_name scratch buffer in the loop over and over. But wait, there's
> more! We're actually _more_ efficient than the original which did one
> allocation per entry, because:
> 
>   1. We can allocate the correct number of bytes for each name, rather
>      than using the over-estimated buffer made by strbuf.
> 
>   2. In strdup_strings mode, strmap is smart enough to use a FLEXPTR to
>      stick the name inside the struct. So we've actually reduced the
>      number of allocations per entry by 1.
> 
> Now possibly it is not even worth doing this optimization, because this
> is not really a hot path. But it doesn't violate any module boundaries,
> and I think the "loop over a reusable strbuf" trick is a general idiom
> for solving these kinds of allocation problems. So a good thing to keep
> in our toolbox.

Nice, thanks for digging! I see that Junio has already merged the topic
to `next` though -- is this a mere "Let this cook before the next cycle
starts" or will it stay in next?

If the latter then I'll leave this as-is, otherwise I'll send a revised
version to make this a bit more efficient.

Thanks!

Patrick