Re: [PATCH v2 01/23] Documentation/technical: describe pseudo-merge bitmaps format

From

Taylor Blau <me@ttaylorr.com>

Date

May 6, 2024, 16:37 UTC

Message-ID

<ZjkHT9XVl7ua8E14@nand.local>

In-Reply-To

<ZjjEjNRp2BAMWJ47@tanuki>

On Mon, May 06, 2024 at 01:52:44PM +0200, Patrick Steinhardt wrote:

> > diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt
> > index f5d200939b0..63a7177ac08 100644
> > --- a/Documentation/technical/bitmap-format.txt
> > +++ b/Documentation/technical/bitmap-format.txt
> > @@ -255,3 +255,182 @@ triplet is -
> >  	xor_row (4 byte integer, network byte order): ::
> >  	The position of the triplet whose bitmap is used to compress
> >  	this one, or `0xffffffff` if no such bitmap exists.
> > +
> > +Pseudo-merge bitmaps
> > +--------------------
> > +
> > +If the `BITMAP_OPT_PSEUDO_MERGES` flag is set, a variable number of
> > +bytes (preceding the name-hash cache, commit lookup table, and trailing
> > +checksum) of the `.bitmap` file is used to store pseudo-merge bitmaps.
>
> Here you say that the section is supposed to come before some other
> sections, whereas the first sentence in the "File format" section says
> that it is the last section in a bitmap file.

> > +A "pseudo-merge bitmap" is used to refer to a pair of bitmaps, as
> > +follows:
> > +
> > +Commit bitmap::
> > +
> > +  A bitmap whose set bits describe the set of commits included in the
> > +  pseudo-merge's "merge" bitmap (as below).
> > +
> > +Merge bitmap::
> > +
> > +  A bitmap whose set bits describe the reachability closure over the set
> > +  of commits in the pseudo-merge's "commits" bitmap (as above). An
> > +  identical bitmap would be generated for an octopus merge with the same
> > +  set of parents as described in the commits bitmap.
> > +
> > +Pseudo-merge bitmaps can accelerate bitmap traversals when all commits
> > +for a given pseudo-merge are listed on either side of the traversal,
> > +either directly (by explicitly asking for them as part of the `HAVES`
> > +or `WANTS`) or indirectly (by encountering them during a fill-in
> > +traversal).
> > +
> > +=== Use-cases
>
> I feel like starting with the problems that the whole feature is
> intended to solve would help the reading flow quite a bit. So I'd move
> this whole section up.

--- 8< ---

diff --git a/Documentation/technical/bitmap-format.txt b/Documentation/technical/bitmap-format.txt
index 63a7177ac0..144f377e35 100644
--- a/Documentation/technical/bitmap-format.txt
+++ b/Documentation/technical/bitmap-format.txt
@@ -263,6 +263,26 @@ If the `BITMAP_OPT_PSEUDO_MERGES` flag is set, a variable number of
 bytes (preceding the name-hash cache, commit lookup table, and trailing
 checksum) of the `.bitmap` file is used to store pseudo-merge bitmaps.

+=== Problem
+
+When a bitmap traversal is performed, the client may have to do some
+amount of "fill-in" traversal to find the set of objects reachable from
+references which do not have bitmap coverage within the repository.
+
+This fill-in traversal can be expensive, and can become a significant
+bottleneck in repositories that have a large number of references with
+poor bitmap coverage. Ideally every single reference would have
+reachability bitmap coverage, but this is also not feasible as doing so
+would reduce cache locality when reading the .bitmap file, and we would
+also spend a significant amount of time XOR'ing individual bitmaps
+together to generate a result.
+
+This section describes "pseudo-merge bitmaps", a new kind of
+reachability bitmap that describes the set of objects reachable from a
+group of references, rather than an individual reference.
+
+=== Overview
+
 A "pseudo-merge bitmap" is used to refer to a pair of bitmaps, as
 follows:
--- >8 ---

> > +For example, suppose there exists a pseudo-merge bitmap with a large
> > +number of commits, all of which are listed in the `WANTS` section of
> > +some bitmap traversal query. When pseudo-merge bitmaps are enabled, the
> > +bitmap machinery can quickly determine there is a pseudo-merge which
> > +satisfies some subset of the wanted objects on either side of the query.
> > +Then, we can inflate the EWAH-compressed bitmap, and `OR` it in to the
> > +resulting bitmap. By contrast, without pseudo-merge bitmaps, we would
> > +have to repeat the decompression and `OR`-ing step over a potentially
> > +large number of individual bitmaps, which can take proportionally more
> > +time.
> > +
> > +Another benefit of pseudo-merges arises when there is some combination
> > +of (a) a large number of references, with (b) poor bitmap coverage, and
> > +(c) deep, nested trees, making fill-in traversal relatively expensive.
> > +For example, suppose that there are a large enough number of tags where
> > +bitmapping each of the tags individually is infeasible. Without
> > +pseudo-merge bitmaps, computing the result of, say, `git rev-list
> > +--use-bitmap-index --count --objects --tags` would likely require a
> > +large amount of fill-in traversal. But when a large quantity of those
> > +tags are stored together in a pseudo-merge bitmap, the bitmap machinery
> > +can take advantage of the fact that we only care about the union of
> > +objects reachable from all of those tags, and answer the query much
> > +faster.
>
> I would start the explanation with a discussion of the problem before
> presenting the solution to those problems. In the current version it's
> the other way round, you present a solution to a problem that isn't yet
> explained
>
> It might also be helpful to discuss a bit who is supposed to create
> those pseudo-merge bitmaps. Does Git do so automatically for all tags?
> Does the admin have to configure this? If the latter, when do you want
> to create those and what strategies are there to create them?

The pseudo-merge bitmaps are created by Git itself, configured via the
options described later on in this series. I'm happy to add a specific
call-out, but I would rather do it elsewhere outside of
Documentation/technical/bitmap-format.txt, which I think should be
mostly focused on the on-disk format.

> > +=== File format
> > +
> > +If enabled, pseudo-merge bitmaps are stored in an optional section at
> > +the end of a `.bitmap` file. The format is as follows:
> > +
> > +....
> > ++-------------------------------------------+
> > +|               .bitmap File                |
> > ++-------------------------------------------+
> > +|                                           |
> > +|  Pseudo-merge bitmaps (Variable Length)   |
> > +|  +---------------------------+            |
> > +|  | commits_bitmap (EWAH)     |            |
> > +|  +---------------------------+            |
> > +|  | merge_bitmap (EWAH)       |            |
> > +|  +---------------------------+            |
> > +|                                           |
> > ++-------------------------------------------+
> > +|                                           |
> > +|  Lookup Table                             |
> > +|  +------------+--------------+            |
> > +|  | commit_pos |    offset    |            |
> > +|  +------------+--------------+            |
> > +|  |  4 bytes   |   8 bytes    |            |
> > +|  +------------+--------------+            |
>
> It's a bit confusing that in the EWAH section above you have the type of
> the fields in the same line as the field itself, whereas here you have
> them formatted in a separate box. This makes the reader wonder at first
> whether this is two or four fields. How about the following instead:
>
>     |  Lookup Table                             |
>     |  +---------------------------+            |
>     |  | commit_pos (4 bytes)      |            |
>     |  +---------------------------+            |
>     |  | offset (8 bytes)          |            |
>     |  +---------------------------+            |
>
> The same comment applies to the other sections further down.

Much preferable, thanks. I made the change to use the suggested format
here and elsewhere in the document.

> In case you have multiple pseudo-merge bitmaps, is the whole of the
> above repeated for each bitmap or is it just parts of it?

The "pseudo-merge bitmaps" section contains a variable number of pairs
of EWAH bitmaps, one pair for each pseudo-merge bitmap. I think this is
covered below where it says "one or more pseudo-merge bitmaps, each
containing: [...]", but let me know if I should be more explicit.

> > +* An (optional) extended lookup table (written if and only if there is
> > +  at least one commit which appears in more than one pseudo-merge).
> > +  There are as many entries as commits which appear in multiple
> > +  pseudo-merges. Each entry contains the following:
> > +
> > +  ** `N`, a 4-byte unsigned value equal to the number of pseudo-merges
> > +     which contain a given commit.
>
> How exactly is the given commit identified? Or in other words, given an
> entry in the lookup table here, how do I figure out what commit it
> belongs to?

They aren't identified within this section. The extended lookup table is
indexed into via the lookup table with an offset that is stored in the
`offset` field when the MSB is set.

> > +  ** An array of `N` 8-byte unsigned values, each of which is
> > +     interpreted as an offset (relative to the beginning of the
> > +     `.bitmap` file) at which a pseudo-merge bitmap for this commit can
> > +     be read. These values occur in no particular order.
> > +
> > +* Positions for all pseudo-merges, each stored as an 8-byte unsigned
> > +  value (in network byte-order) containing the offset (relative to the
> > +  beginnign of the `.bitmap` file) of each consecutive pseudo-merge.
>
> s/beginnign/beginning

Great catch, thanks!

Thanks,
Taylor