{"thread":{"id":"55922","subject":"[PATCH] bitmaps: don't recurse into trees already in the bitmap","startedAt":"2021-06-14T07:27:09Z","lastAt":"2021-06-22T19:42:05Z","messageCount":9,"participants":["Jeff King","Derrick Stolee","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"427276","messageId":"YMcExxF7DI6k+sZ+@coredump.intra.peff.net","threadId":"55922","inReplyTo":null,"subject":"[PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-14T07:27:03Z","receivedAt":"2021-06-14T07:27:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"If an object is already mentioned in a reachability bitmap we are\nbuilding, then by definition so are all of the objects it can reach. We\nhave an optimization to stop traversing commits when we see they are\nalready in the bitmap, but we don't do the same for trees.\n\nIt's generally unavoidable to recurse into trees for commits not yet\ncovered by bitmaps (since most commits generally do have unique\ntop-level trees). But they usually have subtrees that are shared with\nother commits (i.e., all of the subtrees the commit _didn't_ touch). And\nsome of those commits (and their trees) may be covered by the bitmap.\n\nUsually this isn't _too_ big a deal, because we'll visit those subtrees\nonly once in total for the whole walk. But if you have a large number of\nunbitmapped commits, and if your tree is big, then you may end up\nopening a lot of sub-trees for no good reason.\n\nWe can use the same optimization we do for commits here: when we are\nabout to open a tree, see if it's in the bitmap (either the one we are\nbuilding, or the \"seen\" bitmap which covers the UNINTERESTING side of\nthe bitmap when doing a set-difference).\n\nThis works especially well because we'll visit all commits before\nhitting any trees. So even in a history like:\n\n  A -- B\n\nif \"A\" has a bitmap on disk but \"B\" doesn't, we'll already have OR-ed in\nthe results from A before looking at B's tree (so we really will only\nlook at trees touched by B).\n\nFor most repositories, the timings produced by p5310 are unspectacular.\nHere's linux.git:\n\n  Test                         HEAD^             HEAD\n  --------------------------------------------------------------------\n  5310.4: simulated clone      6.00(5.90+0.10)   5.98(5.90+0.08) -0.3%\n  5310.5: simulated fetch      2.98(5.45+0.18)   2.85(5.31+0.18) -4.4%\n  5310.7: rev-list (commits)   0.32(0.29+0.03)   0.33(0.30+0.03) +3.1%\n  5310.8: rev-list (objects)   1.48(1.44+0.03)   1.49(1.44+0.05) +0.7%\n\nAny improvement there is within the noise (the +3.1% on test 7 has to be\nnoise, since we are not recursing into trees, and thus the new code\nisn't even run). The results for git.git are likewise uninteresting.\n\nBut here are numbers from some other real-world repositories (that are\nnot public). This one's tree is comparable in size to linux.git, but has\n~16k refs (and so less complete bitmap coverage):\n\n  Test                         HEAD^               HEAD\n  -------------------------------------------------------------------------\n  5310.4: simulated clone      38.34(39.86+0.74)   33.95(35.53+0.76) -11.5%\n  5310.5: simulated fetch      2.29(6.31+0.35)     2.20(5.97+0.41) -3.9%\n  5310.7: rev-list (commits)   0.99(0.86+0.13)     0.96(0.85+0.11) -3.0%\n  5310.8: rev-list (objects)   11.32(11.04+0.27)   6.59(6.37+0.21) -41.8%\n\nAnd here's another with a very large tree (~340k entries), and a fairly\nlarge number of refs (~10k):\n\n  Test                         HEAD^               HEAD\n  -------------------------------------------------------------------------\n  5310.3: simulated clone      53.83(54.71+1.54)   39.77(40.76+1.50) -26.1%\n  5310.4: simulated fetch      19.91(20.11+0.56)   19.79(19.98+0.67) -0.6%\n  5310.6: rev-list (commits)   0.54(0.44+0.11)     0.51(0.43+0.07) -5.6%\n  5310.7: rev-list (objects)   24.32(23.59+0.73)   9.85(9.49+0.36) -59.5%\n\nThis patch provides substantial improvements in these larger cases, and\nhave any drawbacks for smaller ones (the cost of the bitmap check is\nquite small compared to an actual tree traversal).\n\nNote that we have to add a version of revision.c's include_check\ncallback which handles non-commits. We could possibly consolidate this\ninto a single callback for all objects types, as there's only one user\nof the feature which would need converted (pack-bitmap.c:should_include).\nThat would in theory let us avoid duplicating any logic. But when I\ntried it, the code ended up much worse to read, with lots of repeated\n\"if it's a commit do this, otherwise do that\". Having two separate\ncallbacks splits that naturally, and matches the existing split of\nshow_commit/show_object callbacks.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nPatrick, I cc'd you since you mentioned you'd tried using bitmaps to\noptimize a few queries, but they sometimes made things slower. This\nmight help some (but I doubt it will make all problems go away).\n\nOf course, any review is appreciated, as well. :)\n\n list-objects.c |  3 +++\n pack-bitmap.c  | 17 +++++++++++++++++\n revision.h     |  1 +\n 3 files changed, 21 insertions(+)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex 7f404677d5..473a332416 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -164,6 +164,9 @@ static void process_tree(struct traversal_context *ctx,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n+\tif (revs->include_check_obj &&\n+\t    !revs->include_check_obj(&tree->object, revs->include_check_data))\n+\t\treturn;\n \n \tfailed_parse = parse_tree_gently(tree, 1);\n \tif (failed_parse) {\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex d90e1d9d8c..9dfee4a5b7 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -525,6 +525,22 @@ static int should_include(struct commit *commit, void *_data)\n \treturn 1;\n }\n \n+static int should_include_obj(struct object *obj, void *_data)\n+{\n+\tstruct include_data *data = _data;\n+\tint bitmap_pos;\n+\n+\tbitmap_pos = bitmap_position(data->bitmap_git, &obj->oid);\n+\tif (bitmap_pos < 0)\n+\t\treturn 1;\n+\tif ((data->seen && bitmap_get(data->seen, bitmap_pos)) ||\n+\t     bitmap_get(data->base, bitmap_pos)) {\n+\t\tobj->flags |= SEEN;\n+\t\treturn 0;\n+\t}\n+\treturn 1;\n+}\n+\n static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t\tstruct bitmap **base,\n \t\t\t\tstruct commit *commit)\n@@ -620,6 +636,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\tincdata.seen = seen;\n \n \t\trevs->include_check = should_include;\n+\t\trevs->include_check_obj = should_include_obj;\n \t\trevs->include_check_data = &incdata;\n \n \t\tif (prepare_revision_walk(revs))\ndiff --git a/revision.h b/revision.h\nindex 93aa012f51..7bb5fa4e7c 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -262,6 +262,7 @@ struct rev_info {\n \tint min_parents;\n \tint max_parents;\n \tint (*include_check)(struct commit *, void *);\n+\tint (*include_check_obj)(struct object *obj, void *);\n \tvoid *include_check_data;\n \n \t/* diff info for patches and for paths limiting */\n-- \n2.32.0.549.g52475a27a6\n"},{"id":"427330","messageId":"YMdGGL6v8LrbcAJP@coredump.intra.peff.net","threadId":"55922","inReplyTo":"YMcExxF7DI6k+sZ+@coredump.intra.peff.net","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-14T12:05:44Z","receivedAt":"2021-06-14T12:05:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jun 14, 2021 at 03:27:04AM -0400, Jeff King wrote:\n\n> @@ -620,6 +636,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n>  \t\tincdata.seen = seen;\n>  \n>  \t\trevs->include_check = should_include;\n> +\t\trevs->include_check_obj = should_include_obj;\n>  \t\trevs->include_check_data = &incdata;\n>  \n>  \t\tif (prepare_revision_walk(revs))\n\nWhoops. This is missing one crucial thing. I wrote this patch a month or\ntwo ago, but cherry-picked it onto the current master. These days we\nhave 1e951c6473 (pack-bitmap: clean up include_check after use,\n2021-04-28), so we need to do the same cleanup.\n\nt5304 notices, and I even caught it before sending, but I failed to\nstage the change before running \"git commit --amend\". One of these days\nI will figure out this whole \"git\" thing.\n\nThe squashable fix is just:\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 9dfee4a5b7..bfc10148f5 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -650,6 +650,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t\t      &show_data, NULL);\n \n \t\trevs->include_check = NULL;\n+\t\trevs->include_check_obj = NULL;\n \t\trevs->include_check_data = NULL;\n \t}\n \n\nbut the complete corrected patch is below.\n\n-- >8 --\nSubject: [PATCH] bitmaps: don't recurse into trees already in the bitmap\n\nIf an object is already mentioned in a reachability bitmap we are\nbuilding, then by definition so are all of the objects it can reach. We\nhave an optimization to stop traversing commits when we see they are\nalready in the bitmap, but we don't do the same for trees.\n\nIt's generally unavoidable to recurse into trees for commits not yet\ncovered by bitmaps (since most commits generally do have unique\ntop-level trees). But they usually have subtrees that are shared with\nother commits (i.e., all of the subtrees the commit _didn't_ touch). And\nsome of those commits (and their trees) may be covered by the bitmap.\n\nUsually this isn't _too_ big a deal, because we'll visit those subtrees\nonly once in total for the whole walk. But if you have a large number of\nunbitmapped commits, and if your tree is big, then you may end up\nopening a lot of sub-trees for no good reason.\n\nWe can use the same optimization we do for commits here: when we are\nabout to open a tree, see if it's in the bitmap (either the one we are\nbuilding, or the \"seen\" bitmap which covers the UNINTERESTING side of\nthe bitmap when doing a set-difference).\n\nThis works especially well because we'll visit all commits before\nhitting any trees. So even in a history like:\n\n  A -- B\n\nif \"A\" has a bitmap on disk but \"B\" doesn't, we'll already have OR-ed in\nthe results from A before looking at B's tree (so we really will only\nlook at trees touched by B).\n\nFor most repositories, the timings produced by p5310 are unspectacular.\nHere's linux.git:\n\n  Test                         HEAD^             HEAD\n  --------------------------------------------------------------------\n  5310.4: simulated clone      6.00(5.90+0.10)   5.98(5.90+0.08) -0.3%\n  5310.5: simulated fetch      2.98(5.45+0.18)   2.85(5.31+0.18) -4.4%\n  5310.7: rev-list (commits)   0.32(0.29+0.03)   0.33(0.30+0.03) +3.1%\n  5310.8: rev-list (objects)   1.48(1.44+0.03)   1.49(1.44+0.05) +0.7%\n\nAny improvement there is within the noise (the +3.1% on test 7 has to be\nnoise, since we are not recursing into trees, and thus the new code\nisn't even run). The results for git.git are likewise uninteresting.\n\nBut here are numbers from some other real-world repositories (that are\nnot public). This one's tree is comparable in size to linux.git, but has\n~16k refs (and so less complete bitmap coverage):\n\n  Test                         HEAD^               HEAD\n  -------------------------------------------------------------------------\n  5310.4: simulated clone      38.34(39.86+0.74)   33.95(35.53+0.76) -11.5%\n  5310.5: simulated fetch      2.29(6.31+0.35)     2.20(5.97+0.41) -3.9%\n  5310.7: rev-list (commits)   0.99(0.86+0.13)     0.96(0.85+0.11) -3.0%\n  5310.8: rev-list (objects)   11.32(11.04+0.27)   6.59(6.37+0.21) -41.8%\n\nAnd here's another with a very large tree (~340k entries), and a fairly\nlarge number of refs (~10k):\n\n  Test                         HEAD^               HEAD\n  -------------------------------------------------------------------------\n  5310.3: simulated clone      53.83(54.71+1.54)   39.77(40.76+1.50) -26.1%\n  5310.4: simulated fetch      19.91(20.11+0.56)   19.79(19.98+0.67) -0.6%\n  5310.6: rev-list (commits)   0.54(0.44+0.11)     0.51(0.43+0.07) -5.6%\n  5310.7: rev-list (objects)   24.32(23.59+0.73)   9.85(9.49+0.36) -59.5%\n\nThis patch provides substantial improvements in these larger cases, and\nhave any drawbacks for smaller ones (the cost of the bitmap check is\nquite small compared to an actual tree traversal).\n\nNote that we have to add a version of revision.c's include_check\ncallback which handles non-commits. We could possibly consolidate this\ninto a single callback for all objects types, as there's only one user\nof the feature which would need converted (pack-bitmap.c:should_include).\nThat would in theory let us avoid duplicating any logic. But when I\ntried it, the code ended up much worse to read, with lots of repeated\n\"if it's a commit do this, otherwise do that\". Having two separate\ncallbacks splits that naturally, and matches the existing split of\nshow_commit/show_object callbacks.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\n list-objects.c |  3 +++\n pack-bitmap.c  | 18 ++++++++++++++++++\n revision.h     |  1 +\n 3 files changed, 22 insertions(+)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex 7f404677d5..473a332416 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -164,6 +164,9 @@ static void process_tree(struct traversal_context *ctx,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n+\tif (revs->include_check_obj &&\n+\t    !revs->include_check_obj(&tree->object, revs->include_check_data))\n+\t\treturn;\n \n \tfailed_parse = parse_tree_gently(tree, 1);\n \tif (failed_parse) {\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex d90e1d9d8c..bfc10148f5 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -525,6 +525,22 @@ static int should_include(struct commit *commit, void *_data)\n \treturn 1;\n }\n \n+static int should_include_obj(struct object *obj, void *_data)\n+{\n+\tstruct include_data *data = _data;\n+\tint bitmap_pos;\n+\n+\tbitmap_pos = bitmap_position(data->bitmap_git, &obj->oid);\n+\tif (bitmap_pos < 0)\n+\t\treturn 1;\n+\tif ((data->seen && bitmap_get(data->seen, bitmap_pos)) ||\n+\t     bitmap_get(data->base, bitmap_pos)) {\n+\t\tobj->flags |= SEEN;\n+\t\treturn 0;\n+\t}\n+\treturn 1;\n+}\n+\n static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t\tstruct bitmap **base,\n \t\t\t\tstruct commit *commit)\n@@ -620,6 +636,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\tincdata.seen = seen;\n \n \t\trevs->include_check = should_include;\n+\t\trevs->include_check_obj = should_include_obj;\n \t\trevs->include_check_data = &incdata;\n \n \t\tif (prepare_revision_walk(revs))\n@@ -633,6 +650,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t\t      &show_data, NULL);\n \n \t\trevs->include_check = NULL;\n+\t\trevs->include_check_obj = NULL;\n \t\trevs->include_check_data = NULL;\n \t}\n \ndiff --git a/revision.h b/revision.h\nindex 93aa012f51..7bb5fa4e7c 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -262,6 +262,7 @@ struct rev_info {\n \tint min_parents;\n \tint max_parents;\n \tint (*include_check)(struct commit *, void *);\n+\tint (*include_check_obj)(struct object *obj, void *);\n \tvoid *include_check_data;\n \n \t/* diff info for patches and for paths limiting */\n-- \n2.32.0.549.g52475a27a6\n\n"},{"id":"427476","messageId":"471cb9be-bb72-6a37-ede8-f9421d9d3ebe@gmail.com","threadId":"55922","inReplyTo":"YMdGGL6v8LrbcAJP@coredump.intra.peff.net","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-15T14:17:04Z","receivedAt":"2021-06-15T14:24:04Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/14/2021 8:05 AM, Jeff King wrote:\n> On Mon, Jun 14, 2021 at 03:27:04AM -0400, Jeff King wrote:\n...\n> We can use the same optimization we do for commits here: when we are\n> about to open a tree, see if it's in the bitmap (either the one we are\n> building, or the \"seen\" bitmap which covers the UNINTERESTING side of\n> the bitmap when doing a set-difference).\n\nI was surprised that we were not already doing this. As Git can handle\nlarger repos now than it could a few years ago, I expect this\noptimization to be immediately valuable, and critical in years to come.\n\n> But here are numbers from some other real-world repositories (that are\n> not public). This one's tree is comparable in size to linux.git, but has\n> ~16k refs (and so less complete bitmap coverage):\n> \n>   Test                         HEAD^               HEAD\n>   -------------------------------------------------------------------------\n>   5310.4: simulated clone      38.34(39.86+0.74)   33.95(35.53+0.76) -11.5%\n>   5310.5: simulated fetch      2.29(6.31+0.35)     2.20(5.97+0.41) -3.9%\n>   5310.7: rev-list (commits)   0.99(0.86+0.13)     0.96(0.85+0.11) -3.0%\n>   5310.8: rev-list (objects)   11.32(11.04+0.27)   6.59(6.37+0.21) -41.8%\n> \n> And here's another with a very large tree (~340k entries), and a fairly\n> large number of refs (~10k):\n> \n>   Test                         HEAD^               HEAD\n>   -------------------------------------------------------------------------\n>   5310.3: simulated clone      53.83(54.71+1.54)   39.77(40.76+1.50) -26.1%\n>   5310.4: simulated fetch      19.91(20.11+0.56)   19.79(19.98+0.67) -0.6%\n>   5310.6: rev-list (commits)   0.54(0.44+0.11)     0.51(0.43+0.07) -5.6%\n>   5310.7: rev-list (objects)   24.32(23.59+0.73)   9.85(9.49+0.36) -59.5%\n> \n> This patch provides substantial improvements in these larger cases, and\n> have any drawbacks for smaller ones (the cost of the bitmap check is\n> quite small compared to an actual tree traversal).\n\nThese many-refs scenarios make sense as something that is difficult to\nverify using a single fork of an open-source project, but is common in\nmany closed-source projects that do not use forking to reduce the ref\ncount per repo.\n\nI was impressed by how little code was required for this change. LGTM.\n\nThanks,\n-Stolee\n"},{"id":"427607","messageId":"YMnvCI/jksyn2flD@tanuki","threadId":"55922","inReplyTo":"471cb9be-bb72-6a37-ede8-f9421d9d3ebe@gmail.com","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-06-16T12:31:04Z","receivedAt":"2021-06-16T12:29:16Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Jun 15, 2021 at 10:17:04AM -0400, Derrick Stolee wrote:\n> On 6/14/2021 8:05 AM, Jeff King wrote:\n[snip]\n> > But here are numbers from some other real-world repositories (that are\n> > not public). This one's tree is comparable in size to linux.git, but has\n> > ~16k refs (and so less complete bitmap coverage):\n> > \n> >   Test                         HEAD^               HEAD\n> >   -------------------------------------------------------------------------\n> >   5310.4: simulated clone      38.34(39.86+0.74)   33.95(35.53+0.76) -11.5%\n> >   5310.5: simulated fetch      2.29(6.31+0.35)     2.20(5.97+0.41) -3.9%\n> >   5310.7: rev-list (commits)   0.99(0.86+0.13)     0.96(0.85+0.11) -3.0%\n> >   5310.8: rev-list (objects)   11.32(11.04+0.27)   6.59(6.37+0.21) -41.8%\n> > \n> > And here's another with a very large tree (~340k entries), and a fairly\n> > large number of refs (~10k):\n> > \n> >   Test                         HEAD^               HEAD\n> >   -------------------------------------------------------------------------\n> >   5310.3: simulated clone      53.83(54.71+1.54)   39.77(40.76+1.50) -26.1%\n> >   5310.4: simulated fetch      19.91(20.11+0.56)   19.79(19.98+0.67) -0.6%\n> >   5310.6: rev-list (commits)   0.54(0.44+0.11)     0.51(0.43+0.07) -5.6%\n> >   5310.7: rev-list (objects)   24.32(23.59+0.73)   9.85(9.49+0.36) -59.5%\n> > \n> > This patch provides substantial improvements in these larger cases, and\n> > have any drawbacks for smaller ones (the cost of the bitmap check is\n> > quite small compared to an actual tree traversal).\n> \n> These many-refs scenarios make sense as something that is difficult to\n> verify using a single fork of an open-source project, but is common in\n> many closed-source projects that do not use forking to reduce the ref\n> count per repo.\n\nAgreed. What I typically do to emulate this is to use some version of\nfollowing command to create refs for \"$n\" commits.\n\n    git log --all --format=\"tformat:create refs/commit/%h %H\" |\n        shuf | head -n \"$n\" | git update-ref --stdin\n\nIt's obviously not ideal given that resulting refs are distributed at\nrandom. But combined with a sufficiently large repo, it's still helped\nme at times to reproduce adverse performance at times.\n\nAnyway, the patch does look good to me and sounds like it may help with\nsome of the cases where I have observed adverse performance with bitmaps\nenabled in the past. Thanks!\n\nPatrick\n"},{"id":"427819","messageId":"YMyYz6Tavj5l6S8n@coredump.intra.peff.net","threadId":"55922","inReplyTo":"YMnvCI/jksyn2flD@tanuki","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-18T12:59:59Z","receivedAt":"2021-06-18T13:00:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 16, 2021 at 02:31:04PM +0200, Patrick Steinhardt wrote:\n\n> > These many-refs scenarios make sense as something that is difficult to\n> > verify using a single fork of an open-source project, but is common in\n> > many closed-source projects that do not use forking to reduce the ref\n> > count per repo.\n> \n> Agreed. What I typically do to emulate this is to use some version of\n> following command to create refs for \"$n\" commits.\n> \n>     git log --all --format=\"tformat:create refs/commit/%h %H\" |\n>         shuf | head -n \"$n\" | git update-ref --stdin\n> \n> It's obviously not ideal given that resulting refs are distributed at\n> random. But combined with a sufficiently large repo, it's still helped\n> me at times to reproduce adverse performance at times.\n\nYeah, I've done something similar. But I'd caution people into reading\ntoo much into performance tests from something like that. What I've\nfound over the years is that traversal and bitmap performance can be\nsomewhat sensitive to tree shape and bitmap placement (which in turn is\noften influenced by ref placement, if you are using delta islands or the\nrecently added pack.preferBitmapTips).\n\nMore than once I've spent many head-scratching hours trying to determine\nwhy some real-world repo performs better or worse than expected. :)\n\n> Anyway, the patch does look good to me and sounds like it may help with\n> some of the cases where I have observed adverse performance with bitmaps\n> enabled in the past. Thanks!\n\nThanks for taking a look!\n\n-Peff\n"},{"id":"427825","messageId":"YMyhCTaHmm6oNFpB@xps","threadId":"55922","inReplyTo":"YMyYz6Tavj5l6S8n@coredump.intra.peff.net","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-06-18T13:35:05Z","receivedAt":"2021-06-18T13:30:42Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Jun 18, 2021 at 08:59:59AM -0400, Jeff King wrote:\n> On Wed, Jun 16, 2021 at 02:31:04PM +0200, Patrick Steinhardt wrote:\n> \n> > > These many-refs scenarios make sense as something that is difficult to\n> > > verify using a single fork of an open-source project, but is common in\n> > > many closed-source projects that do not use forking to reduce the ref\n> > > count per repo.\n> > \n> > Agreed. What I typically do to emulate this is to use some version of\n> > following command to create refs for \"$n\" commits.\n> > \n> >     git log --all --format=\"tformat:create refs/commit/%h %H\" |\n> >         shuf | head -n \"$n\" | git update-ref --stdin\n> > \n> > It's obviously not ideal given that resulting refs are distributed at\n> > random. But combined with a sufficiently large repo, it's still helped\n> > me at times to reproduce adverse performance at times.\n> \n> Yeah, I've done something similar. But I'd caution people into reading\n> too much into performance tests from something like that. What I've\n> found over the years is that traversal and bitmap performance can be\n> somewhat sensitive to tree shape and bitmap placement (which in turn is\n> often influenced by ref placement, if you are using delta islands or the\n> recently added pack.preferBitmapTips).\n> \n> More than once I've spent many head-scratching hours trying to determine\n> why some real-world repo performs better or worse than expected. :)\n\nI couldn't agree more. I've also had my fair share of weird performance\ncharacteristics in completely unexpected ways. Unfortunately, it has\nmade me become quite cautious about bitmaps given that they've already\ncaused their fair share of perfomance regressions.\n\nBut your work here actually encourages me to give it another try soonish\nand see what kind of repo shapes make them explode this time.\n\nPatrick\n"},{"id":"427830","messageId":"YMypONmXt142dhbb@coredump.intra.peff.net","threadId":"55922","inReplyTo":"YMyhCTaHmm6oNFpB@xps","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-18T14:10:00Z","receivedAt":"2021-06-18T14:10:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 18, 2021 at 03:35:05PM +0200, Patrick Steinhardt wrote:\n\n> > More than once I've spent many head-scratching hours trying to determine\n> > why some real-world repo performs better or worse than expected. :)\n> \n> I couldn't agree more. I've also had my fair share of weird performance\n> characteristics in completely unexpected ways. Unfortunately, it has\n> made me become quite cautious about bitmaps given that they've already\n> caused their fair share of perfomance regressions.\n> \n> But your work here actually encourages me to give it another try soonish\n> and see what kind of repo shapes make them explode this time.\n\nNot really for immediate work, but I just wanted to note while I'm\nthinking about it: the two big things that can actually make bitmaps\n_worse_ than a regular traversal are:\n\n  - loading the bitmaps is inherently linear in the file size. We could\n    do better with an mmap-able index of bitmapped commits in the file.\n    This would be easy to add as an extension to the file. This matters\n    most for really small queries (the absolute time to parse the bitmap\n    file isn't that high, but if the non-bitmap query can be answered in\n    a few milliseconds, it becomes relatively more important).\n\n  - we produce a definite answer of reachability for the bitmaps by\n    filling in a bitmap for the negative (UNINTERESTING) tips, then one\n    for the regular tips, and then taking a set difference. Whereas a\n    normal traversal walks both sides together until it hits a merge\n    base, and then actually looks into the trees in the boundary\n    commits. This normal-traversal technique may look at fewer objects\n    overall for some cases (especially if you have a lot of negative\n    tips, like with \"--not --all\" and not-so-good bitmap coverage). But\n    it does mean we may report an object as in the traversal when it's\n    actually not (if it was added/removed in part of the uninteresting\n    history, and so not present at the boundary).\n\n    We could possibly teach the bitmap traversal to behave more like\n    a normal one. I suspect this would clear up most of the regressions\n    you'd see using bitmaps with rev-list.\n\nThere is one other related case I've run into. If you put a bitmap on\nevery commit, you'd _think_ that would make everything faster, since\nyou'd never traverse at all. But there's an inflection point where you\nspend more time going through each bitmap twiddling bits (which remember\nis O(nr_of_objects * nr_bitmapped_commits) bits across all of them). And\nmost of those bits will already be \"1\", so there's a point where the\nsaved traversal is less than the cost of OR-ing bits.\n\nAnyway, this is all big-picture stuff that I don't expect you to work on\nor even respond to. I'm mostly just writing up some thoughts that I\ndon't think have made it to the list in a coherent form. I'm not sure if\nI'll eventually work on some of them or not (but anybody who is\ninterested can be my guest :) ).\n\n-Peff\n"},{"id":"428193","messageId":"YNG/05+fmA0YPKj7@ncase","threadId":"55922","inReplyTo":"YMyhCTaHmm6oNFpB@xps","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2021-06-22T10:47:57Z","receivedAt":"2021-06-22T10:48:06Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Jun 18, 2021 at 03:35:05PM +0200, Patrick Steinhardt wrote:\n> On Fri, Jun 18, 2021 at 08:59:59AM -0400, Jeff King wrote:\n> > On Wed, Jun 16, 2021 at 02:31:04PM +0200, Patrick Steinhardt wrote:\n> > \n> > > > These many-refs scenarios make sense as something that is difficult to\n> > > > verify using a single fork of an open-source project, but is common in\n> > > > many closed-source projects that do not use forking to reduce the ref\n> > > > count per repo.\n> > > \n> > > Agreed. What I typically do to emulate this is to use some version of\n> > > following command to create refs for \"$n\" commits.\n> > > \n> > >     git log --all --format=\"tformat:create refs/commit/%h %H\" |\n> > >         shuf | head -n \"$n\" | git update-ref --stdin\n> > > \n> > > It's obviously not ideal given that resulting refs are distributed at\n> > > random. But combined with a sufficiently large repo, it's still helped\n> > > me at times to reproduce adverse performance at times.\n> > \n> > Yeah, I've done something similar. But I'd caution people into reading\n> > too much into performance tests from something like that. What I've\n> > found over the years is that traversal and bitmap performance can be\n> > somewhat sensitive to tree shape and bitmap placement (which in turn is\n> > often influenced by ref placement, if you are using delta islands or the\n> > recently added pack.preferBitmapTips).\n> > \n> > More than once I've spent many head-scratching hours trying to determine\n> > why some real-world repo performs better or worse than expected. :)\n> \n> I couldn't agree more. I've also had my fair share of weird performance\n> characteristics in completely unexpected ways. Unfortunately, it has\n> made me become quite cautious about bitmaps given that they've already\n> caused their fair share of perfomance regressions.\n> \n> But your work here actually encourages me to give it another try soonish\n> and see what kind of repo shapes make them explode this time.\n> \n> Patrick\n\nToday I've been experimenting with the connectivity check of\ngit-receive-pack(1) once again to see whether I'm able to get a\nperformance improvement if the git-rev-list(1) command spawned as part\nof the connectivity check uses `--use-bitmap-index`.\n\nTurns out the answer is \"no\": it has exactly the same performance\ncharacteristics when pushing into a bitmapped repository (linux.git)\ncompared to the version not using a bitmap index, except for once case\nwhere it performs 70x worse: force-pushing \"master~10:master\" into a\nbitmapped repo takes 11s instead of 0.15s with bitmaps enabled.\n\nJust leaving this here as a note for anybody (or myself) to pick up at a\nlater point.\n\nPatrick\n"},{"id":"428231","messageId":"YNI8iyzObjxH0/ED@coredump.intra.peff.net","threadId":"55922","inReplyTo":"YNG/05+fmA0YPKj7@ncase","subject":"Re: [PATCH] bitmaps: don't recurse into trees already in the bitmap","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-22T19:39:55Z","receivedAt":"2021-06-22T19:42:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jun 22, 2021 at 12:47:57PM +0200, Patrick Steinhardt wrote:\n\n> Today I've been experimenting with the connectivity check of\n> git-receive-pack(1) once again to see whether I'm able to get a\n> performance improvement if the git-rev-list(1) command spawned as part\n> of the connectivity check uses `--use-bitmap-index`.\n> \n> Turns out the answer is \"no\": it has exactly the same performance\n> characteristics when pushing into a bitmapped repository (linux.git)\n> compared to the version not using a bitmap index, except for once case\n> where it performs 70x worse: force-pushing \"master~10:master\" into a\n> bitmapped repo takes 11s instead of 0.15s with bitmaps enabled.\n> \n> Just leaving this here as a note for anybody (or myself) to pick up at a\n> later point.\n\nThanks. I'd wager that's probably the \"we find the exact bitmap for the\n'haves'\" problem. There are probably a lot of old refs with so-so bitmap\ncoverage, and we traverse all of them down to the nearest bitmap. If we\nfilled in the bitmap by traversing commits in timestamp or generation\norder and ending at the merge-base, we could probably avoid looking at\nthem at all.\n\n-Peff\n"}]}