Skip to content

pack-bitmap: bitmap generation improvements

Taylor Blau git 4 versions – New

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest24 patches 0 repliesNew
  2. v324 patches 3 repliesSuperseded
  3. v224 patches 46 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v123 patches25 repliesSuperseded

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/24ewah/ewah_bitmap.c: avoid open-coding ALLOC_GROW()ewah/ewah_bitmap.c+4 -110 replies
2/24pack-bitmap: fix header size checkpack-bitmap.c+4 -30 replies
3/24pack-bitmap: bounds-check size of cache extensionpack-bitmap.c t/t5310-pack-bitmaps.sh+21 -40 replies
4/24t5310: drop size of truncated ewah bitmapt/t5310-pack-bitmaps.sh+8 -70 replies
5/24rev-list: die when --test-bitmap detects a mismatchpack-bitmap.c+1 -10 replies
6/24ewah: factor out bitmap growthewah/bitmap.c+9 -50 replies
7/24ewah: make bitmap growth less aggressiveewah/bitmap.c+4 -70 replies
8/24ewah: implement bitmap_or()ewah/bitmap.c+9 -00 replies
9/24ewah: add bitmap_dup() functionewah/bitmap.c ewah/ewok.h+8 -00 replies
10/24pack-bitmap-write: reimplement bitmap writingpack-bitmap-write.c+172 -1340 replies
11/24pack-bitmap-write: pass ownership of intermediate bitmapspack-bitmap-write.c+8 -20 replies
12/24pack-bitmap-write: fill bitmap with commit historypack-bitmap-write.c+23 -70 replies
13/24bitmap: implement bitmap_is_subset()ewah/bitmap.c ewah/ewok.h+22 -10 replies
14/24commit: implement commit_list_contains()commit.c commit.h+13 -00 replies
15/24t5310: add branch-based checkst/t5310-pack-bitmaps.sh+34 -270 replies
16/24pack-bitmap-write: rename children to reverse_edgespack-bitmap-write.c+3 -30 replies
17/24pack-bitmap.c: check reads more aggressively when loadingpack-bitmap.c+6 -10 replies
18/24pack-bitmap-write: build fewer intermediate bitmapspack-bitmap-write.c t/t5310-pack-bitmaps.sh+148 -90 replies
19/24pack-bitmap-write: ignore BITMAP_FLAG_REUSEbuiltin/pack-objects.c pack-bitmap-write.c pack-bitmap.c +1 more+16 -870 replies
20/24pack-bitmap: factor out 'bitmap_for_commit()'pack-bitmap.c pack-bitmap.h+21 -140 replies
21/24pack-bitmap: factor out 'add_commit_to_bitmap()'pack-bitmap.c+21 -150 replies
22/24pack-bitmap-write: use existing bitmapspack-bitmap-write.c+36 -40 replies
23/24pack-bitmap-write: relax unique revwalk conditionpack-bitmap-write.c t/t5310-pack-bitmaps.sh+22 -250 replies
24/24pack-bitmap-write: better reuse bitmapspack-bitmap-write.c+38 -20 replies

Reviews trailers per patch

None of the 24 patches has a Reviewed-by or Acked-by.

PatchJunio C HamanoJeff KingJohannes Schindelin
1/24
2/24
3/24
4/24Helped-by
5/24
6/24
7/24
8/24
9/24
10/24
11/24
12/24
13/24Helped-by
14/24
15/24Helped-by
16/24
17/24
18/24Helped-by Helped-by
19/24
20/24
21/24
22/24
23/24Helped-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.

Read the v4 thread

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