{"thread":{"id":"50501","subject":"[PATCH 0/3] some prune optimizations","startedAt":"2019-02-14T04:32:34Z","lastAt":"2019-05-24T13:41:46Z","messageCount":57,"participants":["Jeff King","Eric Sunshine","Eric Wong","Ævar Arnfjörð Bjarmason","SZEDER Gábor","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"369275","messageId":"20190214043127.GA19019@sigill.intra.peff.net","threadId":"50501","inReplyTo":null,"subject":"[PATCH 0/3] some prune optimizations","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-02-14T04:31:28Z","receivedAt":"2019-02-14T04:32:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Here are two optimizations for git-prune that we've been running at\nGitHub for ages. No particular reason to share them now; they just\nfinally floated to the top of my todo pile. Do note that I rebased and\npolished them (and the third one is brand new), so the concepts are\nproven, but it's possible I introduced a new bug. ;)\n\n [1/3]: prune: lazily perform reachability traversal\n [2/3]: prune: use bitmaps for reachability traversal\n [3/3]: prune: check SEEN flag for reachability\n\n builtin/prune.c | 44 +++++++++++++++++++++++++++++++------------\n reachable.c | 42 +++++++++++++++++++++++++++++++++++++++++\n t/perf/p5304-prune.sh | 35 ++++++++++++++++++++++++++++++++++\n t/t5304-prune.sh | 12 ++++++++++++\n 4 files changed, 121 insertions(+), 12 deletions(-)\n create mode 100755 t/perf/p5304-prune.sh\n\n-Peff\n"},{"id":"369276","messageId":"20190214043522.GA19183@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190214043127.GA19019@sigill.intra.peff.net","subject":"[PATCH 1/3] prune: lazily perform reachability traversal","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-02-14T04:35:22Z","receivedAt":"2019-02-14T04:35:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The general strategy of \"git prune\" is to do a full reachability walk,\nthen for each loose object see if we found it in our walk. But if we\ndon't have any loose objects, we don't need to do the expensive walk in\nthe first place.\n\nThis patch postpones that walk until the first time we need to see its\nresults.\n\nNote that this is really a specific case of a more general optimization,\nwhich is that we could traverse only far enough to find the object under\nconsideration (i.e., stop the traversal when we find it, then pick up\nagain when asked about the next object, etc). That could save us in some\ninstances from having to do a full walk. But it's actually a bit tricky\nto do with our traversal code, and you'd need to do a full walk anyway\nif you have even a single unreachable object (which you generally do, if\nany objects are actually left after running git-repack).\n\nSo in practice this lazy-load of the full walk catches one easy but\ncommon case (i.e., you've just repacked via git-gc, and there's nothing\nunreachable).\n\nThe perf script is fairly contrived, but it does show off the\nimprovement:\n\n Test HEAD^ HEAD\n -------------------------------------------------------------------------\n 5304.4: prune with no objects 3.66(3.60+0.05) 0.00(0.00+0.00) -100.0%\n\nand would let us know if we accidentally regress this optimization.\n\nNote also that we need to take special care with prune_shallow(), which\nrelies on us having performed the traversal. So this optimization can\nonly kick in for a non-shallow repository. Since this is easy to get\nwrong and is not covered by existing tests, let's add an extra test to\nt5304 that covers this case explicitly.\n\nSigned-off-by: Jeff King \n---\nThe diff looks nice with --color-moved. I wish there was a way to\ncommunicate that information in a plaintext email.\n\n builtin/prune.c | 43 ++++++++++++++++++++++++++++++++-----------\n t/perf/p5304-prune.sh | 24 ++++++++++++++++++++++++\n t/t5304-prune.sh | 12 ++++++++++++\n 3 files changed, 68 insertions(+), 11 deletions(-)\n create mode 100755 t/perf/p5304-prune.sh\n\ndiff --git a/builtin/prune.c b/builtin/prune.c\nindex 1ec9ddd751..04b6573945 100644\n--- a/builtin/prune.c\n+++ b/builtin/prune.c\n@@ -31,16 +31,40 @@ static int prune_tmp_file(const char *fullpath)\n \treturn 0;\n }\n \n-static int prune_object(const struct object_id *oid, const char *fullpath,\n-\t\t\tvoid *data)\n+static void perform_reachability_traversal(struct rev_info *revs)\n {\n-\tstruct stat st;\n+\tstatic int initialized;\n+\tstruct progress *progress = NULL;\n+\n+\tif (initialized)\n+\t\treturn;\n+\n+\tif (show_progress)\n+\t\tprogress = start_delayed_progress(_(\"Checking connectivity\"), 0);\n+\tmark_reachable_objects(revs, 1, expire, progress);\n+\tstop_progress(&progress);\n+\tinitialized = 1;\n+}\n+\n+static int is_object_reachable(const struct object_id *oid,\n+\t\t\t struct rev_info *revs)\n+{\n+\tperform_reachability_traversal(revs);\n \n \t/*\n \t * Do we know about this object?\n \t * It must have been reachable\n \t */\n-\tif (lookup_object(the_repository, oid->hash))\n+\treturn !!lookup_object(the_repository, oid->hash);\n+}\n+\n+static int prune_object(const struct object_id *oid, const char *fullpath,\n+\t\t\tvoid *data)\n+{\n+\tstruct rev_info *revs = data;\n+\tstruct stat st;\n+\n+\tif (is_object_reachable(oid, revs))\n \t\treturn 0;\n \n \tif (lstat(fullpath, &st)) {\n@@ -102,7 +126,6 @@ static void remove_temporary_files(const char *path)\n int cmd_prune(int argc, const char **argv, const char *prefix)\n {\n \tstruct rev_info revs;\n-\tstruct progress *progress = NULL;\n \tint exclude_promisor_objects = 0;\n \tconst struct option options[] = {\n \t\tOPT__DRY_RUN(&show_only, N_(\"do not remove, show only\")),\n@@ -142,17 +165,13 @@ int cmd_prune(int argc, const char **argv, const char *prefix)\n \n \tif (show_progress == -1)\n \t\tshow_progress = isatty(2);\n-\tif (show_progress)\n-\t\tprogress = start_delayed_progress(_(\"Checking connectivity\"), 0);\n \tif (exclude_promisor_objects) {\n \t\tfetch_if_missing = 0;\n \t\trevs.exclude_promisor_objects = 1;\n \t}\n \n-\tmark_reachable_objects(&revs, 1, expire, progress);\n-\tstop_progress(&progress);\n \tfor_each_loose_file_in_objdir(get_object_directory(), prune_object,\n-\t\t\t\t prune_cruft, prune_subdir, NULL);\n+\t\t\t\t prune_cruft, prune_subdir, &revs);\n \n \tprune_packed_objects(show_only ? PRUNE_PACKED_DRY_RUN : 0);\n \tremove_temporary_files(get_object_directory());\n@@ -160,8 +179,10 @@ int cmd_prune(int argc, const char **argv, const char *prefix)\n \tremove_temporary_files(s);\n \tfree(s);\n \n-\tif (is_repository_shallow(the_repository))\n+\tif (is_repository_shallow(the_repository)) {\n+\t\tperform_reachability_traversal(&revs);\n \t\tprune_shallow(show_only ? PRUNE_SHOW_ONLY : 0);\n+\t}\n \n \treturn 0;\n }\ndiff --git a/t/perf/p5304-prune.sh b/t/perf/p5304-prune.sh\nnew file mode 100755\nindex 0000000000..3c852084eb\n--- /dev/null\n+++ b/t/perf/p5304-prune.sh\n@@ -0,0 +1,24 @@\n+#!/bin/sh\n+\n+test_description='performance tests of prune'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+test_expect_success 'remove reachable loose objects' '\n+\tgit repack -ad\n+'\n+\n+test_expect_success 'remove unreachable loose objects' '\n+\tgit prune\n+'\n+\n+test_expect_success 'confirm there are no loose objects' '\n+\tgit count-objects | grep ^0\n+'\n+\n+test_perf 'prune with no objects' '\n+\tgit prune\n+'\n+\n+test_done\ndiff --git a/t/t5304-prune.sh b/t/t5304-prune.sh\nindex 270da21ac3..2c19a790c1 100755\n--- a/t/t5304-prune.sh\n+++ b/t/t5304-prune.sh\n@@ -274,6 +274,18 @@ test_expect_success 'prune .git/shallow' '\n \ttest_path_is_missing .git/shallow\n '\n \n+test_expect_success 'prune .git/shallow when there are no loose objects' '\n+\tSHA1=$(echo hi|git commit-tree HEAD^{tree}) &&\n+\techo $SHA1 >.git/shallow &&\n+\tgit update-ref refs/heads/shallow-tip $SHA1 &&\n+\tgit repack -ad &&\n+\t# verify assumption that all loose objects are gone\n+\tgit count-objects | grep ^0 &&\n+\tgit prune &&\n+\techo $SHA1 >expect &&\n+\ttest_cmp expect .git/shallow\n+'\n+\n test_expect_success 'prune: handle alternate object database' '\n \ttest_create_repo A &&\n \tgit -C A commit --allow-empty -m \"initial commit\" &&\n-- \n2.21.0.rc0.586.gffba1126a0\n\n"},{"id":"369277","messageId":"20190214043743.GB19183@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190214043127.GA19019@sigill.intra.peff.net","subject":"[PATCH 2/3] prune: use bitmaps for reachability traversal","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-02-14T04:37:43Z","receivedAt":"2019-02-14T04:37:46Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Pruning generally has to traverse the whole commit graph in order to\nsee which objects are reachable. This is the exact problem that\nreachability bitmaps were meant to solve, so let's use them (if they're\navailable, of course).\n\nHere are timings on git.git:\n\n Test HEAD^ HEAD\n ------------------------------------------------------------------------\n 5304.6: prune with bitmaps 3.65(3.56+0.09) 1.01(0.92+0.08) -72.3%\n\nAnd on linux.git:\n\n Test HEAD^ HEAD\n --------------------------------------------------------------------------\n 5304.6: prune with bitmaps 35.05(34.79+0.23) 3.00(2.78+0.21) -91.4%\n\nThe tests show a pretty optimal case, as we'll have just repacked and\nshould have pretty good coverage of all refs with our bitmaps. But\nthat's actually pretty realistic: normally prune is run via \"gc\" right\nafter repacking.\n\nA few notes on the implementation:\n\n - the change is actually in reachable.c, so it would improve\n reachability traversals by \"reflog expire --stale-fix\", as well.\n Those aren't performed regularly, though (a normal \"git gc\" doesn't\n use --stale-fix), so they're not really worth measuring. There's a\n low chance of regressing that caller, since the use of bitmaps is\n totally transparent from the caller's perspective.\n\n - The bitmap case could actually get away without creating a \"struct\n object\", and instead the caller could just look up each object id in\n the bitmap result. However, this would be a marginal improvement in\n runtime, and it would make the callers much more complicated. They'd\n have to handle both the bitmap and non-bitmap cases separately, and\n in the case of git-prune, we'd also have to tweak prune_shallow(),\n which relies on our SEEN flags.\n\n - Because we do create real object structs, we go through a few\n contortions to create ones of the right type. This isn't strictly\n necessary (lookup_unknown_object() would suffice), but it's more\n memory efficient to use the correct types, since we already know\n them.\n\nSigned-off-by: Jeff King \n---\n reachable.c | 42 ++++++++++++++++++++++++++++++++++++++++++\n t/perf/p5304-prune.sh | 11 +++++++++++\n 2 files changed, 53 insertions(+)\n\ndiff --git a/reachable.c b/reachable.c\nindex 6e9b810d2a..0d00a91de4 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -12,6 +12,7 @@\n #include \"packfile.h\"\n #include \"worktree.h\"\n #include \"object-store.h\"\n+#include \"pack-bitmap.h\"\n \n struct connectivity_progress {\n \tstruct progress *progress;\n@@ -158,10 +159,44 @@ int add_unseen_recent_objects_to_traversal(struct rev_info *revs,\n \t\t\t\t FOR_EACH_OBJECT_LOCAL_ONLY);\n }\n \n+static void *lookup_object_by_type(struct repository *r,\n+\t\t\t\t const struct object_id *oid,\n+\t\t\t\t enum object_type type)\n+{\n+\tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\t\treturn lookup_commit(r, oid);\n+\tcase OBJ_TREE:\n+\t\treturn lookup_tree(r, oid);\n+\tcase OBJ_TAG:\n+\t\treturn lookup_tag(r, oid);\n+\tcase OBJ_BLOB:\n+\t\treturn lookup_blob(r, oid);\n+\tdefault:\n+\t\tdie(\"BUG: unknown object type %d\", type);\n+\t}\n+}\n+\n+static int mark_object_seen(const struct object_id *oid,\n+\t\t\t enum object_type type,\n+\t\t\t int exclude,\n+\t\t\t uint32_t name_hash,\n+\t\t\t struct packed_git *found_pack,\n+\t\t\t off_t found_offset)\n+{\n+\tstruct object *obj = lookup_object_by_type(the_repository, oid, type);\n+\tif (!obj)\n+\t\tdie(\"unable to create object '%s'\", oid_to_hex(oid));\n+\n+\tobj->flags |= SEEN;\n+\treturn 0;\n+}\n+\n void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n \t\t\t timestamp_t mark_recent, struct progress *progress)\n {\n \tstruct connectivity_progress cp;\n+\tstruct bitmap_index *bitmap_git;\n \n \t/*\n \t * Set up revision parsing, and mark us as being interested\n@@ -188,6 +223,13 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n \tcp.progress = progress;\n \tcp.count = 0;\n \n+\tbitmap_git = prepare_bitmap_walk(revs);\n+\tif (bitmap_git) {\n+\t\ttraverse_bitmap_commit_list(bitmap_git, mark_object_seen);\n+\t\tfree_bitmap_index(bitmap_git);\n+\t\treturn;\n+\t}\n+\n \t/*\n \t * Set up the revision walk - this will move all commits\n \t * from the pending list to the commit walking list.\ndiff --git a/t/perf/p5304-prune.sh b/t/perf/p5304-prune.sh\nindex 3c852084eb..83baedb8a4 100755\n--- a/t/perf/p5304-prune.sh\n+++ b/t/perf/p5304-prune.sh\n@@ -21,4 +21,15 @@ test_perf 'prune with no objects' '\n \tgit prune\n '\n \n+test_expect_success 'repack with bitmaps' '\n+\tgit repack -adb\n+'\n+\n+# We have to create the object in each trial run, since otherwise\n+# runs after the first see no object and just skip the traversal entirely!\n+test_perf 'prune with bitmaps' '\n+\techo \"probably not present in repo\" | git hash-object -w --stdin &&\n+\tgit prune\n+'\n+\n test_done\n-- \n2.21.0.rc0.586.gffba1126a0\n\n"},{"id":"369278","messageId":"20190214043821.GC19183@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190214043127.GA19019@sigill.intra.peff.net","subject":"[PATCH 3/3] prune: check SEEN flag for reachability","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-02-14T04:38:21Z","receivedAt":"2019-02-14T04:38:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The git-prune command checks reachability by doing a traversal, and then\nchecking whether a given object exists in the global object hash. This\ncan yield false positives if any other part of the code had to create an\nobject struct for some reason. It's not clear whether this is even\npossible, but it's more robust to rely on something a little more\nconcrete: the SEEN flag set by our traversal.\n\nNote that there is a slight possibility of regression here, as we're\nrelying on mark_reachable_objects() to consistently set the flag.\nHowever, it has always done so, and we're already relying on that fact\nin prune_shallow(), which is called as part of git-prune. So this is\nmaking these two parts of the prune operation more consistent.\n\nSigned-off-by: Jeff King \n---\n builtin/prune.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/prune.c b/builtin/prune.c\nindex 04b6573945..97613eccb5 100644\n--- a/builtin/prune.c\n+++ b/builtin/prune.c\n@@ -49,13 +49,12 @@ static void perform_reachability_traversal(struct rev_info *revs)\n static int is_object_reachable(const struct object_id *oid,\n \t\t\t struct rev_info *revs)\n {\n+\tstruct object *obj;\n+\n \tperform_reachability_traversal(revs);\n \n-\t/*\n-\t * Do we know about this object?\n-\t * It must have been reachable\n-\t */\n-\treturn !!lookup_object(the_repository, oid->hash);\n+\tobj = lookup_object(the_repository, oid->hash);\n+\treturn obj && (obj->flags & SEEN);\n }\n \n static int prune_object(const struct object_id *oid, const char *fullpath,\n-- \n2.21.0.rc0.586.gffba1126a0\n"},{"id":"369306","messageId":"CAPig+cQVUZT4ZyMeP5xDcvypjucVeRUP2cN=tL9c5DVoONSNng@mail.gmail.com","threadId":"50501","inReplyTo":"20190214043522.GA19183@sigill.intra.peff.net","subject":"Re: [PATCH 1/3] prune: lazily perform reachability traversal","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2019-02-14T10:54:25Z","receivedAt":"2019-02-14T10:54:38Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Wed, Feb 13, 2019 at 11:35 PM Jeff King wrote:\n> diff --git a/t/t5304-prune.sh b/t/t5304-prune.sh\n> @@ -274,6 +274,18 @@ test_expect_success 'prune .git/shallow' '\n> +test_expect_success 'prune .git/shallow when there are no loose objects' '\n> + SHA1=$(echo hi|git commit-tree HEAD^{tree}) &&\n\nPerhaps name this variable 'oid' rather than 'SHA1' to make brian happy.\n\n> + echo $SHA1 >.git/shallow &&\n> + git update-ref refs/heads/shallow-tip $SHA1 &&\n> + git repack -ad &&\n> + # verify assumption that all loose objects are gone\n> + git count-objects | grep ^0 &&\n> + git prune &&\n> + echo $SHA1 >expect &&\n> + test_cmp expect .git/shallow\n> +'\n"},{"id":"369307","messageId":"20190214110736.GA27609@sigill.intra.peff.net","threadId":"50501","inReplyTo":"CAPig+cQVUZT4ZyMeP5xDcvypjucVeRUP2cN=tL9c5DVoONSNng@mail.gmail.com","subject":"Re: [PATCH 1/3] prune: lazily perform reachability traversal","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-02-14T11:07:36Z","receivedAt":"2019-02-14T11:07:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 14, 2019 at 05:54:25AM -0500, Eric Sunshine wrote:\n\n> On Wed, Feb 13, 2019 at 11:35 PM Jeff King wrote:\n> > diff --git a/t/t5304-prune.sh b/t/t5304-prune.sh\n> > @@ -274,6 +274,18 @@ test_expect_success 'prune .git/shallow' '\n> > +test_expect_success 'prune .git/shallow when there are no loose objects' '\n> > + SHA1=$(echo hi|git commit-tree HEAD^{tree}) &&\n> \n> Perhaps name this variable 'oid' rather than 'SHA1' to make brian happy.\n\nHeh, that line (and the one below it) are cut-and-paste from the setup\nof the test directly above.\n\nPerhaps we should do this on top:\n\n-- >8 --\nSubject: [PATCH] t5304: rename \"sha1\" variables to \"oid\"\n\nLet's make the script less jarring to read in a post-sha1 world by\nusing more hash-agnostic variable names.\n\nSigned-off-by: Jeff King \n---\n t/t5304-prune.sh | 24 ++++++++++++------------\n 1 file changed, 12 insertions(+), 12 deletions(-)\n\ndiff --git a/t/t5304-prune.sh b/t/t5304-prune.sh\nindex 2c19a790c1..1eeb828a15 100755\n--- a/t/t5304-prune.sh\n+++ b/t/t5304-prune.sh\n@@ -118,10 +118,10 @@ test_expect_success 'prune: do not prune detached HEAD with no reflog' '\n \n test_expect_success 'prune: prune former HEAD after checking out branch' '\n \n-\thead_sha1=$(git rev-parse HEAD) &&\n+\thead_oid=$(git rev-parse HEAD) &&\n \tgit checkout --quiet master &&\n \tgit prune -v >prune_actual &&\n-\tgrep \"$head_sha1\" prune_actual\n+\tgrep \"$head_oid\" prune_actual\n \n '\n \n@@ -265,24 +265,24 @@ EOF\n '\n \n test_expect_success 'prune .git/shallow' '\n-\tSHA1=$(echo hi|git commit-tree HEAD^{tree}) &&\n-\techo $SHA1 >.git/shallow &&\n+\toid=$(echo hi|git commit-tree HEAD^{tree}) &&\n+\techo $oid >.git/shallow &&\n \tgit prune --dry-run >out &&\n-\tgrep $SHA1 .git/shallow &&\n-\tgrep $SHA1 out &&\n+\tgrep $oid .git/shallow &&\n+\tgrep $oid out &&\n \tgit prune &&\n \ttest_path_is_missing .git/shallow\n '\n \n test_expect_success 'prune .git/shallow when there are no loose objects' '\n-\tSHA1=$(echo hi|git commit-tree HEAD^{tree}) &&\n-\techo $SHA1 >.git/shallow &&\n-\tgit update-ref refs/heads/shallow-tip $SHA1 &&\n+\toid=$(echo hi|git commit-tree HEAD^{tree}) &&\n+\techo $oid >.git/shallow &&\n+\tgit update-ref refs/heads/shallow-tip $oid &&\n \tgit repack -ad &&\n \t# verify assumption that all loose objects are gone\n \tgit count-objects | grep ^0 &&\n \tgit prune &&\n-\techo $SHA1 >expect &&\n+\techo $oid >expect &&\n \ttest_cmp expect .git/shallow\n '\n \n@@ -326,8 +326,8 @@ test_expect_success 'prune: handle HEAD reflog in multiple worktrees' '\n \t\tgit reset --hard HEAD^\n \t) &&\n \tgit prune --expire=now &&\n-\tSHA1=`git hash-object expected` &&\n-\tgit -C third-worktree show \"$SHA1\" >actual &&\n+\toid=`git hash-object expected` &&\n+\tgit -C third-worktree show \"$oid\" >actual &&\n \ttest_cmp expected actual\n '\n \n-- \n2.21.0.rc1.567.g7f045cdc92\n\n"},{"id":"371018","messageId":"20190309024944.zcbwgvn52jsw2a2e@dcvr","threadId":"50501","inReplyTo":"20190214043743.GB19183@sigill.intra.peff.net","subject":"bitmaps by default? [was: prune: use bitmaps for reachability traversal]","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2019-03-09T02:49:44Z","receivedAt":"2019-03-09T02:49:46Z","isPatch":false,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jeff King wrote:\n> Pruning generally has to traverse the whole commit graph in order to\n> see which objects are reachable. This is the exact problem that\n> reachability bitmaps were meant to solve, so let's use them (if they're\n> available, of course).\n\nPerhaps this is good impetus for doing bitmaps by default?\n\nIt would make life easier for people new to hosting git servers\n(and hopefully reduce centralization :)\n\n\nI started working on it, but t0410-partial-clone.sh fails with\n\"Failed to write bitmap index. Packfile doesn't have full\nclosure\"; so more work needs to be done w.r.t. default behavior\non partial clones...\n\nHere's my WIP:\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 67f8978043..ca98d32715 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -14,7 +14,7 @@\n \n static int delta_base_offset = 1;\n static int pack_kept_objects = -1;\n-static int write_bitmaps;\n+static int write_bitmaps = -1;\n static int use_delta_islands;\n static char *packdir, *packtmp;\n \n@@ -344,10 +344,14 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n \n \tif (pack_kept_objects < 0)\n-\t\tpack_kept_objects = write_bitmaps;\n+\t\tpack_kept_objects = write_bitmaps > 0;\n \n-\tif (write_bitmaps && !(pack_everything & ALL_INTO_ONE))\n-\t\tdie(_(incremental_bitmap_conflict_error));\n+\tif (!(pack_everything & ALL_INTO_ONE)) {\n+\t\tif (write_bitmaps > 0)\n+\t\t\tdie(_(incremental_bitmap_conflict_error));\n+\t} else if (write_bitmaps < 0) {\n+\t\twrite_bitmaps = 1;\n+\t}\n \n \tpackdir = mkpathdup(\"%s/pack\", get_object_directory());\n \tpacktmp = mkpathdup(\"%s/.tmp-%d-pack\", packdir, (int)getpid());\n@@ -368,7 +372,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \targv_array_push(&cmd.args, \"--indexed-objects\");\n \tif (repository_format_partial_clone)\n \t\targv_array_push(&cmd.args, \"--exclude-promisor-objects\");\n-\tif (write_bitmaps)\n+\tif (write_bitmaps > 0)\n \t\targv_array_push(&cmd.args, \"--write-bitmap-index\");\n \tif (use_delta_islands)\n \t\targv_array_push(&cmd.args, \"--delta-islands\");\n"},{"id":"371091","messageId":"20190310233956.GB3059@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190309024944.zcbwgvn52jsw2a2e@dcvr","subject":"Re: bitmaps by default? [was: prune: use bitmaps for reachability traversal]","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-10T23:39:57Z","receivedAt":"2019-03-10T23:40:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 09, 2019 at 02:49:44AM +0000, Eric Wong wrote:\n\n> Jeff King wrote:\n> > Pruning generally has to traverse the whole commit graph in order to\n> > see which objects are reachable. This is the exact problem that\n> > reachability bitmaps were meant to solve, so let's use them (if they're\n> > available, of course).\n> \n> Perhaps this is good impetus for doing bitmaps by default?\n\nI'm actually not sure it is, because the prune costs less than making\nthe bitmaps. Here are some timings on linux.git. This full-graph\ntraversal is roughly the same cost as the reachability walk that prune\nwould do internally:\n\n\t$ time git rev-list --objects --all >/dev/null\n\treal\t0m47.714s\n\tuser\t0m47.113s\n\tsys\t0m0.600s\n\nHere's a normal noop repack as a baseline.\n\n\t$ time git repack -ad\n\treal\t1m26.922s\n\tuser\t1m20.029s\n\tsys\t0m7.878s\n\nAnd here's another immediately after with bitmap generation. Generating\nthe bitmaps takes about 100s, compared to the 47s it would save us on\nthe prune.\n\n\t$ time git repack -adb\n\treal\t3m5.915s\n\tuser\t2m59.377s\n\tsys\t0m7.718s\n\nThings are a little rosier if you generate the bitmaps a second time:\n\n\t$ time git repack -adb\n\treal\t1m43.571s\n\tuser\t1m37.403s\n\tsys\t0m8.179s\n\nWe can reuse some of the old bitmaps and it only takes 20 extra seconds,\nmaking it a net win. But I'm not sure how realistic that is. There were\nliterally no new objects introduced between those two command. If this\nwere a \"real\" repack occurring after we'd accumulated a week or two\nworth of objects, how long would it take?\n\nA few other random observations:\n\n - I do suspect there are some real inefficiencies in the way we\n generate bitmaps. It _should_ be about as expensive as the graph\n traversal, but clearly it's not. I think this is because of the way\n the current bitmap code picks commits to bitmap, and then walks\n somewhat haphazardly over the history, trying to accumulate the set\n of objects for each commit. IOW, I believe it may sometimes\n traverse over some sequences of history more than once. So if we\n could make that faster, then the balance would shift in its favor.\n\n - This is comparing the cost of generating the bitmaps to the time\n saved for _one_ operation. On a repo serving many fetches, the cost\n to generate it is amortized over many requests. But for a normal\n end-user, that's not true (they'd presumably push out their work,\n but that usually only needs to walk a small bit of history anyway).\n\n The balance would change if we had more operations that used bitmaps\n (e.g., --contains can use them, as can ahead/behind checks). We\n don't do those things yet, but we could. However, those algorithms\n are also using other commit-graph optimizations, and we've discussed\n revamping the bitmap format as part of that work (one problem in\n particular is that to use the current bitmaps you have to parse the\n whole .bitmap file, making it sometimes a net negative to use the\n bitmaps). So I'd consider holding off any decision like \"let's make\n this the default\" until we see where that work goes.\n\n> It would make life easier for people new to hosting git servers\n> (and hopefully reduce centralization :)\n\nI do think they're a net win for people hosting git servers. But if\nthat's the goal, I think at most you'd want to make bitmaps the default\nfor bare repos. They're really not much help for normal end-user repos\nat this point.\n\n> I started working on it, but t0410-partial-clone.sh fails with\n> \"Failed to write bitmap index. Packfile doesn't have full\n> closure\"; so more work needs to be done w.r.t. default behavior\n> on partial clones...\n\nYeah, you can't use bitmaps at all in an incomplete clone. Shallow\nclones would probably have the same issue (though in general we just\ndisable bitmaps entirely in shallow situations, so that might kick in).\n\n-Peff\n"},{"id":"371217","messageId":"20190312031303.5tutut7zzvxne5dw@dcvr","threadId":"50501","inReplyTo":"20190310233956.GB3059@sigill.intra.peff.net","subject":"[PATCH] repack: enable bitmaps by default on bare repos","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2019-03-12T03:13:03Z","receivedAt":"2019-03-12T03:13:04Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jeff King wrote:\n> On Sat, Mar 09, 2019 at 02:49:44AM +0000, Eric Wong wrote:\n> > It would make life easier for people new to hosting git servers\n> > (and hopefully reduce centralization :)\n> \n> I do think they're a net win for people hosting git servers. But if\n> that's the goal, I think at most you'd want to make bitmaps the default\n> for bare repos. They're really not much help for normal end-user repos\n> at this point.\n\nFair enough, hopefully this can make life easier for admins\nnew to hosting git:\n\n----------8<---------\nSubject: [PATCH] repack: enable bitmaps by default on bare repos\n\nA typical use case for bare repos is for serving clones and\nfetches to clients. Enable bitmaps by default on bare repos to\nmake it easier for admins to host git repos in a performant way.\n\nSigned-off-by: Eric Wong \n---\n builtin/repack.c | 16 ++++++++++------\n t/t7700-repack.sh | 14 +++++++++++++-\n 2 files changed, 23 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 67f8978043..5d4758b515 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -14,7 +14,7 @@\n \n static int delta_base_offset = 1;\n static int pack_kept_objects = -1;\n-static int write_bitmaps;\n+static int write_bitmaps = -1;\n static int use_delta_islands;\n static char *packdir, *packtmp;\n \n@@ -343,11 +343,15 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n \n+\tif (!(pack_everything & ALL_INTO_ONE)) {\n+\t\tif (write_bitmaps > 0)\n+\t\t\tdie(_(incremental_bitmap_conflict_error));\n+\t} else if (write_bitmaps < 0) {\n+\t\twrite_bitmaps = is_bare_repository();\n+\t}\n+\n \tif (pack_kept_objects < 0)\n-\t\tpack_kept_objects = write_bitmaps;\n-\n-\tif (write_bitmaps && !(pack_everything & ALL_INTO_ONE))\n-\t\tdie(_(incremental_bitmap_conflict_error));\n+\t\tpack_kept_objects = write_bitmaps > 0;\n \n \tpackdir = mkpathdup(\"%s/pack\", get_object_directory());\n \tpacktmp = mkpathdup(\"%s/.tmp-%d-pack\", packdir, (int)getpid());\n@@ -368,7 +372,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \targv_array_push(&cmd.args, \"--indexed-objects\");\n \tif (repository_format_partial_clone)\n \t\targv_array_push(&cmd.args, \"--exclude-promisor-objects\");\n-\tif (write_bitmaps)\n+\tif (write_bitmaps > 0)\n \t\targv_array_push(&cmd.args, \"--write-bitmap-index\");\n \tif (use_delta_islands)\n \t\targv_array_push(&cmd.args, \"--delta-islands\");\ndiff --git a/t/t7700-repack.sh b/t/t7700-repack.sh\nindex 6162e2a8e6..3e0b5c40e4 100755\n--- a/t/t7700-repack.sh\n+++ b/t/t7700-repack.sh\n@@ -221,5 +221,17 @@ test_expect_success 'repack --keep-pack' '\n \t)\n '\n \n+test_expect_success 'bitmaps are created by default in bare repos' '\n+\tgit clone --bare .git bare.git &&\n+\tcd bare.git &&\n+\tmkdir old &&\n+\tmv objects/pack/* old &&\n+\tpack=$(ls old/*.pack) &&\n+\ttest_path_is_file \"$pack\" &&\n+\tgit unpack-objects -q <\"$pack\" &&\n+\tgit repack -ad &&\n+\tbitmap=$(ls objects/pack/*.bitmap) &&\n+\ttest_path_is_file \"$bitmap\"\n+'\n+\n test_done\n-\n"},{"id":"371228","messageId":"871s3ccvg5.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190312031303.5tutut7zzvxne5dw@dcvr","subject":"Re: [PATCH] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-03-12T09:07:22Z","receivedAt":"2019-03-12T09:07:27Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Tue, Mar 12 2019, Eric Wong wrote:\n\n> Jeff King wrote:\n>> On Sat, Mar 09, 2019 at 02:49:44AM +0000, Eric Wong wrote:\n>> > It would make life easier for people new to hosting git servers\n>> > (and hopefully reduce centralization :)\n>>\n>> I do think they're a net win for people hosting git servers. But if\n>> that's the goal, I think at most you'd want to make bitmaps the default\n>> for bare repos. They're really not much help for normal end-user repos\n>> at this point.\n>\n> Fair enough, hopefully this can make life easier for admins\n> new to hosting git:\n>\n> ----------8<---------\n> Subject: [PATCH] repack: enable bitmaps by default on bare repos\n>\n> A typical use case for bare repos is for serving clones and\n> fetches to clients. Enable bitmaps by default on bare repos to\n> make it easier for admins to host git repos in a performant way.\n>\n> Signed-off-by: Eric Wong \n> ---\n> builtin/repack.c | 16 ++++++++++------\n> t/t7700-repack.sh | 14 +++++++++++++-\n> 2 files changed, 23 insertions(+), 7 deletions(-)\n>\n> diff --git a/builtin/repack.c b/builtin/repack.c\n> index 67f8978043..5d4758b515 100644\n> --- a/builtin/repack.c\n> +++ b/builtin/repack.c\n> @@ -14,7 +14,7 @@\n>\n> static int delta_base_offset = 1;\n> static int pack_kept_objects = -1;\n> -static int write_bitmaps;\n> +static int write_bitmaps = -1;\n> static int use_delta_islands;\n> static char *packdir, *packtmp;\n>\n> @@ -343,11 +343,15 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n> \t (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n> \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n>\n> +\tif (!(pack_everything & ALL_INTO_ONE)) {\n> +\t\tif (write_bitmaps > 0)\n> +\t\t\tdie(_(incremental_bitmap_conflict_error));\n> +\t} else if (write_bitmaps < 0) {\n> +\t\twrite_bitmaps = is_bare_repository();\n> +\t}\n> +\n> \tif (pack_kept_objects < 0)\n> -\t\tpack_kept_objects = write_bitmaps;\n> -\n> -\tif (write_bitmaps && !(pack_everything & ALL_INTO_ONE))\n> -\t\tdie(_(incremental_bitmap_conflict_error));\n> +\t\tpack_kept_objects = write_bitmaps > 0;\n>\n> \tpackdir = mkpathdup(\"%s/pack\", get_object_directory());\n> \tpacktmp = mkpathdup(\"%s/.tmp-%d-pack\", packdir, (int)getpid());\n> @@ -368,7 +372,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n> \targv_array_push(&cmd.args, \"--indexed-objects\");\n> \tif (repository_format_partial_clone)\n> \t\targv_array_push(&cmd.args, \"--exclude-promisor-objects\");\n> -\tif (write_bitmaps)\n> +\tif (write_bitmaps > 0)\n> \t\targv_array_push(&cmd.args, \"--write-bitmap-index\");\n> \tif (use_delta_islands)\n> \t\targv_array_push(&cmd.args, \"--delta-islands\");\n> diff --git a/t/t7700-repack.sh b/t/t7700-repack.sh\n> index 6162e2a8e6..3e0b5c40e4 100755\n> --- a/t/t7700-repack.sh\n> +++ b/t/t7700-repack.sh\n> @@ -221,5 +221,17 @@ test_expect_success 'repack --keep-pack' '\n> \t)\n> '\n>\n> +test_expect_success 'bitmaps are created by default in bare repos' '\n> +\tgit clone --bare .git bare.git &&\n> +\tcd bare.git &&\n> +\tmkdir old &&\n> +\tmv objects/pack/* old &&\n> +\tpack=$(ls old/*.pack) &&\n> +\ttest_path_is_file \"$pack\" &&\n> +\tgit unpack-objects -q <\"$pack\" &&\n> +\tgit repack -ad &&\n> +\tbitmap=$(ls objects/pack/*.bitmap) &&\n> +\ttest_path_is_file \"$bitmap\"\n> +'\n> +\n> test_done\n> -\n\nLooks sensible in principle, but now the git-repack and git-config docs\ntalking about repack.writeBitmaps are out-of-date. A v2 should update\nthose.\n\nAlso worth testing that -c repack.writeBitmaps=false on a bare\nrepository still overrides it, even though glancing at the code it looks\nlike that case is handled, but without being tested for.\n"},{"id":"371234","messageId":"20190312104954.GA2023@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190312031303.5tutut7zzvxne5dw@dcvr","subject":"Re: [PATCH] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-12T10:49:54Z","receivedAt":"2019-03-12T10:50:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 12, 2019 at 03:13:03AM +0000, Eric Wong wrote:\n\n> > I do think they're a net win for people hosting git servers. But if\n> > that's the goal, I think at most you'd want to make bitmaps the default\n> > for bare repos. They're really not much help for normal end-user repos\n> > at this point.\n> \n> Fair enough, hopefully this can make life easier for admins\n> new to hosting git:\n> \n> ----------8<---------\n> Subject: [PATCH] repack: enable bitmaps by default on bare repos\n> \n> A typical use case for bare repos is for serving clones and\n> fetches to clients. Enable bitmaps by default on bare repos to\n> make it easier for admins to host git repos in a performant way.\n\nOK. I still think of bitmaps as something that might need manual care\nand feeding, but I think that may be leftover superstition. I can't\noffhand think of any real downsides to this.\n\n> static int delta_base_offset = 1;\n> static int pack_kept_objects = -1;\n> -static int write_bitmaps;\n> +static int write_bitmaps = -1;\n\nSo we'll have \"-1\" be \"not decided yet\". Makes sense.\n\n> @@ -343,11 +343,15 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n> \t (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n> \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n> \n> +\tif (!(pack_everything & ALL_INTO_ONE)) {\n> +\t\tif (write_bitmaps > 0)\n> +\t\t\tdie(_(incremental_bitmap_conflict_error));\n> +\t} else if (write_bitmaps < 0) {\n> +\t\twrite_bitmaps = is_bare_repository();\n> +\t}\n\nMight it be easier here to always resolve \"-1\" into a 0/1? I.e., like:\n\n if (write_bitmaps < 0)\n\twrite_bitmaps = (pack_everything & ALL_INTO_ONE) && is_bare_repository();\n\nand then the rest of the logic can stay the same, and does not need to\nbe modified to handle \"write_bitmaps < 0\"?\n\n> +test_expect_success 'bitmaps are created by default in bare repos' '\n> +\tgit clone --bare .git bare.git &&\n> +\tcd bare.git &&\n\nPlease don't \"cd\" outside of a subshell, since it impacts further tests\nthat are added.\n\n> +\tmkdir old &&\n> +\tmv objects/pack/* old &&\n> +\tpack=$(ls old/*.pack) &&\n\nAre we sure we have just done $pack here? Our repo came from a\nlocal-disk clone, which would have just hard-linked whatever was in the\nsource repo. So we're subtly relying on the state that other tests have\nleft.\n\nI'm not sure what we're trying to accomplish with this unpacking,\nthough. Running \"git repack -ad\" should generate bitmaps whether the\nobjects were already in a single pack or not. So I think this test can\njust be:\n\n git clone --bare . bare.git &&\n git -C bare.git repack -ad &&\n bitmap=$(ls objects/pack/*.bitmap)\n test_path_is_file \"$bitmap\"\n\nI do agree with Ævar it might also be worth testing that disabling\nbitmaps explicitly still works. And also that repacking _without_ \"-a\"\n(i.e., an incremental) does not complain about being unable to generate\nbitmaps.\n\n-Peff\n"},{"id":"371243","messageId":"20190312120550.GA7020@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190312104954.GA2023@sigill.intra.peff.net","subject":"Re: [PATCH] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-12T12:05:50Z","receivedAt":"2019-03-12T12:05:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 12, 2019 at 06:49:54AM -0400, Jeff King wrote:\n\n> I'm not sure what we're trying to accomplish with this unpacking,\n> though. Running \"git repack -ad\" should generate bitmaps whether the\n> objects were already in a single pack or not. So I think this test can\n> just be:\n> \n> git clone --bare . bare.git &&\n> git -C bare.git repack -ad &&\n> bitmap=$(ls objects/pack/*.bitmap)\n> test_path_is_file \"$bitmap\"\n\nOf course that should be \"bare.git/objects/pack/*.bitmap\" in the third\nline, since we skipped the \"cd\" entirely.\n\n-Peff\n"},{"id":"371318","messageId":"20190313015133.n7f7lyujnlwfytre@dcvr","threadId":"50501","inReplyTo":"20190312104954.GA2023@sigill.intra.peff.net","subject":"Re: [PATCH] repack: enable bitmaps by default on bare repos","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2019-03-13T01:51:33Z","receivedAt":"2019-03-13T01:51:36Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jeff King wrote:\n> OK. I still think of bitmaps as something that might need manual care\n> and feeding, but I think that may be leftover superstition. I can't\n> offhand think of any real downsides to this.\n\nIt's a _relatively_ new feature to long-time users like us, so\nmaybe the \"new == immature\" mindset sets in[*]. I skimmed some\nmail archives but couldn't find any reason not to...\n\nBut I did find Ævar's forgotten gitperformance doc and thread\nwhere the topic was brought up:\n\n https://public-inbox.org/git/20170403211644.26814-1-avarab@gmail.com/\n\n> On Tue, Mar 12, 2019 at 03:13:03AM +0000, Eric Wong wrote:\n> > @@ -343,11 +343,15 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n> > \t (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n> > \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n> > \n> > +\tif (!(pack_everything & ALL_INTO_ONE)) {\n> > +\t\tif (write_bitmaps > 0)\n> > +\t\t\tdie(_(incremental_bitmap_conflict_error));\n> > +\t} else if (write_bitmaps < 0) {\n> > +\t\twrite_bitmaps = is_bare_repository();\n> > +\t}\n> \n> Might it be easier here to always resolve \"-1\" into a 0/1? I.e., like:\n> \n> if (write_bitmaps < 0)\n> \twrite_bitmaps = (pack_everything & ALL_INTO_ONE) && is_bare_repository();\n> \n> and then the rest of the logic can stay the same, and does not need to\n> be modified to handle \"write_bitmaps < 0\"?\n\nGood point, changed in v2.\n\n> > +test_expect_success 'bitmaps are created by default in bare repos' '\n> > +\tgit clone --bare .git bare.git &&\n> > +\tcd bare.git &&\n> \n> Please don't \"cd\" outside of a subshell, since it impacts further tests\n> that are added.\n\nOops, I got it into my head that each test was already run in a\nseparate subshell :x Fixed.\n\n> > +\tmkdir old &&\n> > +\tmv objects/pack/* old &&\n> > +\tpack=$(ls old/*.pack) &&\n> \n> Are we sure we have just done $pack here? Our repo came from a\n> local-disk clone, which would have just hard-linked whatever was in the\n> source repo. So we're subtly relying on the state that other tests have\n> left.\n> \n> I'm not sure what we're trying to accomplish with this unpacking,\n> though. Running \"git repack -ad\" should generate bitmaps whether the\n> objects were already in a single pack or not. So I think this test can\n> just be:\n\nRight, I forgot \"repack -a\" didn't need loose objects to operate :x\n\n> I do agree with Ævar it might also be worth testing that disabling\n> bitmaps explicitly still works. And also that repacking _without_ \"-a\"\n> (i.e., an incremental) does not complain about being unable to generate\n> bitmaps.\n\nYup, now with additional tests for repack.writeBitmaps=false,\nrepack (w/o \"-a\") and a config/repack.txt update\n\n------------8<---------\nSubject: [PATCH] repack: enable bitmaps by default on bare repos\n\nA typical use case for bare repos is for serving clones and\nfetches to clients. Enable bitmaps by default on bare repos to\nmake it easier for admins to host git repos in a performant way.\n\nSigned-off-by: Eric Wong \nHelped-by: Jeff King \n---\n Documentation/config/repack.txt | 2 +-\n builtin/repack.c | 5 ++++-\n t/t7700-repack.sh | 19 ++++++++++++++++++-\n 3 files changed, 23 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/config/repack.txt b/Documentation/config/repack.txt\nindex a5c37813fd..9c413e177e 100644\n--- a/Documentation/config/repack.txt\n+++ b/Documentation/config/repack.txt\n@@ -24,4 +24,4 @@ repack.writeBitmaps::\n \tpacks created for clones and fetches, at the cost of some disk\n \tspace and extra time spent on the initial repack. This has\n \tno effect if multiple packfiles are created.\n-\tDefaults to false.\n+\tDefaults to true on bare repos, false otherwise.\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 67f8978043..caca113927 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -14,7 +14,7 @@\n \n static int delta_base_offset = 1;\n static int pack_kept_objects = -1;\n-static int write_bitmaps;\n+static int write_bitmaps = -1;\n static int use_delta_islands;\n static char *packdir, *packtmp;\n \n@@ -343,6 +343,9 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n \n+\tif (write_bitmaps < 0)\n+\t\twrite_bitmaps = (pack_everything & ALL_INTO_ONE) &&\n+\t\t\t\t is_bare_repository();\n \tif (pack_kept_objects < 0)\n \t\tpack_kept_objects = write_bitmaps;\n \ndiff --git a/t/t7700-repack.sh b/t/t7700-repack.sh\nindex 6162e2a8e6..6458286dcf 100755\n--- a/t/t7700-repack.sh\n+++ b/t/t7700-repack.sh\n@@ -221,5 +221,22 @@ test_expect_success 'repack --keep-pack' '\n \t)\n '\n \n-test_done\n+test_expect_success 'bitmaps are created by default in bare repos' '\n+\tgit clone --bare .git bare.git &&\n+\tgit -C bare.git repack -ad &&\n+\tbitmap=$(ls bare.git/objects/pack/*.bitmap) &&\n+\ttest_path_is_file \"$bitmap\"\n+'\n+\n+test_expect_success 'incremental repack does not complain' '\n+\tgit -C bare.git repack -q 2>repack.err &&\n+\t! test -s repack.err\n+'\n \n+test_expect_success 'bitmaps can be disabled on bare repos' '\n+\tgit -c repack.writeBitmaps=false -C bare.git repack -ad &&\n+\tbitmap=$(ls bare.git/objects/pack/*.bitmap 2>/dev/null || :) &&\n+\ttest -z \"$bitmap\"\n+'\n+\n+test_done\n-- \nEW\n"},{"id":"371369","messageId":"20190313145417.GA24101@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190313015133.n7f7lyujnlwfytre@dcvr","subject":"Re: [PATCH] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-13T14:54:17Z","receivedAt":"2019-03-13T14:55:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 13, 2019 at 01:51:33AM +0000, Eric Wong wrote:\n\n> But I did find Ævar's forgotten gitperformance doc and thread\n> where the topic was brought up:\n> \n> https://public-inbox.org/git/20170403211644.26814-1-avarab@gmail.com/\n\nOne thing that thread reminded me of: we probably also want to default\npack.writebitmaphashcache on. Otherwise the time saved during the object\nenumeration can backfire when we spend much more time trying delta\ncompression (because we don't know the pathnames of any objects).\n\nThe reason it defaults to off is for on-disk compatibility with JGit.\nBut I have very little experience running without the hash-cache on. We\nadded it very early on because we found performance was not great\nwithout it (I don't know if people running JGit have run into the same\nproblem and if not, why not).\n\n> ------------8<---------\n> Subject: [PATCH] repack: enable bitmaps by default on bare repos\n> \n> A typical use case for bare repos is for serving clones and\n> fetches to clients. Enable bitmaps by default on bare repos to\n> make it easier for admins to host git repos in a performant way.\n\nThis looks good to me, with one minor nit:\n\n> +test_expect_success 'incremental repack does not complain' '\n> +\tgit -C bare.git repack -q 2>repack.err &&\n> +\t! test -s repack.err\n> +'\n\nThis last line could use \"test_must_be_empty\".\n\n-Peff\n"},{"id":"371469","messageId":"20190314091254.nescpfp3n6mbjpmh@dcvr","threadId":"50501","inReplyTo":"20190313145417.GA24101@sigill.intra.peff.net","subject":"[PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Eric Wong","fromEmail":"e@80x24.org","sentAt":"2019-03-14T09:12:54Z","receivedAt":"2019-03-14T09:12:58Z","isPatch":true,"sender":{"key":"e@80x24.org","avatar":null},"body":"Jeff King wrote:\n> On Wed, Mar 13, 2019 at 01:51:33AM +0000, Eric Wong wrote:\n> \n> > But I did find Ævar's forgotten gitperformance doc and thread\n> > where the topic was brought up:\n> > \n> > https://public-inbox.org/git/20170403211644.26814-1-avarab@gmail.com/\n> \n> One thing that thread reminded me of: we probably also want to default\n> pack.writebitmaphashcache on. Otherwise the time saved during the object\n> enumeration can backfire when we spend much more time trying delta\n> compression (because we don't know the pathnames of any objects).\n\nInteresting... I found a big improvement with public-inbox\njust using bitmaps; but have never tried the hash cache.\n\n> The reason it defaults to off is for on-disk compatibility with JGit.\n\nRight. Our documentation seems to indicate JGit just warns (but\ndoesn't fall over), so maybe that can be considered separately.\n\nI've never used JGit myself; and was satisfied enough with\nbitmaps alone that I never tried the hash-cache.\n\n> But I have very little experience running without the hash-cache on. We\n> added it very early on because we found performance was not great\n> without it (I don't know if people running JGit have run into the same\n> problem and if not, why not).\n\nAs far as serving clones and fetches, public-inbox-init has\nalways created bare repos with bitmaps enabled, but without\nthe hash-cache for compatibility concerns.\n\nThat's a lot of fetches and clones over the years.\n\n> > +test_expect_success 'incremental repack does not complain' '\n> > +\tgit -C bare.git repack -q 2>repack.err &&\n> > +\t! test -s repack.err\n> > +'\n> \n> This last line could use \"test_must_be_empty\".\n\nThanks for the review!\n\n---------8<-----------\nSubject: [PATCH] repack: enable bitmaps by default on bare repos\n\nA typical use case for bare repos is for serving clones and\nfetches to clients. Enable bitmaps by default on bare repos to\nmake it easier for admins to host git repos in a performant way.\n\nSigned-off-by: Eric Wong \nHelped-by: Jeff King \n---\n Documentation/config/repack.txt | 2 +-\n builtin/repack.c | 5 ++++-\n t/t7700-repack.sh | 19 ++++++++++++++++++-\n 3 files changed, 23 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/config/repack.txt b/Documentation/config/repack.txt\nindex a5c37813fd..9c413e177e 100644\n--- a/Documentation/config/repack.txt\n+++ b/Documentation/config/repack.txt\n@@ -24,4 +24,4 @@ repack.writeBitmaps::\n \tpacks created for clones and fetches, at the cost of some disk\n \tspace and extra time spent on the initial repack. This has\n \tno effect if multiple packfiles are created.\n-\tDefaults to false.\n+\tDefaults to true on bare repos, false otherwise.\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 67f8978043..caca113927 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -14,7 +14,7 @@\n \n static int delta_base_offset = 1;\n static int pack_kept_objects = -1;\n-static int write_bitmaps;\n+static int write_bitmaps = -1;\n static int use_delta_islands;\n static char *packdir, *packtmp;\n \n@@ -343,6 +343,9 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n \n+\tif (write_bitmaps < 0)\n+\t\twrite_bitmaps = (pack_everything & ALL_INTO_ONE) &&\n+\t\t\t\t is_bare_repository();\n \tif (pack_kept_objects < 0)\n \t\tpack_kept_objects = write_bitmaps;\n \ndiff --git a/t/t7700-repack.sh b/t/t7700-repack.sh\nindex 6162e2a8e6..86d05160a3 100755\n--- a/t/t7700-repack.sh\n+++ b/t/t7700-repack.sh\n@@ -221,5 +221,22 @@ test_expect_success 'repack --keep-pack' '\n \t)\n '\n \n-test_done\n+test_expect_success 'bitmaps are created by default in bare repos' '\n+\tgit clone --bare .git bare.git &&\n+\tgit -C bare.git repack -ad &&\n+\tbitmap=$(ls bare.git/objects/pack/*.bitmap) &&\n+\ttest_path_is_file \"$bitmap\"\n+'\n+\n+test_expect_success 'incremental repack does not complain' '\n+\tgit -C bare.git repack -q 2>repack.err &&\n+\ttest_must_be_empty repack.err\n+'\n \n+test_expect_success 'bitmaps can be disabled on bare repos' '\n+\tgit -c repack.writeBitmaps=false -C bare.git repack -ad &&\n+\tbitmap=$(ls bare.git/objects/pack/*.bitmap 2>/dev/null || :) &&\n+\ttest -z \"$bitmap\"\n+'\n+\n+test_done\n-- \nEW\n"},{"id":"371522","messageId":"20190314160256.GA1573@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190314091254.nescpfp3n6mbjpmh@dcvr","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-14T16:02:56Z","receivedAt":"2019-03-14T16:04:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 14, 2019 at 09:12:54AM +0000, Eric Wong wrote:\n\n> > The reason it defaults to off is for on-disk compatibility with JGit.\n> \n> Right. Our documentation seems to indicate JGit just warns (but\n> doesn't fall over), so maybe that can be considered separately.\n\nI think it was a hard error in the beginning, but they changed it pretty\nsoon after we added more flags. So it might be reasonable to just enable\nit by default (but it wouldn't hurt to double check the behavior).\n\nI tried running t5310 (which does a back-and-forth with jgit) using this\npatch:\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex a154fc29f6..5264bf055a 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -97,7 +97,7 @@ static off_t reuse_packfile_offset;\n static int use_bitmap_index_default = 1;\n static int use_bitmap_index = -1;\n static int write_bitmap_index;\n-static uint16_t write_bitmap_options;\n+static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;\n \n static int exclude_promisor_objects;\n \n\nand it seemed happy.\n\n> As far as serving clones and fetches, public-inbox-init has\n> always created bare repos with bitmaps enabled, but without\n> the hash-cache for compatibility concerns.\n> \n> That's a lot of fetches and clones over the years.\n\nThe symptom you'd see is that \"Compressing objects\" during a fetch takes\na long time, and/or produces lousy deltas. But it matters less if:\n\n - you keep things packed pretty promptly, because we don't bother\n looking for new deltas between objects in the same pack. Just trying\n to clone public-inbox.org/git, it does look like it's mostly packed\n (based on the object counts) but the compression phase still takes\n 10+ seconds.\n\n - how much the names actually help. In your case, I'd think not at\n all, because being based on hashes, they're effectively random. So\n the pack-objects heuristics to try to find deltas between files of\n similar filenames will not help you.\n\nRegarding the second thing, I wondered if the overall packing of your\npublic-inbox git repo might not be good, so I did a \"git repack -adf\n--window=1000\" on a clone. Hundreds of CPU minutes later, I was only\nable to shave off about 80MB. I'm not sure if that means you\noccasionally do very aggressive repacks, or if there simply isn't all\nthat much delta opportunity (after all, you're not storing many versions\nof one file, but rather tons of different emails; I would expect to find\ndeltas between various versions of a patch, though).\n\nAnyway...\n\n> ---------8<-----------\n> Subject: [PATCH] repack: enable bitmaps by default on bare repos\n> \n> A typical use case for bare repos is for serving clones and\n> fetches to clients. Enable bitmaps by default on bare repos to\n> make it easier for admins to host git repos in a performant way.\n> \n> Signed-off-by: Eric Wong \n> Helped-by: Jeff King \n\nThis version looks good to me. If we're going to flip the hash-cache\ndefault, I think that should be a separate patch anyway.\n\n-Peff\n"},{"id":"371565","messageId":"20190315062133.GA13385@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190314160256.GA1573@sigill.intra.peff.net","subject":"[PATCH 0/2] enable bitmap hash-cache by default","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-15T06:21:33Z","receivedAt":"2019-03-15T06:22:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Mar 14, 2019 at 12:02:56PM -0400, Jeff King wrote:\n\n> On Thu, Mar 14, 2019 at 09:12:54AM +0000, Eric Wong wrote:\n> \n> > > The reason it defaults to off is for on-disk compatibility with JGit.\n> > \n> > Right. Our documentation seems to indicate JGit just warns (but\n> > doesn't fall over), so maybe that can be considered separately.\n> \n> I think it was a hard error in the beginning, but they changed it pretty\n> soon after we added more flags. So it might be reasonable to just enable\n> it by default (but it wouldn't hurt to double check the behavior).\n> \n> I tried running t5310 (which does a back-and-forth with jgit) using this\n> patch:\n\nI dug up the actual JGit change, and it was indeed from 2014. So here's\na more complete series to handle that. There's a minor performance\nmystery in the second patch, but I think it might be OK to proceed even\nwithout solving it.\n\nConceptually these go on top of your patch, but they could be applied\nseparately.\n\n [1/2]: t5310: correctly remove bitmaps for jgit test\n [2/2]: pack-objects: default to writing bitmap hash-cache\n\n Documentation/config/pack.txt | 4 +---\n builtin/pack-objects.c | 2 +-\n t/perf/p5310-pack-bitmaps.sh | 3 +--\n t/perf/p5311-pack-bitmaps-fetch.sh | 1 -\n t/t5310-pack-bitmaps.sh | 5 ++---\n 5 files changed, 5 insertions(+), 10 deletions(-)\n\n-Peff\n"},{"id":"371566","messageId":"20190315062243.GA13466@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190315062133.GA13385@sigill.intra.peff.net","subject":"[PATCH 1/2] t5310: correctly remove bitmaps for jgit test","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-15T06:22:44Z","receivedAt":"2019-03-15T06:24:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We use \"jgit gc\" to generate a pack bitmap file, and then make sure our\nimplementation can read it. To prepare the repo before running jgit, we\ntry to \"rm -f\" any existing bitmap files. But we got the path wrong;\nwe're in a bare repo, so looking in \".git/\" finds nothing. Our \"rm\"\ndoesn't complain because of the \"-f\", and when we run \"rev-list\" there\nare two bitmap files (ours and jgit's).\n\nOur reader implementation will ignore one of the bitmap files, but it's\nlikely non-deterministic which one we will use. We'd prefer the one with\nthe more recent timestamp (just because of the way the packed_git list\nis sorted), but in most test runs they'd have identical timestamps.\n\nSo this was probably actually testing something useful about 50% of the\ntime, and other half just testing that we could read our own bitmaps\n(which is covered elsewhere).\n\nSigned-off-by: Jeff King \n---\nJust a cleanup I noticed in the area; can be applied independently from\npatch 2.\n\n t/t5310-pack-bitmaps.sh | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 82d7f7f6a5..44a038881a 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -269,7 +269,7 @@ test_expect_success JGIT 'we can read jgit bitmaps' '\n \tgit clone --bare . compat-jgit.git &&\n \t(\n \t\tcd compat-jgit.git &&\n-\t\trm -f .git/objects/pack/*.bitmap &&\n+\t\trm -f objects/pack/*.bitmap &&\n \t\tjgit gc &&\n \t\tgit rev-list --test-bitmap HEAD\n \t)\n-- \n2.21.0.543.g90eed137f3\n\n"},{"id":"371567","messageId":"20190315062528.GB13466@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190315062133.GA13385@sigill.intra.peff.net","subject":"[PATCH 2/2] pack-objects: default to writing bitmap hash-cache","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-15T06:25:28Z","receivedAt":"2019-03-15T06:26:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Enabling pack.writebitmaphashcache should always be a performance win.\nIt costs only 4 bytes per object on disk, and the timings in ae4f07fbcc\n(pack-bitmap: implement optional name_hash cache, 2013-12-21) show it\nimproving fetch and partial-bitmap clone times by 40-50%.\n\nThe only reason we didn't enable it by default at the time is that early\nversions of JGit's bitmap reader complained about the presence of\noptional header bits it didn't understand. But that was changed in\nJGit's d2fa3987a (Use bitcheck to check for presence of OPT_FULL option,\n2013-10-30), which made it into JGit v3.5.0 in late 2014.\n\nSo let's turn this option on by default. It's backwards-compatible with\nall versions of Git, and if you are also using JGit on the same\nrepository, you'd only run into problems using a version that's almost 5\nyears old.\n\nWe'll drop the manual setting from all of our test scripts, including\nperf tests. This isn't strictly necessary, but it has two advantages:\n\n 1. If the hash-cache ever stops being enabled by default, our perf\n regression tests will notice.\n\n 2. We can use the modified perf tests to show off the behavior of an\n otherwise unconfigured repo, as shown below.\n\nThese are the results of a few of a perf tests against linux.git that\nshowed interesting results. You can see the expected speedup in 5310.4,\nwhich was noted in ae4f07fbcc. Curiously, 5310.8 did not improve (and\nactually got slower), despite seeing the opposite in ae4f07fbcc.\nI don't have an explanation for that.\n\nThe tests from p5311 did not exist back then, but do show improvements\n(a smaller pack due to better deltas, which we found in less time).\n\n Test HEAD^ HEAD\n -------------------------------------------------------------------------------------\n 5310.4: simulated fetch 7.39(22.70+0.25) 5.64(11.43+0.22) -23.7%\n 5310.8: clone (partial bitmap) 18.45(24.83+1.19) 19.94(28.40+1.36) +8.1%\n 5311.31: server (128 days) 0.41(1.13+0.05) 0.34(0.72+0.02) -17.1%\n 5311.32: size (128 days) 7.4M 7.0M -4.8%\n 5311.33: client (128 days) 1.33(1.49+0.06) 1.29(1.37+0.12) -3.0%\n\nSigned-off-by: Jeff King \n---\n Documentation/config/pack.txt | 4 +---\n builtin/pack-objects.c | 2 +-\n t/perf/p5310-pack-bitmaps.sh | 3 +--\n t/perf/p5311-pack-bitmaps-fetch.sh | 1 -\n t/t5310-pack-bitmaps.sh | 3 +--\n 5 files changed, 4 insertions(+), 9 deletions(-)\n\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex 425c73aa52..9cdcfa7324 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -124,6 +124,4 @@ pack.writeBitmapHashCache::\n \tbitmapped and non-bitmapped objects (e.g., when serving a fetch\n \tbetween an older, bitmapped pack and objects that have been\n \tpushed since the last gc). The downside is that it consumes 4\n-\tbytes per object of disk space, and that JGit's bitmap\n-\timplementation does not understand it, causing it to complain if\n-\tGit and JGit are used on the same repository. Defaults to false.\n+\tbytes per object of disk space. Defaults to true.\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex a154fc29f6..5264bf055a 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -97,7 +97,7 @@ static off_t reuse_packfile_offset;\n static int use_bitmap_index_default = 1;\n static int use_bitmap_index = -1;\n static int write_bitmap_index;\n-static uint16_t write_bitmap_options;\n+static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;\n \n static int exclude_promisor_objects;\n \ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex bb91dbb173..6a3a42531b 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -12,8 +12,7 @@ test_perf_large_repo\n # We intentionally use the deprecated pack.writebitmaps\n # config so that we can test against older versions of git.\n test_expect_success 'setup bitmap config' '\n-\tgit config pack.writebitmaps true &&\n-\tgit config pack.writebitmaphashcache true\n+\tgit config pack.writebitmaps true\n '\n \n test_perf 'repack to disk' '\ndiff --git a/t/perf/p5311-pack-bitmaps-fetch.sh b/t/perf/p5311-pack-bitmaps-fetch.sh\nindex b04575951f..47c3fd7581 100755\n--- a/t/perf/p5311-pack-bitmaps-fetch.sh\n+++ b/t/perf/p5311-pack-bitmaps-fetch.sh\n@@ -7,7 +7,6 @@ test_perf_default_repo\n \n test_expect_success 'create bitmapped server repo' '\n \tgit config pack.writebitmaps true &&\n-\tgit config pack.writebitmaphashcache true &&\n \tgit repack -ad\n '\n \ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 44a038881a..a26c8ba9a2 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -34,8 +34,7 @@ test_expect_success 'setup repo with moderate-sized history' '\n \tbitmaptip=$(git rev-parse master) &&\n \tblob=$(echo tagged-blob | git hash-object -w --stdin) &&\n \tgit tag tagged-blob $blob &&\n-\tgit config repack.writebitmaps true &&\n-\tgit config pack.writebitmaphashcache true\n+\tgit config repack.writebitmaps true\n '\n \n test_expect_success 'full repack creates bitmaps' '\n-- \n2.21.0.543.g90eed137f3\n"},{"id":"371588","messageId":"20190315132545.GA24175@szeder.dev","threadId":"50501","inReplyTo":"20190315062243.GA13466@sigill.intra.peff.net","subject":"Re: [PATCH 1/2] t5310: correctly remove bitmaps for jgit test","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-03-15T13:25:45Z","receivedAt":"2019-03-15T13:25:55Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, Mar 15, 2019 at 02:22:44AM -0400, Jeff King wrote:\n> We use \"jgit gc\" to generate a pack bitmap file, and then make sure our\n> implementation can read it. To prepare the repo before running jgit, we\n> try to \"rm -f\" any existing bitmap files. But we got the path wrong;\n> we're in a bare repo, so looking in \".git/\" finds nothing. Our \"rm\"\n> doesn't complain because of the \"-f\", and when we run \"rev-list\" there\n> are two bitmap files (ours and jgit's).\n\nOh, indeed.\n\n> Our reader implementation will ignore one of the bitmap files, but it's\n> likely non-deterministic which one we will use. We'd prefer the one with\n> the more recent timestamp (just because of the way the packed_git list\n> is sorted), but in most test runs they'd have identical timestamps.\n> \n> So this was probably actually testing something useful about 50% of the\n> time, and other half just testing that we could read our own bitmaps\n> (which is covered elsewhere).\n\nAt least it was testing the right thing up until 87a6bb701a\n(t5310-pack-bitmaps: make JGit tests work with GIT_TEST_SPLIT_INDEX,\n2018-05-10) came along.\n\n\n> t/t5310-pack-bitmaps.sh | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n> \n> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index 82d7f7f6a5..44a038881a 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -269,7 +269,7 @@ test_expect_success JGIT 'we can read jgit bitmaps' '\n> \tgit clone --bare . compat-jgit.git &&\n> \t(\n> \t\tcd compat-jgit.git &&\n> -\t\trm -f .git/objects/pack/*.bitmap &&\n> +\t\trm -f objects/pack/*.bitmap &&\n> \t\tjgit gc &&\n> \t\tgit rev-list --test-bitmap HEAD\n> \t)\n> -- \n> 2.21.0.543.g90eed137f3\n> \n"},{"id":"371616","messageId":"20190315183627.GA4941@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190315132545.GA24175@szeder.dev","subject":"Re: [PATCH 1/2] t5310: correctly remove bitmaps for jgit test","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-03-15T18:36:28Z","receivedAt":"2019-03-15T18:36:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 15, 2019 at 02:25:45PM +0100, SZEDER Gábor wrote:\n\n> > Our reader implementation will ignore one of the bitmap files, but it's\n> > likely non-deterministic which one we will use. We'd prefer the one with\n> > the more recent timestamp (just because of the way the packed_git list\n> > is sorted), but in most test runs they'd have identical timestamps.\n> > \n> > So this was probably actually testing something useful about 50% of the\n> > time, and other half just testing that we could read our own bitmaps\n> > (which is covered elsewhere).\n> \n> At least it was testing the right thing up until 87a6bb701a\n> (t5310-pack-bitmaps: make JGit tests work with GIT_TEST_SPLIT_INDEX,\n> 2018-05-10) came along.\n\nHeh, indeed. I didn't even dig into the history, and just assumed I had\nbotched it in 2013. :)\n\n-Peff\n"},{"id":"373492","messageId":"87zhoz8b9o.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190314091254.nescpfp3n6mbjpmh@dcvr","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-04-09T15:10:43Z","receivedAt":"2019-04-09T15:10:50Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Mar 14 2019, Eric Wong wrote:\n\n> Jeff King wrote:\n>> On Wed, Mar 13, 2019 at 01:51:33AM +0000, Eric Wong wrote:\n>>\n>> > But I did find Ævar's forgotten gitperformance doc and thread\n>> > where the topic was brought up:\n>> >\n>> > https://public-inbox.org/git/20170403211644.26814-1-avarab@gmail.com/\n>>\n>> One thing that thread reminded me of: we probably also want to default\n>> pack.writebitmaphashcache on. Otherwise the time saved during the object\n>> enumeration can backfire when we spend much more time trying delta\n>> compression (because we don't know the pathnames of any objects).\n>\n> Interesting... I found a big improvement with public-inbox\n> just using bitmaps; but have never tried the hash cache.\n>\n>> The reason it defaults to off is for on-disk compatibility with JGit.\n>\n> Right. Our documentation seems to indicate JGit just warns (but\n> doesn't fall over), so maybe that can be considered separately.\n>\n> I've never used JGit myself; and was satisfied enough with\n> bitmaps alone that I never tried the hash-cache.\n>\n>> But I have very little experience running without the hash-cache on. We\n>> added it very early on because we found performance was not great\n>> without it (I don't know if people running JGit have run into the same\n>> problem and if not, why not).\n>\n> As far as serving clones and fetches, public-inbox-init has\n> always created bare repos with bitmaps enabled, but without\n> the hash-cache for compatibility concerns.\n>\n> That's a lot of fetches and clones over the years.\n>\n>> > +test_expect_success 'incremental repack does not complain' '\n>> > +\tgit -C bare.git repack -q 2>repack.err &&\n>> > +\t! test -s repack.err\n>> > +'\n>>\n>> This last line could use \"test_must_be_empty\".\n>\n> Thanks for the review!\n>\n> ---------8<-----------\n> Subject: [PATCH] repack: enable bitmaps by default on bare repos\n>\n> A typical use case for bare repos is for serving clones and\n> fetches to clients. Enable bitmaps by default on bare repos to\n> make it easier for admins to host git repos in a performant way.\n>\n> Signed-off-by: Eric Wong \n> Helped-by: Jeff King \n> ---\n> Documentation/config/repack.txt | 2 +-\n> builtin/repack.c | 5 ++++-\n> t/t7700-repack.sh | 19 ++++++++++++++++++-\n> 3 files changed, 23 insertions(+), 3 deletions(-)\n>\n> diff --git a/Documentation/config/repack.txt b/Documentation/config/repack.txt\n> index a5c37813fd..9c413e177e 100644\n> --- a/Documentation/config/repack.txt\n> +++ b/Documentation/config/repack.txt\n> @@ -24,4 +24,4 @@ repack.writeBitmaps::\n> \tpacks created for clones and fetches, at the cost of some disk\n> \tspace and extra time spent on the initial repack. This has\n> \tno effect if multiple packfiles are created.\n> -\tDefaults to false.\n> +\tDefaults to true on bare repos, false otherwise.\n> diff --git a/builtin/repack.c b/builtin/repack.c\n> index 67f8978043..caca113927 100644\n> --- a/builtin/repack.c\n> +++ b/builtin/repack.c\n> @@ -14,7 +14,7 @@\n>\n> static int delta_base_offset = 1;\n> static int pack_kept_objects = -1;\n> -static int write_bitmaps;\n> +static int write_bitmaps = -1;\n> static int use_delta_islands;\n> static char *packdir, *packtmp;\n>\n> @@ -343,6 +343,9 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n> \t (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n> \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n>\n> +\tif (write_bitmaps < 0)\n> +\t\twrite_bitmaps = (pack_everything & ALL_INTO_ONE) &&\n> +\t\t\t\t is_bare_repository();\n> \tif (pack_kept_objects < 0)\n> \t\tpack_kept_objects = write_bitmaps;\n>\n> diff --git a/t/t7700-repack.sh b/t/t7700-repack.sh\n> index 6162e2a8e6..86d05160a3 100755\n> --- a/t/t7700-repack.sh\n> +++ b/t/t7700-repack.sh\n> @@ -221,5 +221,22 @@ test_expect_success 'repack --keep-pack' '\n> \t)\n> '\n>\n> -test_done\n> +test_expect_success 'bitmaps are created by default in bare repos' '\n> +\tgit clone --bare .git bare.git &&\n> +\tgit -C bare.git repack -ad &&\n> +\tbitmap=$(ls bare.git/objects/pack/*.bitmap) &&\n> +\ttest_path_is_file \"$bitmap\"\n> +'\n> +\n> +test_expect_success 'incremental repack does not complain' '\n> +\tgit -C bare.git repack -q 2>repack.err &&\n> +\ttest_must_be_empty repack.err\n> +'\n>\n> +test_expect_success 'bitmaps can be disabled on bare repos' '\n> +\tgit -c repack.writeBitmaps=false -C bare.git repack -ad &&\n> +\tbitmap=$(ls bare.git/objects/pack/*.bitmap 2>/dev/null || :) &&\n> +\ttest -z \"$bitmap\"\n> +'\n> +\n> +test_done\n\nI've found a case where turning bitmaps on does horrible things for\nbitmap \"push\" performance.\n\nAs it turns out it's not related to this patch per-se, because I had a\n*.bitmap for other reasons, but replying to this because we'd presumably\nget the same thing in the bare repo case once this merges down.\n\nI can't share the repo, but I had a report where just a \"git push\" of a\ntopic branch that was 2/58 ahead/behind took ~2 minutes just in\n\"Enumerating objects\", but ~500ms without bitmaps.\n\nUsing a horrible \"print to stderr\"[1] monkeypatch I'd get without\nbitmaps and reported by trace2 / ts:\n\n Apr 09 16:45:15 16:45:15.365817 git.c:433 | d1 | main | cmd_name | | | | | pack-objects (push/pack-objects)\n Apr 09 16:45:15 16:45:15.366220 builtin/pack-objects.c:3493 | d1 | main | region_enter | r1 | 0.000928 | | pack-objects | label:enumerate-objects\n Apr 09 16:45:15 16:45:15.366241 builtin/pack-objects.c:3495 | d1 | main | region_enter | r1 | 0.000950 | | pack-objects | ..label:enumerate-objects-prepare-packing-data\n Apr 09 16:45:15 16:45:15.366384 builtin/pack-objects.c:3498 | d1 | main | region_leave | r1 | 0.001091 | 0.000141 | pack-objects | ..label:enumerate-objects-prepare-packing-data\n Apr 09 16:45:15 16:45:15.366394 builtin/pack-objects.c:3510 | d1 | main | region_enter | r1 | 0.001102 | | pack-objects | ..label:enumerate-objects-get-obj-list\n Apr 09 16:45:15 get obj list 1\n Apr 09 16:45:15 get obj list 2, did 29391 lines\n Apr 09 16:45:15 get obj list 3\n Apr 09 16:45:15 get obj list 4\n Apr 09 16:45:15 get obj list 5\n Apr 09 16:45:15 get obj list 6\n Apr 09 16:45:15 get obj list 7\n Apr 09 16:45:15 get obj list 8\n Apr 09 16:45:15 get obj list 9\n Apr 09 16:45:15 16:45:15.776559 builtin/pack-objects.c:3514 | d1 | main | region_leave | r1 | 0.411263 | 0.410161 | pack-objects | ..label:enumerate-objects-get-obj-list\n Apr 09 16:45:15 16:45:15.776577 builtin/pack-objects.c:3517 | d1 | main | region_enter | r1 | 0.411285 | | pack-objects | ..label:enumerate-objects-cleanup-preferred-base\n Apr 09 16:45:15 16:45:15.776584 builtin/pack-objects.c:3520 | d1 | main | region_leave | r1 | 0.411292 | 0.000007 | pack-objects | ..label:enumerate-objects-cleanup-preferred-base\n Apr 09 16:45:15 16:45:15.776605 builtin/pack-objects.c:3530 | d1 | main | region_leave | r1 | 0.411313 | 0.410385 | pack-objects | label:enumerate-objects\n Apr 09 16:45:15 16:45:15.776609 builtin/pack-objects.c:3542 | d1 | main | region_enter | r1 | 0.411318 | | pack-objects | label:write-pack-file\n Apr 09 16:45:15 16:45:15.794235 builtin/pack-objects.c:3544 | d1 | main | region_leave | r1 | 0.428942 | 0.017624 | pack-objects | label:write-pack-file\n\nBut with pack.useBitmaps=true:\n\n Apr 09 16:39:59 16:39:59.139022 git.c:433 | d1 | main | cmd_name | | | | | pack-objects (push/pack-objects)\n Apr 09 16:39:59 16:39:59.139398 builtin/pack-objects.c:3493 | d1 | main | region_enter | r1 | 0.000869 | | pack-objects | label:enumerate-objects\n Apr 09 16:39:59 16:39:59.139419 builtin/pack-objects.c:3495 | d1 | main | region_enter | r1 | 0.000892 | | pack-objects | ..label:enumerate-objects-prepare-packing-data\n Apr 09 16:39:59 16:39:59.139551 builtin/pack-objects.c:3498 | d1 | main | region_leave | r1 | 0.001023 | 0.000131 | pack-objects | ..label:enumerate-objects-prepare-packing-data\n Apr 09 16:39:59 16:39:59.139559 builtin/pack-objects.c:3510 | d1 | main | region_enter | r1 | 0.001032 | | pack-objects | ..label:enumerate-objects-get-obj-list\n Apr 09 16:39:59 get obj list 1\n Apr 09 16:39:59 get obj list 2, did 29392 lines\n Apr 09 16:39:59 get obj list 3\n Apr 09 16:39:59 prepping walk\n Apr 09 16:39:59 opening packed bitmap...\n Apr 09 16:39:59 opening packed bitmap done\n Apr 09 16:39:59 walking 29392 pending\n Apr 09 16:39:59 done walking 29392 pending\n Apr 09 16:39:59 prepare_bitmap_walk 3\n Apr 09 16:39:59 prepare_bitmap_walk 4\n Apr 09 16:39:59 prepare_bitmap_walk 5\n Apr 09 16:40:00 prepare_bitmap_walk 6\n Apr 09 16:40:00 prepare_bitmap_walk 6.1\n Apr 09 16:41:35 prepare_bitmap_walk 6.2\n Apr 09 16:41:35 prepare_bitmap_walk 7\n Apr 09 16:41:52 prepare_bitmap_walk 8\n Apr 09 16:41:52 walking?\n Apr 09 16:41:52 traversing\n Apr 09 16:41:52 traversing done\n Apr 09 16:41:52 16:41:52.091634 builtin/pack-objects.c:3514 | d1 | main | region_leave | r1 | 112.953099 | 112.952067 | pack-objects | ..label:enumerate-objects-get-obj-list\n Apr 09 16:41:52 16:41:52.091655 builtin/pack-objects.c:3517 | d1 | main | region_enter | r1 | 112.953128 | | pack-objects | ..label:enumerate-objects-cleanup-preferred-base\n Apr 09 16:41:52 16:41:52.091668 builtin/pack-objects.c:3520 | d1 | main | region_leave | r1 | 112.953141 | 0.000013 | pack-objects | ..label:enumerate-objects-cleanup-preferred-base\n Apr 09 16:41:52 16:41:52.091700 builtin/pack-objects.c:3530 | d1 | main | region_leave | r1 | 112.953172 | 112.952303 | pack-objects | label:enumerate-objects\n Apr 09 16:41:52 16:41:52.091706 builtin/pack-objects.c:3542 | d1 | main | region_enter | r1 | 112.953179 | | pack-objects | label:write-pack-file\n Apr 09 16:41:52 16:41:52.111966 builtin/pack-objects.c:3544 | d1 | main | region_leave | r1 | 112.973438 | 0.020259 | pack-objects | label:write-pack-file\n\nI.e. almost all the time is in get_object_list_from_bitmap() and around\n1m30s in just this in pack-bitmap.c:\n\n haves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n\nAnd then another ~20s in:\n\n wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n\nThis is with 10 packs and where only the largest (initial clone pack)\nhad a *.bitmap, but I can also reproduce with a 'git repack -A -d -b',\ni.e. with only one pack with a *.bitmap, although that makes it a bit\nbetter for the first bit, and almost completely cuts down on the time\nspent in the second phase:\n\n Apr 09 17:08:37 17:08:37.261507 builtin/pack-objects.c:3493 | d1 | main | region_enter | r1 | 0.000922 | | pack-objects | label:enumerate-objects\n Apr 09 17:08:37 17:08:37.261527 builtin/pack-objects.c:3495 | d1 | main | region_enter | r1 | 0.000943 | | pack-objects | ..label:enumerate-objects-prepare-packing-data\n Apr 09 17:08:37 17:08:37.261600 builtin/pack-objects.c:3498 | d1 | main | region_leave | r1 | 0.001015 | 0.000072 | pack-objects | ..label:enumerate-objects-prepare-packing-data\n Apr 09 17:08:37 17:08:37.261608 builtin/pack-objects.c:3510 | d1 | main | region_enter | r1 | 0.001024 | | pack-objects | ..label:enumerate-objects-get-obj-list\n Apr 09 17:08:37 get obj list 1\n Apr 09 17:08:37 get obj list 2, did 29380 lines\n Apr 09 17:08:37 get obj list 3\n Apr 09 17:08:37 prepping walk\n Apr 09 17:08:37 opening packed bitmap...\n Apr 09 17:08:37 opening packed bitmap done\n Apr 09 17:08:37 walking 29380 pending\n Apr 09 17:08:37 done walking 29380 pending\n Apr 09 17:08:37 prepare_bitmap_walk 3\n Apr 09 17:08:37 prepare_bitmap_walk 4\n Apr 09 17:08:37 prepare_bitmap_walk 5\n Apr 09 17:08:38 prepare_bitmap_walk 6\n Apr 09 17:08:38 prepare_bitmap_walk 6.1\n Apr 09 17:09:07 prepare_bitmap_walk 6.2\n Apr 09 17:09:07 prepare_bitmap_walk 7\n Apr 09 17:09:09 prepare_bitmap_walk 8\n Apr 09 17:09:09 walking?\n Apr 09 17:09:09 traversing\n Apr 09 17:09:09 traversing done\n Apr 09 17:09:09 17:09:09.229185 builtin/pack-objects.c:3514 | d1 | main | region_leave | r1 | 31.968595 | 31.967571 | pack-objects | ..label:enumerate-objects-get-obj-list\n Apr 09 17:09:09 17:09:09.229203 builtin/pack-objects.c:3517 | d1 | main | region_enter | r1 | 31.968619 | | pack-objects | ..label:enumerate-objects-cleanup-preferred-base\n Apr 09 17:09:09 17:09:09.229214 builtin/pack-objects.c:3520 | d1 | main | region_leave | r1 | 31.968630 | 0.000011 | pack-objects | ..label:enumerate-objects-cleanup-preferred-base\n Apr 09 17:09:09 17:09:09.229242 builtin/pack-objects.c:3530 | d1 | main | region_leave | r1 | 31.968658 | 31.967736 | pack-objects | label:enumerate-objects\n Apr 09 17:09:09 17:09:09.229265 builtin/pack-objects.c:3542 | d1 | main | region_enter | r1 | 31.968681 | | pack-objects | label:write-pack-file\n Apr 09 17:09:09 17:09:09.251998 builtin/pack-objects.c:3544 | d1 | main | region_leave | r1 | 31.991412 | 0.022731 | pack-objects | label:write-pack-file\n\nI don't have time to dig more into this now, just wanted to send these\ninitial results...\n\n1.\n\n\n\n diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n index a154fc29f6..8b2af1740e 100644\n --- a/builtin/pack-objects.c\n +++ b/builtin/pack-objects.c\n @@ -3052,2 +3052,3 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n {\n +\tfprintf(stderr, \"prepping walk\\n\");\n \tif (!(bitmap_git = prepare_bitmap_walk(revs)))\n @@ -3055,2 +3056,3 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n\n +\tfprintf(stderr, \"walking?\\n\");\n \tif (pack_options_allow_reuse() &&\n @@ -3066,3 +3068,5 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n\n +\tfprintf(stderr, \"traversing\\n\");\n \ttraverse_bitmap_commit_list(bitmap_git, &add_object_entry_from_bitmap);\n +\tfprintf(stderr, \"traversing done\\n\");\n \treturn 0;\n @@ -3091,2 +3095,3 @@ static void get_object_list(int ac, const char **av)\n \tint save_warning;\n +\tint lns = 0;\n\n @@ -3102,3 +3107,5 @@ static void get_object_list(int ac, const char **av)\n\n +\tfprintf(stderr, \"get obj list 1\\n\");\n \twhile (fgets(line, sizeof(line), stdin) != NULL) {\n +\t\tlns++;\n \t\tint len = strlen(line);\n @@ -3128,4 +3135,6 @@ static void get_object_list(int ac, const char **av)\n\n +\tfprintf(stderr, \"get obj list 2, did %d lines\\n\", lns);\n \twarn_on_object_refname_ambiguity = save_warning;\n\n +\tfprintf(stderr, \"get obj list 3\\n\");\n \tif (use_bitmap_index && !get_object_list_from_bitmap(&revs))\n @@ -3133,2 +3142,3 @@ static void get_object_list(int ac, const char **av)\n\n +\tfprintf(stderr, \"get obj list 4\\n\");\n \tif (use_delta_islands)\n @@ -3136,2 +3146,3 @@ static void get_object_list(int ac, const char **av)\n\n +\tfprintf(stderr, \"get obj list 5\\n\");\n \tif (prepare_revision_walk(&revs))\n @@ -3140,2 +3151,3 @@ static void get_object_list(int ac, const char **av)\n\n +\tfprintf(stderr, \"get obj list 6\\n\");\n \tif (!fn_show_object)\n @@ -3146,2 +3158,3 @@ static void get_object_list(int ac, const char **av)\n\n +\tfprintf(stderr, \"get obj list 7\\n\");\n \tif (unpack_unreachable_expiration) {\n @@ -3157,2 +3170,3 @@ static void get_object_list(int ac, const char **av)\n\n +\tfprintf(stderr, \"get obj list 8\\n\");\n \tif (keep_unreachable)\n @@ -3163,2 +3177,3 @@ static void get_object_list(int ac, const char **av)\n \t\tloosen_unused_packed_objects(&revs);\n +\tfprintf(stderr, \"get obj list 9\\n\");\n\n @@ -3478,3 +3493,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\t the_repository);\n +\ttrace2_region_enter(\"pack-objects\", \"enumerate-objects-prepare-packing-data\",\n +\t\t\t the_repository);\n \tprepare_packing_data(the_repository, &to_pack);\n +\ttrace2_region_leave(\"pack-objects\", \"enumerate-objects-prepare-packing-data\",\n +\t\t\t the_repository);\n\n @@ -3482,11 +3501,28 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\tprogress_state = start_progress(_(\"Enumerating objects\"), 0);\n -\tif (!use_internal_rev_list)\n +\tif (!use_internal_rev_list) {\n +\t\ttrace2_region_enter(\"pack-objects\", \"enumerate-objects-read-stdin\",\n +\t\t\t\t the_repository);\n \t\tread_object_list_from_stdin();\n -\telse {\n +\t\ttrace2_region_leave(\"pack-objects\", \"enumerate-objects-read-stdin\",\n +\t\t\t\t the_repository);\n +\t} else {\n +\t\ttrace2_region_enter(\"pack-objects\", \"enumerate-objects-get-obj-list\",\n +\t\t\t\t the_repository);\n \t\tget_object_list(rp.argc, rp.argv);\n \t\targv_array_clear(&rp);\n +\t\ttrace2_region_leave(\"pack-objects\", \"enumerate-objects-get-obj-list\",\n +\t\t\t\t the_repository);\n \t}\n +\ttrace2_region_enter(\"pack-objects\", \"enumerate-objects-cleanup-preferred-base\",\n +\t\t\t the_repository);\n \tcleanup_preferred_base();\n -\tif (include_tag && nr_result)\n +\ttrace2_region_leave(\"pack-objects\", \"enumerate-objects-cleanup-preferred-base\",\n +\t\t\t the_repository);\n +\tif (include_tag && nr_result) {\n +\t\ttrace2_region_enter(\"pack-objects\", \"enumerate-objects-add-tags\",\n +\t\t\t\t the_repository);\n \t\tfor_each_ref(add_ref_tag, NULL);\n +\t\ttrace2_region_leave(\"pack-objects\", \"enumerate-objects-add-tags\",\n +\t\t\t\t the_repository);\n +\t}\n \tstop_progress(&progress_state);\n diff --git a/pack-bitmap.c b/pack-bitmap.c\n index 4695aaf6b4..0ab71597fd 100644\n --- a/pack-bitmap.c\n +++ b/pack-bitmap.c\n @@ -693,5 +693,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t * because we may not need to use it */\n +\tfprintf(stderr, \"opening packed bitmap...\\n\");\n \tif (open_pack_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n +\tfprintf(stderr, \"opening packed bitmap done\\n\");\n\n +\tfprintf(stderr, \"walking %d pending\\n\", revs->pending.nr);\n \tfor (i = 0; i < revs->pending.nr; ++i) {\n @@ -720,2 +723,3 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t}\n +\tfprintf(stderr, \"done walking %d pending\\n\", revs->pending.nr);\n\n @@ -726,2 +730,3 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t */\n +\tfprintf(stderr, \"prepare_bitmap_walk 3\\n\");\n \tif (haves && !in_bitmapped_pack(bitmap_git, haves))\n @@ -729,2 +734,3 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n\n +\tfprintf(stderr, \"prepare_bitmap_walk 4\\n\");\n \t/* if we don't want anything, we're done here */\n @@ -738,2 +744,3 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t */\n +\tfprintf(stderr, \"prepare_bitmap_walk 5\\n\");\n \tif (load_pack_bitmap(bitmap_git) < 0)\n @@ -741,2 +748,3 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n\n +\tfprintf(stderr, \"prepare_bitmap_walk 6\\n\");\n \tobject_array_clear(&revs->pending);\n @@ -745,3 +753,5 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t\trevs->ignore_missing_links = 1;\n + \t\tfprintf(stderr, \"prepare_bitmap_walk 6.1\\n\");\n \t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n + \t\tfprintf(stderr, \"prepare_bitmap_walk 6.2\\n\");\n \t\treset_revision_walk();\n @@ -752,4 +762,6 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t}\n +\tfprintf(stderr, \"prepare_bitmap_walk 7\\n\");\n\n \twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n +\tfprintf(stderr, \"prepare_bitmap_walk 8\\n\");\n\n diff --git a/revision.c b/revision.c\n index eb8e51bc63..4592d01ee7 100644\n --- a/revision.c\n +++ b/revision.c\n @@ -63,2 +63,4 @@ static void mark_tree_contents_uninteresting(struct repository *r,\n\n +\tfprintf(stderr, \"MTCU\\n\");\n +\n \tif (parse_tree_gently(tree, 1) < 0)\n @@ -167,2 +169,4 @@ static void add_children_by_path(struct repository *r,\n\n +\tfprintf(stderr, \"ACBP\\n\");\n +\n \tif (!tree)\n"},{"id":"373620","messageId":"20190410225721.GA32262@sigill.intra.peff.net","threadId":"50501","inReplyTo":"87zhoz8b9o.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-10T22:57:21Z","receivedAt":"2019-04-10T22:57:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 09, 2019 at 05:10:43PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> I've found a case where turning bitmaps on does horrible things for\n> bitmap \"push\" performance.\n> [...]\n> I can't share the repo, but I had a report where just a \"git push\" of a\n> topic branch that was 2/58 ahead/behind took ~2 minutes just in\n> \"Enumerating objects\", but ~500ms without bitmaps.\n\nThat's pretty bad, though I'm not terribly surprised. The worst cases\nare ones where we have to traverse a lot to fill in the bitmap. So\neither there are a lot of commits newer than the bitmapped pack, or\nwe've done a bad job of picking old commits to bitmap, requiring us to\nwalk back to find all of the reachable objects (until we find something\nthat does have a bitmap).\n\nAnd \"bad\" here is somewhat subjective. The other side told us some\n\"have\" lines, and those are what we have to walk back from. _Usually_\nthose would correspond to ref tips, and the bitmap code tries to put a\nbitmap at each ref tip. But if you have tons of refs, it can't always do\nso.\n\n> I.e. almost all the time is in get_object_list_from_bitmap() and around\n> 1m30s in just this in pack-bitmap.c:\n> \n> haves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n> \n> And then another ~20s in:\n> \n> wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n\nYeah, that's where I'd expect the time to go. Inside find_objects()\nwe'll call traverse_commit_list() to do the actual walk.\n\nThe first walk for \"haves\" is looking mostly at old commits. Stuff that\nis mentioned in the pack, but for which we have to walk to find the\nbitmap.\n\nThe second walk for wants is probably mostly looking at new commits.\nThings that don't have a bitmap yet, and for which we have to walk\n(though it's interesting that it's so much more expensive than the\nnon-bitmap walk, which has to fully enumerate those trees itself; that\nimplies that some of the \"haves\" are recent, too, with respect to the\nlast pack).\n\n> This is with 10 packs and where only the largest (initial clone pack)\n> had a *.bitmap, but I can also reproduce with a 'git repack -A -d -b',\n> i.e. with only one pack with a *.bitmap, although that makes it a bit\n> better for the first bit, and almost completely cuts down on the time\n> spent in the second phase:\n\nYeah, that makes sense. By repacking you've taken all those new commits\nand included them in on-disk bitmaps. So I'd expect the \"wants\" to get\nmuch shorter, but the \"haves\" phase staying long means we could do a\nbetter job of picking commits to have on-disk bitmaps.\n\nSo two avenues for exploration I think:\n\n 1. I've long suspected that the bitmap selection code isn't ideal.\n Both in terms of what it picks, but also in its runtime (I think it\n ends up walking the same slices of history multiple times in some\n cases).\n\n 2. The answer we get from a bitmap versus a regular traversal are not\n apples-to-apples equivalent. The regular traversal walks down to\n the UNINTERESTING commits, marks the boundaries trees and blobs as\n UNINTERESTING, and then adds in all the interesting trees and blobs\n minus the UNINTERESTING parts. So it can sometimes give the wrong\n answer, claiming something is interesting when it is not.\n\n Whereas with bitmaps we fill in the trees and blobs as we walk, and\n you get the true answer. But it means we may open up a lot more\n trees than the equivalent traversal would.\n\n So one thing I've never really experimented with (and indeed, never\n really thought about until writing this email) is that the bitmaps\n could try to do that looser style of traversal, knowing that we\n might err on the side of calling things interesting in a few cases.\n But hopefully spending a lot less time opening trees.\n\n I'm not even 100% sure what that would look like in code, but just\n thinking about it from a high level, I don't there's a particular\n mathematical reason it couldn't work.\n\n-Peff\n"},{"id":"373880","messageId":"49e2aa9b-ff22-a8d1-ba72-1c881ff5fab4@gmail.com","threadId":"50501","inReplyTo":"20190214043743.GB19183@sigill.intra.peff.net","subject":"Re: [PATCH 2/3] prune: use bitmaps for reachability traversal","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-04-15T15:00:45Z","receivedAt":"2019-04-15T15:00:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/13/2019 11:37 PM, Jeff King wrote:\n> +static void *lookup_object_by_type(struct repository *r,\n> +\t\t\t\t const struct object_id *oid,\n> +\t\t\t\t enum object_type type)\n> +{\n> +\tswitch (type) {\n> +\tcase OBJ_COMMIT:\n> +\t\treturn lookup_commit(r, oid);\n> +\tcase OBJ_TREE:\n> +\t\treturn lookup_tree(r, oid);\n> +\tcase OBJ_TAG:\n> +\t\treturn lookup_tag(r, oid);\n> +\tcase OBJ_BLOB:\n> +\t\treturn lookup_blob(r, oid);\n> +\tdefault:\n> +\t\tdie(\"BUG: unknown object type %d\", type);\n> +\t}\n> +}\n> +\n> +static int mark_object_seen(const struct object_id *oid,\n> +\t\t\t enum object_type type,\n> +\t\t\t int exclude,\n> +\t\t\t uint32_t name_hash,\n> +\t\t\t struct packed_git *found_pack,\n> +\t\t\t off_t found_offset)\n> +{\n> +\tstruct object *obj = lookup_object_by_type(the_repository, oid, type);\n> +\tif (!obj)\n> +\t\tdie(\"unable to create object '%s'\", oid_to_hex(oid));\n> +\n> +\tobj->flags |= SEEN;\n> +\treturn 0;\n> +}\n> +\n> void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n> \t\t\t timestamp_t mark_recent, struct progress *progress)\n> {\n> \tstruct connectivity_progress cp;\n> +\tstruct bitmap_index *bitmap_git;\n> \n> \t/*\n> \t * Set up revision parsing, and mark us as being interested\n> @@ -188,6 +223,13 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n> \tcp.progress = progress;\n> \tcp.count = 0;\n> \n> +\tbitmap_git = prepare_bitmap_walk(revs);\n> +\tif (bitmap_git) {\n> +\t\ttraverse_bitmap_commit_list(bitmap_git, mark_object_seen);\n> +\t\tfree_bitmap_index(bitmap_git);\n> +\t\treturn;\n> +\t}\n> +\n\nPeff,\n\nThis block after \"if (bitmap_git)\" is not exercised by the (non-performance)\ntest suite, so the rest of the code above is not tested, either. Could a test\nof this \"prune\" capability be added to the regression tests around the bitmaps?\n\nThanks,\n-Stolee\n"},{"id":"374131","messageId":"20190418194953.GA15249@sigill.intra.peff.net","threadId":"50501","inReplyTo":"49e2aa9b-ff22-a8d1-ba72-1c881ff5fab4@gmail.com","subject":"Re: [PATCH 2/3] prune: use bitmaps for reachability traversal","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-18T19:49:53Z","receivedAt":"2019-04-18T19:50:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Apr 15, 2019 at 11:00:45AM -0400, Derrick Stolee wrote:\n\n> > void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n> > \t\t\t timestamp_t mark_recent, struct progress *progress)\n> [...]\n> > \tcp.progress = progress;\n> > \tcp.count = 0;\n> > \n> > +\tbitmap_git = prepare_bitmap_walk(revs);\n> > +\tif (bitmap_git) {\n> > +\t\ttraverse_bitmap_commit_list(bitmap_git, mark_object_seen);\n> > +\t\tfree_bitmap_index(bitmap_git);\n> > +\t\treturn;\n> > +\t}\n> > +\n> \n> This block after \"if (bitmap_git)\" is not exercised by the (non-performance)\n> test suite, so the rest of the code above is not tested, either. Could a test\n> of this \"prune\" capability be added to the regression tests around the bitmaps?\n\nI have somewhat mixed feelings here. We can add a test with a trivial\nbitmap to get code coverage here. But as with many optimizations\n(bitmaps, but also your commit graph work), we get a much more thorough\ncorrectness test by re-running the whole test suite (though we do not\nyet have one for running with bitmaps on), and a better test that the\noptimization is kicking in and working via the t/perf tests.\n\nI dunno. I guess it does not hurt to at least to at least make sure this\ncode is running in the normal suite. I don't think that will find the\nmore interesting regressions, but at least saves us the from the most\negregious ones (\"oops, the whole thing segfaults because somebody\nchanged the API\" kinds of things).\n\n-Peff\n"},{"id":"374132","messageId":"20190418200827.GB15249@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190418194953.GA15249@sigill.intra.peff.net","subject":"[PATCH] t5304: add a test for pruning with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-18T20:08:27Z","receivedAt":"2019-04-18T20:08:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 18, 2019 at 03:49:53PM -0400, Jeff King wrote:\n\n> > This block after \"if (bitmap_git)\" is not exercised by the (non-performance)\n> > test suite, so the rest of the code above is not tested, either. Could a test\n> > of this \"prune\" capability be added to the regression tests around the bitmaps?\n> \n> I have somewhat mixed feelings here. We can add a test with a trivial\n> bitmap to get code coverage here. But as with many optimizations\n> (bitmaps, but also your commit graph work), we get a much more thorough\n> correctness test by re-running the whole test suite (though we do not\n> yet have one for running with bitmaps on), and a better test that the\n> optimization is kicking in and working via the t/perf tests.\n> \n> I dunno. I guess it does not hurt to at least to at least make sure this\n> code is running in the normal suite. I don't think that will find the\n> more interesting regressions, but at least saves us the from the most\n> egregious ones (\"oops, the whole thing segfaults because somebody\n> changed the API\" kinds of things).\n\nSo here's a test. This goes on top of jk/prune-optim (which is also\nalready in master).\n\n-- >8 --\nSubject: [PATCH] t5304: add a test for pruning with bitmaps\n\nCommit fde67d6896 (prune: use bitmaps for reachability traversal,\n2019-02-13) uses bitmaps for pruning when they're available, but only\ncovers this functionality in the t/perf tests. This makes a kind of\nsense, since the point is that the behaviour is indistinguishable before\nand after the patch, just faster.\n\nBut since the bitmap code path is not exercised at all in the regular\ntest suite, it leaves us open to a regression where the behavior does in\nfact change. The most thorough way to test that would be running the\nwhole suite with bitmaps enabled. But we don't yet have a way to do\nthat, and anyway it's expensive to do so. Let's at least add a basic\ntest that exercises this path and make sure we prune an object we should\n(and not one that we shouldn't).\n\nThat would hopefully catch the most obvious breakages early.\n\nSigned-off-by: Jeff King \n---\n t/t5304-prune.sh | 8 ++++++++\n 1 file changed, 8 insertions(+)\n\ndiff --git a/t/t5304-prune.sh b/t/t5304-prune.sh\nindex 1eeb828a15..df60f18fb8 100755\n--- a/t/t5304-prune.sh\n+++ b/t/t5304-prune.sh\n@@ -341,4 +341,12 @@ test_expect_success 'prune: handle expire option correctly' '\n \tgit prune --no-expire\n '\n \n+test_expect_success 'trivial prune with bitmaps enabled' '\n+\tgit repack -adb &&\n+\tblob=$(echo bitmap-unreachable-blob | git hash-object -w --stdin) &&\n+\tgit prune --expire=now &&\n+\tgit cat-file -e HEAD &&\n+\ttest_must_fail git cat-file -e $blob\n+'\n+\n test_done\n-- \n2.21.0.1090.g9d17dac192\n\n"},{"id":"374169","messageId":"ba16afb4-25c1-8148-602e-130b0e17fc89@gmail.com","threadId":"50501","inReplyTo":"20190418200827.GB15249@sigill.intra.peff.net","subject":"Re: [PATCH] t5304: add a test for pruning with bitmaps","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-04-20T01:01:50Z","receivedAt":"2019-04-20T01:03:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/18/2019 4:08 PM, Jeff King wrote:\n> On Thu, Apr 18, 2019 at 03:49:53PM -0400, Jeff King wrote:\n>> I dunno. I guess it does not hurt to at least to at least make sure this\n>> code is running in the normal suite. I don't think that will find the\n>> more interesting regressions, but at least saves us the from the most\n>> egregious ones (\"oops, the whole thing segfaults because somebody\n>> changed the API\" kinds of things).\n\nThat's the level of coverage I was hoping to see. I won't be picky if\nthe OBJ_TAG case isn't hit or something.\n\n> So here's a test. This goes on top of jk/prune-optim (which is also\n> already in master).\n\n[snip]\n\n> +test_expect_success 'trivial prune with bitmaps enabled' '\n> +\tgit repack -adb &&\n> +\tblob=$(echo bitmap-unreachable-blob | git hash-object -w --stdin) &&\n> +\tgit prune --expire=now &&\n> +\tgit cat-file -e HEAD &&\n> +\ttest_must_fail git cat-file -e $blob\n> +'\n> +\n> test_done\n\nThis test does cover the 'mark_object_seen()' method, which I tested by\nremoving the \"!\" in the \"if (!obj) die();\" condition.\n\nHowever, my first inclination was to remove the line\n\n\tobj->flags |= SEEN;\n\nfrom the method, and I found that it still worked! This was confusing,\nso I looked for places where the SEEN flag was added during bitmap walks,\nand it turns out that the objects are marked as SEEN by prepare_bitmap_walk().\n\nThis means that we can remove a lot of the implementation from reachable.c\nand have the same effect (and drop an iteration through the objects). See the\ndiff below.\n\nThoughts?\n-Stolee\n\n-->8--\n\ndiff --git a/reachable.c b/reachable.c\nindex 0d00a91de4..7d2762d47f 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -159,39 +159,6 @@ int add_unseen_recent_objects_to_traversal(struct rev_info *revs,\n FOR_EACH_OBJECT_LOCAL_ONLY);\n }\n\n-static void *lookup_object_by_type(struct repository *r,\n- const struct object_id *oid,\n- enum object_type type)\n-{\n- switch (type) {\n- case OBJ_COMMIT:\n- return lookup_commit(r, oid);\n- case OBJ_TREE:\n- return lookup_tree(r, oid);\n- case OBJ_TAG:\n- return lookup_tag(r, oid);\n- case OBJ_BLOB:\n- return lookup_blob(r, oid);\n- default:\n- die(\"BUG: unknown object type %d\", type);\n- }\n-}\n-\n-static int mark_object_seen(const struct object_id *oid,\n- enum object_type type,\n- int exclude,\n- uint32_t name_hash,\n- struct packed_git *found_pack,\n- off_t found_offset)\n-{\n- struct object *obj = lookup_object_by_type(the_repository, oid, type);\n- if (!obj)\n- die(\"unable to create object '%s'\", oid_to_hex(oid));\n-\n- obj->flags |= SEEN;\n- return 0;\n-}\n-\n void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n timestamp_t mark_recent, struct progress *progress)\n {\n@@ -225,7 +192,10 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n\n bitmap_git = prepare_bitmap_walk(revs);\n if (bitmap_git) {\n- traverse_bitmap_commit_list(bitmap_git, mark_object_seen);\n+ /*\n+ * reachable objects are marked as SEEN\n+ * by prepare_bitmap_walk(revs).\n+ */\n free_bitmap_index(bitmap_git);\n return;\n }\n"},{"id":"374170","messageId":"20190420032435.GA3559@sigill.intra.peff.net","threadId":"50501","inReplyTo":"ba16afb4-25c1-8148-602e-130b0e17fc89@gmail.com","subject":"Re: [PATCH] t5304: add a test for pruning with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-20T03:24:35Z","receivedAt":"2019-04-20T03:24:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 19, 2019 at 09:01:50PM -0400, Derrick Stolee wrote:\n\n> > +test_expect_success 'trivial prune with bitmaps enabled' '\n> > +\tgit repack -adb &&\n> > +\tblob=$(echo bitmap-unreachable-blob | git hash-object -w --stdin) &&\n> > +\tgit prune --expire=now &&\n> > +\tgit cat-file -e HEAD &&\n> > +\ttest_must_fail git cat-file -e $blob\n> > +'\n> > +\n> > test_done\n> \n> This test does cover the 'mark_object_seen()' method, which I tested by\n> removing the \"!\" in the \"if (!obj) die();\" condition.\n> \n> However, my first inclination was to remove the line\n> \n> \tobj->flags |= SEEN;\n> \n> from the method, and I found that it still worked! This was confusing,\n> so I looked for places where the SEEN flag was added during bitmap walks,\n> and it turns out that the objects are marked as SEEN by prepare_bitmap_walk().\n\nI think this is only _some_ objects. The full bitmap is created by\nreading the on-disk bitmaps, and then filling in any necessary gaps by\ndoing a traditional traversal. We also set it on tip objects to de-dup\nthe initial revs->pending list.\n\nTry running t5304 with this:\n\ndiff --git a/reachable.c b/reachable.c\nindex eba6f64e01..7ec73ef43f 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -191,6 +191,8 @@ static int mark_object_seen(const struct object_id *oid,\n \tif (!obj)\n \t\tdie(\"unable to create object '%s'\", oid_to_hex(oid));\n \n+\tif (!(obj->flags & SEEN))\n+\t\tdie(\"seen flag not already there\");\n \tobj->flags |= SEEN;\n \treturn 0;\n }\n\nwhich shows that we are indeed freshly setting SEEN on some objects.\n\nInterestingly, I don't _think_ you can cause an object to get pruned\naccidentally here, because:\n\n 1. Any object that will miss its SEEN has to be in the bitmapped pack,\n and not found through normal traversal.\n\n 2. git-prune only removes loose objects, not packed ones.\n\n 3. Loose objects cannot be in the bitmapped pack. Therefore, no object\n can hit both cases (1) and (2).\n\nEven if that were the end of the story, I don't think I'd want to rely\non it here. The post-condition of the function should be that SEEN is\nset on all reachable objects, whether bitmaps are used or not. And we do\nindeed use this elsewhere:\n\nWe'll later call prune_shallow(), which uses SEEN to discard unreachable\nentries. I'm not sure it even makes sense to have a shallow repo with\nbitmaps, though. Obviously we're lacking the full graph, but I wouldn't\nbe surprised if the shallow code quietly pretends that all is well and\nwe generate bogus bitmaps or something. Or maybe it even mostly works as\nlong as you don't walk over the shallow cut-points.\n\nmark_reachable_objects() is also used for reflog expiration with\n--stale-fix. I tried generating a test that would fail with your patch,\nbut I think it's not quite possible, because --stale-fix will do a\nfollow-up walk of the graph to see which objects mentioned in the reflog\nwe have and do not have. So it doesn't actually break things, it just\nmakes them slower (because we erroneously fail to mark SEEN things that\nit's then forced to walk).\n\nSo I don't _think_ your patch actually breaks anything user-visible, but\nit's a bit like leaving a live grenade in your living room for somebody\nto find.\n\nAnd I think we are indeed covering lookup_object_by_type(), etc in the\nt5304 test I added. So AFAICT all of the new code is covered after that?\n\n-Peff\n"},{"id":"374176","messageId":"78a60be8-414e-cd32-8eb2-36b47702c10d@gmail.com","threadId":"50501","inReplyTo":"20190420032435.GA3559@sigill.intra.peff.net","subject":"Re: [PATCH] t5304: add a test for pruning with bitmaps","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-04-20T21:01:23Z","receivedAt":"2019-04-20T21:02:11Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/19/2019 11:24 PM, Jeff King wrote:\n> Try running t5304 with this:\n> \n> diff --git a/reachable.c b/reachable.c\n> index eba6f64e01..7ec73ef43f 100644\n> --- a/reachable.c\n> +++ b/reachable.c\n> @@ -191,6 +191,8 @@ static int mark_object_seen(const struct object_id *oid,\n> \tif (!obj)\n> \t\tdie(\"unable to create object '%s'\", oid_to_hex(oid));\n> \n> +\tif (!(obj->flags & SEEN))\n> +\t\tdie(\"seen flag not already there\");\n> \tobj->flags |= SEEN;\n> \treturn 0;\n> }\n> \n> which shows that we are indeed freshly setting SEEN on some objects.\n\nGood point! Thanks for clearing that up for me.\n \n> Interestingly, I don't _think_ you can cause an object to get pruned\n> accidentally here, because:\n\n[snip]\n\nI appreciate the additional context that you gave (and I snipped). This\nmakes me comfortable accepting this test as an exercise of the code (to\nguard against future changes that create failures like null-refs) and we\nwill need to rely on the performance suite to catch issues like removing\nthe SEEN markers that I had tested.\n\nThanks,\n-Stolee\n\n"},{"id":"374459","messageId":"xmqq1s1qy2ox.fsf@gitster-ct.c.googlers.com","threadId":"50501","inReplyTo":"20190410225721.GA32262@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-04-25T07:16:46Z","receivedAt":"2019-04-25T07:16:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Apr 09, 2019 at 05:10:43PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> I've found a case where turning bitmaps on does horrible things for\n>> bitmap \"push\" performance.\n>> [...]\n>> I can't share the repo, but I had a report where just a \"git push\" of a\n>> topic branch that was 2/58 ahead/behind took ~2 minutes just in\n>> \"Enumerating objects\", but ~500ms without bitmaps.\n>\n> That's pretty bad, though I'm not terribly surprised.\n\nI was revisiting the recent \"What's cooking\" report, and I am not\nsure what the current status of the topic is.\n\nI do not get a feel that the current bitmap implementation has been\nwidely used in repositories that have vastly different access\npatterns---it probably has been tried only by those who can afford\nthe engineering cost to see if the implementation happens to work\nwell for their workload and some may have chosen to adopt it while\nothers didn't. So it may be very well tuned for the former people\nbut once we merge this topic down, we'll hear from others with quite\ndifferent workload, which may lead to us tuning the code to bit\nbetter to their workload while not hurting other existing users,\nhopefully.\n\nOr not.\n\nI am somewhat tempted to make things more exciting by merging it to\n'next' soonish, but I guess Ævar and you are not quite ready for\nthat excitement yet, judging from the following (which looks quite\nsensible suggestions)?\n\nThanks.\n\n> Yeah, that makes sense. By repacking you've taken all those new commits\n> and included them in on-disk bitmaps. So I'd expect the \"wants\" to get\n> much shorter, but the \"haves\" phase staying long means we could do a\n> better job of picking commits to have on-disk bitmaps.\n>\n> So two avenues for exploration I think:\n>\n> 1. I've long suspected that the bitmap selection code isn't ideal.\n> Both in terms of what it picks, but also in its runtime (I think it\n> ends up walking the same slices of history multiple times in some\n> cases).\n>\n> 2. The answer we get from a bitmap versus a regular traversal are not\n> apples-to-apples equivalent. The regular traversal walks down to\n> the UNINTERESTING commits, marks the boundaries trees and blobs as\n> UNINTERESTING, and then adds in all the interesting trees and blobs\n> minus the UNINTERESTING parts. So it can sometimes give the wrong\n> answer, claiming something is interesting when it is not.\n>\n> Whereas with bitmaps we fill in the trees and blobs as we walk, and\n> you get the true answer. But it means we may open up a lot more\n> trees than the equivalent traversal would.\n>\n> So one thing I've never really experimented with (and indeed, never\n> really thought about until writing this email) is that the bitmaps\n> could try to do that looser style of traversal, knowing that we\n> might err on the side of calling things interesting in a few cases.\n> But hopefully spending a lot less time opening trees.\n>\n> I'm not even 100% sure what that would look like in code, but just\n> thinking about it from a high level, I don't there's a particular\n> mathematical reason it couldn't work.\n>\n> -Peff\n"},{"id":"374895","messageId":"20190504013713.GC17551@sigill.intra.peff.net","threadId":"50501","inReplyTo":"xmqq1s1qy2ox.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-04T01:37:13Z","receivedAt":"2019-05-04T01:42:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 25, 2019 at 04:16:46PM +0900, Junio C Hamano wrote:\n\n> I was revisiting the recent \"What's cooking\" report, and I am not\n> sure what the current status of the topic is.\n> \n> I do not get a feel that the current bitmap implementation has been\n> widely used in repositories that have vastly different access\n> patterns---it probably has been tried only by those who can afford\n> the engineering cost to see if the implementation happens to work\n> well for their workload and some may have chosen to adopt it while\n> others didn't. So it may be very well tuned for the former people\n> but once we merge this topic down, we'll hear from others with quite\n> different workload, which may lead to us tuning the code to bit\n> better to their workload while not hurting other existing users,\n> hopefully.\n> \n> Or not.\n\nNote that Ævar's case was somebody running bitmaps locally and trying to\npush, which I think is generally not a good match for bitmaps (even when\nthey work, they cost more to generate than what you save if you're only\npushing once).\n\nThe goal of Eric's patch was that by kicking in for bare repos, we'd\nmostly be hitting servers that are serving up fetches. So if by\n\"workload\" you mean that we some people might use bare repos for other\ncases, yeah, there's a potential for confusion or regression there.\n\nIf you mean that bitmaps might not work for some workloads even when\nwe're serving a lot of fetches, I won't say that's _not_ true, but my\nexperience is that they are generally a net win. Both for the smaller\nrepositories we see on github.com, but also for big, busy ones that our\non-premises customers use.\n\n Actually, there is one curiosity with Eric's patch that I haven't\n tested. As I've mentioned before, we store \"forks\" as single\n repositories pointing to a single shared alternates repository. Since\n the bitmap code only handles one .bitmap per invocation, you really\n want just one big one in the shared repo. If \"git repack\" in the forks\n started generating one, that would be surprising and annoying.\n\n In practice this is a pretty extreme corner case. And a lot would\n depend on how you're using \"repack\" in the fork (e.g., a partial\n repack would know that it can't generate bitmaps anyway). I'm pretty\n sure it would not even impact our setup at all, but I can probably\n come up with a devils advocate one where it would.\n\n> I am somewhat tempted to make things more exciting by merging it to\n> 'next' soonish, but I guess Ævar and you are not quite ready for\n> that excitement yet, judging from the following (which looks quite\n> sensible suggestions)?\n\nIt's OK with me for this to go to 'next'. Note that the other two\npatches from me could actually graduate separately. One is a\nstraight-out test fix, and the other should always be a win (and does\nnothing if you're not already generating bitmaps).\n\nBy the way, there were some timing puzzles mentioned in that second\ncommit. I re-ran them today and everything was what I'd expect. So I\nwonder if I just screwed up the timings before. I can re-write that\ncommit message if it hasn't made it to 'next' yet.\n\n-Peff\n"},{"id":"374896","messageId":"87a7g2iuem.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190504013713.GC17551@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-04T06:52:01Z","receivedAt":"2019-05-04T06:52:07Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sat, May 04 2019, Jeff King wrote:\n\n> On Thu, Apr 25, 2019 at 04:16:46PM +0900, Junio C Hamano wrote:\n>\n>> I was revisiting the recent \"What's cooking\" report, and I am not\n>> sure what the current status of the topic is.\n>>\n>> I do not get a feel that the current bitmap implementation has been\n>> widely used in repositories that have vastly different access\n>> patterns---it probably has been tried only by those who can afford\n>> the engineering cost to see if the implementation happens to work\n>> well for their workload and some may have chosen to adopt it while\n>> others didn't. So it may be very well tuned for the former people\n>> but once we merge this topic down, we'll hear from others with quite\n>> different workload, which may lead to us tuning the code to bit\n>> better to their workload while not hurting other existing users,\n>> hopefully.\n>>\n>> Or not.\n>\n> Note that Ævar's case was somebody running bitmaps locally and trying to\n> push, which I think is generally not a good match for bitmaps (even when\n> they work, they cost more to generate than what you save if you're only\n> pushing once).\n\nRight. It was *not* caused by this \"enable bitmaps by default on bare\nrepos\" patch (which I wasn't even running with), but *is* indicative of\na pretty big edge case with enabling bitmaps that *will* happen for some\non such bare repos if we ship the patch.\n\n> The goal of Eric's patch was that by kicking in for bare repos, we'd\n> mostly be hitting servers that are serving up fetches. So if by\n> \"workload\" you mean that we some people might use bare repos for other\n> cases, yeah, there's a potential for confusion or regression there.\n\nAs noted I suspect that's a really rare use-case in practice, and in\nreply to Junio's upthread I\nthink it's fine to just try this. Maybe we'll finally get such use-cases\nout of the woodworks by turning it on by default.\n\nAs an aside this is the Nth time I notice how crappy that \"Enumerating\nobjects\" progress bar is. We do a *lot* of things there, including this\nbitmap calculation.\n\nBut just splitting it up might result in either no progress (all\nindividually below 2 seconds), or a lot of noise as you have 20 things\nthat each take 2 seconds. I wonder if someone's looked at supporting:\n\n Enumerating Objects (X%) => Calculating bitmaps (Y%)\n\nWhere X% is the total progres, and %Y is the sub-progress. I eyeballed\ndoing this once by \"chaining\" the progress structs, but there's probably\na less crappy way...\n\n\n> If you mean that bitmaps might not work for some workloads even when\n> we're serving a lot of fetches, I won't say that's _not_ true, but my\n> experience is that they are generally a net win. Both for the smaller\n> repositories we see on github.com, but also for big, busy ones that our\n> on-premises customers use.\n>\n> Actually, there is one curiosity with Eric's patch that I haven't\n> tested. As I've mentioned before, we store \"forks\" as single\n> repositories pointing to a single shared alternates repository. Since\n> the bitmap code only handles one .bitmap per invocation, you really\n> want just one big one in the shared repo. If \"git repack\" in the forks\n> started generating one, that would be surprising and annoying.\n>\n> In practice this is a pretty extreme corner case. And a lot would\n> depend on how you're using \"repack\" in the fork (e.g., a partial\n> repack would know that it can't generate bitmaps anyway). I'm pretty\n> sure it would not even impact our setup at all, but I can probably\n> come up with a devils advocate one where it would.\n>\n>> I am somewhat tempted to make things more exciting by merging it to\n>> 'next' soonish, but I guess Ævar and you are not quite ready for\n>> that excitement yet, judging from the following (which looks quite\n>> sensible suggestions)?\n>\n> It's OK with me for this to go to 'next'. Note that the other two\n> patches from me could actually graduate separately. One is a\n> straight-out test fix, and the other should always be a win (and does\n> nothing if you're not already generating bitmaps).\n>\n> By the way, there were some timing puzzles mentioned in that second\n> commit. I re-ran them today and everything was what I'd expect. So I\n> wonder if I just screwed up the timings before. I can re-write that\n> commit message if it hasn't made it to 'next' yet.\n>\n> -Peff\n"},{"id":"374899","messageId":"20190504132346.GK14763@szeder.dev","threadId":"50501","inReplyTo":"87a7g2iuem.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-04T13:23:47Z","receivedAt":"2019-05-04T13:23:53Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Sat, May 04, 2019 at 08:52:01AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> As an aside this is the Nth time I notice how crappy that \"Enumerating\n> objects\" progress bar is.\n\nAnd don't forget that the commit-graph progress bar still prints\nnonsense :)\n\n https://public-inbox.org/git/87ef6ydds8.fsf@evledraar.gmail.com/\n\n"},{"id":"374995","messageId":"20190507074506.GF28060@sigill.intra.peff.net","threadId":"50501","inReplyTo":"87a7g2iuem.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-07T07:45:06Z","receivedAt":"2019-05-07T07:45:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, May 04, 2019 at 08:52:01AM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > Note that Ævar's case was somebody running bitmaps locally and trying to\n> > push, which I think is generally not a good match for bitmaps (even when\n> > they work, they cost more to generate than what you save if you're only\n> > pushing once).\n> \n> Right. It was *not* caused by this \"enable bitmaps by default on bare\n> repos\" patch (which I wasn't even running with), but *is* indicative of\n> a pretty big edge case with enabling bitmaps that *will* happen for some\n> on such bare repos if we ship the patch.\n\nYeah. To clarify my comments a bit: I do think it would be possible to\nhit a weird case like this while serving fetches (i.e., as far as I know\nthere is nothing in what you saw that is inherent to pushes). But I do\nthink for serving fetches, bitmaps are overall a big net win (based on\nmy experiences).\n\nSo I think it may come down to a tradeoff: enabling this by default\nwould probably be a net win across the population, but that's little\ncomfort to the unlucky somebody who may see it as a regression. I'm not\nsure which is more important to maintain.\n\n> As an aside this is the Nth time I notice how crappy that \"Enumerating\n> objects\" progress bar is. We do a *lot* of things there, including this\n> bitmap calculation.\n> \n> But just splitting it up might result in either no progress (all\n> individually below 2 seconds), or a lot of noise as you have 20 things\n> that each take 2 seconds. I wonder if someone's looked at supporting:\n> \n> Enumerating Objects (X%) => Calculating bitmaps (Y%)\n> \n> Where X% is the total progres, and %Y is the sub-progress. I eyeballed\n> doing this once by \"chaining\" the progress structs, but there's probably\n> a less crappy way...\n\nI don't think it needs to be split; I think we just need to update the\nobject count while we're traversing the bitmaps. The problem is that the\nprogress object is known to pack-objects.c. Without bitmaps, as the\nrevision machinery walks the graph, our callbacks bump the progress\nmeter every time we see an object.\n\nWith bitmaps, all that walking happens behind the scenes, and the bitmap\ncode delivers us the final answer. So we pause for a long time, and then\nsuddenly it shoots forward.\n\nI think we'd want a way to tell the bitmap code to update our progress\nmeter as it traverses (both single objects, but also taking into account\nwhen it finds a bitmap and then suddenly bumps the value by a large\namount).\n\n-Peff\n"},{"id":"374997","messageId":"8736lqisyx.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190507074506.GF28060@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-07T08:12:06Z","receivedAt":"2019-05-07T08:12:11Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Tue, May 07 2019, Jeff King wrote:\n\n> On Sat, May 04, 2019 at 08:52:01AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> > Note that Ævar's case was somebody running bitmaps locally and trying to\n>> > push, which I think is generally not a good match for bitmaps (even when\n>> > they work, they cost more to generate than what you save if you're only\n>> > pushing once).\n>>\n>> Right. It was *not* caused by this \"enable bitmaps by default on bare\n>> repos\" patch (which I wasn't even running with), but *is* indicative of\n>> a pretty big edge case with enabling bitmaps that *will* happen for some\n>> on such bare repos if we ship the patch.\n>\n> Yeah. To clarify my comments a bit: I do think it would be possible to\n> hit a weird case like this while serving fetches (i.e., as far as I know\n> there is nothing in what you saw that is inherent to pushes). But I do\n> think for serving fetches, bitmaps are overall a big net win (based on\n> my experiences).\n>\n> So I think it may come down to a tradeoff: enabling this by default\n> would probably be a net win across the population, but that's little\n> comfort to the unlucky somebody who may see it as a regression. I'm not\n> sure which is more important to maintain.\n>\n>> As an aside this is the Nth time I notice how crappy that \"Enumerating\n>> objects\" progress bar is. We do a *lot* of things there, including this\n>> bitmap calculation.\n>>\n>> But just splitting it up might result in either no progress (all\n>> individually below 2 seconds), or a lot of noise as you have 20 things\n>> that each take 2 seconds. I wonder if someone's looked at supporting:\n>>\n>> Enumerating Objects (X%) => Calculating bitmaps (Y%)\n>>\n>> Where X% is the total progres, and %Y is the sub-progress. I eyeballed\n>> doing this once by \"chaining\" the progress structs, but there's probably\n>> a less crappy way...\n>\n> I don't think it needs to be split; I think we just need to update the\n> object count while we're traversing the bitmaps. The problem is that the\n> progress object is known to pack-objects.c. Without bitmaps, as the\n> revision machinery walks the graph, our callbacks bump the progress\n> meter every time we see an object.\n>\n> With bitmaps, all that walking happens behind the scenes, and the bitmap\n> code delivers us the final answer. So we pause for a long time, and then\n> suddenly it shoots forward.\n>\n> I think we'd want a way to tell the bitmap code to update our progress\n> meter as it traverses (both single objects, but also taking into account\n> when it finds a bitmap and then suddenly bumps the value by a large\n> amount).\n\nNot splitting it will fix the progress bar stalling, so it fixes the\nproblem that the user is wondering if the command is entirely hanging.\n\nBut I was hoping to give the user an idea of roughly where we're\nspending our time, e.g. so you can see how much the pack.useSparse\nsetting is helping (or not).\n\nSo something where we report sub-progress as we go along, and perhaps\nprint some brief summary at the end if it took long enough, e.g.:\n\n Enumerating Objects (X^1%) => Marking trees (Y^1%)\n Enumerating Objects (X^2%) => Calculating bitmaps (Y^2%)\n\nAnd at the end:\n\n Enumerating Objects (100%) in ~2m30s -- (~10s marking trees, ~2m10s bitmaps, ~10s other)\n\nI.e. bringing the whole \"nested\" trace2 regions full circle with the\nprogress bar where we could elect to trace/show some of that info, and\nthen you could turn on some trace2 mode/verbose progress to see more.\n"},{"id":"375096","messageId":"20190508071105.GA14043@sigill.intra.peff.net","threadId":"50501","inReplyTo":"8736lqisyx.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-08T07:11:05Z","receivedAt":"2019-05-08T07:11:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, May 07, 2019 at 10:12:06AM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > I think we'd want a way to tell the bitmap code to update our progress\n> > meter as it traverses (both single objects, but also taking into account\n> > when it finds a bitmap and then suddenly bumps the value by a large\n> > amount).\n> \n> Not splitting it will fix the progress bar stalling, so it fixes the\n> problem that the user is wondering if the command is entirely hanging.\n> \n> But I was hoping to give the user an idea of roughly where we're\n> spending our time, e.g. so you can see how much the pack.useSparse\n> setting is helping (or not).\n\nYeah, I think that's a bigger and more complicated problem. I admit that\nmy main annoyance is just the stall while we fill in the bitmaps (and\nit's easy because the bitmap traversal is the same unit of work as a\nregular traversal).\n\n> So something where we report sub-progress as we go along, and perhaps\n> print some brief summary at the end if it took long enough, e.g.:\n> \n> Enumerating Objects (X^1%) => Marking trees (Y^1%)\n> Enumerating Objects (X^2%) => Calculating bitmaps (Y^2%)\n> \n> And at the end:\n> \n> Enumerating Objects (100%) in ~2m30s -- (~10s marking trees, ~2m10s bitmaps, ~10s other)\n> \n> I.e. bringing the whole \"nested\" trace2 regions full circle with the\n> progress bar where we could elect to trace/show some of that info, and\n> then you could turn on some trace2 mode/verbose progress to see more.\n\nI do wonder if this really needs to be part of the progress bar. The\ngoal of the progress bar is to give the user a sense that work is\nhappening, and (if possible, but not for \"enumerating\") an idea of when\nit might finish. If the trace code can already do detailed timings, then\nshouldn't we just be encouraging people to use that?\n\n-Peff\n"},{"id":"375141","messageId":"561912f3-4761-c690-5327-501e20023e4d@gmail.com","threadId":"50501","inReplyTo":"20190508071105.GA14043@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-08T14:20:24Z","receivedAt":"2019-05-08T14:20:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/8/2019 3:11 AM, Jeff King wrote:\n> On Tue, May 07, 2019 at 10:12:06AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n>>> I think we'd want a way to tell the bitmap code to update our progress\n>>> meter as it traverses (both single objects, but also taking into account\n>>> when it finds a bitmap and then suddenly bumps the value by a large\n>>> amount).\n>>\n>> Not splitting it will fix the progress bar stalling, so it fixes the\n>> problem that the user is wondering if the command is entirely hanging.\n>>\n>> But I was hoping to give the user an idea of roughly where we're\n>> spending our time, e.g. so you can see how much the pack.useSparse\n>> setting is helping (or not).\n> \n> Yeah, I think that's a bigger and more complicated problem. I admit that\n> my main annoyance is just the stall while we fill in the bitmaps (and\n> it's easy because the bitmap traversal is the same unit of work as a\n> regular traversal).\n\nThe pack.useSparse setting also speeds up a section that is not marked\nby progress: that portion usually is walking all UNINTERESTING trees and\nthe\"Enumerating Objects\" progress is just for walking the INTERESTING objects.\n \n>> So something where we report sub-progress as we go along, and perhaps\n>> print some brief summary at the end if it took long enough, e.g.:\n>>\n>> Enumerating Objects (X^1%) => Marking trees (Y^1%)\n>> Enumerating Objects (X^2%) => Calculating bitmaps (Y^2%)\n\nI like this idea for splitting the \"normal\" mechanism, too:\n\n Enumerating Objects (X^1%) => Marking trees (Y^1%)\n Enumerating Objects (X^2%) => Enumerating objects to pack (Y^2%)\n\n>> I.e. bringing the whole \"nested\" trace2 regions full circle with the\n>> progress bar where we could elect to trace/show some of that info, and\n>> then you could turn on some trace2 mode/verbose progress to see more.\n> \n> I do wonder if this really needs to be part of the progress bar. The\n> goal of the progress bar is to give the user a sense that work is\n> happening, and (if possible, but not for \"enumerating\") an idea of when\n> it might finish. If the trace code can already do detailed timings, then\n> shouldn't we just be encouraging people to use that?\n\nThe problem I've seen (without bitmaps) is that running `git push` can\ntake a while before _any_ progress is listed.\n\nGood news is: `pack.useSparse` fixed our push problem in the Windows OS\nrepo. The end-to-end time for `git push` sped up by 7.7x with the change,\nand this \"blank\" time is too fast for users to notice.\n\nUpdating the progress could help in cases without pack.useSparse.\n\nThanks,\n-Stolee\n"},{"id":"375166","messageId":"87sgtohqk9.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190508071105.GA14043@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-08T16:13:58Z","receivedAt":"2019-05-08T16:14:03Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Wed, May 08 2019, Jeff King wrote:\n\n> On Tue, May 07, 2019 at 10:12:06AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> > I think we'd want a way to tell the bitmap code to update our progress\n>> > meter as it traverses (both single objects, but also taking into account\n>> > when it finds a bitmap and then suddenly bumps the value by a large\n>> > amount).\n>>\n>> Not splitting it will fix the progress bar stalling, so it fixes the\n>> problem that the user is wondering if the command is entirely hanging.\n>>\n>> But I was hoping to give the user an idea of roughly where we're\n>> spending our time, e.g. so you can see how much the pack.useSparse\n>> setting is helping (or not).\n>\n> Yeah, I think that's a bigger and more complicated problem. I admit that\n> my main annoyance is just the stall while we fill in the bitmaps (and\n> it's easy because the bitmap traversal is the same unit of work as a\n> regular traversal).\n>\n>> So something where we report sub-progress as we go along, and perhaps\n>> print some brief summary at the end if it took long enough, e.g.:\n>>\n>> Enumerating Objects (X^1%) => Marking trees (Y^1%)\n>> Enumerating Objects (X^2%) => Calculating bitmaps (Y^2%)\n>>\n>> And at the end:\n>>\n>> Enumerating Objects (100%) in ~2m30s -- (~10s marking trees, ~2m10s bitmaps, ~10s other)\n>>\n>> I.e. bringing the whole \"nested\" trace2 regions full circle with the\n>> progress bar where we could elect to trace/show some of that info, and\n>> then you could turn on some trace2 mode/verbose progress to see more.\n>\n> I do wonder if this really needs to be part of the progress bar. The\n> goal of the progress bar is to give the user a sense that work is\n> happening, and (if possible, but not for \"enumerating\") an idea of when\n> it might finish. If the trace code can already do detailed timings, then\n> shouldn't we just be encouraging people to use that?\n\nTo just show work happening we could save ourselves some horizontal\nspace and the debates over counting v.s. enumerating with:\n\n diff --git a/progress.c b/progress.c\n index 0318bdd41b..83336ca391 100644\n --- a/progress.c\n +++ b/progress.c\n @@ -226,3 +226,3 @@ static struct progress *start_progress_delay(const char *title, uint64_t total,\n struct progress *progress = xmalloc(sizeof(*progress));\n - progress->title = title;\n + progress->title = \"Reticulating splines\";\n progress->total = total;\n\n:)\n\nObviously that's silly, but the point is we do show some user messaging\nwith these now, and e.g. the other day here on-list (can't be bothered\nto find the msgid) someone was lamenting that the N progressbars we show\non \"push\" were too verbose.\n\nSo by coalescing some of the existing bars that do one logical operation\n(push) in N steps we could be less verbose without losing the \"stuff's\nhappening\" part of it, and would see if something odd was going on,\ne.g. the \"I/O write\" part being proportionally slower on this box than\nthe other, or when they upgrade bitmaps suddenly showing up as >95% of\nthe time.\n\nThe bit I find interesting about tying it into trace2 is that once you\ndo that the trace logs can contain e.g. min/max/avg/median/percentile\ntime for doing some operation we can break into N steps same/similar\nsteps, which might be interesting for performance analysis.\n"},{"id":"375185","messageId":"87o94chfaa.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190504132346.GK14763@szeder.dev","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-08T20:17:33Z","receivedAt":"2019-05-08T20:17:38Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sat, May 04 2019, SZEDER Gábor wrote:\n\n> On Sat, May 04, 2019 at 08:52:01AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>> As an aside this is the Nth time I notice how crappy that \"Enumerating\n>> objects\" progress bar is.\n>\n> And don't forget that the commit-graph progress bar still prints\n> nonsense :)\n>\n> https://public-inbox.org/git/87ef6ydds8.fsf@evledraar.gmail.com/\n\nI forgot for a bit, but then figured I'd get out of Derrick's way with\nhis more significant commit-graph work (which would have inevitably had\nmerge conflicts with this patch), and look at the time. Here we are\ncoming up on rc0.\n\nI'm inclined to just wait until Derrick's refactorings land post-2.22.0\nunless a) we need it enough before 2.22.0 to cause him trouble b) Junio\nagrees with \"a\" and would take such a patch to fix this part of the\nprogress output before 2.22.0.\n\nIf people (just you would do) tell me \"yes I/we want it\" and Junio says\n\"yeah I'll do that\" I'll write this patch in the next couple of days,\notherwise I'll do other stuff.\n\nJunio?\n"},{"id":"375190","messageId":"20190508222502.GA19990@sigill.intra.peff.net","threadId":"50501","inReplyTo":"87sgtohqk9.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-08T22:25:02Z","receivedAt":"2019-05-08T22:25:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, May 08, 2019 at 06:13:58PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > I do wonder if this really needs to be part of the progress bar. The\n> > goal of the progress bar is to give the user a sense that work is\n> > happening, and (if possible, but not for \"enumerating\") an idea of when\n> > it might finish. If the trace code can already do detailed timings, then\n> > shouldn't we just be encouraging people to use that?\n> [...]\n> - progress->title = title;\n> + progress->title = \"Reticulating splines\";\n\nHeh, OK, that's a fair reductio ad absurdum of my point. I guess what I\nwas trying to say is that we don't need to go overboard with accuracy as\nlong as we're giving a vague sense of the work. Precision measurements\ncan be handled through a different system.\n\nBut I don't mind if you can find a way to do these kind of cascaded\nprogress meters in a way that is pleasing to the eye and not hard to\nhandle in the callers of the code.\n\n-Peff\n"},{"id":"375199","messageId":"xmqqd0ksfe6e.fsf@gitster-ct.c.googlers.com","threadId":"50501","inReplyTo":"87o94chfaa.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-05-09T04:24:25Z","receivedAt":"2019-05-09T04:24:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n\n> On Sat, May 04 2019, SZEDER Gábor wrote:\n> ...\n>> And don't forget that the commit-graph progress bar still prints\n>> nonsense :)\n>\n> I'm inclined to just wait until Derrick's refactorings land post-2.22.0\n\nFine by me. Thanks.\n"},{"id":"376102","messageId":"20190523113031.GA17448@sigill.intra.peff.net","threadId":"50501","inReplyTo":"20190410225721.GA32262@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-23T11:30:31Z","receivedAt":"2019-05-23T11:30:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 10, 2019 at 06:57:21PM -0400, Jeff King wrote:\n\n> 2. The answer we get from a bitmap versus a regular traversal are not\n> apples-to-apples equivalent. The regular traversal walks down to\n> the UNINTERESTING commits, marks the boundaries trees and blobs as\n> UNINTERESTING, and then adds in all the interesting trees and blobs\n> minus the UNINTERESTING parts. So it can sometimes give the wrong\n> answer, claiming something is interesting when it is not.\n> \n> Whereas with bitmaps we fill in the trees and blobs as we walk, and\n> you get the true answer. But it means we may open up a lot more\n> trees than the equivalent traversal would.\n> \n> So one thing I've never really experimented with (and indeed, never\n> really thought about until writing this email) is that the bitmaps\n> could try to do that looser style of traversal, knowing that we\n> might err on the side of calling things interesting in a few cases.\n> But hopefully spending a lot less time opening trees.\n> \n> I'm not even 100% sure what that would look like in code, but just\n> thinking about it from a high level, I don't there's a particular\n> mathematical reason it couldn't work.\n\nI spent a while thinking and experimenting with this tonight. The result\nis the patch below. Ævar, do you still have a copy of the repo that\nmisbehaved? I'd be curious to see how it fares.\n\nFinding the right trees to explore is a little tricky with bitmaps. In\na normal traversal, we consider the \"edges\" to be worth exploring.\nI.e., the places where an UNINTERESTING commit is the parent of an\ninteresting one.\n\nBut with bitmaps, we don't have that information in the same way,\nbecause we're trying to avoid walking the commits in the first place. So\ne.g., in a history like this:\n\n A--B--C\n \\\n D\n\nLet's imagine we're computing \"C..D\", and that D has a bitmap on disk\nbut C does not. When we visit D, we'll see that it has a bitmap, fill in\nthe results in our cumulative \"want\" bitmap, and then stop walking its\nparents (because we know everything they could tell us already).\n\nThen we visit C. It's not bitmapped, so we keep walking. Unlike a normal\ntraversal, we can't stop walking even though there are only\nUNINTERESTING commits left, because we have to fill the complete bitmap,\nincluding A and B (and you can imagine there might be thousands of\nancestors of A, too). The reason is that we skipped adding ancestors of\nD when we saw its bitmap, so no still_interesting() cutoff will work\nthere.\n\nBut how do we know that it's worth looking into the tree of \"B\"? If we\nassume we visit commits before their ancestors (because of the commit\ntimestamp ordering), then we'd see that \"B\" is in the \"want\" bitmap\nalready, which makes it worth visiting its tree.\n\nUnfortunately we'd then continue on to \"A\", and it would _also_ look\ninteresting, because it's also in the \"want\" bitmap. We don't have an\neasy way of knowing that \"A\" is basically already covered by \"B\", and is\ntherefore not worth pursuing. In this example, we could pass down a bit\nfrom B to A as we traverse. But you can imagine another interesting\ncommit branched from A, which _would_ make A's tree worth considering.\n\nFundamentally, as soon as we load a bitmap and stop traversing, we lose\nall information about the graph structure.\n\nSo the patch below just looks at every tree that might be worth\nexploring (so both \"A\" and \"B\" here, but not \"C\"). That shouldn't be any\n_worse_ than what the current code does (because it looks at all the\ntrees). It appears to behave correctly, at least so far as passing the\ntest suite. Running p5310 and p5311 against git.git and linux.git, it\nseems to perform worse. I'm not quite sure why that is (i.e., if I\nscrewed up something in the implementation, or if the algorithm is\nfundamentally worse).\n\nThere are a lot of rough edges in the patch; I was just trying to see if\nthe idea was even viable. So don't bother reviewing it as a real\nproposal for inclusion. If you do read it, I'd recommend just looking at\nthe post-image, since it's essentially a rewrite and the diff is a bit\nmessy.\n\n-Peff\n\n---\n pack-bitmap.c | 398 ++++++++++++++++++++++++--------------------------\n 1 file changed, 193 insertions(+), 205 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 6069b2fe55..4a40f62a38 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -12,6 +12,8 @@\n #include \"packfile.h\"\n #include \"repository.h\"\n #include \"object-store.h\"\n+#include \"blob.h\"\n+#include \"prio-queue.h\"\n \n /*\n * An entry on the bitmap index, representing the bitmap for a given\n@@ -422,180 +424,22 @@ static int ext_index_add_object(struct bitmap_index *bitmap_git,\n \treturn bitmap_pos + bitmap_git->pack->num_objects;\n }\n \n-struct bitmap_show_data {\n-\tstruct bitmap_index *bitmap_git;\n-\tstruct bitmap *base;\n-};\n-\n-static void show_object(struct object *object, const char *name, void *data_)\n-{\n-\tstruct bitmap_show_data *data = data_;\n-\tint bitmap_pos;\n-\n-\tbitmap_pos = bitmap_position(data->bitmap_git, &object->oid);\n-\n-\tif (bitmap_pos < 0)\n-\t\tbitmap_pos = ext_index_add_object(data->bitmap_git, object,\n-\t\t\t\t\t\t name);\n-\n-\tbitmap_set(data->base, bitmap_pos);\n-}\n-\n-static void show_commit(struct commit *commit, void *data)\n-{\n-}\n-\n-static int add_to_include_set(struct bitmap_index *bitmap_git,\n-\t\t\t struct include_data *data,\n-\t\t\t const struct object_id *oid,\n-\t\t\t int bitmap_pos)\n-{\n-\tkhiter_t hash_pos;\n-\n-\tif (data->seen && bitmap_get(data->seen, bitmap_pos))\n-\t\treturn 0;\n-\n-\tif (bitmap_get(data->base, bitmap_pos))\n-\t\treturn 0;\n-\n-\thash_pos = kh_get_oid_map(bitmap_git->bitmaps, *oid);\n-\tif (hash_pos < kh_end(bitmap_git->bitmaps)) {\n-\t\tstruct stored_bitmap *st = kh_value(bitmap_git->bitmaps, hash_pos);\n-\t\tbitmap_or_ewah(data->base, lookup_stored_bitmap(st));\n-\t\treturn 0;\n-\t}\n-\n-\tbitmap_set(data->base, bitmap_pos);\n-\treturn 1;\n-}\n-\n-static int should_include(struct commit *commit, void *_data)\n-{\n-\tstruct include_data *data = _data;\n-\tint bitmap_pos;\n-\n-\tbitmap_pos = bitmap_position(data->bitmap_git, &commit->object.oid);\n-\tif (bitmap_pos < 0)\n-\t\tbitmap_pos = ext_index_add_object(data->bitmap_git,\n-\t\t\t\t\t\t (struct object *)commit,\n-\t\t\t\t\t\t NULL);\n-\n-\tif (!add_to_include_set(data->bitmap_git, data, &commit->object.oid,\n-\t\t\t\tbitmap_pos)) {\n-\t\tstruct commit_list *parent = commit->parents;\n-\n-\t\twhile (parent) {\n-\t\t\tparent->item->object.flags |= SEEN;\n-\t\t\tparent = parent->next;\n-\t\t}\n-\n-\t\treturn 0;\n-\t}\n-\n-\treturn 1;\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-\t\t\t\t struct bitmap *seen)\n+static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\tstruct bitmap **base, struct commit *commit)\n {\n-\tstruct bitmap *base = NULL;\n-\tint needs_walk = 0;\n-\n-\tstruct object_list *not_mapped = NULL;\n-\n-\t/*\n-\t * Go through all the roots for the walk. The ones that have bitmaps\n-\t * on the bitmap index will be `or`ed together to form an initial\n-\t * global reachability analysis.\n-\t *\n-\t * The ones without bitmaps in the index will be stored in the\n-\t * `not_mapped_list` for further processing.\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\tkhiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, object->oid);\n-\n-\t\t\tif (pos < kh_end(bitmap_git->bitmaps)) {\n-\t\t\t\tstruct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);\n-\t\t\t\tstruct ewah_bitmap *or_with = lookup_stored_bitmap(st);\n-\n-\t\t\t\tif (base == NULL)\n-\t\t\t\t\tbase = ewah_to_bitmap(or_with);\n-\t\t\t\telse\n-\t\t\t\t\tbitmap_or_ewah(base, or_with);\n-\n-\t\t\t\tobject->flags |= SEEN;\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t}\n-\n-\t\tobject_list_insert(object, ¬_mapped);\n-\t}\n-\n-\t/*\n-\t * Best case scenario: We found bitmaps for all the roots,\n-\t * so the resulting `or` bitmap has the full reachability analysis\n-\t */\n-\tif (not_mapped == NULL)\n-\t\treturn base;\n-\n-\troots = not_mapped;\n-\n-\t/*\n-\t * Let's iterate through all the roots that don't have bitmaps to\n-\t * check if we can determine them to be reachable from the existing\n-\t * global bitmap.\n-\t *\n-\t * If we cannot find them in the existing global bitmap, we'll need\n-\t * to push them to an actual walk and run it until we can confirm\n-\t * they are reachable\n-\t */\n-\twhile (roots) {\n-\t\tstruct object *object = roots->item;\n-\t\tint pos;\n-\n-\t\troots = roots->next;\n-\t\tpos = bitmap_position(bitmap_git, &object->oid);\n-\n-\t\tif (pos < 0 || base == NULL || !bitmap_get(base, pos)) {\n-\t\t\tobject->flags &= ~UNINTERESTING;\n-\t\t\tadd_pending_object(revs, object, \"\");\n-\t\t\tneeds_walk = 1;\n-\t\t} else {\n-\t\t\tobject->flags |= SEEN;\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 == NULL)\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_data = &incdata;\n-\n-\t\tif (prepare_revision_walk(revs))\n-\t\t\tdie(\"revision walk setup failed\");\n+\tkhiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, commit->object.oid);\n+\tif (pos < kh_end(bitmap_git->bitmaps)) {\n+\t\tstruct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);\n+\t\tstruct ewah_bitmap *or_with = lookup_stored_bitmap(st);\n \n-\t\tshow_data.bitmap_git = bitmap_git;\n-\t\tshow_data.base = base;\n+\t\tif (*base == NULL)\n+\t\t\t*base = ewah_to_bitmap(or_with);\n+\t\telse\n+\t\t\tbitmap_or_ewah(*base, or_with);\n \n-\t\ttraverse_commit_list(revs, show_commit, show_object,\n-\t\t\t\t &show_data);\n+\t\treturn 1;\n \t}\n-\n-\treturn base;\n+\treturn 0;\n }\n \n static void show_extended_objects(struct bitmap_index *bitmap_git,\n@@ -665,24 +509,122 @@ 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+static void add_object_to_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object *obj,\n+\t\t\t\t struct bitmap *bitmap,\n+\t\t\t\t struct bitmap *seen,\n+\t\t\t\t int ignore_missing);\n+\n+static void add_tag_to_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t struct tag *tag,\n+\t\t\t struct bitmap *bitmap,\n+\t\t\t struct bitmap *seen,\n+\t\t\t int ignore_missing)\n+{\n+\tif (parse_tag(tag) < 0 || !tag->tagged) {\n+\t\tif (ignore_missing)\n+\t\t\treturn;\n+\t\tdie(\"unable to parse tag %s\", oid_to_hex(&tag->object.oid));\n+\t}\n+\tadd_object_to_bitmap(bitmap_git, tag->tagged, bitmap, seen,\n+\t\t\t ignore_missing);\n+}\n+\n+static void add_tree_to_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t struct tree *tree,\n+\t\t\t struct bitmap *bitmap,\n+\t\t\t struct bitmap *seen,\n+\t\t\t int ignore_missing)\n {\n-\twhile (roots) {\n-\t\tstruct object *object = roots->item;\n-\t\troots = roots->next;\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n \n-\t\tif (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)\n-\t\t\treturn 1;\n+\tif (parse_tree(tree) < 0) {\n+\t\tif (ignore_missing)\n+\t\t\treturn;\n+\t\tdie(\"unable to parse tree %s\", oid_to_hex(&tree->object.oid));\n \t}\n \n-\treturn 0;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tstruct tree *t = lookup_tree(the_repository, &entry.oid);\n+\t\t\tif (!t) {\n+\t\t\t\tdie(_(\"entry '%s' in tree %s has tree mode, \"\n+\t\t\t\t \"but is not a tree\"),\n+\t\t\t\t entry.path, oid_to_hex(&tree->object.oid));\n+\t\t\t}\n+\t\t\tadd_object_to_bitmap(bitmap_git, &t->object,\n+\t\t\t\t\t bitmap, seen, ignore_missing);\n+\t\t} else if (!S_ISGITLINK(entry.mode)) {\n+\t\t\tstruct blob *b = lookup_blob(the_repository, &entry.oid);\n+\t\t\tif (!b) {\n+\t\t\t\tdie(_(\"entry '%s' in tree %s has blob mode, \"\n+\t\t\t\t \"but is not a blob\"),\n+\t\t\t\t entry.path, oid_to_hex(&tree->object.oid));\n+\t\t\t}\n+\t\t\tadd_object_to_bitmap(bitmap_git, &b->object,\n+\t\t\t\t\t bitmap, seen, ignore_missing);\n+\t\t}\n+\t}\n+\n+\tfree_tree_buffer(tree);\n+}\n+\n+static void add_object_to_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object *obj,\n+\t\t\t\t struct bitmap *bitmap,\n+\t\t\t\t struct bitmap *seen,\n+\t\t\t\t int ignore_missing)\n+{\n+\tint pos = bitmap_position(bitmap_git, &obj->oid);\n+\n+\tif (pos < 0)\n+\t\tpos = ext_index_add_object(bitmap_git, obj, NULL);\n+\n+\tif (bitmap_get(bitmap, pos))\n+\t\treturn; /* already there */\n+\n+\tif (seen && bitmap_get(seen, pos))\n+\t\treturn; /* seen in other bitmap; not worth digging further */\n+\n+\tbitmap_set(bitmap, pos);\n+\n+\tif (obj->type == OBJ_BLOB)\n+\t\treturn;\n+\telse if (obj->type == OBJ_TAG)\n+\t\tadd_tag_to_bitmap(bitmap_git, (struct tag *)obj,\n+\t\t\t\t bitmap, seen, ignore_missing);\n+\telse if (obj->type == OBJ_TREE)\n+\t\tadd_tree_to_bitmap(bitmap_git, (struct tree *)obj,\n+\t\t\t\t bitmap, seen, ignore_missing);\n+\telse\n+\t\tBUG(\"unexpected object type: %d\", obj->type);\n+}\n+\n+static void add_objects_to_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object_list **list,\n+\t\t\t\t struct bitmap *bitmap,\n+\t\t\t\t struct bitmap *seen,\n+\t\t\t\t int ignore_missing)\n+{\n+\twhile (*list) {\n+\t\tstruct object_list *cur = *list;\n+\n+\t\tadd_object_to_bitmap(bitmap_git, cur->item,\n+\t\t\t\t bitmap, seen, ignore_missing);\n+\n+\t\t*list = cur->next;\n+\t\tfree(cur);\n+\t}\n }\n \n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n {\n \tunsigned int i;\n \n+\tstruct prio_queue commits = { compare_commits_by_commit_date };\n+\n \tstruct object_list *wants = NULL;\n \tstruct object_list *haves = NULL;\n \n@@ -714,24 +656,16 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t\t\tobject = parse_object_or_die(&tag->tagged->oid, NULL);\n \t\t}\n \n-\t\tif (object->flags & UNINTERESTING)\n-\t\t\tobject_list_insert(object, &haves);\n-\t\telse\n-\t\t\tobject_list_insert(object, &wants);\n+\t\tif (object->type == OBJ_COMMIT)\n+\t\t\tprio_queue_put(&commits, object);\n+\t\telse {\n+\t\t\tif (object->flags & UNINTERESTING)\n+\t\t\t\tobject_list_insert(object, &haves);\n+\t\t\telse\n+\t\t\t\tobject_list_insert(object, &wants);\n+\t\t}\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-\n \t/*\n \t * now we're going to use bitmaps, so load the actual bitmap entries\n \t * from disk. this is the point of no return; after this the rev_list\n@@ -742,20 +676,74 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\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+\thaves_bitmap = bitmap_new();\n+\twants_bitmap = bitmap_new();\n \n-\t\tif (haves_bitmap == NULL)\n-\t\t\tBUG(\"failed to perform bitmap walk\");\n-\t}\n+\t/*\n+\t * First traverse the relevant commits as we would for a normal\n+\t * traversal.\n+\t */\n+\twhile (commits.nr) {\n+\t\tstruct commit *commit = prio_queue_get(&commits);\n+\t\tstruct bitmap **dst_bitmap;\n+\t\tint pos;\n+\t\tstruct commit_list *parent;\n+\n+\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\tdst_bitmap = &haves_bitmap;\n+\t\telse\n+\t\t\tdst_bitmap = &wants_bitmap;\n \n-\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n+\t\tpos = bitmap_position(bitmap_git, &commit->object.oid);\n+\t\tif (pos >= 0 && *dst_bitmap && bitmap_get(*dst_bitmap, pos))\n+\t\t\tcontinue; /* already covered */\n \n-\tif (!wants_bitmap)\n-\t\tBUG(\"failed to perform bitmap walk\");\n+\t\tif (add_commit_to_bitmap(bitmap_git, dst_bitmap, commit))\n+\t\t\tcontinue; /* skip adding parents, they're covered */\n+\n+\n+\t\t/* otherwise mark ourselves and queue dependent objects */\n+\t\tif (pos < 0)\n+\t\t\tpos = ext_index_add_object(bitmap_git, &commit->object, NULL);\n+\t\tbitmap_set(*dst_bitmap, pos);\n+\t\tif (parse_commit(commit)) {\n+\t\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\t\tcontinue;\n+\t\t\tdie(\"unable to parse commit %s\",\n+\t\t\t oid_to_hex(&commit->object.oid));\n+\t\t}\n+\t\tif (commit->object.flags & UNINTERESTING) {\n+\t\t\t/*\n+\t\t\t * If an uninteresting commit is in the \"wants\" bitmap,\n+\t\t\t * then our tree is worth exploring. This means we may\n+\t\t\t * miss some trees in the \"haves\" that are not\n+\t\t\t * ancestors of \"wants\" (or that are, but we missed\n+\t\t\t * because of out-of-order timestamps).\n+\t\t\t */\n+\t\t\tif (wants_bitmap && bitmap_get(wants_bitmap, pos))\n+\t\t\t\tobject_list_insert(&get_commit_tree(commit)->object,\n+\t\t\t\t\t\t &haves);\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * \"wants\" must always be explored\n+\t\t\t */\n+\t\t\tobject_list_insert(&get_commit_tree(commit)->object,\n+\t\t\t\t\t &wants);\n+\t\t}\n+\n+\t\tfor (parent = commit->parents; parent; parent = parent->next) {\n+\t\t\tif (commit->object.flags & UNINTERESTING)\n+\t\t\t\tparent->item->object.flags |= UNINTERESTING;\n+\t\t\tprio_queue_put(&commits, parent->item);\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * At this point we've processed all of the commits, and queued items\n+\t * in \"haves\" and \"wants\" that need to be marked.\n+\t */\n+\tadd_objects_to_bitmap(bitmap_git, &haves, haves_bitmap, NULL, 1);\n+\tadd_objects_to_bitmap(bitmap_git, &wants, wants_bitmap, haves_bitmap, 0);\n \n \tif (haves_bitmap)\n \t\tbitmap_and_not(wants_bitmap, haves_bitmap);\n-- \n2.22.0.rc1.549.gadb183c4cb\n\n"},{"id":"376103","messageId":"1e0d216b-5e68-faff-883c-778a04f55bde@gmail.com","threadId":"50501","inReplyTo":"20190523113031.GA17448@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-23T12:53:56Z","receivedAt":"2019-05-23T12:54:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/23/2019 7:30 AM, Jeff King wrote:\n> On Wed, Apr 10, 2019 at 06:57:21PM -0400, Jeff King wrote:\n> \n>> 2. The answer we get from a bitmap versus a regular traversal are not\n>> apples-to-apples equivalent. The regular traversal walks down to\n>> the UNINTERESTING commits, marks the boundaries trees and blobs as\n>> UNINTERESTING, and then adds in all the interesting trees and blobs\n>> minus the UNINTERESTING parts. So it can sometimes give the wrong\n>> answer, claiming something is interesting when it is not.\n>>\n>> Whereas with bitmaps we fill in the trees and blobs as we walk, and\n>> you get the true answer. But it means we may open up a lot more\n>> trees than the equivalent traversal would.\n>>\n>> So one thing I've never really experimented with (and indeed, never\n>> really thought about until writing this email) is that the bitmaps\n>> could try to do that looser style of traversal, knowing that we\n>> might err on the side of calling things interesting in a few cases.\n>> But hopefully spending a lot less time opening trees.\n>>\n>> I'm not even 100% sure what that would look like in code, but just\n>> thinking about it from a high level, I don't there's a particular\n>> mathematical reason it couldn't work.\n> \n> I spent a while thinking and experimenting with this tonight. The result\n> is the patch below. Ævar, do you still have a copy of the repo that\n> misbehaved? I'd be curious to see how it fares.\n\nThis patch caught my attention, and I think I understand some of the issues\nat hand. I'm not well-versed specifically in Git's bitmap implementation.\nThe fundamental ideas are there, but my perspective is biased by my own\nindependent bitmap implementation for Azure Repos. What worked there may not\nwork at all here.\n\n> Finding the right trees to explore is a little tricky with bitmaps. In\n> a normal traversal, we consider the \"edges\" to be worth exploring.\n> I.e., the places where an UNINTERESTING commit is the parent of an\n> interesting one.\n\nThis is the \"commit frontier\" which I bring up again below.\n\n> But with bitmaps, we don't have that information in the same way,\n> because we're trying to avoid walking the commits in the first place. So\n> e.g., in a history like this:\n> \n> A--B--C\n> \\\n> D\n> \n> Let's imagine we're computing \"C..D\", and that D has a bitmap on disk\n> but C does not.\n\n(As I read your discussion below, I'm confused. For \"C..D\", C is a have\nand D is a want. We should explore all the haves _first_, then walk the\nwants, right?)\n\n> When we visit D, we'll see that it has a bitmap, fill in\n> the results in our cumulative \"want\" bitmap, and then stop walking its\n> parents (because we know everything they could tell us already).\n\nI may be misreading something, but we would construct _a_ bitmap for C\nby walking its reachable objects until hitting a bitmap we know about.\nPerhaps A or B have a bitmap to start the construction. If we never\nconstruct a bitmap for C, then we don't know what to remove from the \"D\"\nbitmap to show the difference.\n\nIf \"C\" is not even in the bitmap pack, then we don't use bitmaps for\nthis calculation because of this condition:\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\n> Then we visit C. It's not bitmapped, so we keep walking. Unlike a normal\n> traversal, we can't stop walking even though there are only\n> UNINTERESTING commits left, because we have to fill the complete bitmap,\n> including A and B (and you can imagine there might be thousands of\n> ancestors of A, too). The reason is that we skipped adding ancestors of\n> D when we saw its bitmap, so no still_interesting() cutoff will work\n> there.\n> \n> But how do we know that it's worth looking into the tree of \"B\"? If we\n> assume we visit commits before their ancestors (because of the commit\n> timestamp ordering), then we'd see that \"B\" is in the \"want\" bitmap\n> already, which makes it worth visiting its tree.\n> \n> Unfortunately we'd then continue on to \"A\", and it would _also_ look\n> interesting, because it's also in the \"want\" bitmap. We don't have an\n> easy way of knowing that \"A\" is basically already covered by \"B\", and is\n> therefore not worth pursuing. In this example, we could pass down a bit\n> from B to A as we traverse. But you can imagine another interesting\n> commit branched from A, which _would_ make A's tree worth considering.\n> \n> Fundamentally, as soon as we load a bitmap and stop traversing, we lose\n> all information about the graph structure.\n> \n> So the patch below just looks at every tree that might be worth\n> exploring (so both \"A\" and \"B\" here, but not \"C\"). That shouldn't be any\n> _worse_ than what the current code does (because it looks at all the\n> trees). It appears to behave correctly, at least so far as passing the\n> test suite. Running p5310 and p5311 against git.git and linux.git, it\n> seems to perform worse. I'm not quite sure why that is (i.e., if I\n> screwed up something in the implementation, or if the algorithm is\n> fundamentally worse).\n\nI'm of the opinion that the old method was better. It followed a very clear\nthree-step process:\n\n 1. Compute the \"haves\" bitmap.\n\n 2. Compute the \"wants\" bitmap, but don't explore into the \"haves\" bitmap.\n\n 3. Subtract the \"haves\" bitmap from the \"wants\" (in case we added bits to\n the wants before they were in the haves).\n\nBut there is hope in your idea to improve some cases. As noted, we give up\nif all of the haves are not in the bitmapped pack. By starting with a\ncommit walk, we can find the \"commit frontier,\" which is the set of commits\nthat are explored by paint_down_to_common(). In this case, the set {B, C, D}.\n\nAfter walking commits and finding a set of UNINTERESTING commits, we could\nlook for any UNINTERESTING commits that have bitmaps (or simply are in the\nbitmapped pack) and use those to see our \"haves\" bitmap. So, if B has a\nbitmap, but C is too new for the bitmap, then we can still create the haves\nbased on B and then take a bitmap diff \"D minus B\".\n\nIn fact, using the \"merge base set\" for the diff reflects what the non-bitmap\nalgorithm does in this case. It ignores C and only explores B.\n\nI learned a lot looking at both versions of this method side-by-side. Thanks!\n\n-Stolee\n"},{"id":"376112","messageId":"87tvdlt1jp.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190523113031.GA17448@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-23T19:26:34Z","receivedAt":"2019-05-23T19:35:34Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, May 23 2019, Jeff King wrote:\n\n> On Wed, Apr 10, 2019 at 06:57:21PM -0400, Jeff King wrote:\n>\n>> 2. The answer we get from a bitmap versus a regular traversal are not\n>> apples-to-apples equivalent. The regular traversal walks down to\n>> the UNINTERESTING commits, marks the boundaries trees and blobs as\n>> UNINTERESTING, and then adds in all the interesting trees and blobs\n>> minus the UNINTERESTING parts. So it can sometimes give the wrong\n>> answer, claiming something is interesting when it is not.\n>>\n>> Whereas with bitmaps we fill in the trees and blobs as we walk, and\n>> you get the true answer. But it means we may open up a lot more\n>> trees than the equivalent traversal would.\n>>\n>> So one thing I've never really experimented with (and indeed, never\n>> really thought about until writing this email) is that the bitmaps\n>> could try to do that looser style of traversal, knowing that we\n>> might err on the side of calling things interesting in a few cases.\n>> But hopefully spending a lot less time opening trees.\n>>\n>> I'm not even 100% sure what that would look like in code, but just\n>> thinking about it from a high level, I don't there's a particular\n>> mathematical reason it couldn't work.\n>\n> I spent a while thinking and experimenting with this tonight. The result\n> is the patch below. Ævar, do you still have a copy of the repo that\n> misbehaved? I'd be curious to see how it fares.\n\nNo, sorry. I think we could make an artificial test to emulate it, which\nwould be something like:\n\n * ~1 million commits\n * local clone setup to fetch all branches/tags (default 'git clone')\n * local a bit ahead/behind\n * Have old \"main\" pack with *.bitmap, bunch of other packs/loose objects without that\n * push try to push the local change upstream (or to a topic branch)\n\nI tried briefly to emulate this with git.git with:\n\n (\n rm -rf /tmp/git /tmp/git.old &&\n git init /tmp/git.old &&\n git clone --bare https://github.com/git/git.git /tmp/git &&\n cd /tmp/git &&\n old_commit=$(git rev-parse v2.20.0^{}) &&\n git rev-list v2.12.0..v2.21.0|parallel 'git branch topic-{} {}' &&\n cd /tmp/git.old &&\n echo /tmp/git/objects >.git/objects/info/alternates &&\n git branch master $old_commit &&\n git reset --hard master &&\n git repack -Adb &&\n rm .git/objects/info/alternates &&\n for c in {1..10}\n do\n >$c &&\n git add $c &&\n git commit -m\"bump $c\"\n done\n )\n\nBut didn't get anywhere, probably because here my topics are all stuff I\nhave already, and I just have 2x packs.\n\nIt would be really cool to have some test tool that could produce\nvarious \"shape of repo\" states like that. I.e. given an end-state of a\npublic repo emulate various plausible local client states like that\ngiven some assumptions about how often the local client fetches, what\nthe GC settings are etc.\n\n> Finding the right trees to explore is a little tricky with bitmaps. In\n> a normal traversal, we consider the \"edges\" to be worth exploring.\n> I.e., the places where an UNINTERESTING commit is the parent of an\n> interesting one.\n>\n> But with bitmaps, we don't have that information in the same way,\n> because we're trying to avoid walking the commits in the first place. So\n> e.g., in a history like this:\n>\n> A--B--C\n> \\\n> D\n>\n> Let's imagine we're computing \"C..D\", and that D has a bitmap on disk\n> but C does not. When we visit D, we'll see that it has a bitmap, fill in\n> the results in our cumulative \"want\" bitmap, and then stop walking its\n> parents (because we know everything they could tell us already).\n>\n> Then we visit C. It's not bitmapped, so we keep walking. Unlike a normal\n> traversal, we can't stop walking even though there are only\n> UNINTERESTING commits left, because we have to fill the complete bitmap,\n> including A and B (and you can imagine there might be thousands of\n> ancestors of A, too). The reason is that we skipped adding ancestors of\n> D when we saw its bitmap, so no still_interesting() cutoff will work\n> there.\n>\n> But how do we know that it's worth looking into the tree of \"B\"? If we\n> assume we visit commits before their ancestors (because of the commit\n> timestamp ordering), then we'd see that \"B\" is in the \"want\" bitmap\n> already, which makes it worth visiting its tree.\n>\n> Unfortunately we'd then continue on to \"A\", and it would _also_ look\n> interesting, because it's also in the \"want\" bitmap. We don't have an\n> easy way of knowing that \"A\" is basically already covered by \"B\", and is\n> therefore not worth pursuing. In this example, we could pass down a bit\n> from B to A as we traverse. But you can imagine another interesting\n> commit branched from A, which _would_ make A's tree worth considering.\n>\n> Fundamentally, as soon as we load a bitmap and stop traversing, we lose\n> all information about the graph structure.\n>\n> So the patch below just looks at every tree that might be worth\n> exploring (so both \"A\" and \"B\" here, but not \"C\"). That shouldn't be any\n> _worse_ than what the current code does (because it looks at all the\n> trees). It appears to behave correctly, at least so far as passing the\n> test suite. Running p5310 and p5311 against git.git and linux.git, it\n> seems to perform worse. I'm not quite sure why that is (i.e., if I\n> screwed up something in the implementation, or if the algorithm is\n> fundamentally worse).\n>\n> There are a lot of rough edges in the patch; I was just trying to see if\n> the idea was even viable. So don't bother reviewing it as a real\n> proposal for inclusion. If you do read it, I'd recommend just looking at\n> the post-image, since it's essentially a rewrite and the diff is a bit\n> messy.\n>\n> -Peff\n>\n> ---\n> pack-bitmap.c | 398 ++++++++++++++++++++++++--------------------------\n> 1 file changed, 193 insertions(+), 205 deletions(-)\n>\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index 6069b2fe55..4a40f62a38 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -12,6 +12,8 @@\n> #include \"packfile.h\"\n> #include \"repository.h\"\n> #include \"object-store.h\"\n> +#include \"blob.h\"\n> +#include \"prio-queue.h\"\n>\n> /*\n> * An entry on the bitmap index, representing the bitmap for a given\n> @@ -422,180 +424,22 @@ static int ext_index_add_object(struct bitmap_index *bitmap_git,\n> \treturn bitmap_pos + bitmap_git->pack->num_objects;\n> }\n>\n> -struct bitmap_show_data {\n> -\tstruct bitmap_index *bitmap_git;\n> -\tstruct bitmap *base;\n> -};\n> -\n> -static void show_object(struct object *object, const char *name, void *data_)\n> -{\n> -\tstruct bitmap_show_data *data = data_;\n> -\tint bitmap_pos;\n> -\n> -\tbitmap_pos = bitmap_position(data->bitmap_git, &object->oid);\n> -\n> -\tif (bitmap_pos < 0)\n> -\t\tbitmap_pos = ext_index_add_object(data->bitmap_git, object,\n> -\t\t\t\t\t\t name);\n> -\n> -\tbitmap_set(data->base, bitmap_pos);\n> -}\n> -\n> -static void show_commit(struct commit *commit, void *data)\n> -{\n> -}\n> -\n> -static int add_to_include_set(struct bitmap_index *bitmap_git,\n> -\t\t\t struct include_data *data,\n> -\t\t\t const struct object_id *oid,\n> -\t\t\t int bitmap_pos)\n> -{\n> -\tkhiter_t hash_pos;\n> -\n> -\tif (data->seen && bitmap_get(data->seen, bitmap_pos))\n> -\t\treturn 0;\n> -\n> -\tif (bitmap_get(data->base, bitmap_pos))\n> -\t\treturn 0;\n> -\n> -\thash_pos = kh_get_oid_map(bitmap_git->bitmaps, *oid);\n> -\tif (hash_pos < kh_end(bitmap_git->bitmaps)) {\n> -\t\tstruct stored_bitmap *st = kh_value(bitmap_git->bitmaps, hash_pos);\n> -\t\tbitmap_or_ewah(data->base, lookup_stored_bitmap(st));\n> -\t\treturn 0;\n> -\t}\n> -\n> -\tbitmap_set(data->base, bitmap_pos);\n> -\treturn 1;\n> -}\n> -\n> -static int should_include(struct commit *commit, void *_data)\n> -{\n> -\tstruct include_data *data = _data;\n> -\tint bitmap_pos;\n> -\n> -\tbitmap_pos = bitmap_position(data->bitmap_git, &commit->object.oid);\n> -\tif (bitmap_pos < 0)\n> -\t\tbitmap_pos = ext_index_add_object(data->bitmap_git,\n> -\t\t\t\t\t\t (struct object *)commit,\n> -\t\t\t\t\t\t NULL);\n> -\n> -\tif (!add_to_include_set(data->bitmap_git, data, &commit->object.oid,\n> -\t\t\t\tbitmap_pos)) {\n> -\t\tstruct commit_list *parent = commit->parents;\n> -\n> -\t\twhile (parent) {\n> -\t\t\tparent->item->object.flags |= SEEN;\n> -\t\t\tparent = parent->next;\n> -\t\t}\n> -\n> -\t\treturn 0;\n> -\t}\n> -\n> -\treturn 1;\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> -\t\t\t\t struct bitmap *seen)\n> +static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,\n> +\t\t\t\tstruct bitmap **base, struct commit *commit)\n> {\n> -\tstruct bitmap *base = NULL;\n> -\tint needs_walk = 0;\n> -\n> -\tstruct object_list *not_mapped = NULL;\n> -\n> -\t/*\n> -\t * Go through all the roots for the walk. The ones that have bitmaps\n> -\t * on the bitmap index will be `or`ed together to form an initial\n> -\t * global reachability analysis.\n> -\t *\n> -\t * The ones without bitmaps in the index will be stored in the\n> -\t * `not_mapped_list` for further processing.\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\tkhiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, object->oid);\n> -\n> -\t\t\tif (pos < kh_end(bitmap_git->bitmaps)) {\n> -\t\t\t\tstruct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);\n> -\t\t\t\tstruct ewah_bitmap *or_with = lookup_stored_bitmap(st);\n> -\n> -\t\t\t\tif (base == NULL)\n> -\t\t\t\t\tbase = ewah_to_bitmap(or_with);\n> -\t\t\t\telse\n> -\t\t\t\t\tbitmap_or_ewah(base, or_with);\n> -\n> -\t\t\t\tobject->flags |= SEEN;\n> -\t\t\t\tcontinue;\n> -\t\t\t}\n> -\t\t}\n> -\n> -\t\tobject_list_insert(object, ¬_mapped);\n> -\t}\n> -\n> -\t/*\n> -\t * Best case scenario: We found bitmaps for all the roots,\n> -\t * so the resulting `or` bitmap has the full reachability analysis\n> -\t */\n> -\tif (not_mapped == NULL)\n> -\t\treturn base;\n> -\n> -\troots = not_mapped;\n> -\n> -\t/*\n> -\t * Let's iterate through all the roots that don't have bitmaps to\n> -\t * check if we can determine them to be reachable from the existing\n> -\t * global bitmap.\n> -\t *\n> -\t * If we cannot find them in the existing global bitmap, we'll need\n> -\t * to push them to an actual walk and run it until we can confirm\n> -\t * they are reachable\n> -\t */\n> -\twhile (roots) {\n> -\t\tstruct object *object = roots->item;\n> -\t\tint pos;\n> -\n> -\t\troots = roots->next;\n> -\t\tpos = bitmap_position(bitmap_git, &object->oid);\n> -\n> -\t\tif (pos < 0 || base == NULL || !bitmap_get(base, pos)) {\n> -\t\t\tobject->flags &= ~UNINTERESTING;\n> -\t\t\tadd_pending_object(revs, object, \"\");\n> -\t\t\tneeds_walk = 1;\n> -\t\t} else {\n> -\t\t\tobject->flags |= SEEN;\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 == NULL)\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_data = &incdata;\n> -\n> -\t\tif (prepare_revision_walk(revs))\n> -\t\t\tdie(\"revision walk setup failed\");\n> +\tkhiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, commit->object.oid);\n> +\tif (pos < kh_end(bitmap_git->bitmaps)) {\n> +\t\tstruct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);\n> +\t\tstruct ewah_bitmap *or_with = lookup_stored_bitmap(st);\n>\n> -\t\tshow_data.bitmap_git = bitmap_git;\n> -\t\tshow_data.base = base;\n> +\t\tif (*base == NULL)\n> +\t\t\t*base = ewah_to_bitmap(or_with);\n> +\t\telse\n> +\t\t\tbitmap_or_ewah(*base, or_with);\n>\n> -\t\ttraverse_commit_list(revs, show_commit, show_object,\n> -\t\t\t\t &show_data);\n> +\t\treturn 1;\n> \t}\n> -\n> -\treturn base;\n> +\treturn 0;\n> }\n>\n> static void show_extended_objects(struct bitmap_index *bitmap_git,\n> @@ -665,24 +509,122 @@ 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> +static void add_object_to_bitmap(struct bitmap_index *bitmap_git,\n> +\t\t\t\t struct object *obj,\n> +\t\t\t\t struct bitmap *bitmap,\n> +\t\t\t\t struct bitmap *seen,\n> +\t\t\t\t int ignore_missing);\n> +\n> +static void add_tag_to_bitmap(struct bitmap_index *bitmap_git,\n> +\t\t\t struct tag *tag,\n> +\t\t\t struct bitmap *bitmap,\n> +\t\t\t struct bitmap *seen,\n> +\t\t\t int ignore_missing)\n> +{\n> +\tif (parse_tag(tag) < 0 || !tag->tagged) {\n> +\t\tif (ignore_missing)\n> +\t\t\treturn;\n> +\t\tdie(\"unable to parse tag %s\", oid_to_hex(&tag->object.oid));\n> +\t}\n> +\tadd_object_to_bitmap(bitmap_git, tag->tagged, bitmap, seen,\n> +\t\t\t ignore_missing);\n> +}\n> +\n> +static void add_tree_to_bitmap(struct bitmap_index *bitmap_git,\n> +\t\t\t struct tree *tree,\n> +\t\t\t struct bitmap *bitmap,\n> +\t\t\t struct bitmap *seen,\n> +\t\t\t int ignore_missing)\n> {\n> -\twhile (roots) {\n> -\t\tstruct object *object = roots->item;\n> -\t\troots = roots->next;\n> +\tstruct tree_desc desc;\n> +\tstruct name_entry entry;\n>\n> -\t\tif (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)\n> -\t\t\treturn 1;\n> +\tif (parse_tree(tree) < 0) {\n> +\t\tif (ignore_missing)\n> +\t\t\treturn;\n> +\t\tdie(\"unable to parse tree %s\", oid_to_hex(&tree->object.oid));\n> \t}\n>\n> -\treturn 0;\n> +\tinit_tree_desc(&desc, tree->buffer, tree->size);\n> +\twhile (tree_entry(&desc, &entry)) {\n> +\t\tif (S_ISDIR(entry.mode)) {\n> +\t\t\tstruct tree *t = lookup_tree(the_repository, &entry.oid);\n> +\t\t\tif (!t) {\n> +\t\t\t\tdie(_(\"entry '%s' in tree %s has tree mode, \"\n> +\t\t\t\t \"but is not a tree\"),\n> +\t\t\t\t entry.path, oid_to_hex(&tree->object.oid));\n> +\t\t\t}\n> +\t\t\tadd_object_to_bitmap(bitmap_git, &t->object,\n> +\t\t\t\t\t bitmap, seen, ignore_missing);\n> +\t\t} else if (!S_ISGITLINK(entry.mode)) {\n> +\t\t\tstruct blob *b = lookup_blob(the_repository, &entry.oid);\n> +\t\t\tif (!b) {\n> +\t\t\t\tdie(_(\"entry '%s' in tree %s has blob mode, \"\n> +\t\t\t\t \"but is not a blob\"),\n> +\t\t\t\t entry.path, oid_to_hex(&tree->object.oid));\n> +\t\t\t}\n> +\t\t\tadd_object_to_bitmap(bitmap_git, &b->object,\n> +\t\t\t\t\t bitmap, seen, ignore_missing);\n> +\t\t}\n> +\t}\n> +\n> +\tfree_tree_buffer(tree);\n> +}\n> +\n> +static void add_object_to_bitmap(struct bitmap_index *bitmap_git,\n> +\t\t\t\t struct object *obj,\n> +\t\t\t\t struct bitmap *bitmap,\n> +\t\t\t\t struct bitmap *seen,\n> +\t\t\t\t int ignore_missing)\n> +{\n> +\tint pos = bitmap_position(bitmap_git, &obj->oid);\n> +\n> +\tif (pos < 0)\n> +\t\tpos = ext_index_add_object(bitmap_git, obj, NULL);\n> +\n> +\tif (bitmap_get(bitmap, pos))\n> +\t\treturn; /* already there */\n> +\n> +\tif (seen && bitmap_get(seen, pos))\n> +\t\treturn; /* seen in other bitmap; not worth digging further */\n> +\n> +\tbitmap_set(bitmap, pos);\n> +\n> +\tif (obj->type == OBJ_BLOB)\n> +\t\treturn;\n> +\telse if (obj->type == OBJ_TAG)\n> +\t\tadd_tag_to_bitmap(bitmap_git, (struct tag *)obj,\n> +\t\t\t\t bitmap, seen, ignore_missing);\n> +\telse if (obj->type == OBJ_TREE)\n> +\t\tadd_tree_to_bitmap(bitmap_git, (struct tree *)obj,\n> +\t\t\t\t bitmap, seen, ignore_missing);\n> +\telse\n> +\t\tBUG(\"unexpected object type: %d\", obj->type);\n> +}\n> +\n> +static void add_objects_to_bitmap(struct bitmap_index *bitmap_git,\n> +\t\t\t\t struct object_list **list,\n> +\t\t\t\t struct bitmap *bitmap,\n> +\t\t\t\t struct bitmap *seen,\n> +\t\t\t\t int ignore_missing)\n> +{\n> +\twhile (*list) {\n> +\t\tstruct object_list *cur = *list;\n> +\n> +\t\tadd_object_to_bitmap(bitmap_git, cur->item,\n> +\t\t\t\t bitmap, seen, ignore_missing);\n> +\n> +\t\t*list = cur->next;\n> +\t\tfree(cur);\n> +\t}\n> }\n>\n> struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n> {\n> \tunsigned int i;\n>\n> +\tstruct prio_queue commits = { compare_commits_by_commit_date };\n> +\n> \tstruct object_list *wants = NULL;\n> \tstruct object_list *haves = NULL;\n>\n> @@ -714,24 +656,16 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n> \t\t\tobject = parse_object_or_die(&tag->tagged->oid, NULL);\n> \t\t}\n>\n> -\t\tif (object->flags & UNINTERESTING)\n> -\t\t\tobject_list_insert(object, &haves);\n> -\t\telse\n> -\t\t\tobject_list_insert(object, &wants);\n> +\t\tif (object->type == OBJ_COMMIT)\n> +\t\t\tprio_queue_put(&commits, object);\n> +\t\telse {\n> +\t\t\tif (object->flags & UNINTERESTING)\n> +\t\t\t\tobject_list_insert(object, &haves);\n> +\t\t\telse\n> +\t\t\t\tobject_list_insert(object, &wants);\n> +\t\t}\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> -\n> \t/*\n> \t * now we're going to use bitmaps, so load the actual bitmap entries\n> \t * from disk. this is the point of no return; after this the rev_list\n> @@ -742,20 +676,74 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\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> +\thaves_bitmap = bitmap_new();\n> +\twants_bitmap = bitmap_new();\n>\n> -\t\tif (haves_bitmap == NULL)\n> -\t\t\tBUG(\"failed to perform bitmap walk\");\n> -\t}\n> +\t/*\n> +\t * First traverse the relevant commits as we would for a normal\n> +\t * traversal.\n> +\t */\n> +\twhile (commits.nr) {\n> +\t\tstruct commit *commit = prio_queue_get(&commits);\n> +\t\tstruct bitmap **dst_bitmap;\n> +\t\tint pos;\n> +\t\tstruct commit_list *parent;\n> +\n> +\t\tif (commit->object.flags & UNINTERESTING)\n> +\t\t\tdst_bitmap = &haves_bitmap;\n> +\t\telse\n> +\t\t\tdst_bitmap = &wants_bitmap;\n>\n> -\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n> +\t\tpos = bitmap_position(bitmap_git, &commit->object.oid);\n> +\t\tif (pos >= 0 && *dst_bitmap && bitmap_get(*dst_bitmap, pos))\n> +\t\t\tcontinue; /* already covered */\n>\n> -\tif (!wants_bitmap)\n> -\t\tBUG(\"failed to perform bitmap walk\");\n> +\t\tif (add_commit_to_bitmap(bitmap_git, dst_bitmap, commit))\n> +\t\t\tcontinue; /* skip adding parents, they're covered */\n> +\n> +\n> +\t\t/* otherwise mark ourselves and queue dependent objects */\n> +\t\tif (pos < 0)\n> +\t\t\tpos = ext_index_add_object(bitmap_git, &commit->object, NULL);\n> +\t\tbitmap_set(*dst_bitmap, pos);\n> +\t\tif (parse_commit(commit)) {\n> +\t\t\tif (commit->object.flags & UNINTERESTING)\n> +\t\t\t\tcontinue;\n> +\t\t\tdie(\"unable to parse commit %s\",\n> +\t\t\t oid_to_hex(&commit->object.oid));\n> +\t\t}\n> +\t\tif (commit->object.flags & UNINTERESTING) {\n> +\t\t\t/*\n> +\t\t\t * If an uninteresting commit is in the \"wants\" bitmap,\n> +\t\t\t * then our tree is worth exploring. This means we may\n> +\t\t\t * miss some trees in the \"haves\" that are not\n> +\t\t\t * ancestors of \"wants\" (or that are, but we missed\n> +\t\t\t * because of out-of-order timestamps).\n> +\t\t\t */\n> +\t\t\tif (wants_bitmap && bitmap_get(wants_bitmap, pos))\n> +\t\t\t\tobject_list_insert(&get_commit_tree(commit)->object,\n> +\t\t\t\t\t\t &haves);\n> +\t\t} else {\n> +\t\t\t/*\n> +\t\t\t * \"wants\" must always be explored\n> +\t\t\t */\n> +\t\t\tobject_list_insert(&get_commit_tree(commit)->object,\n> +\t\t\t\t\t &wants);\n> +\t\t}\n> +\n> +\t\tfor (parent = commit->parents; parent; parent = parent->next) {\n> +\t\t\tif (commit->object.flags & UNINTERESTING)\n> +\t\t\t\tparent->item->object.flags |= UNINTERESTING;\n> +\t\t\tprio_queue_put(&commits, parent->item);\n> +\t\t}\n> +\t}\n> +\n> +\t/*\n> +\t * At this point we've processed all of the commits, and queued items\n> +\t * in \"haves\" and \"wants\" that need to be marked.\n> +\t */\n> +\tadd_objects_to_bitmap(bitmap_git, &haves, haves_bitmap, NULL, 1);\n> +\tadd_objects_to_bitmap(bitmap_git, &wants, wants_bitmap, haves_bitmap, 0);\n>\n> \tif (haves_bitmap)\n> \t\tbitmap_and_not(wants_bitmap, haves_bitmap);\n"},{"id":"376149","messageId":"20190524072426.GG25694@sigill.intra.peff.net","threadId":"50501","inReplyTo":"1e0d216b-5e68-faff-883c-778a04f55bde@gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-24T07:24:26Z","receivedAt":"2019-05-24T07:24:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 23, 2019 at 08:53:56AM -0400, Derrick Stolee wrote:\n\n> > I spent a while thinking and experimenting with this tonight. The result\n> > is the patch below. Ævar, do you still have a copy of the repo that\n> > misbehaved? I'd be curious to see how it fares.\n> \n> This patch caught my attention, and I think I understand some of the issues\n> at hand. I'm not well-versed specifically in Git's bitmap implementation.\n> The fundamental ideas are there, but my perspective is biased by my own\n> independent bitmap implementation for Azure Repos. What worked there may not\n> work at all here.\n\nThanks for looking at this. There are a lot of short-comings in the\ncurrent bitmap implementation, so if there's a better way to do things,\nI'm not opposed to moving to a new format. :)\n\n> > Finding the right trees to explore is a little tricky with bitmaps. In\n> > a normal traversal, we consider the \"edges\" to be worth exploring.\n> > I.e., the places where an UNINTERESTING commit is the parent of an\n> > interesting one.\n> \n> This is the \"commit frontier\" which I bring up again below.\n\nRight. I actually had trouble coming up with a succinct way of\ndescribing this, and stole the definition from your recent blog post. ;)\n\n> > But with bitmaps, we don't have that information in the same way,\n> > because we're trying to avoid walking the commits in the first place. So\n> > e.g., in a history like this:\n> > \n> > A--B--C\n> > \\\n> > D\n> > \n> > Let's imagine we're computing \"C..D\", and that D has a bitmap on disk\n> > but C does not.\n> \n> (As I read your discussion below, I'm confused. For \"C..D\", C is a have\n> and D is a want. We should explore all the haves _first_, then walk the\n> wants, right?)\n\nI think I may have confused things by starting my description with a\nhypothetical combined want/have walk. To take a step back: the problem\nwe were discussing is that we spend a lot of time reading trees to fill\nin the \"have\" bitmap, even though most of those objects are unlikely to\nbe in the \"want\" in the first place (only the frontier trees are really\nuseful).\n\nThe current code does indeed fill the \"have\" bitmap first (so that while\nwalking \"want\", it can avoid walking down paths whose bits we know we're\ngoing to clear eventually anyway). But we can't know the frontier if we\ncompletely fill the \"have\" bitmap first. We have to walk both sides\ntogether, looking for the frontier.\n\n> > When we visit D, we'll see that it has a bitmap, fill in\n> > the results in our cumulative \"want\" bitmap, and then stop walking its\n> > parents (because we know everything they could tell us already).\n> \n> I may be misreading something, but we would construct _a_ bitmap for C\n> by walking its reachable objects until hitting a bitmap we know about.\n> Perhaps A or B have a bitmap to start the construction. If we never\n> construct a bitmap for C, then we don't know what to remove from the \"D\"\n> bitmap to show the difference.\n\nYes, and that's how the current code works. If we walk back to B and it\nhas a bitmap, we can stop walking there and just OR in its bitmap, and\nlook at the trees for any intermediate commits (in this case just C) to\nfill in the rest.\n\nThe problem is that we don't have a bitmap for every commit. So you can\nimagine a history like this:\n\n A_1 -- A_2 -- ... -- A_1000 -- B -- C\n \\\n\t\t\t\t D\n\nwhere we have a bitmap _only_ for D. Filling in the accurate and true\nbitmap for C requires walking a thousand commits (and their trees!),\nwhen the non-bitmap algorithm would find the frontier at B and call that\ngood enough.\n\n> If \"C\" is not even in the bitmap pack, then we don't use bitmaps for\n> this calculation because of this condition:\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\nRight, but it may be in the pack but without a bitmap. We don't store a\nbitmap for every commit. The idea was to save space, but select some key\ncommits that let us generally find a bitmap with a small amount of\nwalking. And most of the time it works fine. But in some cases, we seem\nto find pathological cases where we do quite a lot of walking.\n\nAs I said earlier in the thread, I suspect our commit selection is not\ngreat. It's mostly some heuristics we threw together in 2013, and I\ndon't think it was tested very thoroughly. So fixing that may be a\nsimpler approach.\n\nWhat I was wondering here was whether we could get an easy fix based on\nthe same frontier ideas that the non-bitmap walk uses.\n\n> I'm of the opinion that the old method was better. It followed a very clear\n> three-step process:\n> \n> 1. Compute the \"haves\" bitmap.\n> \n> 2. Compute the \"wants\" bitmap, but don't explore into the \"haves\" bitmap.\n> \n> 3. Subtract the \"haves\" bitmap from the \"wants\" (in case we added bits to\n> the wants before they were in the haves).\n\nRight, this is _way_ simpler. But it necessarily means spending effort\nto find the complete \"haves\", because we don't know which parts are\nuseful.\n\n> But there is hope in your idea to improve some cases. As noted, we give up\n> if all of the haves are not in the bitmapped pack. By starting with a\n> commit walk, we can find the \"commit frontier,\" which is the set of commits\n> that are explored by paint_down_to_common(). In this case, the set {B, C, D}.\n> \n> After walking commits and finding a set of UNINTERESTING commits, we could\n> look for any UNINTERESTING commits that have bitmaps (or simply are in the\n> bitmapped pack) and use those to see our \"haves\" bitmap. So, if B has a\n> bitmap, but C is too new for the bitmap, then we can still create the haves\n> based on B and then take a bitmap diff \"D minus B\".\n\nBut doing that commit walk to find the frontier negates part of the\npurpose of using the bitmaps, which is avoiding even walking commits.\nGoing back to a variant of our example:\n\n A -- B -- C_1 -- .. -- C_1000\n \\\n\t D_1 -- .. -- D_1000\n\nIf we have a bitmap at C_1000 and D_1000, we don't have to walk any\ncommits at all. But finding the frontier requires walking 2000 commits.\n\nIs there a way to find it with just bitmaps? You can certainly find the\nintersection, but you don't have any idea which of the many shared\ncommits is the merge base. Of course in this example you don't actually\ncare about the frontier (you have the full answer immediately). But how\ndo you decide which way to optimize: try to avoid walking commits to\nget a quick answer from bitmaps, or prefer to walk some commits to find\nthe frontier and avoid opening too many trees?\n\n-Peff\n"},{"id":"376150","messageId":"20190524072724.GH25694@sigill.intra.peff.net","threadId":"50501","inReplyTo":"87tvdlt1jp.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-24T07:27:24Z","receivedAt":"2019-05-24T07:27:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, May 23, 2019 at 09:26:34PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > I spent a while thinking and experimenting with this tonight. The result\n> > is the patch below. Ævar, do you still have a copy of the repo that\n> > misbehaved? I'd be curious to see how it fares.\n> \n> No, sorry. I think we could make an artificial test to emulate it, which\n> would be something like:\n> \n> * ~1 million commits\n> * local clone setup to fetch all branches/tags (default 'git clone')\n> * local a bit ahead/behind\n> * Have old \"main\" pack with *.bitmap, bunch of other packs/loose objects without that\n> * push try to push the local change upstream (or to a topic branch)\n> \n> I tried briefly to emulate this with git.git with:\n> [...]\n> But didn't get anywhere, probably because here my topics are all stuff I\n> have already, and I just have 2x packs.\n\nYeah, I haven't been able to find a reproduction for this problem at\nwill. The bitmaps are _supposed_ to be sprinkled around through the\ncommit graph so that we don't have to walk far. But presumably in your\ncase that was not so.\n\nI'm not sure what tickles the bitmap-writer to fail so hard. Is it\nhaving too many refs? Weird patterns in the graph? Just a ton of\ncommits?\n\n-Peff\n"},{"id":"376152","messageId":"87r28offs6.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190524072724.GH25694@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-24T07:55:05Z","receivedAt":"2019-05-24T07:55:10Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 24 2019, Jeff King wrote:\n\n> On Thu, May 23, 2019 at 09:26:34PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> > I spent a while thinking and experimenting with this tonight. The result\n>> > is the patch below. Ævar, do you still have a copy of the repo that\n>> > misbehaved? I'd be curious to see how it fares.\n>>\n>> No, sorry. I think we could make an artificial test to emulate it, which\n>> would be something like:\n>>\n>> * ~1 million commits\n>> * local clone setup to fetch all branches/tags (default 'git clone')\n>> * local a bit ahead/behind\n>> * Have old \"main\" pack with *.bitmap, bunch of other packs/loose objects without that\n>> * push try to push the local change upstream (or to a topic branch)\n>>\n>> I tried briefly to emulate this with git.git with:\n>> [...]\n>> But didn't get anywhere, probably because here my topics are all stuff I\n>> have already, and I just have 2x packs.\n>\n> Yeah, I haven't been able to find a reproduction for this problem at\n> will. The bitmaps are _supposed_ to be sprinkled around through the\n> commit graph so that we don't have to walk far. But presumably in your\n> case that was not so.\n>\n> I'm not sure what tickles the bitmap-writer to fail so hard. Is it\n> having too many refs? Weird patterns in the graph? Just a ton of\n> commits?\n\nAh, why did only this ancient (big) pack have a bitmap?\n\nThe bitmap writer had never failed, this was just a repository where\nsome automation (on a dev/staging box) cloned a repo, and someone had\nonce run a manual \"repack\" to make make a pack with a bitmap.\n\nThen as time passed that pack stayed around, and re-looking at this that\ncould have only happened because I had gc.bigPackThreshold turned on.\n\nI.e. without that we'd have eventually done a full repack, so the bitmap\nwould have gone away.\n\nSo getting the repo into that state was a series of unlikely events.\n\nI think to the extent that this is an issue we can reproduce in the\nfuture the proper fix for it in lieu of some easy fix in the bitmap code\nwould be to just teach \"gc\" to unlink old *.bitmap files if we detect\nthey're too stale.\n\nI.e. we don't need to deal gracefully with some case where the bitmaps\njust cover some tiny part of the graph, we can just teach \"gc\" to either\nupdate them, or (if we're not currently writing them) unlink them.\n\nThat seems to me to be a good idea in general, not just with bitmaps but\nalso the commit graph. If we're doing a GC and our current settings\naren't such that we'd update those files, shouldn't we just unlink them?\n"},{"id":"376156","messageId":"20190524082605.GB9082@sigill.intra.peff.net","threadId":"50501","inReplyTo":"87r28offs6.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-05-24T08:26:06Z","receivedAt":"2019-05-24T08:26:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, May 24, 2019 at 09:55:05AM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> > I'm not sure what tickles the bitmap-writer to fail so hard. Is it\n> > having too many refs? Weird patterns in the graph? Just a ton of\n> > commits?\n> \n> Ah, why did only this ancient (big) pack have a bitmap?\n> \n> The bitmap writer had never failed, this was just a repository where\n> some automation (on a dev/staging box) cloned a repo, and someone had\n> once run a manual \"repack\" to make make a pack with a bitmap.\n\nJust to be clear, by \"fail\" I didn't mean that the writer failed to\nproduce. I just meant it had poor commit selection for its bitmap\ncoverage. But...\n\n> Then as time passed that pack stayed around, and re-looking at this that\n> could have only happened because I had gc.bigPackThreshold turned on.\n> \n> I.e. without that we'd have eventually done a full repack, so the bitmap\n> would have gone away.\n> \n> So getting the repo into that state was a series of unlikely events.\n\nAh, now that's interesting. The issue may have just been that we had a\nton of un-bitmapped commits because they weren't in the bitmapped pack\nat all. The logic that Stolee pointed out earlier:\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\nis pretty feeble. If you have even _one_ UNINTERESTING tip that's in the\npack, we'll try to use bitmaps. And in your case, you almost certainly\nhad old tags on both the client and the server there were in the old\nbitmapped pack, but then a huge swath of history that had happened since\nthen. And it was that newer part of the graph that we had to walk to\nfill in the bitmap.\n\nSo all of this makes pretty good sense to me now. Bitmaps work\nincrementally as you add new, un-bitmapped history. But the cost gets\nhigher and higher the longer you go before repacking and generating new\nbitmaps. So your case was very similar to a repo that uses bitmaps but\njust hadn't packed in a really long time.\n\n> I think to the extent that this is an issue we can reproduce in the\n> future the proper fix for it in lieu of some easy fix in the bitmap code\n> would be to just teach \"gc\" to unlink old *.bitmap files if we detect\n> they're too stale.\n\nYeah. This could happen if you simply accumulated history without ever\nrunning \"gc\". But in general we can probably assume that \"gc\" will run\nperiodically (though there is a real blind spot if you push up a very\nhuge chunk of history in one pack, since gc counts packs, not objects).\n\nI agree that if gc is deciding to leave a big pack, it should probably\nditch the bitmaps for it.\n\n> I.e. we don't need to deal gracefully with some case where the bitmaps\n> just cover some tiny part of the graph, we can just teach \"gc\" to either\n> update them, or (if we're not currently writing them) unlink them.\n\nUnfortunately I don't think we can update them, because all of the\nreachable objects need to be in the same pack. So any scheme that isn't\ndoing a periodic all-into-one repack probably shouldn't be using\nbitmaps. I wonder if we need to tweak Eric's bitmaps-by-default logic to\nbetter account for this.\n\n> That seems to me to be a good idea in general, not just with bitmaps but\n> also the commit graph. If we're doing a GC and our current settings\n> aren't such that we'd update those files, shouldn't we just unlink them?\n\nI don't think the commit graph would suffer from this. It's not tied to\na specific pack, so it can be freely updated on any gc. You still have\nthe problem when gc does not run. It's possible that auto-gc should have\nseparate thresholds for different activities (e.g., number of packs\nshould tell us when to repack objects, number of loose refs should tell\nus when to pack refs, number of un-annotated commits should tell us when\nto update the commit graph). The trouble is that some of those checks\nare non-trivial.\n\nIn the long run, I think the plan is for the commit graph to allow cheap\nincremental updating, which may make it reasonable to just update it\npreemptively after every fetch/push.\n\n-Peff\n"},{"id":"376158","messageId":"87pno8fcp8.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190524082605.GB9082@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-24T09:01:39Z","receivedAt":"2019-05-24T09:01:44Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 24 2019, Jeff King wrote:\n\n> On Fri, May 24, 2019 at 09:55:05AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>\n>> > I'm not sure what tickles the bitmap-writer to fail so hard. Is it\n>> > having too many refs? Weird patterns in the graph? Just a ton of\n>> > commits?\n>>\n>> Ah, why did only this ancient (big) pack have a bitmap?\n>>\n>> The bitmap writer had never failed, this was just a repository where\n>> some automation (on a dev/staging box) cloned a repo, and someone had\n>> once run a manual \"repack\" to make make a pack with a bitmap.\n>\n> Just to be clear, by \"fail\" I didn't mean that the writer failed to\n> produce. I just meant it had poor commit selection for its bitmap\n> coverage. But...\n>\n>> Then as time passed that pack stayed around, and re-looking at this that\n>> could have only happened because I had gc.bigPackThreshold turned on.\n>>\n>> I.e. without that we'd have eventually done a full repack, so the bitmap\n>> would have gone away.\n>>\n>> So getting the repo into that state was a series of unlikely events.\n>\n> Ah, now that's interesting. The issue may have just been that we had a\n> ton of un-bitmapped commits because they weren't in the bitmapped pack\n> at all. The logic that Stolee pointed out earlier:\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>\n> is pretty feeble. If you have even _one_ UNINTERESTING tip that's in the\n> pack, we'll try to use bitmaps. And in your case, you almost certainly\n> had old tags on both the client and the server there were in the old\n> bitmapped pack, but then a huge swath of history that had happened since\n> then. And it was that newer part of the graph that we had to walk to\n> fill in the bitmap.\n>\n> So all of this makes pretty good sense to me now. Bitmaps work\n> incrementally as you add new, un-bitmapped history. But the cost gets\n> higher and higher the longer you go before repacking and generating new\n> bitmaps. So your case was very similar to a repo that uses bitmaps but\n> just hadn't packed in a really long time.\n>\n>> I think to the extent that this is an issue we can reproduce in the\n>> future the proper fix for it in lieu of some easy fix in the bitmap code\n>> would be to just teach \"gc\" to unlink old *.bitmap files if we detect\n>> they're too stale.\n>\n> Yeah. This could happen if you simply accumulated history without ever\n> running \"gc\". But in general we can probably assume that \"gc\" will run\n> periodically (though there is a real blind spot if you push up a very\n> huge chunk of history in one pack, since gc counts packs, not objects).\n>\n> I agree that if gc is deciding to leave a big pack, it should probably\n> ditch the bitmaps for it.\n>\n>> I.e. we don't need to deal gracefully with some case where the bitmaps\n>> just cover some tiny part of the graph, we can just teach \"gc\" to either\n>> update them, or (if we're not currently writing them) unlink them.\n>\n> Unfortunately I don't think we can update them, because all of the\n> reachable objects need to be in the same pack. So any scheme that isn't\n> doing a periodic all-into-one repack probably shouldn't be using\n> bitmaps. I wonder if we need to tweak Eric's bitmaps-by-default logic to\n> better account for this.\n\nI mean either we'd update them via repacking, or have some heuristic to\ndo away with them.\n\n>> That seems to me to be a good idea in general, not just with bitmaps but\n>> also the commit graph. If we're doing a GC and our current settings\n>> aren't such that we'd update those files, shouldn't we just unlink them?\n>\n> I don't think the commit graph would suffer from this. It's not tied to\n> a specific pack, so it can be freely updated on any gc. You still have\n> the problem when gc does not run. It's possible that auto-gc should have\n> separate thresholds for different activities (e.g., number of packs\n> should tell us when to repack objects, number of loose refs should tell\n> us when to pack refs, number of un-annotated commits should tell us when\n> to update the commit graph). The trouble is that some of those checks\n> are non-trivial.\n>\n> In the long run, I think the plan is for the commit graph to allow cheap\n> incremental updating, which may make it reasonable to just update it\n> preemptively after every fetch/push.\n\nI don't think it's a performance problem to have an old commit-graph\nlying around. But if you turn on the commit-graph, run gc a bunch, then\nturn it off in config we'll have it lying around forever, even if you do\nsubsequent gc's.\n\nSo I think we should delete such things on the general principle that\nthe end-state of a gc's shouldn't be the accumulation of the values of\npast configuration options if we can help it.\n\nMaybe that screws over other users who did a \"commit-graph write\"\nwithout setting gc.writeCommitGraph, but I think the only sane thing to\ndo is to make \"gc\" fully 'own' such things if its turned on at all. We\ndon't worry e.g. that we can't repack some recent pack because a user\nmight have just manually produced it with handcrafted love seconds\nearlier.\n\nSome of what you bring up is \"let's do incremental GC\". I agree, but\nthink that can be considered separately from what GC should do *when* it\nruns, whether that's a \"full\" or \"partial\" run.\n"},{"id":"376165","messageId":"20190524092920.GD951@szeder.dev","threadId":"50501","inReplyTo":"87pno8fcp8.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-24T09:29:20Z","receivedAt":"2019-05-24T09:29:27Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, May 24, 2019 at 11:01:39AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> I don't think it's a performance problem to have an old commit-graph\n> lying around. But if you turn on the commit-graph, run gc a bunch, then\n> turn it off in config we'll have it lying around forever, even if you do\n> subsequent gc's.\n> \n> So I think we should delete such things on the general principle that\n> the end-state of a gc's shouldn't be the accumulation of the values of\n> past configuration options if we can help it.\n> \n> Maybe that screws over other users who did a \"commit-graph write\"\n> without setting gc.writeCommitGraph, but I think the only sane thing to\n> do is to make \"gc\" fully 'own' such things if its turned on at all.\n\nNote that there is 'core.commitGraph' as well; as long as it's\nenabled, no commit-graph files should be deleted.\n\n"},{"id":"376175","messageId":"cbd7540b-0d36-e378-c5e7-871a70e47e18@gmail.com","threadId":"50501","inReplyTo":"20190524072426.GG25694@sigill.intra.peff.net","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-24T10:33:00Z","receivedAt":"2019-05-24T10:33:04Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/24/2019 3:24 AM, Jeff King wrote:\n> On Thu, May 23, 2019 at 08:53:56AM -0400, Derrick Stolee wrote:\n> \n>>> I spent a while thinking and experimenting with this tonight. The result\n>>> is the patch below. Ævar, do you still have a copy of the repo that\n>>> misbehaved? I'd be curious to see how it fares.\n>>\n>> This patch caught my attention, and I think I understand some of the issues\n>> at hand. I'm not well-versed specifically in Git's bitmap implementation.\n>> The fundamental ideas are there, but my perspective is biased by my own\n>> independent bitmap implementation for Azure Repos. What worked there may not\n>> work at all here.\n> \n> Thanks for looking at this. There are a lot of short-comings in the\n> current bitmap implementation, so if there's a better way to do things,\n> I'm not opposed to moving to a new format. :)\n> \n>>> Finding the right trees to explore is a little tricky with bitmaps. In\n>>> a normal traversal, we consider the \"edges\" to be worth exploring.\n>>> I.e., the places where an UNINTERESTING commit is the parent of an\n>>> interesting one.\n>>\n>> This is the \"commit frontier\" which I bring up again below.\n> \n> Right. I actually had trouble coming up with a succinct way of\n> describing this, and stole the definition from your recent blog post. ;)\n> \n>>> But with bitmaps, we don't have that information in the same way,\n>>> because we're trying to avoid walking the commits in the first place. So\n>>> e.g., in a history like this:\n>>>\n>>> A--B--C\n>>> \\\n>>> D\n>>>\n>>> Let's imagine we're computing \"C..D\", and that D has a bitmap on disk\n>>> but C does not.\n>>\n>> (As I read your discussion below, I'm confused. For \"C..D\", C is a have\n>> and D is a want. We should explore all the haves _first_, then walk the\n>> wants, right?)\n> \n> I think I may have confused things by starting my description with a\n> hypothetical combined want/have walk. To take a step back: the problem\n> we were discussing is that we spend a lot of time reading trees to fill\n> in the \"have\" bitmap, even though most of those objects are unlikely to\n> be in the \"want\" in the first place (only the frontier trees are really\n> useful).\n\nThank you for resolving my confusion.\n\n[snip]\n\n> As I said earlier in the thread, I suspect our commit selection is not\n> great. It's mostly some heuristics we threw together in 2013, and I\n> don't think it was tested very thoroughly. So fixing that may be a\n> simpler approach.\n\nIt's a hard problem! There are no _sure_ answers here, and what works in\nsome cases will probably not work in other cases.\n \n> What I was wondering here was whether we could get an easy fix based on\n> the same frontier ideas that the non-bitmap walk uses.\n\n[snip]\n \n> But doing that commit walk to find the frontier negates part of the\n> purpose of using the bitmaps, which is avoiding even walking commits.\n> Going back to a variant of our example:\n> \n> A -- B -- C_1 -- .. -- C_1000\n> \\\n> \t D_1 -- .. -- D_1000\n> \n> If we have a bitmap at C_1000 and D_1000, we don't have to walk any\n> commits at all. But finding the frontier requires walking 2000 commits.\n\nIn my opinion, walking commits is easy (easier with the commit-graph)\nand walking trees is hard. We probably _should_ do more commit walking if\nit helps avoid walking some trees.\n \n> Is there a way to find it with just bitmaps? You can certainly find the\n> intersection, but you don't have any idea which of the many shared\n> commits is the merge base. Of course in this example you don't actually\n> care about the frontier (you have the full answer immediately). But how\n> do you decide which way to optimize: try to avoid walking commits to\n> get a quick answer from bitmaps, or prefer to walk some commits to find\n> the frontier and avoid opening too many trees?\n\nWith a new perspective on the problem, I think perhaps trying to solve this\nproblem with bitmaps is incorrect. If you want to use bitmaps for C..D and\nyou don't have any bitmaps in the range D..C, then maybe we should just use\nthe old-fashioned method of walking trees? In your examples above, the\nnew method would walk trees for the commits in {B, C_i, D_j} while the\nbitmap method would walk trees for the commits in {B, C_i, A_k}. I would\nexpect the list of {A_k} commits to be the largest in most cases.\n\nThe approach here would be to do the commit frontier walk, and check for\ncommits with bitmaps along the way. If we don't find an UNINTERESTING\nbitmap, then use the non-bitmap way instead. Perhaps worth a shot.\n\nI'll bring up this code snippet again:\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\nIn addition to this, we can fill the \"haves\" set with the commits\nin D..C (with boundary) and then check if any of those commits have a\nprecomputed bitmap. If not, goto cleanup.\n\nThanks,\n-Stolee\n"},{"id":"376177","messageId":"87imu0f6fh.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190524092920.GD951@szeder.dev","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-24T11:17:06Z","receivedAt":"2019-05-24T11:17:12Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 24 2019, SZEDER Gábor wrote:\n\n> On Fri, May 24, 2019 at 11:01:39AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>> I don't think it's a performance problem to have an old commit-graph\n>> lying around. But if you turn on the commit-graph, run gc a bunch, then\n>> turn it off in config we'll have it lying around forever, even if you do\n>> subsequent gc's.\n>>\n>> So I think we should delete such things on the general principle that\n>> the end-state of a gc's shouldn't be the accumulation of the values of\n>> past configuration options if we can help it.\n>>\n>> Maybe that screws over other users who did a \"commit-graph write\"\n>> without setting gc.writeCommitGraph, but I think the only sane thing to\n>> do is to make \"gc\" fully 'own' such things if its turned on at all.\n>\n> Note that there is 'core.commitGraph' as well; as long as it's\n> enabled, no commit-graph files should be deleted.\n\nWhy? If we won't update it or write it if it's not there, why keep it\naround?\n\nIt means the commit-graph code and anything else (like bitmaps) needs to\ndeal with stale data for the common and default gc --auto case.\n\nYou also can't have e.g. a global core.commitGraph=true config along\nwith a per-repo gc.writeCommitGraph=true config do what you expect.\n\nNow just because you wanted to write it for some you'll end up keeping\nit around forever because you'd also want to optimistically always use\nit if it's there.\n\nNote that I'm talking about the *default* gc semantics, they don't have\nto cover all advanced use-cases, just be good enough for most, and it's\nalso important that they're as simple as possible, and don't result in\nstuff like \"my performance sucks because I turned this config option on\nonce a year ago for 2 days\".\n"},{"id":"376178","messageId":"20190524113112.30185-1-dstolee@microsoft.com","threadId":"50501","inReplyTo":"20190523113031.GA17448@sigill.intra.peff.net","subject":"[PATCH] pack-bitmap: look for an uninteresting bitmap","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-05-24T11:31:12Z","receivedAt":"2019-05-24T11:31:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"If we try to do a range query such as C..D with topology as\n\n A_0 - ... - A_10000 - B - C_1 - ... - C_1000 - C\n \\\n D_1 - ... - D_1000 - D\n\nand none of the commits in {A_i, B, C_j, C} have a computed\nbitmap, then we will very likely walk many many trees before\ncomputing one for the \"have\" bitmap.\n\nInstead, perform a commit walk to the boundary of C...D and\nlook for computed bitmaps in { B, C_j, C }. If any are found,\nthen it is worth starting from there and building a bitmap.\nIf not, revert to the old method of walking trees.\n\nNOTE: this is only a proof-of-concept, as it fails a test in\nt5310-pack-bitmaps.sh (clearly marked as a failure now).\n\nReported-by: Ævar Arnfjörð Bjarmason \nHelped-by: Jeff King \nSigned-off-by: Derrick Stolee \n---\n\nOn 5/23/2019 7:30 AM, Jeff King wrote:> +\t/*\n> +\t * First traverse the relevant commits as we would for a normal\n> +\t * traversal.\n> +\t */\n> +\twhile (commits.nr) {\n> +\t\tstruct commit *commit = prio_queue_get(&commits);\n> +\t\tstruct bitmap **dst_bitmap;\n\nI was looking at this code again, and noticed this while() condition.\n\nShouldn't this use queue_has_nonstale() like in paint_down_to_common()?\n\nLooking at the body of the loop, I don't see a way for the loop to stop\nwithout it walking the entire history of C _and_ D.\n\nBased on that, I wrote the patch below as an experiment. The\nhas_uninteresting_bitmap_in_frontier() shamelessly steals code from\npaint_down_to_common(). Note the failing test, but perhaps there is\nsomething salvageable from this.\n\nThanks,\n-Stolee\n\n\n pack-bitmap.c | 92 ++++++++++++++++++++++++++++++++++++++++-\n t/t5310-pack-bitmaps.sh | 2 +-\n 2 files changed, 91 insertions(+), 3 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 6069b2fe55..1f4683663e 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -12,6 +12,7 @@\n #include \"packfile.h\"\n #include \"repository.h\"\n #include \"object-store.h\"\n+#include \"prio-queue.h\"\n \n /*\n * An entry on the bitmap index, representing the bitmap for a given\n@@ -679,6 +680,81 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n \treturn 0;\n }\n \n+#define PARENT1 (1u<<16)\n+#define PARENT2 (1u<<17)\n+#define STALE (1u<<18)\n+\n+static const int all_flags = { PARENT1 | PARENT2 | STALE };\n+\n+static int queue_has_nonstale(struct prio_queue *queue)\n+{\n+\tint i;\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct commit *commit = queue->array[i].data;\n+\t\tif (!(commit->object.flags & STALE))\n+\t\t\treturn 1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int has_uninteresting_bitmap_in_frontier(struct repository *r,\n+\t\t\t\t\t\tstruct commit_list *list,\n+\t\t\t\t\t\tstruct bitmap_index *bitmap_git)\n+{\n+\tint res = 0;\n+\tstruct commit_list *iter = list;\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n+\n+\twhile (iter) {\n+\t\tprio_queue_put(&queue, iter->item);\n+\t\titer = iter->next;\n+\t}\n+\n+\twhile (queue_has_nonstale(&queue)) {\n+\t\tstruct commit *commit = prio_queue_get(&queue);\n+\t\tstruct commit_list *parents;\n+\t\tint flags;\n+\n+\t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n+\t\tif (flags == (PARENT1 | PARENT2)) {\n+\t\t\t/* Mark parents of a found merge stale */\n+\t\t\tflags |= STALE;\n+\t\t}\n+\n+\t\tif (flags & PARENT1) {\n+\t\t\tkhiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, commit->object.oid);\n+\n+\t\t\tif (pos < kh_end(bitmap_git->bitmaps)) {\n+\t\t\t\tres = 1;\n+\t\t\t\tgoto cleanup;\n+\t\t\t}\n+\t\t}\n+\n+\t\tparents = commit->parents;\n+\t\twhile (parents) {\n+\t\t\tstruct commit *p = parents->item;\n+\t\t\tparents = parents->next;\n+\t\t\tif ((p->object.flags & flags) == flags)\n+\t\t\t\tcontinue;\n+\t\t\tif (repo_parse_commit(r, p))\n+\t\t\t\tgoto cleanup;\n+\t\t\tp->object.flags |= flags;\n+\t\t\tprio_queue_put(&queue, p);\n+\t\t}\n+\t}\n+\n+cleanup:\n+\tclear_prio_queue(&queue);\n+\n+\titer = list;\n+\twhile (iter) {\n+\t\tclear_commit_marks(iter->item, all_flags);\n+\t\titer = iter->next;\n+\t}\n+\n+\treturn res;\n+}\n+\n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n {\n \tunsigned int i;\n@@ -689,6 +765,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tstruct bitmap *wants_bitmap = NULL;\n \tstruct bitmap *haves_bitmap = NULL;\n \n+\tstruct commit_list *commits = NULL;\n+\n \tstruct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));\n \t/* try to open a bitmapped pack, but don't parse it yet\n \t * because we may not need to use it */\n@@ -704,16 +782,22 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \t\twhile (object->type == OBJ_TAG) {\n \t\t\tstruct tag *tag = (struct tag *) object;\n \n-\t\t\tif (object->flags & UNINTERESTING)\n+\t\t\tif (object->flags & UNINTERESTING) {\n+\t\t\t\tobject->flags |= PARENT1;\n \t\t\t\tobject_list_insert(object, &haves);\n-\t\t\telse\n+\t\t\t} else {\n+\t\t\t\tobject->flags |= PARENT2;\n \t\t\t\tobject_list_insert(object, &wants);\n+\t\t\t}\n \n \t\t\tif (!tag->tagged)\n \t\t\t\tdie(\"bad tag\");\n \t\t\tobject = parse_object_or_die(&tag->tagged->oid, NULL);\n \t\t}\n \n+\t\tif (object->type == OBJ_COMMIT)\n+\t\t\tcommit_list_insert((struct commit *)object, &commits);\n+\n \t\tif (object->flags & UNINTERESTING)\n \t\t\tobject_list_insert(object, &haves);\n \t\telse\n@@ -740,6 +824,10 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tif (load_pack_bitmap(bitmap_git) < 0)\n \t\tgoto cleanup;\n \n+\tif (!has_uninteresting_bitmap_in_frontier(the_repository, commits, bitmap_git))\n+\t\tgoto cleanup;\n+\n+\t/* this is the real no-turning-back point! */\n \tobject_array_clear(&revs->pending);\n \n \tif (haves) {\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex a26c8ba9a2..615608fbbf 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -422,7 +422,7 @@ test_expect_success 'fetch without bitmaps ignores delta against old base' '\n '\n \n # And do the same for the bitmap case, where we do expect to find the delta.\n-test_expect_success 'fetch with bitmaps can reuse old base' '\n+test_expect_failure 'fetch with bitmaps can reuse old base' '\n \ttest_config pack.usebitmaps true &&\n \ttest_when_finished \"rm -rf client.git\" &&\n \tgit init --bare client.git &&\n-- \n2.22.0.rc0\n\n"},{"id":"376180","messageId":"20190524114114.GH951@szeder.dev","threadId":"50501","inReplyTo":"87imu0f6fh.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-24T11:41:14Z","receivedAt":"2019-05-24T11:41:20Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, May 24, 2019 at 01:17:06PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Fri, May 24 2019, SZEDER Gábor wrote:\n> \n> > On Fri, May 24, 2019 at 11:01:39AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> >> I don't think it's a performance problem to have an old commit-graph\n> >> lying around. But if you turn on the commit-graph, run gc a bunch, then\n> >> turn it off in config we'll have it lying around forever, even if you do\n> >> subsequent gc's.\n> >>\n> >> So I think we should delete such things on the general principle that\n> >> the end-state of a gc's shouldn't be the accumulation of the values of\n> >> past configuration options if we can help it.\n> >>\n> >> Maybe that screws over other users who did a \"commit-graph write\"\n> >> without setting gc.writeCommitGraph, but I think the only sane thing to\n> >> do is to make \"gc\" fully 'own' such things if its turned on at all.\n> >\n> > Note that there is 'core.commitGraph' as well; as long as it's\n> > enabled, no commit-graph files should be deleted.\n> \n> Why? If we won't update it or write it if it's not there, why keep it\n> around?\n\nTo read it, if 'core.commitGraph' says that is should be read.\n\n> It means the commit-graph code and anything else (like bitmaps) needs to\n> deal with stale data for the common and default gc --auto case.\n> \n> You also can't have e.g. a global core.commitGraph=true config along\n> with a per-repo gc.writeCommitGraph=true config do what you expect.\n> \n> Now just because you wanted to write it for some you'll end up keeping\n> it around forever because you'd also want to optimistically always use\n> it if it's there.\n\nThis is exactly what I expect it to do.\n\n\n> Note that I'm talking about the *default* gc semantics, they don't have\n> to cover all advanced use-cases, just be good enough for most, and it's\n> also important that they're as simple as possible, and don't result in\n> stuff like \"my performance sucks because I turned this config option on\n> once a year ago for 2 days\".\n"},{"id":"376181","messageId":"87ftp4f4j8.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190524114114.GH951@szeder.dev","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-24T11:58:03Z","receivedAt":"2019-05-24T11:58:08Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 24 2019, SZEDER Gábor wrote:\n\n> On Fri, May 24, 2019 at 01:17:06PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Fri, May 24 2019, SZEDER Gábor wrote:\n>>\n>> > On Fri, May 24, 2019 at 11:01:39AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>> >> I don't think it's a performance problem to have an old commit-graph\n>> >> lying around. But if you turn on the commit-graph, run gc a bunch, then\n>> >> turn it off in config we'll have it lying around forever, even if you do\n>> >> subsequent gc's.\n>> >>\n>> >> So I think we should delete such things on the general principle that\n>> >> the end-state of a gc's shouldn't be the accumulation of the values of\n>> >> past configuration options if we can help it.\n>> >>\n>> >> Maybe that screws over other users who did a \"commit-graph write\"\n>> >> without setting gc.writeCommitGraph, but I think the only sane thing to\n>> >> do is to make \"gc\" fully 'own' such things if its turned on at all.\n>> >\n>> > Note that there is 'core.commitGraph' as well; as long as it's\n>> > enabled, no commit-graph files should be deleted.\n>>\n>> Why? If we won't update it or write it if it's not there, why keep it\n>> around?\n>\n> To read it, if 'core.commitGraph' says that is should be read.\n>\n>> It means the commit-graph code and anything else (like bitmaps) needs to\n>> deal with stale data for the common and default gc --auto case.\n>>\n>> You also can't have e.g. a global core.commitGraph=true config along\n>> with a per-repo gc.writeCommitGraph=true config do what you expect.\n>>\n>> Now just because you wanted to write it for some you'll end up keeping\n>> it around forever because you'd also want to optimistically always use\n>> it if it's there.\n>\n> This is exactly what I expect it to do.\n\nDo you also expect base packs with an associated bitmap to have an\nimplicit *.keep flag under gc with pack.writeBitmaps=false and\npack.useBitmaps=true?\n\n>> Note that I'm talking about the *default* gc semantics, they don't have\n>> to cover all advanced use-cases, just be good enough for most, and it's\n>> also important that they're as simple as possible, and don't result in\n>> stuff like \"my performance sucks because I turned this config option on\n>> once a year ago for 2 days\".\n"},{"id":"376187","messageId":"20190524123419.GI951@szeder.dev","threadId":"50501","inReplyTo":"87ftp4f4j8.fsf@evledraar.gmail.com","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-05-24T12:34:19Z","receivedAt":"2019-05-24T12:34:25Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Fri, May 24, 2019 at 01:58:03PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Fri, May 24 2019, SZEDER Gábor wrote:\n> \n> > On Fri, May 24, 2019 at 01:17:06PM +0200, Ævar Arnfjörð Bjarmason wrote:\n> >>\n> >> On Fri, May 24 2019, SZEDER Gábor wrote:\n> >>\n> >> > On Fri, May 24, 2019 at 11:01:39AM +0200, Ævar Arnfjörð Bjarmason wrote:\n> >> >> I don't think it's a performance problem to have an old commit-graph\n> >> >> lying around. But if you turn on the commit-graph, run gc a bunch, then\n> >> >> turn it off in config we'll have it lying around forever, even if you do\n> >> >> subsequent gc's.\n> >> >>\n> >> >> So I think we should delete such things on the general principle that\n> >> >> the end-state of a gc's shouldn't be the accumulation of the values of\n> >> >> past configuration options if we can help it.\n> >> >>\n> >> >> Maybe that screws over other users who did a \"commit-graph write\"\n> >> >> without setting gc.writeCommitGraph, but I think the only sane thing to\n> >> >> do is to make \"gc\" fully 'own' such things if its turned on at all.\n> >> >\n> >> > Note that there is 'core.commitGraph' as well; as long as it's\n> >> > enabled, no commit-graph files should be deleted.\n> >>\n> >> Why? If we won't update it or write it if it's not there, why keep it\n> >> around?\n> >\n> > To read it, if 'core.commitGraph' says that is should be read.\n> >\n> >> It means the commit-graph code and anything else (like bitmaps) needs to\n> >> deal with stale data for the common and default gc --auto case.\n> >>\n> >> You also can't have e.g. a global core.commitGraph=true config along\n> >> with a per-repo gc.writeCommitGraph=true config do what you expect.\n> >>\n> >> Now just because you wanted to write it for some you'll end up keeping\n> >> it around forever because you'd also want to optimistically always use\n> >> it if it's there.\n> >\n> > This is exactly what I expect it to do.\n> \n> Do you also expect base packs with an associated bitmap to have an\n> implicit *.keep flag under gc with pack.writeBitmaps=false and\n> pack.useBitmaps=true?\n\nI don't understand what an \"implicit *.keep flag\" is. However, since\na reachability bitmap is always associated with a pack, but the\ncommit-graph is not, I don't think this is a valid comparison.\n\n> >> Note that I'm talking about the *default* gc semantics, they don't have\n> >> to cover all advanced use-cases, just be good enough for most, and it's\n> >> also important that they're as simple as possible, and don't result in\n> >> stuff like \"my performance sucks because I turned this config option on\n> >> once a year ago for 2 days\".\n"},{"id":"376189","messageId":"87d0k8ezqj.fsf@evledraar.gmail.com","threadId":"50501","inReplyTo":"20190524123419.GI951@szeder.dev","subject":"Re: [PATCH v3] repack: enable bitmaps by default on bare repos","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-05-24T13:41:40Z","receivedAt":"2019-05-24T13:41:46Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, May 24 2019, SZEDER Gábor wrote:\n\n> On Fri, May 24, 2019 at 01:58:03PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Fri, May 24 2019, SZEDER Gábor wrote:\n>>\n>> > On Fri, May 24, 2019 at 01:17:06PM +0200, Ævar Arnfjörð Bjarmason wrote:\n>> >>\n>> >> On Fri, May 24 2019, SZEDER Gábor wrote:\n>> >>\n>> >> > On Fri, May 24, 2019 at 11:01:39AM +0200, Ævar Arnfjörð Bjarmason wrote:\n>> >> >> I don't think it's a performance problem to have an old commit-graph\n>> >> >> lying around. But if you turn on the commit-graph, run gc a bunch, then\n>> >> >> turn it off in config we'll have it lying around forever, even if you do\n>> >> >> subsequent gc's.\n>> >> >>\n>> >> >> So I think we should delete such things on the general principle that\n>> >> >> the end-state of a gc's shouldn't be the accumulation of the values of\n>> >> >> past configuration options if we can help it.\n>> >> >>\n>> >> >> Maybe that screws over other users who did a \"commit-graph write\"\n>> >> >> without setting gc.writeCommitGraph, but I think the only sane thing to\n>> >> >> do is to make \"gc\" fully 'own' such things if its turned on at all.\n>> >> >\n>> >> > Note that there is 'core.commitGraph' as well; as long as it's\n>> >> > enabled, no commit-graph files should be deleted.\n>> >>\n>> >> Why? If we won't update it or write it if it's not there, why keep it\n>> >> around?\n>> >\n>> > To read it, if 'core.commitGraph' says that is should be read.\n>> >\n>> >> It means the commit-graph code and anything else (like bitmaps) needs to\n>> >> deal with stale data for the common and default gc --auto case.\n>> >>\n>> >> You also can't have e.g. a global core.commitGraph=true config along\n>> >> with a per-repo gc.writeCommitGraph=true config do what you expect.\n>> >>\n>> >> Now just because you wanted to write it for some you'll end up keeping\n>> >> it around forever because you'd also want to optimistically always use\n>> >> it if it's there.\n>> >\n>> > This is exactly what I expect it to do.\n>>\n>> Do you also expect base packs with an associated bitmap to have an\n>> implicit *.keep flag under gc with pack.writeBitmaps=false and\n>> pack.useBitmaps=true?\n>\n> I don't understand what an \"implicit *.keep flag\" is[...]\n\nA .keep means we keep the pack, and e.g. gc.bigPackThreshold is\neffectively an implicit *.keep flag on a pack matching some critera,\nwhich in this case caused this issue of a stale *.bitmap file (since the\npack wasn't touched, neither was the bitmap).\n\n> [...]However, since a reachability bitmap is always associated with a\n> pack, but the commit-graph is not, I don't think this is a valid\n> comparison.\n\nI don't either, I'm just trying to understand where you're coming from,\nand I still don't.\n\nThat bitmaps are associated with specific packs and the commit graph\nisn't is an internal implementation detail. Users who care about that\ndistinction either don't use \"git gc\" or would be willing to tweak its\nsettings.\n\nFor the rest I think removing existing side-indexes is a good default\nfor the practical reasons mentioned upthread.\n\n>> >> Note that I'm talking about the *default* gc semantics, they don't have\n>> >> to cover all advanced use-cases, just be good enough for most, and it's\n>> >> also important that they're as simple as possible, and don't result in\n>> >> stuff like \"my performance sucks because I turned this config option on\n>> >> once a year ago for 2 days\".\n"}]}