Re: [PATCH v2 1/8] odb/source-packed: improve lookup when enumerating objects
- From
Patrick Steinhardt <ps@pks.im>
- Date
- Jul 13, 2026, 09:54 UTC
- Message-ID
- <alS1440iifvTvGKP@pks.im>
- In-Reply-To
- <alFxRvkfNgJRCQTB@com-79390>
On Fri, Jul 10, 2026 at 03:25:10PM -0700, Taylor Blau wrote:
Show 16 quoted lines
> 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.
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.
In any case, this code ultimately derives from 3f5f1cff92 (midx: introduce `bsearch_one_midx()`, 2024-08-06). If one squints a bit you can see that it's still roughly in the same shape.
Show 7 quoted lines
> How often do we call this function with a prefix longer than a > single byte? I have no idea, but I would suspect that it makes up the > majority of calls. If we read the OID fanout chunk, we could narrow the > range that we enumerate through, and only compare the second byte > onwards of the given prefix, if one exists. In the single-byte prefix > case, this means that we shouldn't have to do any memory comparisons at > all.
The function is currently used to find unique prefixes and to disambiguate object names. So whenever we either want to abbreviate a object ID or in case we cant to figure out whether a given object ID prefix is unique we'll end up calling it.
If this logic is currently wrong (or at least wasteful) though I'd propose to fix this in a separate series, as it's been this way for quite a while.
Thanks!
Patrick