| Message ID | 76e7e3b9cca7fb957384ed98f2cd32cf11ff8488.1710972293.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | pack-bitmap: pseudo-merge reachability bitmaps | expand |
Taylor Blau <me@ttaylorr.com> writes: > 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. Before talking about what problem, which is not addressed adequately with existing mechanisms, it will solve? > +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). "either side of" implies there are two sides. Is it correct to understand that they are "the side reachable from HAVE" and "the other side that is reachable from WANT"? > +=== 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. Here you only talk about WANT but still mention "either side of". How would the HAVE side of the query contribute to the computation? > + ** `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`. "union of the set of objects reachable from all", meaning if an object is listed here, all commits in commits_bitmap are guaranteed to reach that object? It sounds more like the intersction of sets than union. > +* 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: "a pseudo-merged commit" is a new term. It was explained what "a pseudo-merge bitmap" is already, and it was explained that "a pseudo-merge bitmap" consists of a pair of bitmaps (commit bitmap that records which commit belongs to the "pseudo-merge", and merge bitmap that records objects reachable from all commits in the commit bitmap). But we haven't heard of "a pseudo-merged commit", or what the verb "to pseudo-merge a commit" means. Does it merely mean "a commit that is recorded in the commit-bitmap half of a pseudo-merge bitmap"? It still is unclear at this point in the description if a commit can be part of only one such commit-bitmap and makes readers reading hiccup, until a few paragraphs below where extended table is there to help a commit recorded in commit-bitmap of more than one pseudo-merge bitmaps. I'll stop here for now, but this made me even more convinced that the presentation order needs to be rethought to sell why this whole thing is a good idea by telling readers what problem it is solving, why a new data structure helps and how, etc. Perhaps you can start by trying to write a paragraph of description for the topic suitable for the "What's cooking" report, which needs to do a good elevator pitch. Thanks. > + ** `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. > + > +* A 4-byte unsigned value (in network byte-order) equal to the number of > + pseudo-merges. > + > +* A 4-byte unsigned value (in network byte-order) equal to the number of > + unique commits which appear in any pseudo-merge. > + > +* An 8-byte unsigned value (in network byte-order) equal to the number > + of bytes between the start of the pseudo-merge section and the > + beginning of the lookup table. > + > +* An 8-byte unsigned value (in network byte-order) equal to the number > + of bytes in the pseudo-merge section (including this field).
On Thu, Mar 21, 2024 at 02:24:10PM -0700, Junio C Hamano wrote: > Taylor Blau <me@ttaylorr.com> writes: > > > +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). > > "either side of" implies there are two sides. Is it correct to > understand that they are "the side reachable from HAVE" and "the > other side that is reachable from WANT"? Yes, exactly. > > +=== 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. > > Here you only talk about WANT but still mention "either side of". > How would the HAVE side of the query contribute to the computation? Apologies for the confusion. In the first sentence, I'm talking about a specific case where all parents of a pseudo-merge commit are listed in/reachable from the WANTS side of a traversal. The second sentence describes the general case. The order should be swapped so that the second sentence comes first, and vice-versa for the sentence beginning with "For example, [...]". > > + ** `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`. > > "union of the set of objects reachable from all", meaning if an > object is listed here, all commits in commits_bitmap are guaranteed > to reach that object? It sounds more like the intersction of sets > than union. Oops, yes, I definitely meant intersection here. Thanks for a close read. > > +* 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: > > "a pseudo-merged commit" is a new term. It was explained what "a > pseudo-merge bitmap" is already, and it was explained that "a > pseudo-merge bitmap" consists of a pair of bitmaps (commit bitmap > that records which commit belongs to the "pseudo-merge", and merge > bitmap that records objects reachable from all commits in the commit > bitmap). But we haven't heard of "a pseudo-merged commit", or what > the verb "to pseudo-merge a commit" means. > > Does it merely mean "a commit that is recorded in the commit-bitmap > half of a pseudo-merge bitmap"? It still is unclear at this point > in the description if a commit can be part of only one such > commit-bitmap and makes readers reading hiccup, until a few > paragraphs below where extended table is there to help a commit > recorded in commit-bitmap of more than one pseudo-merge bitmaps. Sorry for being unclear here. A pseudo-merge "commit" refers to a conceptual octopus-merge commit whose parents are the ones listed in the "parents" bitmap of the pseudo-merge bitmap, as defined. The "objects" bitmap is the set of objects reachable from that imaginary commit, or, equivalently, the intersection of objects reachable from the commits listed in the parents bitmap. I'll make this more clear in the next version, thanks. > I'll stop here for now, but this made me even more convinced that > the presentation order needs to be rethought to sell why this whole > thing is a good idea by telling readers what problem it is solving, > why a new data structure helps and how, etc. Perhaps you can start > by trying to write a paragraph of description for the topic suitable > for the "What's cooking" report, which needs to do a good elevator > pitch. I'm sorry that the ordering was sub-optimal here. For the purposes of the WC report, I would write the following if I were queuing this topic: * tb/pseudo-merge-bitmaps (2024-03-21) 24 commits - t/perf: implement performace tests for pseudo-merge bitmaps - pseudo-merge: implement support for finding existing merges - ewah: `bitmap_equals_ewah()` - pack-bitmap: extra trace2 information - pack-bitmap.c: use pseudo-merges during traversal - t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` - pack-bitmap: implement test helpers for pseudo-merge - ewah: implement `ewah_bitmap_popcount()` - pseudo-merge: implement support for reading pseudo-merge commits - pack-bitmap.c: read pseudo-merge extension - pseudo-merge: scaffolding for reads - pack-bitmap: extract `read_bitmap()` function - pack-bitmap-write.c: write pseudo-merge table - pack-bitmap-write.c: select pseudo-merge commits - pseudo-merge: implement support for selecting pseudo-merge commits - pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public - pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` - pack-bitmap-write: support storing pseudo-merge commits - pseudo-merge.ch: initial commit - pack-bitmap: move some initialization to `bitmap_writer_init()` - pack-bitmap: drop unused `max_bitmaps` parameter - ewah: implement `ewah_bitmap_is_subset()` - config: repo_config_get_expiry() - Documentation/technical: describe pseudo-merge bitmaps format The pack-bitmap machinery has been extended to write bitmaps for pseudo-merges, which are imaginary commits which act as octopus merges covering groups of the un-bitmapped parts of history at reference tips. Thanks, Taylor
Taylor Blau <me@ttaylorr.com> writes: > The pack-bitmap machinery has been extended to write bitmaps for > pseudo-merges, which are imaginary commits which act as octopus > merges covering groups of the un-bitmapped parts of history at > reference tips. That is "what the topic does", and does not cover "why does it do so" and/or "for what effect". I can sort-of see that allowing us to record a pre-combined bitmap for octopus merges that do not exist, we have more flexibility compared to the original bitmap machinery where we can only put bitmap to commits that exist. What is not clear is what this additional flexibility is used for. Does the approach takes advantage of that additional flexibility to reduce redundancy, allowing us to have the same bitmap coverage with smaller number of bitmaps? Thanks.
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. + +* A 4-byte unsigned value (in network byte-order) equal to the number of + pseudo-merges. + +* A 4-byte unsigned value (in network byte-order) equal to the number of + unique commits which appear in any pseudo-merge. + +* An 8-byte unsigned value (in network byte-order) equal to the number + of bytes between the start of the pseudo-merge section and the + beginning of the lookup table. + +* An 8-byte unsigned value (in network byte-order) equal to the number + of bytes in the pseudo-merge section (including this field).
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(+)