Makefile: Add git patch to fix pathological perf with bitmap indices

With commit eccda331e (blob: Enable use of bitmap indices when searching
LFS pointers, 2021-03-11), we have added a feature flag which allows the
use of bitmap indices to accelerate searching for LFS pointers. As it
turns out, our usage of git-rev-list(1) triggered a pathological edge
case when adding negative tags to its invocation when bitmap indices are
in use. This issue was fixed upstream with commit 540cdc11ad
(pack-bitmap: avoid traversal of objects referenced by uninteresting
tag, 2021-03-22), which has recently been merged to git's `next` branch.

Add the patch such that we can reenable the use of bitmap indices and
add more tests to verify that the since then newly added ListLFSPointers
and ListAllLFSPointers RPCs behave well with bitmap indices.

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