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

[Taylor Blau <me@ttaylorr.com>]

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