[PATCH 00/24] pack-bitmap: pseudo-merge reachability bitmaps

This series implements a new idea in the pack-bitmap machinery called "pseudo-merge reachability bitmaps".

BACKGROUND ==========

Pseudo-merge bitmaps conceptually represent storing bitmaps for octopus-merges covering the reference tips in a repository not selected for bitmaps, decreasing the size (number of parents) of consecutive merges according to an inverse power-law.

(Note that a complete description of the on-disk format can be found in Documentation/technical/bitmap-format.txt, and the configuration details in the "bitmapPseudoMerge" section of 'git-config(1)').

Commits are assigned into pseudo-merge group(s) according to a number of parameters unique to each defined group, like so:

    [bitmapPseudoMerge "name"]
        pattern = "refs/*"
        decay = 100
        sampleRate = 100
        threshold = 1.week.ago
        maxMerges = 64
        stableThreshold = 1.month.ago
        stableSize = 1024

Users can create zero or more pseudo-merge groups. Pseudo-merge groups look at reference tips matching the given pattern, and use the commits at the tips of those (matching) references as candidates for forming the pseudo-merge groups.

The full details are spelled out in git-config(1), but the gist is as follows:

  - "decay" controls the decay rate between consecutive groups
    (effectively setting 'k' in the decay function 'f(n)=C*n^-k')

  - "sampleRate" controls how often (between 0 and 100, inclusive) to
    select a candidate for inclusion within a pseudo-merge group

  - "threshold" sets the minimum age for an un-bitmapped reference tip
    to join a pseudo-merge gruop

  - "maxMerges" controls how many unstable pseudo-merge groups we'll
    create

In addition, there are a pair of parameters controlling "stable" pseudo-merge groups, meant to cover commits that are so old as to be highly unlikely to change. "stableThreshold" controls the minimum age, and "stableSize" controls the fixed size of each of these groups. Stable pseudo-merges do not follow the inverse power-law decay function as above.

Pseudo-merges can be grouped evevn further if the given pattern has one or more capture groups, similar to delta islands. In a fork-network repository (where each fork is a remote, and all objects live in aggregate in a repository called "network.git"), you can group branches/tags separately by fork ID like so:

    [bitmapPseudoMerge "branches"]
        pattern = "refs/remotes/([0-9])+/heads/"
        [...]

    [bitmapPseudoMerge "tags"]
        pattern = "refs/remotes/([0-9])+/tags/"
        [...]

Pseudo-merges are an additive optimization. A pseudo-merge may only be used when all of its parents are part of either the "haves" or "wants" side of a reachability query.

This is why groups with "older" commits tend to be larger (since they are less likely to change, thus more likely to be usable over time). The same is true for "newer" pseudo-merge groups being smaller.

USAGE =====

Here's a best-case scenario for using pseudo-merge bitmaps. This is a local copy of a relatively large (private) repository that has a large number of references (~44k) with poor bitmap coverage, spike-y branches, and deep-ish trees.

First, we generate a new bitmap with 64 pseudo-merge commits covering the un-bitmapped parts of this repository, like so.

    $ GIT_TRACE2_PERF=1 GIT_TRACE2_PERF_BRIEF=1 \
      git.compile \
        -c bitmapPseudoMerge.all.pattern='refs/' \
        -c bitmapPseudoMerge.all.threshold=now \
        -c bitmapPseudoMerge.all.stableThreshold=never \
        -c bitmapPseudoMerge.all.maxMerges=64 \
        -c pack.writeBitmapLookupTable=true \
        repack -adb
    [...]
    d1 | main | data         | r1  | 476.227928 |  0.058245 | progress     | ....total_objects:1
    d1 | main | region_leave | r1  | 476.227938 |  0.058255 | progress     | ..label:Selecting pseudo-merge commits
    d1 | main | region_enter | r1  | 476.227946 |           | progress     | ..label:Building bitmaps
    d1 | main | region_enter | r1  | 476.227949 |           | pack-bitmap- | ....label:building_bitmaps_total
    d1 | main | data         | r1  | 476.228348 |  0.000399 | bitmap       | ......opened bitmap file:.git/objects/pack/pack-47e6bced8a8f64d82802a77f2f1cf5eeac24f295.pack
    d1 | main | data         | r1  | 485.947246 |  9.719297 | pack-bitmap- | ......num_selected_commits:733
    d1 | main | data         | r1  | 485.947269 |  9.719320 | pack-bitmap- | ......num_maximal_commits:115
    d1 | main | region_leave | r1  | 1033.008932 | 556.780983 | pack-bitmap- | ....label:building_bitmaps_total
    d1 | main | data         | r1  | 1033.008953 | 556.781007 | pack-bitmap- | ....building_bitmaps_reused:700
    d1 | main | data         | r1  | 1033.008957 | 556.781011 | pack-bitmap- | ....building_bitmaps_pseudo_merge_reused:0
    d1 | main | data         | r1  | 1033.008968 | 556.781022 | progress     | ....total_objects:733
    d1 | main | region_leave | r1  | 1033.008971 | 556.781025 | progress     | ..label:Building bitmaps

(Note: this repository had an up-to-date .bitmap prior to generating pseudo-merges, so we spend about ~9 minutes (on an unoptimized build) generating psuedo-merges. This feels expensive, but maybe my intuition is wrong. I've spent quite a bit of time trying to drive this down, but I still think there is some medium-hanging fruit left here to get this to be even cheaper.)

PERFORMANCE ===========

From there, we can compare the time it takes to generate a count of reachable objects with and without using pseudo-merge bitmaps:

    $ hyperfine -L v ,.compile 'git{v} rev-list --all --objects --count --use-bitmap-index'
    Benchmark 1: git rev-list --all --objects --count --use-bitmap-index
      Time (mean ± σ):     16.129 s ±  0.079 s    [User: 15.681 s, System: 0.446 s]
      Range (min … max):   16.029 s … 16.243 s    10 runs

    Benchmark 2: git.compile rev-list --all --objects --count --use-bitmap-index
      Time (mean ± σ):     874.9 ms ±  20.4 ms    [User: 611.4 ms, System: 263.3 ms]
      Range (min … max):   847.1 ms … 904.3 ms    10 runs

    Summary
      git.compile rev-list --all --objects --count --use-bitmap-index ran
       18.43 ± 0.44 times faster than git rev-list --all --objects --count --use-bitmap-index

Similarly for clone performance (this impact here is less dramatic than above, primarily because we end up accumulating most objects via pack-reuse, but enumeration is faster by roughly the same quantity as above):

    $ hyperfine --runs=3 -L v ,.compile 'git{v} pack-objects \
      --all --use-bitmap-index --delta-base-offset \
      --stdout --all-progress </dev/null >/dev/null'
    Benchmark 1: git pack-objects \
      --all --use-bitmap-index --delta-base-offset \
      --stdout --all-progress </dev/null >/dev/null
      Time (mean ± σ):     93.811 s ±  2.202 s    [User: 80.905 s, System: 7.674 s]
      Range (min … max):   92.136 s … 96.305 s    3 runs

    Benchmark 2: git.compile pack-objects \
      --all --use-bitmap-index --delta-base-offset \
      --stdout --all-progress </dev/null >/dev/null
      Time (mean ± σ):     79.608 s ±  0.764 s    [User: 68.304 s, System: 7.215 s]
      Range (min … max):   78.912 s … 80.425 s    3 runs

    Summary
      git.compile pack-objects --all --use-bitmap-index --delta-base-offset --stdout --all-progress </dev/null >/dev/null ran
        1.18 ± 0.03 times faster than git pack-objects --all --use-bitmap-index --delta-base-offset --stdout --all-progress </dev/null >/dev/null

In a smaller repository, like git.git, the perfomrance number are much less dramatic (here we're generating the numbers from the new p5333 performance test), but show that we do not pay a performance penalty for using pseudo-merges:

    Test                                                                this tree
    -----------------------------------------------------------------------------------
    5333.2: git rev-list --count --all --objects (no bitmaps)           3.46(3.37+0.09)
    5333.3: git rev-list --count --all --objects (no pseudo-merges)     0.13(0.11+0.01)
    5333.4: git rev-list --count --all --objects (with pseudo-merges)   0.12(0.11+0.01)

CONCLUSION ==========

This series turned out to be quite the adventure to work on ;-). Many thanks to Peff, who developed this idea together with me during the end of October, 2021.

Review on this large topic is greatly appreciated. Likewise, if folks have good ideas on either (a) how to speed-up generating these bitmaps, or (b) a sense of whether or not the current performance is acceptable, I am all ears.

Thanks in advance for anyone interested in reviewing this topic, and I look forward to your feedback!

Taylor Blau (24):
  Documentation/technical: describe pseudo-merge bitmaps format
  config: repo_config_get_expiry()
  ewah: implement `ewah_bitmap_is_subset()`
  pack-bitmap: drop unused `max_bitmaps` parameter
  pack-bitmap: move some initialization to `bitmap_writer_init()`
  pseudo-merge.ch: initial commit
  pack-bitmap-write: support storing pseudo-merge commits
  pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()`
  pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public
  pseudo-merge: implement support for selecting pseudo-merge commits
  pack-bitmap-write.c: select pseudo-merge commits
  pack-bitmap-write.c: write pseudo-merge table
  pack-bitmap: extract `read_bitmap()` function
  pseudo-merge: scaffolding for reads
  pack-bitmap.c: read pseudo-merge extension
  pseudo-merge: implement support for reading pseudo-merge commits
  ewah: implement `ewah_bitmap_popcount()`
  pack-bitmap: implement test helpers for pseudo-merge
  t/test-lib-functions.sh: support `--date` in `test_commit_bulk()`
  pack-bitmap.c: use pseudo-merges during traversal
  pack-bitmap: extra trace2 information
  ewah: `bitmap_equals_ewah()`
  pseudo-merge: implement support for finding existing merges
  t/perf: implement performace tests for pseudo-merge bitmaps

 Documentation/config.txt                     |   2 +
 Documentation/config/bitmap-pseudo-merge.txt |  75 ++
 Documentation/technical/bitmap-format.txt    | 205 +++++
 Makefile                                     |   1 +
 builtin/pack-objects.c                       |   3 +-
 config.c                                     |  18 +
 config.h                                     |   2 +
 ewah/bitmap.c                                |  76 ++
 ewah/ewok.h                                  |   3 +
 midx.c                                       |   3 +-
 pack-bitmap-write.c                          | 275 ++++++-
 pack-bitmap.c                                | 359 ++++++++-
 pack-bitmap.h                                |  16 +-
 pseudo-merge.c                               | 739 +++++++++++++++++++
 pseudo-merge.h                               | 218 ++++++
 t/helper/test-bitmap.c                       |  34 +-
 t/perf/p5333-pseudo-merge-bitmaps.sh         |  32 +
 t/t5333-pseudo-merge-bitmaps.sh              | 389 ++++++++++
 t/test-lib-functions.sh                      |  12 +-
 19 files changed, 2401 insertions(+), 61 deletions(-)
 create mode 100644 Documentation/config/bitmap-pseudo-merge.txt
 create mode 100644 pseudo-merge.c
 create mode 100644 pseudo-merge.h
 create mode 100755 t/perf/p5333-pseudo-merge-bitmaps.sh
 create mode 100755 t/t5333-pseudo-merge-bitmaps.sh

base-commit: 3bd955d26919e149552f34aacf8a4e6368c26cec