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

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

quoted

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