]> git.ipfire.org Git - thirdparty/git.git/commit
pack-bitmap: sort bitmaps before XORing
authorTaylor Blau <me@ttaylorr.com>
Wed, 27 May 2026 19:56:05 +0000 (15:56 -0400)
committerJunio C Hamano <gitster@pobox.com>
Wed, 27 May 2026 20:23:01 +0000 (05:23 +0900)
commitdcccd997462e2130bcc35f933285ff087454275e
treec7c1c808bd032751cb31a1383e08ac1a899cd343
parentc720bbcc53f223236220c7a879f0a0e73e5d3739
pack-bitmap: sort bitmaps before XORing

Reachability bitmaps may be stored as XORs against nearby bitmaps, up to
10 away. However, when callers provide selected commits in an arbitrary
order, the writer may miss good ancestor/descendant pairs and produce
much larger bitmap files without changing query coverage.

Sort the selected bitmaps in date order (from oldest to newest) before
computing XOR offsets, leaving pseudo-merge bitmaps alone (which we will
deal with separately in following commits).

On our same testing repository from previous commits, this change shrunk
our selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a
~72.24% reduction in the on-disk size of our *.bitmap file. The time to
generate the smaller bitmap file decreased by ~3.69 seconds, though this
is likely mostly noise.

Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
pack-bitmap-write.c