Re: [PATCH v4 01/13] Documentation: describe incremental MIDX bitmaps

[Taylor Blau <me@ttaylorr.com>]

On Mon, Mar 17, 2025 at 09:16:18PM -0400, Jeff King wrote:
> On Fri, Mar 14, 2025 at 04:18:20PM -0400, Taylor Blau wrote:
>
> > +In the incremental MIDX design, we extend this definition to include
> > +objects from multiple layers of the MIDX chain. The pseudo-pack order
> > +for incremental MIDXs is determined by concatenating the pseudo-pack
> > +ordering for each layer of the MIDX chain in order. Formally two objects
> > +`o1` and `o2` are compared as follows:
> > +
> > +1. If `o1` appears in an earlier layer of the MIDX chain than `o2`, then
> > +  `o1` is considered less than `o2`.
> > +
> > +2. Otherwise, if `o1` and `o2` appear in the same MIDX layer, and that
> > +   MIDX layer has no base, then if one of `pack(o1)` and `pack(o2)` is
> > +   preferred and the other is not, then the preferred one sorts first. If
> > +   there is a base layer (i.e. the MIDX layer is not the first layer in
> > +   the chain), then if `pack(o1)` appears earlier in that MIDX layer's
> > +   pack order, than `o1` is less than `o2`. Likewise if `pack(o2)`
> > +   appears earlier, than the opposite is true.
> > +
> > +3. Otherwise, `o1` and `o2` appear in the same pack, and thus in the
> > +   same MIDX layer. Sort `o1` and `o2` by their offset within their
> > +   containing packfile.
>
> OK, I think this ordering makes sense. I had to read this description
> over several times to make sure I wasn't missing something. The earlier
> part that says "it's just concatenating the pack order of the layers" is
> a much more intuitive way of looking at it (modulo that you might need
> to remove duplicates found in earlier layers).
>
> But I think an even more basic way of thinking about it is that it's the
> same as the pseudo-pack order you would get if you had a single midx of
> all of the packs in all of the layers (in their layer order). We already
> have to deal with (and have documented) duplicates in that case.
>
> Not really suggesting any wording change here, just making sure I
> grokked it all.

Yeah, those are both excellent ways to think about it. I hadn't
considered the "the new ordering is the same as the pseudo-pack order
you'd get if you had a single MIDX of all the packs in layer order"
thing before, but it's quite intuitive.

As a side note, it's somewhat hilarious to me that we could really
write:

    "The new ordering is the same as the pseudo-pack order you'd get if
    you had a single MIDX of all the packs in layer order, which is the
    same order you'd get if you had a single pack containing all of the
    objects in MIDX order."

;-)

> > +Note that the preferred pack is a property of the MIDX chain, not the
> > +individual layers themselves. Fundamentally we could introduce a
> > +per-layer preferred pack, but this is less relevant now that we can
> > +perform multi-pack reuse across the set of packs in a MIDX.
>
> Calling this out explicitly is good, since it's an obvious question
> for somebody to have.

Thanks, I think this was an addition from Patrick's earlier review of
the series.

> OK, so each layer's bitmap does depend on the layers above/before it.
> That obviously needs to happen because each incremental midx is not
> likely to be a complete reachability set anyway.
>
> But I also wondered what would happen with a situation like this:
>
>   A -- B
>    \
>     -- C
>
> stored like this:
>
>   base midx:
>     - pack 1:
>       - object A
>       - object B, which can reach A
>   incremental midx:
>     - pack 2:
>       - object A
>       - object C, which can reach A
>
> That is, two objects B and C both depend on A, which is duplicated in
> two midx layers. Even if the incremental midx is complete in the sense
> that C only depends on A, its bitmap cannot just be "11". Because the
> bit position for object A in the incremental midx does not exist in the
> pseudo-pack order at all! It must refer to the copy of "A" in the base
> midx, so it's correct bitmap is "101" (A and C, but not B).
>

Right. Since the base MIDX has objects A and B, B's bitmap here would be
"11". C's bit position in the subsequent layer is a function of where it
sits not just in that MIDX layer, but how many (de-duplicated) objects
exist in all prior layers. There are two, so the earliest bit position
possible to allocate towards C is the third bit. And since C reaches A,
its bitmap would indeed be "101".

> Again, just talking through it here.

Heh, thanks for saying so. It's good to know when we're just talking
through examples versus asking for changes. (Of course, the mere fact of
talking through an example is sometimes enough to suggest a change by
virtue of that example being confusing enough to need to be talked
through in the first place).

> > +Note also that only the bitmap pertaining to the most recent layer in an
> > +incremental MIDX chain is used to store reachability information about
> > +the interesting and uninteresting objects in a reachability query.
> > +Earlier bitmap layers are only used to look up commit and pseudo-merge
> > +bitmaps from that layer, as well as the type-level bitmaps for objects
> > +in that layer.
>
> I'm not quite sure what this means, but I guess you're saying that
> internally as we produce a bitmap, we'll always use the complete bitmap
> over all of the layers?

That's exactly right.

> > +To simplify the implementation, type-level bitmaps are iterated
> > +simultaneously, and their results are OR'd together to avoid recursively
> > +calling internal bitmap functions.
>
> OK, I guess we'll see what this means in the patches. ;)
>
> The general rules for the data structure make sense to me, though.

Great, and thanks in advance for the review as I work through the rest
of your emails :-).

Thanks,
Taylor