On Mon, Mar 01, 2021 at 08:21:11PM -0800, Jonathan Tan wrote: > > +== multi-pack-index reverse indexes > > + > > +Similar to the pack-based reverse index, the multi-pack index can also > > +be used to generate a reverse index. > > + > > +Instead of mapping between offset, pack-, and index position, this > > +reverse index maps between an object's position within the MIDX, and > > +that object's position within a pseudo-pack that the MIDX describes. > > + > > +To clarify these three orderings > > The paragraph seems to only describe 2 orderings - object's position > within the MIDX and object's position within the pseudo-pack. (Is the > third one the offset within the MIDX - which is, I believe, trivially > computable from the position within the MIDX?) Sorry for the confusion. I was trying to distinguish between ordering based on object offset, pack position, and index position. I guess you could count that as 2, 3, or 4 different orderings (if you classify "pack vs MIDX", "offset vs pack pos vs index pos" or the last three plus "vs MIDX pos"). But I think that all of that is needlessly confusing, so I'd much rather just say "To clarify the difference between these orderings". > Also, which are stored in the .rev file? The paragraph above describes it a little bit "this reverse index maps between ...", but I think it could be made clearer. (I was intentionally brief there since I wanted to not get too far into the details before explaining the relevant concepts, but I think I went too far). How does this sound? --- >8 --- diff --git a/Documentation/technical/pack-format.txt b/Documentation/technical/pack-format.txt index 77eb591057..4bbbb188a4 100644 --- a/Documentation/technical/pack-format.txt +++ b/Documentation/technical/pack-format.txt @@ -387,12 +387,15 @@ be used to generate a reverse index. Instead of mapping between offset, pack-, and index position, this reverse index maps between an object's position within the MIDX, and -that object's position within a pseudo-pack that the MIDX describes. +that object's position within a pseudo-pack that the MIDX describes +(i.e., the ith entry of the multi-pack reverse index holds the MIDX +position of ith object in pseudo-pack order). -To clarify these three orderings, consider a multi-pack reachability -bitmap (which does not yet exist, but is what we are building towards -here). Each bit needs to correspond to an object in the MIDX, and so we -need an efficient mapping from bit position to MIDX position. +To clarify the difference between these orderings, consider a multi-pack +reachability bitmap (which does not yet exist, but is what we are +building towards here). Each bit needs to correspond to an object in the +MIDX, and so we need an efficient mapping from bit position to MIDX +position. One solution is to let bits occupy the same position in the oid-sorted index stored by the MIDX. But because oids are effectively random, there
