diff options
Diffstat (limited to '_support')
| -rw-r--r-- | _support/git-patches/pack-bitmap-avoid-traversal-of-uninteresting-tag.patch | 102 |
1 files changed, 102 insertions, 0 deletions
diff --git a/_support/git-patches/pack-bitmap-avoid-traversal-of-uninteresting-tag.patch b/_support/git-patches/pack-bitmap-avoid-traversal-of-uninteresting-tag.patch new file mode 100644 index 000000000..03ab856ef --- /dev/null +++ b/_support/git-patches/pack-bitmap-avoid-traversal-of-uninteresting-tag.patch @@ -0,0 +1,102 @@ +commit 540cdc11adf0574a9a2d52fc687a84a2f4a93ad8 +Author: Patrick Steinhardt <ps@pks.im> +Date: Mon Mar 22 13:19:06 2021 +0100 + + pack-bitmap: avoid traversal of objects referenced by uninteresting tag + + When preparing the bitmap walk, we first establish the set of of have + and want objects by iterating over the set of pending objects: if an + object is marked as uninteresting, it's declared as an object we already + have, otherwise as an object we want. These two sets are then used to + compute which transitively referenced objects we need to obtain. + + One special case here are tag objects: when a tag is requested, we + resolve it to its first not-tag object and add both resolved objects as + well as the tag itself into either the have or want set. Given that the + uninteresting-property always propagates to referenced objects, it is + clear that if the tag is uninteresting, so are its children and vice + versa. But we fail to propagate the flag, which effectively means that + referenced objects will always be interesting except for the case where + they have already been marked as uninteresting explicitly. + + This mislabeling does not impact correctness: we now have it in our + "wants" set, and given that we later do an `AND NOT` of the bitmaps of + "wants" and "haves" sets it is clear that the result must be the same. + But we now start to needlessly traverse the tag's referenced objects in + case it is uninteresting, even though we know that each referenced + object will be uninteresting anyway. In the worst case, this can lead to + a complete graph walk just to establish that we do not care for any + object. + + Fix the issue by propagating the `UNINTERESTING` flag to pointees of tag + objects and add a benchmark with negative revisions to p5310. This shows + some nice performance benefits, tested with linux.git: + + Test HEAD~ HEAD + --------------------------------------------------------------------------------------------------------------- + 5310.3: repack to disk 193.18(181.46+16.42) 194.61(183.41+15.83) +0.7% + 5310.4: simulated clone 25.93(24.88+1.05) 25.81(24.73+1.08) -0.5% + 5310.5: simulated fetch 2.64(5.30+0.69) 2.59(5.16+0.65) -1.9% + 5310.6: pack to file (bitmap) 58.75(57.56+6.30) 58.29(57.61+5.73) -0.8% + 5310.7: rev-list (commits) 1.45(1.18+0.26) 1.46(1.22+0.24) +0.7% + 5310.8: rev-list (objects) 15.35(14.22+1.13) 15.30(14.23+1.07) -0.3% + 5310.9: rev-list with tag negated via --not --all (objects) 22.49(20.93+1.56) 0.11(0.09+0.01) -99.5% + 5310.10: rev-list with negative tag (objects) 0.61(0.44+0.16) 0.51(0.35+0.16) -16.4% + 5310.11: rev-list count with blob:none 12.15(11.19+0.96) 12.18(11.19+0.99) +0.2% + 5310.12: rev-list count with blob:limit=1k 17.77(15.71+2.06) 17.75(15.63+2.12) -0.1% + 5310.13: rev-list count with tree:0 1.69(1.31+0.38) 1.68(1.28+0.39) -0.6% + 5310.14: simulated partial clone 20.14(19.15+0.98) 19.98(18.93+1.05) -0.8% + 5310.16: clone (partial bitmap) 12.78(13.89+1.07) 12.72(13.99+1.01) -0.5% + 5310.17: pack to file (partial bitmap) 42.07(45.44+2.72) 41.44(44.66+2.80) -1.5% + 5310.18: rev-list with tree filter (partial bitmap) 0.44(0.29+0.15) 0.46(0.32+0.14) +4.5% + + While most benchmarks are probably in the range of noise, the newly + added 5310.9 and 5310.10 benchmarks consistenly perform better. + + Signed-off-by: Patrick Steinhardt <ps@pks.im>. + Signed-off-by: Junio C Hamano <gitster@pobox.com> + +diff --git a/pack-bitmap.c b/pack-bitmap.c +index 4077e731e8..2d3bc415da 100644 +--- a/pack-bitmap.c ++++ b/pack-bitmap.c +@@ -969,6 +969,7 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, + object_list_insert(object, &wants); + + object = parse_object_or_die(get_tagged_oid(tag), NULL); ++ object->flags |= (tag->object.flags & UNINTERESTING); + } + + if (object->flags & UNINTERESTING) +diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh +index b3e725f031..452be01056 100755 +--- a/t/perf/p5310-pack-bitmaps.sh ++++ b/t/perf/p5310-pack-bitmaps.sh +@@ -15,6 +15,12 @@ test_expect_success 'setup bitmap config' ' + git config pack.writebitmaps true + ' + ++# we need to create the tag up front such that it is covered by the repack and ++# thus by generated bitmaps. ++test_expect_success 'create tags' ' ++ git tag --message="tag pointing to HEAD" perf-tag HEAD ++' ++ + test_perf 'repack to disk' ' + git repack -ad + ' +@@ -43,6 +49,14 @@ test_perf 'rev-list (objects)' ' + git rev-list --all --use-bitmap-index --objects >/dev/null + ' + ++test_perf 'rev-list with tag negated via --not --all (objects)' ' ++ git rev-list perf-tag --not --all --use-bitmap-index --objects >/dev/null ++' ++ ++test_perf 'rev-list with negative tag (objects)' ' ++ git rev-list HEAD --not perf-tag --use-bitmap-index --objects >/dev/null ++' ++ + test_perf 'rev-list count with blob:none' ' + git rev-list --use-bitmap-index --count --objects --all \ + --filter=blob:none >/dev/null |