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

[Taylor Blau <me@ttaylorr.com>]

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:
>
> > 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