[PATCH 0/8] pack-bitmap-write: speed up bitmap generation

[Taylor Blau <me@ttaylorr.com>]

Note to the maintainer:

 * This series is based on 'tb/pseudo-merge-bugfixes', with
   'ps/clang-w-glibc-2.43-and-_Generic' merged in. I suggest queueing it
   as 'tb/bitmap-build-performance'.

   The latter merge is only to avoid the current Clang/glibc 2.43 CI
   breakage, and is unrelated to the bitmap changes themselves.

This series improves the performance of reachability bitmap generation,
focusing on very large repositories and the penalty to generate
pseudo-merge reachability bitmaps.

The first few patches address hot paths in the ordinary bitmap build:

 - pass object positions into `fill_bitmap_tree()` so callers can avoid
   redundant lookups,

 - check subtree bits before recursing, which avoids many no-op
   `fill_bitmap_tree()` calls,

 - reuse already-stored selected bitmaps when `fill_bitmap_commit()`
   reaches a selected ancestor, and

 - add a small direct-mapped cache from object IDs to bitmap positions
   to avoid repeated pack/MIDX lookups while filling bitmaps.

On the large repository that I have been using to benchmark these
changes (~4.8M commits and ~57M total objects), the no-pseudo-merge
bitmap generation case drops **from ~612.5 seconds to ~294.1 seconds**.

The next patch sorts selected bitmaps before choosing XOR offsets. This
does not change bitmap selection/coverage, but in the same repository it
shrinks the generated bitmap file **from ~635.5 MiB to ~176.4 MiB** by
putting related ancestor/descendant bitmaps close enough together for
the XOR search window to find them.

The final two patches focus on pseudo-merge bitmaps. The existing code
feeds pseudo-merges into the same maximal-commit selection machinery as
ordinary selected commits. That machinery works well for real history,
but not pseudo-merges.

Instead, this series builds ordinary selected bitmaps first, then builds
pseudo-merge bitmaps afterwards. The later pseudo-merge fill can still
reuse stored selected ancestor bitmaps, and can also reuse an existing
on-disk pseudo-merge bitmap when the parent set matches.

With the coarse pseudo-merge configuration used for testing:

    [bitmapPseudoMerge "all"]
        pattern=refs/
        threshold=now
        stableSize=10000000
        maxMerges=8

, the optimized no-pseudo-merge case takes ~294.1 seconds, while the
**pseudo-merge case takes ~328.4 seconds**. Before the final change, the
same pseudo-merge configuration took ~575.0 seconds.

On our testing repository, it is faster at the end of this series to
generate bitmaps with pseudo-merges (~328 seconds as above) than it is
to generate bitmaps without pseudo-merges at the start of this series
(~612 seconds).

Thanks in advance for your review!

Taylor Blau (8):
  pack-bitmap: pass object position to `fill_bitmap_tree()`
  pack-bitmap: check subtree bits before recursing
  pack-bitmap: reuse stored selected bitmaps
  pack-bitmap: consolidate `find_object_pos()` success path
  pack-bitmap: cache object positions during fill
  pack-bitmap: sort bitmaps before XORing
  pack-bitmap: remember pseudo-merge parents
  pack-bitmap: build pseudo-merge bitmaps after regular bitmaps

 pack-bitmap-write.c | 431 +++++++++++++++++++++++++++++++++++++-------
 pack-bitmap.h       |   7 +
 2 files changed, 377 insertions(+), 61 deletions(-)


base-commit: c3d7ca7d982efc3a848fd85f34e867cfc0a99479
-- 
2.54.0.rc1.84.g30ce254312c