{"thread":{"id":"55339","subject":"[PATCH] pack-bitmap: avoid traversal of objects referenced by uninteresting tag","startedAt":"2021-03-17T16:07:31Z","lastAt":"2021-03-22T12:20:18Z","messageCount":4,"participants":["Patrick Steinhardt","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"419479","messageId":"e342077ed116fb47c6a0fa645abd5558310efb09.1615993858.git.ps@pks.im","threadId":"55339","inReplyTo":null,"subject":"[PATCH] pack-bitmap: avoid traversal of objects referenced by uninteresting tag","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-03-17T15:11:14Z","receivedAt":"2021-03-17T16:07:31Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When preparing the bitmap walk, we first establish the set of of have\nand want objects by iterating over the set of pending objects: if an\nobject is marked as uninteresting, it's declared as an object we already\nhave, otherwise as an object we want. These two sets are then used to\ncompute which transitively referenced objects we need to obtain.\n\nOne special case here are tag objects: when a tag is requested, we\nresolve it to its first not-tag object and add both resolved objects as\nwell as the tag itself into either the have or want set. Given that the\nuninteresting-property always propagates to referenced objects, it is\nclear that if the tag is uninteresting, so are its children and vice\nversa. But we fail to propagate the flag, which effectively means that\nreferenced objects will always be interesting except for the case where\nthey have already been marked as uninteresting explicitly.\n\nThis mislabeling does not impact correctness: we now have it in our\n\"wants\" set, and given that we later do an `AND NOT` of the bitmaps of\n\"wants\" and \"haves\" sets it is clear that the result must be the same.\nBut we now start to needlessly traverse the tag's referenced objects in\ncase it is uninteresting, even though we know that each referenced\nobject will be uninteresting anyway. In the worst case, this can lead to\na complete graph walk just to establish that we do not care for any\nobject.\n\nFix the issue by propagating the `UNINTERESTING` flag to pointees of tag\nobjects and add a benchmark with negative revisions to p5310. This shows\nsome nice performance benefits, tested with linux.git:\n\nTest                                                  HEAD                   HEAD~\n--------------------------------------------------------------------------------------------------------\n5310.2: repack to disk                                194.96(183.59+16.01)   195.98(184.04+16.67) +0.5%\n5310.3: simulated clone                               26.09(25.04+1.05)      26.11(24.95+1.16) +0.1%\n5310.4: simulated fetch                               2.64(5.25+0.72)        2.59(4.99+0.72) -1.9%\n5310.5: pack to file (bitmap)                         58.70(58.19+5.66)      58.99(58.66+5.52) +0.5%\n5310.6: rev-list (commits)                            1.46(1.19+0.27)        1.47(1.21+0.25) +0.7%\n5310.7: rev-list (objects)                            15.54(14.48+1.06)      16.17(15.06+1.11) +4.1%\n5310.8: rev-list with negation (objects)              0.09(0.07+0.02)        23.13(21.53+1.60) +25600.0%\n5310.9: rev-list count with blob:none                 12.40(11.43+0.97)      12.38(11.33+1.04) -0.2%\n5310.10: rev-list count with blob:limit=1k            18.14(16.09+2.05)      18.26(16.18+2.07) +0.7%\n5310.11: rev-list count with tree:0                   1.71(1.32+0.39)        1.67(1.31+0.36) -2.3%\n5310.12: simulated partial clone                      20.20(19.15+1.04)      20.45(19.34+1.10) +1.2%\n5310.14: clone (partial bitmap)                       12.68(13.89+1.03)      12.84(13.91+1.03) +1.3%\n5310.15: pack to file (partial bitmap)                42.10(45.33+2.76)      42.30(45.41+2.76) +0.5%\n5310.16: rev-list with tree filter (partial bitmap)   0.47(0.30+0.16)        0.45(0.30+0.14) -4.3%\n\nWhile most benchmarks are probably in the range of noise, the newly\nadded 5310.8 benchmark shows a performance improvement of 25600%.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>.\n---\n pack-bitmap.c                | 1 +\n t/perf/p5310-pack-bitmaps.sh | 4 ++++\n 2 files changed, 5 insertions(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 1f69b5fa85..11118a92e8 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -997,6 +997,7 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\t\tobject_list_insert(object, &wants);\n \n \t\t\tobject = parse_object_or_die(get_tagged_oid(tag), NULL);\n+\t\t\tobject->flags |= (tag->object.flags & UNINTERESTING);\n \t\t}\n \n \t\tif (object->flags & UNINTERESTING)\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex b3e725f031..2910c818ac 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -43,6 +43,10 @@ test_perf 'rev-list (objects)' '\n \tgit rev-list --all --use-bitmap-index --objects >/dev/null\n '\n \n+test_perf 'rev-list with negation (objects)' '\n+\tgit rev-list --not --all --use-bitmap-index --objects >/dev/null\n+'\n+\n test_perf 'rev-list count with blob:none' '\n \tgit rev-list --use-bitmap-index --count --objects --all \\\n \t\t--filter=blob:none >/dev/null\n-- \n2.31.0\n\n"},{"id":"419673","messageId":"xmqqk0q4ov95.fsf@gitster.g","threadId":"55339","inReplyTo":"e342077ed116fb47c6a0fa645abd5558310efb09.1615993858.git.ps@pks.im","subject":"Re: [PATCH] pack-bitmap: avoid traversal of objects referenced by uninteresting tag","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-03-19T00:13:58Z","receivedAt":"2021-03-19T00:14:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> While most benchmarks are probably in the range of noise, the newly\n> added 5310.8 benchmark shows a performance improvement of 25600%.\n\nwhich sounds impressive, but ...\n\n> +test_perf 'rev-list with negation (objects)' '\n> +\tgit rev-list --not --all --use-bitmap-index --objects >/dev/null\n> +'\n\n... is this an interesting use case to begin with, without any\npositive end?\n\n> +\n>  test_perf 'rev-list count with blob:none' '\n>  \tgit rev-list --use-bitmap-index --count --objects --all \\\n>  \t\t--filter=blob:none >/dev/null\n"},{"id":"419944","messageId":"YFiKqf8P0XVSca8L@ncase","threadId":"55339","inReplyTo":"xmqqk0q4ov95.fsf@gitster.g","subject":"Re: [PATCH] pack-bitmap: avoid traversal of objects referenced by uninteresting tag","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-03-22T12:16:49Z","receivedAt":"2021-03-22T12:18:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Mar 18, 2021 at 05:13:58PM -0700, Junio C Hamano wrote:\n> Patrick Steinhardt <ps@pks.im> writes:\n> \n> > While most benchmarks are probably in the range of noise, the newly\n> > added 5310.8 benchmark shows a performance improvement of 25600%.\n> \n> which sounds impressive, but ...\n> \n> > +test_perf 'rev-list with negation (objects)' '\n> > +\tgit rev-list --not --all --use-bitmap-index --objects >/dev/null\n> > +'\n> \n> ... is this an interesting use case to begin with, without any\n> positive end?\n\nNot at all, but it's easy enough to end up with something similar. E.g.\n`git rev-list $TAG --not --all` wouldn't typically show anything at all\nif `$TAG` is covered by a revision either, but it shows the same\nspeedup.\n\nI've changed the benchmark to be a bit more realistic here. I've also\nadded a second benchmark which shows a modest 16-20% speedup when using\n`git rev-list HEAD --not $TAG`, where `HEAD` and `$TAG` point to the\nsame commit. There's probably other cases that may show speedups, but I\nhope those are good enough for now.\n\nPatrick\n"},{"id":"419945","messageId":"f9aae7a54ec5bb957cb1882f3da465bc8b09388b.1616415462.git.ps@pks.im","threadId":"55339","inReplyTo":"e342077ed116fb47c6a0fa645abd5558310efb09.1615993858.git.ps@pks.im","subject":"[PATCH v2] pack-bitmap: avoid traversal of objects referenced by uninteresting tag","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-03-22T12:19:06Z","receivedAt":"2021-03-22T12:20:18Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When preparing the bitmap walk, we first establish the set of of have\nand want objects by iterating over the set of pending objects: if an\nobject is marked as uninteresting, it's declared as an object we already\nhave, otherwise as an object we want. These two sets are then used to\ncompute which transitively referenced objects we need to obtain.\n\nOne special case here are tag objects: when a tag is requested, we\nresolve it to its first not-tag object and add both resolved objects as\nwell as the tag itself into either the have or want set. Given that the\nuninteresting-property always propagates to referenced objects, it is\nclear that if the tag is uninteresting, so are its children and vice\nversa. But we fail to propagate the flag, which effectively means that\nreferenced objects will always be interesting except for the case where\nthey have already been marked as uninteresting explicitly.\n\nThis mislabeling does not impact correctness: we now have it in our\n\"wants\" set, and given that we later do an `AND NOT` of the bitmaps of\n\"wants\" and \"haves\" sets it is clear that the result must be the same.\nBut we now start to needlessly traverse the tag's referenced objects in\ncase it is uninteresting, even though we know that each referenced\nobject will be uninteresting anyway. In the worst case, this can lead to\na complete graph walk just to establish that we do not care for any\nobject.\n\nFix the issue by propagating the `UNINTERESTING` flag to pointees of tag\nobjects and add a benchmark with negative revisions to p5310. This shows\nsome nice performance benefits, tested with linux.git:\n\nTest                                                          HEAD~                  HEAD\n---------------------------------------------------------------------------------------------------------------\n5310.3: repack to disk                                        193.18(181.46+16.42)   194.61(183.41+15.83) +0.7%\n5310.4: simulated clone                                       25.93(24.88+1.05)      25.81(24.73+1.08) -0.5%\n5310.5: simulated fetch                                       2.64(5.30+0.69)        2.59(5.16+0.65) -1.9%\n5310.6: pack to file (bitmap)                                 58.75(57.56+6.30)      58.29(57.61+5.73) -0.8%\n5310.7: rev-list (commits)                                    1.45(1.18+0.26)        1.46(1.22+0.24) +0.7%\n5310.8: rev-list (objects)                                    15.35(14.22+1.13)      15.30(14.23+1.07) -0.3%\n5310.9: rev-list with tag negated via --not --all (objects)   22.49(20.93+1.56)      0.11(0.09+0.01) -99.5%\n5310.10: rev-list with negative tag (objects)                 0.61(0.44+0.16)        0.51(0.35+0.16) -16.4%\n5310.11: rev-list count with blob:none                        12.15(11.19+0.96)      12.18(11.19+0.99) +0.2%\n5310.12: rev-list count with blob:limit=1k                    17.77(15.71+2.06)      17.75(15.63+2.12) -0.1%\n5310.13: rev-list count with tree:0                           1.69(1.31+0.38)        1.68(1.28+0.39) -0.6%\n5310.14: simulated partial clone                              20.14(19.15+0.98)      19.98(18.93+1.05) -0.8%\n5310.16: clone (partial bitmap)                               12.78(13.89+1.07)      12.72(13.99+1.01) -0.5%\n5310.17: pack to file (partial bitmap)                        42.07(45.44+2.72)      41.44(44.66+2.80) -1.5%\n5310.18: rev-list with tree filter (partial bitmap)           0.44(0.29+0.15)        0.46(0.32+0.14) +4.5%\n\nWhile most benchmarks are probably in the range of noise, the newly\nadded 5310.9 and 5310.10 benchmarks consistenly perform better.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>.\n---\n\nVersion two of this patch modifies the benchmark to be a bit more\nrealistic by also adding a positive query (previously, all queries were\nnegative so it's clear that it can't ever show anything). I've also\nadded a second benchmark.\n\n pack-bitmap.c                |  1 +\n t/perf/p5310-pack-bitmaps.sh | 14 ++++++++++++++\n 2 files changed, 15 insertions(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 1f69b5fa85..11118a92e8 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -997,6 +997,7 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\t\tobject_list_insert(object, &wants);\n \n \t\t\tobject = parse_object_or_die(get_tagged_oid(tag), NULL);\n+\t\t\tobject->flags |= (tag->object.flags & UNINTERESTING);\n \t\t}\n \n \t\tif (object->flags & UNINTERESTING)\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex b3e725f031..452be01056 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -15,6 +15,12 @@ test_expect_success 'setup bitmap config' '\n \tgit config pack.writebitmaps true\n '\n \n+# we need to create the tag up front such that it is covered by the repack and\n+# thus by generated bitmaps.\n+test_expect_success 'create tags' '\n+\tgit tag --message=\"tag pointing to HEAD\" perf-tag HEAD\n+'\n+\n test_perf 'repack to disk' '\n \tgit repack -ad\n '\n@@ -43,6 +49,14 @@ test_perf 'rev-list (objects)' '\n \tgit rev-list --all --use-bitmap-index --objects >/dev/null\n '\n \n+test_perf 'rev-list with tag negated via --not --all (objects)' '\n+\tgit rev-list perf-tag --not --all --use-bitmap-index --objects >/dev/null\n+'\n+\n+test_perf 'rev-list with negative tag (objects)' '\n+\tgit rev-list HEAD --not perf-tag --use-bitmap-index --objects >/dev/null\n+'\n+\n test_perf 'rev-list count with blob:none' '\n \tgit rev-list --use-bitmap-index --count --objects --all \\\n \t\t--filter=blob:none >/dev/null\n-- \n2.31.0\n\n"}]}