From: Taylor Blau <me@ttaylorr.com>
To: git@vger.kernel.org
Cc: Jeff King <peff@peff.net>, Elijah Newren <newren@gmail.com>,
Junio C Hamano <gitster@pobox.com>
Subject: [PATCH 00/24] pack-bitmap: pseudo-merge reachability bitmaps
Date: Wed, 20 Mar 2024 18:04:57 -0400 [thread overview]
Message-ID: <cover.1710972293.git.me@ttaylorr.com> (raw)
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
--
2.44.0.303.g1dc5e5b124c
next reply other threads:[~2024-03-20 22:04 UTC|newest]
Thread overview: 74+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-20 22:04 Taylor Blau [this message]
2024-03-20 22:05 ` [PATCH 01/24] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-03-21 21:24 ` Junio C Hamano
2024-03-21 22:13 ` Taylor Blau
2024-03-21 22:22 ` Junio C Hamano
2024-03-20 22:05 ` [PATCH 02/24] config: repo_config_get_expiry() Taylor Blau
2024-04-10 17:54 ` Jeff King
2024-04-29 19:39 ` Taylor Blau
2024-03-20 22:05 ` [PATCH 03/24] ewah: implement `ewah_bitmap_is_subset()` Taylor Blau
2024-04-10 18:05 ` Jeff King
2024-04-29 19:47 ` Taylor Blau
2024-03-20 22:05 ` [PATCH 04/24] pack-bitmap: drop unused `max_bitmaps` parameter Taylor Blau
2024-04-10 18:06 ` Jeff King
2024-03-20 22:05 ` [PATCH 05/24] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-04-10 18:10 ` Jeff King
2024-03-20 22:05 ` [PATCH 06/24] pseudo-merge.ch: initial commit Taylor Blau
2024-03-20 22:05 ` [PATCH 07/24] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 08/24] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-03-20 22:05 ` [PATCH 09/24] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-03-20 22:05 ` [PATCH 10/24] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 11/24] pack-bitmap-write.c: select " Taylor Blau
2024-03-20 22:05 ` [PATCH 12/24] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-03-20 22:05 ` [PATCH 13/24] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-03-20 22:05 ` [PATCH 14/24] pseudo-merge: scaffolding for reads Taylor Blau
2024-03-20 22:05 ` [PATCH 15/24] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-03-20 22:05 ` [PATCH 16/24] pseudo-merge: implement support for reading pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 17/24] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-03-20 22:05 ` [PATCH 18/24] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-03-20 22:05 ` [PATCH 19/24] t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` Taylor Blau
2024-03-20 22:05 ` [PATCH 20/24] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-03-20 22:06 ` [PATCH 21/24] pack-bitmap: extra trace2 information Taylor Blau
2024-03-20 22:06 ` [PATCH 22/24] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-03-20 22:06 ` [PATCH 23/24] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-03-20 22:06 ` [PATCH 24/24] t/perf: implement performace tests for pseudo-merge bitmaps Taylor Blau
2024-03-21 19:50 ` [PATCH 00/24] pack-bitmap: pseudo-merge reachability bitmaps Junio C Hamano
2024-04-29 20:42 ` [PATCH v2 00/23] " Taylor Blau
2024-04-29 20:42 ` [PATCH v2 01/23] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 16:37 ` Taylor Blau
2024-05-10 11:46 ` Patrick Steinhardt
2024-04-29 20:43 ` [PATCH v2 02/23] ewah: implement `ewah_bitmap_is_subset()` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 03/23] pack-bitmap: drop unused `max_bitmaps` parameter Taylor Blau
2024-04-29 20:43 ` [PATCH v2 04/23] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 18:24 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 05/23] pseudo-merge.ch: initial commit Taylor Blau
2024-04-29 20:43 ` [PATCH v2 06/23] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 18:48 ` Taylor Blau
2024-05-10 11:47 ` Patrick Steinhardt
2024-04-29 20:43 ` [PATCH v2 07/23] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 08/23] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-04-29 20:43 ` [PATCH v2 09/23] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-05-06 11:53 ` Patrick Steinhardt
2024-05-06 19:58 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 10/23] pack-bitmap-write.c: select " Taylor Blau
2024-05-06 11:53 ` Patrick Steinhardt
2024-05-06 20:05 ` Taylor Blau
2024-05-10 11:47 ` Patrick Steinhardt
2024-04-29 20:43 ` [PATCH v2 11/23] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-04-29 20:43 ` [PATCH v2 12/23] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-04-29 20:43 ` [PATCH v2 13/23] pseudo-merge: scaffolding for reads Taylor Blau
2024-04-29 20:43 ` [PATCH v2 14/23] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-04-29 20:44 ` [PATCH v2 15/23] pseudo-merge: implement support for reading pseudo-merge commits Taylor Blau
2024-04-29 20:44 ` [PATCH v2 16/23] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 17/23] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-04-29 20:44 ` [PATCH v2 18/23] t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 19/23] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-04-29 20:44 ` [PATCH v2 20/23] pack-bitmap: extra trace2 information Taylor Blau
2024-04-29 20:44 ` [PATCH v2 21/23] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 22/23] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-04-29 20:44 ` [PATCH v2 23/23] t/perf: implement performace tests for pseudo-merge bitmaps Taylor Blau
2024-04-30 20:03 ` [PATCH v2 00/23] pack-bitmap: pseudo-merge reachability bitmaps Junio C Hamano
2024-05-01 14:40 ` Taylor Blau
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=cover.1710972293.git.me@ttaylorr.com \
--to=me@ttaylorr.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=newren@gmail.com \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).