{"thread":{"id":"51370","subject":"[PATCH v3 4/5] repack: optionally assume transitive kept packs","startedAt":"2019-06-24T12:17:15Z","lastAt":"2019-06-25T10:52:49Z","messageCount":11,"participants":["Nathaniel Filardo","Derrick Stolee","Dr N.W. Filardo"],"isPatch":true,"patchVersion":3,"patchTotal":5},"messages":[{"id":"377862","messageId":"20190624120711.27744-5-nwf20@cl.cam.ac.uk","threadId":"51370","inReplyTo":"20190624120711.27744-1-nwf20@cl.cam.ac.uk","subject":"[PATCH v3 4/5] repack: optionally assume transitive kept packs","fromName":"Nathaniel Filardo","fromEmail":"nwf20@cl.cam.ac.uk","sentAt":"2019-06-24T12:07:10Z","receivedAt":"2019-06-24T12:17:15Z","isPatch":true,"sender":{"key":"nwf20@cl.cam.ac.uk","avatar":null},"body":"If the user is careful to mark .pack files as kept only when they refer\nto (other) kept packs, then we can rely on this when walking the object\ngraph in subsequent repack operations and reduce the time and memory\nspent building the object graph.\n\nTowards that end, then, teach git repack to enumerate the COMMITs and\nTREEs in kept packs and mark them as UNINTERESTING for pack-object's\noperation.  Because this creates UNINTERESTING marks, we make repack's\n--assume-pack-keep-transitive imply --sparse for pack-object to avoid\nhauling the entire object graph into memory.\n\nIn testing with a 203GB repository with 80M objects, this amounts to\nseveral gigabytes of memory and over ten minutes saved.  This machine\nhas 32G of RAM and the repository is on a fast SSD to speed testing.\n\nAll told, this test repository takes about 33 minutes elapsed (28\nminutes in user code) and 3 GB of RAM to repack 12M objects occupying\n33GB scattered across 477 pack files not marked as kept (the remainder\nof the objects are spread across three kept pack files).  The time and\nRAM usage with --assume-pack-keep-transitive should be dominated by\nfactors proportional to the size and number of un-kept objects.\n\nWithout these optimizations, it takes about 45 minutes (34 minutes in\nuser code) and 7 GB of RAM to compute the same pack file.  The extra\ntime and total memory use are expected to be proportional to the kept\npacks' size, not the working set of the repack.  The time discrepancy\ncan be expected to be more dramatic when the repository is on spinning\nrust rather than SSD.\n\nSigned-off-by: Nathaniel Filardo <nwf20@cl.cam.ac.uk>\n---\n Documentation/git-repack.txt | 21 +++++++++++++\n builtin/repack.c             | 57 ++++++++++++++++++++++++++++++++++--\n 2 files changed, 76 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\nindex 836d81457a..014812c4bb 100644\n--- a/Documentation/git-repack.txt\n+++ b/Documentation/git-repack.txt\n@@ -169,6 +169,27 @@ depth is 4095.\n \tPass the `--sparse` option to `git-pack-objects`; see\n \tlinkgit:git-pack-objects[1].\n \n+--assume-pack-keep-transitive::\n+\tThis flag accelerates the search for objects to pack by assuming\n+\tthat commit objects found in kept packfiles make reference only\n+\tto that or other kept packfiles.  This is very useful if, for\n+\texample, this repository periodically repacks all reachable objects\n+\tand marks the resulting pack file as kept.\n+\n+\tBecause this option may prevent git from descending into kept packs,\n+\tno objects inside kept packs will be available for delta processing.\n+\tOne should therefore restrict the use of this option to situations\n+\twhere delta processing is disabled or when relatively large amounts\n+\tof data are considered and the relative gain of a wider set of\n+\tpossible delta base objects is reduced.\n+\n+\tThe simplest way to ensure transitivity of kept packs is to run `git\n+\trepack` with `-a` (or `-A`) and `-d` and mark all resulting packs as\n+\tkept, never removing the kept marker.  In practice, one may wish to\n+\twait to mark packs as kept until they are sufficiently large\n+\t(reducing the number of pack files necessary for a given set of\n+\tobjects) but not so large as to be unwieldy.\n+\n Configuration\n -------------\n \ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 4cfdd62bb8..a2cd479686 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -11,6 +11,8 @@\n #include \"midx.h\"\n #include \"packfile.h\"\n #include \"object-store.h\"\n+#include \"revision.h\"\n+#include \"list-objects.h\"\n \n static int delta_base_offset = 1;\n static int pack_kept_objects = -1;\n@@ -256,6 +258,30 @@ static void repack_promisor_objects(const struct pack_objects_args *args,\n \t\tdie(_(\"could not finish pack-objects to repack promisor objects\"));\n }\n \n+static void apkt_show_commit(struct commit *commit, void *data)\n+{\n+\tstruct tree *tree;\n+\tstruct pack_entry e;\n+\n+\tif (!find_pack_entry(the_repository, &commit->object.oid, &e))\n+\t\treturn;\n+\n+\tif (!(e.p->pack_keep || e.p->pack_keep_in_core))\n+\t\treturn;\n+\n+\ttree = get_commit_tree(commit);\n+\tif (tree)\n+\t\ttree->object.flags |= UNINTERESTING;\n+\n+\twrite_oid(&commit->object.oid, e.p, 0, data);\n+\twrite_oid(&tree->object.oid, NULL, 0, data);\n+}\n+\n+static void apkt_show_object(struct object *obj, const char *name, void *data)\n+{\n+\treturn;\n+}\n+\n #define ALL_INTO_ONE 1\n #define LOOSEN_UNREACHABLE 2\n \n@@ -287,6 +313,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \tstruct string_list keep_pack_list = STRING_LIST_INIT_NODUP;\n \tint no_update_server_info = 0;\n \tint midx_cleared = 0;\n+\tint assume_pack_keep_transitive = 0;\n \tstruct pack_objects_args po_args = {NULL};\n \tint sparse = 0;\n \n@@ -329,6 +356,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"repack objects in packs marked with .keep\")),\n \t\tOPT_BOOL(0, \"sparse\", &sparse,\n \t\t\t N_(\"use the sparse reachability algorithm\")),\n+\t\tOPT_BOOL(0, \"assume-pack-keep-transitive\", &assume_pack_keep_transitive,\n+\t\t\t\tN_(\"assume kept packs reference only kept packs\")),\n \t\tOPT_STRING_LIST(0, \"keep-pack\", &keep_pack_list, N_(\"name\"),\n \t\t\t\tN_(\"do not repack this pack\")),\n \t\tOPT_END()\n@@ -346,6 +375,11 @@ 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 (assume_pack_keep_transitive) {\n+\t\t/* imply --honor-pack-keep */\n+\t\tpack_kept_objects = 0;\n+\t}\n+\n \tif (write_bitmaps < 0)\n \t\twrite_bitmaps = (pack_everything & ALL_INTO_ONE) &&\n \t\t\t\t is_bare_repository();\n@@ -372,7 +406,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \targv_array_push(&cmd.args, \"--all\");\n \targv_array_push(&cmd.args, \"--reflog\");\n \targv_array_push(&cmd.args, \"--indexed-objects\");\n-\tif (sparse)\n+\tif (sparse || assume_pack_keep_transitive)\n \t\targv_array_push(&cmd.args, \"--sparse\");\n \tif (repository_format_partial_clone)\n \t\targv_array_push(&cmd.args, \"--exclude-promisor-objects\");\n@@ -407,12 +441,31 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\targv_array_push(&cmd.args, \"--incremental\");\n \t}\n \n-\tcmd.no_stdin = 1;\n+\tcmd.in = -1;\n+\tcmd.no_stdin = !assume_pack_keep_transitive;\n \n \tret = start_command(&cmd);\n \tif (ret)\n \t\treturn ret;\n \n+\tif (assume_pack_keep_transitive) {\n+\t\tstruct rev_info revs;\n+\t\tconst char *revargv[] = { \"skip\", \"--all\", \"--reflog\", \"--indexed-objects\", NULL };\n+\n+\t\trepo_init_revisions(the_repository, &revs, NULL);\n+\t\trevs.sparse_tree_walk = !!(sparse || assume_pack_keep_transitive);\n+\t\tsetup_revisions(sizeof(revargv)/sizeof(revargv[0]) - 1 , revargv, &revs, NULL);\n+\t\tif (prepare_revision_walk(&revs))\n+\t\t\tdie(\"revision walk setup failed\");\n+\n+\t\txwrite(cmd.in, \"--not\\n\", 6);\n+\t\ttraverse_commit_list(&revs, apkt_show_commit, apkt_show_object,\n+\t\t\t\t     &cmd);\n+\t\txwrite(cmd.in, \"--not\\n\", 6);\n+\n+\t\tclose(cmd.in);\n+\t}\n+\n \tout = xfdopen(cmd.out, \"r\");\n \twhile (strbuf_getline_lf(&line, out) != EOF) {\n \t\tif (line.len != the_hash_algo->hexsz)\n-- \n2.17.1\n\n"},{"id":"377863","messageId":"20190624120711.27744-4-nwf20@cl.cam.ac.uk","threadId":"51370","inReplyTo":"20190624120711.27744-1-nwf20@cl.cam.ac.uk","subject":"[PATCH v3 3/5] repack: add --sparse and pass to pack-objects","fromName":"Nathaniel Filardo","fromEmail":"nwf20@cl.cam.ac.uk","sentAt":"2019-06-24T12:07:09Z","receivedAt":"2019-06-24T12:17:16Z","isPatch":true,"sender":{"key":"nwf20@cl.cam.ac.uk","avatar":null},"body":"The sparse connectivity algorithm saves a whole lot of time when there\nare UNINTERESTING trees around.\n---\n Documentation/git-repack.txt   | 4 ++++\n builtin/repack.c               | 5 +++++\n t/t5322-pack-objects-sparse.sh | 6 ++++++\n 3 files changed, 15 insertions(+)\n\ndiff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\nindex aa0cc8bd44..836d81457a 100644\n--- a/Documentation/git-repack.txt\n+++ b/Documentation/git-repack.txt\n@@ -165,6 +165,10 @@ depth is 4095.\n \tPass the `--delta-islands` option to `git-pack-objects`, see\n \tlinkgit:git-pack-objects[1].\n \n+--sparse::\n+\tPass the `--sparse` option to `git-pack-objects`; see\n+\tlinkgit:git-pack-objects[1].\n+\n Configuration\n -------------\n \ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex caca113927..4cfdd62bb8 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -288,6 +288,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \tint no_update_server_info = 0;\n \tint midx_cleared = 0;\n \tstruct pack_objects_args po_args = {NULL};\n+\tint sparse = 0;\n \n \tstruct option builtin_repack_options[] = {\n \t\tOPT_BIT('a', NULL, &pack_everything,\n@@ -326,6 +327,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"maximum size of each packfile\")),\n \t\tOPT_BOOL(0, \"pack-kept-objects\", &pack_kept_objects,\n \t\t\t\tN_(\"repack objects in packs marked with .keep\")),\n+\t\tOPT_BOOL(0, \"sparse\", &sparse,\n+\t\t\t N_(\"use the sparse reachability algorithm\")),\n \t\tOPT_STRING_LIST(0, \"keep-pack\", &keep_pack_list, N_(\"name\"),\n \t\t\t\tN_(\"do not repack this pack\")),\n \t\tOPT_END()\n@@ -369,6 +372,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \targv_array_push(&cmd.args, \"--all\");\n \targv_array_push(&cmd.args, \"--reflog\");\n \targv_array_push(&cmd.args, \"--indexed-objects\");\n+\tif (sparse)\n+\t\targv_array_push(&cmd.args, \"--sparse\");\n \tif (repository_format_partial_clone)\n \t\targv_array_push(&cmd.args, \"--exclude-promisor-objects\");\n \tif (write_bitmaps)\ndiff --git a/t/t5322-pack-objects-sparse.sh b/t/t5322-pack-objects-sparse.sh\nindex 7124b5581a..66e133dcfe 100755\n--- a/t/t5322-pack-objects-sparse.sh\n+++ b/t/t5322-pack-objects-sparse.sh\n@@ -133,4 +133,10 @@ test_expect_success 'pack.useSparse overridden' '\n \ttest_cmp required_objects.txt sparse_objects.txt\n '\n \n+# repack --sparse invokes pack-objects --sparse\n+test_expect_success 'repack --sparse and fsck' '\n+\tgit repack -a --sparse &&\n+\tgit fsck\n+'\n+\n test_done\n-- \n2.17.1\n\n"},{"id":"377864","messageId":"20190624120711.27744-1-nwf20@cl.cam.ac.uk","threadId":"51370","inReplyTo":null,"subject":"[PATCH v3 0/5] Speed up repacking when lots of pack-kept objects","fromName":"Nathaniel Filardo","fromEmail":"nwf20@cl.cam.ac.uk","sentAt":"2019-06-24T12:07:06Z","receivedAt":"2019-06-24T12:17:18Z","isPatch":true,"sender":{"key":"nwf20@cl.cam.ac.uk","avatar":null},"body":"This patch series improves handling of very large repositories, as generated\nby, for example, bup (https://github.com/bup/bup).  Prolonged operation\nthereof creates quite a lot of small pack files; repacking improves\nfilesystem performance of the objects/pack directory, but is quite\nexpensive, in terms of time and memory.  We have adopted a strategy that\nmarks \"large\" (tens of GB) of pack files as \"kept\" and defers repacking\nuntil there are enough un-kept packs or enough bytes of un-kept objects.\n(The first patch in the series will make our accounting easier, replacing\nsome terrible shell scripting with grep.)\n\nWhile this strategy has generally improved our lives relative to either\nextreme (not repacking, or repacking after every bup save operation), it\nstill leaves a good bit to be desired.  Because our packs are marked as\nkept, repacking will leave the objects therein alone, but it still must\ninstantiate in memory and walk the entire object graph.  However, because\nour kept packs are transitively closed, such that an object in one\nnecessarily references only objects in other kept packs, we should like to\navoid reasoning about them more or less altogether.\n\nThis series attempts to do just that.  The fourth patch (\"repack: optionally\nassume transitive kept packs\") adds an option to builtin/repack to enumerate\ncommits (and their trees) within kept packs as UNINTERESTING to its spawned\nbuiltin/pack-objects command.  Together with inducing the use of sparse\nreachability, this speeds enumerating candidate objects for repacking and\nthereby substantially reduces the runtime of our repack operations, while\nproducing identical results.  Some test results are reported in that patch's\ncommit log.\n\nThis reroll incorporates feedback from Derrick Stolee, is rebased, and\nis updated to pass \"make test\".\n\nNathaniel Filardo (5):\n  count-objects: report statistics about kept packs\n  revision walk: optionally use sparse reachability\n  repack: add --sparse and pass to pack-objects\n  repack: optionally assume transitive kept packs\n  builtin/gc: add --assume-pack-keep-transitive\n\n Documentation/git-count-objects.txt |  8 ++++\n Documentation/git-gc.txt            |  4 ++\n Documentation/git-repack.txt        | 25 ++++++++++++\n bisect.c                            |  2 +-\n builtin/count-objects.c             | 17 +++++++-\n builtin/gc.c                        |  5 +++\n builtin/pack-objects.c              |  3 +-\n builtin/repack.c                    | 60 ++++++++++++++++++++++++++++-\n builtin/rev-list.c                  |  2 +-\n http-push.c                         |  2 +-\n list-objects.c                      |  5 +--\n list-objects.h                      |  3 +-\n revision.c                          |  3 +-\n revision.h                          |  1 +\n t/t5322-pack-objects-sparse.sh      |  6 +++\n t/t5500-fetch-pack.sh               |  8 ++--\n 16 files changed, 137 insertions(+), 17 deletions(-)\n\n-- \n2.17.1\n\n"},{"id":"377865","messageId":"20190624120711.27744-3-nwf20@cl.cam.ac.uk","threadId":"51370","inReplyTo":"20190624120711.27744-1-nwf20@cl.cam.ac.uk","subject":"[PATCH v3 2/5] revision walk: optionally use sparse reachability","fromName":"Nathaniel Filardo","fromEmail":"nwf20@cl.cam.ac.uk","sentAt":"2019-06-24T12:07:08Z","receivedAt":"2019-06-24T12:21:47Z","isPatch":true,"sender":{"key":"nwf20@cl.cam.ac.uk","avatar":null},"body":"Add another bit flag to the struct rev_info.\n\nThe only caller that uses this after this patch is builtin/pack-objects.\nWithout this, sparsity seems to do little good therein, as\nprepare_revision_walk will densely propagate UNINTERESTING flags from\ntrees to tree contents, before mark_edges_uninteresting has a chance to\nbe faster by being sparse.\n\nWhile here, drop the \"sparse\" parameter to mark_edges_uninteresting,\nintroduced in 4f6d26b167 (\"list-objects: consume sparse tree walk\",\n2019-01-16) which can now use the flag in struct rev_info.  No\nfunctional change intended.\n\nSigned-off-by: Nathaniel Filardo <nwf20@cl.cam.ac.uk>\n---\n bisect.c               | 2 +-\n builtin/pack-objects.c | 3 ++-\n builtin/rev-list.c     | 2 +-\n http-push.c            | 2 +-\n list-objects.c         | 5 ++---\n list-objects.h         | 3 +--\n revision.c             | 3 ++-\n revision.h             | 1 +\n 8 files changed, 11 insertions(+), 10 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex e87ac29a51..b6ed2b5c92 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -658,7 +658,7 @@ static void bisect_common(struct rev_info *revs)\n \tif (prepare_revision_walk(revs))\n \t\tdie(\"revision walk setup failed\");\n \tif (revs->tree_objects)\n-\t\tmark_edges_uninteresting(revs, NULL, 0);\n+\t\tmark_edges_uninteresting(revs, NULL);\n }\n \n static void exit_if_skipped_commits(struct commit_list *tried,\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex b2be8869c2..afda6064ca 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3136,9 +3136,10 @@ static void get_object_list(int ac, const char **av)\n \tif (use_delta_islands)\n \t\tload_delta_islands(the_repository);\n \n+\trevs.sparse_tree_walk = !!sparse;\n \tif (prepare_revision_walk(&revs))\n \t\tdie(_(\"revision walk setup failed\"));\n-\tmark_edges_uninteresting(&revs, show_edge, sparse);\n+\tmark_edges_uninteresting(&revs, show_edge);\n \n \tif (!fn_show_object)\n \t\tfn_show_object = show_object;\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 660172b014..74658b7344 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -548,7 +548,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (prepare_revision_walk(&revs))\n \t\tdie(\"revision walk setup failed\");\n \tif (revs.tree_objects)\n-\t\tmark_edges_uninteresting(&revs, show_edge, 0);\n+\t\tmark_edges_uninteresting(&revs, show_edge);\n \n \tif (bisect_list) {\n \t\tint reaches, all;\ndiff --git a/http-push.c b/http-push.c\nindex e36561a6db..fad6382069 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1934,7 +1934,7 @@ int cmd_main(int argc, const char **argv)\n \t\tpushing = 0;\n \t\tif (prepare_revision_walk(&revs))\n \t\t\tdie(\"revision walk setup failed\");\n-\t\tmark_edges_uninteresting(&revs, NULL, 0);\n+\t\tmark_edges_uninteresting(&revs, NULL);\n \t\tobjects_to_send = get_delta(&revs, ref_lock);\n \t\tfinish_all_active_slots();\n \ndiff --git a/list-objects.c b/list-objects.c\nindex b5651ddd5b..175673cf78 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -264,13 +264,12 @@ static void add_edge_parents(struct commit *commit,\n }\n \n void mark_edges_uninteresting(struct rev_info *revs,\n-\t\t\t      show_edge_fn show_edge,\n-\t\t\t      int sparse)\n+\t\t\t      show_edge_fn show_edge)\n {\n \tstruct commit_list *list;\n \tint i;\n \n-\tif (sparse) {\n+\tif (revs->sparse_tree_walk) {\n \t\tstruct oidset set;\n \t\toidset_init(&set, 16);\n \ndiff --git a/list-objects.h b/list-objects.h\nindex a952680e46..9388d96785 100644\n--- a/list-objects.h\n+++ b/list-objects.h\n@@ -11,8 +11,7 @@ void traverse_commit_list(struct rev_info *, show_commit_fn, show_object_fn, voi\n \n typedef void (*show_edge_fn)(struct commit *);\n void mark_edges_uninteresting(struct rev_info *revs,\n-\t\t\t      show_edge_fn show_edge,\n-\t\t\t      int sparse);\n+\t\t\t      show_edge_fn show_edge);\n \n struct oidset;\n struct list_objects_filter_options;\ndiff --git a/revision.c b/revision.c\nindex 621feb9df7..ef523c4a1e 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -458,7 +458,8 @@ static struct commit *handle_commit(struct rev_info *revs,\n \t\tif (!revs->tree_objects)\n \t\t\treturn NULL;\n \t\tif (flags & UNINTERESTING) {\n-\t\t\tmark_tree_contents_uninteresting(revs->repo, tree);\n+\t\t\tif (!revs->sparse_tree_walk)\n+\t\t\t\tmark_tree_contents_uninteresting(revs->repo, tree);\n \t\t\treturn NULL;\n \t\t}\n \t\tadd_pending_object_with_path(revs, object, name, mode, path);\ndiff --git a/revision.h b/revision.h\nindex 4134dc6029..a7154566b3 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -145,6 +145,7 @@ struct rev_info {\n \t\t\tfirst_parent_only:1,\n \t\t\tline_level_traverse:1,\n \t\t\ttree_blobs_in_commit_order:1,\n+\t\t\tsparse_tree_walk:1,\n \n \t\t\t/*\n \t\t\t * Blobs are shown without regard for their existence.\n-- \n2.17.1\n\n"},{"id":"377866","messageId":"20190624120711.27744-2-nwf20@cl.cam.ac.uk","threadId":"51370","inReplyTo":"20190624120711.27744-1-nwf20@cl.cam.ac.uk","subject":"[PATCH v3 1/5] count-objects: report statistics about kept packs","fromName":"Nathaniel Filardo","fromEmail":"nwf20@cl.cam.ac.uk","sentAt":"2019-06-24T12:07:07Z","receivedAt":"2019-06-24T12:21:48Z","isPatch":true,"sender":{"key":"nwf20@cl.cam.ac.uk","avatar":null},"body":"Specifically: number of kept packs, size of kept packs (and indexes),\nand number of objects in kept packs.\n\nAdd documentation of resulting fields.  While here, correct the omission\nfrom ae72f68541 (\"count-objects -v: show number of packs as well.\",\n2006-12-27) of the \"packs\" field.\n\nUpdate tests which were searching for the \"in-pack\" field without\nthe terminating colon and so were now also picking up the \"in-pack-keep\"\nfield.\n\nSigned-off-by: Nathaniel Filardo <nwf20@cl.cam.ac.uk>\n\nupdate count-objects\n---\n Documentation/git-count-objects.txt |  8 ++++++++\n builtin/count-objects.c             | 17 +++++++++++++++--\n t/t5500-fetch-pack.sh               |  8 ++++----\n 3 files changed, 27 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/git-count-objects.txt b/Documentation/git-count-objects.txt\nindex cb9b4d2e46..8d88f87856 100644\n--- a/Documentation/git-count-objects.txt\n+++ b/Documentation/git-count-objects.txt\n@@ -26,10 +26,18 @@ count: the number of loose objects\n +\n size: disk space consumed by loose objects, in KiB (unless -H is specified)\n +\n+packs: the number of pack files\n++\n+packs-keep: the number of pack files marked kept\n++\n in-pack: the number of in-pack objects\n +\n+in-pack-keep: the number of objects in packs marked kept\n++\n size-pack: disk space consumed by the packs, in KiB (unless -H is specified)\n +\n+size-pack-keep: disk space consumed by kept packs, in KiB (unless -H is specified)\n++\n prune-packable: the number of loose objects that are also present in\n the packs. These objects could be pruned using `git prune-packed`.\n +\ndiff --git a/builtin/count-objects.c b/builtin/count-objects.c\nindex 3fae474f6f..0309c7907f 100644\n--- a/builtin/count-objects.c\n+++ b/builtin/count-objects.c\n@@ -117,17 +117,24 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \n \tif (verbose) {\n \t\tstruct packed_git *p;\n-\t\tunsigned long num_pack = 0;\n-\t\toff_t size_pack = 0;\n+\t\tunsigned long num_pack = 0, num_pack_keep = 0;\n+\t\tunsigned long packed_keep = 0;\n+\t\toff_t size_pack = 0, size_pack_keep = 0;\n \t\tstruct strbuf loose_buf = STRBUF_INIT;\n \t\tstruct strbuf pack_buf = STRBUF_INIT;\n \t\tstruct strbuf garbage_buf = STRBUF_INIT;\n+\t\tstruct strbuf pack_keep_buf = STRBUF_INIT;\n \n \t\tfor (p = get_all_packs(the_repository); p; p = p->next) {\n \t\t\tif (!p->pack_local)\n \t\t\t\tcontinue;\n \t\t\tif (open_pack_index(p))\n \t\t\t\tcontinue;\n+\t\t\tif (p->pack_keep || p->pack_keep_in_core) {\n+\t\t\t\tpacked_keep += p->num_objects;\n+\t\t\t\tsize_pack_keep += p->pack_size + p->index_size;\n+\t\t\t\tnum_pack_keep++;\n+\t\t\t}\n \t\t\tpacked += p->num_objects;\n \t\t\tsize_pack += p->pack_size + p->index_size;\n \t\t\tnum_pack++;\n@@ -136,12 +143,15 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \t\tif (human_readable) {\n \t\t\tstrbuf_humanise_bytes(&loose_buf, loose_size);\n \t\t\tstrbuf_humanise_bytes(&pack_buf, size_pack);\n+\t\t\tstrbuf_humanise_bytes(&pack_keep_buf, size_pack_keep);\n \t\t\tstrbuf_humanise_bytes(&garbage_buf, size_garbage);\n \t\t} else {\n \t\t\tstrbuf_addf(&loose_buf, \"%lu\",\n \t\t\t\t    (unsigned long)(loose_size / 1024));\n \t\t\tstrbuf_addf(&pack_buf, \"%lu\",\n \t\t\t\t    (unsigned long)(size_pack / 1024));\n+\t\t\tstrbuf_addf(&pack_keep_buf, \"%lu\",\n+\t\t\t\t    (unsigned long)(size_pack_keep / 1024));\n \t\t\tstrbuf_addf(&garbage_buf, \"%lu\",\n \t\t\t\t    (unsigned long)(size_garbage / 1024));\n \t\t}\n@@ -149,8 +159,11 @@ int cmd_count_objects(int argc, const char **argv, const char *prefix)\n \t\tprintf(\"count: %lu\\n\", loose);\n \t\tprintf(\"size: %s\\n\", loose_buf.buf);\n \t\tprintf(\"in-pack: %lu\\n\", packed);\n+\t\tprintf(\"in-pack-keep: %lu\\n\", packed_keep);\n \t\tprintf(\"packs: %lu\\n\", num_pack);\n+\t\tprintf(\"packs-keep: %lu\\n\", num_pack_keep);\n \t\tprintf(\"size-pack: %s\\n\", pack_buf.buf);\n+\t\tprintf(\"size-pack-keep: %s\\n\", pack_keep_buf.buf);\n \t\tprintf(\"prune-packable: %lu\\n\", packed_loose);\n \t\tprintf(\"garbage: %lu\\n\", garbage);\n \t\tprintf(\"size-garbage: %s\\n\", garbage_buf.buf);\ndiff --git a/t/t5500-fetch-pack.sh b/t/t5500-fetch-pack.sh\nindex 1c71c0ec77..a1d154a4ee 100755\n--- a/t/t5500-fetch-pack.sh\n+++ b/t/t5500-fetch-pack.sh\n@@ -328,7 +328,7 @@ test_expect_success 'clone shallow with --branch' '\n test_expect_success 'clone shallow object count' '\n \techo \"in-pack: 3\" > count3.expected &&\n \tGIT_DIR=shallow3/.git git count-objects -v |\n-\t\tgrep \"^in-pack\" > count3.actual &&\n+\t\tgrep \"^in-pack:\" > count3.actual &&\n \ttest_cmp count3.expected count3.actual\n '\n \n@@ -357,7 +357,7 @@ EOF\n \n \techo \"in-pack: 4\" > count6.expected &&\n \tGIT_DIR=shallow6/.git git count-objects -v |\n-\t\tgrep \"^in-pack\" > count6.actual &&\n+\t\tgrep \"^in-pack:\" > count6.actual &&\n \ttest_cmp count6.expected count6.actual\n '\n \n@@ -372,7 +372,7 @@ EOF\n \n \techo \"in-pack: 4\" > count7.expected &&\n \tGIT_DIR=shallow7/.git git count-objects -v |\n-\t\tgrep \"^in-pack\" > count7.actual &&\n+\t\tgrep \"^in-pack:\" > count7.actual &&\n \ttest_cmp count7.expected count7.actual\n '\n \n@@ -381,7 +381,7 @@ test_expect_success 'clone shallow with packed refs' '\n \tgit clone --depth 1 --branch A \"file://$(pwd)/.\" shallow8 &&\n \techo \"in-pack: 4\" > count8.expected &&\n \tGIT_DIR=shallow8/.git git count-objects -v |\n-\t\tgrep \"^in-pack\" > count8.actual &&\n+\t\tgrep \"^in-pack:\" > count8.actual &&\n \ttest_cmp count8.expected count8.actual\n '\n \n-- \n2.17.1\n\n"},{"id":"377867","messageId":"20190624120711.27744-6-nwf20@cl.cam.ac.uk","threadId":"51370","inReplyTo":"20190624120711.27744-1-nwf20@cl.cam.ac.uk","subject":"[PATCH v3 5/5] builtin/gc: add --assume-pack-keep-transitive","fromName":"Nathaniel Filardo","fromEmail":"nwf20@cl.cam.ac.uk","sentAt":"2019-06-24T12:07:11Z","receivedAt":"2019-06-24T12:21:51Z","isPatch":true,"sender":{"key":"nwf20@cl.cam.ac.uk","avatar":null},"body":"Just pass it on down to builtin/repack.\n\nSigned-off-by: Nathaniel Filardo <nwf20@cl.cam.ac.uk>\n---\n Documentation/git-gc.txt | 4 ++++\n builtin/gc.c             | 5 +++++\n 2 files changed, 9 insertions(+)\n\ndiff --git a/Documentation/git-gc.txt b/Documentation/git-gc.txt\nindex 247f765604..6f9f15ef19 100644\n--- a/Documentation/git-gc.txt\n+++ b/Documentation/git-gc.txt\n@@ -77,6 +77,10 @@ be performed as well.\n \t`.keep` files are consolidated into a single pack. When this\n \toption is used, `gc.bigPackThreshold` is ignored.\n \n+--assume-pack-keep-transitive::\n+\tPass the `--assume-pack-keep-transitive` option to `git-repack`;\n+\tsee linkgit:git-repack[1].\n+\n AGGRESSIVE\n ----------\n \ndiff --git a/builtin/gc.c b/builtin/gc.c\nindex 8943bcc300..1b304631c5 100644\n--- a/builtin/gc.c\n+++ b/builtin/gc.c\n@@ -525,6 +525,7 @@ static void gc_before_repack(void)\n int cmd_gc(int argc, const char **argv, const char *prefix)\n {\n \tint aggressive = 0;\n+\tint assume_pack_keep_transitive = 0;\n \tint auto_gc = 0;\n \tint quiet = 0;\n \tint force = 0;\n@@ -547,6 +548,8 @@ int cmd_gc(int argc, const char **argv, const char *prefix)\n \t\t\t   PARSE_OPT_NOCOMPLETE),\n \t\tOPT_BOOL(0, \"keep-largest-pack\", &keep_base_pack,\n \t\t\t N_(\"repack all other packs except the largest pack\")),\n+\t\tOPT_BOOL(0, \"assume-pack-keep-transitive\", &assume_pack_keep_transitive,\n+\t\t\t N_(\"assume kept packs reference only kept packs\")),\n \t\tOPT_END()\n \t};\n \n@@ -585,6 +588,8 @@ int cmd_gc(int argc, const char **argv, const char *prefix)\n \t}\n \tif (quiet)\n \t\targv_array_push(&repack, \"-q\");\n+\tif (assume_pack_keep_transitive)\n+\t\targv_array_push(&repack, \"--assume-pack-keep-transitive\");\n \n \tif (auto_gc) {\n \t\t/*\n-- \n2.17.1\n\n"},{"id":"377871","messageId":"504c99bb-d264-4fc1-5dfb-00a691dfe39a@gmail.com","threadId":"51370","inReplyTo":"20190624120711.27744-2-nwf20@cl.cam.ac.uk","subject":"Re: [PATCH v3 1/5] count-objects: report statistics about kept packs","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-06-24T12:52:18Z","receivedAt":"2019-06-24T12:52:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/2019 8:07 AM, Nathaniel Filardo wrote:\n> Signed-off-by: Nathaniel Filardo <nwf20@cl.cam.ac.uk>\n> \n> update count-objects\n> ---\n\nThis post-signoff text looks like cruft from a rebase.\n\n-Stolee\n"},{"id":"377872","messageId":"6e726082-8275-b94e-c3d7-8899f00ea958@gmail.com","threadId":"51370","inReplyTo":"20190624120711.27744-3-nwf20@cl.cam.ac.uk","subject":"Re: [PATCH v3 2/5] revision walk: optionally use sparse reachability","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-06-24T12:54:25Z","receivedAt":"2019-06-24T12:54:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/2019 8:07 AM, Nathaniel Filardo wrote:\n> Add another bit flag to the struct rev_info.\n> \n> The only caller that uses this after this patch is builtin/pack-objects.\n> Without this, sparsity seems to do little good therein, as\n> prepare_revision_walk will densely propagate UNINTERESTING flags from\n> trees to tree contents, before mark_edges_uninteresting has a chance to\n> be faster by being sparse.\n> \n> While here, drop the \"sparse\" parameter to mark_edges_uninteresting,\n> introduced in 4f6d26b167 (\"list-objects: consume sparse tree walk\",\n> 2019-01-16) which can now use the flag in struct rev_info.  No\n> functional change intended.\n\nLooks like a straight-forward refactor to me. I'll keep reading\nfor the use of this new bitflag.\n\n-Stolee\n"},{"id":"377882","messageId":"25cd9bcb-9b8f-662c-75d2-a5b32d7febbc@gmail.com","threadId":"51370","inReplyTo":"20190624120711.27744-4-nwf20@cl.cam.ac.uk","subject":"Re: [PATCH v3 3/5] repack: add --sparse and pass to pack-objects","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-06-24T13:03:26Z","receivedAt":"2019-06-24T13:03:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/2019 8:07 AM, Nathaniel Filardo wrote:\n> The sparse connectivity algorithm saves a whole lot of time when there\n> are UNINTERESTING trees around.\n\nNeat! Any chance for some example performance stats?\n\n> ---\n\nLooks like you forgot your Signed-off-by here.\n\n> +# repack --sparse invokes pack-objects --sparse\n> +test_expect_success 'repack --sparse and fsck' '\n> +\tgit repack -a --sparse &&\n> +\tgit fsck\n> +'\n\nThis test may not be enough to properly test the sparse\nalgorithm, as it is only really enabled when the --revs\nargument is given to the pack-objects process AND there\nis a \"NOT\" ref (i.e. \"!{oid}\" over stdin). Using \"-a\" here\nwill not have any \"NOT\" references. OR maybe this already\nis enough when you have the .keep packs. Is there a way\nyou could set up the packs in this test to explicitly be\nin the situation you describe where the sparse option\nspeeds things up?\n\nIt's hard to check that the '--sparse' option is doing\nanything in a test, but it is important that we run the\nlogic. One way to see if this test is doing anything is\nto insert a die() somewhere. For example, this die()\nstatement will check if we ever needed to mark things\nuninteresting in a workdir path with both UNINTERESTING\nand INTERESTING trees:\n\ndiff --git a/revision.c b/revision.c\nindex eb8e51bc63..8835f8e7b1 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -227,6 +227,7 @@ void mark_trees_uninteresting_sparse(struct repository *r,\n        if (!has_uninteresting || !has_interesting)\n                return;\n\n+       die(\"we exercised the logic!\");\n        paths_and_oids_init(&map);\n\n        oidset_iter_init(trees, &iter);\n\nThe implementation of the argument looks straight-forward.\nIt appears we are passing the argument to the sub-process,\nso the bitflag isn't used yet.\n\n-Stolee\n\n"},{"id":"377886","messageId":"fbbbbd2e-3f0f-ffbb-e617-220602c9950f@gmail.com","threadId":"51370","inReplyTo":"20190624120711.27744-5-nwf20@cl.cam.ac.uk","subject":"Re: [PATCH v3 4/5] repack: optionally assume transitive kept packs","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-06-24T13:21:23Z","receivedAt":"2019-06-24T13:21:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/2019 8:07 AM, Nathaniel Filardo wrote:\n> If the user is careful to mark .pack files as kept only when they refer\n> to (other) kept packs, then we can rely on this when walking the object\n> graph in subsequent repack operations and reduce the time and memory\n> spent building the object graph.\n> \n> Towards that end, then, teach git repack to enumerate the COMMITs and\n> TREEs in kept packs and mark them as UNINTERESTING for pack-object's\n> operation.  Because this creates UNINTERESTING marks, we make repack's\n> --assume-pack-keep-transitive imply --sparse for pack-object to avoid\n> hauling the entire object graph into memory.\n> \n> In testing with a 203GB repository with 80M objects, this amounts to\n> several gigabytes of memory and over ten minutes saved.  This machine\n> has 32G of RAM and the repository is on a fast SSD to speed testing.\n\nThanks for the performance details!\n\n> All told, this test repository takes about 33 minutes elapsed (28\n> minutes in user code) and 3 GB of RAM to repack 12M objects occupying\n> 33GB scattered across 477 pack files not marked as kept (the remainder\n> of the objects are spread across three kept pack files).  The time and\n> RAM usage with --assume-pack-keep-transitive should be dominated by\n> factors proportional to the size and number of un-kept objects.\n> \n> Without these optimizations, it takes about 45 minutes (34 minutes in\n> user code) and 7 GB of RAM to compute the same pack file.  The extra\n> time and total memory use are expected to be proportional to the kept\n> packs' size, not the working set of the repack.  The time discrepancy\n> can be expected to be more dramatic when the repository is on spinning\n> rust rather than SSD.\n> \n> Signed-off-by: Nathaniel Filardo <nwf20@cl.cam.ac.uk>\n> ---\n>  Documentation/git-repack.txt | 21 +++++++++++++\n>  builtin/repack.c             | 57 ++++++++++++++++++++++++++++++++++--\n>  2 files changed, 76 insertions(+), 2 deletions(-)\n> \n> diff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\n> index 836d81457a..014812c4bb 100644\n> --- a/Documentation/git-repack.txt\n> +++ b/Documentation/git-repack.txt\n> @@ -169,6 +169,27 @@ depth is 4095.\n>  \tPass the `--sparse` option to `git-pack-objects`; see\n>  \tlinkgit:git-pack-objects[1].\n>  \n> +--assume-pack-keep-transitive::\n> +\tThis flag accelerates the search for objects to pack by assuming\n> +\tthat commit objects found in kept packfiles make reference only\n> +\tto that or other kept packfiles.  This is very useful if, for\n> +\texample, this repository periodically repacks all reachable objects\n> +\tand marks the resulting pack file as kept.\n> +\n> +\tBecause this option may prevent git from descending into kept packs,\n> +\tno objects inside kept packs will be available for delta processing.\n> +\tOne should therefore restrict the use of this option to situations\n> +\twhere delta processing is disabled or when relatively large amounts\n> +\tof data are considered and the relative gain of a wider set of\n> +\tpossible delta base objects is reduced.\n> +\n> +\tThe simplest way to ensure transitivity of kept packs is to run `git\n> +\trepack` with `-a` (or `-A`) and `-d` and mark all resulting packs as\n> +\tkept, never removing the kept marker.  In practice, one may wish to\n> +\twait to mark packs as kept until they are sufficiently large\n> +\t(reducing the number of pack files necessary for a given set of\n> +\tobjects) but not so large as to be unwieldy.\n> +\n>  Configuration\n>  -------------\n>  \n> diff --git a/builtin/repack.c b/builtin/repack.c\n> index 4cfdd62bb8..a2cd479686 100644\n> --- a/builtin/repack.c\n> +++ b/builtin/repack.c\n> @@ -11,6 +11,8 @@\n>  #include \"midx.h\"\n>  #include \"packfile.h\"\n>  #include \"object-store.h\"\n> +#include \"revision.h\"\n> +#include \"list-objects.h\"\n>  \n>  static int delta_base_offset = 1;\n>  static int pack_kept_objects = -1;\n> @@ -256,6 +258,30 @@ static void repack_promisor_objects(const struct pack_objects_args *args,\n>  \t\tdie(_(\"could not finish pack-objects to repack promisor objects\"));\n>  }\n>  \n> +static void apkt_show_commit(struct commit *commit, void *data)\n> +{\n> +\tstruct tree *tree;\n> +\tstruct pack_entry e;\n> +\n> +\tif (!find_pack_entry(the_repository, &commit->object.oid, &e))\n> +\t\treturn;\n> +\n> +\tif (!(e.p->pack_keep || e.p->pack_keep_in_core))\n> +\t\treturn;\n> +\n> +\ttree = get_commit_tree(commit);\n> +\tif (tree)\n> +\t\ttree->object.flags |= UNINTERESTING;\n> +\n> +\twrite_oid(&commit->object.oid, e.p, 0, data);\n> +\twrite_oid(&tree->object.oid, NULL, 0, data);\n> +}\n> +\n> +static void apkt_show_object(struct object *obj, const char *name, void *data)\n> +{\n> +\treturn;\n> +}\n> +\n>  #define ALL_INTO_ONE 1\n>  #define LOOSEN_UNREACHABLE 2\n>  \n> @@ -287,6 +313,7 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n>  \tstruct string_list keep_pack_list = STRING_LIST_INIT_NODUP;\n>  \tint no_update_server_info = 0;\n>  \tint midx_cleared = 0;\n> +\tint assume_pack_keep_transitive = 0;\n>  \tstruct pack_objects_args po_args = {NULL};\n>  \tint sparse = 0;\n>  \n> @@ -329,6 +356,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n>  \t\t\t\tN_(\"repack objects in packs marked with .keep\")),\n>  \t\tOPT_BOOL(0, \"sparse\", &sparse,\n>  \t\t\t N_(\"use the sparse reachability algorithm\")),\n> +\t\tOPT_BOOL(0, \"assume-pack-keep-transitive\", &assume_pack_keep_transitive,\n> +\t\t\t\tN_(\"assume kept packs reference only kept packs\")),\n>  \t\tOPT_STRING_LIST(0, \"keep-pack\", &keep_pack_list, N_(\"name\"),\n>  \t\t\t\tN_(\"do not repack this pack\")),\n>  \t\tOPT_END()\n> @@ -346,6 +375,11 @@ 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 (assume_pack_keep_transitive) {\n> +\t\t/* imply --honor-pack-keep */\n> +\t\tpack_kept_objects = 0;\n> +\t}\n> +\n\nIf you also set `sparse = 1;` here, then...\n\n> -\tif (sparse)\n> +\tif (sparse || assume_pack_keep_transitive)\n>  \t\targv_array_push(&cmd.args, \"--sparse\");\n\n...this logic can stay the same. And be simpler.\n\n>  \tif (repository_format_partial_clone)\n>  \t\targv_array_push(&cmd.args, \"--exclude-promisor-objects\");\n> @@ -407,12 +441,31 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n>  \t\targv_array_push(&cmd.args, \"--incremental\");\n>  \t}\n>  \n> -\tcmd.no_stdin = 1;\n> +\tcmd.in = -1;\n> +\tcmd.no_stdin = !assume_pack_keep_transitive;\n\nI wonder if this `cmd.in = -1;` needs to be here, or should be in\nthe `if (assume_pack_keep_transitive)` block below.\n\n>  \n>  \tret = start_command(&cmd);\n>  \tif (ret)\n>  \t\treturn ret;\n>  \n> +\tif (assume_pack_keep_transitive) {\n> +\t\tstruct rev_info revs;\n> +\t\tconst char *revargv[] = { \"skip\", \"--all\", \"--reflog\", \"--indexed-objects\", NULL };\n> +\n> +\t\trepo_init_revisions(the_repository, &revs, NULL);\n\n> +\t\trevs.sparse_tree_walk = !!(sparse || assume_pack_keep_transitive);\n\nHere is the bitflag! Excellent. Again, this can be simplified if we set `sparse = 1`\nin the first assume_pack_keep_transitive block.\n\n> +\t\tsetup_revisions(sizeof(revargv)/sizeof(revargv[0]) - 1 , revargv, &revs, NULL);\n\nSome whitespace strangeness on this line.\n\n> +\t\tif (prepare_revision_walk(&revs))\n> +\t\t\tdie(\"revision walk setup failed\");\n\nThis string should be localizable. It's not entirely your fault, since running\n'git grep -A 1 prepare_revision_walk' shows a variety of different uses, most\nof which don't use the localizable string, but enough do that you could add it\nhere.\n\n> +\n> +\t\txwrite(cmd.in, \"--not\\n\", 6);\n> +\t\ttraverse_commit_list(&revs, apkt_show_commit, apkt_show_object,\n> +\t\t\t\t     &cmd);\n> +\t\txwrite(cmd.in, \"--not\\n\", 6);\n> +\n> +\t\tclose(cmd.in);\n> +\t}\n> +\n>  \tout = xfdopen(cmd.out, \"r\");\n>  \twhile (strbuf_getline_lf(&line, out) != EOF) {\n>  \t\tif (line.len != the_hash_algo->hexsz)\n> \n\n"},{"id":"377964","messageId":"62970caebf1e341f72e46c1f2f98fa09@cam.ac.uk","threadId":"51370","inReplyTo":"fbbbbd2e-3f0f-ffbb-e617-220602c9950f@gmail.com","subject":"Re: [PATCH v3 4/5] repack: optionally assume transitive kept packs","fromName":"Dr N.W. Filardo","fromEmail":"nwf20@cam.ac.uk","sentAt":"2019-06-25T10:32:36Z","receivedAt":"2019-06-25T10:52:49Z","isPatch":true,"sender":{"key":"nwf20@cam.ac.uk","avatar":null},"body":"On 2019-06-24 14:21, Derrick Stolee wrote:\n> On 6/24/2019 8:07 AM, Nathaniel Filardo wrote:\n>> If the user is careful to mark .pack files as kept only when they\n>> refer\n>> to (other) kept packs, then we can rely on this when walking the\n>> object\n>> graph in subsequent repack operations and reduce the time and memory\n>> spent building the object graph.\n>> \n>> Towards that end, then, teach git repack to enumerate the COMMITs and\n>> TREEs in kept packs and mark them as UNINTERESTING for pack-object's\n>> operation.  Because this creates UNINTERESTING marks, we make repack's\n>> --assume-pack-keep-transitive imply --sparse for pack-object to avoid\n>> hauling the entire object graph into memory.\n>> \n>> In testing with a 203GB repository with 80M objects, this amounts to\n>> several gigabytes of memory and over ten minutes saved.  This machine\n>> has 32G of RAM and the repository is on a fast SSD to speed testing.\n> \n> Thanks for the performance details!\n\nHappy to provide.  Hopefully they justify my desire to see these patches\nland in mainline. :)\n\n>> All told, this test repository takes about 33 minutes elapsed (28\n>> minutes in user code) and 3 GB of RAM to repack 12M objects occupying\n>> 33GB scattered across 477 pack files not marked as kept (the remainder\n>> of the objects are spread across three kept pack files).  The time and\n>> RAM usage with --assume-pack-keep-transitive should be dominated by\n>> factors proportional to the size and number of un-kept objects.\n>> \n>> Without these optimizations, it takes about 45 minutes (34 minutes in\n>> user code) and 7 GB of RAM to compute the same pack file.  The extra\n>> time and total memory use are expected to be proportional to the kept\n>> packs' size, not the working set of the repack.  The time discrepancy\n>> can be expected to be more dramatic when the repository is on spinning\n>> rust rather than SSD.\n>> \n>> Signed-off-by: Nathaniel Filardo <nwf20@cl.cam.ac.uk>\n>> ---\n>>  Documentation/git-repack.txt | 21 +++++++++++++\n>>  builtin/repack.c             | 57\n>> ++++++++++++++++++++++++++++++++++--\n>>  2 files changed, 76 insertions(+), 2 deletions(-)\n>> \n>> diff --git a/Documentation/git-repack.txt\n>> b/Documentation/git-repack.txt\n>> index 836d81457a..014812c4bb 100644\n>> --- a/Documentation/git-repack.txt\n>> +++ b/Documentation/git-repack.txt\n>> @@ -169,6 +169,27 @@ depth is 4095.\n>>  \tPass the `--sparse` option to `git-pack-objects`; see\n>>  \tlinkgit:git-pack-objects[1].\n>> \n>> +--assume-pack-keep-transitive::\n>> +\tThis flag accelerates the search for objects to pack by assuming\n>> +\tthat commit objects found in kept packfiles make reference only\n>> +\tto that or other kept packfiles.  This is very useful if, for\n>> +\texample, this repository periodically repacks all reachable objects\n>> +\tand marks the resulting pack file as kept.\n>> +\n>> +\tBecause this option may prevent git from descending into kept packs,\n>> +\tno objects inside kept packs will be available for delta processing.\n>> +\tOne should therefore restrict the use of this option to situations\n>> +\twhere delta processing is disabled or when relatively large amounts\n>> +\tof data are considered and the relative gain of a wider set of\n>> +\tpossible delta base objects is reduced.\n>> +\n>> +\tThe simplest way to ensure transitivity of kept packs is to run `git\n>> +\trepack` with `-a` (or `-A`) and `-d` and mark all resulting packs as\n>> +\tkept, never removing the kept marker.  In practice, one may wish to\n>> +\twait to mark packs as kept until they are sufficiently large\n>> +\t(reducing the number of pack files necessary for a given set of\n>> +\tobjects) but not so large as to be unwieldy.\n>> +\n>>  Configuration\n>>  -------------\n>> \n>> diff --git a/builtin/repack.c b/builtin/repack.c\n>> index 4cfdd62bb8..a2cd479686 100644\n>> --- a/builtin/repack.c\n>> +++ b/builtin/repack.c\n>> @@ -11,6 +11,8 @@\n>>  #include \"midx.h\"\n>>  #include \"packfile.h\"\n>>  #include \"object-store.h\"\n>> +#include \"revision.h\"\n>> +#include \"list-objects.h\"\n>> \n>>  static int delta_base_offset = 1;\n>>  static int pack_kept_objects = -1;\n>> @@ -256,6 +258,30 @@ static void repack_promisor_objects(const struct\n>> pack_objects_args *args,\n>>  \t\tdie(_(\"could not finish pack-objects to repack promisor objects\"));\n>>  }\n>> \n>> +static void apkt_show_commit(struct commit *commit, void *data)\n>> +{\n>> +\tstruct tree *tree;\n>> +\tstruct pack_entry e;\n>> +\n>> +\tif (!find_pack_entry(the_repository, &commit->object.oid, &e))\n>> +\t\treturn;\n>> +\n>> +\tif (!(e.p->pack_keep || e.p->pack_keep_in_core))\n>> +\t\treturn;\n>> +\n>> +\ttree = get_commit_tree(commit);\n>> +\tif (tree)\n>> +\t\ttree->object.flags |= UNINTERESTING;\n>> +\n>> +\twrite_oid(&commit->object.oid, e.p, 0, data);\n>> +\twrite_oid(&tree->object.oid, NULL, 0, data);\n>> +}\n>> +\n>> +static void apkt_show_object(struct object *obj, const char *name,\n>> void *data)\n>> +{\n>> +\treturn;\n>> +}\n>> +\n>>  #define ALL_INTO_ONE 1\n>>  #define LOOSEN_UNREACHABLE 2\n>> \n>> @@ -287,6 +313,7 @@ int cmd_repack(int argc, const char **argv, const\n>> char *prefix)\n>>  \tstruct string_list keep_pack_list = STRING_LIST_INIT_NODUP;\n>>  \tint no_update_server_info = 0;\n>>  \tint midx_cleared = 0;\n>> +\tint assume_pack_keep_transitive = 0;\n>>  \tstruct pack_objects_args po_args = {NULL};\n>>  \tint sparse = 0;\n>> \n>> @@ -329,6 +356,8 @@ int cmd_repack(int argc, const char **argv, const\n>> char *prefix)\n>>  \t\t\t\tN_(\"repack objects in packs marked with .keep\")),\n>>  \t\tOPT_BOOL(0, \"sparse\", &sparse,\n>>  \t\t\t N_(\"use the sparse reachability algorithm\")),\n>> +\t\tOPT_BOOL(0, \"assume-pack-keep-transitive\",\n>> &assume_pack_keep_transitive,\n>> +\t\t\t\tN_(\"assume kept packs reference only kept packs\")),\n>>  \t\tOPT_STRING_LIST(0, \"keep-pack\", &keep_pack_list, N_(\"name\"),\n>>  \t\t\t\tN_(\"do not repack this pack\")),\n>>  \t\tOPT_END()\n>> @@ -346,6 +375,11 @@ int cmd_repack(int argc, const char **argv, const\n>> char *prefix)\n>>  \t    (unpack_unreachable || (pack_everything & LOOSEN_UNREACHABLE)))\n>>  \t\tdie(_(\"--keep-unreachable and -A are incompatible\"));\n>> \n>> +\tif (assume_pack_keep_transitive) {\n>> +\t\t/* imply --honor-pack-keep */\n>> +\t\tpack_kept_objects = 0;\n>> +\t}\n>> +\n> \n> If you also set `sparse = 1;` here, then...\n\nThat seems reasonable.\n\n>> -\tif (sparse)\n>> +\tif (sparse || assume_pack_keep_transitive)\n>>  \t\targv_array_push(&cmd.args, \"--sparse\");\n> \n> ...this logic can stay the same. And be simpler.\n\nDone.\n\n>>  \tif (repository_format_partial_clone)\n>>  \t\targv_array_push(&cmd.args, \"--exclude-promisor-objects\");\n>> @@ -407,12 +441,31 @@ int cmd_repack(int argc, const char **argv,\n>> const char *prefix)\n>>  \t\targv_array_push(&cmd.args, \"--incremental\");\n>>  \t}\n>> \n>> -\tcmd.no_stdin = 1;\n>> +\tcmd.in = -1;\n>> +\tcmd.no_stdin = !assume_pack_keep_transitive;\n> \n> I wonder if this `cmd.in = -1;` needs to be here, or should be in\n> the `if (assume_pack_keep_transitive)` block below.\n\nIt doesn't need to be, I suppose, but it seemed a little less subtle to\njust assign it either way, as it will either be ignored or do the right\nthing below.\n\n>> \n>>  \tret = start_command(&cmd);\n>>  \tif (ret)\n>>  \t\treturn ret;\n>> \n>> +\tif (assume_pack_keep_transitive) {\n>> +\t\tstruct rev_info revs;\n>> +\t\tconst char *revargv[] = { \"skip\", \"--all\", \"--reflog\",\n>> \"--indexed-objects\", NULL };\n>> +\n>> +\t\trepo_init_revisions(the_repository, &revs, NULL);\n> \n>> +\t\trevs.sparse_tree_walk = !!(sparse || assume_pack_keep_transitive);\n> \n> Here is the bitflag! Excellent. Again, this can be simplified if we\n> set `sparse = 1`\n> in the first assume_pack_keep_transitive block.\n\nIn fact, maybe it should just be set to 1, because we're only here if...\n.\nI wonder if this is some cruft left over from how I developed the patch.\nI'm OK with either \"= 1\" or \"= sparse\", as you prefer.\n\n>> +\t\tsetup_revisions(sizeof(revargv)/sizeof(revargv[0]) - 1 , revargv,\n>> &revs, NULL);\n> \n> Some whitespace strangeness on this line.\n\nSpurious space before , removed.\n\n>> +\t\tif (prepare_revision_walk(&revs))\n>> +\t\t\tdie(\"revision walk setup failed\");\n> \n> This string should be localizable. It's not entirely your fault, since\n> running\n> 'git grep -A 1 prepare_revision_walk' shows a variety of different\n> uses, most\n> of which don't use the localizable string, but enough do that you could\n> add it\n> here.\n\nWell, I'll try not to be a further bad example!\n\nThanks for the review.\n--nwf;\n\n"}]}