Re: [PATCH v2 1/8] odb/source-packed: improve lookup when enumerating objects

[Taylor Blau <ttaylorr@openai.com>]

On Mon, Jul 13, 2026 at 11:54:43AM +0200, Patrick Steinhardt wrote:
> On Fri, Jul 10, 2026 at 03:25:10PM -0700, Taylor Blau wrote:
> > On Fri, Jul 10, 2026 at 10:48:53AM +0200, Patrick Steinhardt wrote:
> > > Fix the issue by using `packed_object_info()` directly.
> >
> > What you wrote here makes sense to me insofar as I understand the
> > pluggable ODB code.
> >
> > However, I am confused by the way this function is written in general.
> > We use `bsearch_one_midx()` to locate the first possible MIDX position
> > in which an object matching the given prefix may exist, which is
> > sensible. However, we go from that position up to "num", where "num" is
> > the total number of objects in the MIDX!
> >
> > Functionally this is not incorrect as we will happily discard objects
> > that do not match the prefix. But it causes us to waste CPU cycles
> > repeatedly calling `match_hash()` (at least for the first byte of the
> > prefix) for objects that we know will match.
>
> That's not quite true though, as we abort iteration as soon as
> `match_hash()` tells us that the prefix doesn't match anymore.

Right, we neither iterate through more objects than necessary once we
know that `match_hash()` will stop returning true, nor do we emit
objects that don't actually match the prefix.

What I was trying to say above is that in the special case where our
prefix is a single byte long, we don't have to call `match_hash()` at
*all*, since we can enumerate just the portion of the fanout for that
specific byte, and we know that all such entries will match.

> Or do you mean that `num` should only be `m->num_objects` instead of
> also iterating through `num_objects_in_base`? I have to admit that I'm
> alwas struggling with the chained MIDX. It's never quite clear to me
> whether a given function cares about the complete chain or whether it
> really only cares about a single MIDX.

If the goal is to yield all such objects that match the prefix, then we
need to enumerate each layer. The analogy that I have had in my head
while working on these is that they are the same conceptually as the
incremental commit-graph format.

Thanks,
Taylor