{"thread":{"id":"59648","subject":"[PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","startedAt":"2023-04-25T00:00:28Z","lastAt":"2023-06-08T16:25:47Z","messageCount":51,"participants":["Taylor Blau","Junio C Hamano","Derrick Stolee","Felipe Contreras"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"475991","messageId":"cover.1682380788.git.me@ttaylorr.com","threadId":"59648","inReplyTo":null,"subject":"[PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T00:00:17Z","receivedAt":"2023-04-25T00:00:28Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Here is a short (but dense) series that I worked on towards the end of\n2021 with Peff.\n\nIts goal is to improve the bitmap traversal we implement in\nprepare_bitmap_walk(). Specifically, it avoids building up a complete\nbitmap of the \"haves\" side, and instead uses a combination of (a)\nUNINTERESTING commits between the tips and boundary, and (b) the\nboundary itself.\n\nThe gory details are laid out in 3/3, but the high-level overview of the\nnew algorithm to compute the set of objects between \"haves\" and \"wants\"\nusing bitmaps is:\n\n 1. Build a (partial) bitmap of the haves side by first OR-ing any\n bitmap(s) that already exist for UNINTERESTING commits between the\n haves and the boundary.\n\n 2. For each commit along the boundary, add it as a fill-in traversal\n tip (where the traversal terminates once an existing bitmap is\n found), and perform fill-in traversal.\n\n 3. Build up a complete bitmap of the wants side as usual, stopping any\n time we intersect the (partial) haves side.\n\nThis improves many cases where using bitmaps was significantly *slower*\nthan regular, non-bitmap traversal. In some instances, using bitmaps is\nstill slower than the non-bitmap case, but it is a substantial\nimprovement over the classic bitmap walk.\n\n $ ours=\"$(git branch --show-current)\"\n argv=\"--count --objects $ours --not --exclude=$ours --branches\"\n hyperfine \\\n -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n -n 'existing bitmap traversal' \"git rev-list --use-bitmap-index $argv\" \\\n -n 'this commit' \"git.compile rev-list --use-bitmap-index $argv\"\n Benchmark 1: no bitmaps\n Time (mean ± σ): 15.1 ms ± 4.1 ms [User: 8.1 ms, System: 6.9 ms]\n Range (min … max): 7.4 ms … 21.8 ms 131 runs\n\n Benchmark 2: existing bitmap traversal\n Time (mean ± σ): 82.6 ms ± 9.2 ms [User: 63.6 ms, System: 19.0 ms]\n Range (min … max): 73.8 ms … 105.4 ms 28 runs\n\n Benchmark 3: this commit\n Time (mean ± σ): 19.8 ms ± 3.1 ms [User: 13.0 ms, System: 6.8 ms]\n Range (min … max): 17.7 ms … 38.6 ms 158 runs\n\n Summary\n 'no bitmaps' ran\n 1.31 ± 0.41 times faster than 'this commit'\n 5.49 ± 1.62 times faster than 'existing bitmap traversal'\n\nIn a large repository on GitHub.com, the timings to compute the objects\nunique to \"master\", as in:\n\n $ git rev-list --count --objects master --not --exclude=master --branches\n\nimprove as follows:\n\n - 1.012 sec (without bitmaps)\n - 29.571 sec (with the existing bitmap walk)\n - 2.279 sec (with these patches)\n\nThe first couple of patches are preparatory, and the third patch is the\nsubstantive one.\n\nPlease have a look and poke any holes you can find in the new approach\n:-). Thanks in advance for your review.\n\nTaylor Blau (3):\n revision: support tracking uninteresting commits\n pack-bitmap.c: extract `fill_in_bitmap()`\n pack-bitmap.c: use commit boundary during bitmap traversal\n\n pack-bitmap.c | 252 ++++++++++++++++++++++++++++++++++++++------------\n revision.c | 10 +-\n revision.h | 5 +\n 3 files changed, 205 insertions(+), 62 deletions(-)\n\n-- \n2.40.0.380.gda896aa358.dirty\n"},{"id":"475992","messageId":"a643678c0ff7d1a910b1d6c33a839166e2a6a7b2.1682380788.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"[PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T00:00:20Z","receivedAt":"2023-04-25T00:00:30Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The boundary-based bitmap walk will want to know which commits were\nmarked UNINTERESTING in the walk used to discover the boundary.\n\nTrack which commits are marked as such during list limitation as well as\nthe topo walk step, though the latter is not used.\n\nSigned-off-by: Taylor Blau \n---\n revision.c | 10 +++++++++-\n revision.h | 5 +++++\n 2 files changed, 14 insertions(+), 1 deletion(-)\n\ndiff --git a/revision.c b/revision.c\nindex 106ca1ce6c..7177244e7a 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1446,6 +1446,9 @@ static int limit_list(struct rev_info *revs)\n \t\tif (process_parents(revs, commit, &original_list, NULL) < 0)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n+\t\t\tif (revs->collect_uninteresting)\n+\t\t\t\tadd_object_array(obj, NULL,\n+\t\t\t\t\t\t &revs->uninteresting_commits);\n \t\t\tmark_parents_uninteresting(revs, commit);\n \t\t\tslop = still_interesting(original_list, date, slop, &interesting_cache);\n \t\t\tif (slop)\n@@ -3072,6 +3075,7 @@ void release_revisions(struct rev_info *revs)\n \tdiff_free(&revs->pruning);\n \treflog_walk_info_release(revs->reflog_info);\n \trelease_revisions_topo_walk_info(revs->topo_walk_info);\n+\tobject_array_clear(&revs->uninteresting_commits);\n }\n \n static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)\n@@ -3522,8 +3526,12 @@ static void explore_walk_step(struct rev_info *revs)\n \tif (process_parents(revs, c, NULL, NULL) < 0)\n \t\treturn;\n \n-\tif (c->object.flags & UNINTERESTING)\n+\tif (c->object.flags & UNINTERESTING) {\n+\t\tif (revs->collect_uninteresting)\n+\t\t\tadd_object_array(&c->object, NULL,\n+\t\t\t\t\t &revs->uninteresting_commits);\n \t\tmark_parents_uninteresting(revs, c);\n+\t}\n \n \tfor (p = c->parents; p; p = p->next)\n \t\ttest_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);\ndiff --git a/revision.h b/revision.h\nindex e8f6de9684..1385b29c76 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -124,6 +124,9 @@ struct rev_info {\n \t/* Parents of shown commits */\n \tstruct object_array boundary_commits;\n \n+\t/* UNINTERESTING commits between the tips and boundary */\n+\tstruct object_array uninteresting_commits;\n+\n \t/* The end-points specified by the end user */\n \tstruct rev_cmdline_info cmdline;\n \n@@ -183,6 +186,7 @@ struct rev_info {\n \t\t\tunpacked:1,\n \t\t\tno_kept_objects:1,\n \t\t\tboundary:2,\n+\t\t\tcollect_uninteresting:1,\n \t\t\tcount:1,\n \t\t\tleft_right:1,\n \t\t\tleft_only:1,\n@@ -404,6 +408,7 @@ struct rev_info {\n \t.expand_tabs_in_log = -1, \\\n \t.commit_format = CMIT_FMT_DEFAULT, \\\n \t.expand_tabs_in_log_default = 8, \\\n+\t.uninteresting_commits = OBJECT_ARRAY_INIT, \\\n }\n \n /**\n-- \n2.40.0.380.gda896aa358.dirty\n\n"},{"id":"475993","messageId":"7624d3b5ba0415588a924aad2b855088e3d2028b.1682380788.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"[PATCH 2/3] pack-bitmap.c: extract `fill_in_bitmap()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T00:00:23Z","receivedAt":"2023-04-25T00:00:33Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"To prepare for the boundary-based bitmap walk to perform a fill-in\ntraversal using the boundary of either side as the tips, extract routine\nused to perform fill-in traversal by `find_objects()` so that it can be\nused in both places.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 66 +++++++++++++++++++++++++++++----------------------\n 1 file changed, 37 insertions(+), 29 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex b2e7d06d60..046240d072 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1040,6 +1040,41 @@ static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n \treturn 1;\n }\n \n+static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct rev_info *revs,\n+\t\t\t\t struct bitmap *base,\n+\t\t\t\t struct bitmap *seen)\n+{\n+\tstruct include_data incdata;\n+\tstruct bitmap_show_data show_data;\n+\n+\tif (base == NULL)\n+\t\tbase = bitmap_new();\n+\n+\tincdata.bitmap_git = bitmap_git;\n+\tincdata.base = base;\n+\tincdata.seen = seen;\n+\n+\trevs->include_check = should_include;\n+\trevs->include_check_obj = should_include_obj;\n+\trevs->include_check_data = &incdata;\n+\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"revision walk setup failed\");\n+\n+\tshow_data.bitmap_git = bitmap_git;\n+\tshow_data.base = base;\n+\n+\ttraverse_commit_list_filtered(revs, show_commit, show_object,\n+\t\t\t\t &show_data, NULL);\n+\n+\trevs->include_check = NULL;\n+\trevs->include_check_obj = NULL;\n+\trevs->include_check_data = NULL;\n+\n+\treturn base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1105,35 +1140,8 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk) {\n-\t\tstruct include_data incdata;\n-\t\tstruct bitmap_show_data show_data;\n-\n-\t\tif (!base)\n-\t\t\tbase = bitmap_new();\n-\n-\t\tincdata.bitmap_git = bitmap_git;\n-\t\tincdata.base = base;\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-\t\t\tdie(_(\"revision walk setup failed\"));\n-\n-\t\tshow_data.bitmap_git = bitmap_git;\n-\t\tshow_data.base = base;\n-\n-\t\ttraverse_commit_list(revs,\n-\t\t\t\t show_commit, show_object,\n-\t\t\t\t &show_data);\n-\n-\t\trevs->include_check = NULL;\n-\t\trevs->include_check_obj = NULL;\n-\t\trevs->include_check_data = NULL;\n-\t}\n+\tif (needs_walk)\n+\t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n \n \treturn base;\n }\n-- \n2.40.0.380.gda896aa358.dirty\n\n"},{"id":"475994","messageId":"91ed8c70f22dd2c47c60d650323579fc42cc7f2d.1682380788.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"[PATCH 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T00:00:26Z","receivedAt":"2023-04-25T00:00:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When reachability bitmap coverage exists in a repository, Git will use a\ndifferent (and hopefully faster) traversal to compute revision walks.\n\nConsider a set of positive and negative tips (which we'll refer to with\ntheir standard bitmap parlance by, \"wants\", and \"haves\"). In order to\nfigure out what objects exist between the tips, the existing traversal\nin prepare_bitmap_walk() looks something like:\n\n 1. Consider if we can even compute the set of objects with bitmaps,\n and fall back to the usual traversal if we cannot. For example,\n pathspec limiting traversals can't be computed using bitmaps (since\n they don't know which objects are at which paths). The same is true\n of certain kinds of non-trivial object filters.\n\n 2. If we can compute the traversal with bitmaps, partition the\n (dereferenced) tips into two object lists, \"haves\", and \"wants\",\n based on whether or not the objects have the UNINTERESTING flag,\n respectively.\n\n 3. Fall back to the ordinary object traversal if either (a) there are\n no haves, (b) none of the haves are in the bitmapped pack or MIDX,\n or (c) there are no wants.\n\n 4. Construct a reachability bitmap for the \"haves\" side by walking\n from the revision tips down to any existing bitmaps, OR-ing in any\n bitmaps as they are found.\n\n 5. Then do the same for the \"wants\" side, stopping at any objects that\n appear in the \"haves\" bitmap.\n\n 6. Filter the results if any object filter (that can be easily\n computed with bitmaps alone) was given, and then return back to the\n caller.\n\nWhen there is good bitmap coverage relative to the traversal tips, this\nwalk is often significantly faster than an ordinary object traversal\nbecause it can visit far fewer objects.\n\nBut in certain cases, it can be significantly *slower* than the usual\nobject traversal. Why? Because we need to compute complete bitmaps on\neither side of the walk. If either one (or both) of the sides require\nwalking many (or all!) objects before they get to an existing bitmap,\nthe extra bitmap machinery is mostly or all overhead.\n\nOne of the benefits, however, is that even if the walk is slower, bitmap\ntraversals are guaranteed to provide an *exact* answer. Unlike the\ntraditional object traversal algorithm, which can over-count the results\nby not opening trees for older commits, the bitmap walk builds an exact\nreachability bitmap for either side, meaning the results are never\nover-counted.\n\nBut producing non-exact results is OK for our traversal here (both in\nthe bitmap case and not), as long as the results are over-counted, not\nunder.\n\nRelaxing the bitmap traversal to allow it to produce over-counted\nresults gives us the opportunity to make some significant improvements.\nInstead of the above, the new algorithm only has to walk from the\n*boundary* down to the nearest bitmap, instead of from each of the\nUNINTERESTING tips.\n\nThe boundary-based approach still has degenerate cases, but we'll show\nin a moment that it is often a significant improvement.\n\nThe new algorithm works as follows:\n\n 1. Build a (partial) bitmap of the haves side by first OR-ing any\n bitmap(s) that already exist for UNINTERESTING commits between the\n haves and the boundary.\n\n 2. For each commit along the boundary, add it as a fill-in traversal\n tip (where the traversal terminates once an existing bitmap is\n found), and perform fill-in traversal.\n\n 3. Build up a complete bitmap of the wants side as usual, stopping any\n time we intersect the (partial) haves side.\n\n 4. Return the results.\n\nAnd is more-or-less equivalent to using the *old* algorithm with this\ninvocation:\n\n $ git rev-list --objects --boundary $WANTS --not $HAVES |\n perl -lne 'print $1 if /^-(.*)/' |\n xargs git rev-list --objects --use-bitmap-index $WANTS --not\n\nThe new result performs significantly better in many cases, particularly\nwhen the distance from the boundary commit(s) to an existing bitmap is\nshorter than the distance from (all of) the have tips to the nearest\nbitmapped commit.\n\nNote that when using the old bitmap traversal algorithm, the results can\nbe *slower* than without bitmaps! Under the new algorithm, the result is\ncomputed faster with bitmaps than without (at the cost of over-counting\nthe true number of objects in a similar fashion as the non-bitmap\ntraversal):\n\n # (Computing objects unique to 'master' among all branches, not\n # using bitmaps).\n $ time git rev-list --count --objects master --not --exclude=master --branches\n 54\n\n real\t0m1.012s\n user\t0m0.796s\n sys\t0m0.214s\n\n # (Computing the same uniqueness query using the old bitmap\n # traversal algorithm.)\n $ time git rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches\n 42\n\n real\t0m29.571s\n user\t0m28.404s\n sys\t0m1.164s\n\n # (Computing the same uniqueness query using the new bitmap\n # traversal algorithm.)\n $ time git.compile rev-list --count --objects --use-bitmap-index master --not --exclude=master --branches\n 54\n\n real\t0m2.279s\n user\t0m2.023s\n sys\t0m0.256s\n\nThe new algorithm is still slower than not using bitmaps at all, but it\nis nearly a 13-fold improvement over the existing traversal.\n\nIn a more realistic setting (using my local copy of git.git), I can\nobserve a similar speed-up:\n\n $ ours=\"$(git branch --show-current)\"\n argv=\"--count --objects $ours --not --exclude=$ours --branches\"\n hyperfine \\\n -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n -n 'existing bitmap traversal' \"git rev-list --use-bitmap-index $argv\" \\\n -n 'this commit' \"git.compile rev-list --use-bitmap-index $argv\"\n Benchmark 1: no bitmaps\n Time (mean ± σ): 15.1 ms ± 4.1 ms [User: 8.1 ms, System: 6.9 ms]\n Range (min … max): 7.4 ms … 21.8 ms 131 runs\n\n Benchmark 2: existing bitmap traversal\n Time (mean ± σ): 82.6 ms ± 9.2 ms [User: 63.6 ms, System: 19.0 ms]\n Range (min … max): 73.8 ms … 105.4 ms 28 runs\n\n Benchmark 3: this commit\n Time (mean ± σ): 19.8 ms ± 3.1 ms [User: 13.0 ms, System: 6.8 ms]\n Range (min … max): 17.7 ms … 38.6 ms 158 runs\n\n Summary\n 'no bitmaps' ran\n 1.31 ± 0.41 times faster than 'this commit'\n 5.49 ± 1.62 times faster than 'existing bitmap traversal'\n\nHere, the new algorithm is also still slower than not using bitmaps, but\nrepresents a 4-fold improvement over the existing traversal in a more\nmodest example.\n\nSince this algorithm was originally written (nearly a year and a half\nago, at the time of writing), the bitmap lookup table shipped, making\nthe new algorithm's result more competitive. A few other future\ndirections for improving bitmap traversal times beyond not using bitmaps\nat all:\n\n - Decrease the cost to decompress and OR together many bitmaps\n together (particularly when enumerating the uninteresting side of\n the walk). Here we could explore more efficient bitmap storage\n techniques, like Roaring+Run and/or use SIMD instructions to speed\n up ORing them together.\n\n - Store pseudo-merge bitmaps, which could allow us to OR together\n fewer \"summary\" bitmaps (which would also help with the above).\n\nHelped-by: Jeff King \nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 194 ++++++++++++++++++++++++++++++++++++++++----------\n 1 file changed, 158 insertions(+), 36 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 046240d072..c47c97f35b 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1048,7 +1048,7 @@ static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n \tstruct include_data incdata;\n \tstruct bitmap_show_data show_data;\n \n-\tif (base == NULL)\n+\tif (!base)\n \t\tbase = bitmap_new();\n \n \tincdata.bitmap_git = bitmap_git;\n@@ -1075,6 +1075,145 @@ static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n \treturn base;\n }\n \n+static int obj_in_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t struct object *obj, struct bitmap *bitmap)\n+{\n+\tint pos;\n+\n+\tif (!bitmap)\n+\t\treturn 0;\n+\tpos = bitmap_position(bitmap_git, &obj->oid);\n+\tif (pos < 0)\n+\t\treturn 0;\n+\treturn bitmap_get(bitmap, pos);\n+}\n+\n+static void show_boundary_commit(struct commit *commit, void *data)\n+{\n+\tstruct object_array *boundary = data;\n+\tif (!(commit->object.flags & BOUNDARY))\n+\t\treturn;\n+\n+\tadd_object_array(&commit->object, \"\", boundary);\n+}\n+\n+static void show_boundary_object(struct object *object,\n+\t\t\t\t const char *name, void *data)\n+{\n+\tBUG(\"should not be called\");\n+}\n+\n+static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n+\t\t\t\t\t struct rev_info *revs,\n+\t\t\t\t\t struct object_list *roots)\n+{\n+\tstruct bitmap *base = NULL;\n+\tstruct object_array boundary = OBJECT_ARRAY_INIT;\n+\tint any_missing = 0;\n+\tunsigned int i;\n+\tint tmp_blobs, tmp_trees, tmp_tags;\n+\n+\trevs->ignore_missing_links = 1;\n+\trevs->collect_uninteresting = 1;\n+\n+\t/*\n+\t * OR in any existing reachability bitmaps among `roots` into `base`.\n+\t */\n+\twhile (roots) {\n+\t\tstruct object *object = roots->item;\n+\t\troots = roots->next;\n+\n+\t\tif (object->type == OBJ_COMMIT &&\n+\t\t !obj_in_bitmap(bitmap_git, object, base) &&\n+\t\t add_commit_to_bitmap(bitmap_git, &base,\n+\t\t\t\t\t (struct commit *)object)) {\n+\t\t\tobject->flags |= SEEN;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tany_missing = 1;\n+\t}\n+\n+\tif (!any_missing)\n+\t\tgoto cleanup;\n+\n+\ttmp_blobs = revs->blob_objects;\n+\ttmp_trees = revs->tree_objects;\n+\ttmp_tags = revs->blob_objects;\n+\trevs->blob_objects = 0;\n+\trevs->tree_objects = 0;\n+\trevs->tag_objects = 0;\n+\n+\t/*\n+\t * We didn't have complete coverage of the roots. First OR in any\n+\t * bitmaps that are UNINTERESTING between the tips and boundary.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"revision walk setup failed\");\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-load-bitmaps\", the_repository);\n+\tfor (i = 0; i < revs->uninteresting_commits.nr; i++) {\n+\t\tstruct object *obj = revs->uninteresting_commits.objects[i].item;\n+\t\tif (obj->type != OBJ_COMMIT)\n+\t\t\tBUG(\"unexpected non-commit %s marked uninteresting\",\n+\t\t\t oid_to_hex(&obj->oid));\n+\n+\t\tif (obj_in_bitmap(bitmap_git, obj, base))\n+\t\t\tcontinue;\n+\n+\t\tadd_commit_to_bitmap(bitmap_git, &base, (struct commit *)obj);\n+\t}\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-load-bitmaps\", the_repository);\n+\n+\t/*\n+\t * Then add the boundary commit(s) as fill-in traversal tips.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\trevs->boundary = 1;\n+\ttraverse_commit_list_filtered(revs,\n+\t\t\t\t show_boundary_commit,\n+\t\t\t\t show_boundary_object,\n+\t\t\t\t &boundary, NULL);\n+\trevs->boundary = 0;\n+\trevs->blob_objects = tmp_blobs;\n+\trevs->tree_objects = tmp_trees;\n+\trevs->tag_objects = tmp_tags;\n+\n+\treset_revision_walk();\n+\tclear_object_flags(UNINTERESTING);\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\tif (boundary.nr) {\n+\t\tstruct object *obj;\n+\t\tint needs_walk = 0;\n+\n+\t\tfor (i = 0; i < boundary.nr; i++) {\n+\t\t\tobj = boundary.objects[i].item;\n+\n+\t\t\tif (obj_in_bitmap(bitmap_git, obj, base)) {\n+\t\t\t\tobj->flags |= SEEN;\n+\t\t\t} else {\n+\t\t\t\tadd_pending_object(revs, obj, \"\");\n+\t\t\t\tneeds_walk = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (needs_walk)\n+\t\t\tbase = fill_in_bitmap(bitmap_git, revs, base, NULL);\n+\t}\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\n+\n+cleanup:\n+\trevs->ignore_missing_links = 0;\n+\trevs->collect_uninteresting = 0;\n+\n+\treturn base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1140,8 +1279,21 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk)\n+\tif (needs_walk) {\n+\t\t/*\n+\t\t * This fill-in traversal may walk over some objects\n+\t\t * again, since we have already traversed in order to\n+\t\t * find the boundary.\n+\t\t *\n+\t\t * But this extra walk should be extremely cheap, since\n+\t\t * all commit objects are loaded into memory, and\n+\t\t * because we skip walking to parents that are\n+\t\t * UNINTERESTING, since it will be marked in the haves\n+\t\t * bitmap already (or it has an on-disk bitmap, since\n+\t\t * OR-ing it in covers all of its ancestors).\n+\t\t */\n \t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n+\t}\n \n \treturn base;\n }\n@@ -1257,25 +1409,6 @@ static void show_objects_for_type(\n \t}\n }\n \n-static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n-\t\t\t struct object_list *roots)\n-{\n-\twhile (roots) {\n-\t\tstruct object *object = roots->item;\n-\t\troots = roots->next;\n-\n-\t\tif (bitmap_is_midx(bitmap_git)) {\n-\t\t\tif (bsearch_midx(&object->oid, bitmap_git->midx, NULL))\n-\t\t\t\treturn 1;\n-\t\t} else {\n-\t\t\tif (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)\n-\t\t\t\treturn 1;\n-\t\t}\n-\t}\n-\n-\treturn 0;\n-}\n-\n static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct object_list *tip_objects,\n \t\t\t\t enum object_type type)\n@@ -1583,14 +1716,6 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\tobject_list_insert(object, &wants);\n \t}\n \n-\t/*\n-\t * if we have a HAVES list, but none of those haves is contained\n-\t * in the packfile that has a bitmap, we don't have anything to\n-\t * optimize here\n-\t */\n-\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n-\t\tgoto cleanup;\n-\n \t/* if we don't want anything, we're done here */\n \tif (!wants)\n \t\tgoto cleanup;\n@@ -1603,18 +1728,15 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \tif (load_bitmap(bitmap_git) < 0)\n \t\tgoto cleanup;\n \n-\tobject_array_clear(&revs->pending);\n-\n \tif (haves) {\n-\t\trevs->ignore_missing_links = 1;\n-\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n-\t\treset_revision_walk();\n-\t\trevs->ignore_missing_links = 0;\n-\n+\t\thaves_bitmap = find_boundary_objects(bitmap_git, revs, haves);\n \t\tif (!haves_bitmap)\n \t\t\tBUG(\"failed to perform bitmap walk\");\n \t}\n \n+\tobject_array_clear(&revs->pending);\n+\treset_revision_walk();\n+\n \twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n \n \tif (!wants_bitmap)\n-- \n2.40.0.380.gda896aa358.dirty\n"},{"id":"476047","messageId":"xmqqy1mfzvpq.fsf@gitster.g","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-25T18:02:25Z","receivedAt":"2023-04-25T18:03:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> This improves many cases where using bitmaps was significantly *slower*\n> than regular, non-bitmap traversal. In some instances, using bitmaps is\n> still slower than the non-bitmap case, but it is a substantial\n> improvement over the classic bitmap walk.\n> ...\n> In a large repository on GitHub.com, the timings to compute the objects\n> unique to \"master\", as in:\n>\n> $ git rev-list --count --objects master --not --exclude=master --branches\n>\n> improve as follows:\n\nCurious---when would it be significantly faster to use bitmaps?\n\"Most of the time\"? \"In not-too-large repository?\"\n\n"},{"id":"476048","messageId":"f25c6234-83c0-fa49-85f5-9005e312b8a3@github.com","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-25T18:06:25Z","receivedAt":"2023-04-25T18:06:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/24/2023 8:00 PM, Taylor Blau wrote:\n> Here is a short (but dense) series that I worked on towards the end of\n> 2021 with Peff.\n> \n> Its goal is to improve the bitmap traversal we implement in\n> prepare_bitmap_walk(). Specifically, it avoids building up a complete\n> bitmap of the \"haves\" side, and instead uses a combination of (a)\n> UNINTERESTING commits between the tips and boundary, and (b) the\n> boundary itself.\n> \n> The gory details are laid out in 3/3, but the high-level overview of the\n> new algorithm to compute the set of objects between \"haves\" and \"wants\"\n> using bitmaps is:\n> \n> 1. Build a (partial) bitmap of the haves side by first OR-ing any\n> bitmap(s) that already exist for UNINTERESTING commits between the\n> haves and the boundary.\n> \n> 2. For each commit along the boundary, add it as a fill-in traversal\n> tip (where the traversal terminates once an existing bitmap is\n> found), and perform fill-in traversal.\n> \n> 3. Build up a complete bitmap of the wants side as usual, stopping any\n> time we intersect the (partial) haves side.\n\nIn other words: this generates something closer to the object set in the\nnon-bitmapped object walk. The only difference is that the new bitmapped\nalgorithm will see objects that were re-introduced across the boundary\n(say, a blob was reverted to its older mode).\n \n> This improves many cases where using bitmaps was significantly *slower*\n> than regular, non-bitmap traversal. In some instances, using bitmaps is\n> still slower than the non-bitmap case, but it is a substantial\n> improvement over the classic bitmap walk.> \n> $ ours=\"$(git branch --show-current)\"\n> argv=\"--count --objects $ours --not --exclude=$ours --branches\"\n> hyperfine \\\n> -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n> -n 'existing bitmap traversal' \"git rev-list --use-bitmap-index $argv\" \\\n> -n 'this commit' \"git.compile rev-list --use-bitmap-index $argv\"\n> Benchmark 1: no bitmaps\n> Time (mean ± σ): 15.1 ms ± 4.1 ms [User: 8.1 ms, System: 6.9 ms]\n> Range (min … max): 7.4 ms … 21.8 ms 131 runs\n> \n> Benchmark 2: existing bitmap traversal\n> Time (mean ± σ): 82.6 ms ± 9.2 ms [User: 63.6 ms, System: 19.0 ms]\n> Range (min … max): 73.8 ms … 105.4 ms 28 runs\n> \n> Benchmark 3: this commit\n> Time (mean ± σ): 19.8 ms ± 3.1 ms [User: 13.0 ms, System: 6.8 ms]\n> Range (min … max): 17.7 ms … 38.6 ms 158 runs\n> \n> Summary\n> 'no bitmaps' ran\n> 1.31 ± 0.41 times faster than 'this commit'\n> 5.49 ± 1.62 times faster than 'existing bitmap traversal'\n> \n> In a large repository on GitHub.com, the timings to compute the objects\n> unique to \"master\", as in:\n> \n> $ git rev-list --count --objects master --not --exclude=master --branches\n> \n> improve as follows:\n> \n> - 1.012 sec (without bitmaps)\n> - 29.571 sec (with the existing bitmap walk)\n> - 2.279 sec (with these patches)\n\nFor my curiosity, and since you already have a test environment set up,\ncould you redo the \"without bitmaps\" case with pack.useSparse true and\nfalse? When the option was created and defaulted to true, we never\nreally explored comparing it to the bitmap case. In fact, I assumed the\nbitmap case was faster in important cases like this (where there is a\nsubstantial difference in object counts), but your data is surprising me\nthat the sparse algorithm is outperforming bitmaps, even with this new\nalgorithm.\n\nThe main question I'd like to ask is: is pack.useSparse contributing\nin an important way to the performance here?\n \nI'll go poking into the patches now.\n\nThanks,\n-Stolee\n"},{"id":"476049","messageId":"0b8884ea-f37b-b7d4-6edb-825ca935a893@github.com","threadId":"59648","inReplyTo":"a643678c0ff7d1a910b1d6c33a839166e2a6a7b2.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-25T18:15:49Z","receivedAt":"2023-04-25T18:15:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/24/2023 8:00 PM, Taylor Blau wrote:\n> The boundary-based bitmap walk will want to know which commits were\n> marked UNINTERESTING in the walk used to discover the boundary.\n> \n> Track which commits are marked as such during list limitation as well as\n> the topo walk step, though the latter is not used.\n\nI was surprised to see this as an addition to revision.c, and\nonly specific to limit_list() (and its iterative copy). I would\nexpect this to work for non-topo-order, too. I suppose we couldn't\ncompletely trust that the first visit to a commit includes the\nUNINTERESTING flag if there is clock skew in the commit history.\n\nBut could we also do this at the caller's end by passing a\ncallback that checks each walked commit if it is UNINTERESTING\nand adds it to a set?\n\nI know that the walking code in builtin/pack-objects.c does\nthis same computation, but it's muddled with other checks and\nthe trees are marked as UNINTERESTING at the same time. It\ndoesn't seem like we can reuse anything directly out of there,\nbut it did give me the idea to try a callback.\n\nThanks,\n-Stolee\n"},{"id":"476050","messageId":"xmqqsfcnzuse.fsf@gitster.g","threadId":"59648","inReplyTo":"a643678c0ff7d1a910b1d6c33a839166e2a6a7b2.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-25T18:22:25Z","receivedAt":"2023-04-25T18:22:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> The boundary-based bitmap walk will want to know which commits were\n> marked UNINTERESTING in the walk used to discover the boundary.\n>\n> Track which commits are marked as such during list limitation as well as\n> the topo walk step, though the latter is not used.\n\nThere are many more places, other than these two that are touched by\nthis patch, where a commit is marked with the UNINTERESTING bit\n(e.g. mark_parents_uninteresting(), process_parents()) and it is\nnot quite clear if the commits smudged with the UNINTERESTING bit in\nthese other places are eventually seen by these two places that\nsomebody else smudged them and get collected.\n\nOr am I wrong to understand that the idea is to collect all\nUNINTERESTING commits?\n\nAlso don't these two places see the same commit more than once, say\nwhen traversing from two branch tips with UNINTERESTING bit set and\nthe traversals meet at the fork point of these two branches? Would\nsuch a commit get added to the array in duplicates?\n\nThanks.\n"},{"id":"476051","messageId":"1a09d246-5750-7d98-08f7-bad6d3dee3c9@github.com","threadId":"59648","inReplyTo":"xmqqy1mfzvpq.fsf@gitster.g","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-25T18:30:01Z","receivedAt":"2023-04-25T18:30:10Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/25/2023 2:02 PM, Junio C Hamano wrote:\n> Taylor Blau writes:\n> \n>> This improves many cases where using bitmaps was significantly *slower*\n>> than regular, non-bitmap traversal. In some instances, using bitmaps is\n>> still slower than the non-bitmap case, but it is a substantial\n>> improvement over the classic bitmap walk.\n>> ...\n>> In a large repository on GitHub.com, the timings to compute the objects\n>> unique to \"master\", as in:\n>>\n>> $ git rev-list --count --objects master --not --exclude=master --branches\n>>\n>> improve as follows:\n> \n> Curious---when would it be significantly faster to use bitmaps?\n> \"Most of the time\"? \"In not-too-large repository?\"\n\nThis is an interesting question that is very difficult to predict\nin advance.\n\nWhen building an independent implementation of reachability bitmaps\nfor Azure Repos, we never managed to make the bitmap method faster\nfor incremental fetches, on average, and so only enabled them during\nfull clones (no haves).\n\nOf course, it's relatively easy to construct something that looks\nlike an incremental fetch but is as expensive as a clone (include\none have being a root commit), but it is very rare in practice.\n\nIt would be interesting if we used the initial commit walk to the\nboundary as a predictor of whether bitmaps would be good, or if\nwe should use the tree-parsing walk instead.\n\nBut perhaps this series gets the bitmap walk \"close enough\" in\nthe typical case that it's better to use bitmaps in the chance that\nwe have accidentally hit a case where we'd normally need to walk a\nlot of trees.\n\nThanks,\n-Stolee\n\n\n"},{"id":"476052","messageId":"xmqqmt2vzubq.fsf@gitster.g","threadId":"59648","inReplyTo":"7624d3b5ba0415588a924aad2b855088e3d2028b.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 2/3] pack-bitmap.c: extract `fill_in_bitmap()`","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-25T18:32:25Z","receivedAt":"2023-04-25T18:32:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> To prepare for the boundary-based bitmap walk to perform a fill-in\n> traversal using the boundary of either side as the tips, extract routine\n> used to perform fill-in traversal by `find_objects()` so that it can be\n> used in both places.\n\nWhat is done is not a literal \"extract\", though. Worth mentioning here?\n\n> Signed-off-by: Taylor Blau \n> ---\n> pack-bitmap.c | 66 +++++++++++++++++++++++++++++----------------------\n> 1 file changed, 37 insertions(+), 29 deletions(-)\n>\n> +\tif (base == NULL)\n> +\t\tbase = bitmap_new();\n\nStyle?\n\n> +\tincdata.bitmap_git = bitmap_git;\n> +\tincdata.base = base;\n> +\tincdata.seen = seen;\n> +\n> +\trevs->include_check = should_include;\n> +\trevs->include_check_obj = should_include_obj;\n> +\trevs->include_check_data = &incdata;\n> +\n> +\tif (prepare_revision_walk(revs))\n> +\t\tdie(\"revision walk setup failed\");\n> +\n> +\tshow_data.bitmap_git = bitmap_git;\n> +\tshow_data.base = base;\n> +\n> +\ttraverse_commit_list_filtered(revs, show_commit, show_object,\n> +\t\t\t\t &show_data, NULL);\n\nThe original uses the variant without \"_filtered\" suffix. In a\nlater update when the second caller is added, the new caller may\nneed to extend it, but shouldn't that wait until that step?\n\nThanks.\n"},{"id":"476053","messageId":"ZEggkPQRCvZ7FcJP@nand.local","threadId":"59648","inReplyTo":"xmqqsfcnzuse.fsf@gitster.g","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T18:48:48Z","receivedAt":"2023-04-25T18:48:55Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 11:22:25AM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> Or am I wrong to understand that the idea is to collect all\n> UNINTERESTING commits?\n\nThe idea is to collect UNINTERESTING commits between the tips and their\ncommit boundary. This field should probably be renamed to indicate that.\n\nThanks,\nTaylor\n"},{"id":"476058","messageId":"ZEghQRZWZIlZcIed@nand.local","threadId":"59648","inReplyTo":"xmqqmt2vzubq.fsf@gitster.g","subject":"Re: [PATCH 2/3] pack-bitmap.c: extract `fill_in_bitmap()`t","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T18:51:45Z","receivedAt":"2023-04-25T18:53:11Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 11:32:25AM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> > To prepare for the boundary-based bitmap walk to perform a fill-in\n> > traversal using the boundary of either side as the tips, extract routine\n> > used to perform fill-in traversal by `find_objects()` so that it can be\n> > used in both places.\n>\n> What is done is not a literal \"extract\", though. Worth mentioning here?\n\nOops. It is supposed to be a literal extraction, but this patch was\noriginally written before 3e0370a8d2 (list-objects: consolidate\ntraverse_commit_list[_filtered], 2022-03-09).\n\n> > ---\n> > pack-bitmap.c | 66 +++++++++++++++++++++++++++++----------------------\n> > 1 file changed, 37 insertions(+), 29 deletions(-)\n> >\n> > +\tif (base == NULL)\n> > +\t\tbase = bitmap_new();\n>\n> Style?\n\n...It was also written before afe8a9070b (tree-wide: apply\nequals-null.cocci, 2022-05-02), which is where this \"if (base == NULL)\"\nthing comes from. I fixed both to be a clean extraction with no\nfunctional changes.\n\nThanks,\nTaylor\n"},{"id":"476059","messageId":"xmqqh6t3ztee.fsf@gitster.g","threadId":"59648","inReplyTo":"91ed8c70f22dd2c47c60d650323579fc42cc7f2d.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-25T18:52:25Z","receivedAt":"2023-04-25T18:54:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> 3. Fall back to the ordinary object traversal if either (a) there are\n> no haves, (b) none of the haves are in the bitmapped pack or MIDX,\n> or (c) there are no wants.\n\nTangents. If there are no haves, wouldn't the answer by definition\neverything that are reachable from all wants? Is there a reason why\na bitmapped walk cannot fulfill such a request? If there are no\nwants, wouldn't the answer by definition an empty set? Again, I am\nnot sure what the ordinary object traversal is expected to do in\nsuch a case.\n\nThese questions are not at all important, as this part is an\nexplation of what happened in the old code.\n\n> Relaxing the bitmap traversal to allow it to produce over-counted\n> results gives us the opportunity to make some significant improvements.\n> Instead of the above, the new algorithm only has to walk from the\n> *boundary* down to the nearest bitmap, instead of from each of the\n> UNINTERESTING tips.\n\nIs it only me, or are all readers equally confused by the use of\nthe term \"boundary\" that hasn't been given any definition?\n\n> And is more-or-less equivalent to using the *old* algorithm with this\n> invocation:\n>\n> $ git rev-list --objects --boundary $WANTS --not $HAVES |\n\nIt is especially confusing because the \"--boundary\" (at least as I\noriginally had invented it), i.e. a commit that is smudged with\nUNINTERESTING bit, whose parent we did not bother to dig further to\npaint with the same UNINTERESTING bit, is not something we start our\ncomputation with; it is something we learn _after_ completing the\nhistory traversing. So I am utterly confused X-<.\n\n\n"},{"id":"476060","messageId":"a143150d-7cf5-c697-0e48-0f7af1c6de8f@github.com","threadId":"59648","inReplyTo":"91ed8c70f22dd2c47c60d650323579fc42cc7f2d.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-25T18:53:46Z","receivedAt":"2023-04-25T18:55:05Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/24/2023 8:00 PM, Taylor Blau wrote:\n> When reachability bitmap coverage exists in a repository, Git will use a\n> different (and hopefully faster) traversal to compute revision walks.\n\nBefore getting into the code...\n\n> Consider a set of positive and negative tips (which we'll refer to with\n> their standard bitmap parlance by, \"wants\", and \"haves\"). In order to\n> figure out what objects exist between the tips, the existing traversal\n> in prepare_bitmap_walk() looks something like:\n\n> 4. Construct a reachability bitmap for the \"haves\" side by walking\n> from the revision tips down to any existing bitmaps, OR-ing in any\n> bitmaps as they are found.\n> \n> 5. Then do the same for the \"wants\" side, stopping at any objects that\n> appear in the \"haves\" bitmap.\n\nOne important thing about this older algorithm is that it will avoid\nincluding trees and blobs that are reachable from the \"haves\" that\nare not reachable from the boundary between \"haves\" and \"wants\". The\nmost obvious case is that someone force-pushed a branch after rewording\nthe commit messages but keeping the trees and blobs identical.\n\nThis case is rare, and usually the objects that would be repeated are\nlow enough in count and size (with deltas) that it's not a big deal, but\nit is worth bringing up. I didn't see a reference to this side of the\ndifference in your message.\n\n> One of the benefits, however, is that even if the walk is slower, bitmap\n> traversals are guaranteed to provide an *exact* answer. Unlike the\n> traditional object traversal algorithm, which can over-count the results\n> by not opening trees for older commits, the bitmap walk builds an exact\n> reachability bitmap for either side, meaning the results are never\n> over-counted.\n\nSo the new algorithm is a new, third state of \"not overcounting things\nreachable beyond the commit-walk boundary\" and \"overcounting things\nreachable from the wants..haves commit region\".\n\n> But producing non-exact results is OK for our traversal here (both in\n> the bitmap case and not), as long as the results are over-counted, not\n> under.\n\nTrue, our response will not create a pack-file that cannot be applied\nlocally, but it might be larger than required.\n\nFor these reasons, I'm surprised that this patch completely replaces\nthe old algorithm for the new one. I would prefer to see a config\noption that enables this new algorithm. It would be safer to deploy\nthat way, too.\n\n> The new result performs significantly better in many cases, particularly\n> when the distance from the boundary commit(s) to an existing bitmap is\n> shorter than the distance from (all of) the have tips to the nearest\n> bitmapped commit.\n\nAside: we may even gain benefits by adjusting the commits selected for\nbitmaps by trying for this data shape. One way to attempt this is to\nnot focus on refs but on history common to \"most refs\" using first-\nparent history as a good heuristic. If a commit appears in a lot of\nfirst-parent histories, then it is more likely to be helpful to these\nkinds of walks.\n \n> Note that when using the old bitmap traversal algorithm, the results can\n> be *slower* than without bitmaps! Under the new algorithm, the result is\n> computed faster with bitmaps than without (at the cost of over-counting\n> the true number of objects in a similar fashion as the non-bitmap\n> traversal):\n>\n> # (Computing objects unique to 'master' among all branches, not\n> # using bitmaps).\n> $ time git rev-list --count --objects master --not --exclude=master --branches\n> 54\n\nI like how you included the output of --count here. It might be interesting\nto demonstrate the different forms of overcounting in a carefully constructed\ntest case, which would help us be sure that we are using the desired\nalgorithm during a test case.\n\n> real\t0m1.012s (no bitmaps)\n> real\t0m29.571s (bitmaps, old)\n> real\t0m2.279s (bitmaps, new)\n\n> The new algorithm is still slower than not using bitmaps at all, but it\n> is nearly a 13-fold improvement over the existing traversal.\n \n> In a more realistic setting (using my local copy of git.git), I can\n> observe a similar speed-up:\n...\n> Here, the new algorithm is also still slower than not using bitmaps, but\n> represents a 4-fold improvement over the existing traversal in a more\n> modest example.\n\nInteresting that the new bitmap algorithm is worse in all presented cases.\n\nHow \"atypical\" do we need to be in order for bitmaps to outperform the\ntree-parsing algorithm? Do we need to try \"--branches --not master~1000\"\nto replicate a stale single-branch clone getting every latest commit?\n\n(I'll leave code review to a separate reply.)\n\nThanks,\n-Stolee\n"},{"id":"476062","messageId":"ZEgikbdP8M2sDMlM@nand.local","threadId":"59648","inReplyTo":"1a09d246-5750-7d98-08f7-bad6d3dee3c9@github.com","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T18:57:21Z","receivedAt":"2023-04-25T18:57:56Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 02:30:01PM -0400, Derrick Stolee wrote:\n> On 4/25/2023 2:02 PM, Junio C Hamano wrote:\n> > Taylor Blau writes:\n> >\n> >> This improves many cases where using bitmaps was significantly *slower*\n> >> than regular, non-bitmap traversal. In some instances, using bitmaps is\n> >> still slower than the non-bitmap case, but it is a substantial\n> >> improvement over the classic bitmap walk.\n> >> ...\n> >> In a large repository on GitHub.com, the timings to compute the objects\n> >> unique to \"master\", as in:\n> >>\n> >> $ git rev-list --count --objects master --not --exclude=master --branches\n> >>\n> >> improve as follows:\n> >\n> > Curious---when would it be significantly faster to use bitmaps?\n> > \"Most of the time\"? \"In not-too-large repository?\"\n>\n> This is an interesting question that is very difficult to predict\n> in advance.\n\nIndeed ;-).\n\n> It would be interesting if we used the initial commit walk to the\n> boundary as a predictor of whether bitmaps would be good, or if\n> we should use the tree-parsing walk instead.\n\nI think that this is tough, too. When making a prediction, it would be\ngood if we could avoid walking down to the nearest bitmap, since by that\npoint, you might as well have used bitmaps (if you found one before\nreaching the root(s) of history).\n\nI think the best heuristic we have available is if we have is something\nlike \"# of UNINTERESTING commits between the tips and boundary\", since\nwe OR those in ahead of time, and then the fill-in traversal will\n(usually, not always) be cheap.\n\nBut I think that heuristic probably isn't too predictive, since it would\noften give you the wrong prediction, say, when there are no\nUNINTERESTING commits between the tips and boundary, but the boundary is\nbitmapped.\n\nAnother approach you could take is to cut off the fill-in traversal at\nsome point, or start with whichever is presumed to be faster and then\ndynamically switch to the other at some point during the walk. But that\nalso depends on repository shape/size, and machine configuration.\n\nSo I think it's extremely difficult to get \"right\", but if others have\nsuggestions, I would certainly be receptive to them :-).\n\n> But perhaps this series gets the bitmap walk \"close enough\" in\n> the typical case that it's better to use bitmaps in the chance that\n> we have accidentally hit a case where we'd normally need to walk a\n> lot of trees.\n\nYeah, that is definitely part of this series's goal. Another framing is,\nfor configurations that are using bitmaps everywhere, this should reduce\nthe number of cases where using bitmaps is *significantly* slower than\nnot.\n\nThanks,\nTaylor\n"},{"id":"476063","messageId":"ZEgjiAtK8O0+dbht@nand.local","threadId":"59648","inReplyTo":"f25c6234-83c0-fa49-85f5-9005e312b8a3@github.com","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-04-25T19:01:28Z","receivedAt":"2023-04-25T19:01:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 02:06:25PM -0400, Derrick Stolee wrote:\n> In other words: this generates something closer to the object set in the\n> non-bitmapped object walk. The only difference is that the new bitmapped\n> algorithm will see objects that were re-introduced across the boundary\n> (say, a blob was reverted to its older mode).\n\nVery well put, thank you.\n\n> For my curiosity, and since you already have a test environment set up,\n> could you redo the \"without bitmaps\" case with pack.useSparse true and\n> false? When the option was created and defaulted to true, we never\n> really explored comparing it to the bitmap case. In fact, I assumed the\n> bitmap case was faster in important cases like this (where there is a\n> substantial difference in object counts), but your data is surprising me\n> that the sparse algorithm is outperforming bitmaps, even with this new\n> algorithm.\n>\n> The main question I'd like to ask is: is pack.useSparse contributing\n> in an important way to the performance here?\n\nI don't know enough about pack.useSparse to say with certainty, but\ntrying again on the same repository (which is reasonably well-packed at\nthe moment), they appear about the same:\n\n $ time git -c pack.useSparse=false rev-list --count --objects master \\\n --not --exclude=master --branches\n 14\n\n real\t0m0.986s\n user\t0m0.599s\n sys\t0m0.387s\n\n $ time git -c pack.useSparse=true rev-list --count --objects master \\\n --not --exclude=master --branches\n 14\n\n real\t0m0.985s\n user\t0m0.600s\n sys\t0m0.385s\n\n> I'll go poking into the patches now.\n\nThanks in advance for your review :-).\n\nThanks,\nTaylor\n"},{"id":"476067","messageId":"5943de3d-3dad-c600-c6d6-3c10c2851071@github.com","threadId":"59648","inReplyTo":"ZEgikbdP8M2sDMlM@nand.local","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-25T19:52:29Z","receivedAt":"2023-04-25T19:52:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/25/2023 2:57 PM, Taylor Blau wrote:\n> On Tue, Apr 25, 2023 at 02:30:01PM -0400, Derrick Stolee wrote:\n>> It would be interesting if we used the initial commit walk to the\n>> boundary as a predictor of whether bitmaps would be good, or if\n>> we should use the tree-parsing walk instead.\n> \n> I think that this is tough, too. When making a prediction, it would be\n> good if we could avoid walking down to the nearest bitmap, since by that\n> point, you might as well have used bitmaps (if you found one before\n> reaching the root(s) of history).\n\nThis isn't quite as cut-and-dry, because walking commits is much\nfaster than walking trees. I agree that we shouldn't walk too far\nto avoid wasting time, but somehow we'd want to think about the\ndistance between the commits we want to cover and the bitmap(s)\nwe found in their history.\n\n>> But perhaps this series gets the bitmap walk \"close enough\" in\n>> the typical case that it's better to use bitmaps in the chance that\n>> we have accidentally hit a case where we'd normally need to walk a\n>> lot of trees.\n> \n> Yeah, that is definitely part of this series's goal. Another framing is,\n> for configurations that are using bitmaps everywhere, this should reduce\n> the number of cases where using bitmaps is *significantly* slower than\n> not.\n\nIt's a good opportunity to re-think if we should be using bitmaps in\nthese contexts at all, or if there is a simpler thing to do by\ndisabling them when 'haves' exist. I don't think that's the right\nthing to do in all cases, but the experiments you've demonstrated here\nseem to point in that direction.\n\nThanks,\n-Stolee\n"},{"id":"476068","messageId":"aa162f0f-022d-7216-51c9-c53884362628@github.com","threadId":"59648","inReplyTo":"ZEgjiAtK8O0+dbht@nand.local","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-25T20:27:21Z","receivedAt":"2023-04-25T20:27:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/25/2023 3:01 PM, Taylor Blau wrote:\n> On Tue, Apr 25, 2023 at 02:06:25PM -0400, Derrick Stolee wrote:\n>> For my curiosity, and since you already have a test environment set up,\n>> could you redo the \"without bitmaps\" case with pack.useSparse true and\n>> false? When the option was created and defaulted to true, we never\n>> really explored comparing it to the bitmap case. In fact, I assumed the\n>> bitmap case was faster in important cases like this (where there is a\n>> substantial difference in object counts), but your data is surprising me\n>> that the sparse algorithm is outperforming bitmaps, even with this new\n>> algorithm.\n>>\n>> The main question I'd like to ask is: is pack.useSparse contributing\n>> in an important way to the performance here?\n> \n> I don't know enough about pack.useSparse to say with certainty, but\n> trying again on the same repository (which is reasonably well-packed at\n> the moment), they appear about the same:\n\nThanks for running that. I apologize, but I didn't sync in my head\nthat you're purposefully using 'git rev-list' to do the walk and the\nconfig only makes a difference for 'git pack-objects'. The suspiciously\nclose timings is indeed too suspicious. Thus, the performance numbers\nyou are considering are not identical to what would happen in 'git\npack-objects' by default.\n\nSo, I created my own example using git.git, which included this input:\n\n\trefs/remotes/origin/master\n\trefs/remotes/origin/maint\n\trefs/remotes/origin/next\n\trefs/remotes/origin/seen\n\t^refs/remotes/origin/master~1000\n\nAnd there is a clear preference for pack.useSparse=false in this\ncase:\n\nBenchmark 1: GIT_TRACE2_PERF=\"/home/stolee/_git/git/git-review/trace-true.txt\" ~/_git/git/git-review/git -c pack.useSparse=true -c pack.useBitmaps=false pack-objects --stdout --revs /dev/null\n Time (mean ± σ): 2.857 s ± 0.031 s [User: 6.850 s, System: 0.378 s]\n Range (min … max): 2.814 s … 2.922 s 10 runs\n \nBenchmark 2: GIT_TRACE2_PERF=\"/home/stolee/_git/git/git-review/trace-false.txt\" ~/_git/git/git-review/git -c pack.useSparse=false -c pack.useBitmaps=false pack-objects --stdout --revs /dev/null\n Time (mean ± σ): 2.682 s ± 0.029 s [User: 6.678 s, System: 0.388 s]\n Range (min … max): 2.653 s … 2.753 s 10 runs\n \nand I used the perf traces to extract that the enumerate objects\nphase took ~550ms for the sparse walk and ~375ms for the non-sparse\nversion.\n\nBut using this same input, I'm able to construct an example where\nyour modified bitmap walk is faster than the non-sparse object walk:\n\nBenchmark 1: GIT_TRACE2_PERF=\"/home/stolee/_git/git/git-review/trace-true.txt\" ~/_git/git/git-review/git -c pack.useSparse=false -c pack.useBitmaps=true pack-objects --stdout --revs /dev/null\n Time (mean ± σ): 2.045 s ± 0.039 s [User: 6.464 s, System: 0.334 s]\n Range (min … max): 1.966 s … 2.089 s 10 runs\n \nBenchmark 2: GIT_TRACE2_PERF=\"/home/stolee/_git/git/git-review/trace-false.txt\" ~/_git/git/git-review/git -c pack.useSparse=false -c pack.useBitmaps=false pack-objects --stdout --revs /dev/null\n Time (mean ± σ): 2.138 s ± 0.034 s [User: 6.070 s, System: 0.333 s]\n Range (min … max): 2.058 s … 2.182 s 10 runs\n\n(Here, the enumerate objects phase takes ~230ms on average.)\n\nI can easily swap this by changing my negative ref to\n\n ^revs/remotes/origin/master\n\nBenchmark 1: GIT_TRACE2_PERF=\"/home/stolee/_git/git/git-review/trace-true.txt\" ~/_git/git/git-review/git -c pack.useSparse=false -c pack.useBitmaps=true pack-objects --stdout --revs /dev/null\n Time (mean ± σ): 521.0 ms ± 28.8 ms [User: 1190.9 ms, System: 103.6 ms]\n Range (min … max): 496.5 ms … 589.8 ms 10 runs\n \nBenchmark 2: GIT_TRACE2_PERF=\"/home/stolee/_git/git/git-review/trace-false.txt\" ~/_git/git/git-review/git -c pack.useSparse=false -c pack.useBitmaps=false pack-objects --stdout --revs /dev/null\n Time (mean ± σ): 498.5 ms ± 13.2 ms [User: 1089.1 ms, System: 123.3 ms]\n Range (min … max): 471.3 ms … 513.6 ms 10 runs\n\nwhich gives us reason to think about \"small fetches\" don't need\nbitmaps, but \"big fetches\" do. But that can be done separately\nfrom this patch.\n\nContext about the sparse walk:\n\nThe sparse walk uses the names of the paths with respect to the root \ntrees as a way to walk only the \"new\" objects without walking the\nentire object set at the boundary. This makes a big difference in\nrepos with many files at HEAD, but the risk is that those path names\nbecome significant overhead if there are enough new changes spread\nacross a large fraction of the tree. For clients pushing the work\nof a single developer, the sparse algorithm outperforms the default\nwalk.\n\nI wrote about this years ago in [1] and almost brought it up earlier\nas a description of the commit boundary (called the frontier in [1]),\nbut the sparse object walk is helpful to visualize.\n\n[1] https://devblogs.microsoft.com/devops/exploring-new-frontiers-for-git-push-performance/\n\nThanks,\n-Stolee\n"},{"id":"476387","messageId":"xmqqo7n33dsx.fsf@gitster.g","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-01T22:08:30Z","receivedAt":"2023-05-01T22:08:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> Here is a short (but dense) series that I worked on towards the end of\n> 2021 with Peff.\n\nThe topic gathered interest on the day it was posted but after 24\nhours or so activities seem to have quieted down. Are we expecting\na polished version? Or did it open a can of worms that is a bit\nlarger than we want to deal with and the topic is left on backburner?\n\nThanks.\n"},{"id":"476467","messageId":"64518133eea7_200ae2948a@chronos.notmuch","threadId":"59648","inReplyTo":"xmqqh6t3ztee.fsf@gitster.g","subject":"Re: [PATCH 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2023-05-02T21:31:31Z","receivedAt":"2023-05-02T21:31:35Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Junio C Hamano wrote:\n> Taylor Blau writes:\n\n> > Relaxing the bitmap traversal to allow it to produce over-counted\n> > results gives us the opportunity to make some significant improvements.\n> > Instead of the above, the new algorithm only has to walk from the\n> > *boundary* down to the nearest bitmap, instead of from each of the\n> > UNINTERESTING tips.\n> \n> Is it only me, or are all readers equally confused by the use of\n> the term \"boundary\" that hasn't been given any definition?\n> \n> > And is more-or-less equivalent to using the *old* algorithm with this\n> > invocation:\n> >\n> > $ git rev-list --objects --boundary $WANTS --not $HAVES |\n> \n> It is especially confusing because the \"--boundary\" (at least as I\n> originally had invented it), i.e. a commit that is smudged with\n> UNINTERESTING bit, whose parent we did not bother to dig further to\n> paint with the same UNINTERESTING bit, is not something we start our\n> computation with; it is something we learn _after_ completing the\n> history traversing. So I am utterly confused X-<.\n\nI don't know if it's the case, but in my mind all the `--not $HAVES` are\nboundaries. Some of these might be overshadowed by another boundary higher up\nin the topology and thus not shown, so in a sense are \"uninteresting\nboundaries\".\n\nPerhaps because you invented `--boundary` you think a \"boundary\" is only an\ninteresting boundary which must be computed, and all the other are not true\nboundaries.\n\nCheers.\n\n-- \nFelipe Contreras\n"},{"id":"476477","messageId":"ZFGiKtLlmQFtZftO@nand.local","threadId":"59648","inReplyTo":"xmqqo7n33dsx.fsf@gitster.g","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-02T23:52:10Z","receivedAt":"2023-05-02T23:52:16Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, May 01, 2023 at 03:08:30PM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> > Here is a short (but dense) series that I worked on towards the end of\n> > 2021 with Peff.\n>\n> The topic gathered interest on the day it was posted but after 24\n> hours or so activities seem to have quieted down. Are we expecting\n> a polished version? Or did it open a can of worms that is a bit\n> larger than we want to deal with and the topic is left on backburner?\n\nWe are expecting a polished version ;-). Though I haven't gotten to it\nas soon as I had hoped. I should have something on the list tomorrow,\nthough.\n\nBut, no, the can of worms is as expected here, and I need to provide\nsome more thorough explanation (e.g., we can collect UNINTERESTING\ncommits in limit_list() only because we only need to walk down to the\nfirst UNINTERESTING commit common to both sides, and no further).\n\nSorry for the delay, more soon.\n\nThanks,\nTaylor\n"},{"id":"476568","messageId":"ZFLVQdjXoEmGImml@nand.local","threadId":"59648","inReplyTo":"xmqqh6t3ztee.fsf@gitster.g","subject":"Re: [PATCH 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-03T21:42:25Z","receivedAt":"2023-05-03T21:42:31Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 11:52:25AM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> > 3. Fall back to the ordinary object traversal if either (a) there are\n> > no haves, (b) none of the haves are in the bitmapped pack or MIDX,\n> > or (c) there are no wants.\n>\n> Tangents. If there are no haves, wouldn't the answer by definition\n> everything that are reachable from all wants? Is there a reason why\n> a bitmapped walk cannot fulfill such a request? If there are no\n> wants, wouldn't the answer by definition an empty set? Again, I am\n> not sure what the ordinary object traversal is expected to do in\n> such a case.\n\nOops, (a) is just wrong. The old code is:\n\n /*\n * if we have a HAVES list, but none of those haves is contained\n * in the packfile that has a bitmap, we don't have anything to\n * optimize here\n */\n if (haves && !in_bitmapped_pack(bitmap_git, haves))\n goto cleanup;\n\nwhich is itself an iffy optimization that I have toyed with the idea of\ngetting rid of over the years, since I am skeptical that it is doing\nmuch even in the classic bitmap traversal.\n\nBut we only do that in_bitmapped_pack() if there are haves to begin\nwith, so (a) from my commit message is incorrect. Sorry about that.\n\n> > And is more-or-less equivalent to using the *old* algorithm with this\n> > invocation:\n> >\n> > $ git rev-list --objects --boundary $WANTS --not $HAVES |\n>\n> It is especially confusing because the \"--boundary\" (at least as I\n> originally had invented it), i.e. a commit that is smudged with\n> UNINTERESTING bit, whose parent we did not bother to dig further to\n> paint with the same UNINTERESTING bit, is not something we start our\n> computation with; it is something we learn _after_ completing the\n> history traversing. So I am utterly confused X-<.\n\nHmm. This is from code that Peff and I wrote together a long time ago.\nMy recollection is that we only care about the UNINTERESTING commits\nbetween the tips and boundary (as you described it), but no further, and\nthat we could discover that set during limit_list() alone.\n\nBut maybe not? I honestly cannot remember. Perhaps Peff does?\n\nThanks,\nTaylor\n"},{"id":"476569","messageId":"ZFLVkrrtMXaOJCxS@nand.local","threadId":"59648","inReplyTo":"5943de3d-3dad-c600-c6d6-3c10c2851071@github.com","subject":"Re: [PATCH 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-03T21:43:46Z","receivedAt":"2023-05-03T21:43:51Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 03:52:29PM -0400, Derrick Stolee wrote:\n> It's a good opportunity to re-think if we should be using bitmaps in\n> these contexts at all, or if there is a simpler thing to do by\n> disabling them when 'haves' exist. I don't think that's the right\n> thing to do in all cases, but the experiments you've demonstrated here\n> seem to point in that direction.\n\nYes, I agree that it's a worthwhile direction to consider in the future.\nI fear that it will be hard to come up with absolute rules here, but\nthat doesn't mean it isn't worth trying :-).\n\nThanks,\nTaylor\n"},{"id":"476571","messageId":"ZFLWwTAIxRnNUKDp@nand.local","threadId":"59648","inReplyTo":"0b8884ea-f37b-b7d4-6edb-825ca935a893@github.com","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-03T21:48:49Z","receivedAt":"2023-05-03T21:48:55Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 02:15:49PM -0400, Derrick Stolee wrote:\n> On 4/24/2023 8:00 PM, Taylor Blau wrote:\n> > The boundary-based bitmap walk will want to know which commits were\n> > marked UNINTERESTING in the walk used to discover the boundary.\n> >\n> > Track which commits are marked as such during list limitation as well as\n> > the topo walk step, though the latter is not used.\n>\n> I was surprised to see this as an addition to revision.c, and\n> only specific to limit_list() (and its iterative copy). I would\n> expect this to work for non-topo-order, too. I suppose we couldn't\n> completely trust that the first visit to a commit includes the\n> UNINTERESTING flag if there is clock skew in the commit history.\n\nYeah, the distinction between limit_list() and the --topo-order code\nmakes things a little funky here. But I think that's OK, since\n`--topo-order` is not likely to be used here, since this is all\nbitmap-based traversal. IOW, I think that it would be reasonable to ban\nthe revision args combination of --use-bitmap-index with --topo-order.\n\n> But could we also do this at the caller's end by passing a\n> callback that checks each walked commit if it is UNINTERESTING\n> and adds it to a set?\n\nI think I remember trying this when I originally wrote this code, and\nended up discarding the idea because it walked over more commits than we\nneeded to consider.\n\nThanks,\nTaylor\n"},{"id":"476575","messageId":"xmqq5y99oz5h.fsf@gitster.g","threadId":"59648","inReplyTo":"ZFLVQdjXoEmGImml@nand.local","subject":"Re: [PATCH 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-03T21:58:34Z","receivedAt":"2023-05-03T21:58:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> Hmm. This is from code that Peff and I wrote together a long time ago.\n> My recollection is that we only care about the UNINTERESTING commits\n> between the tips and boundary (as you described it), but no further, and\n> that we could discover that set during limit_list() alone.\n>\n> But maybe not? I honestly cannot remember. Perhaps Peff does?\n\nYes, that matches my understanding.\n\nBy the time you finish limit_list(), from the \"revision traversal\"\npoint of view, you have done all the hard work already, sifting\ncommits between the ones that are and are not interesting. I am\nsurprised that whatever you learn only after reaching that point is\nstill helpful to optimize some operations.\n\n\n\n"},{"id":"476577","messageId":"ZFLbXTKOK6KTEy7q@nand.local","threadId":"59648","inReplyTo":"0b8884ea-f37b-b7d4-6edb-825ca935a893@github.com","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-03T22:08:29Z","receivedAt":"2023-05-03T22:08:34Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 25, 2023 at 02:15:49PM -0400, Derrick Stolee wrote:\n> I know that the walking code in builtin/pack-objects.c does\n> this same computation, but it's muddled with other checks and\n> the trees are marked as UNINTERESTING at the same time. It\n> doesn't seem like we can reuse anything directly out of there,\n> but it did give me the idea to try a callback.\n\nInteresting idea. When you say callback, do you mean a function that we\ninvoke in place of where we currently call `add_object_array()`? Or do\nyou mean something else? Curious.\n\nThanks,\nTaylor\n"},{"id":"476593","messageId":"3ba50e8c-16c1-8fe2-f6b9-4113bbebe8e0@github.com","threadId":"59648","inReplyTo":"ZFLWwTAIxRnNUKDp@nand.local","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-04T13:46:11Z","receivedAt":"2023-05-04T13:46:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/3/2023 5:48 PM, Taylor Blau wrote:\n> On Tue, Apr 25, 2023 at 02:15:49PM -0400, Derrick Stolee wrote:\n>> On 4/24/2023 8:00 PM, Taylor Blau wrote:\n>>> The boundary-based bitmap walk will want to know which commits were\n>>> marked UNINTERESTING in the walk used to discover the boundary.\n>>>\n>>> Track which commits are marked as such during list limitation as well as\n>>> the topo walk step, though the latter is not used.\n>>\n>> I was surprised to see this as an addition to revision.c, and\n>> only specific to limit_list() (and its iterative copy). I would\n>> expect this to work for non-topo-order, too. I suppose we couldn't\n>> completely trust that the first visit to a commit includes the\n>> UNINTERESTING flag if there is clock skew in the commit history.\n> \n> Yeah, the distinction between limit_list() and the --topo-order code\n> makes things a little funky here. But I think that's OK, since\n> `--topo-order` is not likely to be used here, since this is all\n> bitmap-based traversal. IOW, I think that it would be reasonable to ban\n> the revision args combination of --use-bitmap-index with --topo-order.\n \nI think there is a miscommunication here, since the limit_list()\ncode will only be run if there is a need to \"walk to the end\" before\noutputting results. --topo-order is an example of something that\ntriggers this need, but it is disabled by default.\n\nIt seems that revs->collect_uninteresting would be a condition that\nshould signal to enable revs->limited so this code is actually\nexecuted.\n\nTaking a look at how this works with your current patch, the only\nthing I can think is that since your initial commits include some\nUNINTERESTING commits, that actually triggers revs->limited = 1\nin handle_commit(). It's an indirect use, and without such a\ncommit the boundary would be empty, anyway.\n\nThanks,\n-Stolee\n"},{"id":"476594","messageId":"7a0ea3d7-f67b-8f9d-f9ea-550fcc05108d@github.com","threadId":"59648","inReplyTo":"ZFLbXTKOK6KTEy7q@nand.local","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-04T13:59:32Z","receivedAt":"2023-05-04T13:59:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/3/2023 6:08 PM, Taylor Blau wrote:\n> On Tue, Apr 25, 2023 at 02:15:49PM -0400, Derrick Stolee wrote:\n>> I know that the walking code in builtin/pack-objects.c does\n>> this same computation, but it's muddled with other checks and\n>> the trees are marked as UNINTERESTING at the same time. It\n>> doesn't seem like we can reuse anything directly out of there,\n>> but it did give me the idea to try a callback.\n> \n> Interesting idea. When you say callback, do you mean a function that we\n> invoke in place of where we currently call `add_object_array()`? Or do\n> you mean something else? Curious.\n\nI was talking about passing a callback into the revision walk\ninstead of having the revision code create a list, as you\nreplied to in this response:\n\n>> But could we also do this at the caller's end by passing a\n>> callback that checks each walked commit if it is UNINTERESTING\n>> and adds it to a set?\n> \n> I think I remember trying this when I originally wrote this code, and\n> ended up discarding the idea because it walked over more commits than we\n> needed to consider.\n \nIt's interesting that it walked more commits than you wanted. I\nsuppose it's somehow related to the boundary condition you're\nimplying by enabling the construction of this list.\n\nCould you describe the situation where more commits are walked\nthan you want? I imagine we can't actually stop at the boundary\nbecause we need to know that certain commits are actually reachable\nfrom those boundary commits.\n\nHere's an example (assume horizontal levels are equal generation\nnumber for the sake of the walk's stopping condition).\n\n 1 (UNINTERESTING) 2 (INTERESTING)\n |\\_____ ____/|\n | \\ / |\n 3 4 5 6\n | |\\__ | |\n | | \\| |\n 7 8 [9] 10\n | | | |\n 11 12 13 14\n | | | ___/|\n | | |/ |\n 15 16 [17] 18\n | | ___|____/\n | |/ |\n (19) [20] 21\n\nHere, 9, 17, and 20 are the boundary, as they are UNINITERESTING\nbut reachable from an interesting commit (5, 14, and 18,\nrespectively). This is sufficient to provide a stopping point\nfor this single-directional difference \"2 --not 1\".\n\nIt's important that we didn't stop walking at 9, since its\nUNINTERESTING bit needed to propagate through 13 to get to 17.\n\nNote that 19 is reachable from 1 but not 2, so we would need to\nkeep walking if we were looking for the boundary of the symmetric\ndifference 1...2. But we don't need it here since everything at\nthat level is marked UNINTERESTING so the walk can stop.\n\nIs this example sufficiently complex for you to describe what\ncauses the extra commit walking? In such a case, what does the\nobject array approach add to prevent the extra walking?\n\nThanks,\n-Stolee\n"},{"id":"476630","messageId":"cover.1683307620.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"[PATCH v2 0/2] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-05T17:27:30Z","receivedAt":"2023-05-05T17:27:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Here is a reroll of my series to implement a boundary-based bitmap\ntraversal algorithm that I worked on towards the end of 2021 with Peff.\n\nThe algorithm is unchanged from the last version, but the implementation\nhas been made much more straightforward, thanks to a very helpful\nsuggestion from Stolee.\n\nInstead of hackily trying to write down all of the UNINTERESTING commits\nbetween the tips and boundary within limit_list(), we can just perform a\ncommit-only walk, which will give us the set of commits that we need.\n\nThanks in advance for your review.\n\nTaylor Blau (2):\n pack-bitmap.c: extract `fill_in_bitmap()`\n pack-bitmap.c: use commit boundary during bitmap traversal\n\n pack-bitmap.c | 249 +++++++++++++++++++++++++++++++++++++-------------\n 1 file changed, 188 insertions(+), 61 deletions(-)\n\nRange-diff against v1:\n1: a643678c0f < -: ---------- revision: support tracking uninteresting commits\n2: 7624d3b5ba ! 1: a3a1522439 pack-bitmap.c: extract `fill_in_bitmap()`\n @@ pack-bitmap.c: static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n +\tstruct include_data incdata;\n +\tstruct bitmap_show_data show_data;\n +\n -+\tif (base == NULL)\n ++\tif (!base)\n +\t\tbase = bitmap_new();\n +\n +\tincdata.bitmap_git = bitmap_git;\n @@ pack-bitmap.c: static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n +\trevs->include_check_data = &incdata;\n +\n +\tif (prepare_revision_walk(revs))\n -+\t\tdie(\"revision walk setup failed\");\n ++\t\tdie(_(\"revision walk setup failed\"));\n +\n +\tshow_data.bitmap_git = bitmap_git;\n +\tshow_data.base = base;\n +\n -+\ttraverse_commit_list_filtered(revs, show_commit, show_object,\n -+\t\t\t\t &show_data, NULL);\n ++\ttraverse_commit_list(revs, show_commit, show_object, &show_data);\n +\n +\trevs->include_check = NULL;\n +\trevs->include_check_obj = NULL;\n3: 91ed8c70f2 ! 2: 1993af00cb pack-bitmap.c: use commit boundary during bitmap traversal\n @@ Commit message\n different (and hopefully faster) traversal to compute revision walks.\n \n Consider a set of positive and negative tips (which we'll refer to with\n - their standard bitmap parlance by, \"wants\", and \"haves\"). In order to\n + their standard bitmap parlance by \"wants\", and \"haves\"). In order to\n figure out what objects exist between the tips, the existing traversal\n - in prepare_bitmap_walk() looks something like:\n + in `prepare_bitmap_walk()` does something like:\n \n 1. Consider if we can even compute the set of objects with bitmaps,\n and fall back to the usual traversal if we cannot. For example,\n @@ Commit message\n respectively.\n \n 3. Fall back to the ordinary object traversal if either (a) there are\n - no haves, (b) none of the haves are in the bitmapped pack or MIDX,\n - or (c) there are no wants.\n + more than zero haves, none of which are in the bitmapped pack or\n + MIDX, or (b) there are no wants.\n \n 4. Construct a reachability bitmap for the \"haves\" side by walking\n from the revision tips down to any existing bitmaps, OR-ing in any\n @@ Commit message\n And is more-or-less equivalent to using the *old* algorithm with this\n invocation:\n \n - $ git rev-list --objects --boundary $WANTS --not $HAVES |\n - perl -lne 'print $1 if /^-(.*)/' |\n - xargs git rev-list --objects --use-bitmap-index $WANTS --not\n + $ git rev-list --objects --use-bitmap-index $WANTS --not \\\n + $(git rev-list --objects --boundary $WANTS --not $HAVES |\n + perl -lne 'print $1 if /^-(.*)/')\n \n The new result performs significantly better in many cases, particularly\n when the distance from the boundary commit(s) to an existing bitmap is\n @@ Commit message\n # (Computing objects unique to 'master' among all branches, not\n # using bitmaps).\n $ time git rev-list --count --objects master --not --exclude=master --branches\n - 54\n + 43\n \n - real 0m1.012s\n - user 0m0.796s\n - sys 0m0.214s\n + real 0m0.346s\n + user 0m0.231s\n + sys 0m0.115s\n \n # (Computing the same uniqueness query using the old bitmap\n # traversal algorithm.)\n $ time git rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches\n - 42\n + 41\n \n - real 0m29.571s\n - user 0m28.404s\n - sys 0m1.164s\n + real 0m20.007s\n + user 0m19.045s\n + sys 0m0.960s\n \n # (Computing the same uniqueness query using the new bitmap\n # traversal algorithm.)\n - $ time git.compile rev-list --count --objects --use-bitmap-index master --not --exclude=master --branches\n - 54\n + $ time git.compile rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches\n + 41\n \n - real 0m2.279s\n - user 0m2.023s\n - sys 0m0.256s\n + real 0m1.748s\n + user 0m1.428s\n + sys 0m0.320s\n \n The new algorithm is still slower than not using bitmaps at all, but it\n - is nearly a 13-fold improvement over the existing traversal.\n + is nearly a 11-fold improvement over the existing traversal.\n \n In a more realistic setting (using my local copy of git.git), I can\n - observe a similar speed-up:\n + observe a similar (if more modest) speed-up:\n \n $ ours=\"$(git branch --show-current)\"\n argv=\"--count --objects $ours --not --exclude=$ours --branches\"\n @@ Commit message\n -n 'existing bitmap traversal' \"git rev-list --use-bitmap-index $argv\" \\\n -n 'this commit' \"git.compile rev-list --use-bitmap-index $argv\"\n Benchmark 1: no bitmaps\n - Time (mean ± σ): 15.1 ms ± 4.1 ms [User: 8.1 ms, System: 6.9 ms]\n - Range (min … max): 7.4 ms … 21.8 ms 131 runs\n + Time (mean ± σ): 5.8 ms ± 0.2 ms [User: 3.3 ms, System: 2.4 ms]\n + Range (min … max): 5.4 ms … 7.0 ms 409 runs\n \n Benchmark 2: existing bitmap traversal\n - Time (mean ± σ): 82.6 ms ± 9.2 ms [User: 63.6 ms, System: 19.0 ms]\n - Range (min … max): 73.8 ms … 105.4 ms 28 runs\n + Time (mean ± σ): 65.3 ms ± 0.6 ms [User: 49.3 ms, System: 15.8 ms]\n + Range (min … max): 64.1 ms … 66.9 ms 45 runs\n \n Benchmark 3: this commit\n - Time (mean ± σ): 19.8 ms ± 3.1 ms [User: 13.0 ms, System: 6.8 ms]\n - Range (min … max): 17.7 ms … 38.6 ms 158 runs\n + Time (mean ± σ): 19.8 ms ± 0.3 ms [User: 12.9 ms, System: 6.8 ms]\n + Range (min … max): 19.1 ms … 20.8 ms 150 runs\n \n Summary\n 'no bitmaps' ran\n - 1.31 ± 0.41 times faster than 'this commit'\n - 5.49 ± 1.62 times faster than 'existing bitmap traversal'\n + 3.43 ± 0.14 times faster than 'this commit'\n + 11.34 ± 0.45 times faster than 'existing bitmap traversal'\n \n Here, the new algorithm is also still slower than not using bitmaps, but\n - represents a 4-fold improvement over the existing traversal in a more\n - modest example.\n + represents a more than 3-fold improvement over the existing traversal in\n + a more modest example.\n \n Since this algorithm was originally written (nearly a year and a half\n ago, at the time of writing), the bitmap lookup table shipped, making\n @@ Commit message\n fewer \"summary\" bitmaps (which would also help with the above).\n \n Helped-by: Jeff King \n + Helped-by: Derrick Stolee \n Signed-off-by: Taylor Blau \n \n ## pack-bitmap.c ##\n -@@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n - \tstruct include_data incdata;\n - \tstruct bitmap_show_data show_data;\n - \n --\tif (base == NULL)\n -+\tif (!base)\n - \t\tbase = bitmap_new();\n - \n - \tincdata.bitmap_git = bitmap_git;\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n \treturn base;\n }\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\treturn bitmap_get(bitmap, pos);\n +}\n +\n -+static void show_boundary_commit(struct commit *commit, void *data)\n ++struct bitmap_boundary_cb {\n ++\tstruct bitmap_index *bitmap_git;\n ++\tstruct bitmap *base;\n ++\n ++\tstruct object_array boundary;\n ++};\n ++\n ++static void show_boundary_commit(struct commit *commit, void *_data)\n +{\n -+\tstruct object_array *boundary = data;\n -+\tif (!(commit->object.flags & BOUNDARY))\n -+\t\treturn;\n ++\tstruct bitmap_boundary_cb *data = _data;\n +\n -+\tadd_object_array(&commit->object, \"\", boundary);\n ++\tif (commit->object.flags & BOUNDARY)\n ++\t\tadd_object_array(&commit->object, \"\", &data->boundary);\n ++\n ++\tif (commit->object.flags & UNINTERESTING) {\n ++\t\tif (obj_in_bitmap(data->bitmap_git, &commit->object,\n ++\t\t\t\t data->base))\n ++\t\t\treturn;\n ++\n ++\t\tadd_commit_to_bitmap(data->bitmap_git, &data->base, commit);\n ++\t}\n +}\n +\n +static void show_boundary_object(struct object *object,\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\t\t\t\t\t struct rev_info *revs,\n +\t\t\t\t\t struct object_list *roots)\n +{\n -+\tstruct bitmap *base = NULL;\n -+\tstruct object_array boundary = OBJECT_ARRAY_INIT;\n -+\tint any_missing = 0;\n ++\tstruct bitmap_boundary_cb cb = { .bitmap_git = bitmap_git };\n +\tunsigned int i;\n -+\tint tmp_blobs, tmp_trees, tmp_tags;\n ++\tunsigned int tmp_blobs, tmp_trees, tmp_tags;\n ++\tint any_missing = 0;\n +\n +\trevs->ignore_missing_links = 1;\n -+\trevs->collect_uninteresting = 1;\n +\n +\t/*\n +\t * OR in any existing reachability bitmaps among `roots` into `base`.\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\t\troots = roots->next;\n +\n +\t\tif (object->type == OBJ_COMMIT &&\n -+\t\t !obj_in_bitmap(bitmap_git, object, base) &&\n -+\t\t add_commit_to_bitmap(bitmap_git, &base,\n ++\t\t !obj_in_bitmap(bitmap_git, object, cb.base) &&\n ++\t\t add_commit_to_bitmap(bitmap_git, &cb.base,\n +\t\t\t\t\t (struct commit *)object)) {\n +\t\t\tobject->flags |= SEEN;\n +\t\t\tcontinue;\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\trevs->tag_objects = 0;\n +\n +\t/*\n -+\t * We didn't have complete coverage of the roots. First OR in any\n -+\t * bitmaps that are UNINTERESTING between the tips and boundary.\n ++\t * We didn't have complete coverage of the roots. First setup a\n ++\t * revision walk to (a) OR in any bitmaps that are UNINTERESTING\n ++\t * between the tips and boundary, and (b) record the boundary.\n +\t */\n +\ttrace2_region_enter(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n +\tif (prepare_revision_walk(revs))\n +\t\tdie(\"revision walk setup failed\");\n +\ttrace2_region_leave(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n +\n -+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-load-bitmaps\", the_repository);\n -+\tfor (i = 0; i < revs->uninteresting_commits.nr; i++) {\n -+\t\tstruct object *obj = revs->uninteresting_commits.objects[i].item;\n -+\t\tif (obj->type != OBJ_COMMIT)\n -+\t\t\tBUG(\"unexpected non-commit %s marked uninteresting\",\n -+\t\t\t oid_to_hex(&obj->oid));\n -+\n -+\t\tif (obj_in_bitmap(bitmap_git, obj, base))\n -+\t\t\tcontinue;\n -+\n -+\t\tadd_commit_to_bitmap(bitmap_git, &base, (struct commit *)obj);\n -+\t}\n -+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-load-bitmaps\", the_repository);\n -+\n -+\t/*\n -+\t * Then add the boundary commit(s) as fill-in traversal tips.\n -+\t */\n +\ttrace2_region_enter(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n +\trevs->boundary = 1;\n +\ttraverse_commit_list_filtered(revs,\n +\t\t\t\t show_boundary_commit,\n +\t\t\t\t show_boundary_object,\n -+\t\t\t\t &boundary, NULL);\n ++\t\t\t\t &cb, NULL);\n +\trevs->boundary = 0;\n +\trevs->blob_objects = tmp_blobs;\n +\trevs->tree_objects = tmp_trees;\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\tclear_object_flags(UNINTERESTING);\n +\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n +\n ++\t/*\n ++\t * Then add the boundary commit(s) as fill-in traversal tips.\n ++\t */\n +\ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n -+\tif (boundary.nr) {\n ++\tif (cb.boundary.nr) {\n +\t\tstruct object *obj;\n +\t\tint needs_walk = 0;\n +\n -+\t\tfor (i = 0; i < boundary.nr; i++) {\n -+\t\t\tobj = boundary.objects[i].item;\n ++\t\tfor (i = 0; i < cb.boundary.nr; i++) {\n ++\t\t\tobj = cb.boundary.objects[i].item;\n +\n -+\t\t\tif (obj_in_bitmap(bitmap_git, obj, base)) {\n ++\t\t\tif (obj_in_bitmap(bitmap_git, obj, cb.base)) {\n +\t\t\t\tobj->flags |= SEEN;\n +\t\t\t} else {\n +\t\t\t\tadd_pending_object(revs, obj, \"\");\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\t\t}\n +\n +\t\tif (needs_walk)\n -+\t\t\tbase = fill_in_bitmap(bitmap_git, revs, base, NULL);\n ++\t\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n +\t}\n +\ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n +\n +\n +cleanup:\n +\trevs->ignore_missing_links = 0;\n -+\trevs->collect_uninteresting = 0;\n +\n -+\treturn base;\n ++\treturn cb.base;\n +}\n +\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \tif (!wants)\n \t\tgoto cleanup;\n @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n - \tif (load_bitmap(bitmap_git) < 0)\n + \tif (load_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n \n -\tobject_array_clear(&revs->pending);\n-- \n2.40.1.478.gcab26587e8\n"},{"id":"476631","messageId":"a3a15224390e90655f8ec443158df447f9d37184.1683307620.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1683307620.git.me@ttaylorr.com","subject":"[PATCH v2 1/2] pack-bitmap.c: extract `fill_in_bitmap()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-05T17:27:33Z","receivedAt":"2023-05-05T17:27:40Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"To prepare for the boundary-based bitmap walk to perform a fill-in\ntraversal using the boundary of either side as the tips, extract routine\nused to perform fill-in traversal by `find_objects()` so that it can be\nused in both places.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 65 ++++++++++++++++++++++++++++-----------------------\n 1 file changed, 36 insertions(+), 29 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e0fad723bf..5d2cc6ac96 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1043,6 +1043,40 @@ static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n \treturn 1;\n }\n \n+static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct rev_info *revs,\n+\t\t\t\t struct bitmap *base,\n+\t\t\t\t struct bitmap *seen)\n+{\n+\tstruct include_data incdata;\n+\tstruct bitmap_show_data show_data;\n+\n+\tif (!base)\n+\t\tbase = bitmap_new();\n+\n+\tincdata.bitmap_git = bitmap_git;\n+\tincdata.base = base;\n+\tincdata.seen = seen;\n+\n+\trevs->include_check = should_include;\n+\trevs->include_check_obj = should_include_obj;\n+\trevs->include_check_data = &incdata;\n+\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(_(\"revision walk setup failed\"));\n+\n+\tshow_data.bitmap_git = bitmap_git;\n+\tshow_data.base = base;\n+\n+\ttraverse_commit_list(revs, show_commit, show_object, &show_data);\n+\n+\trevs->include_check = NULL;\n+\trevs->include_check_obj = NULL;\n+\trevs->include_check_data = NULL;\n+\n+\treturn base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1108,35 +1142,8 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk) {\n-\t\tstruct include_data incdata;\n-\t\tstruct bitmap_show_data show_data;\n-\n-\t\tif (!base)\n-\t\t\tbase = bitmap_new();\n-\n-\t\tincdata.bitmap_git = bitmap_git;\n-\t\tincdata.base = base;\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-\t\t\tdie(_(\"revision walk setup failed\"));\n-\n-\t\tshow_data.bitmap_git = bitmap_git;\n-\t\tshow_data.base = base;\n-\n-\t\ttraverse_commit_list(revs,\n-\t\t\t\t show_commit, show_object,\n-\t\t\t\t &show_data);\n-\n-\t\trevs->include_check = NULL;\n-\t\trevs->include_check_obj = NULL;\n-\t\trevs->include_check_data = NULL;\n-\t}\n+\tif (needs_walk)\n+\t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n \n \treturn base;\n }\n-- \n2.40.1.478.gcab26587e8\n\n"},{"id":"476632","messageId":"1993af00cba3af83755da557816c1c7a8b52c844.1683307620.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1683307620.git.me@ttaylorr.com","subject":"[PATCH v2 2/2] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-05T17:27:36Z","receivedAt":"2023-05-05T17:27:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When reachability bitmap coverage exists in a repository, Git will use a\ndifferent (and hopefully faster) traversal to compute revision walks.\n\nConsider a set of positive and negative tips (which we'll refer to with\ntheir standard bitmap parlance by \"wants\", and \"haves\"). In order to\nfigure out what objects exist between the tips, the existing traversal\nin `prepare_bitmap_walk()` does something like:\n\n 1. Consider if we can even compute the set of objects with bitmaps,\n and fall back to the usual traversal if we cannot. For example,\n pathspec limiting traversals can't be computed using bitmaps (since\n they don't know which objects are at which paths). The same is true\n of certain kinds of non-trivial object filters.\n\n 2. If we can compute the traversal with bitmaps, partition the\n (dereferenced) tips into two object lists, \"haves\", and \"wants\",\n based on whether or not the objects have the UNINTERESTING flag,\n respectively.\n\n 3. Fall back to the ordinary object traversal if either (a) there are\n more than zero haves, none of which are in the bitmapped pack or\n MIDX, or (b) there are no wants.\n\n 4. Construct a reachability bitmap for the \"haves\" side by walking\n from the revision tips down to any existing bitmaps, OR-ing in any\n bitmaps as they are found.\n\n 5. Then do the same for the \"wants\" side, stopping at any objects that\n appear in the \"haves\" bitmap.\n\n 6. Filter the results if any object filter (that can be easily\n computed with bitmaps alone) was given, and then return back to the\n caller.\n\nWhen there is good bitmap coverage relative to the traversal tips, this\nwalk is often significantly faster than an ordinary object traversal\nbecause it can visit far fewer objects.\n\nBut in certain cases, it can be significantly *slower* than the usual\nobject traversal. Why? Because we need to compute complete bitmaps on\neither side of the walk. If either one (or both) of the sides require\nwalking many (or all!) objects before they get to an existing bitmap,\nthe extra bitmap machinery is mostly or all overhead.\n\nOne of the benefits, however, is that even if the walk is slower, bitmap\ntraversals are guaranteed to provide an *exact* answer. Unlike the\ntraditional object traversal algorithm, which can over-count the results\nby not opening trees for older commits, the bitmap walk builds an exact\nreachability bitmap for either side, meaning the results are never\nover-counted.\n\nBut producing non-exact results is OK for our traversal here (both in\nthe bitmap case and not), as long as the results are over-counted, not\nunder.\n\nRelaxing the bitmap traversal to allow it to produce over-counted\nresults gives us the opportunity to make some significant improvements.\nInstead of the above, the new algorithm only has to walk from the\n*boundary* down to the nearest bitmap, instead of from each of the\nUNINTERESTING tips.\n\nThe boundary-based approach still has degenerate cases, but we'll show\nin a moment that it is often a significant improvement.\n\nThe new algorithm works as follows:\n\n 1. Build a (partial) bitmap of the haves side by first OR-ing any\n bitmap(s) that already exist for UNINTERESTING commits between the\n haves and the boundary.\n\n 2. For each commit along the boundary, add it as a fill-in traversal\n tip (where the traversal terminates once an existing bitmap is\n found), and perform fill-in traversal.\n\n 3. Build up a complete bitmap of the wants side as usual, stopping any\n time we intersect the (partial) haves side.\n\n 4. Return the results.\n\nAnd is more-or-less equivalent to using the *old* algorithm with this\ninvocation:\n\n $ git rev-list --objects --use-bitmap-index $WANTS --not \\\n $(git rev-list --objects --boundary $WANTS --not $HAVES |\n perl -lne 'print $1 if /^-(.*)/')\n\nThe new result performs significantly better in many cases, particularly\nwhen the distance from the boundary commit(s) to an existing bitmap is\nshorter than the distance from (all of) the have tips to the nearest\nbitmapped commit.\n\nNote that when using the old bitmap traversal algorithm, the results can\nbe *slower* than without bitmaps! Under the new algorithm, the result is\ncomputed faster with bitmaps than without (at the cost of over-counting\nthe true number of objects in a similar fashion as the non-bitmap\ntraversal):\n\n # (Computing objects unique to 'master' among all branches, not\n # using bitmaps).\n $ time git rev-list --count --objects master --not --exclude=master --branches\n 43\n\n real\t0m0.346s\n user\t0m0.231s\n sys\t0m0.115s\n\n # (Computing the same uniqueness query using the old bitmap\n # traversal algorithm.)\n $ time git rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches\n 41\n\n real\t0m20.007s\n user\t0m19.045s\n sys\t0m0.960s\n\n # (Computing the same uniqueness query using the new bitmap\n # traversal algorithm.)\n $ time git.compile rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches\n 41\n\n real\t0m1.748s\n user\t0m1.428s\n sys\t0m0.320s\n\nThe new algorithm is still slower than not using bitmaps at all, but it\nis nearly a 11-fold improvement over the existing traversal.\n\nIn a more realistic setting (using my local copy of git.git), I can\nobserve a similar (if more modest) speed-up:\n\n $ ours=\"$(git branch --show-current)\"\n argv=\"--count --objects $ours --not --exclude=$ours --branches\"\n hyperfine \\\n -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n -n 'existing bitmap traversal' \"git rev-list --use-bitmap-index $argv\" \\\n -n 'this commit' \"git.compile rev-list --use-bitmap-index $argv\"\n Benchmark 1: no bitmaps\n Time (mean ± σ): 5.8 ms ± 0.2 ms [User: 3.3 ms, System: 2.4 ms]\n Range (min … max): 5.4 ms … 7.0 ms 409 runs\n\n Benchmark 2: existing bitmap traversal\n Time (mean ± σ): 65.3 ms ± 0.6 ms [User: 49.3 ms, System: 15.8 ms]\n Range (min … max): 64.1 ms … 66.9 ms 45 runs\n\n Benchmark 3: this commit\n Time (mean ± σ): 19.8 ms ± 0.3 ms [User: 12.9 ms, System: 6.8 ms]\n Range (min … max): 19.1 ms … 20.8 ms 150 runs\n\n Summary\n 'no bitmaps' ran\n 3.43 ± 0.14 times faster than 'this commit'\n 11.34 ± 0.45 times faster than 'existing bitmap traversal'\n\nHere, the new algorithm is also still slower than not using bitmaps, but\nrepresents a more than 3-fold improvement over the existing traversal in\na more modest example.\n\nSince this algorithm was originally written (nearly a year and a half\nago, at the time of writing), the bitmap lookup table shipped, making\nthe new algorithm's result more competitive. A few other future\ndirections for improving bitmap traversal times beyond not using bitmaps\nat all:\n\n - Decrease the cost to decompress and OR together many bitmaps\n together (particularly when enumerating the uninteresting side of\n the walk). Here we could explore more efficient bitmap storage\n techniques, like Roaring+Run and/or use SIMD instructions to speed\n up ORing them together.\n\n - Store pseudo-merge bitmaps, which could allow us to OR together\n fewer \"summary\" bitmaps (which would also help with the above).\n\nHelped-by: Jeff King \nHelped-by: Derrick Stolee \nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 190 ++++++++++++++++++++++++++++++++++++++++----------\n 1 file changed, 155 insertions(+), 35 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 5d2cc6ac96..634fc10156 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1077,6 +1077,143 @@ static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n \treturn base;\n }\n \n+static int obj_in_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t struct object *obj, struct bitmap *bitmap)\n+{\n+\tint pos;\n+\n+\tif (!bitmap)\n+\t\treturn 0;\n+\tpos = bitmap_position(bitmap_git, &obj->oid);\n+\tif (pos < 0)\n+\t\treturn 0;\n+\treturn bitmap_get(bitmap, pos);\n+}\n+\n+struct bitmap_boundary_cb {\n+\tstruct bitmap_index *bitmap_git;\n+\tstruct bitmap *base;\n+\n+\tstruct object_array boundary;\n+};\n+\n+static void show_boundary_commit(struct commit *commit, void *_data)\n+{\n+\tstruct bitmap_boundary_cb *data = _data;\n+\n+\tif (commit->object.flags & BOUNDARY)\n+\t\tadd_object_array(&commit->object, \"\", &data->boundary);\n+\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\tif (obj_in_bitmap(data->bitmap_git, &commit->object,\n+\t\t\t\t data->base))\n+\t\t\treturn;\n+\n+\t\tadd_commit_to_bitmap(data->bitmap_git, &data->base, commit);\n+\t}\n+}\n+\n+static void show_boundary_object(struct object *object,\n+\t\t\t\t const char *name, void *data)\n+{\n+\tBUG(\"should not be called\");\n+}\n+\n+static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n+\t\t\t\t\t struct rev_info *revs,\n+\t\t\t\t\t struct object_list *roots)\n+{\n+\tstruct bitmap_boundary_cb cb = { .bitmap_git = bitmap_git };\n+\tunsigned int i;\n+\tunsigned int tmp_blobs, tmp_trees, tmp_tags;\n+\tint any_missing = 0;\n+\n+\trevs->ignore_missing_links = 1;\n+\n+\t/*\n+\t * OR in any existing reachability bitmaps among `roots` into `base`.\n+\t */\n+\twhile (roots) {\n+\t\tstruct object *object = roots->item;\n+\t\troots = roots->next;\n+\n+\t\tif (object->type == OBJ_COMMIT &&\n+\t\t !obj_in_bitmap(bitmap_git, object, cb.base) &&\n+\t\t add_commit_to_bitmap(bitmap_git, &cb.base,\n+\t\t\t\t\t (struct commit *)object)) {\n+\t\t\tobject->flags |= SEEN;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tany_missing = 1;\n+\t}\n+\n+\tif (!any_missing)\n+\t\tgoto cleanup;\n+\n+\ttmp_blobs = revs->blob_objects;\n+\ttmp_trees = revs->tree_objects;\n+\ttmp_tags = revs->blob_objects;\n+\trevs->blob_objects = 0;\n+\trevs->tree_objects = 0;\n+\trevs->tag_objects = 0;\n+\n+\t/*\n+\t * We didn't have complete coverage of the roots. First setup a\n+\t * revision walk to (a) OR in any bitmaps that are UNINTERESTING\n+\t * between the tips and boundary, and (b) record the boundary.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"revision walk setup failed\");\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\trevs->boundary = 1;\n+\ttraverse_commit_list_filtered(revs,\n+\t\t\t\t show_boundary_commit,\n+\t\t\t\t show_boundary_object,\n+\t\t\t\t &cb, NULL);\n+\trevs->boundary = 0;\n+\trevs->blob_objects = tmp_blobs;\n+\trevs->tree_objects = tmp_trees;\n+\trevs->tag_objects = tmp_tags;\n+\n+\treset_revision_walk();\n+\tclear_object_flags(UNINTERESTING);\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\n+\t/*\n+\t * Then add the boundary commit(s) as fill-in traversal tips.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\tif (cb.boundary.nr) {\n+\t\tstruct object *obj;\n+\t\tint needs_walk = 0;\n+\n+\t\tfor (i = 0; i < cb.boundary.nr; i++) {\n+\t\t\tobj = cb.boundary.objects[i].item;\n+\n+\t\t\tif (obj_in_bitmap(bitmap_git, obj, cb.base)) {\n+\t\t\t\tobj->flags |= SEEN;\n+\t\t\t} else {\n+\t\t\t\tadd_pending_object(revs, obj, \"\");\n+\t\t\t\tneeds_walk = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (needs_walk)\n+\t\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n+\t}\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\n+\n+cleanup:\n+\trevs->ignore_missing_links = 0;\n+\n+\treturn cb.base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1142,8 +1279,21 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk)\n+\tif (needs_walk) {\n+\t\t/*\n+\t\t * This fill-in traversal may walk over some objects\n+\t\t * again, since we have already traversed in order to\n+\t\t * find the boundary.\n+\t\t *\n+\t\t * But this extra walk should be extremely cheap, since\n+\t\t * all commit objects are loaded into memory, and\n+\t\t * because we skip walking to parents that are\n+\t\t * UNINTERESTING, since it will be marked in the haves\n+\t\t * bitmap already (or it has an on-disk bitmap, since\n+\t\t * OR-ing it in covers all of its ancestors).\n+\t\t */\n \t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n+\t}\n \n \treturn base;\n }\n@@ -1259,25 +1409,6 @@ static void show_objects_for_type(\n \t}\n }\n \n-static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n-\t\t\t struct object_list *roots)\n-{\n-\twhile (roots) {\n-\t\tstruct object *object = roots->item;\n-\t\troots = roots->next;\n-\n-\t\tif (bitmap_is_midx(bitmap_git)) {\n-\t\t\tif (bsearch_midx(&object->oid, bitmap_git->midx, NULL))\n-\t\t\t\treturn 1;\n-\t\t} else {\n-\t\t\tif (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)\n-\t\t\t\treturn 1;\n-\t\t}\n-\t}\n-\n-\treturn 0;\n-}\n-\n static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct object_list *tip_objects,\n \t\t\t\t enum object_type type)\n@@ -1585,14 +1716,6 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\tobject_list_insert(object, &wants);\n \t}\n \n-\t/*\n-\t * if we have a HAVES list, but none of those haves is contained\n-\t * in the packfile that has a bitmap, we don't have anything to\n-\t * optimize here\n-\t */\n-\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n-\t\tgoto cleanup;\n-\n \t/* if we don't want anything, we're done here */\n \tif (!wants)\n \t\tgoto cleanup;\n@@ -1605,18 +1728,15 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \tif (load_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n \n-\tobject_array_clear(&revs->pending);\n-\n \tif (haves) {\n-\t\trevs->ignore_missing_links = 1;\n-\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n-\t\treset_revision_walk();\n-\t\trevs->ignore_missing_links = 0;\n-\n+\t\thaves_bitmap = find_boundary_objects(bitmap_git, revs, haves);\n \t\tif (!haves_bitmap)\n \t\t\tBUG(\"failed to perform bitmap walk\");\n \t}\n \n+\tobject_array_clear(&revs->pending);\n+\treset_revision_walk();\n+\n \twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n \n \tif (!wants_bitmap)\n-- \n2.40.1.478.gcab26587e8\n"},{"id":"476634","messageId":"ZFU9Ra4br6NTi4Cg@nand.local","threadId":"59648","inReplyTo":"7a0ea3d7-f67b-8f9d-f9ea-550fcc05108d@github.com","subject":"Re: [PATCH 1/3] revision: support tracking uninteresting commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-05T17:30:45Z","receivedAt":"2023-05-05T17:30:51Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, May 04, 2023 at 09:59:32AM -0400, Derrick Stolee wrote:\n> It's interesting that it walked more commits than you wanted. I\n> suppose it's somehow related to the boundary condition you're\n> implying by enabling the construction of this list.\n>\n> Could you describe the situation where more commits are walked\n> than you want? I imagine we can't actually stop at the boundary\n> because we need to know that certain commits are actually reachable\n> from those boundary commits.\n\nI honestly cannot remember, and was unable to reproduce it when I\nreworked the substantive portion of this series last night.\n\nFor posterity, Stolee and I had an off-list discussion yesterday where\nhe walked me through his suggestion to implement the boundary search via\na straightforward revision walk, instead of grafting onto cherry-picked\ncomponents of the revision internals.\n\nIt works great, and I have been unable to trick it into \"walking too\nmuch\".\n\nThanks,\nTaylor\n"},{"id":"476635","messageId":"xmqq1qjuel94.fsf@gitster.g","threadId":"59648","inReplyTo":"cover.1683307620.git.me@ttaylorr.com","subject":"Re: [PATCH v2 0/2] pack-bitmap: boundary-based bitmap traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-05T17:33:27Z","receivedAt":"2023-05-05T17:33:35Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> Instead of hackily trying to write down all of the UNINTERESTING commits\n> between the tips and boundary within limit_list(), we can just perform a\n> commit-only walk, which will give us the set of commits that we need.\n\nThat does make a lot of sense.\n\n"},{"id":"476638","messageId":"6c8d9142-9013-f3f0-0619-b3780b86b6ab@github.com","threadId":"59648","inReplyTo":"cover.1683307620.git.me@ttaylorr.com","subject":"Re: [PATCH v2 0/2] pack-bitmap: boundary-based bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-05T17:59:31Z","receivedAt":"2023-05-05T17:59:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/5/2023 1:27 PM, Taylor Blau wrote:\n> Here is a reroll of my series to implement a boundary-based bitmap\n> traversal algorithm that I worked on towards the end of 2021 with Peff.\n> \n> The algorithm is unchanged from the last version, but the implementation\n> has been made much more straightforward, thanks to a very helpful\n> suggestion from Stolee.\n> \n> Instead of hackily trying to write down all of the UNINTERESTING commits\n> between the tips and boundary within limit_list(), we can just perform a\n> commit-only walk, which will give us the set of commits that we need.\n\nSomething that didn't seem to get attention in this version was buried\ndeep in the commentary of my high-level review [1]:\n\n> For these reasons, I'm surprised that this patch completely replaces\n> the old algorithm for the new one. I would prefer to see a config\n> option that enables this new algorithm. It would be safer to deploy\n> that way, too.\n\nI still think it would be nice to keep the two algorithms for at least\na little while instead of completely removing the old one. Let's gather\nsome more evidence and get more reps in with the new algorithm before\nmaking it the new default. I could imagine a scenario where someone\nreally wants to spend the extra time to make sure none of the objects\nreachable from the UNINTERESTING commits are included in the output of\nthis diff.\n\n[1] https://lore.kernel.org/git/a143150d-7cf5-c697-0e48-0f7af1c6de8f@github.com/\n\nThanks,\n-Stolee\n"},{"id":"476639","messageId":"e6e2401a-519a-4859-d20b-6b947e94e1ec@github.com","threadId":"59648","inReplyTo":"1993af00cba3af83755da557816c1c7a8b52c844.1683307620.git.me@ttaylorr.com","subject":"Re: [PATCH v2 2/2] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-05T18:13:45Z","receivedAt":"2023-05-05T18:13:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/5/2023 1:27 PM, Taylor Blau wrote:\n\n> +static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n> +\t\t\t\t\t struct rev_info *revs,\n> +\t\t\t\t\t struct object_list *roots)\n> +{\n> +\tstruct bitmap_boundary_cb cb = { .bitmap_git = bitmap_git };\n> +\tunsigned int i;\n> +\tunsigned int tmp_blobs, tmp_trees, tmp_tags;\n> +\tint any_missing = 0;\n> +\n> +\trevs->ignore_missing_links = 1;\n> +\n> +\t/*\n> +\t * OR in any existing reachability bitmaps among `roots` into `base`.\n> +\t */\n> +\twhile (roots) {\n> +\t\tstruct object *object = roots->item;\n> +\t\troots = roots->next;\n> +\n> +\t\tif (object->type == OBJ_COMMIT &&\n> +\t\t !obj_in_bitmap(bitmap_git, object, cb.base) &&\n> +\t\t add_commit_to_bitmap(bitmap_git, &cb.base,\n> +\t\t\t\t\t (struct commit *)object)) {\n> +\t\t\tobject->flags |= SEEN;\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tany_missing = 1;\n> +\t}\n> +\n> +\tif (!any_missing)\n> +\t\tgoto cleanup;\n\nHere, we check if the list of roots are completely covered by existing\nbitmaps. This prevents doing the commit-only walk as well as the boundary\nchecks.\n\nThere's another confusing bit here: if we have a bitmap for the commit,\nthen we mark it as SEEN. Does that mean that the later commit walk will\nskip walking its history? Would we then get a boundary that is actually\nfurther in history than necessary? (\"A --not B C\" would walk all of\nB..A if C has a bitmap, even if a lot of that region is reachable from C.)\n\nMy initial thought here was that this is an unlikely case, so the\noptimization isn't worth the code complexity. But now, I'm a little\nconcerned that it actually hurts the later walk in the case of multiple\nroots.\n\n> +\ttmp_blobs = revs->blob_objects;\n> +\ttmp_trees = revs->tree_objects;\n> +\ttmp_tags = revs->blob_objects;\n> +\trevs->blob_objects = 0;\n> +\trevs->tree_objects = 0;\n> +\trevs->tag_objects = 0;\n> +\n> +\t/*\n> +\t * We didn't have complete coverage of the roots. First setup a\n> +\t * revision walk to (a) OR in any bitmaps that are UNINTERESTING\n> +\t * between the tips and boundary, and (b) record the boundary.\n> +\t */\n> +\ttrace2_region_enter(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n> +\tif (prepare_revision_walk(revs))\n> +\t\tdie(\"revision walk setup failed\");\n> +\ttrace2_region_leave(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n> +\n> +\ttrace2_region_enter(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n> +\trevs->boundary = 1;\n> +\ttraverse_commit_list_filtered(revs,\n> +\t\t\t\t show_boundary_commit,\n> +\t\t\t\t show_boundary_object,\n> +\t\t\t\t &cb, NULL);\n\nLooks good. Callbacks were clear when I read them.\n\n> +\trevs->boundary = 0;\n> +\trevs->blob_objects = tmp_blobs;\n> +\trevs->tree_objects = tmp_trees;\n> +\trevs->tag_objects = tmp_tags;\n\nThese would seem more natural if they were after the trace2_region_leave().\n\n> +\treset_revision_walk();\n> +\tclear_object_flags(UNINTERESTING);\n> +\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n> +\n> +\t/*\n> +\t * Then add the boundary commit(s) as fill-in traversal tips.\n> +\t */\n> +\ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n> +\tif (cb.boundary.nr) {\n\nMaking this an if block does help keep its variables more local. It does\nmake me think about whether the trace2 regions should be within the block,\nbut it's easier to analyze things when the regions are expected to be present.\n\n> +\t\tstruct object *obj;\n> +\t\tint needs_walk = 0;\n> +\n> +\t\tfor (i = 0; i < cb.boundary.nr; i++) {\n> +\t\t\tobj = cb.boundary.objects[i].item;\n> +\n> +\t\t\tif (obj_in_bitmap(bitmap_git, obj, cb.base)) {\n> +\t\t\t\tobj->flags |= SEEN;\n\nThis SEEN makes sense: we want to terminate the walk here as everything\nreachable is already in the bitmap.\n\n> +\t\t\t} else {\n> +\t\t\t\tadd_pending_object(revs, obj, \"\");\n> +\t\t\t\tneeds_walk = 1;\n> +\t\t\t}\n> +\t\t}\n> +\n> +\t\tif (needs_walk)\n> +\t\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n\nI wonder if fill_in_bitmap() already does \"the right thing\" when there\nare no pending objects or when all pending objects are already in the\nbitmap. Do we need to do these checks, or should we just put all boundary\ncommits in the pending set?\n\n> +\t}\n> +\ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n> +\n> +\n\nnit: extra empty line\n\n> +cleanup:\n> +\trevs->ignore_missing_links = 0;\n> +\n> +\treturn cb.base;\n\nDo we need to clean up the cb.boundary object array?\n\n> +}\n> +\n\n...\n\n> @@ -1605,18 +1728,15 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n> \tif (load_bitmap(revs->repo, bitmap_git) < 0)\n> \t\tgoto cleanup;\n> \n> -\tobject_array_clear(&revs->pending);\n> -\n> \tif (haves) {\n> -\t\trevs->ignore_missing_links = 1;\n> -\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n> -\t\treset_revision_walk();\n> -\t\trevs->ignore_missing_links = 0;\n> -\n> +\t\thaves_bitmap = find_boundary_objects(bitmap_git, revs, haves);\n> \t\tif (!haves_bitmap)\n> \t\t\tBUG(\"failed to perform bitmap walk\");\n> \t}\n\nI mentioned in reply to the cover letter that deleting this older algorithm\nis likely premature at this point, and we might want to keep it in general\nas an option.\n\n> +\tobject_array_clear(&revs->pending);\n> +\treset_revision_walk();\n> +\n\nThanks,\n-Stolee\n"},{"id":"476640","messageId":"ZFVOXc6qvVWsI/2C@nand.local","threadId":"59648","inReplyTo":"e6e2401a-519a-4859-d20b-6b947e94e1ec@github.com","subject":"Re: [PATCH v2 2/2] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-05T18:43:41Z","receivedAt":"2023-05-05T18:43:50Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 05, 2023 at 02:13:45PM -0400, Derrick Stolee wrote:\n> On 5/5/2023 1:27 PM, Taylor Blau wrote:\n>\n> > +static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n> > +\t\t\t\t\t struct rev_info *revs,\n> > +\t\t\t\t\t struct object_list *roots)\n> > +{\n> > +\tstruct bitmap_boundary_cb cb = { .bitmap_git = bitmap_git };\n> > +\tunsigned int i;\n> > +\tunsigned int tmp_blobs, tmp_trees, tmp_tags;\n> > +\tint any_missing = 0;\n> > +\n> > +\trevs->ignore_missing_links = 1;\n> > +\n> > +\t/*\n> > +\t * OR in any existing reachability bitmaps among `roots` into `base`.\n> > +\t */\n> > +\twhile (roots) {\n> > +\t\tstruct object *object = roots->item;\n> > +\t\troots = roots->next;\n> > +\n> > +\t\tif (object->type == OBJ_COMMIT &&\n> > +\t\t !obj_in_bitmap(bitmap_git, object, cb.base) &&\n> > +\t\t add_commit_to_bitmap(bitmap_git, &cb.base,\n> > +\t\t\t\t\t (struct commit *)object)) {\n> > +\t\t\tobject->flags |= SEEN;\n> > +\t\t\tcontinue;\n> > +\t\t}\n> > +\n> > +\t\tany_missing = 1;\n> > +\t}\n> > +\n> > +\tif (!any_missing)\n> > +\t\tgoto cleanup;\n>\n> Here, we check if the list of roots are completely covered by existing\n> bitmaps. This prevents doing the commit-only walk as well as the boundary\n> checks.\n>\n> There's another confusing bit here: if we have a bitmap for the commit,\n> then we mark it as SEEN. Does that mean that the later commit walk will\n> skip walking its history? Would we then get a boundary that is actually\n> further in history than necessary? (\"A --not B C\" would walk all of\n> B..A if C has a bitmap, even if a lot of that region is reachable from C.)\n>\n> My initial thought here was that this is an unlikely case, so the\n> optimization isn't worth the code complexity. But now, I'm a little\n> concerned that it actually hurts the later walk in the case of multiple\n> roots.\n\nThe point about commits with existing bitmaps as SEEN hurting the\nboundary traversal is a good one that I hadn't considered. I agree with\nwhat you're saying here, though I think that the optimization still\nmakes sense (without touching the SEEN bit).\n\nIf all of the haves have existing bitmaps, we don't want to bother\nstarting the boundary traversal at all, since we can just OR those\ntogether and be done. So I think we'd just want to drop the SEEN bits\nthere, but let me know if I am missing something.\n\n> > +\trevs->boundary = 0;\n> > +\trevs->blob_objects = tmp_blobs;\n> > +\trevs->tree_objects = tmp_trees;\n> > +\trevs->tag_objects = tmp_tags;\n>\n> These would seem more natural if they were after the trace2_region_leave().\n\nGood suggestion, thanks.\n\n> > +\t\t\t} else {\n> > +\t\t\t\tadd_pending_object(revs, obj, \"\");\n> > +\t\t\t\tneeds_walk = 1;\n> > +\t\t\t}\n> > +\t\t}\n> > +\n> > +\t\tif (needs_walk)\n> > +\t\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n>\n> I wonder if fill_in_bitmap() already does \"the right thing\" when there\n> are no pending objects or when all pending objects are already in the\n> bitmap. Do we need to do these checks, or should we just put all boundary\n> commits in the pending set?\n\nGreat suggestion. It does do the right thing via its `should_include`\nchecks, which see if the commit we're trying to process is already in\nthe bitmap, and if so, propagates SEEN to it and its parents.\n\nHere's a diff that I generated after reading through this message, let\nme know if you think I'm missing anything:\n\n--- >8 ---\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 634fc10156..f57b74bcc0 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1141,7 +1141,6 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n \t\t !obj_in_bitmap(bitmap_git, object, cb.base) &&\n \t\t add_commit_to_bitmap(bitmap_git, &cb.base,\n \t\t\t\t\t (struct commit *)object)) {\n-\t\t\tobject->flags |= SEEN;\n \t\t\tcontinue;\n \t\t}\n\n@@ -1175,13 +1174,14 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t show_boundary_object,\n \t\t\t\t &cb, NULL);\n \trevs->boundary = 0;\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\n \trevs->blob_objects = tmp_blobs;\n \trevs->tree_objects = tmp_trees;\n \trevs->tag_objects = tmp_tags;\n\n \treset_revision_walk();\n \tclear_object_flags(UNINTERESTING);\n-\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n\n \t/*\n \t * Then add the boundary commit(s) as fill-in traversal tips.\n@@ -1189,26 +1189,21 @@ static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n \ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n \tif (cb.boundary.nr) {\n \t\tstruct object *obj;\n-\t\tint needs_walk = 0;\n-\n \t\tfor (i = 0; i < cb.boundary.nr; i++) {\n \t\t\tobj = cb.boundary.objects[i].item;\n\n-\t\t\tif (obj_in_bitmap(bitmap_git, obj, cb.base)) {\n+\t\t\tif (obj_in_bitmap(bitmap_git, obj, cb.base))\n \t\t\t\tobj->flags |= SEEN;\n-\t\t\t} else {\n+\t\t\telse\n \t\t\t\tadd_pending_object(revs, obj, \"\");\n-\t\t\t\tneeds_walk = 1;\n-\t\t\t}\n \t\t}\n\n-\t\tif (needs_walk)\n-\t\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n+\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n \t}\n \ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n\n-\n cleanup:\n+\tobject_array_clear(&cb.boundary);\n \trevs->ignore_missing_links = 0;\n\n \treturn cb.base;\n--- 8< ---\n\nThanks,\nTaylor\n"},{"id":"476641","messageId":"ZFVO9kFZ+lr32WxY@nand.local","threadId":"59648","inReplyTo":"6c8d9142-9013-f3f0-0619-b3780b86b6ab@github.com","subject":"Re: [PATCH v2 0/2] pack-bitmap: boundary-based bitmap traversalt","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-05T18:46:14Z","receivedAt":"2023-05-05T18:46:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 05, 2023 at 01:59:31PM -0400, Derrick Stolee wrote:\n> On 5/5/2023 1:27 PM, Taylor Blau wrote:\n> > Here is a reroll of my series to implement a boundary-based bitmap\n> > traversal algorithm that I worked on towards the end of 2021 with Peff.\n> >\n> > The algorithm is unchanged from the last version, but the implementation\n> > has been made much more straightforward, thanks to a very helpful\n> > suggestion from Stolee.\n> >\n> > Instead of hackily trying to write down all of the UNINTERESTING commits\n> > between the tips and boundary within limit_list(), we can just perform a\n> > commit-only walk, which will give us the set of commits that we need.\n>\n> Something that didn't seem to get attention in this version was buried\n> deep in the commentary of my high-level review [1]:\n\nOops, sorry, I definitely missed this unintentionally and did not mean\nto ignore it.\n\n> > For these reasons, I'm surprised that this patch completely replaces\n> > the old algorithm for the new one. I would prefer to see a config\n> > option that enables this new algorithm. It would be safer to deploy\n> > that way, too.\n>\n> I still think it would be nice to keep the two algorithms for at least\n> a little while instead of completely removing the old one. Let's gather\n> some more evidence and get more reps in with the new algorithm before\n> making it the new default. I could imagine a scenario where someone\n> really wants to spend the extra time to make sure none of the objects\n> reachable from the UNINTERESTING commits are included in the output of\n> this diff.\n>\n> [1] https://lore.kernel.org/git/a143150d-7cf5-c697-0e48-0f7af1c6de8f@github.com/\n\nHmm. I'm not opposed to keeping the old algorithm around, though I\nwonder what the configuration option would look like here. I imagine\nthat we don't want to support the old algorithm indefinitely, though.\n\nPerhaps something like `pack.useBoundaryBitmapTraversal` (implied by\n`feature.experimental`), defaulting to \"false\", and then eventually\n\"true\"?\n\nThanks,\nTaylor\n"},{"id":"476646","messageId":"4ce3ff5f-e7cd-f604-f5da-66939be7d314@github.com","threadId":"59648","inReplyTo":"ZFVO9kFZ+lr32WxY@nand.local","subject":"Re: [PATCH v2 0/2] pack-bitmap: boundary-based bitmap traversalt","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-05T20:45:35Z","receivedAt":"2023-05-05T20:45:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"\n\nOn 5/5/2023 2:46 PM, Taylor Blau wrote:\n> On Fri, May 05, 2023 at 01:59:31PM -0400, Derrick Stolee wrote:\n>> On 5/5/2023 1:27 PM, Taylor Blau wrote:\n>>> Here is a reroll of my series to implement a boundary-based bitmap\n>>> traversal algorithm that I worked on towards the end of 2021 with Peff.\n>>>\n>>> The algorithm is unchanged from the last version, but the implementation\n>>> has been made much more straightforward, thanks to a very helpful\n>>> suggestion from Stolee.\n>>>\n>>> Instead of hackily trying to write down all of the UNINTERESTING commits\n>>> between the tips and boundary within limit_list(), we can just perform a\n>>> commit-only walk, which will give us the set of commits that we need.\n>>\n>> Something that didn't seem to get attention in this version was buried\n>> deep in the commentary of my high-level review [1]:\n> \n> Oops, sorry, I definitely missed this unintentionally and did not mean\n> to ignore it.\n\nI had to dig deep to find it, even after knowing it was in there\nsomewhere, so I'm not upset it didn't happen this version.\n\n>>> For these reasons, I'm surprised that this patch completely replaces\n>>> the old algorithm for the new one. I would prefer to see a config\n>>> option that enables this new algorithm. It would be safer to deploy\n>>> that way, too.\n>>\n>> I still think it would be nice to keep the two algorithms for at least\n>> a little while instead of completely removing the old one. Let's gather\n>> some more evidence and get more reps in with the new algorithm before\n>> making it the new default. I could imagine a scenario where someone\n>> really wants to spend the extra time to make sure none of the objects\n>> reachable from the UNINTERESTING commits are included in the output of\n>> this diff.\n>>\n>> [1] https://lore.kernel.org/git/a143150d-7cf5-c697-0e48-0f7af1c6de8f@github.com/\n> \n> Hmm. I'm not opposed to keeping the old algorithm around, though I\n> wonder what the configuration option would look like here. I imagine\n> that we don't want to support the old algorithm indefinitely, though.\n> \n> Perhaps something like `pack.useBoundaryBitmapTraversal` (implied by\n> `feature.experimental`), defaulting to \"false\", and then eventually\n> \"true\"?\n\nThis name makes sense to me. Including it in feature.experimental right\naway seems like a good idea. Incrementing it to \"true\" by default after\na single release would make sense, too, since the performance benefits\nare so clear. Just important to have that emergency toggle.\n\nThanks,\n-Stolee\n"},{"id":"476778","messageId":"cover.1683567065.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"[PATCH v3 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-08T17:38:02Z","receivedAt":"2023-05-08T17:38:13Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Here is another small reroll of my series to implement a boundary-based\nbitmap traversal algorithm that I worked on towards the end of 2021 with\nPeff.\n\nThe algorithm is the same as in the last round, though I cleaned up a\nfew things throughout thanks to another very helpful review from Stolee.\n\nOne significant change from last time is that the new algorithm is\nopt-in behind feature.experimental, giving users a way to try out the\nnew implementation while still being able to switch back to the\nknown-good traversal in case anything goes wrong.\n\nHopefully after a version or two we can safely remove the conditional\nand drop the existing algorithm.\n\nThanks in advance for your review.\n\nTaylor Blau (3):\n object: add object_array initializer helper function\n pack-bitmap.c: extract `fill_in_bitmap()`\n pack-bitmap.c: use commit boundary during bitmap traversal\n\n Documentation/config/feature.txt | 3 +\n Documentation/config/pack.txt | 17 +++\n ci/run-build-and-tests.sh | 1 +\n object.c | 6 +\n object.h | 2 +\n pack-bitmap.c | 241 ++++++++++++++++++++++++++-----\n pack-bitmap.h | 4 +\n repo-settings.c | 7 +-\n repository.h | 1 +\n t/README | 4 +\n t/t5310-pack-bitmaps.sh | 38 +++++\n 11 files changed, 284 insertions(+), 40 deletions(-)\n\nRange-diff against v2:\n-: ---------- > 1: c31508ac4a object: add object_array initializer helper function\n1: a3a1522439 = 2: e7b30490da pack-bitmap.c: extract `fill_in_bitmap()`\n2: 1993af00cb ! 3: 8a8f41e0c4 pack-bitmap.c: use commit boundary during bitmap traversal\n @@ Commit message\n the true number of objects in a similar fashion as the non-bitmap\n traversal):\n \n - # (Computing objects unique to 'master' among all branches, not\n - # using bitmaps).\n - $ time git rev-list --count --objects master --not --exclude=master --branches\n - 43\n + # (Computing the number of tagged objects not on any branches\n + # without bitmaps).\n + $ time git rev-list --count --objects --tags --not --branches\n + 20\n \n - real 0m0.346s\n - user 0m0.231s\n - sys 0m0.115s\n + real 0m1.388s\n + user 0m1.092s\n + sys 0m0.296s\n \n - # (Computing the same uniqueness query using the old bitmap\n - # traversal algorithm.)\n - $ time git rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches\n - 41\n + # (Computing the same query using the old bitmap traversal).\n + $ time git rev-list --count --objects --tags --not --branches --use-bitmap-index\n + 19\n \n - real 0m20.007s\n - user 0m19.045s\n - sys 0m0.960s\n + real 0m22.709s\n + user 0m21.628s\n + sys 0m1.076s\n \n - # (Computing the same uniqueness query using the new bitmap\n - # traversal algorithm.)\n - $ time git.compile rev-list --use-bitmap-index --count --objects master --not --exclude=master --branches\n - 41\n + # (this commit)\n + $ time git.compile rev-list --count --objects --tags --not --branches --use-bitmap-index\n + 19\n \n - real 0m1.748s\n - user 0m1.428s\n - sys 0m0.320s\n + real 0m1.518s\n + user 0m1.234s\n + sys 0m0.284s\n \n The new algorithm is still slower than not using bitmaps at all, but it\n - is nearly a 11-fold improvement over the existing traversal.\n + is nearly a 15-fold improvement over the existing traversal.\n \n In a more realistic setting (using my local copy of git.git), I can\n observe a similar (if more modest) speed-up:\n \n - $ ours=\"$(git branch --show-current)\"\n - argv=\"--count --objects $ours --not --exclude=$ours --branches\"\n - hyperfine \\\n - -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n - -n 'existing bitmap traversal' \"git rev-list --use-bitmap-index $argv\" \\\n - -n 'this commit' \"git.compile rev-list --use-bitmap-index $argv\"\n + $ argv=\"--count --objects --branches --not --tags\"\n + hyperfine \\\n + -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n + -n 'existing traversal' \"git.compile rev-list --use-bitmap-index $argv\" \\\n + -n 'boundary traversal' \"git.compile -c pack.useBitmapBoundaryTraversal=true rev-list --use-bitmap-index $argv\"\n Benchmark 1: no bitmaps\n - Time (mean ± σ): 5.8 ms ± 0.2 ms [User: 3.3 ms, System: 2.4 ms]\n - Range (min … max): 5.4 ms … 7.0 ms 409 runs\n + Time (mean ± σ): 124.6 ms ± 2.1 ms [User: 103.7 ms, System: 20.8 ms]\n + Range (min … max): 122.6 ms … 133.1 ms 22 runs\n \n - Benchmark 2: existing bitmap traversal\n - Time (mean ± σ): 65.3 ms ± 0.6 ms [User: 49.3 ms, System: 15.8 ms]\n - Range (min … max): 64.1 ms … 66.9 ms 45 runs\n + Benchmark 2: existing traversal\n + Time (mean ± σ): 368.6 ms ± 3.0 ms [User: 325.3 ms, System: 43.1 ms]\n + Range (min … max): 365.1 ms … 374.8 ms 10 runs\n \n - Benchmark 3: this commit\n - Time (mean ± σ): 19.8 ms ± 0.3 ms [User: 12.9 ms, System: 6.8 ms]\n - Range (min … max): 19.1 ms … 20.8 ms 150 runs\n + Benchmark 3: boundary traversal\n + Time (mean ± σ): 167.6 ms ± 0.9 ms [User: 139.5 ms, System: 27.9 ms]\n + Range (min … max): 166.1 ms … 169.2 ms 17 runs\n \n Summary\n 'no bitmaps' ran\n - 3.43 ± 0.14 times faster than 'this commit'\n - 11.34 ± 0.45 times faster than 'existing bitmap traversal'\n + 1.34 ± 0.02 times faster than 'boundary traversal'\n + 2.96 ± 0.05 times faster than 'existing traversal'\n \n Here, the new algorithm is also still slower than not using bitmaps, but\n - represents a more than 3-fold improvement over the existing traversal in\n + represents a more than 2-fold improvement over the existing traversal in\n a more modest example.\n \n Since this algorithm was originally written (nearly a year and a half\n @@ Commit message\n Helped-by: Derrick Stolee \n Signed-off-by: Taylor Blau \n \n + ## Documentation/config/feature.txt ##\n +@@ Documentation/config/feature.txt: feature.experimental::\n + +\n + * `fetch.negotiationAlgorithm=skipping` may improve fetch negotiation times by\n + skipping more commits at a time, reducing the number of round trips.\n +++\n ++* `pack.useBitmapBoundaryTraversal=true` may improve bitmap traversal times by\n ++walking fewer objects.\n + \n + feature.manyFiles::\n + \tEnable config options that optimize for repos with many files in the\n +\n + ## Documentation/config/pack.txt ##\n +@@ Documentation/config/pack.txt: pack.useBitmaps::\n + \ttrue. You should not generally need to turn this off unless\n + \tyou are debugging pack bitmaps.\n + \n ++pack.useBitmapBoundaryTraversal::\n ++\tWhen true, Git will use an experimental algorithm for computing\n ++\treachability queries with bitmaps. Instead of building up\n ++\tcomplete bitmaps for all of the negated tips and then OR-ing\n ++\tthem together, consider negated tips with existing bitmaps as\n ++\tadditive (i.e. OR-ing them into the result if they exist,\n ++\tignoring them otherwise), and build up a bitmap at the boundary\n ++\tinstead.\n +++\n ++When using this algorithm, Git may include too many objects as a result\n ++of not opening up trees belonging to certain UNINTERESTING commits. This\n ++inexactness matches the non-bitmap traversal algorithm.\n +++\n ++In many cases, this can provide a speed-up over the exact algorithm,\n ++particularly when there is poor bitmap coverage of the negated side of\n ++the query.\n ++\n + pack.useSparse::\n + \tWhen true, git will default to using the '--sparse' option in\n + \t'git pack-objects' when the '--revs' option is present. This\n +\n + ## ci/run-build-and-tests.sh ##\n +@@ ci/run-build-and-tests.sh: linux-TEST-vars)\n + \texport GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master\n + \texport GIT_TEST_NO_WRITE_REV_INDEX=1\n + \texport GIT_TEST_CHECKOUT_WORKERS=2\n ++\texport GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n + \t;;\n + linux-clang)\n + \texport GIT_TEST_DEFAULT_HASH=sha1\n +\n ## pack-bitmap.c ##\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n \treturn base;\n }\n \n -+static int obj_in_bitmap(struct bitmap_index *bitmap_git,\n -+\t\t\t struct object *obj, struct bitmap *bitmap)\n -+{\n -+\tint pos;\n -+\n -+\tif (!bitmap)\n -+\t\treturn 0;\n -+\tpos = bitmap_position(bitmap_git, &obj->oid);\n -+\tif (pos < 0)\n -+\t\treturn 0;\n -+\treturn bitmap_get(bitmap, pos);\n -+}\n -+\n +struct bitmap_boundary_cb {\n +\tstruct bitmap_index *bitmap_git;\n +\tstruct bitmap *base;\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\t\tadd_object_array(&commit->object, \"\", &data->boundary);\n +\n +\tif (commit->object.flags & UNINTERESTING) {\n -+\t\tif (obj_in_bitmap(data->bitmap_git, &commit->object,\n -+\t\t\t\t data->base))\n ++\t\tif (bitmap_walk_contains(data->bitmap_git, data->base,\n ++\t\t\t\t\t &commit->object.oid))\n +\t\t\treturn;\n +\n +\t\tadd_commit_to_bitmap(data->bitmap_git, &data->base, commit);\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\t\t\t\t\t struct rev_info *revs,\n +\t\t\t\t\t struct object_list *roots)\n +{\n -+\tstruct bitmap_boundary_cb cb = { .bitmap_git = bitmap_git };\n ++\tstruct bitmap_boundary_cb cb;\n ++\tstruct object_list *root;\n +\tunsigned int i;\n +\tunsigned int tmp_blobs, tmp_trees, tmp_tags;\n +\tint any_missing = 0;\n +\n ++\tcb.bitmap_git = bitmap_git;\n ++\tcb.base = bitmap_new();\n ++\tobject_array_init(&cb.boundary);\n ++\n +\trevs->ignore_missing_links = 1;\n +\n +\t/*\n -+\t * OR in any existing reachability bitmaps among `roots` into `base`.\n ++\t * OR in any existing reachability bitmaps among `roots` into\n ++\t * `cb.base`.\n +\t */\n -+\twhile (roots) {\n -+\t\tstruct object *object = roots->item;\n -+\t\troots = roots->next;\n ++\tfor (root = roots; root; root = root->next) {\n ++\t\tstruct object *object = root->item;\n ++\t\tif (object->type != OBJ_COMMIT ||\n ++\t\t bitmap_walk_contains(bitmap_git, cb.base, &object->oid))\n ++\t\t\tcontinue;\n +\n -+\t\tif (object->type == OBJ_COMMIT &&\n -+\t\t !obj_in_bitmap(bitmap_git, object, cb.base) &&\n -+\t\t add_commit_to_bitmap(bitmap_git, &cb.base,\n -+\t\t\t\t\t (struct commit *)object)) {\n -+\t\t\tobject->flags |= SEEN;\n ++\t\tif (add_commit_to_bitmap(bitmap_git, &cb.base,\n ++\t\t\t\t\t (struct commit *)object))\n +\t\t\tcontinue;\n -+\t\t}\n +\n +\t\tany_missing = 1;\n +\t}\n @@ pack-bitmap.c: static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_\n +\t\t\t\t show_boundary_object,\n +\t\t\t\t &cb, NULL);\n +\trevs->boundary = 0;\n ++\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n ++\n +\trevs->blob_objects = tmp_blobs;\n +\trevs->tree_objects = tmp_trees;\n +\trevs->tag_objects = tmp_tags;\n +\n +\treset_revision_walk();\n +\tclear_object_flags(UNINTERESTING);\n -+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n +\n +\t/*\n +\t * Then add the boundary commit(s) as fill-in traversal tips.\n +\t */\n +\ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n -+\tif (cb.boundary.nr) {\n -+\t\tstruct object *obj;\n -+\t\tint needs_walk = 0;\n -+\n -+\t\tfor (i = 0; i < cb.boundary.nr; i++) {\n -+\t\t\tobj = cb.boundary.objects[i].item;\n -+\n -+\t\t\tif (obj_in_bitmap(bitmap_git, obj, cb.base)) {\n -+\t\t\t\tobj->flags |= SEEN;\n -+\t\t\t} else {\n -+\t\t\t\tadd_pending_object(revs, obj, \"\");\n -+\t\t\t\tneeds_walk = 1;\n -+\t\t\t}\n -+\t\t}\n -+\n -+\t\tif (needs_walk)\n -+\t\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n ++\tfor (i = 0; i < cb.boundary.nr; i++) {\n ++\t\tstruct object *obj = cb.boundary.objects[i].item;\n ++\t\tif (bitmap_walk_contains(bitmap_git, cb.base, &obj->oid))\n ++\t\t\tobj->flags |= SEEN;\n ++\t\telse\n ++\t\t\tadd_pending_object(revs, obj, \"\");\n +\t}\n ++\tif (revs->pending.nr)\n ++\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n +\ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n +\n -+\n +cleanup:\n ++\tobject_array_clear(&cb.boundary);\n +\trevs->ignore_missing_links = 0;\n +\n +\treturn cb.base;\n @@ pack-bitmap.c: static struct bitmap *find_objects(struct bitmap_index *bitmap_gi\n \n \treturn base;\n }\n -@@ pack-bitmap.c: static void show_objects_for_type(\n - \t}\n - }\n +@@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n + \t\t\t\t\t int filter_provided_objects)\n + {\n + \tunsigned int i;\n ++\tint use_boundary_traversal;\n \n --static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n --\t\t\t struct object_list *roots)\n --{\n --\twhile (roots) {\n --\t\tstruct object *object = roots->item;\n --\t\troots = roots->next;\n --\n --\t\tif (bitmap_is_midx(bitmap_git)) {\n --\t\t\tif (bsearch_midx(&object->oid, bitmap_git->midx, NULL))\n --\t\t\t\treturn 1;\n --\t\t} else {\n --\t\t\tif (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)\n --\t\t\t\treturn 1;\n --\t\t}\n --\t}\n --\n --\treturn 0;\n --}\n --\n - static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,\n - \t\t\t\t struct object_list *tip_objects,\n - \t\t\t\t enum object_type type)\n + \tstruct object_list *wants = NULL;\n + \tstruct object_list *haves = NULL;\n @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\tobject_list_insert(object, &wants);\n \t}\n @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n -\t */\n -\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n -\t\tgoto cleanup;\n --\n ++\tuse_boundary_traversal = git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL, -1);\n ++\tif (use_boundary_traversal < 0) {\n ++\t\tprepare_repo_settings(revs->repo);\n ++\t\tuse_boundary_traversal = revs->repo->settings.pack_use_bitmap_boundary_traversal;\n ++\t}\n ++\n ++\tif (!use_boundary_traversal) {\n ++\t\t/*\n ++\t\t * if we have a HAVES list, but none of those haves is contained\n ++\t\t * in the packfile that has a bitmap, we don't have anything to\n ++\t\t * optimize here\n ++\t\t */\n ++\t\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n ++\t\t\tgoto cleanup;\n ++\t}\n + \n \t/* if we don't want anything, we're done here */\n \tif (!wants)\n - \t\tgoto cleanup;\n @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \tif (load_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n \n -\tobject_array_clear(&revs->pending);\n --\n ++\tif (!use_boundary_traversal)\n ++\t\tobject_array_clear(&revs->pending);\n + \n \tif (haves) {\n -\t\trevs->ignore_missing_links = 1;\n -\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n -\t\treset_revision_walk();\n -\t\trevs->ignore_missing_links = 0;\n --\n -+\t\thaves_bitmap = find_boundary_objects(bitmap_git, revs, haves);\n ++\t\tif (use_boundary_traversal) {\n ++\t\t\ttrace2_region_enter(\"pack-bitmap\", \"haves/boundary\", the_repository);\n ++\t\t\thaves_bitmap = find_boundary_objects(bitmap_git, revs, haves);\n ++\t\t\ttrace2_region_leave(\"pack-bitmap\", \"haves/boundary\", the_repository);\n ++\t\t} else {\n ++\t\t\ttrace2_region_enter(\"pack-bitmap\", \"haves/classic\", the_repository);\n ++\t\t\trevs->ignore_missing_links = 1;\n ++\t\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n ++\t\t\treset_revision_walk();\n ++\t\t\trevs->ignore_missing_links = 0;\n ++\t\t\ttrace2_region_leave(\"pack-bitmap\", \"haves/classic\", the_repository);\n ++\t\t}\n + \n \t\tif (!haves_bitmap)\n \t\t\tBUG(\"failed to perform bitmap walk\");\n \t}\n \n -+\tobject_array_clear(&revs->pending);\n -+\treset_revision_walk();\n ++\tif (use_boundary_traversal) {\n ++\t\tobject_array_clear(&revs->pending);\n ++\t\treset_revision_walk();\n ++\t}\n +\n \twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n \n \tif (!wants_bitmap)\n +\n + ## pack-bitmap.h ##\n +@@ pack-bitmap.h: void traverse_bitmap_commit_list(struct bitmap_index *,\n + void test_bitmap_walk(struct rev_info *revs);\n + int test_bitmap_commits(struct repository *r);\n + int test_bitmap_hashes(struct repository *r);\n ++\n ++#define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \\\n ++\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\"\n ++\n + struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n + \t\t\t\t\t int filter_provided_objects);\n + uint32_t midx_preferred_pack(struct bitmap_index *bitmap_git);\n +\n + ## repo-settings.c ##\n +@@ repo-settings.c: void prepare_repo_settings(struct repository *r)\n + \trepo_cfg_bool(r, \"feature.experimental\", &experimental, 0);\n + \n + \t/* Defaults modified by feature.* */\n +-\tif (experimental)\n ++\tif (experimental) {\n + \t\tr->settings.fetch_negotiation_algorithm = FETCH_NEGOTIATION_SKIPPING;\n ++\t\tr->settings.pack_use_bitmap_boundary_traversal = 1;\n ++\t}\n + \tif (manyfiles) {\n + \t\tr->settings.index_version = 4;\n + \t\tr->settings.index_skip_hash = 1;\n +@@ repo-settings.c: void prepare_repo_settings(struct repository *r)\n + \trepo_cfg_bool(r, \"index.sparse\", &r->settings.sparse_index, 0);\n + \trepo_cfg_bool(r, \"index.skiphash\", &r->settings.index_skip_hash, r->settings.index_skip_hash);\n + \trepo_cfg_bool(r, \"pack.readreverseindex\", &r->settings.pack_read_reverse_index, 1);\n ++\trepo_cfg_bool(r, \"pack.usebitmapboundarytraversal\",\n ++\t\t &r->settings.pack_use_bitmap_boundary_traversal,\n ++\t\t r->settings.pack_use_bitmap_boundary_traversal);\n + \n + \t/*\n + \t * The GIT_TEST_MULTI_PACK_INDEX variable is special in that\n +\n + ## repository.h ##\n +@@ repository.h: struct repo_settings {\n + \tint command_requires_full_index;\n + \tint sparse_index;\n + \tint pack_read_reverse_index;\n ++\tint pack_use_bitmap_boundary_traversal;\n + \n + \tstruct fsmonitor_settings *fsmonitor; /* lazily loaded */\n + \n +\n + ## t/README ##\n +@@ t/README: GIT_TEST_INDEX_VERSION= exercises the index read/write code path\n + for the index version specified. Can be set to any valid version\n + (currently 2, 3, or 4).\n + \n ++GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL= if enabled will\n ++use the boundary-based bitmap traversal algorithm. See the documentation\n ++of `pack.useBitmapBoundaryTraversal` for more details.\n ++\n + GIT_TEST_PACK_SPARSE= if disabled will default the pack-objects\n + builtin to use the non-sparse object walk. This can still be overridden by\n + the --sparse command-line argument.\n +\n + ## t/t5310-pack-bitmaps.sh ##\n +@@ t/t5310-pack-bitmaps.sh: test_description='exercise basic bitmap functionality'\n + # their place.\n + GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0\n + \n ++# Likewise, allow individual tests to control whether or not they use\n ++# the boundary-based traversal.\n ++sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n ++\n + objpath () {\n + \techo \".git/objects/$(echo \"$1\" | sed -e 's|\\(..\\)|\\1/|')\"\n + }\n +@@ t/t5310-pack-bitmaps.sh: test_bitmap_cases () {\n + \n + test_bitmap_cases\n + \n ++GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n ++export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n ++\n ++test_bitmap_cases\n ++\n ++sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n ++\n + test_expect_success 'incremental repack fails when bitmaps are requested' '\n + \ttest_commit more-1 &&\n + \ttest_must_fail git repack -d 2>err &&\n +@@ t/t5310-pack-bitmaps.sh: test_expect_success 'incremental repack can disable bitmaps' '\n + \tgit repack -d --no-write-bitmap-index\n + '\n + \n ++test_expect_success 'boundary-based traversal is used when requested' '\n ++\tgit repack -a -d --write-bitmap-index &&\n ++\n ++\tfor argv in \\\n ++\t\t\"git -c pack.useBitmapBoundaryTraversal=true\" \\\n ++\t\t\"git -c feature.experimental=true\" \\\n ++\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 git\"\n ++\tdo\n ++\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n ++\t\t\t--use-bitmap-index second..other 2>perf\" &&\n ++\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/boundary\\\"\" perf ||\n ++\t\t\treturn 1\n ++\tdone &&\n ++\n ++\tfor argv in \\\n ++\t\t\"git -c pack.useBitmapBoundaryTraversal=false\" \\\n ++\t\t\"git -c feature.experimental=true -c pack.useBitmapBoundaryTraversal=false\" \\\n ++\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c pack.useBitmapBoundaryTraversal=true\" \\\n ++\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c feature.experimental=true\"\n ++\tdo\n ++\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n ++\t\t\t--use-bitmap-index second..other 2>perf\" &&\n ++\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/classic\\\"\" perf ||\n ++\t\t\treturn 1\n ++\tdone\n ++'\n ++\n + test_bitmap_cases \"pack.writeBitmapLookupTable\"\n + \n + test_expect_success 'verify writing bitmap lookup table when enabled' '\n-- \n2.40.1.479.g8f2b93ade7\n"},{"id":"476779","messageId":"c31508ac4a5f335a6b923fdf84b20b4871298ee0.1683567065.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1683567065.git.me@ttaylorr.com","subject":"[PATCH v3 1/3] object: add object_array initializer helper function","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-08T17:38:06Z","receivedAt":"2023-05-08T17:38:15Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The object_array API has an OBJECT_ARRAY_INIT macro, but lacks a\nfunction to initialize an object_array at a given location in memory.\n\nIntroduce `object_array_init()` to implement such a function.\n\nSigned-off-by: Taylor Blau \n---\n object.c | 6 ++++++\n object.h | 2 ++\n 2 files changed, 8 insertions(+)\n\ndiff --git a/object.c b/object.c\nindex 6d4ef1524d..f1adb458b6 100644\n--- a/object.c\n+++ b/object.c\n@@ -356,6 +356,12 @@ void object_list_free(struct object_list **list)\n */\n static char object_array_slopbuf[1];\n \n+void object_array_init(struct object_array *array)\n+{\n+\tstruct object_array blank = OBJECT_ARRAY_INIT;\n+\tmemcpy(array, &blank, sizeof(*array));\n+}\n+\n void add_object_array_with_path(struct object *obj, const char *name,\n \t\t\t\tstruct object_array *array,\n \t\t\t\tunsigned mode, const char *path)\ndiff --git a/object.h b/object.h\nindex 96e52e24fb..c335435f9c 100644\n--- a/object.h\n+++ b/object.h\n@@ -57,6 +57,8 @@ struct object_array {\n \n #define OBJECT_ARRAY_INIT { 0 }\n \n+void object_array_init(struct object_array *array);\n+\n /*\n * object flag allocation:\n * revision.h: 0---------10 15 23------27\n-- \n2.40.1.479.g8f2b93ade7\n\n"},{"id":"476780","messageId":"e7b30490dae51b1375545ba19561900ed0f340b7.1683567065.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1683567065.git.me@ttaylorr.com","subject":"[PATCH v3 2/3] pack-bitmap.c: extract `fill_in_bitmap()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-08T17:38:09Z","receivedAt":"2023-05-08T17:38:27Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"To prepare for the boundary-based bitmap walk to perform a fill-in\ntraversal using the boundary of either side as the tips, extract routine\nused to perform fill-in traversal by `find_objects()` so that it can be\nused in both places.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 65 ++++++++++++++++++++++++++++-----------------------\n 1 file changed, 36 insertions(+), 29 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e0fad723bf..5d2cc6ac96 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1043,6 +1043,40 @@ static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n \treturn 1;\n }\n \n+static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct rev_info *revs,\n+\t\t\t\t struct bitmap *base,\n+\t\t\t\t struct bitmap *seen)\n+{\n+\tstruct include_data incdata;\n+\tstruct bitmap_show_data show_data;\n+\n+\tif (!base)\n+\t\tbase = bitmap_new();\n+\n+\tincdata.bitmap_git = bitmap_git;\n+\tincdata.base = base;\n+\tincdata.seen = seen;\n+\n+\trevs->include_check = should_include;\n+\trevs->include_check_obj = should_include_obj;\n+\trevs->include_check_data = &incdata;\n+\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(_(\"revision walk setup failed\"));\n+\n+\tshow_data.bitmap_git = bitmap_git;\n+\tshow_data.base = base;\n+\n+\ttraverse_commit_list(revs, show_commit, show_object, &show_data);\n+\n+\trevs->include_check = NULL;\n+\trevs->include_check_obj = NULL;\n+\trevs->include_check_data = NULL;\n+\n+\treturn base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1108,35 +1142,8 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk) {\n-\t\tstruct include_data incdata;\n-\t\tstruct bitmap_show_data show_data;\n-\n-\t\tif (!base)\n-\t\t\tbase = bitmap_new();\n-\n-\t\tincdata.bitmap_git = bitmap_git;\n-\t\tincdata.base = base;\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-\t\t\tdie(_(\"revision walk setup failed\"));\n-\n-\t\tshow_data.bitmap_git = bitmap_git;\n-\t\tshow_data.base = base;\n-\n-\t\ttraverse_commit_list(revs,\n-\t\t\t\t show_commit, show_object,\n-\t\t\t\t &show_data);\n-\n-\t\trevs->include_check = NULL;\n-\t\trevs->include_check_obj = NULL;\n-\t\trevs->include_check_data = NULL;\n-\t}\n+\tif (needs_walk)\n+\t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n \n \treturn base;\n }\n-- \n2.40.1.479.g8f2b93ade7\n\n"},{"id":"476781","messageId":"8a8f41e0c410f9160b8ff922333c13ed68f7334b.1683567065.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1683567065.git.me@ttaylorr.com","subject":"[PATCH v3 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-08T17:38:12Z","receivedAt":"2023-05-08T17:38:30Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When reachability bitmap coverage exists in a repository, Git will use a\ndifferent (and hopefully faster) traversal to compute revision walks.\n\nConsider a set of positive and negative tips (which we'll refer to with\ntheir standard bitmap parlance by \"wants\", and \"haves\"). In order to\nfigure out what objects exist between the tips, the existing traversal\nin `prepare_bitmap_walk()` does something like:\n\n 1. Consider if we can even compute the set of objects with bitmaps,\n and fall back to the usual traversal if we cannot. For example,\n pathspec limiting traversals can't be computed using bitmaps (since\n they don't know which objects are at which paths). The same is true\n of certain kinds of non-trivial object filters.\n\n 2. If we can compute the traversal with bitmaps, partition the\n (dereferenced) tips into two object lists, \"haves\", and \"wants\",\n based on whether or not the objects have the UNINTERESTING flag,\n respectively.\n\n 3. Fall back to the ordinary object traversal if either (a) there are\n more than zero haves, none of which are in the bitmapped pack or\n MIDX, or (b) there are no wants.\n\n 4. Construct a reachability bitmap for the \"haves\" side by walking\n from the revision tips down to any existing bitmaps, OR-ing in any\n bitmaps as they are found.\n\n 5. Then do the same for the \"wants\" side, stopping at any objects that\n appear in the \"haves\" bitmap.\n\n 6. Filter the results if any object filter (that can be easily\n computed with bitmaps alone) was given, and then return back to the\n caller.\n\nWhen there is good bitmap coverage relative to the traversal tips, this\nwalk is often significantly faster than an ordinary object traversal\nbecause it can visit far fewer objects.\n\nBut in certain cases, it can be significantly *slower* than the usual\nobject traversal. Why? Because we need to compute complete bitmaps on\neither side of the walk. If either one (or both) of the sides require\nwalking many (or all!) objects before they get to an existing bitmap,\nthe extra bitmap machinery is mostly or all overhead.\n\nOne of the benefits, however, is that even if the walk is slower, bitmap\ntraversals are guaranteed to provide an *exact* answer. Unlike the\ntraditional object traversal algorithm, which can over-count the results\nby not opening trees for older commits, the bitmap walk builds an exact\nreachability bitmap for either side, meaning the results are never\nover-counted.\n\nBut producing non-exact results is OK for our traversal here (both in\nthe bitmap case and not), as long as the results are over-counted, not\nunder.\n\nRelaxing the bitmap traversal to allow it to produce over-counted\nresults gives us the opportunity to make some significant improvements.\nInstead of the above, the new algorithm only has to walk from the\n*boundary* down to the nearest bitmap, instead of from each of the\nUNINTERESTING tips.\n\nThe boundary-based approach still has degenerate cases, but we'll show\nin a moment that it is often a significant improvement.\n\nThe new algorithm works as follows:\n\n 1. Build a (partial) bitmap of the haves side by first OR-ing any\n bitmap(s) that already exist for UNINTERESTING commits between the\n haves and the boundary.\n\n 2. For each commit along the boundary, add it as a fill-in traversal\n tip (where the traversal terminates once an existing bitmap is\n found), and perform fill-in traversal.\n\n 3. Build up a complete bitmap of the wants side as usual, stopping any\n time we intersect the (partial) haves side.\n\n 4. Return the results.\n\nAnd is more-or-less equivalent to using the *old* algorithm with this\ninvocation:\n\n $ git rev-list --objects --use-bitmap-index $WANTS --not \\\n $(git rev-list --objects --boundary $WANTS --not $HAVES |\n perl -lne 'print $1 if /^-(.*)/')\n\nThe new result performs significantly better in many cases, particularly\nwhen the distance from the boundary commit(s) to an existing bitmap is\nshorter than the distance from (all of) the have tips to the nearest\nbitmapped commit.\n\nNote that when using the old bitmap traversal algorithm, the results can\nbe *slower* than without bitmaps! Under the new algorithm, the result is\ncomputed faster with bitmaps than without (at the cost of over-counting\nthe true number of objects in a similar fashion as the non-bitmap\ntraversal):\n\n # (Computing the number of tagged objects not on any branches\n # without bitmaps).\n $ time git rev-list --count --objects --tags --not --branches\n 20\n\n real\t0m1.388s\n user\t0m1.092s\n sys\t0m0.296s\n\n # (Computing the same query using the old bitmap traversal).\n $ time git rev-list --count --objects --tags --not --branches --use-bitmap-index\n 19\n\n real\t0m22.709s\n user\t0m21.628s\n sys\t0m1.076s\n\n # (this commit)\n $ time git.compile rev-list --count --objects --tags --not --branches --use-bitmap-index\n 19\n\n real\t0m1.518s\n user\t0m1.234s\n sys\t0m0.284s\n\nThe new algorithm is still slower than not using bitmaps at all, but it\nis nearly a 15-fold improvement over the existing traversal.\n\nIn a more realistic setting (using my local copy of git.git), I can\nobserve a similar (if more modest) speed-up:\n\n $ argv=\"--count --objects --branches --not --tags\"\n hyperfine \\\n -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n -n 'existing traversal' \"git.compile rev-list --use-bitmap-index $argv\" \\\n -n 'boundary traversal' \"git.compile -c pack.useBitmapBoundaryTraversal=true rev-list --use-bitmap-index $argv\"\n Benchmark 1: no bitmaps\n Time (mean ± σ): 124.6 ms ± 2.1 ms [User: 103.7 ms, System: 20.8 ms]\n Range (min … max): 122.6 ms … 133.1 ms 22 runs\n\n Benchmark 2: existing traversal\n Time (mean ± σ): 368.6 ms ± 3.0 ms [User: 325.3 ms, System: 43.1 ms]\n Range (min … max): 365.1 ms … 374.8 ms 10 runs\n\n Benchmark 3: boundary traversal\n Time (mean ± σ): 167.6 ms ± 0.9 ms [User: 139.5 ms, System: 27.9 ms]\n Range (min … max): 166.1 ms … 169.2 ms 17 runs\n\n Summary\n 'no bitmaps' ran\n 1.34 ± 0.02 times faster than 'boundary traversal'\n 2.96 ± 0.05 times faster than 'existing traversal'\n\nHere, the new algorithm is also still slower than not using bitmaps, but\nrepresents a more than 2-fold improvement over the existing traversal in\na more modest example.\n\nSince this algorithm was originally written (nearly a year and a half\nago, at the time of writing), the bitmap lookup table shipped, making\nthe new algorithm's result more competitive. A few other future\ndirections for improving bitmap traversal times beyond not using bitmaps\nat all:\n\n - Decrease the cost to decompress and OR together many bitmaps\n together (particularly when enumerating the uninteresting side of\n the walk). Here we could explore more efficient bitmap storage\n techniques, like Roaring+Run and/or use SIMD instructions to speed\n up ORing them together.\n\n - Store pseudo-merge bitmaps, which could allow us to OR together\n fewer \"summary\" bitmaps (which would also help with the above).\n\nHelped-by: Jeff King \nHelped-by: Derrick Stolee \nSigned-off-by: Taylor Blau \n---\n Documentation/config/feature.txt | 3 +\n Documentation/config/pack.txt | 17 +++\n ci/run-build-and-tests.sh | 1 +\n pack-bitmap.c | 182 ++++++++++++++++++++++++++++---\n pack-bitmap.h | 4 +\n repo-settings.c | 7 +-\n repository.h | 1 +\n t/README | 4 +\n t/t5310-pack-bitmaps.sh | 38 +++++++\n 9 files changed, 243 insertions(+), 14 deletions(-)\n\ndiff --git a/Documentation/config/feature.txt b/Documentation/config/feature.txt\nindex 17b4d39f89..bf9546fca4 100644\n--- a/Documentation/config/feature.txt\n+++ b/Documentation/config/feature.txt\n@@ -14,6 +14,9 @@ feature.experimental::\n +\n * `fetch.negotiationAlgorithm=skipping` may improve fetch negotiation times by\n skipping more commits at a time, reducing the number of round trips.\n++\n+* `pack.useBitmapBoundaryTraversal=true` may improve bitmap traversal times by\n+walking fewer objects.\n \n feature.manyFiles::\n \tEnable config options that optimize for repos with many files in the\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex d4c7c9d4e4..3748136d14 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -123,6 +123,23 @@ pack.useBitmaps::\n \ttrue. You should not generally need to turn this off unless\n \tyou are debugging pack bitmaps.\n \n+pack.useBitmapBoundaryTraversal::\n+\tWhen true, Git will use an experimental algorithm for computing\n+\treachability queries with bitmaps. Instead of building up\n+\tcomplete bitmaps for all of the negated tips and then OR-ing\n+\tthem together, consider negated tips with existing bitmaps as\n+\tadditive (i.e. OR-ing them into the result if they exist,\n+\tignoring them otherwise), and build up a bitmap at the boundary\n+\tinstead.\n++\n+When using this algorithm, Git may include too many objects as a result\n+of not opening up trees belonging to certain UNINTERESTING commits. This\n+inexactness matches the non-bitmap traversal algorithm.\n++\n+In many cases, this can provide a speed-up over the exact algorithm,\n+particularly when there is poor bitmap coverage of the negated side of\n+the query.\n+\n pack.useSparse::\n \tWhen true, git will default to using the '--sparse' option in\n \t'git pack-objects' when the '--revs' option is present. This\ndiff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh\nindex a18b13a41d..2528f25e31 100755\n--- a/ci/run-build-and-tests.sh\n+++ b/ci/run-build-and-tests.sh\n@@ -29,6 +29,7 @@ linux-TEST-vars)\n \texport GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master\n \texport GIT_TEST_NO_WRITE_REV_INDEX=1\n \texport GIT_TEST_CHECKOUT_WORKERS=2\n+\texport GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n \t;;\n linux-clang)\n \texport GIT_TEST_DEFAULT_HASH=sha1\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 5d2cc6ac96..e8a1579b16 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1077,6 +1077,126 @@ static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n \treturn base;\n }\n \n+struct bitmap_boundary_cb {\n+\tstruct bitmap_index *bitmap_git;\n+\tstruct bitmap *base;\n+\n+\tstruct object_array boundary;\n+};\n+\n+static void show_boundary_commit(struct commit *commit, void *_data)\n+{\n+\tstruct bitmap_boundary_cb *data = _data;\n+\n+\tif (commit->object.flags & BOUNDARY)\n+\t\tadd_object_array(&commit->object, \"\", &data->boundary);\n+\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\tif (bitmap_walk_contains(data->bitmap_git, data->base,\n+\t\t\t\t\t &commit->object.oid))\n+\t\t\treturn;\n+\n+\t\tadd_commit_to_bitmap(data->bitmap_git, &data->base, commit);\n+\t}\n+}\n+\n+static void show_boundary_object(struct object *object,\n+\t\t\t\t const char *name, void *data)\n+{\n+\tBUG(\"should not be called\");\n+}\n+\n+static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n+\t\t\t\t\t struct rev_info *revs,\n+\t\t\t\t\t struct object_list *roots)\n+{\n+\tstruct bitmap_boundary_cb cb;\n+\tstruct object_list *root;\n+\tunsigned int i;\n+\tunsigned int tmp_blobs, tmp_trees, tmp_tags;\n+\tint any_missing = 0;\n+\n+\tcb.bitmap_git = bitmap_git;\n+\tcb.base = bitmap_new();\n+\tobject_array_init(&cb.boundary);\n+\n+\trevs->ignore_missing_links = 1;\n+\n+\t/*\n+\t * OR in any existing reachability bitmaps among `roots` into\n+\t * `cb.base`.\n+\t */\n+\tfor (root = roots; root; root = root->next) {\n+\t\tstruct object *object = root->item;\n+\t\tif (object->type != OBJ_COMMIT ||\n+\t\t bitmap_walk_contains(bitmap_git, cb.base, &object->oid))\n+\t\t\tcontinue;\n+\n+\t\tif (add_commit_to_bitmap(bitmap_git, &cb.base,\n+\t\t\t\t\t (struct commit *)object))\n+\t\t\tcontinue;\n+\n+\t\tany_missing = 1;\n+\t}\n+\n+\tif (!any_missing)\n+\t\tgoto cleanup;\n+\n+\ttmp_blobs = revs->blob_objects;\n+\ttmp_trees = revs->tree_objects;\n+\ttmp_tags = revs->blob_objects;\n+\trevs->blob_objects = 0;\n+\trevs->tree_objects = 0;\n+\trevs->tag_objects = 0;\n+\n+\t/*\n+\t * We didn't have complete coverage of the roots. First setup a\n+\t * revision walk to (a) OR in any bitmaps that are UNINTERESTING\n+\t * between the tips and boundary, and (b) record the boundary.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"revision walk setup failed\");\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\trevs->boundary = 1;\n+\ttraverse_commit_list_filtered(revs,\n+\t\t\t\t show_boundary_commit,\n+\t\t\t\t show_boundary_object,\n+\t\t\t\t &cb, NULL);\n+\trevs->boundary = 0;\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\n+\trevs->blob_objects = tmp_blobs;\n+\trevs->tree_objects = tmp_trees;\n+\trevs->tag_objects = tmp_tags;\n+\n+\treset_revision_walk();\n+\tclear_object_flags(UNINTERESTING);\n+\n+\t/*\n+\t * Then add the boundary commit(s) as fill-in traversal tips.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\tfor (i = 0; i < cb.boundary.nr; i++) {\n+\t\tstruct object *obj = cb.boundary.objects[i].item;\n+\t\tif (bitmap_walk_contains(bitmap_git, cb.base, &obj->oid))\n+\t\t\tobj->flags |= SEEN;\n+\t\telse\n+\t\t\tadd_pending_object(revs, obj, \"\");\n+\t}\n+\tif (revs->pending.nr)\n+\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\n+cleanup:\n+\tobject_array_clear(&cb.boundary);\n+\trevs->ignore_missing_links = 0;\n+\n+\treturn cb.base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1142,8 +1262,21 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk)\n+\tif (needs_walk) {\n+\t\t/*\n+\t\t * This fill-in traversal may walk over some objects\n+\t\t * again, since we have already traversed in order to\n+\t\t * find the boundary.\n+\t\t *\n+\t\t * But this extra walk should be extremely cheap, since\n+\t\t * all commit objects are loaded into memory, and\n+\t\t * because we skip walking to parents that are\n+\t\t * UNINTERESTING, since it will be marked in the haves\n+\t\t * bitmap already (or it has an on-disk bitmap, since\n+\t\t * OR-ing it in covers all of its ancestors).\n+\t\t */\n \t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n+\t}\n \n \treturn base;\n }\n@@ -1535,6 +1668,7 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\t\t\t int filter_provided_objects)\n {\n \tunsigned int i;\n+\tint use_boundary_traversal;\n \n \tstruct object_list *wants = NULL;\n \tstruct object_list *haves = NULL;\n@@ -1585,13 +1719,21 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\tobject_list_insert(object, &wants);\n \t}\n \n-\t/*\n-\t * if we have a HAVES list, but none of those haves is contained\n-\t * in the packfile that has a bitmap, we don't have anything to\n-\t * optimize here\n-\t */\n-\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n-\t\tgoto cleanup;\n+\tuse_boundary_traversal = git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL, -1);\n+\tif (use_boundary_traversal < 0) {\n+\t\tprepare_repo_settings(revs->repo);\n+\t\tuse_boundary_traversal = revs->repo->settings.pack_use_bitmap_boundary_traversal;\n+\t}\n+\n+\tif (!use_boundary_traversal) {\n+\t\t/*\n+\t\t * if we have a HAVES list, but none of those haves is contained\n+\t\t * in the packfile that has a bitmap, we don't have anything to\n+\t\t * optimize here\n+\t\t */\n+\t\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n+\t\t\tgoto cleanup;\n+\t}\n \n \t/* if we don't want anything, we're done here */\n \tif (!wants)\n@@ -1605,18 +1747,32 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \tif (load_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n \n-\tobject_array_clear(&revs->pending);\n+\tif (!use_boundary_traversal)\n+\t\tobject_array_clear(&revs->pending);\n \n \tif (haves) {\n-\t\trevs->ignore_missing_links = 1;\n-\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n-\t\treset_revision_walk();\n-\t\trevs->ignore_missing_links = 0;\n+\t\tif (use_boundary_traversal) {\n+\t\t\ttrace2_region_enter(\"pack-bitmap\", \"haves/boundary\", the_repository);\n+\t\t\thaves_bitmap = find_boundary_objects(bitmap_git, revs, haves);\n+\t\t\ttrace2_region_leave(\"pack-bitmap\", \"haves/boundary\", the_repository);\n+\t\t} else {\n+\t\t\ttrace2_region_enter(\"pack-bitmap\", \"haves/classic\", the_repository);\n+\t\t\trevs->ignore_missing_links = 1;\n+\t\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n+\t\t\treset_revision_walk();\n+\t\t\trevs->ignore_missing_links = 0;\n+\t\t\ttrace2_region_leave(\"pack-bitmap\", \"haves/classic\", the_repository);\n+\t\t}\n \n \t\tif (!haves_bitmap)\n \t\t\tBUG(\"failed to perform bitmap walk\");\n \t}\n \n+\tif (use_boundary_traversal) {\n+\t\tobject_array_clear(&revs->pending);\n+\t\treset_revision_walk();\n+\t}\n+\n \twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n \n \tif (!wants_bitmap)\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex f0180b5276..daa72b6331 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -62,6 +62,10 @@ void traverse_bitmap_commit_list(struct bitmap_index *,\n void test_bitmap_walk(struct rev_info *revs);\n int test_bitmap_commits(struct repository *r);\n int test_bitmap_hashes(struct repository *r);\n+\n+#define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \\\n+\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\"\n+\n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\t\t\t int filter_provided_objects);\n uint32_t midx_preferred_pack(struct bitmap_index *bitmap_git);\ndiff --git a/repo-settings.c b/repo-settings.c\nindex d220c5dd9f..7b566d729d 100644\n--- a/repo-settings.c\n+++ b/repo-settings.c\n@@ -41,8 +41,10 @@ void prepare_repo_settings(struct repository *r)\n \trepo_cfg_bool(r, \"feature.experimental\", &experimental, 0);\n \n \t/* Defaults modified by feature.* */\n-\tif (experimental)\n+\tif (experimental) {\n \t\tr->settings.fetch_negotiation_algorithm = FETCH_NEGOTIATION_SKIPPING;\n+\t\tr->settings.pack_use_bitmap_boundary_traversal = 1;\n+\t}\n \tif (manyfiles) {\n \t\tr->settings.index_version = 4;\n \t\tr->settings.index_skip_hash = 1;\n@@ -62,6 +64,9 @@ void prepare_repo_settings(struct repository *r)\n \trepo_cfg_bool(r, \"index.sparse\", &r->settings.sparse_index, 0);\n \trepo_cfg_bool(r, \"index.skiphash\", &r->settings.index_skip_hash, r->settings.index_skip_hash);\n \trepo_cfg_bool(r, \"pack.readreverseindex\", &r->settings.pack_read_reverse_index, 1);\n+\trepo_cfg_bool(r, \"pack.usebitmapboundarytraversal\",\n+\t\t &r->settings.pack_use_bitmap_boundary_traversal,\n+\t\t r->settings.pack_use_bitmap_boundary_traversal);\n \n \t/*\n \t * The GIT_TEST_MULTI_PACK_INDEX variable is special in that\ndiff --git a/repository.h b/repository.h\nindex 1a13ff2867..c42f7ab6bd 100644\n--- a/repository.h\n+++ b/repository.h\n@@ -37,6 +37,7 @@ struct repo_settings {\n \tint command_requires_full_index;\n \tint sparse_index;\n \tint pack_read_reverse_index;\n+\tint pack_use_bitmap_boundary_traversal;\n \n \tstruct fsmonitor_settings *fsmonitor; /* lazily loaded */\n \ndiff --git a/t/README b/t/README\nindex bdfac4cceb..b71a065e4a 100644\n--- a/t/README\n+++ b/t/README\n@@ -442,6 +442,10 @@ GIT_TEST_INDEX_VERSION= exercises the index read/write code path\n for the index version specified. Can be set to any valid version\n (currently 2, 3, or 4).\n \n+GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL= if enabled will\n+use the boundary-based bitmap traversal algorithm. See the documentation\n+of `pack.useBitmapBoundaryTraversal` for more details.\n+\n GIT_TEST_PACK_SPARSE= if disabled will default the pack-objects\n builtin to use the non-sparse object walk. This can still be overridden by\n the --sparse command-line argument.\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 526a5a506e..78c1c6c923 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -9,6 +9,10 @@ test_description='exercise basic bitmap functionality'\n # their place.\n GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0\n \n+# Likewise, allow individual tests to control whether or not they use\n+# the boundary-based traversal.\n+sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n+\n objpath () {\n \techo \".git/objects/$(echo \"$1\" | sed -e 's|\\(..\\)|\\1/|')\"\n }\n@@ -457,6 +461,13 @@ test_bitmap_cases () {\n \n test_bitmap_cases\n \n+GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n+export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n+\n+test_bitmap_cases\n+\n+sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n+\n test_expect_success 'incremental repack fails when bitmaps are requested' '\n \ttest_commit more-1 &&\n \ttest_must_fail git repack -d 2>err &&\n@@ -468,6 +479,33 @@ test_expect_success 'incremental repack can disable bitmaps' '\n \tgit repack -d --no-write-bitmap-index\n '\n \n+test_expect_success 'boundary-based traversal is used when requested' '\n+\tgit repack -a -d --write-bitmap-index &&\n+\n+\tfor argv in \\\n+\t\t\"git -c pack.useBitmapBoundaryTraversal=true\" \\\n+\t\t\"git -c feature.experimental=true\" \\\n+\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 git\"\n+\tdo\n+\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n+\t\t\t--use-bitmap-index second..other 2>perf\" &&\n+\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/boundary\\\"\" perf ||\n+\t\t\treturn 1\n+\tdone &&\n+\n+\tfor argv in \\\n+\t\t\"git -c pack.useBitmapBoundaryTraversal=false\" \\\n+\t\t\"git -c feature.experimental=true -c pack.useBitmapBoundaryTraversal=false\" \\\n+\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c pack.useBitmapBoundaryTraversal=true\" \\\n+\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c feature.experimental=true\"\n+\tdo\n+\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n+\t\t\t--use-bitmap-index second..other 2>perf\" &&\n+\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/classic\\\"\" perf ||\n+\t\t\treturn 1\n+\tdone\n+'\n+\n test_bitmap_cases \"pack.writeBitmapLookupTable\"\n \n test_expect_success 'verify writing bitmap lookup table when enabled' '\n-- \n2.40.1.479.g8f2b93ade7\n"},{"id":"476810","messageId":"673a2b60-0556-fc2b-edf7-f2a19ef5dcbe@github.com","threadId":"59648","inReplyTo":"8a8f41e0c410f9160b8ff922333c13ed68f7334b.1683567065.git.me@ttaylorr.com","subject":"Re: [PATCH v3 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-08T20:53:35Z","receivedAt":"2023-05-08T20:54:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/8/2023 1:38 PM, Taylor Blau wrote:\n\n> -\t/*\n> -\t * if we have a HAVES list, but none of those haves is contained\n> -\t * in the packfile that has a bitmap, we don't have anything to\n> -\t * optimize here\n> -\t */\n> -\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n> -\t\tgoto cleanup;\n> +\tuse_boundary_traversal = git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL, -1);\n> +\tif (use_boundary_traversal < 0) {\n> +\t\tprepare_repo_settings(revs->repo);\n> +\t\tuse_boundary_traversal = revs->repo->settings.pack_use_bitmap_boundary_traversal;\n> +\t}\n> +\n> +\tif (!use_boundary_traversal) {\n> +\t\t/*\n> +\t\t * if we have a HAVES list, but none of those haves is contained\n> +\t\t * in the packfile that has a bitmap, we don't have anything to\n> +\t\t * optimize here\n> +\t\t */\n> +\t\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n> +\t\t\tgoto cleanup;\n> +\t}\n\nI was reading along, nodding my head, until I came across this comment.\nI recognize that it's moved from an existing place, but this seems very\nstrange and incorrect.\n\nIs this implying that if the 'haves' are not in the bitmapped pack, then\nwe _can't_ construct a bitmap representing the objects they can reach?\n\nDo we not have the ability to extend the object order beyond the bitmapped\npack in-memory in a way that allows us to provide bit positions for the\nobjects not in the bitmapped pack?\n\nI can understand saying \"it might be more expensive to construct a bitmap\nhere, because we need to walk into the bitmapped pack before we have a\nhope of hitting a bitmap.\" However, that's far from \"we don't have anything\nto optimize\".\n\nThis comment is from fff42755efc (pack-bitmap: add support for bitmap\nindexes, 2013-12-21), and perhaps at that time we didn't have the ability\nto construct a reachability bitmap across the non-bitmapped pack.\n\nSomething to think about removing in the future, but not a blocker for\nthis series. Getting it out of the way for the boundary-based walk makes\neven more sense because the commits to check are those in the boundary,\nnot the haves themselves.\n \n> +test_expect_success 'boundary-based traversal is used when requested' '\n> +\tgit repack -a -d --write-bitmap-index &&\n> +\n> +\tfor argv in \\\n> +\t\t\"git -c pack.useBitmapBoundaryTraversal=true\" \\\n> +\t\t\"git -c feature.experimental=true\" \\\n> +\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 git\"\n> +\tdo\n> +\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n> +\t\t\t--use-bitmap-index second..other 2>perf\" &&\n> +\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/boundary\\\"\" perf ||\n> +\t\t\treturn 1\n> +\tdone &&\n> +\n> +\tfor argv in \\\n> +\t\t\"git -c pack.useBitmapBoundaryTraversal=false\" \\\n> +\t\t\"git -c feature.experimental=true -c pack.useBitmapBoundaryTraversal=false\" \\\n> +\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c pack.useBitmapBoundaryTraversal=true\" \\\n> +\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c feature.experimental=true\"\n\nThis ordering (GIT_TEST_*=0 overrides config) seems backwards to me, but\nit doesn't really matter since it's a GIT_TEST_* variable. Thanks for\nincluding tests so the order is documented.\n\n> +\tdo\n> +\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n> +\t\t\t--use-bitmap-index second..other 2>perf\" &&\n> +\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/classic\\\"\" perf ||\n> +\t\t\treturn 1\n\nnit: you should be able to use 'test_region' here. Probably not worth\na re-roll, as everything else looks good to me.\n\nThanks,\n-Stolee\n"},{"id":"476834","messageId":"ZFlzsYAREyA+6NLX@nand.local","threadId":"59648","inReplyTo":"673a2b60-0556-fc2b-edf7-f2a19ef5dcbe@github.com","subject":"Re: [PATCH v3 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-08T22:12:01Z","receivedAt":"2023-05-08T22:12:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, May 08, 2023 at 04:53:35PM -0400, Derrick Stolee wrote:\n> On 5/8/2023 1:38 PM, Taylor Blau wrote:\n>\n> > -\t/*\n> > -\t * if we have a HAVES list, but none of those haves is contained\n> > -\t * in the packfile that has a bitmap, we don't have anything to\n> > -\t * optimize here\n> > -\t */\n> > -\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n> > -\t\tgoto cleanup;\n> > +\tuse_boundary_traversal = git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL, -1);\n> > +\tif (use_boundary_traversal < 0) {\n> > +\t\tprepare_repo_settings(revs->repo);\n> > +\t\tuse_boundary_traversal = revs->repo->settings.pack_use_bitmap_boundary_traversal;\n> > +\t}\n> > +\n> > +\tif (!use_boundary_traversal) {\n> > +\t\t/*\n> > +\t\t * if we have a HAVES list, but none of those haves is contained\n> > +\t\t * in the packfile that has a bitmap, we don't have anything to\n> > +\t\t * optimize here\n> > +\t\t */\n> > +\t\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n> > +\t\t\tgoto cleanup;\n> > +\t}\n>\n> I was reading along, nodding my head, until I came across this comment.\n> I recognize that it's moved from an existing place, but this seems very\n> strange and incorrect.\n>\n> Is this implying that if the 'haves' are not in the bitmapped pack, then\n> we _can't_ construct a bitmap representing the objects they can reach?\n>\n> Do we not have the ability to extend the object order beyond the bitmapped\n> pack in-memory in a way that allows us to provide bit positions for the\n> objects not in the bitmapped pack?\n\nIt is a strange heuristic indeed, and I had the same thought as you the\nfirst time I remember encountering this part of the code.\n\nin_bitmapped_pack() asks whether there is at least one of the given set\nof objects which appears in the pack/MIDX corresponding with our bitmap.\nIn other words, this heuristic causes us to bail when none of the\nobjects listed as haves appear in the corresponding pack/MIDX.\n\nStrictly speaking, there isn't a fundamental limitation preventing us\nfrom using the bitmap traversal in cases where none of the tips exist in\nthe bitmapped pack/MIDX. That's what the extended index is for (see\n`bitmap_position_extended()` and `ext_index_add_object()` for more\ndetails).\n\nAFAICT, the heuristic here is another way of saying, \"if none of these\nhaves appear in the corresponding pack or MIDX, my bitmap coverage is\nlikely bad enough that it's not worth trying to construct a full bitmap\non the haves side (and we should fall back to the ordinary object\ntraversal)\".\n\n> I can understand saying \"it might be more expensive to construct a bitmap\n> here, because we need to walk into the bitmapped pack before we have a\n> hope of hitting a bitmap.\" However, that's far from \"we don't have anything\n> to optimize\".\n\nAgreed.\n\n> Something to think about removing in the future, but not a blocker for\n> this series. Getting it out of the way for the boundary-based walk makes\n> even more sense because the commits to check are those in the boundary,\n> not the haves themselves.\n\nYeah. I think that what we do here will end up depending on the\nperformance of the boundary based approach. If it's a clear enough win\nin a majority of cases, I'd just as soon drop the classic traversal (and\nwith it, this heuristic).\n\nBut if we do end up keeping the classic traversal around for a while, I\nabsolutely agree that we should investigate and consider dropping this\noptimization, which I have long-suspected as not being very useful.\n\n> > +test_expect_success 'boundary-based traversal is used when requested' '\n> > +\tgit repack -a -d --write-bitmap-index &&\n> > +\n> > +\tfor argv in \\\n> > +\t\t\"git -c pack.useBitmapBoundaryTraversal=true\" \\\n> > +\t\t\"git -c feature.experimental=true\" \\\n> > +\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 git\"\n> > +\tdo\n> > +\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n> > +\t\t\t--use-bitmap-index second..other 2>perf\" &&\n> > +\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/boundary\\\"\" perf ||\n> > +\t\t\treturn 1\n> > +\tdone &&\n> > +\n> > +\tfor argv in \\\n> > +\t\t\"git -c pack.useBitmapBoundaryTraversal=false\" \\\n> > +\t\t\"git -c feature.experimental=true -c pack.useBitmapBoundaryTraversal=false\" \\\n> > +\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c pack.useBitmapBoundaryTraversal=true\" \\\n> > +\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c feature.experimental=true\"\n>\n> This ordering (GIT_TEST_*=0 overrides config) seems backwards to me, but\n> it doesn't really matter since it's a GIT_TEST_* variable. Thanks for\n> including tests so the order is documented.\n\nNow that you mention it, I think it's backwards too ;-). But I agree\nthat documenting it here is sufficient (and ideally, we don't have to\nlive with this GIT_TEST variable for more than a release or two,\nanyway).\n\n> > +\tdo\n> > +\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n> > +\t\t\t--use-bitmap-index second..other 2>perf\" &&\n> > +\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/classic\\\"\" perf ||\n> > +\t\t\treturn 1\n>\n> nit: you should be able to use 'test_region' here. Probably not worth\n> a re-roll, as everything else looks good to me.\n\nAh, I didn't know of `test_region` before. I'll keep it in mind, thanks!\n\nThanks,\nTaylor\n"},{"id":"477005","messageId":"xmqqmt2b23ut.fsf@gitster.g","threadId":"59648","inReplyTo":"cover.1683567065.git.me@ttaylorr.com","subject":"Re: [PATCH v3 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-05-10T22:55:54Z","receivedAt":"2023-05-10T22:56:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> Here is another small reroll of my series to implement a boundary-based\n> bitmap traversal algorithm that I worked on towards the end of 2021 with\n> Peff.\n>\n> The algorithm is the same as in the last round, though I cleaned up a\n> few things throughout thanks to another very helpful review from Stolee.\n>\n> One significant change from last time is that the new algorithm is\n> opt-in behind feature.experimental, giving users a way to try out the\n> new implementation while still being able to switch back to the\n> known-good traversal in case anything goes wrong.\n\nIt seems that the comments the topic received on the previous round\nhave all been addressed adequately? Does everybody feel comfortable\nmerging this topic to 'next'?\n\nThanks.\n"},{"id":"477006","messageId":"ZFwkXtkAau4MNtKv@nand.local","threadId":"59648","inReplyTo":"xmqqmt2b23ut.fsf@gitster.g","subject":"Re: [PATCH v3 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-05-10T23:10:22Z","receivedAt":"2023-05-10T23:10:29Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, May 10, 2023 at 03:55:54PM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> > Here is another small reroll of my series to implement a boundary-based\n> > bitmap traversal algorithm that I worked on towards the end of 2021 with\n> > Peff.\n> >\n> > The algorithm is the same as in the last round, though I cleaned up a\n> > few things throughout thanks to another very helpful review from Stolee.\n> >\n> > One significant change from last time is that the new algorithm is\n> > opt-in behind feature.experimental, giving users a way to try out the\n> > new implementation while still being able to switch back to the\n> > known-good traversal in case anything goes wrong.\n>\n> It seems that the comments the topic received on the previous round\n> have all been addressed adequately? Does everybody feel comfortable\n> merging this topic to 'next'?\n\nThanks. I agree and think that this is ready to merge down. Even though\nit is changing the traversal algorithm, it should be relatively safe to\nmerge since the new behavior is hidden behind an opt-in configuration\noption.\n\nThanks,\nTaylor\n"},{"id":"477038","messageId":"7c4425fe-c1e9-0410-2b14-a33fcf89b428@github.com","threadId":"59648","inReplyTo":"ZFwkXtkAau4MNtKv@nand.local","subject":"Re: [PATCH v3 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-05-11T15:23:38Z","receivedAt":"2023-05-11T15:23:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/10/2023 7:10 PM, Taylor Blau wrote:\n> On Wed, May 10, 2023 at 03:55:54PM -0700, Junio C Hamano wrote:\n>> Taylor Blau writes:\n>>\n>>> Here is another small reroll of my series to implement a boundary-based\n>>> bitmap traversal algorithm that I worked on towards the end of 2021 with\n>>> Peff.\n>>>\n>>> The algorithm is the same as in the last round, though I cleaned up a\n>>> few things throughout thanks to another very helpful review from Stolee.\n>>>\n>>> One significant change from last time is that the new algorithm is\n>>> opt-in behind feature.experimental, giving users a way to try out the\n>>> new implementation while still being able to switch back to the\n>>> known-good traversal in case anything goes wrong.\n>>\n>> It seems that the comments the topic received on the previous round\n>> have all been addressed adequately? Does everybody feel comfortable\n>> merging this topic to 'next'?\n> \n> Thanks. I agree and think that this is ready to merge down. Even though\n> it is changing the traversal algorithm, it should be relatively safe to\n> merge since the new behavior is hidden behind an opt-in configuration\n> option.\n\nYes, I'm happy with this version.\n\nThanks,\n-Stolee\n"},{"id":"478168","messageId":"cover.1686231639.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1682380788.git.me@ttaylorr.com","subject":"[PATCH v4 0/3] pack-bitmap: boundary-based bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-06-08T16:25:15Z","receivedAt":"2023-06-08T16:25:34Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Here is another copy of the reroll I sent a few weeks ago[1] of the\nboundary-based bitmap traversal topic.\n\nIt is identical to the previous version, except rebased onto the current\ntip of 'master', which thankfully produced no conflicts.\n\nMy plan remains to drop the conditional after a version or two, and\nhopefully having this be in 'master'/'next' sooner rather than later\nwill help us build additional confidence with folks who use those\nbranches as the base for their daily driver.\n\nThanks in advance for your review.\n\n[1]: https://lore.kernel.org/git/cover.1683567065.git.me@ttaylorr.com/\n\nTaylor Blau (3):\n object: add object_array initializer helper function\n pack-bitmap.c: extract `fill_in_bitmap()`\n pack-bitmap.c: use commit boundary during bitmap traversal\n\n Documentation/config/feature.txt | 3 +\n Documentation/config/pack.txt | 17 +++\n ci/run-build-and-tests.sh | 1 +\n object.c | 6 +\n object.h | 2 +\n pack-bitmap.c | 241 ++++++++++++++++++++++++++-----\n pack-bitmap.h | 4 +\n repo-settings.c | 7 +-\n repository.h | 1 +\n t/README | 4 +\n t/t5310-pack-bitmaps.sh | 38 +++++\n 11 files changed, 284 insertions(+), 40 deletions(-)\n\nRange-diff against v3:\n1: c31508ac4a = 1: 1fff820874 object: add object_array initializer helper function\n2: e7b30490da = 2: fa67382e21 pack-bitmap.c: extract `fill_in_bitmap()`\n3: 8a8f41e0c4 = 3: b80d17c938 pack-bitmap.c: use commit boundary during bitmap traversal\n-- \n2.41.0.3.gb80d17c938\n"},{"id":"478169","messageId":"1fff8208746c4c6e0dca7bdfb554cc69e6ead5b4.1686231639.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1686231639.git.me@ttaylorr.com","subject":"[PATCH v4 1/3] object: add object_array initializer helper function","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-06-08T16:25:20Z","receivedAt":"2023-06-08T16:25:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The object_array API has an OBJECT_ARRAY_INIT macro, but lacks a\nfunction to initialize an object_array at a given location in memory.\n\nIntroduce `object_array_init()` to implement such a function.\n\nSigned-off-by: Taylor Blau \n---\n object.c | 6 ++++++\n object.h | 2 ++\n 2 files changed, 8 insertions(+)\n\ndiff --git a/object.c b/object.c\nindex 6d4ef1524d..f1adb458b6 100644\n--- a/object.c\n+++ b/object.c\n@@ -356,6 +356,12 @@ void object_list_free(struct object_list **list)\n */\n static char object_array_slopbuf[1];\n \n+void object_array_init(struct object_array *array)\n+{\n+\tstruct object_array blank = OBJECT_ARRAY_INIT;\n+\tmemcpy(array, &blank, sizeof(*array));\n+}\n+\n void add_object_array_with_path(struct object *obj, const char *name,\n \t\t\t\tstruct object_array *array,\n \t\t\t\tunsigned mode, const char *path)\ndiff --git a/object.h b/object.h\nindex 5871615fee..114d45954d 100644\n--- a/object.h\n+++ b/object.h\n@@ -58,6 +58,8 @@ struct object_array {\n \n #define OBJECT_ARRAY_INIT { 0 }\n \n+void object_array_init(struct object_array *array);\n+\n /*\n * object flag allocation:\n * revision.h: 0---------10 15 23------27\n-- \n2.41.0.3.gb80d17c938\n\n"},{"id":"478170","messageId":"fa67382e21598e920737e2dd0e6ca929be025939.1686231639.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1686231639.git.me@ttaylorr.com","subject":"[PATCH v4 2/3] pack-bitmap.c: extract `fill_in_bitmap()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-06-08T16:25:26Z","receivedAt":"2023-06-08T16:25:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"To prepare for the boundary-based bitmap walk to perform a fill-in\ntraversal using the boundary of either side as the tips, extract routine\nused to perform fill-in traversal by `find_objects()` so that it can be\nused in both places.\n\nSigned-off-by: Taylor Blau \n---\n pack-bitmap.c | 65 ++++++++++++++++++++++++++++-----------------------\n 1 file changed, 36 insertions(+), 29 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 999f962602..c1a9c70061 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1043,6 +1043,40 @@ static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n \treturn 1;\n }\n \n+static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct rev_info *revs,\n+\t\t\t\t struct bitmap *base,\n+\t\t\t\t struct bitmap *seen)\n+{\n+\tstruct include_data incdata;\n+\tstruct bitmap_show_data show_data;\n+\n+\tif (!base)\n+\t\tbase = bitmap_new();\n+\n+\tincdata.bitmap_git = bitmap_git;\n+\tincdata.base = base;\n+\tincdata.seen = seen;\n+\n+\trevs->include_check = should_include;\n+\trevs->include_check_obj = should_include_obj;\n+\trevs->include_check_data = &incdata;\n+\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(_(\"revision walk setup failed\"));\n+\n+\tshow_data.bitmap_git = bitmap_git;\n+\tshow_data.base = base;\n+\n+\ttraverse_commit_list(revs, show_commit, show_object, &show_data);\n+\n+\trevs->include_check = NULL;\n+\trevs->include_check_obj = NULL;\n+\trevs->include_check_data = NULL;\n+\n+\treturn base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1108,35 +1142,8 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk) {\n-\t\tstruct include_data incdata;\n-\t\tstruct bitmap_show_data show_data;\n-\n-\t\tif (!base)\n-\t\t\tbase = bitmap_new();\n-\n-\t\tincdata.bitmap_git = bitmap_git;\n-\t\tincdata.base = base;\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-\t\t\tdie(_(\"revision walk setup failed\"));\n-\n-\t\tshow_data.bitmap_git = bitmap_git;\n-\t\tshow_data.base = base;\n-\n-\t\ttraverse_commit_list(revs,\n-\t\t\t\t show_commit, show_object,\n-\t\t\t\t &show_data);\n-\n-\t\trevs->include_check = NULL;\n-\t\trevs->include_check_obj = NULL;\n-\t\trevs->include_check_data = NULL;\n-\t}\n+\tif (needs_walk)\n+\t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n \n \treturn base;\n }\n-- \n2.41.0.3.gb80d17c938\n\n"},{"id":"478171","messageId":"b80d17c93886beebf14fcc9e1407973b80006b34.1686231639.git.me@ttaylorr.com","threadId":"59648","inReplyTo":"cover.1686231639.git.me@ttaylorr.com","subject":"[PATCH v4 3/3] pack-bitmap.c: use commit boundary during bitmap traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-06-08T16:25:31Z","receivedAt":"2023-06-08T16:25:47Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"When reachability bitmap coverage exists in a repository, Git will use a\ndifferent (and hopefully faster) traversal to compute revision walks.\n\nConsider a set of positive and negative tips (which we'll refer to with\ntheir standard bitmap parlance by \"wants\", and \"haves\"). In order to\nfigure out what objects exist between the tips, the existing traversal\nin `prepare_bitmap_walk()` does something like:\n\n 1. Consider if we can even compute the set of objects with bitmaps,\n and fall back to the usual traversal if we cannot. For example,\n pathspec limiting traversals can't be computed using bitmaps (since\n they don't know which objects are at which paths). The same is true\n of certain kinds of non-trivial object filters.\n\n 2. If we can compute the traversal with bitmaps, partition the\n (dereferenced) tips into two object lists, \"haves\", and \"wants\",\n based on whether or not the objects have the UNINTERESTING flag,\n respectively.\n\n 3. Fall back to the ordinary object traversal if either (a) there are\n more than zero haves, none of which are in the bitmapped pack or\n MIDX, or (b) there are no wants.\n\n 4. Construct a reachability bitmap for the \"haves\" side by walking\n from the revision tips down to any existing bitmaps, OR-ing in any\n bitmaps as they are found.\n\n 5. Then do the same for the \"wants\" side, stopping at any objects that\n appear in the \"haves\" bitmap.\n\n 6. Filter the results if any object filter (that can be easily\n computed with bitmaps alone) was given, and then return back to the\n caller.\n\nWhen there is good bitmap coverage relative to the traversal tips, this\nwalk is often significantly faster than an ordinary object traversal\nbecause it can visit far fewer objects.\n\nBut in certain cases, it can be significantly *slower* than the usual\nobject traversal. Why? Because we need to compute complete bitmaps on\neither side of the walk. If either one (or both) of the sides require\nwalking many (or all!) objects before they get to an existing bitmap,\nthe extra bitmap machinery is mostly or all overhead.\n\nOne of the benefits, however, is that even if the walk is slower, bitmap\ntraversals are guaranteed to provide an *exact* answer. Unlike the\ntraditional object traversal algorithm, which can over-count the results\nby not opening trees for older commits, the bitmap walk builds an exact\nreachability bitmap for either side, meaning the results are never\nover-counted.\n\nBut producing non-exact results is OK for our traversal here (both in\nthe bitmap case and not), as long as the results are over-counted, not\nunder.\n\nRelaxing the bitmap traversal to allow it to produce over-counted\nresults gives us the opportunity to make some significant improvements.\nInstead of the above, the new algorithm only has to walk from the\n*boundary* down to the nearest bitmap, instead of from each of the\nUNINTERESTING tips.\n\nThe boundary-based approach still has degenerate cases, but we'll show\nin a moment that it is often a significant improvement.\n\nThe new algorithm works as follows:\n\n 1. Build a (partial) bitmap of the haves side by first OR-ing any\n bitmap(s) that already exist for UNINTERESTING commits between the\n haves and the boundary.\n\n 2. For each commit along the boundary, add it as a fill-in traversal\n tip (where the traversal terminates once an existing bitmap is\n found), and perform fill-in traversal.\n\n 3. Build up a complete bitmap of the wants side as usual, stopping any\n time we intersect the (partial) haves side.\n\n 4. Return the results.\n\nAnd is more-or-less equivalent to using the *old* algorithm with this\ninvocation:\n\n $ git rev-list --objects --use-bitmap-index $WANTS --not \\\n $(git rev-list --objects --boundary $WANTS --not $HAVES |\n perl -lne 'print $1 if /^-(.*)/')\n\nThe new result performs significantly better in many cases, particularly\nwhen the distance from the boundary commit(s) to an existing bitmap is\nshorter than the distance from (all of) the have tips to the nearest\nbitmapped commit.\n\nNote that when using the old bitmap traversal algorithm, the results can\nbe *slower* than without bitmaps! Under the new algorithm, the result is\ncomputed faster with bitmaps than without (at the cost of over-counting\nthe true number of objects in a similar fashion as the non-bitmap\ntraversal):\n\n # (Computing the number of tagged objects not on any branches\n # without bitmaps).\n $ time git rev-list --count --objects --tags --not --branches\n 20\n\n real\t0m1.388s\n user\t0m1.092s\n sys\t0m0.296s\n\n # (Computing the same query using the old bitmap traversal).\n $ time git rev-list --count --objects --tags --not --branches --use-bitmap-index\n 19\n\n real\t0m22.709s\n user\t0m21.628s\n sys\t0m1.076s\n\n # (this commit)\n $ time git.compile rev-list --count --objects --tags --not --branches --use-bitmap-index\n 19\n\n real\t0m1.518s\n user\t0m1.234s\n sys\t0m0.284s\n\nThe new algorithm is still slower than not using bitmaps at all, but it\nis nearly a 15-fold improvement over the existing traversal.\n\nIn a more realistic setting (using my local copy of git.git), I can\nobserve a similar (if more modest) speed-up:\n\n $ argv=\"--count --objects --branches --not --tags\"\n hyperfine \\\n -n 'no bitmaps' \"git.compile rev-list $argv\" \\\n -n 'existing traversal' \"git.compile rev-list --use-bitmap-index $argv\" \\\n -n 'boundary traversal' \"git.compile -c pack.useBitmapBoundaryTraversal=true rev-list --use-bitmap-index $argv\"\n Benchmark 1: no bitmaps\n Time (mean ± σ): 124.6 ms ± 2.1 ms [User: 103.7 ms, System: 20.8 ms]\n Range (min … max): 122.6 ms … 133.1 ms 22 runs\n\n Benchmark 2: existing traversal\n Time (mean ± σ): 368.6 ms ± 3.0 ms [User: 325.3 ms, System: 43.1 ms]\n Range (min … max): 365.1 ms … 374.8 ms 10 runs\n\n Benchmark 3: boundary traversal\n Time (mean ± σ): 167.6 ms ± 0.9 ms [User: 139.5 ms, System: 27.9 ms]\n Range (min … max): 166.1 ms … 169.2 ms 17 runs\n\n Summary\n 'no bitmaps' ran\n 1.34 ± 0.02 times faster than 'boundary traversal'\n 2.96 ± 0.05 times faster than 'existing traversal'\n\nHere, the new algorithm is also still slower than not using bitmaps, but\nrepresents a more than 2-fold improvement over the existing traversal in\na more modest example.\n\nSince this algorithm was originally written (nearly a year and a half\nago, at the time of writing), the bitmap lookup table shipped, making\nthe new algorithm's result more competitive. A few other future\ndirections for improving bitmap traversal times beyond not using bitmaps\nat all:\n\n - Decrease the cost to decompress and OR together many bitmaps\n together (particularly when enumerating the uninteresting side of\n the walk). Here we could explore more efficient bitmap storage\n techniques, like Roaring+Run and/or use SIMD instructions to speed\n up ORing them together.\n\n - Store pseudo-merge bitmaps, which could allow us to OR together\n fewer \"summary\" bitmaps (which would also help with the above).\n\nHelped-by: Jeff King \nHelped-by: Derrick Stolee \nSigned-off-by: Taylor Blau \n---\n Documentation/config/feature.txt | 3 +\n Documentation/config/pack.txt | 17 +++\n ci/run-build-and-tests.sh | 1 +\n pack-bitmap.c | 182 ++++++++++++++++++++++++++++---\n pack-bitmap.h | 4 +\n repo-settings.c | 7 +-\n repository.h | 1 +\n t/README | 4 +\n t/t5310-pack-bitmaps.sh | 38 +++++++\n 9 files changed, 243 insertions(+), 14 deletions(-)\n\ndiff --git a/Documentation/config/feature.txt b/Documentation/config/feature.txt\nindex 17b4d39f89..bf9546fca4 100644\n--- a/Documentation/config/feature.txt\n+++ b/Documentation/config/feature.txt\n@@ -14,6 +14,9 @@ feature.experimental::\n +\n * `fetch.negotiationAlgorithm=skipping` may improve fetch negotiation times by\n skipping more commits at a time, reducing the number of round trips.\n++\n+* `pack.useBitmapBoundaryTraversal=true` may improve bitmap traversal times by\n+walking fewer objects.\n \n feature.manyFiles::\n \tEnable config options that optimize for repos with many files in the\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex d4c7c9d4e4..3748136d14 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -123,6 +123,23 @@ pack.useBitmaps::\n \ttrue. You should not generally need to turn this off unless\n \tyou are debugging pack bitmaps.\n \n+pack.useBitmapBoundaryTraversal::\n+\tWhen true, Git will use an experimental algorithm for computing\n+\treachability queries with bitmaps. Instead of building up\n+\tcomplete bitmaps for all of the negated tips and then OR-ing\n+\tthem together, consider negated tips with existing bitmaps as\n+\tadditive (i.e. OR-ing them into the result if they exist,\n+\tignoring them otherwise), and build up a bitmap at the boundary\n+\tinstead.\n++\n+When using this algorithm, Git may include too many objects as a result\n+of not opening up trees belonging to certain UNINTERESTING commits. This\n+inexactness matches the non-bitmap traversal algorithm.\n++\n+In many cases, this can provide a speed-up over the exact algorithm,\n+particularly when there is poor bitmap coverage of the negated side of\n+the query.\n+\n pack.useSparse::\n \tWhen true, git will default to using the '--sparse' option in\n \t'git pack-objects' when the '--revs' option is present. This\ndiff --git a/ci/run-build-and-tests.sh b/ci/run-build-and-tests.sh\nindex a18b13a41d..2528f25e31 100755\n--- a/ci/run-build-and-tests.sh\n+++ b/ci/run-build-and-tests.sh\n@@ -29,6 +29,7 @@ linux-TEST-vars)\n \texport GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=master\n \texport GIT_TEST_NO_WRITE_REV_INDEX=1\n \texport GIT_TEST_CHECKOUT_WORKERS=2\n+\texport GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n \t;;\n linux-clang)\n \texport GIT_TEST_DEFAULT_HASH=sha1\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex c1a9c70061..894bff02c5 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1077,6 +1077,126 @@ static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,\n \treturn base;\n }\n \n+struct bitmap_boundary_cb {\n+\tstruct bitmap_index *bitmap_git;\n+\tstruct bitmap *base;\n+\n+\tstruct object_array boundary;\n+};\n+\n+static void show_boundary_commit(struct commit *commit, void *_data)\n+{\n+\tstruct bitmap_boundary_cb *data = _data;\n+\n+\tif (commit->object.flags & BOUNDARY)\n+\t\tadd_object_array(&commit->object, \"\", &data->boundary);\n+\n+\tif (commit->object.flags & UNINTERESTING) {\n+\t\tif (bitmap_walk_contains(data->bitmap_git, data->base,\n+\t\t\t\t\t &commit->object.oid))\n+\t\t\treturn;\n+\n+\t\tadd_commit_to_bitmap(data->bitmap_git, &data->base, commit);\n+\t}\n+}\n+\n+static void show_boundary_object(struct object *object,\n+\t\t\t\t const char *name, void *data)\n+{\n+\tBUG(\"should not be called\");\n+}\n+\n+static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,\n+\t\t\t\t\t struct rev_info *revs,\n+\t\t\t\t\t struct object_list *roots)\n+{\n+\tstruct bitmap_boundary_cb cb;\n+\tstruct object_list *root;\n+\tunsigned int i;\n+\tunsigned int tmp_blobs, tmp_trees, tmp_tags;\n+\tint any_missing = 0;\n+\n+\tcb.bitmap_git = bitmap_git;\n+\tcb.base = bitmap_new();\n+\tobject_array_init(&cb.boundary);\n+\n+\trevs->ignore_missing_links = 1;\n+\n+\t/*\n+\t * OR in any existing reachability bitmaps among `roots` into\n+\t * `cb.base`.\n+\t */\n+\tfor (root = roots; root; root = root->next) {\n+\t\tstruct object *object = root->item;\n+\t\tif (object->type != OBJ_COMMIT ||\n+\t\t bitmap_walk_contains(bitmap_git, cb.base, &object->oid))\n+\t\t\tcontinue;\n+\n+\t\tif (add_commit_to_bitmap(bitmap_git, &cb.base,\n+\t\t\t\t\t (struct commit *)object))\n+\t\t\tcontinue;\n+\n+\t\tany_missing = 1;\n+\t}\n+\n+\tif (!any_missing)\n+\t\tgoto cleanup;\n+\n+\ttmp_blobs = revs->blob_objects;\n+\ttmp_trees = revs->tree_objects;\n+\ttmp_tags = revs->blob_objects;\n+\trevs->blob_objects = 0;\n+\trevs->tree_objects = 0;\n+\trevs->tag_objects = 0;\n+\n+\t/*\n+\t * We didn't have complete coverage of the roots. First setup a\n+\t * revision walk to (a) OR in any bitmaps that are UNINTERESTING\n+\t * between the tips and boundary, and (b) record the boundary.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"revision walk setup failed\");\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-prepare\", the_repository);\n+\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\trevs->boundary = 1;\n+\ttraverse_commit_list_filtered(revs,\n+\t\t\t\t show_boundary_commit,\n+\t\t\t\t show_boundary_object,\n+\t\t\t\t &cb, NULL);\n+\trevs->boundary = 0;\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-traverse\", the_repository);\n+\n+\trevs->blob_objects = tmp_blobs;\n+\trevs->tree_objects = tmp_trees;\n+\trevs->tag_objects = tmp_tags;\n+\n+\treset_revision_walk();\n+\tclear_object_flags(UNINTERESTING);\n+\n+\t/*\n+\t * Then add the boundary commit(s) as fill-in traversal tips.\n+\t */\n+\ttrace2_region_enter(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\tfor (i = 0; i < cb.boundary.nr; i++) {\n+\t\tstruct object *obj = cb.boundary.objects[i].item;\n+\t\tif (bitmap_walk_contains(bitmap_git, cb.base, &obj->oid))\n+\t\t\tobj->flags |= SEEN;\n+\t\telse\n+\t\t\tadd_pending_object(revs, obj, \"\");\n+\t}\n+\tif (revs->pending.nr)\n+\t\tcb.base = fill_in_bitmap(bitmap_git, revs, cb.base, NULL);\n+\ttrace2_region_leave(\"pack-bitmap\", \"boundary-fill-in\", the_repository);\n+\n+cleanup:\n+\tobject_array_clear(&cb.boundary);\n+\trevs->ignore_missing_links = 0;\n+\n+\treturn cb.base;\n+}\n+\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t struct object_list *roots,\n@@ -1142,8 +1262,21 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t}\n \t}\n \n-\tif (needs_walk)\n+\tif (needs_walk) {\n+\t\t/*\n+\t\t * This fill-in traversal may walk over some objects\n+\t\t * again, since we have already traversed in order to\n+\t\t * find the boundary.\n+\t\t *\n+\t\t * But this extra walk should be extremely cheap, since\n+\t\t * all commit objects are loaded into memory, and\n+\t\t * because we skip walking to parents that are\n+\t\t * UNINTERESTING, since it will be marked in the haves\n+\t\t * bitmap already (or it has an on-disk bitmap, since\n+\t\t * OR-ing it in covers all of its ancestors).\n+\t\t */\n \t\tbase = fill_in_bitmap(bitmap_git, revs, base, seen);\n+\t}\n \n \treturn base;\n }\n@@ -1535,6 +1668,7 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\t\t\t int filter_provided_objects)\n {\n \tunsigned int i;\n+\tint use_boundary_traversal;\n \n \tstruct object_list *wants = NULL;\n \tstruct object_list *haves = NULL;\n@@ -1585,13 +1719,21 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\tobject_list_insert(object, &wants);\n \t}\n \n-\t/*\n-\t * if we have a HAVES list, but none of those haves is contained\n-\t * in the packfile that has a bitmap, we don't have anything to\n-\t * optimize here\n-\t */\n-\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n-\t\tgoto cleanup;\n+\tuse_boundary_traversal = git_env_bool(GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL, -1);\n+\tif (use_boundary_traversal < 0) {\n+\t\tprepare_repo_settings(revs->repo);\n+\t\tuse_boundary_traversal = revs->repo->settings.pack_use_bitmap_boundary_traversal;\n+\t}\n+\n+\tif (!use_boundary_traversal) {\n+\t\t/*\n+\t\t * if we have a HAVES list, but none of those haves is contained\n+\t\t * in the packfile that has a bitmap, we don't have anything to\n+\t\t * optimize here\n+\t\t */\n+\t\tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n+\t\t\tgoto cleanup;\n+\t}\n \n \t/* if we don't want anything, we're done here */\n \tif (!wants)\n@@ -1605,18 +1747,32 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \tif (load_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n \n-\tobject_array_clear(&revs->pending);\n+\tif (!use_boundary_traversal)\n+\t\tobject_array_clear(&revs->pending);\n \n \tif (haves) {\n-\t\trevs->ignore_missing_links = 1;\n-\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n-\t\treset_revision_walk();\n-\t\trevs->ignore_missing_links = 0;\n+\t\tif (use_boundary_traversal) {\n+\t\t\ttrace2_region_enter(\"pack-bitmap\", \"haves/boundary\", the_repository);\n+\t\t\thaves_bitmap = find_boundary_objects(bitmap_git, revs, haves);\n+\t\t\ttrace2_region_leave(\"pack-bitmap\", \"haves/boundary\", the_repository);\n+\t\t} else {\n+\t\t\ttrace2_region_enter(\"pack-bitmap\", \"haves/classic\", the_repository);\n+\t\t\trevs->ignore_missing_links = 1;\n+\t\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n+\t\t\treset_revision_walk();\n+\t\t\trevs->ignore_missing_links = 0;\n+\t\t\ttrace2_region_leave(\"pack-bitmap\", \"haves/classic\", the_repository);\n+\t\t}\n \n \t\tif (!haves_bitmap)\n \t\t\tBUG(\"failed to perform bitmap walk\");\n \t}\n \n+\tif (use_boundary_traversal) {\n+\t\tobject_array_clear(&revs->pending);\n+\t\treset_revision_walk();\n+\t}\n+\n \twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n \n \tif (!wants_bitmap)\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 84591f041b..5273a6a019 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -62,6 +62,10 @@ void traverse_bitmap_commit_list(struct bitmap_index *,\n void test_bitmap_walk(struct rev_info *revs);\n int test_bitmap_commits(struct repository *r);\n int test_bitmap_hashes(struct repository *r);\n+\n+#define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \\\n+\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\"\n+\n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\t\t\t int filter_provided_objects);\n uint32_t midx_preferred_pack(struct bitmap_index *bitmap_git);\ndiff --git a/repo-settings.c b/repo-settings.c\nindex d220c5dd9f..7b566d729d 100644\n--- a/repo-settings.c\n+++ b/repo-settings.c\n@@ -41,8 +41,10 @@ void prepare_repo_settings(struct repository *r)\n \trepo_cfg_bool(r, \"feature.experimental\", &experimental, 0);\n \n \t/* Defaults modified by feature.* */\n-\tif (experimental)\n+\tif (experimental) {\n \t\tr->settings.fetch_negotiation_algorithm = FETCH_NEGOTIATION_SKIPPING;\n+\t\tr->settings.pack_use_bitmap_boundary_traversal = 1;\n+\t}\n \tif (manyfiles) {\n \t\tr->settings.index_version = 4;\n \t\tr->settings.index_skip_hash = 1;\n@@ -62,6 +64,9 @@ void prepare_repo_settings(struct repository *r)\n \trepo_cfg_bool(r, \"index.sparse\", &r->settings.sparse_index, 0);\n \trepo_cfg_bool(r, \"index.skiphash\", &r->settings.index_skip_hash, r->settings.index_skip_hash);\n \trepo_cfg_bool(r, \"pack.readreverseindex\", &r->settings.pack_read_reverse_index, 1);\n+\trepo_cfg_bool(r, \"pack.usebitmapboundarytraversal\",\n+\t\t &r->settings.pack_use_bitmap_boundary_traversal,\n+\t\t r->settings.pack_use_bitmap_boundary_traversal);\n \n \t/*\n \t * The GIT_TEST_MULTI_PACK_INDEX variable is special in that\ndiff --git a/repository.h b/repository.h\nindex 1a13ff2867..c42f7ab6bd 100644\n--- a/repository.h\n+++ b/repository.h\n@@ -37,6 +37,7 @@ struct repo_settings {\n \tint command_requires_full_index;\n \tint sparse_index;\n \tint pack_read_reverse_index;\n+\tint pack_use_bitmap_boundary_traversal;\n \n \tstruct fsmonitor_settings *fsmonitor; /* lazily loaded */\n \ndiff --git a/t/README b/t/README\nindex bdfac4cceb..b71a065e4a 100644\n--- a/t/README\n+++ b/t/README\n@@ -442,6 +442,10 @@ GIT_TEST_INDEX_VERSION= exercises the index read/write code path\n for the index version specified. Can be set to any valid version\n (currently 2, 3, or 4).\n \n+GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL= if enabled will\n+use the boundary-based bitmap traversal algorithm. See the documentation\n+of `pack.useBitmapBoundaryTraversal` for more details.\n+\n GIT_TEST_PACK_SPARSE= if disabled will default the pack-objects\n builtin to use the non-sparse object walk. This can still be overridden by\n the --sparse command-line argument.\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 526a5a506e..78c1c6c923 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -9,6 +9,10 @@ test_description='exercise basic bitmap functionality'\n # their place.\n GIT_TEST_MULTI_PACK_INDEX_WRITE_BITMAP=0\n \n+# Likewise, allow individual tests to control whether or not they use\n+# the boundary-based traversal.\n+sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n+\n objpath () {\n \techo \".git/objects/$(echo \"$1\" | sed -e 's|\\(..\\)|\\1/|')\"\n }\n@@ -457,6 +461,13 @@ test_bitmap_cases () {\n \n test_bitmap_cases\n \n+GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1\n+export GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n+\n+test_bitmap_cases\n+\n+sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL\n+\n test_expect_success 'incremental repack fails when bitmaps are requested' '\n \ttest_commit more-1 &&\n \ttest_must_fail git repack -d 2>err &&\n@@ -468,6 +479,33 @@ test_expect_success 'incremental repack can disable bitmaps' '\n \tgit repack -d --no-write-bitmap-index\n '\n \n+test_expect_success 'boundary-based traversal is used when requested' '\n+\tgit repack -a -d --write-bitmap-index &&\n+\n+\tfor argv in \\\n+\t\t\"git -c pack.useBitmapBoundaryTraversal=true\" \\\n+\t\t\"git -c feature.experimental=true\" \\\n+\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=1 git\"\n+\tdo\n+\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n+\t\t\t--use-bitmap-index second..other 2>perf\" &&\n+\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/boundary\\\"\" perf ||\n+\t\t\treturn 1\n+\tdone &&\n+\n+\tfor argv in \\\n+\t\t\"git -c pack.useBitmapBoundaryTraversal=false\" \\\n+\t\t\"git -c feature.experimental=true -c pack.useBitmapBoundaryTraversal=false\" \\\n+\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c pack.useBitmapBoundaryTraversal=true\" \\\n+\t\t\"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL=0 git -c feature.experimental=true\"\n+\tdo\n+\t\teval \"GIT_TRACE2_EVENT=1 $argv rev-list --objects \\\n+\t\t\t--use-bitmap-index second..other 2>perf\" &&\n+\t\tgrep \"\\\"region_enter\\\".*\\\"label\\\":\\\"haves/classic\\\"\" perf ||\n+\t\t\treturn 1\n+\tdone\n+'\n+\n test_bitmap_cases \"pack.writeBitmapLookupTable\"\n \n test_expect_success 'verify writing bitmap lookup table when enabled' '\n-- \n2.41.0.3.gb80d17c938\n"}]}