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

> Prepare to implement pseudo-merge bitmaps over the next several commits
> by first describing the serialization format which will store the new
> pseudo-merge bitmaps themselves.
> 
> This format is implemented as an optional extension within the bitmap v1
> format, making it compatible with previous versions of Git, as well as
> the original .bitmap implementation within JGit.
> 
> The format (as well as a general description of pseudo-merge bitmaps,
> and motivating use-case(s)) is described in detail in the patch contents
> below, but the high-level description is as follows:
> 
>   - An array of pseudo-merge bitmaps, each containing a pair of EWAH
>     bitmaps: one describing the set of pseudo-merge "parents", and
>     another describing the set of object(s) reachable from those
>     parents.
> 
>   - A lookup table to determine which pseudo-merge(s) a given commit
>     appears in. An optional extended lookup table follows when there is
>     at least one commit which appears in multiple pseudo-merge groups.
> 
>   - Trailing metadata, including the number of pseudo-merge(s), number
>     of unique parents, the offset within the .bitmap file for the
>     pseudo-merge commit lookup table, and the size of the optional
>     extension itself.
> 
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
>  Documentation/technical/bitmap-format.txt | 179 ++++++++++++++++++++++
>  1 file changed, 179 insertions(+)
> 
> 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.

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

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

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

> +|                                           |
> +|  Offset Cases:                            |
> +|  -------------                            |
> +|                                           |
> +|  1. MSB Unset: single pseudo-merge bitmap |
> +|     + offset to pseudo-merge bitmap       |
> +|                                           |
> +|  2. MSB Set: multiple pseudo-merges       |
> +|     + offset to extended lookup table     |
> +|                                           |
> ++-------------------------------------------+
> +|                                           |
> +|  Extended Lookup Table (Optional)         |
> +|                                           |
> +|  +----+----------+----------+----------+  |
> +|  | N  | Offset 1 |   ....   | Offset N |  |
> +|  +----+----------+----------+----------+  |
> +|  |    |  8 bytes |   ....   |  8 bytes |  |
> +|  +----+----------+----------+----------+  |
> +|                                           |
> ++-------------------------------------------+
> +|                                           |
> +|  Pseudo-merge Metadata                    |
> +|  +------------------+----------------+    |
> +|  | # pseudo-merges  | # Commits      |    |
> +|  +------------------+----------------+    |
> +|  | 4 bytes          | 4 bytes        |    |
> +|  +------------------+----------------+    |
> +|                                           |
> +|  +------------------+----------------+    |
> +|  | Lookup offset    | Extension size |    |
> +|  +------------------+----------------+    |
> +|  | 8 bytes          | 8 bytes        |    |
> +|  +------------------+----------------+    |
> +|                                           |
> ++-------------------------------------------+
> +....
> +
> +* One or more pseudo-merge bitmaps, each containing:

> +  ** `commits_bitmap`, an EWAH-compressed bitmap describing the set of
> +     commits included in the this psuedo-merge.
> +
> +  ** `merge_bitmap`, an EWAH-compressed bitmap describing the union of
> +     the set of objects reachable from all commits listed in the
> +     `commits_bitmap`.
> +
> +* A lookup table, mapping pseudo-merged commits to the pseudo-merges
> +  they belong to. Entries appear in increasing order of each commit's
> +  bit position. Each entry is 12 bytes wide, and is comprised of the
> +  following:
> +
> +  ** `commit_pos`, a 4-byte unsigned value (in network byte-order)
> +     containing the bit position for this commit.
> +
> +  ** `offset`, an 8-byte unsigned value (also in network byte-order)
> +  containing either one of two possible offsets, depending on whether or
> +  not the most-significant bit is set.
> +
> +    *** If unset (i.e. `offset & ((uint64_t)1<<63) == 0`), the offset
> +	(relative to the beginning of the `.bitmap` file) at which the
> +	pseudo-merge bitmap for this commit can be read. This indicates
> +	only a single pseudo-merge bitmap contains this commit.
> +
> +    *** If set (i.e. `offset & ((uint64_t)1<<63) != 0`), the offset
> +	(again relative to the beginning of the `.bitmap` file) at which
> +	the extended offset table can be located describing the set of
> +	pseudo-merge bitmaps which contain this commit. This indicates
> +	that multiple pseudo-merge bitmaps contain this commit.
> +
> +* 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.

> +  ** 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.