Re: [PATCH v4 04/13] pack-bitmap.c: teach `bitmap_for_commit()` about incremental MIDXs

On Mon, Mar 17, 2025 at 09:38:23PM -0400, Jeff King wrote:

On Fri, Mar 14, 2025 at 04:18:31PM -0400, Taylor Blau wrote:

quoted

The pack-bitmap machinery uses `bitmap_for_commit()` to locate the
EWAH-compressed bitmap corresponding to some given commit object.

Teach this function about incremental MIDX bitmaps by teaching it to
recur on earlier bitmap layers when it fails to find a given commit in
the current layer.

The changes to do so are as follows:

  - Avoid initializing hash_pos at its declaration, since
    bitmap_for_commit() is now a recursive function and may receive a
    NULL bitmap_index pointer as its first argument.

  - In cases where we would previously return NULL (to indicate that a
    lookup failed and the given bitmap_index does not contain an entry
    corresponding to the given commit), recursively call the function on
    the previous bitmap layer.

This makes sense, though it does make me wonder if we could/should store
a (midx/pack,pos) pair. I.e., a master hash table stored once for the
whole midx stack. And then you wouldn't need to recurse; it would just
be a single lookup.

Or would that work badly with the lazy nature? You'd need to load all of
the layers to fill it (rather than doing each incrementally). OTOH, if
you ask for the bitmap for commit X you're eventually going to have to
figure out what's in all of the layers as soon as you have a miss and
have to check them all. And I think the lookup table extension is what's
supposed to make that cheap-ish.

I think that it's a good idea, though TBH I think there is even more
room for improvement there, like recording cache misses. I suspect the
details are fiddly enough that I'd rather tackle them outside of this
already-fiddly series, though ;-).

Thanks,
Taylor