Re: [PATCH v2 12/15] Documentation/technical: describe multi-pack reverse indexes

From: Taylor Blau <me@ttaylorr.com>
Date: Mar 2, 2021, 19:15 UTC
Message-ID: <YD6OxwU936MRKa1I@nand.local>
In-Reply-To: <20210302042111.4038479-1-jonathantanmy@google.com>

On Mon, Mar 01, 2021 at 08:21:11PM -0800, Jonathan Tan wrote:

Show 15 quoted lines

> > +== 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