Re: What's cooking in git.git (Oct 2020, #03; Mon, 19)

From: Jeff King <peff@peff.net>
Date: Oct 27, 2020, 08:39 UTC
Message-ID: <20201027083906.GA61563@coredump.intra.peff.net>
In-Reply-To: <CABPp-BFV8ZAu5vLarG2mX8gT5bfV31oqbd-vjAQF_YDcyNSRiw@mail.gmail.com>

On Fri, Oct 23, 2020 at 12:17:43PM -0700, Elijah Newren wrote:

Show 13 quoted lines

> > I suspect my "check_and_add" function could be folded into Elijah's
> > implementation. The other big difference is that mine uses the
> > FLEX_ALLOC approach, and his doesn't. I haven't digested the code and
> > discussion around that from Elijah's series yet.
> 
> From a brief glance, it looks like the code in shortlog would probably
> be easy to convert over.  But more important is making sure we have a
> strmap/strset/strintmap API that we like.  You provided a lot of good
> feedback and pointers on the first round of the series, so if you
> could find some time to take a look at the second round, it'd be very
> appreciated.  I'm also very interested in your opinion on whether the
> changes I made were good enough, or if you'd like me to dig further
> into whether going the FLEX_ALLOC route will work.

I suspect the FLEX_ALLOC thing wouldn't really matter much either way for the use I added in shortlog. It would rarely have more than a handful of entries in it anyway: one per trailer in a given commit. I suspect it might even perform better as an unsorted list, given the size of N, but as soon as you code something like that somebody shows up with a commit that has 10,000 "Reviewed-by" trailers in it or something. ;)

One possible solution is to use FLEXPTR_ALLOC, which embeds the string in the struct but adds a pointer to it, as well. That gives most of the benefits of FLEX_ALLOC (one malloc per entry instead of two, and better cache locality), with only a small cost (8 bytes per entry). And it would let the same data type be used to hold your use cases that do pointer comparison (they'd use an empty FLEX_ARRAY and just set the pointer as appropriate). And you only have to care when creating the struct; all of the readers just look at the pointer, which is always valid.

If you wanted to get _really_ crazy you could probably have a union of the pointer and the FLEX_ARRAY, and then you could save those 8 bytes. Not sure if that's worth the complexity (we need a separate bit flag to tell the two cases apart, and every read would have to check it).

Hopefully that gives you some food for thought for now. I had hoped to read through the series carefully tonight, but didn't get to it. But it is on my todo list.

-Peff