pack-bitmap: bitmap generation improvements
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v4 Latest24 patches 0 repliesNew
- v324 patches 3 repliesSuperseded
- v224 patches 46 repliesSuperseded
Earlier versions · 1
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v1 | 23 patches | 25 replies | Superseded |
Patches in v4 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/24 | ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW()ewah/ | +4 | 0 replies | |
| 2/24 | pack-bitmap: fix header size checkpack-bitmap.c | +4 | 0 replies | |
| 3/24 | pack-bitmap: bounds-check size of cache extensionpack-bitmap.c t/ | +21 | 0 replies | |
| 4/24 | t5310: drop size of truncated ewah bitmapt/ | +8 | 0 replies | |
| 5/24 | rev-list: die when --test-bitmap detects a mismatchpack-bitmap.c | +1 | 0 replies | |
| 6/24 | ewah: factor out bitmap growthewah/ | +9 | 0 replies | |
| 7/24 | ewah: make bitmap growth less aggressiveewah/ | +4 | 0 replies | |
| 8/24 | ewah: implement bitmap_or()ewah/ | +9 | 0 replies | |
| 9/24 | ewah: add bitmap_dup() functionewah/ ewah/ | +8 | 0 replies | |
| 10/24 | pack-bitmap-write: reimplement bitmap writingpack-bitmap-write.c | +172 | 0 replies | |
| 11/24 | pack-bitmap-write: pass ownership of intermediate bitmapspack-bitmap-write.c | +8 | 0 replies | |
| 12/24 | pack-bitmap-write: fill bitmap with commit historypack-bitmap-write.c | +23 | 0 replies | |
| 13/24 | bitmap: implement bitmap_is_subset()ewah/ ewah/ | +22 | 0 replies | |
| 14/24 | commit: implement commit_list_contains()commit.c commit.h | +13 | 0 replies | |
| 15/24 | t5310: add branch-based checkst/ | +34 | 0 replies | |
| 16/24 | pack-bitmap-write: rename children to reverse_edgespack-bitmap-write.c | +3 | 0 replies | |
| 17/24 | pack-bitmap.c: check reads more aggressively when loadingpack-bitmap.c | +6 | 0 replies | |
| 18/24 | pack-bitmap-write: build fewer intermediate bitmapspack-bitmap-write.c t/ | +148 | 0 replies | |
| 19/24 | pack-bitmap-write: ignore BITMAP_FLAG_REUSEbuiltin/ pack-bitmap-write.c pack-bitmap.c +1 more | +16 | 0 replies | |
| 20/24 | pack-bitmap: factor out 'bitmap_for_commit()'pack-bitmap.c pack-bitmap.h | +21 | 0 replies | |
| 21/24 | pack-bitmap: factor out 'add_commit_to_bitmap()'pack-bitmap.c | +21 | 0 replies | |
| 22/24 | pack-bitmap-write: use existing bitmapspack-bitmap-write.c | +36 | 0 replies | |
| 23/24 | pack-bitmap-write: relax unique revwalk conditionpack-bitmap-write.c t/ | +22 | 0 replies | |
| 24/24 | pack-bitmap-write: better reuse bitmapspack-bitmap-write.c | +38 | 0 replies |
Reviews trailers per patch
None of the 24 patches has a Reviewed-by or Acked-by.
| Patch | Junio C Hamano | Jeff King | Johannes Schindelin |
|---|---|---|---|
| 1/24 | |||
| 2/24 | |||
| 3/24 | |||
| 4/24 | Helped-by | ||
| 5/24 | |||
| 6/24 | |||
| 7/24 | |||
| 8/24 | |||
| 9/24 | |||
| 10/24 | |||
| 11/24 | |||
| 12/24 | |||
| 13/24 | Helped-by | ||
| 14/24 | |||
| 15/24 | Helped-by | ||
| 16/24 | |||
| 17/24 | |||
| 18/24 | Helped-by | Helped-by | |
| 19/24 | |||
| 20/24 | |||
| 21/24 | |||
| 22/24 | |||
| 23/24 | Helped-by | ||
| 24/24 |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes. Scroll the table sideways for all 3 reviewers.
Cover letter [PATCH v4 00/24] pack-bitmap: bitmap generation improvements
Here's v4 as requested from [1, 2], but I think we can safely call this "the improved v3", since all we're doing here is removing new instances of "master" as part of the ongoing default branch transition.
A range-diff that shows this is included below, but it counts v4's 4/24 as a complete replacement of v3's, so careful readers are encouraged to look at the inter-diff there.
I also snuck a typo-fix into 23/24 (which has existed unnoticed since v1) changing "rewalk" to "revwalk".
Sorry for all of the shuffling around, hopefully this one should do the trick.
[1]: https://lore.kernel.org/git/[email protected]/
[2]: https://lore.kernel.org/git/[email protected]/
Derrick Stolee (9):
pack-bitmap-write: fill bitmap with commit history
bitmap: implement bitmap_is_subset()
commit: implement commit_list_contains()
t5310: add branch-based checks
pack-bitmap-write: rename children to reverse_edges
pack-bitmap-write: build fewer intermediate bitmaps
pack-bitmap-write: use existing bitmaps
pack-bitmap-write: relax unique revwalk condition
pack-bitmap-write: better reuse bitmaps
Jeff King (11):
pack-bitmap: fix header size check
pack-bitmap: bounds-check size of cache extension
t5310: drop size of truncated ewah bitmap
rev-list: die when --test-bitmap detects a mismatch
ewah: factor out bitmap growth
ewah: make bitmap growth less aggressive
ewah: implement bitmap_or()
ewah: add bitmap_dup() function
pack-bitmap-write: reimplement bitmap writing
pack-bitmap-write: pass ownership of intermediate bitmaps
pack-bitmap-write: ignore BITMAP_FLAG_REUSE
Taylor Blau (4):
ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW() pack-bitmap.c: check reads more aggressively when loading
pack-bitmap: factor out 'bitmap_for_commit()'
pack-bitmap: factor out 'add_commit_to_bitmap()'
builtin/pack-objects.c | 1 - commit.c | 11 + commit.h | 2 + ewah/bitmap.c | 54 ++++- ewah/ewah_bitmap.c | 15 +- ewah/ewok.h | 3 +- pack-bitmap-write.c | 474 ++++++++++++++++++++++++++-------------- pack-bitmap.c | 139 ++++++------ pack-bitmap.h | 8 +- t/t5310-pack-bitmaps.sh | 177 +++++++++++---- 10 files changed, 583 insertions(+), 301 deletions(-)
Range-diff against v3:
1: 0b25ba4ca7 = 1: e72f85f82f ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW() 2: b455b248e4 = 2: b24395e4b0 pack-bitmap: fix header size check 3: 7322427444 = 3: 97533dba27 pack-bitmap: bounds-check size of cache extension 4: 055bc1fe66 < -: ---------- t5310: drop size of truncated ewah bitmap -: ---------- > 4: 2e7454d7b9 t5310: drop size of truncated ewah bitmap 5: c99cacea67 = 5: 3cb4156372 rev-list: die when --test-bitmap detects a mismatch 6: b79360383e = 6: 570bf22425 ewah: factor out bitmap growth 7: 4b56f12932 = 7: 48a1949ee6 ewah: make bitmap growth less aggressive 8: 34137a7f35 = 8: 04bf0de474 ewah: implement bitmap_or() 9: fe89f87716 = 9: c8bd4ed5fa ewah: add bitmap_dup() function 10: 91cd8b1a49 = 10: bbeb87a95d pack-bitmap-write: reimplement bitmap writing 11: 64598024ec = 11: f87c11700b pack-bitmap-write: pass ownership of intermediate bitmaps 12: 93fc437a3c = 12: c466dda576 pack-bitmap-write: fill bitmap with commit history 13: 0d5213ba44 = 13: 0cfa932b71 bitmap: implement bitmap_is_subset() 14: 72e745fed8 = 14: 033fb2ed55 commit: implement commit_list_contains() 15: c2cae4a8d0 ! 15: 76071f9f4e t5310: add branch-based checks
@@ Commit message
'master' and 'other' branches.
+ Helped-by: Junio C Hamano <[email protected]>
## t/t5310-pack-bitmaps.sh ##
@@ t/t5310-pack-bitmaps.sh: test_expect_success 'rev-list --test-bitmap verifies bi
- test_expect_success "counting non-linear history ($state)" '
+ test_expect_success "counting non-linear history ($state, $branch)" '
- git rev-list --count other...master >expect &&
- git rev-list --use-bitmap-index --count other...master >actual &&
+ git rev-list --count other...second >expect &&
+ git rev-list --use-bitmap-index --count other...second >actual &&
test_cmp expect actual
'
@@ t/t5310-pack-bitmaps.sh: test_expect_success 'rev-list --test-bitmap verifies bi
+rev_list_tests () {
+ state=$1
+
-+ for branch in "master" "other"
++ for branch in "second" "other"
+ do
+ rev_list_tests_head
+ done
16: c0e2b6f5d9 = 16: d8c6f0f0bc pack-bitmap-write: rename children to reverse_edges
17: 37f9636098 = 17: 2e08243706 pack-bitmap.c: check reads more aggressively when loading
18: e520c8fdc4 ! 18: b4c5d2c3df pack-bitmap-write: build fewer intermediate bitmaps
@@ Commit message
Helped-by: Jeff King <[email protected]>
Signed-off-by: Derrick Stolee <[email protected]>
+ Helped-by: Johannes Schindelin <[email protected]>
Signed-off-by: Taylor Blau <[email protected]>
## pack-bitmap-write.c ##
@@ t/t5310-pack-bitmaps.sh: has_any () {
test_expect_success 'setup repo with moderate-sized history' '
- test_commit_bulk --id=file 100 &&
+ test_commit_bulk --id=file 10 &&
+ git branch -M second &&
git checkout -b other HEAD~5 &&
test_commit_bulk --id=side 10 &&
+
@@ t/t5310-pack-bitmaps.sh: has_any () {
+ # ambiguous merge-bases
+
+ git checkout -b merge-left other~2 &&
-+ git merge master~2 -m "merge-left" &&
++ git merge second~2 -m "merge-left" &&
+
-+ git checkout -b merge-right master~1 &&
++ git checkout -b merge-right second~1 &&
+ git merge other~1 -m "merge-right" &&
+
-+ git checkout -b octo-master master &&
-+ git merge merge-left merge-right -m "octopus-master" &&
++ git checkout -b octo-second second &&
++ git merge merge-left merge-right -m "octopus-second" &&
+
+ git checkout -b octo-other other &&
+ git merge merge-left merge-right -m "octopus-other" &&
@@ t/t5310-pack-bitmaps.sh: has_any () {
+ git checkout other &&
+ git merge octo-other -m "pull octopus" &&
+
- git checkout master &&
-+ git merge octo-master -m "pull octopus" &&
+ git checkout second &&
++ git merge octo-second -m "pull octopus" &&
+
+ # Remove these branches so they are not selected
+ # as bitmap tips
+ git branch -D merge-left &&
+ git branch -D merge-right &&
+ git branch -D octo-other &&
-+ git branch -D octo-master &&
++ git branch -D octo-second &&
+
+ # add padding to make these merges less interesting
+ # and avoid having them selected for bitmaps
+ test_commit_bulk --id=file 100 &&
+ git checkout other &&
+ test_commit_bulk --id=side 100 &&
-+ git checkout master &&
++ git checkout second &&
+
- bitmaptip=$(git rev-parse master) &&
+ bitmaptip=$(git rev-parse second) &&
blob=$(echo tagged-blob | git hash-object -w --stdin) &&
git tag tagged-blob $blob &&
@@ t/t5310-pack-bitmaps.sh: test_expect_success 'setup repo with moderate-sized history' '
19: c3975fcf78 = 19: d973cf240d pack-bitmap-write: ignore BITMAP_FLAG_REUSE
20: d5ef2c7f81 = 20: 4d7a4184ac pack-bitmap: factor out 'bitmap_for_commit()'
21: f0500190f0 = 21: bd3a16088b pack-bitmap: factor out 'add_commit_to_bitmap()'
22: c6fde2b0c4 = 22: e0d989b98f pack-bitmap-write: use existing bitmaps
23: 50d2031deb ! 23: 8f9fdb0f43 pack-bitmap-write: relax unique rewalk condition @@ Metadata
Author: Derrick Stolee <[email protected]>
## Commit message ##
- pack-bitmap-write: relax unique rewalk condition
+ pack-bitmap-write: relax unique revwalk condition
The previous commits improved the bitmap computation process for very long, linear histories with many refs by removing quadratic growth in
@@ Commit message
this patch | 88.478 | 53.218 | 2.157 | 2.224 |
+ Helped-by: Johannes Schindelin <[email protected]>
## pack-bitmap-write.c ##
@@ pack-bitmap-write.c: static void bitmap_builder_init(struct bitmap_builder *bb,
## t/t5310-pack-bitmaps.sh ##
+@@ t/t5310-pack-bitmaps.sh: has_any () {
+ # To ensure the logic for "maximal commits" is exercised, make
+ # the repository a bit more complicated.
+ #
+-# other master
++# other second
+ # * *
+ # (99 commits) (99 commits)
+ # * *
+ # |\ /|
+-# | * octo-other octo-master * |
++# | * octo-other octo-second * |
+ # |/|\_________ ____________/|\|
+ # | \ \/ __________/ |
+ # | | ________/\ / |
@@ t/t5310-pack-bitmaps.sh: has_any () {
# \|
# * (base)
@@ t/t5310-pack-bitmaps.sh: has_any () {
-# for master (bit 0) and other (bit 1), and some flexibility -# in the order that merge bases are visited, the bitmasks at -# the end should be:
-+# for master (bit 0) and other (bit 1), the bitmasks at the ++# for second (bit 0) and other (bit 1), the bitmasks at the
+# end should be:
#
- # master: 1 (maximal, selected)
+-# master: 1 (maximal, selected)
++# second: 1 (maximal, selected)
# other: 01 (maximal, selected)
-# octo-master: 1
-# octo-other: 01
24: 6b9950771e = 24: 720b6e0dc7 pack-bitmap-write: better reuse bitmaps --
2.29.2.533.g07db1f5344