{"thread":{"id":"62091","subject":"[PATCH 01/30] path-walk: introduce an object walk by path","startedAt":"2024-09-10T02:29:00Z","lastAt":"2024-09-23T16:56:23Z","messageCount":38,"participants":["Derrick Stolee via GitGitGadget","Jeff Hostetler via GitGitGadget","Junio C Hamano","Christian Couder","Derrick Stolee","Kristoffer Haugsbakk"],"isPatch":true,"patchVersion":1,"patchTotal":30},"messages":[{"id":"502492","messageId":"a53bd0d37606c890d2fd2b715ce0bc92ff787b66.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 01/30] path-walk: introduce an object walk by path","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:26Z","receivedAt":"2024-09-10T02:29:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of a few planned applications, introduce the most basic form\nof a path-walk API. It currently assumes that there are no UNINTERESTING\nobjects, and does not include any complicated filters. It calls a function\npointer on groups of tree and blob objects as grouped by path. This only\nincludes objects the first time they are discovered, so an object that\nappears at multiple paths will not be included in two batches.\n\nThere are many future adaptations that could be made, but they are left for\nfuture updates when consumers are ready to take advantage of those features.\n\nRFC TODO: It would be helpful to create a test-tool that allows printing of\neach batch for strong testing.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n path-walk.c | 235 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n path-walk.h | 43 ++++++++++\n 3 files changed, 279 insertions(+)\n create mode 100644 path-walk.c\n create mode 100644 path-walk.h\n\ndiff --git a/Makefile b/Makefile\nindex deb175a0408..e83f6de9a2c 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1090,6 +1090,7 @@ LIB_OBJS += parse-options.o\n LIB_OBJS += patch-delta.o\n LIB_OBJS += patch-ids.o\n LIB_OBJS += path.o\n+LIB_OBJS += path-walk.o\n LIB_OBJS += pathspec.o\n LIB_OBJS += pkt-line.o\n LIB_OBJS += preload-index.o\ndiff --git a/path-walk.c b/path-walk.c\nnew file mode 100644\nindex 00000000000..2edfa0572e4\n--- /dev/null\n+++ b/path-walk.c\n@@ -0,0 +1,235 @@\n+/*\n+ * path-walk.c: implementation for path-based walks of the object graph.\n+ */\n+#include \"git-compat-util.h\"\n+#include \"path-walk.h\"\n+#include \"blob.h\"\n+#include \"commit.h\"\n+#include \"dir.h\"\n+#include \"hashmap.h\"\n+#include \"hex.h\"\n+#include \"object.h\"\n+#include \"oid-array.h\"\n+#include \"revision.h\"\n+#include \"string-list.h\"\n+#include \"strmap.h\"\n+#include \"trace2.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+\n+struct type_and_oid_list\n+{\n+\tenum object_type type;\n+\tstruct oid_array oids;\n+};\n+\n+#define TYPE_AND_OID_LIST_INIT { \\\n+\t.type = OBJ_NONE, \t \\\n+\t.oids = OID_ARRAY_INIT\t \\\n+}\n+\n+struct path_walk_context {\n+\t/**\n+\t * Repeats of data in 'struct path_walk_info' for\n+\t * access with fewer characters.\n+\t */\n+\tstruct repository *repo;\n+\tstruct rev_info *revs;\n+\tstruct path_walk_info *info;\n+\n+\t/**\n+\t * Map a path to a 'struct type_and_oid_list'\n+\t * containing the objects discovered at that\n+\t * path.\n+\t */\n+\tstruct strmap paths_to_lists;\n+\n+\t/**\n+\t * Store the current list of paths in a stack, to\n+\t * facilitate depth-first-search without recursion.\n+\t */\n+\tstruct string_list path_stack;\n+};\n+\n+static int add_children(struct path_walk_context *ctx,\n+\t\t\tconst char *base_path,\n+\t\t\tstruct object_id *oid)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct strbuf path = STRBUF_INIT;\n+\tsize_t base_len;\n+\tstruct tree *tree = lookup_tree(ctx->repo, oid);\n+\n+\tif (!tree) {\n+\t\terror(_(\"failed to walk children of tree %s: not found\"),\n+\t\t oid_to_hex(oid));\n+\t\treturn -1;\n+\t}\n+\n+\tstrbuf_addstr(&path, base_path);\n+\tbase_len = path.len;\n+\n+\tparse_tree(tree);\n+\tinit_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tstruct type_and_oid_list *list;\n+\t\tstruct object *o;\n+\t\t/* Not actually true, but we will ignore submodules later. */\n+\t\tenum object_type type = S_ISDIR(entry.mode) ? OBJ_TREE : OBJ_BLOB;\n+\n+\t\t/* Skip submodules. */\n+\t\tif (S_ISGITLINK(entry.mode))\n+\t\t\tcontinue;\n+\n+\t\tif (type == OBJ_TREE) {\n+\t\t\tstruct tree *child = lookup_tree(ctx->repo, &entry.oid);\n+\t\t\to = child ? &child->object : NULL;\n+\t\t} else if (type == OBJ_BLOB) {\n+\t\t\tstruct blob *child = lookup_blob(ctx->repo, &entry.oid);\n+\t\t\to = child ? &child->object : NULL;\n+\t\t} else {\n+\t\t\t/* Wrong type? */\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (!o) /* report error?*/\n+\t\t\tcontinue;\n+\n+\t\t/* Skip this object if already seen. */\n+\t\tif (o->flags & SEEN)\n+\t\t\tcontinue;\n+\t\to->flags |= SEEN;\n+\n+\t\tstrbuf_setlen(&path, base_len);\n+\t\tstrbuf_add(&path, entry.path, entry.pathlen);\n+\n+\t\t/*\n+\t\t * Trees will end with \"/\" for concatenation and distinction\n+\t\t * from blobs at the same path.\n+\t\t */\n+\t\tif (type == OBJ_TREE)\n+\t\t\tstrbuf_addch(&path, '/');\n+\n+\t\tif (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) {\n+\t\t\tCALLOC_ARRAY(list, 1);\n+\t\t\tlist->type = type;\n+\t\t\tstrmap_put(&ctx->paths_to_lists, path.buf, list);\n+\t\t\tstring_list_append(&ctx->path_stack, path.buf);\n+\t\t}\n+\t\toid_array_append(&list->oids, &entry.oid);\n+\t}\n+\n+\tfree_tree_buffer(tree);\n+\tstrbuf_release(&path);\n+\treturn 0;\n+}\n+\n+/*\n+ * For each path in paths_to_explore, walk the trees another level\n+ * and add any found blobs to the batch (but only if they don't\n+ * exist and haven't been added yet).\n+ */\n+static int walk_path(struct path_walk_context *ctx,\n+\t\t const char *path)\n+{\n+\tstruct type_and_oid_list *list;\n+\tint ret = 0;\n+\n+\tlist = strmap_get(&ctx->paths_to_lists, path);\n+\n+\t/* Evaluate function pointer on this data. */\n+\tret = ctx->info->path_fn(path, &list->oids, list->type,\n+\t\t\t\t ctx->info->path_fn_data);\n+\n+\t/* Expand data for children. */\n+\tif (list->type == OBJ_TREE) {\n+\t\tfor (size_t i = 0; i < list->oids.nr; i++) {\n+\t\t\tret |= add_children(ctx,\n+\t\t\t\t\t path,\n+\t\t\t\t\t &list->oids.oid[i]);\n+\t\t}\n+\t}\n+\n+\toid_array_clear(&list->oids);\n+\tstrmap_remove(&ctx->paths_to_lists, path, 1);\n+\treturn ret;\n+}\n+\n+static void clear_strmap(struct strmap *map)\n+{\n+\tstruct hashmap_iter iter;\n+\tstruct strmap_entry *e;\n+\n+\thashmap_for_each_entry(&map->map, &iter, e, ent) {\n+\t\tstruct type_and_oid_list *list = e->value;\n+\t\toid_array_clear(&list->oids);\n+\t}\n+\tstrmap_clear(map, 1);\n+\tstrmap_init(map);\n+}\n+\n+/**\n+ * Given the configuration of 'info', walk the commits based on 'info->revs' and\n+ * call 'info->path_fn' on each discovered path.\n+ *\n+ * Returns nonzero on an error.\n+ */\n+int walk_objects_by_path(struct path_walk_info *info)\n+{\n+\tconst char *root_path = \"\";\n+\tint ret = 0;\n+\tsize_t commits_nr = 0, paths_nr = 0;\n+\tstruct commit *c;\n+\tstruct type_and_oid_list *root_tree_list;\n+\tstruct path_walk_context ctx = {\n+\t\t.repo = info->revs->repo,\n+\t\t.revs = info->revs,\n+\t\t.info = info,\n+\t\t.path_stack = STRING_LIST_INIT_DUP,\n+\t\t.paths_to_lists = STRMAP_INIT\n+\t};\n+\n+\ttrace2_region_enter(\"path-walk\", \"commit-walk\", info->revs->repo);\n+\n+\t/* Insert a single list for the root tree into the paths. */\n+\tCALLOC_ARRAY(root_tree_list, 1);\n+\troot_tree_list->type = OBJ_TREE;\n+\tstrmap_put(&ctx.paths_to_lists, root_path, root_tree_list);\n+\n+\tif (prepare_revision_walk(info->revs))\n+\t\tdie(_(\"failed to setup revision walk\"));\n+\n+\twhile ((c = get_revision(info->revs))) {\n+\t\tstruct object_id *oid = get_commit_tree_oid(c);\n+\t\tstruct tree *t = lookup_tree(info->revs->repo, oid);\n+\t\tcommits_nr++;\n+\n+\t\tif (t)\n+\t\t\toid_array_append(&root_tree_list->oids, oid);\n+\t\telse\n+\t\t\twarning(\"could not find tree %s\", oid_to_hex(oid));\n+\t}\n+\n+\ttrace2_data_intmax(\"path-walk\", ctx.repo, \"commits\", commits_nr);\n+\ttrace2_region_leave(\"path-walk\", \"commit-walk\", info->revs->repo);\n+\n+\tstring_list_append(&ctx.path_stack, root_path);\n+\n+\ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\n+\twhile (!ret && ctx.path_stack.nr) {\n+\t\tchar *path = ctx.path_stack.items[ctx.path_stack.nr - 1].string;\n+\t\tctx.path_stack.nr--;\n+\t\tpaths_nr++;\n+\n+\t\tret = walk_path(&ctx, path);\n+\n+\t\tfree(path);\n+\t}\n+\ttrace2_data_intmax(\"path-walk\", ctx.repo, \"paths\", paths_nr);\n+\ttrace2_region_leave(\"path-walk\", \"path-walk\", info->revs->repo);\n+\n+\tclear_strmap(&ctx.paths_to_lists);\n+\tstring_list_clear(&ctx.path_stack, 0);\n+\treturn ret;\n+}\ndiff --git a/path-walk.h b/path-walk.h\nnew file mode 100644\nindex 00000000000..c9e94a98bc8\n--- /dev/null\n+++ b/path-walk.h\n@@ -0,0 +1,43 @@\n+/*\n+ * path-walk.h : Methods and structures for walking the object graph in batches\n+ * by the paths that can reach those objects.\n+ */\n+#include \"object.h\" /* Required for 'enum object_type'. */\n+\n+struct rev_info;\n+struct oid_array;\n+\n+/**\n+ * The type of a function pointer for the method that is called on a list of\n+ * objects reachable at a given path.\n+ */\n+typedef int (*path_fn)(const char *path,\n+\t\t struct oid_array *oids,\n+\t\t enum object_type type,\n+\t\t void *data);\n+\n+struct path_walk_info {\n+\t/**\n+\t * revs provides the definitions for the commit walk, including\n+\t * which commits are UNINTERESTING or not.\n+\t */\n+\tstruct rev_info *revs;\n+\n+\t/**\n+\t * The caller wishes to execute custom logic on objects reachable at a\n+\t * given path. Every reachable object will be visited exactly once, and\n+\t * the first path to see an object wins. This may not be a stable choice.\n+\t */\n+\tpath_fn path_fn;\n+\tvoid *path_fn_data;\n+};\n+\n+#define PATH_WALK_INFO_INIT { 0 }\n+\n+/**\n+ * Given the configuration of 'info', walk the commits based on 'info->revs' and\n+ * call 'info->path_fn' on each discovered path.\n+ *\n+ * Returns nonzero on an error.\n+ */\n+int walk_objects_by_path(struct path_walk_info *info);\n-- \ngitgitgadget\n\n"},{"id":"502493","messageId":"41c49bba131ed014cc4f7ab579313527dd4c9d29.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 02/30] backfill: add builtin boilerplate","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:27Z","receivedAt":"2024-09-10T02:29:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of implementing 'git backfill', populate the necessary files\nwith the boilerplate of a new builtin.\n\nRFC TODO: When preparing this for a full implementation, make sure it is\nbased on the newest standards introduced by [1].\n\n[1] https://lore.kernel.org/git/xmqqjzfq2f0f.fsf@gitster.g/T/#m606036ea2e75a6d6819d6b5c90e729643b0ff7f7\n [PATCH 1/3] builtin: add a repository parameter for builtin functions\n\nSigned-off-by: Derrick Stolee \n---\n .gitignore | 1 +\n Documentation/git-backfill.txt | 23 +++++++++++++++++++++++\n Makefile | 1 +\n builtin.h | 1 +\n builtin/backfill.c | 29 +++++++++++++++++++++++++++++\n command-list.txt | 1 +\n git.c | 1 +\n 7 files changed, 57 insertions(+)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 builtin/backfill.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 8caf3700c23..8f5cb938ecb 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -19,6 +19,7 @@\n /git-apply\n /git-archimport\n /git-archive\n+/git-backfill\n /git-bisect\n /git-blame\n /git-branch\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nnew file mode 100644\nindex 00000000000..640144187d3\n--- /dev/null\n+++ b/Documentation/git-backfill.txt\n@@ -0,0 +1,23 @@\n+git-backfill(1)\n+===============\n+\n+NAME\n+----\n+git-backfill - Download missing objects in a partial clone\n+\n+\n+SYNOPSIS\n+--------\n+[verse]\n+'git backfill' []\n+\n+DESCRIPTION\n+-----------\n+\n+SEE ALSO\n+--------\n+linkgit:git-clone[1].\n+\n+GIT\n+---\n+Part of the linkgit:git[1] suite\ndiff --git a/Makefile b/Makefile\nindex e83f6de9a2c..4305474d96e 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1198,6 +1198,7 @@ BUILTIN_OBJS += builtin/am.o\n BUILTIN_OBJS += builtin/annotate.o\n BUILTIN_OBJS += builtin/apply.o\n BUILTIN_OBJS += builtin/archive.o\n+BUILTIN_OBJS += builtin/backfill.o\n BUILTIN_OBJS += builtin/bisect.o\n BUILTIN_OBJS += builtin/blame.o\n BUILTIN_OBJS += builtin/branch.o\ndiff --git a/builtin.h b/builtin.h\nindex 14fa0171607..73dd0ccbe8c 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -127,6 +127,7 @@ int cmd_am(int argc, const char **argv, const char *prefix);\n int cmd_annotate(int argc, const char **argv, const char *prefix);\n int cmd_apply(int argc, const char **argv, const char *prefix);\n int cmd_archive(int argc, const char **argv, const char *prefix);\n+int cmd_backfill(int argc, const char **argv, const char *prefix);\n int cmd_bisect(int argc, const char **argv, const char *prefix);\n int cmd_blame(int argc, const char **argv, const char *prefix);\n int cmd_branch(int argc, const char **argv, const char *prefix);\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nnew file mode 100644\nindex 00000000000..77b05a2f838\n--- /dev/null\n+++ b/builtin/backfill.c\n@@ -0,0 +1,29 @@\n+#include \"builtin.h\"\n+#include \"config.h\"\n+#include \"parse-options.h\"\n+#include \"repository.h\"\n+#include \"object.h\"\n+\n+static const char * const builtin_backfill_usage[] = {\n+\tN_(\"git backfill []\"),\n+\tNULL\n+};\n+\n+int cmd_backfill(int argc, const char **argv, const char *prefix)\n+{\n+\tstruct option options[] = {\n+\t\tOPT_END(),\n+\t};\n+\n+\tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n+\t\tusage_with_options(builtin_backfill_usage, options);\n+\n+\targc = parse_options(argc, argv, prefix, options, builtin_backfill_usage,\n+\t\t\t 0);\n+\n+\tgit_config(git_default_config, NULL);\n+\n+\tdie(_(\"not implemented\"));\n+\n+\treturn 0;\n+}\ndiff --git a/command-list.txt b/command-list.txt\nindex e0bb87b3b5c..c537114b468 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -60,6 +60,7 @@ git-annotate ancillaryinterrogators\n git-apply plumbingmanipulators complete\n git-archimport foreignscminterface\n git-archive mainporcelain\n+git-backfill mainporcelain history\n git-bisect mainporcelain info\n git-blame ancillaryinterrogators complete\n git-branch mainporcelain history\ndiff --git a/git.c b/git.c\nindex 9a618a2740f..4f2215e9c8b 100644\n--- a/git.c\n+++ b/git.c\n@@ -509,6 +509,7 @@ static struct cmd_struct commands[] = {\n \t{ \"annotate\", cmd_annotate, RUN_SETUP },\n \t{ \"apply\", cmd_apply, RUN_SETUP_GENTLY },\n \t{ \"archive\", cmd_archive, RUN_SETUP_GENTLY },\n+\t{ \"backfill\", cmd_backfill, RUN_SETUP },\n \t{ \"bisect\", cmd_bisect, RUN_SETUP },\n \t{ \"blame\", cmd_blame, RUN_SETUP },\n \t{ \"branch\", cmd_branch, RUN_SETUP | DELAY_PAGER_CONFIG },\n-- \ngitgitgadget\n\n"},{"id":"502494","messageId":"pull.1786.git.1725935335.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":null,"subject":"[PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:25Z","receivedAt":"2024-09-10T02:29:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This RFC is ultimately about introducing a new way to walk objects, called\nthe \"path-walk API\" in the new path-walk.[ch] files. Before digging into the\ndetails of the API, let's discuss the applications which will hint at the\nAPI's design.\n\n\nAPPLICATIONS OF THE PATH-WALK API\n=================================\n\nThe applications of this API were discovered in the following order, though\nI recommend reversing the order for the priority of their actual\nimplementation in future patch series:\n\n * git backfill: a builtin to download missing blobs in a blobless partial\n clone, done in batches and grouped by the path they appear in to maximize\n delta compression in each batch. Allows focusing on the paths of the\n sparse-checkout to only get the blobs necessary for history queries in\n the current focus.\n\n * git survey: Jeff Hostetler built this feature [1] as a way to get\n functionality similar to git-sizer [2], but using the internals of Git to\n do it faster. It also displays information not available to git-sizer,\n like the on-disk size of objects. This RFC presents a simplified version\n of the builtin focused on listing the paths that contribute the most to\n the on-disk size of trees and blobs.\n\n * git pack-objects --path-walk: In order to find a way to compute deltas\n among objects of the same path, I applied the path-walk API to 'git\n pack-objects' behind an optional flag. There are overlaps with the\n '--sparse' option [3], [4] that can be used here. This provides perfect\n partitioning by path name, without any possible collisions from the\n name-hash algorithm. It also allows using the name-hash values to find\n cross-path delta chains in a second pass.\n\n * git repack --full-name-hash: If we are worried about name-hsah\n collisions, an easier thing to implement is a different name-hash\n algorithm that is less likely to have collisions. This feature was\n already sent to the mailing list as a fully-reviewable series [5]. It is\n included here because this series allows testing the --path-walk option\n against the --full-name-hash.\n\n[1] https://github.com/microsoft/git/pull/667 [2]\nhttps://github.com/github/git-sizer [3]\nhttps://github.com/git/git/compare/5d826e972970a784bd7a7bdf587512510097b8c7...99dbbfa8ddbba2b620965d026d4ec199b8837a6f\n[4]\nhttps://devblogs.microsoft.com/devops/exploring-new-frontiers-for-git-push-performance/\n[5]\nhttps://lore.kernel.org/git/pull.1785.git.1725890210.gitgitgadget@gmail.com\n\n\nTIMELINE FOR CREATING THESE APPLICATIONS IN THIS ORDER\n======================================================\n\nHere's the story about how these applications came about: I was tasked with\nunderstanding why certain internal repositories were growing larger than\nexpected. (Feel free to skip. Otherwise, thank you for indulging me.)\n\nI first prototyped 'git backfill' as a way to download some of the largest\nrepositories without being blocked on a full clone. This batched download\nmechanism allowed me to essentially have a retryable clone, since the client\ncould restart the process from scratch and skip any objects that were\nalready on disk. It was natural to batch based on the path of the blobs in\norder to theoretically save time and network bandwidth due to better delta\ncalculations.\n\nWhile investigating these repositories, I had some data hinting at the total\nsize of the objects by type. But I was most interested in learning what\nexactly was causing this growth. I did have a hint that the \"release\"\nbranches were taking up much more space than the default branch, since\ncloning with --single-branch resulted in ~55GB of data but then fetching the\nrelease branches led to an additional ~125GB of data. Using \"git diff\" it\nwas clear that these branches stored some CHANGELOG.json and CHANGELOG.md\nfiles, but the diffs were relatively small (but multiple such changes were\nbatched together into a single new commit). I needed to see why exactly\nthese paths were taking up so much space.\n\nTo this, I turned to Jeff Hostetler's new \"git survey\" command. This told me\ninformation about the total size of trees and blobs and told me the path\nname for the individual blobs that were the largest in the repository. These\npaths were typically binary files that appeared only once or twice and did\nnot account for the scale issues. I modified 'git survey' to use the same\npath-batching logic as in 'git backfill' to then consider each batch of\nobjects and their size. Thus, the \"path-walk API\" was born. (This RFC\ncontains a version that looks like it was created before 'git backfill'.)\n\nThe repository I was looking at had a clear pattern in its top 100 file\npaths by on-disk size: 99 of them were CHANGELOG.json and CHANGELOG.md\nfiles. The .md files surprised me, since they were always simple appends of\nthe previous .md file at the same path. The .json files were capped in how\nmany versions were being listed (at least in recent versions) but the data\nit stored was harder to compress. So I went looking into how 'git push' was\ncalculating these delta bases. Adding some debug information to 'git\npack-objects' demonstrated that the previous file versions were not being\nmatched as delta bases. Instead, other new blobs in the push were being used\nas delta bases.\n\nThis meant that what should have been a trivial set of deltas bloated to\n20-60 MB. (We will see later that it is possible for these to be 100-500\nKB.)\n\nHere is where I went on a little bit of a detour. (Come with me, it's\nimportant.) I knew that 'git pack-objects' used a name-hash to group objects\nby path, so I assumed that the reason these delta bases were not found was\nbecause the UNINTERESTING objects were not being added to the packing list.\nI have since discovered that this is incorrect, but I might have gotten\nstuck if I didn't think this.\n\nThis seemed like a natural reason to extend the path-walk API to allow\nwalking commits and tags as part of 'git pack-objects' behind a new\n'--path-walk' option. The idea here is to compute deltas among the objects\nthat share a common path and then later go through the (type, name-hash,\nsize) sorting system to find other delta bases across path boundaries. After\na lot of testing, failing, and testing again, the implementation in this RFC\nfinally works to achieve the goal. It's not pretty (especially with how it\nhandles tags) but it gets the job done.\n\nIn hindsight, I realized that the UNINTERESTING objects were being\nconsidered, but due to collisions in the name-hash algorithm these objects\nwere being sorted outside of the delta computation window. For this reason,\nI thought to create a new name-hash algorithm. Thus, the --full-name-hash\noption for 'git pack-objects' and 'git repack' was born. This feature was\nsplit out and sent to the mailing list independently from this RFC.\n\n\nRFC GOALS\n=========\n\nThe goals of this RFC are:\n\n 1. To demonstrate potential applications of the path-walk API to motivate\n its generality as these features are sent in full-quality patch series,\n but in a different order.\n\n 2. To communicate the discoveries found during the --path-walk and\n --full-name-hash features in 'git pack-objects' and 'git repack'. This\n includes comparing and contrasting the effectiveness of these features.\n\n 3. To demonstrate the value of the path-based batching in the 'git survey'\n feature, and to inspire others to think about what other statistics\n would be valuable in that feature. (I anticipate that once a base is\n established, multiple contributors will help expand its functionality\n long into the future.)\n\n\nRFC OUTLINE\n===========\n\nThe patches are grouped roughly by the application, in order of discovery:\n\n\nPART I: 'git backfill'\n======================\n\nThese patches introduce the 'git backfill' builtin including its\n'--batch-size' and '--sparse' options. While this is the first and simplest\napplication, it is also the lowest priority in terms of user need.\n\n * path-walk: introduce an object walk by path\n * backfill: add builtin boilerplate\n * backfill: basic functionality and tests\n * backfill: add --batch-size= option\n * backfill: add --sparse option\n * backfill: assume --sparse when sparse-checkout is enabled\n\n\nPART II: 'git survey'\n=====================\n\nThese patches reimplement a subset of the functionality of 'git survey' as\nwell as generalize some of the data structures that Jeff's implementation\nmade. The flexibility hopefully comes through to show the potential for\nfuture extensions. These patches are quite rough and will need more\nattention before they can be sent for full review.\n\n * path-walk: allow consumer to specify object types\n * path-walk: allow visiting tags\n * survey: stub in new experimental git-survey command\n * survey: add command line opts to select references\n * survey: collect the set of requested refs\n * survey: start pretty printing data in table form\n * survey: add object count summary\n * survey: summarize total sizes by object type\n * survey: show progress during object walk\n * survey: add ability to track prioritized lists\n * survey: add report of \"largest\" paths\n\n\nPART III: 'git pack-objects --path-walk'\n========================================\n\nHere is where I think the meat of the RFC really lies. There are still some\nrough edges, but the data will show that 'git pack-objects --path-walk' has\nthe potential to be an extremely effective way to pack objects. (Caveats\nwill come later in the analysis section.)\n\n * revision: create mark_trees_uninteresting_dense()\n * path-walk: add prune_all_uninteresting option\n * pack-objects: add --path-walk option\n * pack-objects: extract should_attempt_deltas()\n * pack-objects: introduce GIT_TEST_PACK_PATH_WALK\n * p5313: add size comparison test\n * repack: add --path-walk option\n * pack-objects: enable --path-walk via config\n * scalar: enable path-walk during push via config\n\nOne obvious issue with this current implementation is that it inlines much\nof the delta calculation into the \"Enumerate objects\" phase, and thus makes\nit single-threaded. This should be fixed before being considered for full\nreview, but even without threading this version can out-perform the standard\npacking strategy in terms of end-to-end packing time!\n\n\nPART IV: 'git repack --full-name-hash'\n======================================\n\nThis is a simplified version of the patch series that was split out by\nitself earlier for full review. This was split out on its own partly because\nit doesn't actually use the path-walk API. This has benefits and drawbacks,\nbut it seems like a quick win for many scenarios.\n\n * pack-objects: add --full-name-hash option\n * test-name-hash: add helper to compute name-hash functions\n * p5314: add a size test for name-hash collisions\n * pack-objects: output debug info about deltas\n\nThis last patch is an add-on of the debugging information that I used to\ndiscover issues with delta bases during 'git push'.\n\n\nDISCUSSION OF NAME HASH\n=======================\n\nOne thing to talk about before digging into --path-walk and --full-name-hash\nfeatures is the existing name-hash algorithm. This hash algorithm creates a\nuint32_t based on the final 16 characters of the path name, weighing the\nlast characters more. There are multiple benefits to this:\n\n 1. Files of common types (.c, .txt, ...) may be grouped together.\n\n 2. Files that are renamed across directories may be grouped together.\n\n(Thanks, Junio, for making this second benefit clear.)\n\nThe issue here is that some common patterns arise in repositories that use\ncommon path names across directories, and those files are creating name-hash\ncollisions and making the sort less effective. One thing that can counteract\nthese collisions is to increase the --window setting, but this significantly\nslows the delta computations.\n\nThus, the --path-walk and --full-name-hash features both attempt to combat\nthese name-hash collisions in very different ways. The --path-walk mechanism\nuses the path-walk API to consider batches of objects that all share the\nsame path. This avoids storing every possible path names in memory while\ndoing the object walk, but still gives nice boundaries for delta compression\npossibilities. After the path-walk is complete, the full packing list is\nstill sorted via name-hash and this allows for cross-path deltas. This is\ncritical!\n\nThe --full-name-hash feature does the simpler choice of replacing the\nname-hash method with one that has fewer collisions, but loses the benefits\nof \"nearby\" paths having close hash values.\n\nThis naturally leads to these two main differences in the two approaches:\n\n 1. The --full-name-hash feature is not good for 'git push' or similarly\n small pack-files. Since it limits the delta chains to objects with the\n same full path and loses the benefit of \"nearby\" paths, this feature\n should be used for larger repacks. In my testing, 'git push' simulations\n almost always have poor packing but 'git repack -adf' simulations have\n packing rivaling the --path-walk option.\n\n 2. The --path-walk option changes the object ordering significantly,\n meaning it may not ever be appropriate to combine with advanced\n repacking features such as delta islands or even reachability bitmaps.\n While my testing has shown that the --path-walk repacks are the most\n efficient of all options, this limitation makes me hesitate to recommend\n it wider than client repositories.\n\nOne natural question to consider is to think about storing both the\nname-hash and the full-name-hash and doing two delta passes, each one\nsorting the objects by a different hash function. The first issue is that we\ndon't want to store two hash values per object, as that will significantly\nincrease the memory pressure during repacking. This could be side-stepped by\nstoring the full-name-hash in the packing list and then a second mapping\nfrom full-name-hash to name-hash. However, that still leads to the two\npasses taking extra time. The --path-walk approach is faster than even a\nsingle pass. And in the right scenarios, the --full-name-hash option is very\nclose to the --path-walk results.\n\n\nANALYSIS OF PACKING STRATEGIES\n==============================\n\nSince I was focused on an internal monorepo that stored a large collection\nof Javascript packages, it should be no surprise that I eventually found\nother Javascript repositories that used similar tooling and thus had similar\nissues with unexplained scale problems. I'll use these four repositories as\nexamples repeatedly, but one is actually public: microsoft/fluentui [6].\nI'll use Repo B, C, and D for the others, in increasing size.\n\n[6] https://github.com/microsoft/fluentui\n\nIn each of these repositories, doing a full repack ('git repack -adf') right\nafter cloning presents a sizeable reduction in space. This is expected for\nservers not being optimized for exactly the reachable set I'm cloning. So,\nI'll focus on how much the default repacking parameters compare to using the\n--full-name-hash or --path-walk options:\n\n| Repo | Standard Repack | With --full-name-hash | With --path-walk |\n|----------|-----------------|-----------------------|------------------|\n| fluentui | 438 MB | 168 MB | 148 MB |\n| Repo B | 6,255 MB | 829 MB | 778 MB |\n| Repo C | 37,737 MB | 7,125 MB | 6,158 MB |\n| Repo D | 130,049 MB | 6,190 MB | 4,432 MB |\n\n\nHopefully these reductions show how much these name-hash collisions are\ncausing issues in these repositories.\n\nFor the fluentui repo, I'm also able to share highlights from the 'git\nsurvey' output immediately after cloning and after repacking with the\n--path-walk option.\n\nFirst, we can consider the total reachable objects in each scenario:\n\nTOTAL OBJECT SIZES BY TYPE\n================================================\nObject Type | Count | Disk Size | Inflated Size\n------------+--------+-----------+--------------\n Commits | 20579 | 10443669 | 15092790\n Trees | 276503 | 40212070 | 244429615\n Blobs | 294500 | 635365661 | 10791187920\n\n\nTOTAL OBJECT SIZES BY TYPE\n================================================\nObject Type | Count | Disk Size | Inflated Size\n------------+--------+-----------+--------------\n Commits | 20579 | 10450605 | 15092790\n Trees | 276503 | 31136263 | 244429615\n Blobs | 294500 | 94442401 | 10791187920\n\n\nNow, we can consider the top 10 file paths before and after repacking with\nthe --path-walk feature:\n\nTOP FILES BY DISK SIZE\n===================================================================\n Path | Count | Disk Size | Inflated Size\n--------------------------------+-------+-----------+--------------\n yarn.lock | 802 | 58060531 | 889120488\n ...-experiments/CHANGELOG.json | 505 | 28439452 | 252723999\n ...fabric-react/CHANGELOG.json | 1270 | 25556510 | 902756623\n ...t-components/CHANGELOG.json | 176 | 20366365 | 244936649\n ...act-charting/CHANGELOG.json | 590 | 20106422 | 208224460\n ...e-components/CHANGELOG.json | 559 | 15761271 | 189061764\n ...act-examples/CHANGELOG.json | 577 | 13615569 | 234949961\n ...react-charting/CHANGELOG.md | 564 | 11205840 | 104337986\n .../experiments/CHANGELOG.json | 569 | 10596377 | 123662770\n ...i-fabric-react/CHANGELOG.md | 1263 | 8154248 | 261494258\n\n\nTOP FILES BY DISK SIZE\n===================================================================\n Path | Count | Disk Size | Inflated Size\n--------------------------------+-------+-----------+--------------\n yarn.lock | 802 | 9909326 | 889120488\n ...iceBrandGuide_16Sep2016.pdf | 1 | 2106334 | 2186005\n ...out/src/images/download.jpg | 1 | 1845249 | 1846117\n ...fluent-ui-logo-inverted.png | 3 | 1370372 | 1447493\n .yarn/releases/cli.js | 1 | 1335657 | 6741614\n ...c/images/fluent-ui-logo.png | 3 | 1272902 | 1341139\n ...ages/fluent-ui-logo-dev.png | 3 | 1130989 | 1186897\n ...nents/public/SegoeUI-VF.ttf | 1 | 1074046 | 1844524\n ...ig/rush/npm-shrinkwrap.json | 138 | 1058531 | 89326567\n ...Accessibility_29Sep2016.pdf | 1 | 856621 | 927268\n\n\nAs we can see from this example, before the repack we are mainly seeing the\ndisk space be dominated by objects that appear at paths with CHANGELOG.json\nor CHANGELOG.md, which are frequently hitting collisions with the default\nname-hash. After the repack with the --path-walk feature, we see the largest\npaths are what we expect: checked in binaries, frequently-edited yarn files,\nand other hard-to- compress data.\n\nThe nice thing about this result is that we can point to files that are\ntaking up space because there is no other way around it, not that the naming\nconvention for the files is causing confusion during packing.\n\n\nWHAT TO DO NOW?\n===============\n\nThank you for reading this far. I hope that this has added context on the\npatch series for the --full-name-hash option, but also provided the right\ncontext for when I come back in a week or so with a review-ready version of\nthe --path-walk option.\n\nThese patches are rough and I want to make sure everyone knows that.\nReviewing them for style or even basic organization may lead to some wasted\ntime. I know that at least one of the patches got mangled and its diff does\nnot match its description (I'm thinking specifically about \"pack-objects:\nextract should_attempt_deltas()\" but this could apply elsewhere).\n\nBut I think that interested parties could take my branch, build it, and give\nthese features a try on their favorite repos. I'd love to hear feedback on\nthe usability and effectiveness, especially if someone finds a case where\nthe --path-walk option is less effective at packing data.\n\nThere are two things going on since I started working on this series that\ncould cause issues with applying this series on top of current 'master' or\nwith topics in 'seen':\n\n * The most obvious one is the collision with the --full-name-hash feature\n under review. The in-review series takes precedent.\n\n * The unused parameter warnings are now errors! I'm glad that got in, but I\n wasn't careful about it in these RFC patches.\n\n * John Cai is proposing to change the builtin interface to have builtin\n methods take a repository pointer. I approve of this effort, but it\n collides with the two new builtins introduced here. As discussed above,\n the 'git survey' and 'git backfill' builtins are the lowest priority\n items for getting merged, in my opinion, so they can wait until that\n change has been made.\n\nI look forward to any and all comments.\n\nThanks! -Stolee\n\nDerrick Stolee (27):\n path-walk: introduce an object walk by path\n backfill: add builtin boilerplate\n backfill: basic functionality and tests\n backfill: add --batch-size= option\n backfill: add --sparse option\n backfill: assume --sparse when sparse-checkout is enabled\n path-walk: allow consumer to specify object types\n path-walk: allow visiting tags\n survey: start pretty printing data in table form\n survey: add object count summary\n survey: summarize total sizes by object type\n survey: show progress during object walk\n survey: add ability to track prioritized lists\n survey: add report of \"largest\" paths\n revision: create mark_trees_uninteresting_dense()\n path-walk: add prune_all_uninteresting option\n pack-objects: add --path-walk option\n pack-objects: extract should_attempt_deltas()\n pack-objects: introduce GIT_TEST_PACK_PATH_WALK\n p5313: add size comparison test\n repack: add --path-walk option\n pack-objects: enable --path-walk via config\n scalar: enable path-walk during push via config\n pack-objects: add --full-name-hash option\n test-name-hash: add helper to compute name-hash functions\n p5314: add a size test for name-hash collisions\n pack-objects: output debug info about deltas\n\nJeff Hostetler (3):\n survey: stub in new experimental `git-survey` command\n survey: add command line opts to select references\n survey: collect the set of requested refs\n\n .gitignore | 2 +\n Documentation/config/pack.txt | 8 +\n Documentation/git-backfill.txt | 60 ++\n Documentation/git-survey.txt | 70 +++\n Makefile | 4 +\n builtin.h | 2 +\n builtin/backfill.c | 141 +++++\n builtin/pack-objects.c | 298 ++++++++--\n builtin/repack.c | 10 +\n builtin/survey.c | 965 +++++++++++++++++++++++++++++++++\n command-list.txt | 2 +\n git.c | 2 +\n pack-objects.h | 20 +\n path-walk.c | 401 ++++++++++++++\n path-walk.h | 73 +++\n repo-settings.c | 3 +\n repository.h | 1 +\n revision.c | 15 +\n revision.h | 1 +\n scalar.c | 1 +\n t/README | 4 +\n t/helper/test-name-hash.c | 23 +\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n t/perf/p5313-pack-objects.sh | 101 ++++\n t/perf/p5314-name-hash.sh | 41 ++\n t/t5620-backfill.sh | 181 +++++++\n t/t8100-git-survey.sh | 76 +++\n 28 files changed, 2469 insertions(+), 38 deletions(-)\n create mode 100644 Documentation/git-backfill.txt\n create mode 100644 Documentation/git-survey.txt\n create mode 100644 builtin/backfill.c\n create mode 100644 builtin/survey.c\n create mode 100644 path-walk.c\n create mode 100644 path-walk.h\n create mode 100644 t/helper/test-name-hash.c\n create mode 100755 t/perf/p5313-pack-objects.sh\n create mode 100755 t/perf/p5314-name-hash.sh\n create mode 100755 t/t5620-backfill.sh\n create mode 100755 t/t8100-git-survey.sh\n\n\nbase-commit: 17d4b10aea6bda2027047a0e3548a6f8ad667dde\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1786%2Fderrickstolee%2Fpath-walk-rfc-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1786/derrickstolee/path-walk-rfc-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1786\n-- \ngitgitgadget\n"},{"id":"502495","messageId":"be21c8370eb5143c3f6e91d354d48465d221692a.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 03/30] backfill: basic functionality and tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:28Z","receivedAt":"2024-09-10T02:29:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe default behavior of 'git backfill' is to fetch all missing blobs that\nare reachable from HEAD. Document and test this behavior.\n\nThe implementation is a very simple use of the path-walk API, initializing\nthe revision walk at HEAD to start the path-walk from all commits reachable\nfrom HEAD. Ignore the object arrays that correspond to tree entries,\nassuming that they are all present already.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 24 ++++++++\n builtin/backfill.c | 101 ++++++++++++++++++++++++++++++++-\n t/t5620-backfill.sh | 97 +++++++++++++++++++++++++++++++\n 3 files changed, 219 insertions(+), 3 deletions(-)\n create mode 100755 t/t5620-backfill.sh\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 640144187d3..0e10f066fef 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -14,6 +14,30 @@ SYNOPSIS\n DESCRIPTION\n -----------\n \n+Blobless partial clones are created using `git clone --filter=blob:none`\n+and then configure the local repository such that the Git client avoids\n+downloading blob objects unless they are required for a local operation.\n+This initially means that the clone and later fetches download reachable\n+commits and trees but no blobs. Later operations that change the `HEAD`\n+pointer, such as `git checkout` or `git merge`, may need to download\n+missing blobs in order to complete their operation.\n+\n+In the worst cases, commands that compute blob diffs, such as `git blame`,\n+become very slow as they download the missing blobs in single-blob\n+requests to satisfy the missing object as the Git command needs it. This\n+leads to multiple download requests and no ability for the Git server to\n+provide delta compression across those objects.\n+\n+The `git backfill` command provides a way for the user to request that\n+Git downloads the missing blobs (with optional filters) such that the\n+missing blobs representing historical versions of files can be downloaded\n+in batches. The `backfill` command attempts to optimize the request by\n+grouping blobs that appear at the same path, hopefully leading to good\n+delta compression in the packfile sent by the server.\n+\n+By default, `git backfill` downloads all blobs reachable from the `HEAD`\n+commit. This set can be restricted or expanded using various options.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 77b05a2f838..23d40fc02a2 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -1,16 +1,113 @@\n #include \"builtin.h\"\n+#include \"git-compat-util.h\"\n #include \"config.h\"\n #include \"parse-options.h\"\n #include \"repository.h\"\n+#include \"commit.h\"\n+#include \"hex.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n #include \"object.h\"\n+#include \"object-store-ll.h\"\n+#include \"oid-array.h\"\n+#include \"oidset.h\"\n+#include \"promisor-remote.h\"\n+#include \"strmap.h\"\n+#include \"string-list.h\"\n+#include \"revision.h\"\n+#include \"trace2.h\"\n+#include \"progress.h\"\n+#include \"packfile.h\"\n+#include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n \tN_(\"git backfill []\"),\n \tNULL\n };\n \n+struct backfill_context {\n+\tstruct repository *repo;\n+\tstruct oid_array current_batch;\n+\tsize_t batch_size;\n+};\n+\n+static void clear_backfill_context(struct backfill_context *ctx)\n+{\n+\toid_array_clear(&ctx->current_batch);\n+}\n+\n+static void download_batch(struct backfill_context *ctx)\n+{\n+\tpromisor_remote_get_direct(ctx->repo,\n+\t\t\t\t ctx->current_batch.oid,\n+\t\t\t\t ctx->current_batch.nr);\n+\toid_array_clear(&ctx->current_batch);\n+\n+\t/*\n+\t * We likely have a new packfile. Add it to the packed list to\n+\t * avoid possible duplicate downloads of the same objects.\n+\t */\n+\treprepare_packed_git(ctx->repo);\n+}\n+\n+static int fill_missing_blobs(const char *path,\n+\t\t\t struct oid_array *list,\n+\t\t\t enum object_type type,\n+\t\t\t void *data)\n+{\n+\tstruct backfill_context *ctx = data;\n+\n+\tif (type != OBJ_BLOB)\n+\t\treturn 0;\n+\n+\tfor (size_t i = 0; i < list->nr; i++) {\n+\t\toff_t size = 0;\n+\t\tstruct object_info info = OBJECT_INFO_INIT;\n+\t\tinfo.disk_sizep = &size;\n+\t\tif (oid_object_info_extended(the_repository,\n+\t\t\t\t\t &list->oid[i],\n+\t\t\t\t\t &info,\n+\t\t\t\t\t OBJECT_INFO_FOR_PREFETCH) ||\n+\t\t !size)\n+\t\t\toid_array_append(&ctx->current_batch, &list->oid[i]);\n+\t}\n+\n+\tif (ctx->current_batch.nr >= ctx->batch_size)\n+\t\tdownload_batch(ctx);\n+\n+\treturn 0;\n+}\n+\n+static int do_backfill(struct backfill_context *ctx)\n+{\n+\tstruct rev_info revs;\n+\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n+\tint ret;\n+\n+\trepo_init_revisions(ctx->repo, &revs, \"\");\n+\thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n+\n+\tinfo.revs = &revs;\n+\tinfo.path_fn = fill_missing_blobs;\n+\tinfo.path_fn_data = ctx;\n+\n+\tret = walk_objects_by_path(&info);\n+\n+\t/* Download the objects that did not fill a batch. */\n+\tif (!ret)\n+\t\tdownload_batch(ctx);\n+\n+\tclear_backfill_context(ctx);\n+\treturn ret;\n+}\n+\n int cmd_backfill(int argc, const char **argv, const char *prefix)\n {\n+\tstruct backfill_context ctx = {\n+\t\t.repo = the_repository,\n+\t\t.current_batch = OID_ARRAY_INIT,\n+\t\t.batch_size = 16000,\n+\t};\n \tstruct option options[] = {\n \t\tOPT_END(),\n \t};\n@@ -23,7 +120,5 @@ int cmd_backfill(int argc, const char **argv, const char *prefix)\n \n \tgit_config(git_default_config, NULL);\n \n-\tdie(_(\"not implemented\"));\n-\n-\treturn 0;\n+\treturn do_backfill(&ctx);\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nnew file mode 100755\nindex 00000000000..43868a4a75f\n--- /dev/null\n+++ b/t/t5620-backfill.sh\n@@ -0,0 +1,97 @@\n+#!/bin/sh\n+\n+test_description='git backfill on partial clones'\n+\n+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main\n+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME\n+\n+TEST_PASSES_SANITIZE_LEAK=0\n+export TEST_PASSES_SANITIZE_LEAK\n+\n+. ./test-lib.sh\n+\n+# We create objects in the 'src' repo.\n+test_expect_success 'setup repo for object creation' '\n+\techo \"{print \\$1}\" >print_1.awk &&\n+\techo \"{print \\$2}\" >print_2.awk &&\n+\n+\tgit init src &&\n+\n+\tmkdir -p src/a/b/c &&\n+\tmkdir -p src/d/e &&\n+\n+\tfor i in 1 2\n+\tdo\n+\t\tfor n in 1 2 3 4\n+\t\tdo\n+\t\t\techo \"Version $i of file $n\" > src/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/$n\" > src/a/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/$n\" > src/a/b/file.$n.txt &&\n+\t\t\techo \"Version $i of file a/b/c/$n\" > src/a/b/c/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/$n\" > src/d/file.$n.txt &&\n+\t\t\techo \"Version $i of file d/e/$n\" > src/d/e/file.$n.txt &&\n+\t\t\tgit -C src add . &&\n+\t\t\tgit -C src commit -m \"Iteration $n\" || return 1\n+\t\tdone\n+\tdone\n+'\n+\n+# Clone 'src' into 'srv.bare' so we have a bare repo to be our origin\n+# server for the partial clone.\n+test_expect_success 'setup bare clone for server' '\n+\tgit clone --bare \"file://$(pwd)/src\" srv.bare &&\n+\tgit -C srv.bare config --local uploadpack.allowfilter 1 &&\n+\tgit -C srv.bare config --local uploadpack.allowanysha1inwant 1\n+'\n+\n+# do basic partial clone from \"srv.bare\"\n+test_expect_success 'do partial clone 1, backfill gets all objects' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill1 &&\n+\n+\t# Backfill with no options gets everything reachable from HEAD.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-file-trace\" git \\\n+\t\t-C backfill1 backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n+. \"$TEST_DIRECTORY\"/lib-httpd.sh\n+start_httpd\n+\n+test_expect_success 'create a partial clone over HTTP' '\n+\tSERVER=\"$HTTPD_DOCUMENT_ROOT_PATH/server\" &&\n+\trm -rf \"$SERVER\" repo &&\n+\tgit clone --bare \"file://$(pwd)/src\" \"$SERVER\" &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowfilter 1 &&\n+\ttest_config -C \"$SERVER\" uploadpack.allowanysha1inwant 1 &&\n+\n+\tgit clone --no-checkout --filter=blob:none \\\n+\t\t\"$HTTPD_URL/smart/server\" backfill-http\n+'\n+\n+test_expect_success 'backfilling over HTTP succeeds' '\n+\tGIT_TRACE2_EVENT=\"$(pwd)/backfill-http-trace\" git \\\n+\t\t-C backfill-http backfill &&\n+\n+\t# We should have engaged the partial clone machinery\n+\ttest_trace2_data promisor fetch_count 48 rev-list-out &&\n+\tawk \"{print \\$1;}\" oids &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/walk-trace\" git -C backfill-http \\\n+\t\tcat-file --batch-check batch-out &&\n+\t! grep missing batch-out\n+'\n+\n+# DO NOT add non-httpd-specific tests here, because the last part of this\n+# test script is only executed when httpd is available and enabled.\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"502496","messageId":"f904b02e08dda5af1620991418755176e0b731e0.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 04/30] backfill: add --batch-size= option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:29Z","receivedAt":"2024-09-10T02:29:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nUsers may want to specify a minimum batch size for their needs. This is only\na minimum: the path-walk API provides a list of OIDs that correspond to the\nsame path, and thus it is optimal to allow delta compression across those\nobjects in a single server request.\n\nWe could consider limiting the request to have a maximum batch size in the\nfuture.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 10 +++++++++-\n builtin/backfill.c | 4 +++-\n t/t5620-backfill.sh | 18 ++++++++++++++++++\n 3 files changed, 30 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 0e10f066fef..9b0bae04e9d 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [verse]\n-'git backfill' []\n+'git backfill' [--batch-size=]\n \n DESCRIPTION\n -----------\n@@ -38,6 +38,14 @@ delta compression in the packfile sent by the server.\n By default, `git backfill` downloads all blobs reachable from the `HEAD`\n commit. This set can be restricted or expanded using various options.\n \n+OPTIONS\n+-------\n+\n+--batch-size=::\n+\tSpecify a minimum size for a batch of missing objects to request\n+\tfrom the server. This size may be exceeded by the last set of\n+\tblobs seen at a given path. Default batch size is 16,000.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 23d40fc02a2..50006f15740 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -21,7 +21,7 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill []\"),\n+\tN_(\"git backfill [--batch-size=]\"),\n \tNULL\n };\n \n@@ -109,6 +109,8 @@ int cmd_backfill(int argc, const char **argv, const char *prefix)\n \t\t.batch_size = 16000,\n \t};\n \tstruct option options[] = {\n+\t\tOPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n+\t\t\t N_(\"Minimun number of objects to request at a time\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 43868a4a75f..2d81559d8e9 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -62,6 +62,24 @@ test_expect_success 'do partial clone 1, backfill gets all objects' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'do partial clone 2, backfill batch size' '\n+\tgit clone --no-checkout --filter=blob:none\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill2 &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/batch-trace\" git \\\n+\t\t-C backfill2 backfill --batch-size=20 &&\n+\n+\t# Batches were used\n+\ttest_trace2_data promisor fetch_count 20 matches &&\n+\ttest_line_count = 2 matches &&\n+\ttest_trace2_data promisor fetch_count 8 revs2 &&\n+\ttest_line_count = 0 revs2\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \n-- \ngitgitgadget\n\n"},{"id":"502497","messageId":"aa34653de3b7bc501cb40d8bded3ddaff20f37ae.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 06/30] backfill: assume --sparse when sparse-checkout is enabled","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:31Z","receivedAt":"2024-09-10T02:29:04Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change introduced the '--[no-]sparse' option for the 'git\nbackfill' command, but did not assume it as enabled by default. However,\nthis is likely the behavior that users will most often want to happen.\nWithout this default, users with a small sparse-checkout may be confused\nwhen 'git backfill' downloads every version of every object in the full\nhistory.\n\nHowever, this is left as a separate change so this decision can be reviewed\nindependently of the value of the '--[no-]sparse' option.\n\nAdd a test of adding the '--sparse' option to a repo without sparse-checkout\nto make it clear that supplying it without a sparse-checkout is an error.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 3 ++-\n builtin/backfill.c | 4 ++++\n t/t5620-backfill.sh | 13 ++++++++++++-\n 3 files changed, 18 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex ecf2ac428ce..066ec6b161a 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -48,7 +48,8 @@ OPTIONS\n \n --[no-]sparse::\n \tOnly download objects if they appear at a path that matches the\n-\tcurrent sparse-checkout.\n+\tcurrent sparse-checkout. If the sparse-checkout feature is enabled,\n+\tthen `--sparse` is assumed and can be disabled with `--no-sparse`.\n \n SEE ALSO\n --------\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex de75471cf44..82a18e58a41 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -5,6 +5,7 @@\n #include \"repository.h\"\n #include \"commit.h\"\n #include \"dir.h\"\n+#include \"environment.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -133,5 +134,8 @@ int cmd_backfill(int argc, const char **argv, const char *prefix)\n \n \tgit_config(git_default_config, NULL);\n \n+\tif (ctx.sparse < 0)\n+\t\tctx.sparse = core_apply_sparse_checkout;\n+\n \treturn do_backfill(&ctx);\n }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex c7bb27b72c1..1fa2e90f8cf 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -80,6 +80,12 @@ test_expect_success 'do partial clone 2, backfill batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse without sparse-checkout fails' '\n+\tgit init not-sparse &&\n+\ttest_must_fail git -C not-sparse backfill --sparse 2>err &&\n+\tgrep \"problem loading sparse-checkout\" err\n+'\n+\n test_expect_success 'backfill --sparse' '\n \tgit clone --sparse --filter=blob:none\t\t\\\n \t\t--single-branch --branch=main \t\t\\\n@@ -108,7 +114,12 @@ test_expect_success 'backfill --sparse' '\n \ttest_trace2_data promisor fetch_count 8 missing &&\n-\ttest_line_count = 24 missing\n+\ttest_line_count = 24 missing &&\n+\n+\t# Disabling the --sparse option (on by default) will download everything\n+\tgit -C backfill3 backfill --no-sparse &&\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 0 missing\n '\n \n test_expect_success 'backfill --sparse without cone mode' '\n-- \ngitgitgadget\n\n"},{"id":"502498","messageId":"cd33c62f9cc7a9b05b0441b956f2b303cd302270.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 05/30] backfill: add --sparse option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:30Z","receivedAt":"2024-09-10T02:29:04Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nOne way to significantly reduce the cost of a Git clone and later fetches is\nto use a blobless partial clone and combine that with a sparse-checkout that\nreduces the paths that need to be populated in the working directory. Not\nonly does this reduce the cost of clones and fetches, the sparse-checkout\nreduces the number of objects needed to download from a promisor remote.\n\nHowever, history investigations can be expensie as computing blob diffs will\ntrigger promisor remote requests for one object at a time. This can be\navoided by downloading the blobs needed for the given sparse-checkout using\n'git backfill' and its new '--sparse' mode, at a time that the user is\nwilling to pay that extra cost.\n\nNote that this is distinctly different from the '--filter=sparse:'\noption, as this assumes that the partial clone has all reachable trees and\nwe are using client-side logic to avoid downloading blobs outside of the\nsparse-checkout cone. This avoids the server-side cost of walking trees\nwhile also achieving a similar goal. It also downloads in batches based on\nsimilar path names, presenting a resumable download if things are\ninterrupted.\n\nThis augments the path-walk API to have a possibly-NULL 'pl' member that may\npoint to a 'struct pattern_list'. This could be more general than the\nsparse-checkout definition at HEAD, but 'git backfill --sparse' is currently\nthe only consumer.\n\nBe sure to test this in both cone mode and not cone mode. Cone mode has the\nbenefit that the path-walk can skip certain paths once they would expand\nbeyond the sparse-checkout.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-backfill.txt | 6 +++-\n builtin/backfill.c | 13 +++++++-\n path-walk.c | 18 +++++++++++\n path-walk.h | 11 +++++++\n t/t5620-backfill.sh | 55 ++++++++++++++++++++++++++++++++++\n 5 files changed, 101 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-backfill.txt b/Documentation/git-backfill.txt\nindex 9b0bae04e9d..ecf2ac428ce 100644\n--- a/Documentation/git-backfill.txt\n+++ b/Documentation/git-backfill.txt\n@@ -9,7 +9,7 @@ git-backfill - Download missing objects in a partial clone\n SYNOPSIS\n --------\n [verse]\n-'git backfill' [--batch-size=]\n+'git backfill' [--batch-size=] [--[no-]sparse]\n \n DESCRIPTION\n -----------\n@@ -46,6 +46,10 @@ OPTIONS\n \tfrom the server. This size may be exceeded by the last set of\n \tblobs seen at a given path. Default batch size is 16,000.\n \n+--[no-]sparse::\n+\tOnly download objects if they appear at a path that matches the\n+\tcurrent sparse-checkout.\n+\n SEE ALSO\n --------\n linkgit:git-clone[1].\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 50006f15740..de75471cf44 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -4,6 +4,7 @@\n #include \"parse-options.h\"\n #include \"repository.h\"\n #include \"commit.h\"\n+#include \"dir.h\"\n #include \"hex.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -21,7 +22,7 @@\n #include \"path-walk.h\"\n \n static const char * const builtin_backfill_usage[] = {\n-\tN_(\"git backfill [--batch-size=]\"),\n+\tN_(\"git backfill [--batch-size=] [--[no-]sparse]\"),\n \tNULL\n };\n \n@@ -29,6 +30,7 @@ struct backfill_context {\n \tstruct repository *repo;\n \tstruct oid_array current_batch;\n \tsize_t batch_size;\n+\tint sparse;\n };\n \n static void clear_backfill_context(struct backfill_context *ctx)\n@@ -84,6 +86,12 @@ static int do_backfill(struct backfill_context *ctx)\n \tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n \tint ret;\n \n+\tif (ctx->sparse) {\n+\t\tCALLOC_ARRAY(info.pl, 1);\n+\t\tif (get_sparse_checkout_patterns(info.pl))\n+\t\t\treturn error(_(\"problem loading sparse-checkout\"));\n+\t}\n+\n \trepo_init_revisions(ctx->repo, &revs, \"\");\n \thandle_revision_arg(\"HEAD\", &revs, 0, 0);\n \n@@ -107,10 +115,13 @@ int cmd_backfill(int argc, const char **argv, const char *prefix)\n \t\t.repo = the_repository,\n \t\t.current_batch = OID_ARRAY_INIT,\n \t\t.batch_size = 16000,\n+\t\t.sparse = 0,\n \t};\n \tstruct option options[] = {\n \t\tOPT_INTEGER(0, \"batch-size\", &ctx.batch_size,\n \t\t\t N_(\"Minimun number of objects to request at a time\")),\n+\t\tOPT_BOOL(0, \"sparse\", &ctx.sparse,\n+\t\t\t N_(\"Restrict the missing objects to the current sparse-checkout\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/path-walk.c b/path-walk.c\nindex 2edfa0572e4..dc2390dd9ea 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -10,6 +10,7 @@\n #include \"hex.h\"\n #include \"object.h\"\n #include \"oid-array.h\"\n+#include \"repository.h\"\n #include \"revision.h\"\n #include \"string-list.h\"\n #include \"strmap.h\"\n@@ -111,6 +112,23 @@ static int add_children(struct path_walk_context *ctx,\n \t\tif (type == OBJ_TREE)\n \t\t\tstrbuf_addch(&path, '/');\n \n+\t\tif (ctx->info->pl) {\n+\t\t\tint dtype;\n+\t\t\tenum pattern_match_result match;\n+\t\t\tmatch = path_matches_pattern_list(path.buf, path.len,\n+\t\t\t\t\t\t\t path.buf + base_len, &dtype,\n+\t\t\t\t\t\t\t ctx->info->pl,\n+\t\t\t\t\t\t\t ctx->repo->index);\n+\n+\t\t\tif (ctx->info->pl->use_cone_patterns &&\n+\t\t\t match == NOT_MATCHED)\n+\t\t\t\tcontinue;\n+\t\t\telse if (!ctx->info->pl->use_cone_patterns &&\n+\t\t\t\t type == OBJ_BLOB &&\n+\t\t\t\t match != MATCHED)\n+\t\t\t\tcontinue;\n+\t\t}\n+\n \t\tif (!(list = strmap_get(&ctx->paths_to_lists, path.buf))) {\n \t\t\tCALLOC_ARRAY(list, 1);\n \t\t\tlist->type = type;\ndiff --git a/path-walk.h b/path-walk.h\nindex c9e94a98bc8..bc1ebba5081 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -6,6 +6,7 @@\n \n struct rev_info;\n struct oid_array;\n+struct pattern_list;\n \n /**\n * The type of a function pointer for the method that is called on a list of\n@@ -30,6 +31,16 @@ struct path_walk_info {\n \t */\n \tpath_fn path_fn;\n \tvoid *path_fn_data;\n+\n+\t/**\n+\t * Specify a sparse-checkout definition to match our paths to. Do not\n+\t * walk outside of this sparse definition. If the patterns are in\n+\t * cone mode, then the search may prune directories that are outside\n+\t * of the cone. If not in cone mode, then all tree paths will be\n+\t * explored but the path_fn will only be called when the path matches\n+\t * the sparse-checkout patterns.\n+\t */\n+\tstruct pattern_list *pl;\n };\n \n #define PATH_WALK_INFO_INIT { 0 }\ndiff --git a/t/t5620-backfill.sh b/t/t5620-backfill.sh\nindex 2d81559d8e9..c7bb27b72c1 100755\n--- a/t/t5620-backfill.sh\n+++ b/t/t5620-backfill.sh\n@@ -80,6 +80,61 @@ test_expect_success 'do partial clone 2, backfill batch size' '\n \ttest_line_count = 0 revs2\n '\n \n+test_expect_success 'backfill --sparse' '\n+\tgit clone --sparse --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill3 &&\n+\n+\t# Initial checkout includes four files at root.\n+\tgit -C backfill3 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 44 missing &&\n+\n+\t# Initial sparse-checkout is just the files at root, so we get the\n+\t# older versions of the four files at tip.\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace1\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 4 missing &&\n+\ttest_line_count = 40 missing &&\n+\n+\t# Expand the sparse-checkout to include 'd' recursively. This\n+\t# engages the algorithm to skip the trees for 'a'. Note that\n+\t# the \"sparse-checkout set\" command downloads the objects at tip\n+\t# to satisfy the current checkout.\n+\tgit -C backfill3 sparse-checkout set d &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/sparse-trace2\" git \\\n+\t\t-C backfill3 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 8 missing &&\n+\ttest_line_count = 24 missing\n+'\n+\n+test_expect_success 'backfill --sparse without cone mode' '\n+\tgit clone --no-checkout --filter=blob:none\t\t\\\n+\t\t--single-branch --branch=main \t\t\\\n+\t\t\"file://$(pwd)/srv.bare\" backfill4 &&\n+\n+\t# No blobs yet\n+\tgit -C backfill4 rev-list --quiet --objects --missing=print HEAD >missing &&\n+\ttest_line_count = 48 missing &&\n+\n+\t# Define sparse-checkout by filename regardless of parent directory.\n+\t# This downloads 6 blobs to satisfy the checkout.\n+\tgit -C backfill4 sparse-checkout set --no-cone \"**/file.1.txt\" &&\n+\tgit -C backfill4 checkout main &&\n+\n+\tGIT_TRACE2_EVENT=\"$(pwd)/no-cone-trace1\" git \\\n+\t\t-C backfill4 backfill --sparse &&\n+\ttest_trace2_data promisor fetch_count 6 missing &&\n+\ttest_line_count = 36 missing\n+'\n+\n . \"$TEST_DIRECTORY\"/lib-httpd.sh\n start_httpd\n \n-- \ngitgitgadget\n\n"},{"id":"502499","messageId":"2829fe3875438f3a9907f36d825d6c24952abded.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 07/30] path-walk: allow consumer to specify object types","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:32Z","receivedAt":"2024-09-10T02:29:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis adds the ability to ask for the commits as a single list. This will\nalso reduce the calls in 'git backfill' to be a BUG() statement if called\nwith anything other than blobs.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/backfill.c | 2 +-\n path-walk.c | 40 ++++++++++++++++++++++++++++++++++------\n path-walk.h | 12 +++++++++++-\n 3 files changed, 46 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin/backfill.c b/builtin/backfill.c\nindex 82a18e58a41..2a1b043f188 100644\n--- a/builtin/backfill.c\n+++ b/builtin/backfill.c\n@@ -61,7 +61,7 @@ static int fill_missing_blobs(const char *path,\n \tstruct backfill_context *ctx = data;\n \n \tif (type != OBJ_BLOB)\n-\t\treturn 0;\n+\t\tBUG(\"fill_missing_blobs only takes blob objects\");\n \n \tfor (size_t i = 0; i < list->nr; i++) {\n \t\toff_t size = 0;\ndiff --git a/path-walk.c b/path-walk.c\nindex dc2390dd9ea..d70e6840fb5 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -83,6 +83,10 @@ static int add_children(struct path_walk_context *ctx,\n \t\tif (S_ISGITLINK(entry.mode))\n \t\t\tcontinue;\n \n+\t\t/* If the caller doesn't want blobs, then don't bother. */\n+\t\tif (!ctx->info->blobs && type == OBJ_BLOB)\n+\t\t\tcontinue;\n+\n \t\tif (type == OBJ_TREE) {\n \t\t\tstruct tree *child = lookup_tree(ctx->repo, &entry.oid);\n \t\t\to = child ? &child->object : NULL;\n@@ -156,9 +160,11 @@ static int walk_path(struct path_walk_context *ctx,\n \n \tlist = strmap_get(&ctx->paths_to_lists, path);\n \n-\t/* Evaluate function pointer on this data. */\n-\tret = ctx->info->path_fn(path, &list->oids, list->type,\n-\t\t\t\t ctx->info->path_fn_data);\n+\t/* Evaluate function pointer on this data, if requested. */\n+\tif ((list->type == OBJ_TREE && ctx->info->trees) ||\n+\t (list->type == OBJ_BLOB && ctx->info->blobs))\n+\t\tret = ctx->info->path_fn(path, &list->oids, list->type,\n+\t\t\t\t\tctx->info->path_fn_data);\n \n \t/* Expand data for children. */\n \tif (list->type == OBJ_TREE) {\n@@ -200,6 +206,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \tsize_t commits_nr = 0, paths_nr = 0;\n \tstruct commit *c;\n \tstruct type_and_oid_list *root_tree_list;\n+\tstruct type_and_oid_list *commit_list;\n \tstruct path_walk_context ctx = {\n \t\t.repo = info->revs->repo,\n \t\t.revs = info->revs,\n@@ -210,28 +217,49 @@ int walk_objects_by_path(struct path_walk_info *info)\n \n \ttrace2_region_enter(\"path-walk\", \"commit-walk\", info->revs->repo);\n \n+\tCALLOC_ARRAY(commit_list, 1);\n+\tcommit_list->type = OBJ_COMMIT;\n+\n \t/* Insert a single list for the root tree into the paths. */\n \tCALLOC_ARRAY(root_tree_list, 1);\n \troot_tree_list->type = OBJ_TREE;\n \tstrmap_put(&ctx.paths_to_lists, root_path, root_tree_list);\n-\n \tif (prepare_revision_walk(info->revs))\n \t\tdie(_(\"failed to setup revision walk\"));\n \n \twhile ((c = get_revision(info->revs))) {\n-\t\tstruct object_id *oid = get_commit_tree_oid(c);\n-\t\tstruct tree *t = lookup_tree(info->revs->repo, oid);\n+\t\tstruct object_id *oid;\n+\t\tstruct tree *t;\n \t\tcommits_nr++;\n \n+\t\tif (info->commits)\n+\t\t\toid_array_append(&commit_list->oids,\n+\t\t\t\t\t &c->object.oid);\n+\n+\t\t/* If we only care about commits, then skip trees. */\n+\t\tif (!info->trees && !info->blobs)\n+\t\t\tcontinue;\n+\n+\t\toid = get_commit_tree_oid(c);\n+\t\tt = lookup_tree(info->revs->repo, oid);\n+\n \t\tif (t)\n \t\t\toid_array_append(&root_tree_list->oids, oid);\n \t\telse\n \t\t\twarning(\"could not find tree %s\", oid_to_hex(oid));\n+\n \t}\n \n \ttrace2_data_intmax(\"path-walk\", ctx.repo, \"commits\", commits_nr);\n \ttrace2_region_leave(\"path-walk\", \"commit-walk\", info->revs->repo);\n \n+\t/* Track all commits. */\n+\tif (info->commits)\n+\t\tret = info->path_fn(\"\", &commit_list->oids, OBJ_COMMIT,\n+\t\t\t\t info->path_fn_data);\n+\toid_array_clear(&commit_list->oids);\n+\tfree(commit_list);\n+\n \tstring_list_append(&ctx.path_stack, root_path);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\ndiff --git a/path-walk.h b/path-walk.h\nindex bc1ebba5081..49b982dade6 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -32,6 +32,14 @@ struct path_walk_info {\n \tpath_fn path_fn;\n \tvoid *path_fn_data;\n \n+\t/**\n+\t * Initialize which object types the path_fn should be called on. This\n+\t * could also limit the walk to skip blobs if not set.\n+\t */\n+\tint commits;\n+\tint trees;\n+\tint blobs;\n+\n \t/**\n \t * Specify a sparse-checkout definition to match our paths to. Do not\n \t * walk outside of this sparse definition. If the patterns are in\n@@ -43,7 +51,9 @@ struct path_walk_info {\n \tstruct pattern_list *pl;\n };\n \n-#define PATH_WALK_INFO_INIT { 0 }\n+#define PATH_WALK_INFO_INIT { \\\n+\t.blobs = 1,\t\t\\\n+}\n \n /**\n * Given the configuration of 'info', walk the commits based on 'info->revs' and\n-- \ngitgitgadget\n\n"},{"id":"502500","messageId":"d67679dc1a3cf055cf9357f2a6bc9ff990cfef43.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 08/30] path-walk: allow visiting tags","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:33Z","receivedAt":"2024-09-10T02:29:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn anticipation of using the path-walk API to analyze tags or include\nthem in a pack-file, add the ability to walk the tags that were included\nin the revision walk.\n\nSigned-off-by: Derrick Stolee \n---\n path-walk.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n path-walk.h | 1 +\n 2 files changed, 59 insertions(+)\n\ndiff --git a/path-walk.c b/path-walk.c\nindex d70e6840fb5..65f9856afa2 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -14,6 +14,7 @@\n #include \"revision.h\"\n #include \"string-list.h\"\n #include \"strmap.h\"\n+#include \"tag.h\"\n #include \"trace2.h\"\n #include \"tree.h\"\n #include \"tree-walk.h\"\n@@ -215,6 +216,9 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t\t.paths_to_lists = STRMAP_INIT\n \t};\n \n+\tstruct oid_array tagged_tree_list = OID_ARRAY_INIT;\n+\tstruct oid_array tagged_blob_list = OID_ARRAY_INIT;\n+\n \ttrace2_region_enter(\"path-walk\", \"commit-walk\", info->revs->repo);\n \n \tCALLOC_ARRAY(commit_list, 1);\n@@ -260,6 +264,60 @@ int walk_objects_by_path(struct path_walk_info *info)\n \toid_array_clear(&commit_list->oids);\n \tfree(commit_list);\n \n+\tif (info->tags) {\n+\t\tstruct oid_array tags = OID_ARRAY_INIT;\n+\n+\t\ttrace2_region_enter(\"path-walk\", \"tag-walk\", info->revs->repo);\n+\n+\t\t/*\n+\t\t * Walk any pending objects at this point, but they should only\n+\t\t * be tags.\n+\t\t */\n+\t\tfor (size_t i = 0; i < info->revs->pending.nr; i++) {\n+\t\t\tstruct object_array_entry *pending = info->revs->pending.objects + i;\n+\t\t\tstruct object *obj = pending->item;\n+\n+\t\t\twhile (obj->type == OBJ_TAG) {\n+\t\t\t\tstruct tag *tag = lookup_tag(info->revs->repo,\n+\t\t\t\t\t\t\t &obj->oid);\n+\t\t\t\toid_array_append(&tags, &obj->oid);\n+\t\t\t\tobj = tag->tagged;\n+\t\t\t}\n+\n+\t\t\tswitch (obj->type) {\n+\t\t\tcase OBJ_TREE:\n+\t\t\t\toid_array_append(&tagged_tree_list, &obj->oid);\n+\t\t\t\tbreak;\n+\n+\t\t\tcase OBJ_BLOB:\n+\t\t\t\toid_array_append(&tagged_blob_list, &obj->oid);\n+\t\t\t\tbreak;\n+\n+\t\t\tcase OBJ_COMMIT:\n+\t\t\t\t/* skip */\n+\t\t\t\tbreak;\n+\n+\t\t\tdefault:\n+\t\t\t\tBUG(\"should not see any other type here\");\n+\t\t\t}\n+\t\t}\n+\n+\t\tinfo->path_fn(\"initial\", &tags, OBJ_TAG, info->path_fn_data);\n+\n+\t\tif (tagged_tree_list.nr)\n+\t\t\tinfo->path_fn(\"tagged-trees\", &tagged_tree_list, OBJ_TREE,\n+\t\t\t\t info->path_fn_data);\n+\t\tif (tagged_blob_list.nr)\n+\t\t\tinfo->path_fn(\"tagged-blobs\", &tagged_blob_list, OBJ_BLOB,\n+\t\t\t\t info->path_fn_data);\n+\n+\t\ttrace2_data_intmax(\"path-walk\", ctx.repo, \"tags\", tags.nr);\n+\t\ttrace2_region_leave(\"path-walk\", \"tag-walk\", info->revs->repo);\n+\t\toid_array_clear(&tags);\n+\t\toid_array_clear(&tagged_tree_list);\n+\t\toid_array_clear(&tagged_blob_list);\n+\t}\n+\n \tstring_list_append(&ctx.path_stack, root_path);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\ndiff --git a/path-walk.h b/path-walk.h\nindex 49b982dade6..637d3b0cabb 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -39,6 +39,7 @@ struct path_walk_info {\n \tint commits;\n \tint trees;\n \tint blobs;\n+\tint tags;\n \n \t/**\n \t * Specify a sparse-checkout definition to match our paths to. Do not\n-- \ngitgitgadget\n\n"},{"id":"502501","messageId":"7d43a1634bbe2d2efa96a806e3de1f1fd480041b.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 09/30] survey: stub in new experimental `git-survey` command","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:34Z","receivedAt":"2024-09-10T02:29:08Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nStart work on a new `git survey` command to scan the repository\nfor monorepo performance and scaling problems. The goal is to\nmeasure the various known \"dimensions of scale\" and serve as a\nfoundation for adding additional measurements as we learn more\nabout Git monorepo scaling problems.\n\nThe initial goal is to complement the scanning and analysis performed\nby the GO-based `git-sizer` (https://github.com/github/git-sizer) tool.\nIt is hoped that by creating a builtin command, we may be able to take\nadvantage of internal Git data structures and code that is not\naccessible from GO to gain further insight into potential scaling\nproblems.\n\nRFC TODO: Adapt this boilerplat to match the upcoming changes to builtin\nmethods that include a 'struct repository' pointer.\n\nCo-authored-by: Derrick Stolee \nSigned-off-by: Jeff Hostetler \nSigned-off-by: Derrick Stolee \n---\n .gitignore | 1 +\n Documentation/git-survey.txt | 36 ++++++++++++++++++++++\n Makefile | 1 +\n builtin.h | 1 +\n builtin/survey.c | 60 ++++++++++++++++++++++++++++++++++++\n command-list.txt | 1 +\n git.c | 1 +\n t/t8100-git-survey.sh | 18 +++++++++++\n 8 files changed, 119 insertions(+)\n create mode 100644 Documentation/git-survey.txt\n create mode 100644 builtin/survey.c\n create mode 100755 t/t8100-git-survey.sh\n\ndiff --git a/.gitignore b/.gitignore\nindex 8f5cb938ecb..3f6fdb31a5e 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -165,6 +165,7 @@\n /git-submodule\n /git-submodule--helper\n /git-subtree\n+/git-survey\n /git-svn\n /git-switch\n /git-symbolic-ref\ndiff --git a/Documentation/git-survey.txt b/Documentation/git-survey.txt\nnew file mode 100644\nindex 00000000000..cdd1ec4358b\n--- /dev/null\n+++ b/Documentation/git-survey.txt\n@@ -0,0 +1,36 @@\n+git-survey(1)\n+=============\n+\n+NAME\n+----\n+git-survey - EXPERIMENTAL: Measure various repository dimensions of scale\n+\n+SYNOPSIS\n+--------\n+[verse]\n+(EXPERIMENTAL!) `git survey` \n+\n+DESCRIPTION\n+-----------\n+\n+Survey the repository and measure various dimensions of scale.\n+\n+As repositories grow to \"monorepo\" size, certain data shapes can cause\n+performance problems. `git-survey` attempts to measure and report on\n+known problem areas.\n+\n+OPTIONS\n+-------\n+\n+--progress::\n+\tShow progress. This is automatically enabled when interactive.\n+\n+OUTPUT\n+------\n+\n+By default, `git survey` will print information about the repository in a\n+human-readable format that includes overviews and tables.\n+\n+GIT\n+---\n+Part of the linkgit:git[1] suite\ndiff --git a/Makefile b/Makefile\nindex 4305474d96e..154de6e01d0 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -1303,6 +1303,7 @@ BUILTIN_OBJS += builtin/sparse-checkout.o\n BUILTIN_OBJS += builtin/stash.o\n BUILTIN_OBJS += builtin/stripspace.o\n BUILTIN_OBJS += builtin/submodule--helper.o\n+BUILTIN_OBJS += builtin/survey.o\n BUILTIN_OBJS += builtin/symbolic-ref.o\n BUILTIN_OBJS += builtin/tag.o\n BUILTIN_OBJS += builtin/unpack-file.o\ndiff --git a/builtin.h b/builtin.h\nindex 73dd0ccbe8c..d4e8cf3b97b 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -239,6 +239,7 @@ int cmd_status(int argc, const char **argv, const char *prefix);\n int cmd_stash(int argc, const char **argv, const char *prefix);\n int cmd_stripspace(int argc, const char **argv, const char *prefix);\n int cmd_submodule__helper(int argc, const char **argv, const char *prefix);\n+int cmd_survey(int argc, const char **argv, const char *prefix);\n int cmd_switch(int argc, const char **argv, const char *prefix);\n int cmd_symbolic_ref(int argc, const char **argv, const char *prefix);\n int cmd_tag(int argc, const char **argv, const char *prefix);\ndiff --git a/builtin/survey.c b/builtin/survey.c\nnew file mode 100644\nindex 00000000000..4cfd0f0293c\n--- /dev/null\n+++ b/builtin/survey.c\n@@ -0,0 +1,60 @@\n+#include \"builtin.h\"\n+#include \"config.h\"\n+#include \"parse-options.h\"\n+\n+static const char * const survey_usage[] = {\n+\tN_(\"(EXPERIMENTAL!) git survey \"),\n+\tNULL,\n+};\n+\n+struct survey_opts {\n+\tint verbose;\n+\tint show_progress;\n+};\n+\n+static struct survey_opts survey_opts = {\n+\t.verbose = 0,\n+\t.show_progress = -1, /* defaults to isatty(2) */\n+};\n+\n+static struct option survey_options[] = {\n+\tOPT__VERBOSE(&survey_opts.verbose, N_(\"verbose output\")),\n+\tOPT_BOOL(0, \"progress\", &survey_opts.show_progress, N_(\"show progress\")),\n+\tOPT_END(),\n+};\n+\n+static int survey_load_config_cb(const char *var, const char *value,\n+\t\t\t\t const struct config_context *ctx, void *pvoid)\n+{\n+\tif (!strcmp(var, \"survey.verbose\")) {\n+\t\tsurvey_opts.verbose = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\tif (!strcmp(var, \"survey.progress\")) {\n+\t\tsurvey_opts.show_progress = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n+\n+\treturn git_default_config(var, value, ctx, pvoid);\n+}\n+\n+static void survey_load_config(void)\n+{\n+\tgit_config(survey_load_config_cb, NULL);\n+}\n+\n+int cmd_survey(int argc, const char **argv, const char *prefix)\n+{\n+\tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n+\t\tusage_with_options(survey_usage, survey_options);\n+\n+\tprepare_repo_settings(the_repository);\n+\tsurvey_load_config();\n+\n+\targc = parse_options(argc, argv, prefix, survey_options, survey_usage, 0);\n+\n+\tif (survey_opts.show_progress < 0)\n+\t\tsurvey_opts.show_progress = isatty(2);\n+\n+\treturn 0;\n+}\ndiff --git a/command-list.txt b/command-list.txt\nindex c537114b468..ecc9d2281a0 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -187,6 +187,7 @@ git-stash mainporcelain\n git-status mainporcelain info\n git-stripspace purehelpers\n git-submodule mainporcelain\n+git-survey mainporcelain\n git-svn foreignscminterface\n git-switch mainporcelain history\n git-symbolic-ref plumbingmanipulators\ndiff --git a/git.c b/git.c\nindex 4f2215e9c8b..98e90838e42 100644\n--- a/git.c\n+++ b/git.c\n@@ -630,6 +630,7 @@ static struct cmd_struct commands[] = {\n \t{ \"status\", cmd_status, RUN_SETUP | NEED_WORK_TREE },\n \t{ \"stripspace\", cmd_stripspace },\n \t{ \"submodule--helper\", cmd_submodule__helper, RUN_SETUP },\n+\t{ \"survey\", cmd_survey, RUN_SETUP },\n \t{ \"switch\", cmd_switch, RUN_SETUP | NEED_WORK_TREE },\n \t{ \"symbolic-ref\", cmd_symbolic_ref, RUN_SETUP },\n \t{ \"tag\", cmd_tag, RUN_SETUP | DELAY_PAGER_CONFIG },\ndiff --git a/t/t8100-git-survey.sh b/t/t8100-git-survey.sh\nnew file mode 100755\nindex 00000000000..2df7fa83629\n--- /dev/null\n+++ b/t/t8100-git-survey.sh\n@@ -0,0 +1,18 @@\n+#!/bin/sh\n+\n+test_description='git survey'\n+\n+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main\n+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME\n+\n+TEST_PASSES_SANITIZE_LEAK=0\n+export TEST_PASSES_SANITIZE_LEAK\n+\n+. ./test-lib.sh\n+\n+test_expect_success 'git survey -h shows experimental warning' '\n+\ttest_expect_code 129 git survey -h 2>usage &&\n+\tgrep \"EXPERIMENTAL!\" usage\n+'\n+\n+test_done\n-- \ngitgitgadget\n\n"},{"id":"502502","messageId":"90986876381e4ccc10c5e191a3928407181e6a04.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 10/30] survey: add command line opts to select references","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:35Z","receivedAt":"2024-09-10T02:29:10Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nBy default we will scan all references in \"refs/heads/\", \"refs/tags/\"\nand \"refs/remotes/\".\n\nAdd command line opts let the use ask for all refs or a subset of them\nand to include a detached HEAD.\n\nSigned-off-by: Jeff Hostetler \nSigned-off-by: Derrick Stolee \n---\n Documentation/git-survey.txt | 34 +++++++++++++\n builtin/survey.c | 99 ++++++++++++++++++++++++++++++++++++\n 2 files changed, 133 insertions(+)\n\ndiff --git a/Documentation/git-survey.txt b/Documentation/git-survey.txt\nindex cdd1ec4358b..c648ef704e3 100644\n--- a/Documentation/git-survey.txt\n+++ b/Documentation/git-survey.txt\n@@ -19,12 +19,46 @@ As repositories grow to \"monorepo\" size, certain data shapes can cause\n performance problems. `git-survey` attempts to measure and report on\n known problem areas.\n \n+Ref Selection and Reachable Objects\n+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n+\n+In this first analysis phase, `git survey` will iterate over the set of\n+requested branches, tags, and other refs and treewalk over all of the\n+reachable commits, trees, and blobs and generate various statistics.\n+\n OPTIONS\n -------\n \n --progress::\n \tShow progress. This is automatically enabled when interactive.\n \n+Ref Selection\n+~~~~~~~~~~~~~\n+\n+The following options control the set of refs that `git survey` will examine.\n+By default, `git survey` will look at tags, local branches, and remote refs.\n+If any of the following options are given, the default set is cleared and\n+only refs for the given options are added.\n+\n+--all-refs::\n+\tUse all refs. This includes local branches, tags, remote refs,\n+\tnotes, and stashes. This option overrides all of the following.\n+\n+--branches::\n+\tAdd local branches (`refs/heads/`) to the set.\n+\n+--tags::\n+\tAdd tags (`refs/tags/`) to the set.\n+\n+--remotes::\n+\tAdd remote branches (`refs/remote/`) to the set.\n+\n+--detached::\n+\tAdd HEAD to the set.\n+\n+--other::\n+\tAdd notes (`refs/notes/`) and stashes (`refs/stash/`) to the set.\n+\n OUTPUT\n ------\n \ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex 4cfd0f0293c..e0e844201de 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -7,19 +7,117 @@ static const char * const survey_usage[] = {\n \tNULL,\n };\n \n+struct survey_refs_wanted {\n+\tint want_all_refs; /* special override */\n+\n+\tint want_branches;\n+\tint want_tags;\n+\tint want_remotes;\n+\tint want_detached;\n+\tint want_other; /* see FILTER_REFS_OTHERS -- refs/notes/, refs/stash/ */\n+};\n+\n+/*\n+ * The set of refs that we will search if the user doesn't select\n+ * any on the command line.\n+ */\n+static struct survey_refs_wanted refs_if_unspecified = {\n+\t.want_all_refs = 0,\n+\n+\t.want_branches = 1,\n+\t.want_tags = 1,\n+\t.want_remotes = 1,\n+\t.want_detached = 0,\n+\t.want_other = 0,\n+};\n+\n struct survey_opts {\n \tint verbose;\n \tint show_progress;\n+\tstruct survey_refs_wanted refs;\n };\n \n static struct survey_opts survey_opts = {\n \t.verbose = 0,\n \t.show_progress = -1, /* defaults to isatty(2) */\n+\n+\t.refs.want_all_refs = -1,\n+\n+\t.refs.want_branches = -1, /* default these to undefined */\n+\t.refs.want_tags = -1,\n+\t.refs.want_remotes = -1,\n+\t.refs.want_detached = -1,\n+\t.refs.want_other = -1,\n };\n \n+/*\n+ * After parsing the command line arguments, figure out which refs we\n+ * should scan.\n+ *\n+ * If ANY were given in positive sense, then we ONLY include them and\n+ * do not use the builtin values.\n+ */\n+static void fixup_refs_wanted(void)\n+{\n+\tstruct survey_refs_wanted *rw = &survey_opts.refs;\n+\n+\t/*\n+\t * `--all-refs` overrides and enables everything.\n+\t */\n+\tif (rw->want_all_refs == 1) {\n+\t\trw->want_branches = 1;\n+\t\trw->want_tags = 1;\n+\t\trw->want_remotes = 1;\n+\t\trw->want_detached = 1;\n+\t\trw->want_other = 1;\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * If none of the `--` were given, we assume all\n+\t * of the builtin unspecified values.\n+\t */\n+\tif (rw->want_branches == -1 &&\n+\t rw->want_tags == -1 &&\n+\t rw->want_remotes == -1 &&\n+\t rw->want_detached == -1 &&\n+\t rw->want_other == -1) {\n+\t\t*rw = refs_if_unspecified;\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * Since we only allow positive boolean values on the command\n+\t * line, we will only have true values where they specified\n+\t * a `--`.\n+\t *\n+\t * So anything that still has an unspecified value should be\n+\t * set to false.\n+\t */\n+\tif (rw->want_branches == -1)\n+\t\trw->want_branches = 0;\n+\tif (rw->want_tags == -1)\n+\t\trw->want_tags = 0;\n+\tif (rw->want_remotes == -1)\n+\t\trw->want_remotes = 0;\n+\tif (rw->want_detached == -1)\n+\t\trw->want_detached = 0;\n+\tif (rw->want_other == -1)\n+\t\trw->want_other = 0;\n+}\n+\n static struct option survey_options[] = {\n \tOPT__VERBOSE(&survey_opts.verbose, N_(\"verbose output\")),\n \tOPT_BOOL(0, \"progress\", &survey_opts.show_progress, N_(\"show progress\")),\n+\n+\tOPT_BOOL_F(0, \"all-refs\", &survey_opts.refs.want_all_refs, N_(\"include all refs\"), PARSE_OPT_NONEG),\n+\n+\tOPT_BOOL_F(0, \"branches\", &survey_opts.refs.want_branches, N_(\"include branches\"), PARSE_OPT_NONEG),\n+\tOPT_BOOL_F(0, \"tags\", &survey_opts.refs.want_tags, N_(\"include tags\"), PARSE_OPT_NONEG),\n+\tOPT_BOOL_F(0, \"remotes\", &survey_opts.refs.want_remotes, N_(\"include all remotes refs\"), PARSE_OPT_NONEG),\n+\tOPT_BOOL_F(0, \"detached\", &survey_opts.refs.want_detached, N_(\"include detached HEAD\"), PARSE_OPT_NONEG),\n+\tOPT_BOOL_F(0, \"other\", &survey_opts.refs.want_other, N_(\"include notes and stashes\"), PARSE_OPT_NONEG),\n+\n \tOPT_END(),\n };\n \n@@ -55,6 +153,7 @@ int cmd_survey(int argc, const char **argv, const char *prefix)\n \n \tif (survey_opts.show_progress < 0)\n \t\tsurvey_opts.show_progress = isatty(2);\n+\tfixup_refs_wanted();\n \n \treturn 0;\n }\n-- \ngitgitgadget\n\n"},{"id":"502503","messageId":"efa1793a5729b152b8961238dd834a26275e969a.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 11/30] survey: collect the set of requested refs","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:36Z","receivedAt":"2024-09-10T02:29:10Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nCollect the set of requested branches, tags, and etc into a ref_array and\ncollect the set of requested patterns into a strvec.\n\nRFC TODO: This patch has some changes that should be in the previous patch,\nto make the diff look a lot better.\n\nCo-authored-by: Derrick Stolee \nSigned-off-by: Jeff Hostetler \nSigned-off-by: Derrick Stolee \n---\n builtin/survey.c | 258 ++++++++++++++++++++++++++++++++++--------\n t/t8100-git-survey.sh | 9 ++\n 2 files changed, 217 insertions(+), 50 deletions(-)\n\ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex e0e844201de..1b4fe591e59 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -1,6 +1,12 @@\n #include \"builtin.h\"\n #include \"config.h\"\n+#include \"object.h\"\n+#include \"object-store-ll.h\"\n #include \"parse-options.h\"\n+#include \"progress.h\"\n+#include \"ref-filter.h\"\n+#include \"strvec.h\"\n+#include \"trace2.h\"\n \n static const char * const survey_usage[] = {\n \tN_(\"(EXPERIMENTAL!) git survey \"),\n@@ -17,18 +23,8 @@ struct survey_refs_wanted {\n \tint want_other; /* see FILTER_REFS_OTHERS -- refs/notes/, refs/stash/ */\n };\n \n-/*\n- * The set of refs that we will search if the user doesn't select\n- * any on the command line.\n- */\n-static struct survey_refs_wanted refs_if_unspecified = {\n-\t.want_all_refs = 0,\n-\n-\t.want_branches = 1,\n-\t.want_tags = 1,\n-\t.want_remotes = 1,\n-\t.want_detached = 0,\n-\t.want_other = 0,\n+static struct survey_refs_wanted default_ref_options = {\n+\t.want_all_refs = 1,\n };\n \n struct survey_opts {\n@@ -37,19 +33,51 @@ struct survey_opts {\n \tstruct survey_refs_wanted refs;\n };\n \n-static struct survey_opts survey_opts = {\n-\t.verbose = 0,\n-\t.show_progress = -1, /* defaults to isatty(2) */\n+struct survey_report_ref_summary {\n+\tsize_t refs_nr;\n+\tsize_t branches_nr;\n+\tsize_t remote_refs_nr;\n+\tsize_t tags_nr;\n+\tsize_t tags_annotated_nr;\n+\tsize_t others_nr;\n+\tsize_t unknown_nr;\n+};\n+\n+/**\n+ * This struct contains all of the information that needs to be printed\n+ * at the end of the exploration of the repository and its references.\n+ */\n+struct survey_report {\n+\tstruct survey_report_ref_summary refs;\n+};\n+\n+struct survey_context {\n+\t/* Options that control what is done. */\n+\tstruct survey_opts opts;\n+\n+\t/* Info for output only. */\n+\tstruct survey_report report;\n \n-\t.refs.want_all_refs = -1,\n+\t/*\n+\t * The rest of the members are about enabling the activity\n+\t * of the 'git survey' command, including ref listings, object\n+\t * pointers, and progress.\n+\t */\n+\n+\tstruct repository *repo;\n+\n+\tstruct progress *progress;\n+\tsize_t progress_nr;\n+\tsize_t progress_total;\n \n-\t.refs.want_branches = -1, /* default these to undefined */\n-\t.refs.want_tags = -1,\n-\t.refs.want_remotes = -1,\n-\t.refs.want_detached = -1,\n-\t.refs.want_other = -1,\n+\tstruct strvec refs;\n };\n \n+static void clear_survey_context(struct survey_context *ctx)\n+{\n+\tstrvec_clear(&ctx->refs);\n+}\n+\n /*\n * After parsing the command line arguments, figure out which refs we\n * should scan.\n@@ -57,9 +85,9 @@ static struct survey_opts survey_opts = {\n * If ANY were given in positive sense, then we ONLY include them and\n * do not use the builtin values.\n */\n-static void fixup_refs_wanted(void)\n+static void fixup_refs_wanted(struct survey_context *ctx)\n {\n-\tstruct survey_refs_wanted *rw = &survey_opts.refs;\n+\tstruct survey_refs_wanted *rw = &ctx->opts.refs;\n \n \t/*\n \t * `--all-refs` overrides and enables everything.\n@@ -82,7 +110,7 @@ static void fixup_refs_wanted(void)\n \t rw->want_remotes == -1 &&\n \t rw->want_detached == -1 &&\n \t rw->want_other == -1) {\n-\t\t*rw = refs_if_unspecified;\n+\t\t*rw = default_ref_options;\n \t\treturn;\n \t}\n \n@@ -106,54 +134,184 @@ static void fixup_refs_wanted(void)\n \t\trw->want_other = 0;\n }\n \n-static struct option survey_options[] = {\n-\tOPT__VERBOSE(&survey_opts.verbose, N_(\"verbose output\")),\n-\tOPT_BOOL(0, \"progress\", &survey_opts.show_progress, N_(\"show progress\")),\n-\n-\tOPT_BOOL_F(0, \"all-refs\", &survey_opts.refs.want_all_refs, N_(\"include all refs\"), PARSE_OPT_NONEG),\n-\n-\tOPT_BOOL_F(0, \"branches\", &survey_opts.refs.want_branches, N_(\"include branches\"), PARSE_OPT_NONEG),\n-\tOPT_BOOL_F(0, \"tags\", &survey_opts.refs.want_tags, N_(\"include tags\"), PARSE_OPT_NONEG),\n-\tOPT_BOOL_F(0, \"remotes\", &survey_opts.refs.want_remotes, N_(\"include all remotes refs\"), PARSE_OPT_NONEG),\n-\tOPT_BOOL_F(0, \"detached\", &survey_opts.refs.want_detached, N_(\"include detached HEAD\"), PARSE_OPT_NONEG),\n-\tOPT_BOOL_F(0, \"other\", &survey_opts.refs.want_other, N_(\"include notes and stashes\"), PARSE_OPT_NONEG),\n-\n-\tOPT_END(),\n-};\n-\n static int survey_load_config_cb(const char *var, const char *value,\n-\t\t\t\t const struct config_context *ctx, void *pvoid)\n+\t\t\t\t const struct config_context *cctx, void *pvoid)\n {\n+\tstruct survey_context *sctx = pvoid;\n \tif (!strcmp(var, \"survey.verbose\")) {\n-\t\tsurvey_opts.verbose = git_config_bool(var, value);\n+\t\tsctx->opts.verbose = git_config_bool(var, value);\n \t\treturn 0;\n \t}\n \tif (!strcmp(var, \"survey.progress\")) {\n-\t\tsurvey_opts.show_progress = git_config_bool(var, value);\n+\t\tsctx->opts.show_progress = git_config_bool(var, value);\n \t\treturn 0;\n \t}\n \n-\treturn git_default_config(var, value, ctx, pvoid);\n+\treturn git_default_config(var, value, cctx, pvoid);\n }\n \n-static void survey_load_config(void)\n+static void survey_load_config(struct survey_context *ctx)\n {\n-\tgit_config(survey_load_config_cb, NULL);\n+\tgit_config(survey_load_config_cb, ctx);\n+}\n+\n+static void do_load_refs(struct survey_context *ctx,\n+\t\t\t struct ref_array *ref_array)\n+{\n+\tstruct ref_filter filter = REF_FILTER_INIT;\n+\tstruct ref_sorting *sorting;\n+\tstruct string_list sorting_options = STRING_LIST_INIT_DUP;\n+\n+\tstring_list_append(&sorting_options, \"objectname\");\n+\tsorting = ref_sorting_options(&sorting_options);\n+\n+\tif (ctx->opts.refs.want_detached)\n+\t\tstrvec_push(&ctx->refs, \"HEAD\");\n+\n+\tif (ctx->opts.refs.want_all_refs) {\n+\t\tstrvec_push(&ctx->refs, \"refs/\");\n+\t} else {\n+\t\tif (ctx->opts.refs.want_branches)\n+\t\t\tstrvec_push(&ctx->refs, \"refs/heads/\");\n+\t\tif (ctx->opts.refs.want_tags)\n+\t\t\tstrvec_push(&ctx->refs, \"refs/tags/\");\n+\t\tif (ctx->opts.refs.want_remotes)\n+\t\t\tstrvec_push(&ctx->refs, \"refs/remotes/\");\n+\t\tif (ctx->opts.refs.want_other) {\n+\t\t\tstrvec_push(&ctx->refs, \"refs/notes/\");\n+\t\t\tstrvec_push(&ctx->refs, \"refs/stash/\");\n+\t\t}\n+\t}\n+\n+\tfilter.name_patterns = ctx->refs.v;\n+\tfilter.ignore_case = 0;\n+\tfilter.match_as_path = 1;\n+\n+\tif (ctx->opts.show_progress) {\n+\t\tctx->progress_total = 0;\n+\t\tctx->progress = start_progress(_(\"Scanning refs...\"), 0);\n+\t}\n+\n+\tfilter_refs(ref_array, &filter, FILTER_REFS_KIND_MASK);\n+\n+\tif (ctx->opts.show_progress) {\n+\t\tctx->progress_total = ref_array->nr;\n+\t\tdisplay_progress(ctx->progress, ctx->progress_total);\n+\t}\n+\n+\tref_array_sort(sorting, ref_array);\n+\n+\tstop_progress(&ctx->progress);\n+\tref_filter_clear(&filter);\n+\tref_sorting_release(sorting);\n+}\n+\n+/*\n+ * The REFS phase:\n+ *\n+ * Load the set of requested refs and assess them for scalablity problems.\n+ * Use that set to start a treewalk to all reachable objects and assess\n+ * them.\n+ *\n+ * This data will give us insights into the repository itself (the number\n+ * of refs, the size and shape of the DAG, the number and size of the\n+ * objects).\n+ *\n+ * Theoretically, this data is independent of the on-disk representation\n+ * (e.g. independent of packing concerns).\n+ */\n+static void survey_phase_refs(struct survey_context *ctx)\n+{\n+\tstruct ref_array ref_array = { 0 };\n+\n+\ttrace2_region_enter(\"survey\", \"phase/refs\", ctx->repo);\n+\tdo_load_refs(ctx, &ref_array);\n+\n+\tctx->report.refs.refs_nr = ref_array.nr;\n+\tfor (size_t i = 0; i < ref_array.nr; i++) {\n+\t\tsize_t size;\n+\t\tstruct ref_array_item *item = ref_array.items[i];\n+\n+\t\tswitch (item->kind) {\n+\t\tcase FILTER_REFS_TAGS:\n+\t\t\tctx->report.refs.tags_nr++;\n+\t\t\tif (oid_object_info(ctx->repo,\n+\t\t\t\t\t &item->objectname,\n+\t\t\t\t\t &size) == OBJ_TAG)\n+\t\t\t\tctx->report.refs.tags_annotated_nr++;\n+\t\t\tbreak;\n+\n+\t\tcase FILTER_REFS_BRANCHES:\n+\t\t\tctx->report.refs.branches_nr++;\n+\t\t\tbreak;\n+\n+\t\tcase FILTER_REFS_REMOTES:\n+\t\t\tctx->report.refs.remote_refs_nr++;\n+\t\t\tbreak;\n+\n+\t\tcase FILTER_REFS_OTHERS:\n+\t\t\tctx->report.refs.others_nr++;\n+\t\t\tbreak;\n+\n+\t\tdefault:\n+\t\t\tctx->report.refs.unknown_nr++;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\ttrace2_region_leave(\"survey\", \"phase/refs\", ctx->repo);\n+\n+\tref_array_clear(&ref_array);\n }\n \n int cmd_survey(int argc, const char **argv, const char *prefix)\n {\n+\tstatic struct survey_context ctx = {\n+\t\t.opts = {\n+\t\t\t.verbose = 0,\n+\t\t\t.show_progress = -1, /* defaults to isatty(2) */\n+\n+\t\t\t.refs.want_all_refs = -1,\n+\n+\t\t\t.refs.want_branches = -1, /* default these to undefined */\n+\t\t\t.refs.want_tags = -1,\n+\t\t\t.refs.want_remotes = -1,\n+\t\t\t.refs.want_detached = -1,\n+\t\t\t.refs.want_other = -1,\n+\t\t},\n+\t\t.refs = STRVEC_INIT,\n+\t};\n+\n+\tstatic struct option survey_options[] = {\n+\t\tOPT__VERBOSE(&ctx.opts.verbose, N_(\"verbose output\")),\n+\t\tOPT_BOOL(0, \"progress\", &ctx.opts.show_progress, N_(\"show progress\")),\n+\n+\t\tOPT_BOOL_F(0, \"all-refs\", &ctx.opts.refs.want_all_refs, N_(\"include all refs\"), PARSE_OPT_NONEG),\n+\n+\t\tOPT_BOOL_F(0, \"branches\", &ctx.opts.refs.want_branches, N_(\"include branches\"), PARSE_OPT_NONEG),\n+\t\tOPT_BOOL_F(0, \"tags\", &ctx.opts.refs.want_tags, N_(\"include tags\"), PARSE_OPT_NONEG),\n+\t\tOPT_BOOL_F(0, \"remotes\", &ctx.opts.refs.want_remotes, N_(\"include all remotes refs\"), PARSE_OPT_NONEG),\n+\t\tOPT_BOOL_F(0, \"detached\", &ctx.opts.refs.want_detached, N_(\"include detached HEAD\"), PARSE_OPT_NONEG),\n+\t\tOPT_BOOL_F(0, \"other\", &ctx.opts.refs.want_other, N_(\"include notes and stashes\"), PARSE_OPT_NONEG),\n+\n+\t\tOPT_END(),\n+\t};\n+\n \tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n \t\tusage_with_options(survey_usage, survey_options);\n \n-\tprepare_repo_settings(the_repository);\n-\tsurvey_load_config();\n+\tctx.repo = the_repository;\n+\tprepare_repo_settings(ctx.repo);\n+\tsurvey_load_config(&ctx);\n \n \targc = parse_options(argc, argv, prefix, survey_options, survey_usage, 0);\n \n-\tif (survey_opts.show_progress < 0)\n-\t\tsurvey_opts.show_progress = isatty(2);\n-\tfixup_refs_wanted();\n+\tif (ctx.opts.show_progress < 0)\n+\t\tctx.opts.show_progress = isatty(2);\n+\tfixup_refs_wanted(&ctx);\n+\n+\tsurvey_phase_refs(&ctx);\n \n+\tclear_survey_context(&ctx);\n \treturn 0;\n }\ndiff --git a/t/t8100-git-survey.sh b/t/t8100-git-survey.sh\nindex 2df7fa83629..5903c90cb57 100755\n--- a/t/t8100-git-survey.sh\n+++ b/t/t8100-git-survey.sh\n@@ -15,4 +15,13 @@ test_expect_success 'git survey -h shows experimental warning' '\n \tgrep \"EXPERIMENTAL!\" usage\n '\n \n+test_expect_success 'creat a semi-interesting repo' '\n+\ttest_commit_bulk 10\n+'\n+\n+test_expect_success 'git survey (default)' '\n+\tgit survey >out 2>err &&\n+\ttest_line_count = 0 err\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"502504","messageId":"44417cceddcaeec9e90acd0b058edd8c80627479.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 12/30] survey: start pretty printing data in table form","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:37Z","receivedAt":"2024-09-10T02:29:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen 'git survey' provides information to the user, this will be presented\nin one of two formats: plaintext and JSON. The JSON implementation will be\ndelayed until the functionality is complete for the plaintext format.\n\nThe most important parts of the plaintext format are headers specifying the\ndifferent sections of the report and tables providing concreted data.\n\nCreate a custom table data structure that allows specifying a list of\nstrings for the row values. When printing the table, check each column for\nthe maximum width so we can create a table of the correct size from the\nstart.\n\nThe table structure is designed to be flexible to the different kinds of\noutput that will be implemented in future changes.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/survey.c | 175 ++++++++++++++++++++++++++++++++++++++++++\n t/t8100-git-survey.sh | 17 +++-\n 2 files changed, 191 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex 1b4fe591e59..b2104e84d61 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -5,6 +5,7 @@\n #include \"parse-options.h\"\n #include \"progress.h\"\n #include \"ref-filter.h\"\n+#include \"strbuf.h\"\n #include \"strvec.h\"\n #include \"trace2.h\"\n \n@@ -27,10 +28,16 @@ static struct survey_refs_wanted default_ref_options = {\n \t.want_all_refs = 1,\n };\n \n+enum survey_format {\n+\tSURVEY_PLAINTEXT = 0,\n+\tSURVEY_JSON = 1,\n+};\n+\n struct survey_opts {\n \tint verbose;\n \tint show_progress;\n \tstruct survey_refs_wanted refs;\n+\tenum survey_format format;\n };\n \n struct survey_report_ref_summary {\n@@ -78,6 +85,161 @@ static void clear_survey_context(struct survey_context *ctx)\n \tstrvec_clear(&ctx->refs);\n }\n \n+struct survey_table {\n+\tconst char *table_name;\n+\tstruct strvec header;\n+\tstruct strvec *rows;\n+\tsize_t rows_nr;\n+\tsize_t rows_alloc;\n+};\n+\n+#define SURVEY_TABLE_INIT {\t\\\n+\t.header = STRVEC_INIT,\t\\\n+}\n+\n+static void clear_table(struct survey_table *table)\n+{\n+\tstrvec_clear(&table->header);\n+\tfor (size_t i = 0; i < table->rows_nr; i++)\n+\t\tstrvec_clear(&table->rows[i]);\n+\tfree(table->rows);\n+}\n+\n+static void insert_table_rowv(struct survey_table *table, ...)\n+{\n+\tva_list ap;\n+\tchar *arg;\n+\tALLOC_GROW(table->rows, table->rows_nr + 1, table->rows_alloc);\n+\n+\tmemset(&table->rows[table->rows_nr], 0, sizeof(struct strvec));\n+\n+\tva_start(ap, table);\n+\twhile ((arg = va_arg(ap, char *)))\n+\t\tstrvec_push(&table->rows[table->rows_nr], arg);\n+\tva_end(ap);\n+\n+\ttable->rows_nr++;\n+}\n+\n+static void print_table_title(const char *name, size_t *widths, size_t nr)\n+{\n+\tstatic struct strbuf lines = STRBUF_INIT;\n+\tsize_t width = 0;\n+\tstrbuf_setlen(&lines, 0);\n+\n+\tstrbuf_addch(&lines, ' ');\n+\tstrbuf_addstr(&lines, name);\n+\tstrbuf_addch(&lines, '\\n');\n+\n+\tfor (size_t i = 0; i < nr; i++) {\n+\t\tif (i)\n+\t\t\twidth += 3;\n+\t\twidth += widths[i];\n+\t}\n+\tstrbuf_addchars(&lines, '=', width);\n+\tprintf(\"%s\\n\", lines.buf);\n+}\n+\n+static void print_row_plaintext(struct strvec *row, size_t *widths)\n+{\n+\tstatic struct strbuf line = STRBUF_INIT;\n+\tstrbuf_setlen(&line, 0);\n+\n+\tfor (size_t i = 0; i < row->nr; i++) {\n+\t\tconst char *str = row->v[i];\n+\t\tsize_t len = strlen(str);\n+\t\tif (i)\n+\t\t\tstrbuf_add(&line, \" | \", 3);\n+\t\tstrbuf_addchars(&line, ' ', widths[i] - len);\n+\t\tstrbuf_add(&line, str, len);\n+\t}\n+\tprintf(\"%s\\n\", line.buf);\n+}\n+\n+static void print_divider_plaintext(size_t *widths, size_t nr)\n+{\n+\tstatic struct strbuf line = STRBUF_INIT;\n+\tstrbuf_setlen(&line, 0);\n+\n+\tfor (size_t i = 0; i < nr; i++) {\n+\t\tif (i)\n+\t\t\tstrbuf_add(&line, \"-+-\", 3);\n+\t\tstrbuf_addchars(&line, '-', widths[i]);\n+\t}\n+\tprintf(\"%s\\n\", line.buf);\n+}\n+\n+static void print_table_plaintext(struct survey_table *table)\n+{\n+\tsize_t *column_widths;\n+\tsize_t columns_nr = table->header.nr;\n+\tCALLOC_ARRAY(column_widths, columns_nr);\n+\n+\tfor (size_t i = 0; i < columns_nr; i++) {\n+\t\tcolumn_widths[i] = strlen(table->header.v[i]);\n+\n+\t\tfor (size_t j = 0; j < table->rows_nr; j++) {\n+\t\t\tsize_t rowlen = strlen(table->rows[j].v[i]);\n+\t\t\tif (column_widths[i] < rowlen)\n+\t\t\t\tcolumn_widths[i] = rowlen;\n+\t\t}\n+\t}\n+\n+\tprint_table_title(table->table_name, column_widths, columns_nr);\n+\tprint_row_plaintext(&table->header, column_widths);\n+\tprint_divider_plaintext(column_widths, columns_nr);\n+\n+\tfor (size_t j = 0; j < table->rows_nr; j++)\n+\t\tprint_row_plaintext(&table->rows[j], column_widths);\n+}\n+\n+static void survey_report_plaintext_refs(struct survey_context *ctx)\n+{\n+\tstruct survey_report_ref_summary *refs = &ctx->report.refs;\n+\tstruct survey_table table = SURVEY_TABLE_INIT;\n+\n+\ttable.table_name = _(\"REFERENCES SUMMARY\");\n+\n+\tstrvec_push(&table.header, _(\"Ref Type\"));\n+\tstrvec_push(&table.header, _(\"Count\"));\n+\n+\tif (ctx->opts.refs.want_all_refs || ctx->opts.refs.want_branches) {\n+\t\tchar *fmt = xstrfmt(\"%\"PRIuMAX\"\", refs->branches_nr);\n+\t\tinsert_table_rowv(&table, _(\"Branches\"), fmt, NULL);\n+\t\tfree(fmt);\n+\t}\n+\n+\tif (ctx->opts.refs.want_all_refs || ctx->opts.refs.want_remotes) {\n+\t\tchar *fmt = xstrfmt(\"%\"PRIuMAX\"\", refs->remote_refs_nr);\n+\t\tinsert_table_rowv(&table, _(\"Remote refs\"), fmt, NULL);\n+\t\tfree(fmt);\n+\t}\n+\n+\tif (ctx->opts.refs.want_all_refs || ctx->opts.refs.want_tags) {\n+\t\tchar *fmt = xstrfmt(\"%\"PRIuMAX\"\", refs->tags_nr);\n+\t\tinsert_table_rowv(&table, _(\"Tags (all)\"), fmt, NULL);\n+\t\tfree(fmt);\n+\t\tfmt = xstrfmt(\"%\"PRIuMAX\"\", refs->tags_annotated_nr);\n+\t\tinsert_table_rowv(&table, _(\"Tags (annotated)\"), fmt, NULL);\n+\t\tfree(fmt);\n+\t}\n+\n+\tprint_table_plaintext(&table);\n+\tclear_table(&table);\n+}\n+\n+static void survey_report_plaintext(struct survey_context *ctx)\n+{\n+\tprintf(\"GIT SURVEY for \\\"%s\\\"\\n\", ctx->repo->worktree);\n+\tprintf(\"-----------------------------------------------------\\n\");\n+\tsurvey_report_plaintext_refs(ctx);\n+}\n+\n+static void survey_report_json(struct survey_context *ctx)\n+{\n+\t/* TODO. */\n+}\n+\n /*\n * After parsing the command line arguments, figure out which refs we\n * should scan.\n@@ -312,6 +474,19 @@ int cmd_survey(int argc, const char **argv, const char *prefix)\n \n \tsurvey_phase_refs(&ctx);\n \n+\tswitch (ctx.opts.format) {\n+\tcase SURVEY_PLAINTEXT:\n+\t\tsurvey_report_plaintext(&ctx);\n+\t\tbreak;\n+\n+\tcase SURVEY_JSON:\n+\t\tsurvey_report_json(&ctx);\n+\t\tbreak;\n+\n+\tdefault:\n+\t\tBUG(\"Undefined format\");\n+\t}\n+\n \tclear_survey_context(&ctx);\n \treturn 0;\n }\ndiff --git a/t/t8100-git-survey.sh b/t/t8100-git-survey.sh\nindex 5903c90cb57..a57f6ca7a59 100755\n--- a/t/t8100-git-survey.sh\n+++ b/t/t8100-git-survey.sh\n@@ -21,7 +21,22 @@ test_expect_success 'creat a semi-interesting repo' '\n \n test_expect_success 'git survey (default)' '\n \tgit survey >out 2>err &&\n-\ttest_line_count = 0 err\n+\ttest_line_count = 0 err &&\n+\n+\tcat >expect <<-EOF &&\n+\tGIT SURVEY for \"$(pwd)\"\n+\t-----------------------------------------------------\n+\t REFERENCES SUMMARY\n+\t========================\n+\t Ref Type | Count\n+\t-----------------+------\n+\t Branches | 1\n+\t Remote refs | 0\n+\t Tags (all) | 0\n+\tTags (annotated) | 0\n+\tEOF\n+\n+\ttest_cmp expect out\n '\n \n test_done\n-- \ngitgitgadget\n\n"},{"id":"502505","messageId":"fcc281ac2bfabb6d19e6be40c41157612c5a3f83.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 13/30] survey: add object count summary","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:38Z","receivedAt":"2024-09-10T02:29:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAt the moment, nothing is obvious about the reason for the use of the\npath-walk API, but this will become more prevelant in future iterations. For\nnow, use the path-walk API to sum up the counts of each kind of object.\n\nFor example, this is the reachable object summary output for my local repo:\n\nREACHABLE OBJECT SUMMARY\n========================\nObject Type | Count\n------------+-------\n Tags | 0\n Commits | 178573\n Trees | 312745\n Blobs | 183035\n\n(Note: the \"Tags\" are zero right now because the path-walk API has not been\nintegrated to walk tags yet. This will be fixed in a later change.)\n\nRFC TODO: make sure tags are walked before this change.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/survey.c | 196 ++++++++++++++++++++++++++++++++++++++++--\n t/t8100-git-survey.sh | 26 ++++--\n 2 files changed, 209 insertions(+), 13 deletions(-)\n\ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex b2104e84d61..504b4edafce 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -1,12 +1,19 @@\n #include \"builtin.h\"\n #include \"config.h\"\n+#include \"environment.h\"\n+#include \"hex.h\"\n #include \"object.h\"\n+#include \"object-name.h\"\n #include \"object-store-ll.h\"\n #include \"parse-options.h\"\n+#include \"path-walk.h\"\n #include \"progress.h\"\n #include \"ref-filter.h\"\n+#include \"refs.h\"\n+#include \"revision.h\"\n #include \"strbuf.h\"\n #include \"strvec.h\"\n+#include \"tag.h\"\n #include \"trace2.h\"\n \n static const char * const survey_usage[] = {\n@@ -50,12 +57,20 @@ struct survey_report_ref_summary {\n \tsize_t unknown_nr;\n };\n \n+struct survey_report_object_summary {\n+\tsize_t commits_nr;\n+\tsize_t tags_nr;\n+\tsize_t trees_nr;\n+\tsize_t blobs_nr;\n+};\n+\n /**\n * This struct contains all of the information that needs to be printed\n * at the end of the exploration of the repository and its references.\n */\n struct survey_report {\n \tstruct survey_report_ref_summary refs;\n+\tstruct survey_report_object_summary reachable_objects;\n };\n \n struct survey_context {\n@@ -78,10 +93,12 @@ struct survey_context {\n \tsize_t progress_total;\n \n \tstruct strvec refs;\n+\tstruct ref_array ref_array;\n };\n \n static void clear_survey_context(struct survey_context *ctx)\n {\n+\tref_array_clear(&ctx->ref_array);\n \tstrvec_clear(&ctx->refs);\n }\n \n@@ -125,10 +142,12 @@ static void print_table_title(const char *name, size_t *widths, size_t nr)\n {\n \tstatic struct strbuf lines = STRBUF_INIT;\n \tsize_t width = 0;\n+\tsize_t min_width;\n \tstrbuf_setlen(&lines, 0);\n \n-\tstrbuf_addch(&lines, ' ');\n+\tstrbuf_addch(&lines, '\\n');\n \tstrbuf_addstr(&lines, name);\n+\tmin_width = lines.len - 1;\n \tstrbuf_addch(&lines, '\\n');\n \n \tfor (size_t i = 0; i < nr; i++) {\n@@ -136,6 +155,10 @@ static void print_table_title(const char *name, size_t *widths, size_t nr)\n \t\t\twidth += 3;\n \t\twidth += widths[i];\n \t}\n+\n+\tif (width < min_width)\n+\t\twidth = min_width;\n+\n \tstrbuf_addchars(&lines, '=', width);\n \tprintf(\"%s\\n\", lines.buf);\n }\n@@ -228,11 +251,43 @@ static void survey_report_plaintext_refs(struct survey_context *ctx)\n \tclear_table(&table);\n }\n \n+static void survey_report_plaintext_reachable_object_summary(struct survey_context *ctx)\n+{\n+\tstruct survey_report_object_summary *objs = &ctx->report.reachable_objects;\n+\tstruct survey_table table = SURVEY_TABLE_INIT;\n+\tchar *fmt;\n+\n+\ttable.table_name = _(\"REACHABLE OBJECT SUMMARY\");\n+\n+\tstrvec_push(&table.header, _(\"Object Type\"));\n+\tstrvec_push(&table.header, _(\"Count\"));\n+\n+\tfmt = xstrfmt(\"%\"PRIuMAX\"\", objs->tags_nr);\n+\tinsert_table_rowv(&table, _(\"Tags\"), fmt, NULL);\n+\tfree(fmt);\n+\n+\tfmt = xstrfmt(\"%\"PRIuMAX\"\", objs->commits_nr);\n+\tinsert_table_rowv(&table, _(\"Commits\"), fmt, NULL);\n+\tfree(fmt);\n+\n+\tfmt = xstrfmt(\"%\"PRIuMAX\"\", objs->trees_nr);\n+\tinsert_table_rowv(&table, _(\"Trees\"), fmt, NULL);\n+\tfree(fmt);\n+\n+\tfmt = xstrfmt(\"%\"PRIuMAX\"\", objs->blobs_nr);\n+\tinsert_table_rowv(&table, _(\"Blobs\"), fmt, NULL);\n+\tfree(fmt);\n+\n+\tprint_table_plaintext(&table);\n+\tclear_table(&table);\n+}\n+\n static void survey_report_plaintext(struct survey_context *ctx)\n {\n \tprintf(\"GIT SURVEY for \\\"%s\\\"\\n\", ctx->repo->worktree);\n \tprintf(\"-----------------------------------------------------\\n\");\n \tsurvey_report_plaintext_refs(ctx);\n+\tsurvey_report_plaintext_reachable_object_summary(ctx);\n }\n \n static void survey_report_json(struct survey_context *ctx)\n@@ -384,15 +439,13 @@ static void do_load_refs(struct survey_context *ctx,\n */\n static void survey_phase_refs(struct survey_context *ctx)\n {\n-\tstruct ref_array ref_array = { 0 };\n-\n \ttrace2_region_enter(\"survey\", \"phase/refs\", ctx->repo);\n-\tdo_load_refs(ctx, &ref_array);\n+\tdo_load_refs(ctx, &ctx->ref_array);\n \n-\tctx->report.refs.refs_nr = ref_array.nr;\n-\tfor (size_t i = 0; i < ref_array.nr; i++) {\n+\tctx->report.refs.refs_nr = ctx->ref_array.nr;\n+\tfor (size_t i = 0; i < ctx->ref_array.nr; i++) {\n \t\tsize_t size;\n-\t\tstruct ref_array_item *item = ref_array.items[i];\n+\t\tstruct ref_array_item *item = ctx->ref_array.items[i];\n \n \t\tswitch (item->kind) {\n \t\tcase FILTER_REFS_TAGS:\n@@ -422,8 +475,133 @@ static void survey_phase_refs(struct survey_context *ctx)\n \t}\n \n \ttrace2_region_leave(\"survey\", \"phase/refs\", ctx->repo);\n+}\n+\n+static void increment_object_counts(\n+\t\tstruct survey_report_object_summary *summary,\n+\t\tenum object_type type,\n+\t\tsize_t nr)\n+{\n+\tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\t\tsummary->commits_nr += nr;\n+\t\tbreak;\n+\n+\tcase OBJ_TREE:\n+\t\tsummary->trees_nr += nr;\n+\t\tbreak;\n+\n+\tcase OBJ_BLOB:\n+\t\tsummary->blobs_nr += nr;\n+\t\tbreak;\n+\n+\tdefault:\n+\t\tbreak;\n+\t}\n+}\n+\n+static int survey_objects_path_walk_fn(const char *path,\n+\t\t\t\t struct oid_array *oids,\n+\t\t\t\t enum object_type type,\n+\t\t\t\t void *data)\n+{\n+\tstruct survey_context *ctx = data;\n+\n+\tincrement_object_counts(&ctx->report.reachable_objects,\n+\t\t\t\ttype, oids->nr);\n+\n+\treturn 0;\n+}\n+\n+static int iterate_tag_chain(struct survey_context *ctx,\n+\t\t\t struct object_id *oid,\n+\t\t\t struct object_id *peeled)\n+{\n+\tstruct object *o = lookup_unknown_object(ctx->repo, oid);\n+\tstruct tag *t;\n+\n+\tif (o->type != OBJ_TAG) {\n+\t\toidcpy(peeled, &o->oid);\n+\t\treturn o->type != OBJ_COMMIT;\n+\t}\n+\n+\tt = lookup_tag(ctx->repo, oid);\n+\twhile (t) {\n+\t\tparse_tag(t);\n+\t\tctx->report.reachable_objects.tags_nr++;\n+\n+\t\tif (!t->tagged)\n+\t\t\tbreak;\n+\n+\t\to = lookup_unknown_object(ctx->repo, &t->tagged->oid);\n+\t\tif (o && o->type == OBJ_TAG)\n+\t\t\tt = lookup_tag(ctx->repo, &t->tagged->oid);\n+\t\telse\n+\t\t\tbreak;\n+\t}\n+\n+\tif (!t || !t->tagged)\n+\t\treturn -1;\n \n-\tref_array_clear(&ref_array);\n+\toidcpy(peeled, &t->tagged->oid);\n+\to = lookup_unknown_object(ctx->repo, peeled);\n+\tif (o && o->type == OBJ_COMMIT)\n+\t\treturn 0;\n+\treturn -1;\n+}\n+\n+static void survey_phase_objects(struct survey_context *ctx)\n+{\n+\tstruct rev_info revs = REV_INFO_INIT;\n+\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n+\tunsigned int add_flags = 0;\n+\n+\ttrace2_region_enter(\"survey\", \"phase/objects\", ctx->repo);\n+\n+\tinfo.revs = &revs;\n+\tinfo.path_fn = survey_objects_path_walk_fn;\n+\tinfo.path_fn_data = ctx;\n+\n+\tinfo.commits = 1;\n+\tinfo.trees = 1;\n+\tinfo.blobs = 1;\n+\tinfo.tags = 1;\n+\n+\trepo_init_revisions(ctx->repo, &revs, \"\");\n+\n+\tfor (size_t i = 0; i < ctx->ref_array.nr; i++) {\n+\t\tstruct ref_array_item *item = ctx->ref_array.items[i];\n+\t\tstruct object_id peeled;\n+\n+\t\tswitch (item->kind) {\n+\t\tcase FILTER_REFS_TAGS:\n+\t\t\tif (!iterate_tag_chain(ctx, &item->objectname, &peeled))\n+\t\t\t\tadd_pending_oid(&revs, NULL, &peeled, add_flags);\n+\t\t\tbreak;\n+\t\tcase FILTER_REFS_BRANCHES:\n+\t\t\tadd_pending_oid(&revs, NULL, &item->objectname, add_flags);\n+\t\t\tbreak;\n+\t\tcase FILTER_REFS_REMOTES:\n+\t\t\tadd_pending_oid(&revs, NULL, &item->objectname, add_flags);\n+\t\t\tbreak;\n+\t\tcase FILTER_REFS_OTHERS:\n+\t\t\t/*\n+\t\t\t * This may be a note, stash, or custom namespace branch.\n+\t\t\t */\n+\t\t\tadd_pending_oid(&revs, NULL, &item->objectname, add_flags);\n+\t\t\tbreak;\n+\t\tcase FILTER_REFS_DETACHED_HEAD:\n+\t\t\tadd_pending_oid(&revs, NULL, &item->objectname, add_flags);\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\twalk_objects_by_path(&info);\n+\n+\trelease_revisions(&revs);\n+\ttrace2_region_leave(\"survey\", \"phase/objects\", ctx->repo);\n }\n \n int cmd_survey(int argc, const char **argv, const char *prefix)\n@@ -474,6 +652,8 @@ int cmd_survey(int argc, const char **argv, const char *prefix)\n \n \tsurvey_phase_refs(&ctx);\n \n+\tsurvey_phase_objects(&ctx);\n+\n \tswitch (ctx.opts.format) {\n \tcase SURVEY_PLAINTEXT:\n \t\tsurvey_report_plaintext(&ctx);\ndiff --git a/t/t8100-git-survey.sh b/t/t8100-git-survey.sh\nindex a57f6ca7a59..0da92eafa95 100755\n--- a/t/t8100-git-survey.sh\n+++ b/t/t8100-git-survey.sh\n@@ -16,24 +16,40 @@ test_expect_success 'git survey -h shows experimental warning' '\n '\n \n test_expect_success 'creat a semi-interesting repo' '\n-\ttest_commit_bulk 10\n+\ttest_commit_bulk 10 &&\n+\tgit tag -a -m one one HEAD~5 &&\n+\tgit tag -a -m two two HEAD~3 &&\n+\tgit tag -a -m three three two &&\n+\tgit tag -a -m four four three &&\n+\tgit update-ref -d refs/tags/three &&\n+\tgit update-ref -d refs/tags/two\n '\n \n test_expect_success 'git survey (default)' '\n-\tgit survey >out 2>err &&\n+\tgit survey --all-refs >out 2>err &&\n \ttest_line_count = 0 err &&\n \n \tcat >expect <<-EOF &&\n \tGIT SURVEY for \"$(pwd)\"\n \t-----------------------------------------------------\n-\t REFERENCES SUMMARY\n+\n+\tREFERENCES SUMMARY\n \t========================\n \t Ref Type | Count\n \t-----------------+------\n \t Branches | 1\n \t Remote refs | 0\n-\t Tags (all) | 0\n-\tTags (annotated) | 0\n+\t Tags (all) | 2\n+\tTags (annotated) | 2\n+\n+\tREACHABLE OBJECT SUMMARY\n+\t========================\n+\tObject Type | Count\n+\t------------+------\n+\t Tags | 0\n+\t Commits | 10\n+\t Trees | 10\n+\t Blobs | 10\n \tEOF\n \n \ttest_cmp expect out\n-- \ngitgitgadget\n\n"},{"id":"502506","messageId":"462ca0b80d29218647ffd26c2ae22c359917f00c.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 14/30] survey: summarize total sizes by object type","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:39Z","receivedAt":"2024-09-10T02:29:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nNow that we have explored objects by count, we can expand that a bit more to\nsummarize the data for the on-disk and inflated size of those objects. This\ninformation is helpful for diagnosing both why disk space (and perhaps\nclone or fetch times) is growing but also why certain operations are slow\nbecause the inflated size of the abstract objects that must be processed is\nso large.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/survey.c | 113 ++++++++++++++++++++++++++++++++++++++++++\n t/t8100-git-survey.sh | 8 +++\n 2 files changed, 121 insertions(+)\n\ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex 504b4edafce..435c4bd452a 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -64,6 +64,19 @@ struct survey_report_object_summary {\n \tsize_t blobs_nr;\n };\n \n+/**\n+ * For some category given by 'label', count the number of objects\n+ * that match that label along with the on-disk size and the size\n+ * after decompressing (both with delta bases and zlib).\n+ */\n+struct survey_report_object_size_summary {\n+\tchar *label;\n+\tsize_t nr;\n+\tsize_t disk_size;\n+\tsize_t inflated_size;\n+\tsize_t num_missing;\n+};\n+\n /**\n * This struct contains all of the information that needs to be printed\n * at the end of the exploration of the repository and its references.\n@@ -71,8 +84,15 @@ struct survey_report_object_summary {\n struct survey_report {\n \tstruct survey_report_ref_summary refs;\n \tstruct survey_report_object_summary reachable_objects;\n+\n+\tstruct survey_report_object_size_summary *by_type;\n };\n \n+#define REPORT_TYPE_COMMIT 0\n+#define REPORT_TYPE_TREE 1\n+#define REPORT_TYPE_BLOB 2\n+#define REPORT_TYPE_COUNT 3\n+\n struct survey_context {\n \t/* Options that control what is done. */\n \tstruct survey_opts opts;\n@@ -282,12 +302,41 @@ static void survey_report_plaintext_reachable_object_summary(struct survey_conte\n \tclear_table(&table);\n }\n \n+static void survey_report_object_sizes(const char *title,\n+\t\t\t\t const char *categories,\n+\t\t\t\t struct survey_report_object_size_summary *summary,\n+\t\t\t\t size_t summary_nr)\n+{\n+\tstruct survey_table table = SURVEY_TABLE_INIT;\n+\ttable.table_name = title;\n+\n+\tstrvec_push(&table.header, xstrdup(categories));\n+\tstrvec_push(&table.header, xstrdup(_(\"Count\")));\n+\tstrvec_push(&table.header, xstrdup(_(\"Disk Size\")));\n+\tstrvec_push(&table.header, xstrdup(_(\"Inflated Size\")));\n+\n+\tfor (size_t i = 0; i < summary_nr; i++) {\n+\t\tinsert_table_rowv(&table, xstrdup(summary[i].label),\n+\t\t\t\t xstrfmt(\"%\"PRIuMAX, summary[i].nr),\n+\t\t\t\t xstrfmt(\"%\"PRIuMAX, summary[i].disk_size),\n+\t\t\t\t xstrfmt(\"%\"PRIuMAX, summary[i].inflated_size),\n+\t\t\t\t NULL);\n+\t}\n+\n+\tprint_table_plaintext(&table);\n+\tclear_table(&table);\n+}\n+\n static void survey_report_plaintext(struct survey_context *ctx)\n {\n \tprintf(\"GIT SURVEY for \\\"%s\\\"\\n\", ctx->repo->worktree);\n \tprintf(\"-----------------------------------------------------\\n\");\n \tsurvey_report_plaintext_refs(ctx);\n \tsurvey_report_plaintext_reachable_object_summary(ctx);\n+\tsurvey_report_object_sizes(_(\"TOTAL OBJECT SIZES BY TYPE\"),\n+\t\t\t\t _(\"Object Type\"),\n+\t\t\t\t ctx->report.by_type,\n+\t\t\t\t REPORT_TYPE_COUNT);\n }\n \n static void survey_report_json(struct survey_context *ctx)\n@@ -500,6 +549,64 @@ static void increment_object_counts(\n \t}\n }\n \n+static void increment_totals(struct survey_context *ctx,\n+\t\t\t struct oid_array *oids,\n+\t\t\t struct survey_report_object_size_summary *summary)\n+{\n+\tfor (size_t i = 0; i < oids->nr; i++) {\n+\t\tstruct object_info oi = OBJECT_INFO_INIT;\n+\t\tunsigned oi_flags = OBJECT_INFO_FOR_PREFETCH;\n+\t\tunsigned long object_length = 0;\n+\t\toff_t disk_sizep = 0;\n+\t\tenum object_type type;\n+\n+\t\toi.typep = &type;\n+\t\toi.sizep = &object_length;\n+\t\toi.disk_sizep = &disk_sizep;\n+\n+\t\tif (oid_object_info_extended(ctx->repo, &oids->oid[i],\n+\t\t\t\t\t &oi, oi_flags) < 0) {\n+\t\t\tsummary->num_missing++;\n+\t\t} else {\n+\t\t\tsummary->nr++;\n+\t\t\tsummary->disk_size += disk_sizep;\n+\t\t\tsummary->inflated_size += object_length;\n+\t\t}\n+\t}\n+}\n+\n+static void increment_object_totals(struct survey_context *ctx,\n+\t\t\t\t struct oid_array *oids,\n+\t\t\t\t enum object_type type)\n+{\n+\tstruct survey_report_object_size_summary *total;\n+\tstruct survey_report_object_size_summary summary = { 0 };\n+\n+\tincrement_totals(ctx, oids, &summary);\n+\n+\tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\t\ttotal = &ctx->report.by_type[REPORT_TYPE_COMMIT];\n+\t\tbreak;\n+\n+\tcase OBJ_TREE:\n+\t\ttotal = &ctx->report.by_type[REPORT_TYPE_TREE];\n+\t\tbreak;\n+\n+\tcase OBJ_BLOB:\n+\t\ttotal = &ctx->report.by_type[REPORT_TYPE_BLOB];\n+\t\tbreak;\n+\n+\tdefault:\n+\t\tBUG(\"No other type allowed\");\n+\t}\n+\n+\ttotal->nr += summary.nr;\n+\ttotal->disk_size += summary.disk_size;\n+\ttotal->inflated_size += summary.inflated_size;\n+\ttotal->num_missing += summary.num_missing;\n+}\n+\n static int survey_objects_path_walk_fn(const char *path,\n \t\t\t\t struct oid_array *oids,\n \t\t\t\t enum object_type type,\n@@ -509,6 +616,7 @@ static int survey_objects_path_walk_fn(const char *path,\n \n \tincrement_object_counts(&ctx->report.reachable_objects,\n \t\t\t\ttype, oids->nr);\n+\tincrement_object_totals(ctx, oids, type);\n \n \treturn 0;\n }\n@@ -567,6 +675,11 @@ static void survey_phase_objects(struct survey_context *ctx)\n \tinfo.blobs = 1;\n \tinfo.tags = 1;\n \n+\tCALLOC_ARRAY(ctx->report.by_type, REPORT_TYPE_COUNT);\n+\tctx->report.by_type[REPORT_TYPE_COMMIT].label = xstrdup(_(\"Commits\"));\n+\tctx->report.by_type[REPORT_TYPE_TREE].label = xstrdup(_(\"Trees\"));\n+\tctx->report.by_type[REPORT_TYPE_BLOB].label = xstrdup(_(\"Blobs\"));\n+\n \trepo_init_revisions(ctx->repo, &revs, \"\");\n \n \tfor (size_t i = 0; i < ctx->ref_array.nr; i++) {\ndiff --git a/t/t8100-git-survey.sh b/t/t8100-git-survey.sh\nindex 0da92eafa95..f8af9601214 100755\n--- a/t/t8100-git-survey.sh\n+++ b/t/t8100-git-survey.sh\n@@ -50,6 +50,14 @@ test_expect_success 'git survey (default)' '\n \t Commits | 10\n \t Trees | 10\n \t Blobs | 10\n+\n+\tTOTAL OBJECT SIZES BY TYPE\n+\t===============================================\n+\tObject Type | Count | Disk Size | Inflated Size\n+\t------------+-------+-----------+--------------\n+\t Commits | 10 | 1523 | 2153\n+\t Trees | 10 | 495 | 1706\n+\t Blobs | 10 | 191 | 101\n \tEOF\n \n \ttest_cmp expect out\n-- \ngitgitgadget\n\n"},{"id":"502507","messageId":"9c54c14435742927a66487df2862204aca8e6fc7.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 15/30] survey: show progress during object walk","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:40Z","receivedAt":"2024-09-10T02:29:15Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nSigned-off-by: Derrick Stolee \n---\n builtin/survey.c | 16 ++++++++++++++++\n 1 file changed, 16 insertions(+)\n\ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex 435c4bd452a..baaaf8a6374 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -618,6 +618,9 @@ static int survey_objects_path_walk_fn(const char *path,\n \t\t\t\ttype, oids->nr);\n \tincrement_object_totals(ctx, oids, type);\n \n+\tctx->progress_nr += oids->nr;\n+\tdisplay_progress(ctx->progress, ctx->progress_nr);\n+\n \treturn 0;\n }\n \n@@ -682,6 +685,11 @@ static void survey_phase_objects(struct survey_context *ctx)\n \n \trepo_init_revisions(ctx->repo, &revs, \"\");\n \n+\tctx->progress_nr = 0;\n+\tctx->progress_total = ctx->ref_array.nr;\n+\tif (ctx->opts.show_progress)\n+\t\tctx->progress = start_progress(_(\"Preparing object walk\"),\n+\t\t\t\t\t ctx->progress_total);\n \tfor (size_t i = 0; i < ctx->ref_array.nr; i++) {\n \t\tstruct ref_array_item *item = ctx->ref_array.items[i];\n \t\tstruct object_id peeled;\n@@ -709,9 +717,17 @@ static void survey_phase_objects(struct survey_context *ctx)\n \t\tdefault:\n \t\t\tbreak;\n \t\t}\n+\n+\t\tdisplay_progress(ctx->progress, ++(ctx->progress_nr));\n \t}\n+\tstop_progress(&ctx->progress);\n \n+\tctx->progress_nr = 0;\n+\tctx->progress_total = 0;\n+\tif (ctx->opts.show_progress)\n+\t\tctx->progress = start_progress(_(\"Walking objects\"), 0);\n \twalk_objects_by_path(&info);\n+\tstop_progress(&ctx->progress);\n \n \trelease_revisions(&revs);\n \ttrace2_region_leave(\"survey\", \"phase/objects\", ctx->repo);\n-- \ngitgitgadget\n\n"},{"id":"502508","messageId":"3504abb269b5229d4aaff4db9f4d694d925ac1b2.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 16/30] survey: add ability to track prioritized lists","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:41Z","receivedAt":"2024-09-10T02:29:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn future changes, we will make use of these methods. The intention is to\nkeep track of the top contributors according to some metric. We don't want\nto store all of the entries and do a sort at the end, so track a\nconstant-size table and remove rows that get pushed out depending on the\nchosen sorting algorithm.\n\nCo-authored-by: Jeff Hostetler \nSigned-off-by; Jeff Hostetler \nSigned-off-by: Derrick Stolee \n---\n builtin/survey.c | 96 ++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 96 insertions(+)\n\ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex baaaf8a6374..ad467e9a88c 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -77,6 +77,102 @@ struct survey_report_object_size_summary {\n \tsize_t num_missing;\n };\n \n+typedef int (*survey_top_size_cmp)(struct survey_report_object_size_summary *s1,\n+\t\t\t\t struct survey_report_object_size_summary *s2);\n+\n+MAYBE_UNUSED\n+static int cmp_by_nr(struct survey_report_object_size_summary *s1,\n+\t\t struct survey_report_object_size_summary *s2)\n+{\n+\tif (s1->nr < s2->nr)\n+\t\treturn -1;\n+\tif (s1->nr > s2->nr)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n+MAYBE_UNUSED\n+static int cmp_by_disk_size(struct survey_report_object_size_summary *s1,\n+\t\t\t struct survey_report_object_size_summary *s2)\n+{\n+\tif (s1->disk_size < s2->disk_size)\n+\t\treturn -1;\n+\tif (s1->disk_size > s2->disk_size)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n+MAYBE_UNUSED\n+static int cmp_by_inflated_size(struct survey_report_object_size_summary *s1,\n+\t\t\t\tstruct survey_report_object_size_summary *s2)\n+{\n+\tif (s1->inflated_size < s2->inflated_size)\n+\t\treturn -1;\n+\tif (s1->inflated_size > s2->inflated_size)\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n+/**\n+ * Store a list of \"top\" categories by some sorting function. When\n+ * inserting a new category, reorder the list and free the one that\n+ * got ejected (if any).\n+ */\n+struct survey_report_top_sizes {\n+\tconst char *name;\n+\tsurvey_top_size_cmp cmp_fn;\n+\tstruct survey_report_object_size_summary *data;\n+\tsize_t nr;\n+\tsize_t alloc;\n+};\n+\n+MAYBE_UNUSED\n+static void init_top_sizes(struct survey_report_top_sizes *top,\n+\t\t\t size_t limit, const char *name,\n+\t\t\t survey_top_size_cmp cmp)\n+{\n+\ttop->name = name;\n+\ttop->alloc = limit;\n+\ttop->nr = 0;\n+\tCALLOC_ARRAY(top->data, limit);\n+\ttop->cmp_fn = cmp;\n+}\n+\n+MAYBE_UNUSED\n+static void clear_top_sizes(struct survey_report_top_sizes *top)\n+{\n+\tfor (size_t i = 0; i < top->nr; i++)\n+\t\tfree(top->data[i].label);\n+\tfree(top->data);\n+}\n+\n+MAYBE_UNUSED\n+static void maybe_insert_into_top_size(struct survey_report_top_sizes *top,\n+\t\t\t\t struct survey_report_object_size_summary *summary)\n+{\n+\tsize_t pos = top->nr;\n+\n+\t/* Compare against list from the bottom. */\n+\twhile (pos > 0 && top->cmp_fn(&top->data[pos - 1], summary) < 0)\n+\t\tpos--;\n+\n+\t/* Not big enough! */\n+\tif (pos >= top->alloc)\n+\t\treturn;\n+\n+\t/* We need to shift the data. */\n+\tif (top->nr == top->alloc)\n+\t\tfree(top->data[top->nr - 1].label);\n+\telse\n+\t\ttop->nr++;\n+\n+\tfor (size_t i = top->nr - 1; i > pos; i--)\n+\t\tmemcpy(&top->data[i], &top->data[i - 1], sizeof(*top->data));\n+\n+\tmemcpy(&top->data[pos], summary, sizeof(*summary));\n+\ttop->data[pos].label = xstrdup(summary->label);\n+}\n+\n /**\n * This struct contains all of the information that needs to be printed\n * at the end of the exploration of the repository and its references.\n-- \ngitgitgadget\n\n"},{"id":"502509","messageId":"9e95914d393ff83054ee419b58b9db4d3560a36c.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 17/30] survey: add report of \"largest\" paths","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:42Z","receivedAt":"2024-09-10T02:29:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nSince we are already walking our reachable objects using the path-walk API,\nlet's now collect lists of the paths that contribute most to different\nmetrics. Specifically, we care about\n\n * Number of versions.\n * Total size on disk.\n * Total inflated size (no delta or zlib compression).\n\nThis information can be critical to discovering which parts of the\nrepository are causing the most growth, especially on-disk size. Different\npacking strategies might help compress data more efficiently, but the toal\ninflated size is a representation of the raw size of all snapshots of those\npaths. Even when stored efficiently on disk, that size represents how much\ninformation must be processed to complete a command such as 'git blame'.\n\nSince the on-disk size is likely to be fragile, stop testing the exact\noutput of 'git survey' and check that the correct set of headers is\noutput.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/survey.c | 90 +++++++++++++++++++++++++++++++++++++------\n t/t8100-git-survey.sh | 12 +++++-\n 2 files changed, 90 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin/survey.c b/builtin/survey.c\nindex ad467e9a88c..90b041967c8 100644\n--- a/builtin/survey.c\n+++ b/builtin/survey.c\n@@ -80,7 +80,6 @@ struct survey_report_object_size_summary {\n typedef int (*survey_top_size_cmp)(struct survey_report_object_size_summary *s1,\n \t\t\t\t struct survey_report_object_size_summary *s2);\n \n-MAYBE_UNUSED\n static int cmp_by_nr(struct survey_report_object_size_summary *s1,\n \t\t struct survey_report_object_size_summary *s2)\n {\n@@ -91,7 +90,6 @@ static int cmp_by_nr(struct survey_report_object_size_summary *s1,\n \treturn 0;\n }\n \n-MAYBE_UNUSED\n static int cmp_by_disk_size(struct survey_report_object_size_summary *s1,\n \t\t\t struct survey_report_object_size_summary *s2)\n {\n@@ -102,7 +100,6 @@ static int cmp_by_disk_size(struct survey_report_object_size_summary *s1,\n \treturn 0;\n }\n \n-MAYBE_UNUSED\n static int cmp_by_inflated_size(struct survey_report_object_size_summary *s1,\n \t\t\t\tstruct survey_report_object_size_summary *s2)\n {\n@@ -126,7 +123,6 @@ struct survey_report_top_sizes {\n \tsize_t alloc;\n };\n \n-MAYBE_UNUSED\n static void init_top_sizes(struct survey_report_top_sizes *top,\n \t\t\t size_t limit, const char *name,\n \t\t\t survey_top_size_cmp cmp)\n@@ -146,7 +142,6 @@ static void clear_top_sizes(struct survey_report_top_sizes *top)\n \tfree(top->data);\n }\n \n-MAYBE_UNUSED\n static void maybe_insert_into_top_size(struct survey_report_top_sizes *top,\n \t\t\t\t struct survey_report_object_size_summary *summary)\n {\n@@ -182,6 +177,10 @@ struct survey_report {\n \tstruct survey_report_object_summary reachable_objects;\n \n \tstruct survey_report_object_size_summary *by_type;\n+\n+\tstruct survey_report_top_sizes *top_paths_by_count;\n+\tstruct survey_report_top_sizes *top_paths_by_disk;\n+\tstruct survey_report_top_sizes *top_paths_by_inflate;\n };\n \n #define REPORT_TYPE_COMMIT 0\n@@ -423,6 +422,13 @@ static void survey_report_object_sizes(const char *title,\n \tclear_table(&table);\n }\n \n+static void survey_report_plaintext_sorted_size(\n+\t\tstruct survey_report_top_sizes *top)\n+{\n+\tsurvey_report_object_sizes(top->name, _(\"Path\"),\n+\t\t\t\t top->data, top->nr);\n+}\n+\n static void survey_report_plaintext(struct survey_context *ctx)\n {\n \tprintf(\"GIT SURVEY for \\\"%s\\\"\\n\", ctx->repo->worktree);\n@@ -433,6 +439,21 @@ static void survey_report_plaintext(struct survey_context *ctx)\n \t\t\t\t _(\"Object Type\"),\n \t\t\t\t ctx->report.by_type,\n \t\t\t\t REPORT_TYPE_COUNT);\n+\n+\tsurvey_report_plaintext_sorted_size(\n+\t\t&ctx->report.top_paths_by_count[REPORT_TYPE_TREE]);\n+\tsurvey_report_plaintext_sorted_size(\n+\t\t&ctx->report.top_paths_by_count[REPORT_TYPE_BLOB]);\n+\n+\tsurvey_report_plaintext_sorted_size(\n+\t\t&ctx->report.top_paths_by_disk[REPORT_TYPE_TREE]);\n+\tsurvey_report_plaintext_sorted_size(\n+\t\t&ctx->report.top_paths_by_disk[REPORT_TYPE_BLOB]);\n+\n+\tsurvey_report_plaintext_sorted_size(\n+\t\t&ctx->report.top_paths_by_inflate[REPORT_TYPE_TREE]);\n+\tsurvey_report_plaintext_sorted_size(\n+\t\t&ctx->report.top_paths_by_inflate[REPORT_TYPE_BLOB]);\n }\n \n static void survey_report_json(struct survey_context *ctx)\n@@ -673,7 +694,8 @@ static void increment_totals(struct survey_context *ctx,\n \n static void increment_object_totals(struct survey_context *ctx,\n \t\t\t\t struct oid_array *oids,\n-\t\t\t\t enum object_type type)\n+\t\t\t\t enum object_type type,\n+\t\t\t\t const char *path)\n {\n \tstruct survey_report_object_size_summary *total;\n \tstruct survey_report_object_size_summary summary = { 0 };\n@@ -701,6 +723,27 @@ static void increment_object_totals(struct survey_context *ctx,\n \ttotal->disk_size += summary.disk_size;\n \ttotal->inflated_size += summary.inflated_size;\n \ttotal->num_missing += summary.num_missing;\n+\n+\tif (type == OBJ_TREE || type == OBJ_BLOB) {\n+\t\tint index = type == OBJ_TREE ?\n+\t\t\t REPORT_TYPE_TREE : REPORT_TYPE_BLOB;\n+\t\tstruct survey_report_top_sizes *top;\n+\n+\t\t/*\n+\t\t * Temporarily store (const char *) here, but it will\n+\t\t * be duped if inserted and will not be freed.\n+\t\t */\n+\t\tsummary.label = (char *)path;\n+\n+\t\ttop = ctx->report.top_paths_by_count;\n+\t\tmaybe_insert_into_top_size(&top[index], &summary);\n+\n+\t\ttop = ctx->report.top_paths_by_disk;\n+\t\tmaybe_insert_into_top_size(&top[index], &summary);\n+\n+\t\ttop = ctx->report.top_paths_by_inflate;\n+\t\tmaybe_insert_into_top_size(&top[index], &summary);\n+\t}\n }\n \n static int survey_objects_path_walk_fn(const char *path,\n@@ -712,7 +755,7 @@ static int survey_objects_path_walk_fn(const char *path,\n \n \tincrement_object_counts(&ctx->report.reachable_objects,\n \t\t\t\ttype, oids->nr);\n-\tincrement_object_totals(ctx, oids, type);\n+\tincrement_object_totals(ctx, oids, type, path);\n \n \tctx->progress_nr += oids->nr;\n \tdisplay_progress(ctx->progress, ctx->progress_nr);\n@@ -757,6 +800,34 @@ static int iterate_tag_chain(struct survey_context *ctx,\n \treturn -1;\n }\n \n+static void initialize_report(struct survey_context *ctx)\n+{\n+\tconst int top_limit = 100;\n+\n+\tCALLOC_ARRAY(ctx->report.by_type, REPORT_TYPE_COUNT);\n+\tctx->report.by_type[REPORT_TYPE_COMMIT].label = xstrdup(_(\"Commits\"));\n+\tctx->report.by_type[REPORT_TYPE_TREE].label = xstrdup(_(\"Trees\"));\n+\tctx->report.by_type[REPORT_TYPE_BLOB].label = xstrdup(_(\"Blobs\"));\n+\n+\tCALLOC_ARRAY(ctx->report.top_paths_by_count, REPORT_TYPE_COUNT);\n+\tinit_top_sizes(&ctx->report.top_paths_by_count[REPORT_TYPE_TREE],\n+\t\t top_limit, _(\"TOP DIRECTORIES BY COUNT\"), cmp_by_nr);\n+\tinit_top_sizes(&ctx->report.top_paths_by_count[REPORT_TYPE_BLOB],\n+\t\t top_limit, _(\"TOP FILES BY COUNT\"), cmp_by_nr);\n+\n+\tCALLOC_ARRAY(ctx->report.top_paths_by_disk, REPORT_TYPE_COUNT);\n+\tinit_top_sizes(&ctx->report.top_paths_by_disk[REPORT_TYPE_TREE],\n+\t\t top_limit, _(\"TOP DIRECTORIES BY DISK SIZE\"), cmp_by_disk_size);\n+\tinit_top_sizes(&ctx->report.top_paths_by_disk[REPORT_TYPE_BLOB],\n+\t\t top_limit, _(\"TOP FILES BY DISK SIZE\"), cmp_by_disk_size);\n+\n+\tCALLOC_ARRAY(ctx->report.top_paths_by_inflate, REPORT_TYPE_COUNT);\n+\tinit_top_sizes(&ctx->report.top_paths_by_inflate[REPORT_TYPE_TREE],\n+\t\t top_limit, _(\"TOP DIRECTORIES BY INFLATED SIZE\"), cmp_by_inflated_size);\n+\tinit_top_sizes(&ctx->report.top_paths_by_inflate[REPORT_TYPE_BLOB],\n+\t\t top_limit, _(\"TOP FILES BY INFLATED SIZE\"), cmp_by_inflated_size);\n+}\n+\n static void survey_phase_objects(struct survey_context *ctx)\n {\n \tstruct rev_info revs = REV_INFO_INIT;\n@@ -774,10 +845,7 @@ static void survey_phase_objects(struct survey_context *ctx)\n \tinfo.blobs = 1;\n \tinfo.tags = 1;\n \n-\tCALLOC_ARRAY(ctx->report.by_type, REPORT_TYPE_COUNT);\n-\tctx->report.by_type[REPORT_TYPE_COMMIT].label = xstrdup(_(\"Commits\"));\n-\tctx->report.by_type[REPORT_TYPE_TREE].label = xstrdup(_(\"Trees\"));\n-\tctx->report.by_type[REPORT_TYPE_BLOB].label = xstrdup(_(\"Blobs\"));\n+\tinitialize_report(ctx);\n \n \trepo_init_revisions(ctx->repo, &revs, \"\");\n \ndiff --git a/t/t8100-git-survey.sh b/t/t8100-git-survey.sh\nindex f8af9601214..c2dab0033f9 100755\n--- a/t/t8100-git-survey.sh\n+++ b/t/t8100-git-survey.sh\n@@ -60,7 +60,17 @@ test_expect_success 'git survey (default)' '\n \t Blobs | 10 | 191 | 101\n \tEOF\n \n-\ttest_cmp expect out\n+\tlines=$(wc -l out-trimmed &&\n+\ttest_cmp expect out-trimmed &&\n+\n+\tfor type in \"DIRECTORIES\" \"FILES\"\n+\tdo\n+\t\tfor metric in \"COUNT\" \"DISK SIZE\" \"INFLATED SIZE\"\n+\t\tdo\n+\t\t\tgrep \"TOP $type BY $metric\" out || return 1\n+\t\tdone || return 1\n+\tdone\n '\n \n test_done\n-- \ngitgitgadget\n\n"},{"id":"502510","messageId":"98a854c4b542309269f56ba0ae8b9a7c1504e409.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 18/30] revision: create mark_trees_uninteresting_dense()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:43Z","receivedAt":"2024-09-10T02:29:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe sparse tree walk algorithm was created in d5d2e93577e (revision:\nimplement sparse algorithm, 2019-01-16) and involves using the\nmark_trees_uninteresting_sparse() method. This method takes a repository\nand an oidset of tree IDs, some of which have the UNINTERESTING flag and\nsome of which do not.\n\nCreate a method that has an equivalent set of preconditions but uses a\n\"dense\" walk (recursively visits all reachable trees, as long as they\nhave not previously been marked UNINTERESTING). This is an important\ndifference from mark_tree_uninteresting(), which short-circuits if the\ngiven tree has the UNINTERESTING flag.\n\nA use of this method will be added in a later change, with a condition\nset whether the sparse or dense approach should be used.\n\nSigned-off-by: Derrick Stolee \n---\n revision.c | 15 +++++++++++++++\n revision.h | 1 +\n 2 files changed, 16 insertions(+)\n\ndiff --git a/revision.c b/revision.c\nindex ac94f8d4292..21c8b6d1bc0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -219,6 +219,21 @@ static void add_children_by_path(struct repository *r,\n \tfree_tree_buffer(tree);\n }\n \n+void mark_trees_uninteresting_dense(struct repository *r,\n+\t\t\t\t struct oidset *trees)\n+{\n+\tstruct object_id *oid;\n+\tstruct oidset_iter iter;\n+\n+\toidset_iter_init(trees, &iter);\n+\twhile ((oid = oidset_iter_next(&iter))) {\n+\t\tstruct tree *tree = lookup_tree(r, oid);\n+\n+\t\tif (tree->object.flags & UNINTERESTING)\n+\t\t\tmark_tree_contents_uninteresting(r, tree);\n+\t}\n+}\n+\n void mark_trees_uninteresting_sparse(struct repository *r,\n \t\t\t\t struct oidset *trees)\n {\ndiff --git a/revision.h b/revision.h\nindex 0e470d1df19..6c3df8e42bf 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -487,6 +487,7 @@ void put_revision_mark(const struct rev_info *revs,\n \n void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit);\n void mark_tree_uninteresting(struct repository *r, struct tree *tree);\n+void mark_trees_uninteresting_dense(struct repository *r, struct oidset *trees);\n void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees);\n \n void show_object_with_name(FILE *, struct object *, const char *);\n-- \ngitgitgadget\n\n"},{"id":"502511","messageId":"78168d98bfc0df7151eac5280e12b95c9fb694ec.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 19/30] path-walk: add prune_all_uninteresting option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:44Z","receivedAt":"2024-09-10T02:29:18Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis option causes the path-walk API to act like the sparse tree-walk\nalgorithm implemented by mark_trees_uninteresting_sparse() in\nlist-objects.c.\n\nStarting from the commits marked as UNINTERESTING, their root trees and\nall objects reachable from those trees are UNINTERSTING, at least as we\nwalk path-by-path. When we reach a path where all objects associated\nwith that path are marked UNINTERESTING, then do no continue walking the\nchildren of that path.\n\nWe need to be careful to pass the UNINTERESTING flag in a deep way on\nthe UNINTERESTING objects before we start the path-walk, or else the\ndepth-first search for the path-walk API may accidentally report some\nobjects as interesting.\n\nSigned-off-by: Derrick Stolee \n---\n path-walk.c | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++---\n path-walk.h | 8 +++++++\n 2 files changed, 73 insertions(+), 3 deletions(-)\n\ndiff --git a/path-walk.c b/path-walk.c\nindex 65f9856afa2..08de29614f7 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -23,6 +23,7 @@ struct type_and_oid_list\n {\n \tenum object_type type;\n \tstruct oid_array oids;\n+\tint maybe_interesting;\n };\n \n #define TYPE_AND_OID_LIST_INIT { \\\n@@ -139,6 +140,9 @@ static int add_children(struct path_walk_context *ctx,\n \t\t\tlist->type = type;\n \t\t\tstrmap_put(&ctx->paths_to_lists, path.buf, list);\n \t\t\tstring_list_append(&ctx->path_stack, path.buf);\n+\n+\t\t\tif (!(o->flags & UNINTERESTING))\n+\t\t\t\tlist->maybe_interesting = 1;\n \t\t}\n \t\toid_array_append(&list->oids, &entry.oid);\n \t}\n@@ -161,6 +165,40 @@ static int walk_path(struct path_walk_context *ctx,\n \n \tlist = strmap_get(&ctx->paths_to_lists, path);\n \n+\tif (ctx->info->prune_all_uninteresting) {\n+\t\t/*\n+\t\t * This is true if all objects were UNINTERESTING\n+\t\t * when added to the list.\n+\t\t */\n+\t\tif (!list->maybe_interesting)\n+\t\t\treturn 0;\n+\n+\t\t/*\n+\t\t * But it's still possible that the objects were set\n+\t\t * as UNINTERESTING after being added. Do a quick check.\n+\t\t */\n+\t\tlist->maybe_interesting = 0;\n+\t\tfor (size_t i = 0;\n+\t\t !list->maybe_interesting && i < list->oids.nr;\n+\t\t i++) {\n+\t\t\tif (list->type == OBJ_TREE) {\n+\t\t\t\tstruct tree *t = lookup_tree(ctx->repo,\n+\t\t\t\t\t\t\t &list->oids.oid[i]);\n+\t\t\t\tif (t && !(t->object.flags & UNINTERESTING))\n+\t\t\t\t\tlist->maybe_interesting = 1;\n+\t\t\t} else {\n+\t\t\t\tstruct blob *b = lookup_blob(ctx->repo,\n+\t\t\t\t\t\t\t &list->oids.oid[i]);\n+\t\t\t\tif (b && !(b->object.flags & UNINTERESTING))\n+\t\t\t\t\tlist->maybe_interesting = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* We have confirmed that all objects are UNINTERESTING. */\n+\t\tif (!list->maybe_interesting)\n+\t\t\treturn 0;\n+\t}\n+\n \t/* Evaluate function pointer on this data, if requested. */\n \tif ((list->type == OBJ_TREE && ctx->info->trees) ||\n \t (list->type == OBJ_BLOB && ctx->info->blobs))\n@@ -203,7 +241,7 @@ static void clear_strmap(struct strmap *map)\n int walk_objects_by_path(struct path_walk_info *info)\n {\n \tconst char *root_path = \"\";\n-\tint ret = 0;\n+\tint ret = 0, has_uninteresting = 0;\n \tsize_t commits_nr = 0, paths_nr = 0;\n \tstruct commit *c;\n \tstruct type_and_oid_list *root_tree_list;\n@@ -215,6 +253,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t\t.path_stack = STRING_LIST_INIT_DUP,\n \t\t.paths_to_lists = STRMAP_INIT\n \t};\n+\tstruct oidset root_tree_set = OIDSET_INIT;\n \n \tstruct oid_array tagged_tree_list = OID_ARRAY_INIT;\n \tstruct oid_array tagged_blob_list = OID_ARRAY_INIT;\n@@ -227,7 +266,9 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t/* Insert a single list for the root tree into the paths. */\n \tCALLOC_ARRAY(root_tree_list, 1);\n \troot_tree_list->type = OBJ_TREE;\n+\troot_tree_list->maybe_interesting = 1;\n \tstrmap_put(&ctx.paths_to_lists, root_path, root_tree_list);\n+\n \tif (prepare_revision_walk(info->revs))\n \t\tdie(_(\"failed to setup revision walk\"));\n \n@@ -247,11 +288,17 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t\toid = get_commit_tree_oid(c);\n \t\tt = lookup_tree(info->revs->repo, oid);\n \n-\t\tif (t)\n+\t\tif (t) {\n+\t\t\toidset_insert(&root_tree_set, oid);\n \t\t\toid_array_append(&root_tree_list->oids, oid);\n-\t\telse\n+\t\t} else {\n \t\t\twarning(\"could not find tree %s\", oid_to_hex(oid));\n+\t\t}\n \n+\t\tif (t && (c->object.flags & UNINTERESTING)) {\n+\t\t\tt->object.flags |= UNINTERESTING;\n+\t\t\thas_uninteresting = 1;\n+\t\t}\n \t}\n \n \ttrace2_data_intmax(\"path-walk\", ctx.repo, \"commits\", commits_nr);\n@@ -318,6 +365,21 @@ int walk_objects_by_path(struct path_walk_info *info)\n \t\toid_array_clear(&tagged_blob_list);\n \t}\n \n+\t/*\n+\t * Before performing a DFS of our paths and emitting them as interesting,\n+\t * do a full walk of the trees to distribute the UNINTERESTING bit. Use\n+\t * the sparse algorithm if prune_all_uninteresting was set.\n+\t */\n+\tif (has_uninteresting) {\n+\t\ttrace2_region_enter(\"path-walk\", \"uninteresting-walk\", info->revs->repo);\n+\t\tif (info->prune_all_uninteresting)\n+\t\t\tmark_trees_uninteresting_sparse(ctx.repo, &root_tree_set);\n+\t\telse\n+\t\t\tmark_trees_uninteresting_dense(ctx.repo, &root_tree_set);\n+\t\ttrace2_region_leave(\"path-walk\", \"uninteresting-walk\", info->revs->repo);\n+\t}\n+\toidset_clear(&root_tree_set);\n+\n \tstring_list_append(&ctx.path_stack, root_path);\n \n \ttrace2_region_enter(\"path-walk\", \"path-walk\", info->revs->repo);\ndiff --git a/path-walk.h b/path-walk.h\nindex 637d3b0cabb..7c02bca7156 100644\n--- a/path-walk.h\n+++ b/path-walk.h\n@@ -50,6 +50,14 @@ struct path_walk_info {\n \t * the sparse-checkout patterns.\n \t */\n \tstruct pattern_list *pl;\n+\n+\t/**\n+\t * When 'prune_all_uninteresting' is set and a path has all objects\n+\t * marked as UNINTERESTING, then the path-walk will not visit those\n+\t * objects. It will not call path_fn on those objects and will not\n+\t * walk the children of such trees.\n+\t */\n+\tint prune_all_uninteresting;\n };\n \n #define PATH_WALK_INFO_INIT { \\\n-- \ngitgitgadget\n\n"},{"id":"502512","messageId":"3455af21e1bea375f38d21cc3b1d718ca6e563e4.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 20/30] pack-objects: add --path-walk option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:45Z","receivedAt":"2024-09-10T02:29:19Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn order to more easily compute delta bases among objects that appear at the\nexact same path, add a --path-walk option to 'git pack-objects'.\n\nThis option will use the path-walk API instead of the object walk given by\nthe revision machinery. Since objects will be provided in batches\nrepresenting a common path, those objects can be tested for delta bases\nimmediately instead of waiting for a sort of the full object list by\nname-hash. This has multiple benefits, including avoiding collisions by\nname-hash.\n\nThe objects marked as UNINTERESTING are included in these batches, so we\nare guaranteeing some locality to find good delta bases.\n\nAfter the individual passes are done on a per-path basis, the default\nname-hash is used to find other opportunistic delta bases that did not\nmatch exactly by the full path name.\n\nRFC TODO: It is important to note that this option is inherently\nincompatible with using a bitmap index. This walk probably also does not\nwork with other advanced features, such as delta islands.\n\nGetting ahead of myself, this option compares well with --full-name-hash\nwhen the packfile is large enough, but also performs at least as well as\nthe default in all cases that I've seen.\n\nRFC TODO: this should probably be recording the batch locations to another\nlist so they could be processed in a second phase using threads.\n\nRFC TODO: list some examples of how this outperforms previous pack-objects\nstrategies. (This is coming in later commits that include performance\ntest changes.)\n\nSigned-off-by: Derrick Stolee \n---\n builtin/pack-objects.c | 209 ++++++++++++++++++++++++++++++++++-------\n path-walk.c | 2 +-\n 2 files changed, 177 insertions(+), 34 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 778be80f564..3d0bb33427d 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -39,6 +39,9 @@\n #include \"promisor-remote.h\"\n #include \"pack-mtimes.h\"\n #include \"parse-options.h\"\n+#include \"blob.h\"\n+#include \"tree.h\"\n+#include \"path-walk.h\"\n \n /*\n * Objects we are going to pack are collected in the `to_pack` structure.\n@@ -215,6 +218,7 @@ static int delta_search_threads;\n static int pack_to_stdout;\n static int sparse;\n static int thin;\n+static int path_walk;\n static int num_preferred_base;\n static struct progress *progress_state;\n \n@@ -3139,6 +3143,38 @@ static int add_ref_tag(const char *tag UNUSED, const char *referent UNUSED, cons\n \treturn 0;\n }\n \n+static int should_attempt_deltas(struct object_entry *entry)\n+{\n+\tif (DELTA(entry))\n+\t\t/* This happens if we decided to reuse existing\n+\t\t * delta from a pack. \"reuse_delta &&\" is implied.\n+\t\t */\n+\t\treturn 0;\n+\n+\tif (!entry->type_valid ||\n+\t\toe_size_less_than(&to_pack, entry, 50))\n+\t\treturn 0;\n+\n+\tif (entry->no_try_delta)\n+\t\treturn 0;\n+\n+\tif (!entry->preferred_base) {\n+\t\tif (oe_type(entry) < 0)\n+\t\t\tdie(_(\"unable to get type of object %s\"),\n+\t\t\t\toid_to_hex(&entry->idx.oid));\n+\t} else {\n+\t\tif (oe_type(entry) < 0) {\n+\t\t\t/*\n+\t\t\t * This object is not found, but we\n+\t\t\t * don't have to include it anyway.\n+\t\t\t */\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\n+\treturn 1;\n+}\n+\n static void prepare_pack(int window, int depth)\n {\n \tstruct object_entry **delta_list;\n@@ -3169,33 +3205,11 @@ static void prepare_pack(int window, int depth)\n \tfor (i = 0; i < to_pack.nr_objects; i++) {\n \t\tstruct object_entry *entry = to_pack.objects + i;\n \n-\t\tif (DELTA(entry))\n-\t\t\t/* This happens if we decided to reuse existing\n-\t\t\t * delta from a pack. \"reuse_delta &&\" is implied.\n-\t\t\t */\n+\t\tif (!should_attempt_deltas(entry))\n \t\t\tcontinue;\n \n-\t\tif (!entry->type_valid ||\n-\t\t oe_size_less_than(&to_pack, entry, 50))\n-\t\t\tcontinue;\n-\n-\t\tif (entry->no_try_delta)\n-\t\t\tcontinue;\n-\n-\t\tif (!entry->preferred_base) {\n+\t\tif (!entry->preferred_base)\n \t\t\tnr_deltas++;\n-\t\t\tif (oe_type(entry) < 0)\n-\t\t\t\tdie(_(\"unable to get type of object %s\"),\n-\t\t\t\t oid_to_hex(&entry->idx.oid));\n-\t\t} else {\n-\t\t\tif (oe_type(entry) < 0) {\n-\t\t\t\t/*\n-\t\t\t\t * This object is not found, but we\n-\t\t\t\t * don't have to include it anyway.\n-\t\t\t\t */\n-\t\t\t\tcontinue;\n-\t\t\t}\n-\t\t}\n \n \t\tdelta_list[n++] = entry;\n \t}\n@@ -4110,6 +4124,117 @@ static void mark_bitmap_preferred_tips(void)\n \t}\n }\n \n+static inline int is_oid_interesting(struct repository *repo,\n+\t\t\t\t struct object_id *oid,\n+\t\t\t\t enum object_type type)\n+{\n+\tif (type == OBJ_TAG) {\n+\t\tstruct tag *t = lookup_tag(repo, oid);\n+\t\treturn t && !(t->object.flags & UNINTERESTING);\n+\t}\n+\n+\tif (type == OBJ_COMMIT) {\n+\t\tstruct commit *c = lookup_commit(repo, oid);\n+\t\treturn c && !(c->object.flags & UNINTERESTING);\n+\t}\n+\n+\tif (type == OBJ_TREE) {\n+\t\tstruct tree *t = lookup_tree(repo, oid);\n+\t\treturn t && !(t->object.flags & UNINTERESTING);\n+\t}\n+\n+\tif (type == OBJ_BLOB) {\n+\t\tstruct blob *b = lookup_blob(repo, oid);\n+\t\treturn b && !(b->object.flags & UNINTERESTING);\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int add_objects_by_path(const char *path,\n+\t\t\t struct oid_array *oids,\n+\t\t\t enum object_type type,\n+\t\t\t void *data)\n+{\n+\tstruct object_entry **delta_list;\n+\tsize_t oe_start = to_pack.nr_objects;\n+\tsize_t oe_end;\n+\tunsigned int sub_list_size;\n+\tunsigned int *processed = data;\n+\n+\t/*\n+\t * First, add all objects to the packing data, including the ones\n+\t * marked UNINTERESTING (translated to 'exclude') as they can be\n+\t * used as delta bases.\n+\t */\n+\tfor (size_t i = 0; i < oids->nr; i++) {\n+\t\tstruct object_id *oid = &oids->oid[i];\n+\t\tint exclude = !is_oid_interesting(the_repository, oid, type);\n+\t\tadd_object_entry(oid, type, path, exclude);\n+\t}\n+\n+\toe_end = to_pack.nr_objects;\n+\n+\t/* We can skip delta calculations if it is a no-op. */\n+\tif (oe_end == oe_start || !window)\n+\t\treturn 0;\n+\n+\tsub_list_size = 0;\n+\tALLOC_ARRAY(delta_list, oe_end - oe_start);\n+\n+\tfor (size_t i = 0; i < oe_end - oe_start; i++) {\n+\t\tstruct object_entry *entry = to_pack.objects + oe_start + i;\n+\n+\t\tif (!should_attempt_deltas(entry))\n+\t\t\tcontinue;\n+\n+\t\tdelta_list[sub_list_size++] = entry;\n+\t}\n+\n+\t/*\n+\t * Find delta bases among this list of objects that all match the same\n+\t * path. This causes the delta compression to be interleaved in the\n+\t * object walk, which can lead to confusing progress indicators. This is\n+\t * also incompatible with threaded delta calculations. In the future,\n+\t * consider creating a list of regions in the full to_pack.objects array\n+\t * that could be picked up by the threaded delta computation.\n+\t */\n+\tif (sub_list_size && window) {\n+\t\tQSORT(delta_list, sub_list_size, type_size_sort);\n+\t\tfind_deltas(delta_list, &sub_list_size, window, depth, processed);\n+\t}\n+\n+\tfree(delta_list);\n+\treturn 0;\n+}\n+\n+static void get_object_list_path_walk(struct rev_info *revs)\n+{\n+\tstruct path_walk_info info = PATH_WALK_INFO_INIT;\n+\tunsigned int processed = 0;\n+\n+\tinfo.revs = revs;\n+\n+\tinfo.revs->tag_objects = 1;\n+\tinfo.tags = 1;\n+\tinfo.commits = 1;\n+\tinfo.trees = 1;\n+\tinfo.blobs = 1;\n+\tinfo.path_fn = add_objects_by_path;\n+\tinfo.path_fn_data = &processed;\n+\n+\t/*\n+\t * Allow the --[no-]sparse option to be interesting here, if only\n+\t * for testing purposes. Paths with no interesting objects will not\n+\t * contribute to the resulting pack, but only create noisy preferred\n+\t * base objects.\n+\t */\n+\tinfo.prune_all_uninteresting = sparse;\n+\n+\tif (walk_objects_by_path(&info))\n+\t\tdie(_(\"failed to pack objects via path-walk\"));\n+}\n+\n static void get_object_list(struct rev_info *revs, int ac, const char **av)\n {\n \tstruct setup_revision_opt s_r_opt = {\n@@ -4156,7 +4281,7 @@ static void get_object_list(struct rev_info *revs, int ac, const char **av)\n \n \twarn_on_object_refname_ambiguity = save_warning;\n \n-\tif (use_bitmap_index && !get_object_list_from_bitmap(revs))\n+\tif (use_bitmap_index && !path_walk && !get_object_list_from_bitmap(revs))\n \t\treturn;\n \n \tif (use_delta_islands)\n@@ -4165,15 +4290,19 @@ static void get_object_list(struct rev_info *revs, int ac, const char **av)\n \tif (write_bitmap_index)\n \t\tmark_bitmap_preferred_tips();\n \n-\tif (prepare_revision_walk(revs))\n-\t\tdie(_(\"revision walk setup failed\"));\n-\tmark_edges_uninteresting(revs, show_edge, sparse);\n-\n \tif (!fn_show_object)\n \t\tfn_show_object = show_object;\n-\ttraverse_commit_list(revs,\n-\t\t\t show_commit, fn_show_object,\n-\t\t\t NULL);\n+\n+\tif (path_walk) {\n+\t\tget_object_list_path_walk(revs);\n+\t} else {\n+\t\tif (prepare_revision_walk(revs))\n+\t\t\tdie(_(\"revision walk setup failed\"));\n+\t\tmark_edges_uninteresting(revs, show_edge, sparse);\n+\t\ttraverse_commit_list(revs,\n+\t\t\t\tshow_commit, fn_show_object,\n+\t\t\t\tNULL);\n+\t}\n \n \tif (unpack_unreachable_expiration) {\n \t\trevs->ignore_missing_links = 1;\n@@ -4368,6 +4497,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\t N_(\"use the sparse reachability algorithm\")),\n \t\tOPT_BOOL(0, \"thin\", &thin,\n \t\t\t N_(\"create thin packs\")),\n+\t\tOPT_BOOL(0, \"path-walk\", &path_walk,\n+\t\t\t N_(\"use the path-walk API to walk objects when possible\")),\n \t\tOPT_BOOL(0, \"shallow\", &shallow,\n \t\t\t N_(\"create packs suitable for shallow fetches\")),\n \t\tOPT_BOOL(0, \"honor-pack-keep\", &ignore_packed_keep_on_disk,\n@@ -4448,7 +4579,19 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\twindow = 0;\n \n \tstrvec_push(&rp, \"pack-objects\");\n-\tif (thin) {\n+\n+\tif (path_walk && filter_options.choice) {\n+\t\twarning(_(\"cannot use --filter with --path-walk\"));\n+\t\tpath_walk = 0;\n+\t}\n+\tif (path_walk) {\n+\t\tstrvec_push(&rp, \"--boundary\");\n+\t\t /*\n+\t\t * We must disable the bitmaps because we are removing\n+\t\t * the --objects / --objects-edge[-aggressive] options.\n+\t\t */\n+\t\tuse_bitmap_index = 0;\n+\t} else if (thin) {\n \t\tuse_internal_rev_list = 1;\n \t\tstrvec_push(&rp, shallow\n \t\t\t\t? \"--objects-edge-aggressive\"\ndiff --git a/path-walk.c b/path-walk.c\nindex 08de29614f7..9391e0579ae 100644\n--- a/path-walk.c\n+++ b/path-walk.c\n@@ -306,7 +306,7 @@ int walk_objects_by_path(struct path_walk_info *info)\n \n \t/* Track all commits. */\n \tif (info->commits)\n-\t\tret = info->path_fn(\"\", &commit_list->oids, OBJ_COMMIT,\n+\t\tret = info->path_fn(\"initial\", &commit_list->oids, OBJ_COMMIT,\n \t\t\t\t info->path_fn_data);\n \toid_array_clear(&commit_list->oids);\n \tfree(commit_list);\n-- \ngitgitgadget\n\n"},{"id":"502513","messageId":"502008bb7c57327bad65867a70871ef0cf8898b5.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 21/30] pack-objects: extract should_attempt_deltas()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:46Z","receivedAt":"2024-09-10T02:29:20Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nSigned-off-by: Derrick Stolee \n---\n builtin/pack-objects.c | 17 +++++++----------\n 1 file changed, 7 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 3d0bb33427d..b1d684c3417 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3151,8 +3151,7 @@ static int should_attempt_deltas(struct object_entry *entry)\n \t\t */\n \t\treturn 0;\n \n-\tif (!entry->type_valid ||\n-\t\toe_size_less_than(&to_pack, entry, 50))\n+\tif (!entry->type_valid || oe_size_less_than(&to_pack, entry, 50))\n \t\treturn 0;\n \n \tif (entry->no_try_delta)\n@@ -3162,14 +3161,12 @@ static int should_attempt_deltas(struct object_entry *entry)\n \t\tif (oe_type(entry) < 0)\n \t\t\tdie(_(\"unable to get type of object %s\"),\n \t\t\t\toid_to_hex(&entry->idx.oid));\n-\t} else {\n-\t\tif (oe_type(entry) < 0) {\n-\t\t\t/*\n-\t\t\t * This object is not found, but we\n-\t\t\t * don't have to include it anyway.\n-\t\t\t */\n-\t\t\treturn 0;\n-\t\t}\n+\t} else if (oe_type(entry) < 0) {\n+\t\t/*\n+\t\t * This object is not found, but we\n+\t\t * don't have to include it anyway.\n+\t\t */\n+\t\treturn 0;\n \t}\n \n \treturn 1;\n-- \ngitgitgadget\n\n"},{"id":"502514","messageId":"b52ee338d1524a938e679fdeedc04818b75fd4d5.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 22/30] pack-objects: introduce GIT_TEST_PACK_PATH_WALK","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:47Z","receivedAt":"2024-09-10T02:29:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThere are many tests that validate whether 'git pack-objects' works as\nexpected. Instead of duplicating these tests, add a new test environment\nvariable, GIT_TEST_PACK_PATH_WALK, that implies --path-walk by default\nwhen specified.\n\nThis was useful in testing the implementation of the --path-walk\nimplementation, especially in conjunction with test such as:\n\n - t5322-pack-objects-sparse.sh : This demonstrates the effectiveness of\n the --sparse option and how it combines with --path-walk.\n\nRFC TODO: list other helpful test cases, as well as the ones where the\nbehavior breaks if this is enabled...\n\nSigned-off-by: Derrick Stolee \n---\n builtin/pack-objects.c | 1 +\n t/README | 4 ++++\n 2 files changed, 5 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex b1d684c3417..b9fe1b1fbd5 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4534,6 +4534,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \n \tdisable_replace_refs();\n \n+\tpath_walk = git_env_bool(\"GIT_TEST_PACK_PATH_WALK\", 0);\n \tsparse = git_env_bool(\"GIT_TEST_PACK_SPARSE\", -1);\n \tif (the_repository->gitdir) {\n \t\tprepare_repo_settings(the_repository);\ndiff --git a/t/README b/t/README\nindex 44c02d81298..a5d7d0239e0 100644\n--- a/t/README\n+++ b/t/README\n@@ -433,6 +433,10 @@ GIT_TEST_PACK_SPARSE= if disabled will default the pack-objects\n builtin to use the non-sparse object walk. This can still be overridden by\n the --sparse command-line argument.\n \n+GIT_TEST_PACK_PATH_WALK= if enabled will default the pack-objects\n+builtin to use the path-walk API for the object walk. This can still be\n+overridden by the --no-path-walk command-line argument.\n+\n GIT_TEST_PRELOAD_INDEX= exercises the preload-index code path\n by overriding the minimum number of cache entries required per thread.\n \n-- \ngitgitgadget\n\n"},{"id":"502515","messageId":"54bd80701fb9b55910d6d8453f235872fe549fdd.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 23/30] p5313: add size comparison test","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:48Z","receivedAt":"2024-09-10T02:29:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nTo test the benefits of the new --path-walk option in 'git\npack-objects', create a performance test that times the process but also\ncompares the size of the output.\n\nAgainst the microsoft/fluentui repo [1] against a particular commit [2],\nthis has reproducible results of a similar scale:\n\nTest this tree\n---------------------------------------------------------------\n5313.2: thin pack 0.39(0.48+0.03)\n5313.3: thin pack size 1.2M\n5313.4: thin pack with --path-walk 0.09(0.07+0.01)\n5313.5: thin pack size with --path-walk 20.8K\n5313.6: big recent pack 2.13(8.29+0.26)\n5313.7: big recent pack size 17.7M\n5313.8: big recent pack with --path-walk 3.18(4.21+0.22)\n5313.9: big recent pack size with --path-walk 15.0M\n\n[1] https://github.com/microsoft/reactui\n[2] e70848ebac1cd720875bccaa3026f4a9ed700e08\n\nRFC TODO: Note that the path-walk version is slower for the big case,\nbut the delta calculation is single-threaded with the current\nimplementation! It's still faster for the small case that mimics a\ntypical push.\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p5313-pack-objects.sh | 55 ++++++++++++++++++++++++++++++++++++\n 1 file changed, 55 insertions(+)\n create mode 100755 t/perf/p5313-pack-objects.sh\n\ndiff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\nnew file mode 100755\nindex 00000000000..fdcdf188f95\n--- /dev/null\n+++ b/t/perf/p5313-pack-objects.sh\n@@ -0,0 +1,55 @@\n+#!/bin/sh\n+\n+test_description='Tests pack performance using bitmaps'\n+. ./perf-lib.sh\n+\n+GIT_TEST_PASSING_SANITIZE_LEAK=0\n+export GIT_TEST_PASSING_SANITIZE_LEAK\n+\n+test_perf_large_repo\n+\n+test_expect_success 'create rev input' '\n+\tcat >in-thin <<-EOF &&\n+\t$(git rev-parse HEAD)\n+\t^$(git rev-parse HEAD~1)\n+\tEOF\n+\t\n+\tcat >in-big-recent <<-EOF\n+\t$(git rev-parse HEAD)\n+\t^$(git rev-parse HEAD~1000)\n+\tEOF\n+'\n+\n+test_perf 'thin pack' '\n+\tgit pack-objects --thin --stdout --revs --sparse out\n+'\n+\n+test_size 'thin pack size' '\n+\twc -c out\n+'\n+\n+test_size 'thin pack size with --path-walk' '\n+\twc -c out\n+'\n+\n+test_size 'big recent pack size' '\n+\twc -c out\n+'\n+\n+test_size 'big recent pack size with --path-walk' '\n+\twc -c \n\nSince 'git pack-objects' supports a --path-walk option, allow passing it\nthrough in 'git repack'. This presents interesting testing opportunities for\ncomparing the different repacking strategies against each other.\n\nFor the microsoft/fluentui repo [1], the results are very interesting:\n\nTest this tree\n-------------------------------------------------------------------\n5313.10: full repack 97.91(663.47+2.83)\n5313.11: full repack size 449.1K\n5313.12: full repack with --path-walk 105.42(120.49+0.95)\n5313.13: full repack size with --path-walk 159.1K\n\n[1] https://github.com/microsoft/fluentui\n\nThis repo suffers from having a lot of paths that collide in the name\nhash, so examining them in groups by path leads to better deltas. Also,\nin this case, the single-threaded implementation is competitive with the\nfull repack. This is saving time diffing files that have significant\ndifferences from each other.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/repack.c | 5 +++++\n t/perf/p5313-pack-objects.sh | 20 ++++++++++++++++++++\n 2 files changed, 25 insertions(+)\n\ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 62cfa50c50f..9e39a1ea8f8 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -57,6 +57,7 @@ struct pack_objects_args {\n \tint no_reuse_object;\n \tint quiet;\n \tint local;\n+\tint path_walk;\n \tstruct list_objects_filter_options filter_options;\n };\n \n@@ -288,6 +289,8 @@ static void prepare_pack_objects(struct child_process *cmd,\n \t\tstrvec_pushf(&cmd->args, \"--no-reuse-delta\");\n \tif (args->no_reuse_object)\n \t\tstrvec_pushf(&cmd->args, \"--no-reuse-object\");\n+\tif (args->path_walk)\n+\t\tstrvec_pushf(&cmd->args, \"--path-walk\");\n \tif (args->local)\n \t\tstrvec_push(&cmd->args, \"--local\");\n \tif (args->quiet)\n@@ -1158,6 +1161,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"pass --no-reuse-delta to git-pack-objects\")),\n \t\tOPT_BOOL('F', NULL, &po_args.no_reuse_object,\n \t\t\t\tN_(\"pass --no-reuse-object to git-pack-objects\")),\n+\t\tOPT_BOOL(0, \"path-walk\", &po_args.path_walk,\n+\t\t\t\tN_(\"pass --path-walk to git-pack-objects\")),\n \t\tOPT_NEGBIT('n', NULL, &run_update_server_info,\n \t\t\t\tN_(\"do not run git-update-server-info\"), 1),\n \t\tOPT__QUIET(&po_args.quiet, N_(\"be quiet\")),\ndiff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\nindex fdcdf188f95..48fc05bb6c6 100755\n--- a/t/perf/p5313-pack-objects.sh\n+++ b/t/perf/p5313-pack-objects.sh\n@@ -52,4 +52,24 @@ test_size 'big recent pack size with --path-walk' '\n \twc -c \n\nUsers may want to enable the --path-walk option for 'git pack-objects' by\ndefault, especially underneath commands like 'git push' or 'git repack'.\n\nThis should be limited to client repositories, since the --path-walk option\ndisables bitmap walks, so would be bad to include in Git servers when\nserving fetches and clones. There is potential that it may be helpful to\nconsider when repacking the repository, to take advantage of improved deltas\nacross historical versions of the same files.\n\nMuch like how \"pack.useSparse\" was introduced and included in\n\"feature.experimental\" before being enabled by default, use the repository\nsettings infrastructure to make the new \"pack.usePathWalk\" config enabled by\n\"feature.experimental\" and \"feature.manyFiles\".\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/config/pack.txt | 8 ++++++++\n builtin/pack-objects.c | 4 +++-\n repo-settings.c | 3 +++\n repository.h | 1 +\n 4 files changed, 15 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex da527377faf..08d06271177 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -155,6 +155,14 @@ pack.useSparse::\n \tcommits contain certain types of direct renames. Default is\n \t`true`.\n \n+pack.usePathWalk::\n+\tWhen true, git will default to using the '--path-walk' option in\n+\t'git pack-objects' when the '--revs' option is present. This\n+\talgorithm groups objects by path to maximize the ability to\n+\tcompute delta chains across historical versions of the same\n+\tobject. This may disable other options, such as using bitmaps to\n+\tenumerate objects.\n+\n pack.preferBitmapTips::\n \tWhen selecting which commits will receive bitmaps, prefer a\n \tcommit at the tip of any reference that is a suffix of any value\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex b9fe1b1fbd5..e7a9d0349c3 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4534,12 +4534,14 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \n \tdisable_replace_refs();\n \n-\tpath_walk = git_env_bool(\"GIT_TEST_PACK_PATH_WALK\", 0);\n+\tpath_walk = git_env_bool(\"GIT_TEST_PACK_PATH_WALK\", -1);\n \tsparse = git_env_bool(\"GIT_TEST_PACK_SPARSE\", -1);\n \tif (the_repository->gitdir) {\n \t\tprepare_repo_settings(the_repository);\n \t\tif (sparse < 0)\n \t\t\tsparse = the_repository->settings.pack_use_sparse;\n+\t\tif (path_walk < 0)\n+\t\t\tpath_walk = the_repository->settings.pack_use_path_walk;\n \t\tif (the_repository->settings.pack_use_multi_pack_reuse)\n \t\t\tallow_pack_reuse = MULTI_PACK_REUSE;\n \t}\ndiff --git a/repo-settings.c b/repo-settings.c\nindex 2b4e68731be..d9597d84556 100644\n--- a/repo-settings.c\n+++ b/repo-settings.c\n@@ -45,11 +45,13 @@ void prepare_repo_settings(struct repository *r)\n \t\tr->settings.fetch_negotiation_algorithm = FETCH_NEGOTIATION_SKIPPING;\n \t\tr->settings.pack_use_bitmap_boundary_traversal = 1;\n \t\tr->settings.pack_use_multi_pack_reuse = 1;\n+\t\tr->settings.pack_use_path_walk = 1;\n \t}\n \tif (manyfiles) {\n \t\tr->settings.index_version = 4;\n \t\tr->settings.index_skip_hash = 1;\n \t\tr->settings.core_untracked_cache = UNTRACKED_CACHE_WRITE;\n+\t\tr->settings.pack_use_path_walk = 1;\n \t}\n \n \t/* Commit graph config or default, does not cascade (simple) */\n@@ -64,6 +66,7 @@ void prepare_repo_settings(struct repository *r)\n \n \t/* Boolean config or default, does not cascade (simple) */\n \trepo_cfg_bool(r, \"pack.usesparse\", &r->settings.pack_use_sparse, 1);\n+\trepo_cfg_bool(r, \"pack.usepathwalk\", &r->settings.pack_use_path_walk, 0);\n \trepo_cfg_bool(r, \"core.multipackindex\", &r->settings.core_multi_pack_index, 1);\n \trepo_cfg_bool(r, \"index.sparse\", &r->settings.sparse_index, 0);\n \trepo_cfg_bool(r, \"index.skiphash\", &r->settings.index_skip_hash, r->settings.index_skip_hash);\ndiff --git a/repository.h b/repository.h\nindex af6ea0a62cd..2ae9c2b1741 100644\n--- a/repository.h\n+++ b/repository.h\n@@ -62,6 +62,7 @@ struct repo_settings {\n \tenum untracked_cache_setting core_untracked_cache;\n \n \tint pack_use_sparse;\n+\tint pack_use_path_walk;\n \tenum fetch_negotiation_setting fetch_negotiation_algorithm;\n \n \tint core_multi_pack_index;\n-- \ngitgitgadget\n\n"},{"id":"502518","messageId":"4c10f859c8dcc42c4d0470a1f295fba979aca336.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 26/30] scalar: enable path-walk during push via config","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:51Z","receivedAt":"2024-09-10T02:29:23Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nRepositories registered with Scalar are expected to be client-only\nrepositories that are rather large. This means that they are more likely to\nbe good candidates for using the --path-walk option when running 'git\npack-objects', especially under the hood of 'git push'. Enable this config\nin Scalar repositories.\n\nSigned-off-by: Derrick Stolee \n---\n scalar.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/scalar.c b/scalar.c\nindex 6166a8dd4c8..031d1ac179f 100644\n--- a/scalar.c\n+++ b/scalar.c\n@@ -170,6 +170,7 @@ static int set_recommended_config(int reconfigure)\n \t\t{ \"core.autoCRLF\", \"false\" },\n \t\t{ \"core.safeCRLF\", \"false\" },\n \t\t{ \"fetch.showForcedUpdates\", \"false\" },\n+\t\t{ \"push.usePathWalk\", \"true\" },\n \t\t{ NULL, NULL },\n \t};\n \tint i;\n-- \ngitgitgadget\n\n"},{"id":"502519","messageId":"db8cc46909bae552b0b23be9b07fdb2adfa68a10.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 27/30] pack-objects: add --full-name-hash option","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:52Z","receivedAt":"2024-09-10T02:29:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nRFC NOTE: this is essentially the same as the patch introduced\nindependently of the RFC, but now is on top of the --path-walk option\ninstead. This is included in the RFC for comparison purposes.\n\nRFC NOTE: As you can see from the details below, the --full-name-hash\noption essentially attempts to do similar things as the --path-walk\noption, but sometimes misses the mark. Collisions still happen with the\n--full-name-hash option, leading to some misses. However, in cases where\nthe default name-hash algorithm has low collision rates and deltas are\nactually desired across objects with similar names but different full\nnames, the --path-walk option can still take advantage of the default\nname hash approach.\n\nHere are the new performance details simulating a single push in an\ninternal monorepo using a lot of paths that collide in the default name\nhash. We can see that --full-name-hash gets close to the --path-walk\noption's size.\n\nTest this tree\n--------------------------------------------------------------\n5313.2: thin pack 2.43(2.92+0.14)\n5313.3: thin pack size 4.5M\n5313.4: thin pack with --full-name-hash 0.31(0.49+0.12)\n5313.5: thin pack size with --full-name-hash 15.5K\n5313.6: thin pack with --path-walk 0.35(0.31+0.04)\n5313.7: thin pack size with --path-walk 14.2K\n\nHowever, when simulating pushes on repositories that do not have issues\nwith name-hash collisions, the --full-name-hash option presents a\npotential of worse delta calculations, such as this example using my\nlocal Git repository:\n\nTest this tree\n--------------------------------------------------------------\n5313.2: thin pack 0.03(0.01+0.01)\n5313.3: thin pack size 475\n5313.4: thin pack with --full-name-hash 0.02(0.01+0.01)\n5313.5: thin pack size with --full-name-hash 14.8K\n5313.6: thin pack with --path-walk 0.02(0.01+0.01)\n5313.7: thin pack size with --path-walk 475\n\nNote that the path-walk option found the same delta bases as the default\noptions in this case.\n\nIn the full repack case, the --full-name-hash option may be preferable\nbecause it interacts well with other advanced features, such as using\nbitmap indexes and tracking delta islands.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/pack-objects.c | 20 +++++++++++++++-----\n builtin/repack.c | 5 +++++\n pack-objects.h | 20 ++++++++++++++++++++\n t/perf/p5313-pack-objects.sh | 26 ++++++++++++++++++++++++++\n 4 files changed, 66 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex e7a9d0349c3..5d5a57e6b1f 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -270,6 +270,14 @@ struct configured_exclusion {\n static struct oidmap configured_exclusions;\n \n static struct oidset excluded_by_config;\n+static int use_full_name_hash;\n+\n+static inline uint32_t pack_name_hash_fn(const char *name)\n+{\n+\tif (use_full_name_hash)\n+\t\treturn pack_full_name_hash(name);\n+\treturn pack_name_hash(name);\n+}\n \n /*\n * stats\n@@ -1674,7 +1682,7 @@ static int add_object_entry(const struct object_id *oid, enum object_type type,\n \t\treturn 0;\n \t}\n \n-\tcreate_object_entry(oid, type, pack_name_hash(name),\n+\tcreate_object_entry(oid, type, pack_name_hash_fn(name),\n \t\t\t exclude, name && no_try_delta(name),\n \t\t\t found_pack, found_offset);\n \treturn 1;\n@@ -1888,7 +1896,7 @@ static void add_preferred_base_object(const char *name)\n {\n \tstruct pbase_tree *it;\n \tsize_t cmplen;\n-\tunsigned hash = pack_name_hash(name);\n+\tunsigned hash = pack_name_hash_fn(name);\n \n \tif (!num_preferred_base || check_pbase_path(hash))\n \t\treturn;\n@@ -3405,7 +3413,7 @@ static void show_object_pack_hint(struct object *object, const char *name,\n \t * here using a now in order to perhaps improve the delta selection\n \t * process.\n \t */\n-\toe->hash = pack_name_hash(name);\n+\toe->hash = pack_name_hash_fn(name);\n \toe->no_try_delta = name && no_try_delta(name);\n \n \tstdin_packs_hints_nr++;\n@@ -3555,7 +3563,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type\n \tentry = packlist_find(&to_pack, oid);\n \tif (entry) {\n \t\tif (name) {\n-\t\t\tentry->hash = pack_name_hash(name);\n+\t\t\tentry->hash = pack_name_hash_fn(name);\n \t\t\tentry->no_try_delta = no_try_delta(name);\n \t\t}\n \t} else {\n@@ -3578,7 +3586,7 @@ static void add_cruft_object_entry(const struct object_id *oid, enum object_type\n \t\t\treturn;\n \t\t}\n \n-\t\tentry = create_object_entry(oid, type, pack_name_hash(name),\n+\t\tentry = create_object_entry(oid, type, pack_name_hash_fn(name),\n \t\t\t\t\t 0, name && no_try_delta(name),\n \t\t\t\t\t pack, offset);\n \t}\n@@ -4526,6 +4534,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\tOPT_STRING_LIST(0, \"uri-protocol\", &uri_protocols,\n \t\t\t\tN_(\"protocol\"),\n \t\t\t\tN_(\"exclude any configured uploadpack.blobpackfileuri with this protocol\")),\n+\t\tOPT_BOOL(0, \"full-name-hash\", &use_full_name_hash,\n+\t\t\t N_(\"optimize delta compression across identical path names over time\")),\n \t\tOPT_END(),\n \t};\n \ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 9e39a1ea8f8..a1ab103e62d 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -58,6 +58,7 @@ struct pack_objects_args {\n \tint quiet;\n \tint local;\n \tint path_walk;\n+\tint full_name_hash;\n \tstruct list_objects_filter_options filter_options;\n };\n \n@@ -291,6 +292,8 @@ static void prepare_pack_objects(struct child_process *cmd,\n \t\tstrvec_pushf(&cmd->args, \"--no-reuse-object\");\n \tif (args->path_walk)\n \t\tstrvec_pushf(&cmd->args, \"--path-walk\");\n+\tif (args->full_name_hash)\n+\t\tstrvec_pushf(&cmd->args, \"--full-name-hash\");\n \tif (args->local)\n \t\tstrvec_push(&cmd->args, \"--local\");\n \tif (args->quiet)\n@@ -1163,6 +1166,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"pass --no-reuse-object to git-pack-objects\")),\n \t\tOPT_BOOL(0, \"path-walk\", &po_args.path_walk,\n \t\t\t\tN_(\"pass --path-walk to git-pack-objects\")),\n+\t\tOPT_BOOL(0, \"full-name-hash\", &po_args.full_name_hash,\n+\t\t\t\tN_(\"pass --full-name-hash to git-pack-objects\")),\n \t\tOPT_NEGBIT('n', NULL, &run_update_server_info,\n \t\t\t\tN_(\"do not run git-update-server-info\"), 1),\n \t\tOPT__QUIET(&po_args.quiet, N_(\"be quiet\")),\ndiff --git a/pack-objects.h b/pack-objects.h\nindex b9898a4e64b..50097552d03 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -207,6 +207,26 @@ static inline uint32_t pack_name_hash(const char *name)\n \treturn hash;\n }\n \n+static inline uint32_t pack_full_name_hash(const char *name)\n+{\n+\tconst uint32_t bigp = 1234572167U;\n+\tuint32_t c, hash = bigp;\n+\n+\tif (!name)\n+\t\treturn 0;\n+\n+\t/*\n+\t * Just do the dumbest thing possible: add random multiples of a\n+\t * large prime number with a binary shift. Goal is not cryptographic,\n+\t * but generally uniformly distributed.\n+\t */\n+\twhile ((c = *name++) != 0) {\n+\t\thash += c * bigp;\n+\t\thash = (hash >> 5) | (hash << 27);\n+\t}\n+\treturn hash;\n+}\n+\n static inline enum object_type oe_type(const struct object_entry *e)\n {\n \treturn e->type_valid ? e->type_ : OBJ_BAD;\ndiff --git a/t/perf/p5313-pack-objects.sh b/t/perf/p5313-pack-objects.sh\nindex 48fc05bb6c6..b3b7fff8abf 100755\n--- a/t/perf/p5313-pack-objects.sh\n+++ b/t/perf/p5313-pack-objects.sh\n@@ -28,6 +28,14 @@ test_size 'thin pack size' '\n \twc -c out\n+'\n+\n+test_size 'thin pack size with --full-name-hash' '\n+\twc -c out\n '\n@@ -44,6 +52,14 @@ test_size 'big recent pack size' '\n \twc -c out\n+'\n+\n+test_size 'big recent pack size with --full-name-hash' '\n+\twc -c out\n '\n@@ -62,6 +78,16 @@ test_size 'full repack size' '\n \t\t sort -nr | head -n 1\n '\n \n+test_perf 'full repack with --full-name-hash' '\n+\tgit repack -adf --no-write-bitmap-index --full-name-hash\n+'\n+\n+test_size 'full repack size with --full-name-hash' '\n+\tdu -a .git/objects/pack | \\\n+\t awk \"{ print \\$1; }\" | \\\n+\t\t sort -nr | head -n 1\n+'\n+\n test_perf 'full repack with --path-walk' '\n \tgit repack -adf --no-write-bitmap-index --path-walk\n '\n-- \ngitgitgadget\n\n"},{"id":"502520","messageId":"8df39a432fa682212d53d31389d437e86b4513f6.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 28/30] test-name-hash: add helper to compute name-hash functions","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:53Z","receivedAt":"2024-09-10T02:29:24Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nUsing this tool, we can count how many distinct name-hash values exist\nwithin a list of paths. Examples include\n\n git ls-tree -r --name-only HEAD | \\\n\t test-tool name-hash | \\\n \t awk \"{print \\$1;}\" | \\\n \t\t sort -ns | uniq | wc -l\n\nwhich outputs the number of distinct name-hash values that appear at\nHEAD. Or, the following which presents the resulting name-hash values of\nmaximum multiplicity:\n\n git ls-tree -r --name-only HEAD | \\\n\t test-tool name-hash | \\\n\t awk \"{print \\$1;}\" | \\\n\t sort -n | uniq -c | sort -nr | head -n 25\n\nFor an internal monorepo with around a quarter million paths at HEAD,\nthe highest multiplicity for the standard name-hash function was 14,424\nwhile the full name-hash algorithm had only seven hash values with any\ncollision, with a maximum multiplicity of two.\n\nSigned-off-by: Derrick Stolee \n---\n Makefile | 1 +\n t/helper/test-name-hash.c | 23 +++++++++++++++++++++++\n t/helper/test-tool.c | 1 +\n t/helper/test-tool.h | 1 +\n 4 files changed, 26 insertions(+)\n create mode 100644 t/helper/test-name-hash.c\n\ndiff --git a/Makefile b/Makefile\nindex 154de6e01d0..462aff65a50 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -808,6 +808,7 @@ TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o\n TEST_BUILTINS_OBJS += test-match-trees.o\n TEST_BUILTINS_OBJS += test-mergesort.o\n TEST_BUILTINS_OBJS += test-mktemp.o\n+TEST_BUILTINS_OBJS += test-name-hash.o\n TEST_BUILTINS_OBJS += test-oid-array.o\n TEST_BUILTINS_OBJS += test-online-cpus.o\n TEST_BUILTINS_OBJS += test-pack-mtimes.o\ndiff --git a/t/helper/test-name-hash.c b/t/helper/test-name-hash.c\nnew file mode 100644\nindex 00000000000..c82ccd7cefd\n--- /dev/null\n+++ b/t/helper/test-name-hash.c\n@@ -0,0 +1,23 @@\n+/*\n+ * test-name-hash.c: Read a list of paths over stdin and report on their\n+ * name-hash and full name-hash.\n+ */\n+\n+#include \"test-tool.h\"\n+#include \"git-compat-util.h\"\n+#include \"pack-objects.h\"\n+#include \"strbuf.h\"\n+\n+int cmd__name_hash(int argc, const char **argv)\n+{\n+\tstruct strbuf line = STRBUF_INIT;\n+\n+\twhile (!strbuf_getline(&line, stdin)) {\n+\t\tuint32_t name_hash = pack_name_hash(line.buf);\n+\t\tuint32_t full_hash = pack_full_name_hash(line.buf);\n+\n+\t\tprintf(\"%10\"PRIu32\"\\t%10\"PRIu32\"\\t%s\\n\", name_hash, full_hash, line.buf);\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/t/helper/test-tool.c b/t/helper/test-tool.c\nindex f8a67df7de9..4a603921002 100644\n--- a/t/helper/test-tool.c\n+++ b/t/helper/test-tool.c\n@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = {\n \t{ \"match-trees\", cmd__match_trees },\n \t{ \"mergesort\", cmd__mergesort },\n \t{ \"mktemp\", cmd__mktemp },\n+\t{ \"name-hash\", cmd__name_hash },\n \t{ \"oid-array\", cmd__oid_array },\n \t{ \"online-cpus\", cmd__online_cpus },\n \t{ \"pack-mtimes\", cmd__pack_mtimes },\ndiff --git a/t/helper/test-tool.h b/t/helper/test-tool.h\nindex e74bc0ffd41..56a83bf3aac 100644\n--- a/t/helper/test-tool.h\n+++ b/t/helper/test-tool.h\n@@ -37,6 +37,7 @@ int cmd__lazy_init_name_hash(int argc, const char **argv);\n int cmd__match_trees(int argc, const char **argv);\n int cmd__mergesort(int argc, const char **argv);\n int cmd__mktemp(int argc, const char **argv);\n+int cmd__name_hash(int argc, const char **argv);\n int cmd__online_cpus(int argc, const char **argv);\n int cmd__pack_mtimes(int argc, const char **argv);\n int cmd__parse_options(int argc, const char **argv);\n-- \ngitgitgadget\n\n"},{"id":"502521","messageId":"5dcb20a1c5c1e6f5dd676c54fa6b001af9abe072.1725935335.git.gitgitgadget@gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"[PATCH 29/30] p5314: add a size test for name-hash collisions","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-09-10T02:28:54Z","receivedAt":"2024-09-10T02:29:25Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis test helps inform someone as to the behavior of the name-hash\nalgorithms for their repo based on the paths at HEAD.\n\nFor example, the microsoft/fluentui repo had these statistics at time of\ncommitting:\n\nTest this tree\n-----------------------------------------------------------------\n5314.1: paths at head 19.6K\n5314.2: number of distinct name-hashes 8.2K\n5314.3: number of distinct full-name-hashes 19.6K\n5314.4: maximum multiplicity of name-hashes 279\n5314.5: maximum multiplicity of fullname-hashes 1\n\nThat demonstrates that of the nearly twenty thousand path names, they\nare assigned around eight thousand distinct values. 279 paths are\nassigned to a single value, leading the packing algorithm to sort\nobjects from those paths together, by size.\n\nIn this repository, no collisions occur for the full-name-hash\nalgorithm.\n\nIn a more extreme example, an internal monorepo had a much worse\ncollision rate:\n\nTest this tree\n-----------------------------------------------------------------\n5314.1: paths at head 221.6K\n5314.2: number of distinct name-hashes 72.0K\n5314.3: number of distinct full-name-hashes 221.6K\n5314.4: maximum multiplicity of name-hashes 14.4K\n5314.5: maximum multiplicity of fullname-hashes 2\n\nEven in this repository with many more paths at HEAD, the collision rate\nwas low and the maximum number of paths being grouped into a single\nbucket by the full-path-name algorithm was two.\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p5314-name-hash.sh | 41 +++++++++++++++++++++++++++++++++++++++\n 1 file changed, 41 insertions(+)\n create mode 100755 t/perf/p5314-name-hash.sh\n\ndiff --git a/t/perf/p5314-name-hash.sh b/t/perf/p5314-name-hash.sh\nnew file mode 100755\nindex 00000000000..9fe26612fac\n--- /dev/null\n+++ b/t/perf/p5314-name-hash.sh\n@@ -0,0 +1,41 @@\n+#!/bin/sh\n+\n+test_description='Tests pack performance using bitmaps'\n+. ./perf-lib.sh\n+\n+GIT_TEST_PASSING_SANITIZE_LEAK=0\n+export GIT_TEST_PASSING_SANITIZE_LEAK\n+\n+test_perf_large_repo\n+\n+test_size 'paths at head' '\n+\tgit ls-tree -r --name-only HEAD >path-list &&\n+\twc -l name-hashes &&\n+\tcat name-hashes | awk \"{ print \\$1; }\" | sort -n | uniq -c >name-hash-count &&\n+\twc -l full-name-hash-count &&\n+\twc -l \n\nIn order to debug what is going on during delta calculations, add a\n--debug-file= option to 'git pack-objects'. This leads to sending\na JSON-formatted description of the delta information to that file.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/pack-objects.c | 69 ++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 69 insertions(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 5d5a57e6b1f..7d1dd5a6557 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -50,6 +50,9 @@\n */\n static struct packing_data to_pack;\n \n+static FILE *delta_file;\n+static int delta_file_nr;\n+\n static inline struct object_entry *oe_delta(\n \t\tconst struct packing_data *pack,\n \t\tconst struct object_entry *e)\n@@ -516,6 +519,14 @@ static unsigned long write_no_reuse_object(struct hashfile *f, struct object_ent\n \thdrlen = encode_in_pack_object_header(header, sizeof(header),\n \t\t\t\t\t type, size);\n \n+\tif (delta_file) {\n+\t\tif (delta_file_nr++)\n+\t\t\tfprintf(delta_file, \",\\n\");\n+\t\tfprintf(delta_file, \"\\t\\t{\\n\");\n+\t\tfprintf(delta_file, \"\\t\\t\\t\\\"oid\\\" : \\\"%s\\\",\\n\", oid_to_hex(&entry->idx.oid));\n+\t\tfprintf(delta_file, \"\\t\\t\\t\\\"size\\\" : %\"PRIuMAX\",\\n\", datalen);\n+\t}\n+\n \tif (type == OBJ_OFS_DELTA) {\n \t\t/*\n \t\t * Deltas with relative base contain an additional\n@@ -536,6 +547,11 @@ static unsigned long write_no_reuse_object(struct hashfile *f, struct object_ent\n \t\thashwrite(f, header, hdrlen);\n \t\thashwrite(f, dheader + pos, sizeof(dheader) - pos);\n \t\thdrlen += sizeof(dheader) - pos;\n+\t\tif (delta_file) {\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_type\\\" : \\\"OFS\\\",\\n\");\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"offset\\\" : %\"PRIuMAX\",\\n\", ofs);\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_base\\\" : \\\"%s\\\",\\n\", oid_to_hex(&DELTA(entry)->idx.oid));\n+\t\t}\n \t} else if (type == OBJ_REF_DELTA) {\n \t\t/*\n \t\t * Deltas with a base reference contain\n@@ -550,6 +566,10 @@ static unsigned long write_no_reuse_object(struct hashfile *f, struct object_ent\n \t\thashwrite(f, header, hdrlen);\n \t\thashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);\n \t\thdrlen += hashsz;\n+\t\tif (delta_file) {\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_type\\\" : \\\"REF\\\",\\n\");\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_base\\\" : \\\"%s\\\",\\n\", oid_to_hex(&DELTA(entry)->idx.oid));\n+\t\t}\n \t} else {\n \t\tif (limit && hdrlen + datalen + hashsz >= limit) {\n \t\t\tif (st)\n@@ -559,6 +579,10 @@ static unsigned long write_no_reuse_object(struct hashfile *f, struct object_ent\n \t\t}\n \t\thashwrite(f, header, hdrlen);\n \t}\n+\n+\tif (delta_file)\n+\t\tfprintf(delta_file, \"\\t\\t\\t\\\"reused\\\" : false\\n\\t\\t}\");\n+\n \tif (st) {\n \t\tdatalen = write_large_blob_data(st, f, &entry->idx.oid);\n \t\tclose_istream(st);\n@@ -619,6 +643,14 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,\n \t\treturn write_no_reuse_object(f, entry, limit, usable_delta);\n \t}\n \n+\tif (delta_file) {\n+\t\tif (delta_file_nr++)\n+\t\t\tfprintf(delta_file, \",\\n\");\n+\t\tfprintf(delta_file, \"\\t\\t{\\n\");\n+\t\tfprintf(delta_file, \"\\t\\t\\t\\\"oid\\\" : \\\"%s\\\",\\n\", oid_to_hex(&entry->idx.oid));\n+\t\tfprintf(delta_file, \"\\t\\t\\t\\\"size\\\" : %\"PRIuMAX\",\\n\", entry_size);\n+\t}\n+\n \tif (type == OBJ_OFS_DELTA) {\n \t\toff_t ofs = entry->idx.offset - DELTA(entry)->idx.offset;\n \t\tunsigned pos = sizeof(dheader) - 1;\n@@ -633,6 +665,12 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,\n \t\thashwrite(f, dheader + pos, sizeof(dheader) - pos);\n \t\thdrlen += sizeof(dheader) - pos;\n \t\treused_delta++;\n+\n+\t\tif (delta_file) {\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_type\\\" : \\\"OFS\\\",\\n\");\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"offset\\\" : %\"PRIuMAX\",\\n\", ofs);\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_base\\\" : \\\"%s\\\",\\n\", oid_to_hex(&DELTA(entry)->idx.oid));\n+\t\t}\n \t} else if (type == OBJ_REF_DELTA) {\n \t\tif (limit && hdrlen + hashsz + datalen + hashsz >= limit) {\n \t\t\tunuse_pack(&w_curs);\n@@ -642,6 +680,10 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,\n \t\thashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);\n \t\thdrlen += hashsz;\n \t\treused_delta++;\n+\t\tif (delta_file) {\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_type\\\" : \\\"REF\\\",\\n\");\n+\t\t\tfprintf(delta_file, \"\\t\\t\\t\\\"delta_base\\\" : \\\"%s\\\",\\n\", oid_to_hex(&DELTA(entry)->idx.oid));\n+\t\t}\n \t} else {\n \t\tif (limit && hdrlen + datalen + hashsz >= limit) {\n \t\t\tunuse_pack(&w_curs);\n@@ -652,6 +694,10 @@ static off_t write_reuse_object(struct hashfile *f, struct object_entry *entry,\n \tcopy_pack_data(f, p, &w_curs, offset, datalen);\n \tunuse_pack(&w_curs);\n \treused++;\n+\n+\tif (delta_file)\n+\t\tfprintf(delta_file, \"\\t\\t\\t\\\"reused\\\" : true\\n\\t\\t}\");\n+\n \treturn hdrlen + datalen;\n }\n \n@@ -1264,6 +1310,11 @@ static void write_pack_file(void)\n \tALLOC_ARRAY(written_list, to_pack.nr_objects);\n \twrite_order = compute_write_order();\n \n+\tif (delta_file) {\n+\t\tfprintf(delta_file, \"{\\n\\t\\\"num_objects\\\" : %\"PRIu32\",\\n\", to_pack.nr_objects);\n+\t\tfprintf(delta_file, \"\\t\\\"objects\\\" : [\\n\");\n+\t}\n+\n \tdo {\n \t\tunsigned char hash[GIT_MAX_RAWSZ];\n \t\tchar *pack_tmp_name = NULL;\n@@ -1412,6 +1463,9 @@ static void write_pack_file(void)\n \t\t written, nr_result);\n \ttrace2_data_intmax(\"pack-objects\", the_repository,\n \t\t\t \"write_pack_file/wrote\", nr_result);\n+\n+\tif (delta_file)\n+\t\tfprintf(delta_file, \"\\n\\t]\\n}\");\n }\n \n static int no_try_delta(const char *path)\n@@ -4430,6 +4484,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tstruct string_list keep_pack_list = STRING_LIST_INIT_NODUP;\n \tstruct list_objects_filter_options filter_options =\n \t\tLIST_OBJECTS_FILTER_INIT;\n+\tconst char *delta_file_name = NULL;\n \n \tstruct option pack_objects_options[] = {\n \t\tOPT_CALLBACK_F('q', \"quiet\", &progress, NULL,\n@@ -4536,6 +4591,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"exclude any configured uploadpack.blobpackfileuri with this protocol\")),\n \t\tOPT_BOOL(0, \"full-name-hash\", &use_full_name_hash,\n \t\t\t N_(\"optimize delta compression across identical path names over time\")),\n+\t\tOPT_STRING(0, \"delta-file\", &delta_file_name,\n+\t\t\t\tN_(\"filename\"),\n+\t\t\t\tN_(\"output delta compression details to the given file\")),\n \t\tOPT_END(),\n \t};\n \n@@ -4573,6 +4631,12 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (pack_to_stdout != !base_name || argc)\n \t\tusage_with_options(pack_usage, pack_objects_options);\n \n+\tif (delta_file_name) {\n+\t\tdelta_file = fopen(delta_file_name, \"w\");\n+\t\tif (!delta_file)\n+\t\t\tdie_errno(\"failed to open '%s'\", delta_file_name);\n+\t\ttrace2_printf(\"opened '%s' for writing deltas\", delta_file_name);\n+\t}\n \tif (depth < 0)\n \t\tdepth = 0;\n \tif (depth >= (1 << OE_DEPTH_BITS)) {\n@@ -4796,5 +4860,10 @@ cleanup:\n \tlist_objects_filter_release(&filter_options);\n \tstrvec_clear(&rp);\n \n+\tif (delta_file) {\n+\t\tfflush(delta_file);\n+\t\tfclose(delta_file);\n+\t}\n+\n \treturn 0;\n }\n-- \ngitgitgadget\n"},{"id":"502645","messageId":"xmqq8qvx6fmy.fsf@gitster.g","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"Re: [PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-11T21:32:05Z","receivedAt":"2024-09-11T21:32:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> One obvious issue with this current implementation is that it inlines much\n> of the delta calculation into the \"Enumerate objects\" phase, and thus makes\n> it single-threaded.\n\nNaïvely, traversal of history partitioned by paths smells\nembarrassingly parallelizable; it may need some post processing to\nmake sure that the same object only appears once, though, and the\ndevil probably is in the details ;-).\n\nThanks for an enjoyable cover letter that pulls readers in.\n"},{"id":"502949","messageId":"CAP8UFD0uyVk5WPX12sGhWWXkdQWGpBhG29Q-9EmBxHos1XQ_uQ@mail.gmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"Re: [PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2024-09-17T10:41:22Z","receivedAt":"2024-09-17T10:41:37Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Sep 10, 2024 at 4:29 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> This RFC is ultimately about introducing a new way to walk objects, called\n> the \"path-walk API\" in the new path-walk.[ch] files. Before digging into the\n> details of the API, let's discuss the applications which will hint at the\n> API's design.\n>\n>\n> APPLICATIONS OF THE PATH-WALK API\n> =================================\n>\n> The applications of this API were discovered in the following order, though\n> I recommend reversing the order for the priority of their actual\n> implementation in future patch series:\n>\n> * git backfill: a builtin to download missing blobs in a blobless partial\n> clone, done in batches and grouped by the path they appear in to maximize\n> delta compression in each batch. Allows focusing on the paths of the\n> sparse-checkout to only get the blobs necessary for history queries in\n> the current focus.\n\nIt's not very clear if this would be useful when doing a `git\nsparse-checkout add`, or a `git blame` on a file path not covered by\nthe current sparse-checkout, or both. I think it would be clearer if\nthere were a few examples.\n\n> * git survey: Jeff Hostetler built this feature [1] as a way to get\n> functionality similar to git-sizer [2], but using the internals of Git to\n> do it faster. It also displays information not available to git-sizer,\n> like the on-disk size of objects. This RFC presents a simplified version\n> of the builtin focused on listing the paths that contribute the most to\n> the on-disk size of trees and blobs.\n\nNot sure how `git survey` works, but `git sizer` works on a whole\nrepo, so, if they work in the same way, I am not sure I see what a new\npath oriented way to walk repos would bring to the tool.\n\n> * git pack-objects --path-walk: In order to find a way to compute deltas\n> among objects of the same path, I applied the path-walk API to 'git\n> pack-objects' behind an optional flag. There are overlaps with the\n> '--sparse' option [3], [4] that can be used here. This provides perfect\n> partitioning by path name, without any possible collisions from the\n> name-hash algorithm. It also allows using the name-hash values to find\n> cross-path delta chains in a second pass.\n\nDo you mean that the new way to walk repos allows pack-object to\nperform better in the general case or maybe only in the case where\npartial clone without blobs and sparse-checkout are used as described\nin the git backfill related point above?\n\n> * git repack --full-name-hash: If we are worried about name-hsah\n\ns/name-hsah/name-hash/\n\n> collisions, an easier thing to implement is a different name-hash\n> algorithm that is less likely to have collisions.\n\nMaybe it could help to remind people a bit (perhaps in a note or using\na link) what name-hash collisions are and why we could be worried\nabout them.\n\nActually there is a \"DISCUSSION OF NAME HASH\" section below with\nexplanations, so maybe a note could just tell about that section.\n\n> This feature was\n> already sent to the mailing list as a fully-reviewable series [5]. It is\n> included here because this series allows testing the --path-walk option\n> against the --full-name-hash.\n\nDo you mean that the new way to walk repos can be used along with `git\nrepack --full-name-hash` (maybe with `git repack --full-name-hash\n--path-walk` or a config option or otherwise?) and that it brings some\nperformance or other kind (better packs or which ones?) of\nimprovements?\n\n> [1] https://github.com/microsoft/git/pull/667 [2]\n> https://github.com/github/git-sizer [3]\n> https://github.com/git/git/compare/5d826e972970a784bd7a7bdf587512510097b8c7...99dbbfa8ddbba2b620965d026d4ec199b8837a6f\n> [4]\n> https://devblogs.microsoft.com/devops/exploring-new-frontiers-for-git-push-performance/\n> [5]\n> https://lore.kernel.org/git/pull.1785.git.1725890210.gitgitgadget@gmail.com\n\nIt looks like adding line breaks could help make the above link list\nmore readable.\n\n> TIMELINE FOR CREATING THESE APPLICATIONS IN THIS ORDER\n> ======================================================\n>\n> Here's the story about how these applications came about: I was tasked with\n> understanding why certain internal repositories were growing larger than\n> expected. (Feel free to skip. Otherwise, thank you for indulging me.)\n>\n> I first prototyped 'git backfill' as a way to download some of the largest\n> repositories without being blocked on a full clone. This batched download\n> mechanism allowed me to essentially have a retryable clone, since the client\n> could restart the process from scratch and skip any objects that were\n> already on disk. It was natural to batch based on the path of the blobs in\n> order to theoretically save time and network bandwidth due to better delta\n> calculations.\n>\n> While investigating these repositories, I had some data hinting at the total\n> size of the objects by type.\n\nBy type (blob, tree, commit, tag?) or by path? Why would the size of\nthe objects by type be interesting? Could trees delta poorly?\n\n> But I was most interested in learning what\n> exactly was causing this growth. I did have a hint that the \"release\"\n> branches were taking up much more space than the default branch, since\n> cloning with --single-branch resulted in ~55GB of data but then fetching the\n> release branches led to an additional ~125GB of data. Using \"git diff\" it\n> was clear that these branches stored some CHANGELOG.json and CHANGELOG.md\n> files, but the diffs were relatively small (but multiple such changes were\n> batched together into a single new commit). I needed to see why exactly\n> these paths were taking up so much space.\n>\n> To this, I turned to Jeff Hostetler's new \"git survey\" command. This told me\n> information about the total size of trees and blobs and told me the path\n> name for the individual blobs that were the largest in the repository.\n\nNice.\n\n> These\n> paths were typically binary files that appeared only once or twice and did\n> not account for the scale issues.\n\nYou mean they couldn't account for a 55GB to 125GB change in data size?\n\n> I modified 'git survey' to use the same\n> path-batching logic as in 'git backfill' to then consider each batch of\n> objects and their size. Thus, the \"path-walk API\" was born. (This RFC\n> contains a version that looks like it was created before 'git backfill'.)\n>\n> The repository I was looking at had a clear pattern in its top 100 file\n> paths by on-disk size: 99 of them were CHANGELOG.json and CHANGELOG.md\n> files. The .md files surprised me, since they were always simple appends of\n> the previous .md file at the same path. The .json files were capped in how\n> many versions were being listed (at least in recent versions) but the data\n> it stored was harder to compress. So I went looking into how 'git push' was\n> calculating these delta bases. Adding some debug information to 'git\n> pack-objects' demonstrated that the previous file versions were not being\n> matched as delta bases. Instead, other new blobs in the push were being used\n> as delta bases.\n\nInteresting.\n\n> This meant that what should have been a trivial set of deltas bloated to\n> 20-60 MB. (We will see later that it is possible for these to be 100-500\n> KB.)\n>\n> Here is where I went on a little bit of a detour. (Come with me, it's\n> important.) I knew that 'git pack-objects' used a name-hash to group objects\n> by path, so I assumed that the reason these delta bases were not found was\n> because the UNINTERESTING objects were not being added to the packing list.\n> I have since discovered that this is incorrect, but I might have gotten\n> stuck if I didn't think this.\n>\n> This seemed like a natural reason to extend the path-walk API to allow\n> walking commits and tags as part of 'git pack-objects' behind a new\n> '--path-walk' option. The idea here is to compute deltas among the objects\n> that share a common path and then later go through the (type, name-hash,\n> size) sorting system to find other delta bases across path boundaries. After\n> a lot of testing, failing, and testing again, the implementation in this RFC\n> finally works to achieve the goal. It's not pretty (especially with how it\n> handles tags) but it gets the job done.\n\nYeah, if it can significantly improve the generated packfiles (without\ndrawbacks), it looks like a great improvement.\n\n> In hindsight, I realized that the UNINTERESTING objects were being\n> considered, but due to collisions in the name-hash algorithm these objects\n> were being sorted outside of the delta computation window. For this reason,\n> I thought to create a new name-hash algorithm. Thus, the --full-name-hash\n> option for 'git pack-objects' and 'git repack' was born. This feature was\n> split out and sent to the mailing list independently from this RFC.\n\nSo the question is \"Is the problem fully solved by the new name-hash\nalgorithm or are there still benefits to using a new way to walk\nrepos?\"\n\n> RFC GOALS\n> =========\n>\n> The goals of this RFC are:\n>\n> 1. To demonstrate potential applications of the path-walk API to motivate\n> its generality\n\nYeah, the \"Path-walk API and applications\" title summarizes this well.\n\n> as these features are sent in full-quality patch series,\n> but in a different order.\n\nI wonder if the patch series could have been separated and not all\nsent in a 30 patch long series.\n\n> 2. To communicate the discoveries found during the --path-walk and\n> --full-name-hash features in 'git pack-objects' and 'git repack'. This\n> includes comparing and contrasting the effectiveness of these features.\n\nThanks for communicating that.\n\n> 3. To demonstrate the value of the path-based batching in the 'git survey'\n> feature, and to inspire others to think about what other statistics\n> would be valuable in that feature. (I anticipate that once a base is\n> established, multiple contributors will help expand its functionality\n> long into the future.)\n\nYeah, a better git sizer would be valuable for GitLab too and probably\neveryone hosting a significant number of repos.\n\n> RFC OUTLINE\n> ===========\n>\n> The patches are grouped roughly by the application, in order of discovery:\n>\n>\n> PART I: 'git backfill'\n> ======================\n>\n> These patches introduce the 'git backfill' builtin including its\n> '--batch-size' and '--sparse' options. While this is the first and simplest\n> application, it is also the lowest priority in terms of user need.\n>\n> * path-walk: introduce an object walk by path\n> * backfill: add builtin boilerplate\n> * backfill: basic functionality and tests\n> * backfill: add --batch-size= option\n> * backfill: add --sparse option\n> * backfill: assume --sparse when sparse-checkout is enabled\n\nI would prefer a first patch series with all the above and the first\npatch creating a technical doc called maybe\nDocumentation/technical/path-walk.txt which could contain a lot of\ninformation from this RFC and perhaps technical details of how the\npath-walk works and how it is different from a regular walk.\n\n> DISCUSSION OF NAME HASH\n> =======================\n>\n> One thing to talk about before digging into --path-walk and --full-name-hash\n> features is the existing name-hash algorithm. This hash algorithm creates a\n> uint32_t based on the final 16 characters of the path name, weighing the\n> last characters more. There are multiple benefits to this:\n>\n> 1. Files of common types (.c, .txt, ...) may be grouped together.\n>\n> 2. Files that are renamed across directories may be grouped together.\n>\n> (Thanks, Junio, for making this second benefit clear.)\n>\n> The issue here is that some common patterns arise in repositories that use\n> common path names across directories, and those files are creating name-hash\n> collisions and making the sort less effective. One thing that can counteract\n> these collisions is to increase the --window setting, but this significantly\n> slows the delta computations.\n>\n> Thus, the --path-walk and --full-name-hash features both attempt to combat\n> these name-hash collisions in very different ways. The --path-walk mechanism\n> uses the path-walk API to consider batches of objects that all share the\n> same path. This avoids storing every possible path names in memory while\n> doing the object walk, but still gives nice boundaries for delta compression\n> possibilities. After the path-walk is complete, the full packing list is\n> still sorted via name-hash and this allows for cross-path deltas. This is\n> critical!\n>\n> The --full-name-hash feature does the simpler choice of replacing the\n> name-hash method with one that has fewer collisions, but loses the benefits\n> of \"nearby\" paths having close hash values.\n\nThe benefits of \"nearby\" paths are only available with --path-walk,\nnot in the current way object packing works.\n\n> This naturally leads to these two main differences in the two approaches:\n>\n> 1. The --full-name-hash feature is not good for 'git push' or similarly\n> small pack-files. Since it limits the delta chains to objects with the\n> same full path and loses the benefit of \"nearby\" paths, this feature\n> should be used for larger repacks. In my testing, 'git push' simulations\n> almost always have poor packing but 'git repack -adf' simulations have\n> packing rivaling the --path-walk option.\n\nInteresting.\n\n> 2. The --path-walk option changes the object ordering significantly,\n> meaning it may not ever be appropriate to combine with advanced\n> repacking features such as delta islands or even reachability bitmaps.\n> While my testing has shown that the --path-walk repacks are the most\n> efficient of all options, this limitation makes me hesitate to recommend\n> it wider than client repositories.\n\nMight still be interesting to have it for client repos.\n\n> One natural question to consider is to think about storing both the\n> name-hash and the full-name-hash and doing two delta passes, each one\n> sorting the objects by a different hash function. The first issue is that we\n> don't want to store two hash values per object, as that will significantly\n> increase the memory pressure during repacking.\n\nIs one more uint32_t per object really increasing the memory pressure\nso much? Isn't there a way to pack bits together to avoid that?\n\n> This could be side-stepped by\n> storing the full-name-hash in the packing list and then a second mapping\n> from full-name-hash to name-hash. However, that still leads to the two\n> passes taking extra time.\n\nIsn't there a way to sort using both hash functions in a single pass?\n(That is to perform a single pass and when considering an object sort\nit using both hash functions before considering a different object.)\n\n> The --path-walk approach is faster than even a\n> single pass.\n\nIs there a reason for that?\n\n> And in the right scenarios, the --full-name-hash option is very\n> close to the --path-walk results.\n>\n>\n> ANALYSIS OF PACKING STRATEGIES\n> ==============================\n>\n> Since I was focused on an internal monorepo that stored a large collection\n> of Javascript packages, it should be no surprise that I eventually found\n> other Javascript repositories that used similar tooling and thus had similar\n> issues with unexplained scale problems. I'll use these four repositories as\n> examples repeatedly, but one is actually public: microsoft/fluentui [6].\n> I'll use Repo B, C, and D for the others, in increasing size.\n>\n> [6] https://github.com/microsoft/fluentui\n>\n> In each of these repositories, doing a full repack ('git repack -adf') right\n> after cloning presents a sizeable reduction in space. This is expected for\n> servers not being optimized for exactly the reachable set I'm cloning. So,\n> I'll focus on how much the default repacking parameters compare to using the\n> --full-name-hash or --path-walk options:\n>\n> | Repo | Standard Repack | With --full-name-hash | With --path-walk |\n> |----------|-----------------|-----------------------|------------------|\n> | fluentui | 438 MB | 168 MB | 148 MB |\n> | Repo B | 6,255 MB | 829 MB | 778 MB |\n> | Repo C | 37,737 MB | 7,125 MB | 6,158 MB |\n> | Repo D | 130,049 MB | 6,190 MB | 4,432 MB |\n>\n>\n> Hopefully these reductions show how much these name-hash collisions are\n> causing issues in these repositories.\n\nYeah, right. It might be interesting to see the size reduction in % too.\n\n> For the fluentui repo, I'm also able to share highlights from the 'git\n> survey' output immediately after cloning and after repacking with the\n> --path-walk option.\n>\n> First, we can consider the total reachable objects in each scenario:\n>\n> TOTAL OBJECT SIZES BY TYPE\n> ================================================\n> Object Type | Count | Disk Size | Inflated Size\n> ------------+--------+-----------+--------------\n> Commits | 20579 | 10443669 | 15092790\n> Trees | 276503 | 40212070 | 244429615\n> Blobs | 294500 | 635365661 | 10791187920\n>\n> TOTAL OBJECT SIZES BY TYPE\n> ================================================\n> Object Type | Count | Disk Size | Inflated Size\n> ------------+--------+-----------+--------------\n> Commits | 20579 | 10450605 | 15092790\n> Trees | 276503 | 31136263 | 244429615\n> Blobs | 294500 | 94442401 | 10791187920\n\nUsing % of size reduction or increase might help make it a bit clearer here too.\n\n> Now, we can consider the top 10 file paths before and after repacking with\n> the --path-walk feature:\n>\n> TOP FILES BY DISK SIZE\n> ===================================================================\n> Path | Count | Disk Size | Inflated Size\n> --------------------------------+-------+-----------+--------------\n> yarn.lock | 802 | 58060531 | 889120488\n> ...-experiments/CHANGELOG.json | 505 | 28439452 | 252723999\n> ...fabric-react/CHANGELOG.json | 1270 | 25556510 | 902756623\n> ...t-components/CHANGELOG.json | 176 | 20366365 | 244936649\n> ...act-charting/CHANGELOG.json | 590 | 20106422 | 208224460\n> ...e-components/CHANGELOG.json | 559 | 15761271 | 189061764\n> ...act-examples/CHANGELOG.json | 577 | 13615569 | 234949961\n> ...react-charting/CHANGELOG.md | 564 | 11205840 | 104337986\n> .../experiments/CHANGELOG.json | 569 | 10596377 | 123662770\n> ...i-fabric-react/CHANGELOG.md | 1263 | 8154248 | 261494258\n>\n>\n> TOP FILES BY DISK SIZE\n> ===================================================================\n> Path | Count | Disk Size | Inflated Size\n> --------------------------------+-------+-----------+--------------\n> yarn.lock | 802 | 9909326 | 889120488\n> ...iceBrandGuide_16Sep2016.pdf | 1 | 2106334 | 2186005\n> ...out/src/images/download.jpg | 1 | 1845249 | 1846117\n> ...fluent-ui-logo-inverted.png | 3 | 1370372 | 1447493\n> .yarn/releases/cli.js | 1 | 1335657 | 6741614\n> ...c/images/fluent-ui-logo.png | 3 | 1272902 | 1341139\n> ...ages/fluent-ui-logo-dev.png | 3 | 1130989 | 1186897\n> ...nents/public/SegoeUI-VF.ttf | 1 | 1074046 | 1844524\n> ...ig/rush/npm-shrinkwrap.json | 138 | 1058531 | 89326567\n> ...Accessibility_29Sep2016.pdf | 1 | 856621 | 927268\n>\n>\n> As we can see from this example, before the repack we are mainly seeing the\n> disk space be dominated by objects that appear at paths with CHANGELOG.json\n> or CHANGELOG.md, which are frequently hitting collisions with the default\n> name-hash. After the repack with the --path-walk feature, we see the largest\n> paths are what we expect: checked in binaries, frequently-edited yarn files,\n> and other hard-to- compress data.\n>\n> The nice thing about this result is that we can point to files that are\n> taking up space because there is no other way around it, not that the naming\n> convention for the files is causing confusion during packing.\n\nYeah, nice result. I guess the result is the same or very similar when\nthe improved name-hash algorithm is used.\n\n> WHAT TO DO NOW?\n> ===============\n>\n> Thank you for reading this far. I hope that this has added context on the\n> patch series for the --full-name-hash option, but also provided the right\n> context for when I come back in a week or so with a review-ready version of\n> the --path-walk option.\n>\n> These patches are rough and I want to make sure everyone knows that.\n> Reviewing them for style or even basic organization may lead to some wasted\n> time. I know that at least one of the patches got mangled and its diff does\n> not match its description (I'm thinking specifically about \"pack-objects:\n> extract should_attempt_deltas()\" but this could apply elsewhere).\n\nOk, I will wait for the next iteration before reviewing the patches then.\n\n> But I think that interested parties could take my branch, build it, and give\n> these features a try on their favorite repos. I'd love to hear feedback on\n> the usability and effectiveness, especially if someone finds a case where\n> the --path-walk option is less effective at packing data.\n\nI might do that when reviewing the patch series later. I think it can\nstill be valuable for you to get some first feedback from just reading\nthis RFC.\n\nThanks.\n"},{"id":"503034","messageId":"53dc17f8-82e5-40fa-81b7-af89f987928b@gmail.com","threadId":"62091","inReplyTo":"CAP8UFD0uyVk5WPX12sGhWWXkdQWGpBhG29Q-9EmBxHos1XQ_uQ@mail.gmail.com","subject":"Re: [PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-18T23:18:27Z","receivedAt":"2024-09-18T23:18:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/17/24 6:41 AM, Christian Couder wrote:\n > On Tue, Sep 10, 2024 at 4:29 AM Derrick Stolee via GitGitGadget\n > wrote:\n\n >> * git backfill: a builtin to download missing blobs in a blobless partial\n >> clone, done in batches and grouped by the path they appear in to maximize\n >> delta compression in each batch. Allows focusing on the paths of the\n >> sparse-checkout to only get the blobs necessary for history queries in\n >> the current focus.\n >\n > It's not very clear if this would be useful when doing a `git\n > sparse-checkout add`, or a `git blame` on a file path not covered by\n > the current sparse-checkout, or both. I think it would be clearer if\n > there were a few examples.\n\nYou are correct, this doesn't help with either of those examples, as\nthey both require blobs outside of the current sparse-checkout. The\nidea is for users who are most often in a given sparse-checkout to have\nthe experience as if they were in a non-partial Git clone, as long as\nthey restrict their activity within their sparse-checkout.\n\nIf they increase their sparse-checkout, then they can re-run 'git\nbackfill --sparse' to get the still-missing objects in the new paths.\n\n >> * git survey: Jeff Hostetler built this feature [1] as a way to get\n >> functionality similar to git-sizer [2], but using the internals of Git to\n >> do it faster. It also displays information not available to git-sizer,\n >> like the on-disk size of objects. This RFC presents a simplified version\n >> of the builtin focused on listing the paths that contribute the most to\n >> the on-disk size of trees and blobs.\n >\n > Not sure how `git survey` works, but `git sizer` works on a whole\n > repo, so, if they work in the same way, I am not sure I see what a new\n > path oriented way to walk repos would bring to the tool.\n\n`git survey` also works on a whole repo, but with the path-walk API\nimplementation can talk about a group of objects that appear at a common\npath instead of only talking about single extreme objects, such as one\nlarge binary (that never changes) being singled out over a small file\nthat chnages frequently and across all versions contributes more to the\nrepo's disk size.\n\nThe main benefit of using `git survey` over `git-sizer` is that it can\nreport on things internal to Git's storage that are not accessible to\n`git-sizer` through the `git cat-file` output it uses.\n\n >> * git pack-objects --path-walk: In order to find a way to compute deltas\n >> among objects of the same path, I applied the path-walk API to 'git\n >> pack-objects' behind an optional flag. There are overlaps with the\n >> '--sparse' option [3], [4] that can be used here. This provides perfect\n >> partitioning by path name, without any possible collisions from the\n >> name-hash algorithm. It also allows using the name-hash values to find\n >> cross-path delta chains in a second pass.\n >\n > Do you mean that the new way to walk repos allows pack-object to\n > perform better in the general case or maybe only in the case where\n > partial clone without blobs and sparse-checkout are used as described\n > in the git backfill related point above?\n\n From what I can see, `git pack-objects --path-walk` outperforms all other\nrepacking strategies that I have found, but it does have some weaknesses in\nhow it interacts with things like delta islands. There may be other concerns,\nand I _was_ able to find a repo that compressed slightly better with `git\npack-objects --full-name-hash`, but it was also storing computer-generated,\nsingle-line JSON files representing configuration of production systems. I\nwould like to have a more generic thing to say about this, but it will vary\non data shape.\n\n >> This feature was\n >> already sent to the mailing list as a fully-reviewable series [5]. It is\n >> included here because this series allows testing the --path-walk option\n >> against the --full-name-hash.\n >\n > Do you mean that the new way to walk repos can be used along with `git\n > repack --full-name-hash` (maybe with `git repack --full-name-hash\n > --path-walk` or a config option or otherwise?) and that it brings some\n > performance or other kind (better packs or which ones?) of\n > improvements?\n\nCombining the two features actually ends up with very similar performance\nto what `--full-name-hash` already does. It's actually important that the\n`--path-walk` option does a full pass of the objects via the standard\nname-hash after its first pass in groups based on the path.\n\nIt's more that I include performance tests that compare how effective the\ntwo features are relative to the existing repacking strategy and in a few\ndifferent situations. This helps with both time and space performance\nmeasurements.\n\n >> TIMELINE FOR CREATING THESE APPLICATIONS IN THIS ORDER\n >> ======================================================\n >>\n >> Here's the story about how these applications came about: I was tasked with\n >> understanding why certain internal repositories were growing larger than\n >> expected. (Feel free to skip. Otherwise, thank you for indulging me.)\n >>\n >> I first prototyped 'git backfill' as a way to download some of the largest\n >> repositories without being blocked on a full clone. This batched download\n >> mechanism allowed me to essentially have a retryable clone, since the client\n >> could restart the process from scratch and skip any objects that were\n >> already on disk. It was natural to batch based on the path of the blobs in\n >> order to theoretically save time and network bandwidth due to better delta\n >> calculations.\n >>\n >> While investigating these repositories, I had some data hinting at the total\n >> size of the objects by type.\n >\n > By type (blob, tree, commit, tag?) or by path? Why would the size of\n > the objects by type be interesting? Could trees delta poorly?\n\nThe previously-existing data could only group objects by type (commit,\ntree, blob) and report on the size of the reachable objects in those\ncategories. The per-path data was not available as no tool that I knew\nabout had the capability to expose that information.\n\n >> These\n >> paths were typically binary files that appeared only once or twice and did\n >> not account for the scale issues.\n >\n > You mean they couldn't account for a 55GB to 125GB change in data size?\n\nThe numbers were so small they didn't seem like they could have accounted\nfor any issues at all, let alone a hundred gigabytes of data in the repo.\n\n >> RFC GOALS\n >> =========\n >>\n >> The goals of this RFC are:\n >>\n >> 1. To demonstrate potential applications of the path-walk API to motivate\n >> its generality\n >\n > Yeah, the \"Path-walk API and applications\" title summarizes this well.\n >\n >> as these features are sent in full-quality patch series,\n >> but in a different order.\n >\n > I wonder if the patch series could have been separated and not all\n > sent in a 30 patch long series.\n\nI was not clear about this, but the RFC is 30 patches so it's possible to see\nthe big picture, but I will be breaking it into at least four series in\nsequence for actual review. They match the four sections described above, but\nwill be in the opposite order:\n\n A. `git repack --full-name-hash`\n B. `git pack-objects --path-walk`\n C. `git survey`\n D. `git backfill`\n\n(It's possible that `git survey` and `git backfill` may be orthogonal enough\nthat they could be under review at the same time. Alternatively, `git backfill`\nmay jump the line because it's so simple to implement once the path-walk API\nis established.)\n\n >> 3. To demonstrate the value of the path-based batching in the 'git survey'\n >> feature, and to inspire others to think about what other statistics\n >> would be valuable in that feature. (I anticipate that once a base is\n >> established, multiple contributors will help expand its functionality\n >> long into the future.)\n >\n > Yeah, a better git sizer would be valuable for GitLab too and probably\n > everyone hosting a significant number of repos.\n\nThis was definitely Jeff's intention, and I agree. Hopefully we can establish\na baseline quickly and then make room for extensions as people discover new\nways to investigate repo size or performance issues.\n\n >> PART I: 'git backfill'\n >> ======================\n >>\n >> These patches introduce the 'git backfill' builtin including its\n >> '--batch-size' and '--sparse' options. While this is the first and simplest\n >> application, it is also the lowest priority in terms of user need.\n >>\n >> * path-walk: introduce an object walk by path\n >> * backfill: add builtin boilerplate\n >> * backfill: basic functionality and tests\n >> * backfill: add --batch-size= option\n >> * backfill: add --sparse option\n >> * backfill: assume --sparse when sparse-checkout is enabled\n >\n > I would prefer a first patch series with all the above and the first\n > patch creating a technical doc called maybe\n > Documentation/technical/path-walk.txt which could contain a lot of\n > information from this RFC and perhaps technical details of how the\n > path-walk works and how it is different from a regular walk.\n\nMy rework of the `git pack-objects --path-walk` series has a draft of a\ntechnical document as you suggest [1]. I regret not having time to get\nit done before this RFC.\n\n[1] \nhttps://github.com/derrickstolee/git/pull/28/files#diff-d8a8f04540e5fac6727529dcabf05501ba2447a7de340b540f2601e071b45260\n\n >> DISCUSSION OF NAME HASH\n >> =======================\n...\n >> The --full-name-hash feature does the simpler choice of replacing the\n >> name-hash method with one that has fewer collisions, but loses the benefits\n >> of \"nearby\" paths having close hash values.\n >\n > The benefits of \"nearby\" paths are only available with --path-walk,\n > not in the current way object packing works.\n\nI suppose this depends on your definition of \"nearby\" and I think we are\nusing it differently.\n\nThe --full-name-hash mechanism groups objects by their full path name, with\na small probability of a collision with another path, and thus we can think\nabout it as grouping objects by their full path. However, this lack of\ncollision comes at a cost: having unequal but \"near\" hash value does not\nimply any similarity in the full path.\n\nThe standard name-hash algorithm has a form of \"locality\" that provides a\nnice property: paths with unequal by \"near\" hash values will have some\nsimilarities in the end of their path names.\n\nBetween these two mechanisms, the collisions of the standard name-hash\ncan cause objects that should delta together to be separated in the object\norder due to too many objects with the same hash value, even though they\nhave very different full path names. While the full-name-hash mechanism\nhelps keep objects from the same path close together in the order, it\nfails to compute good deltas across objects from different paths, even\nif they may end similarly (implying similar file types or even renames\nacross directories).\n\nThe --path-walk feature has the nice benefit that it first attempts to\ncompute delta bases are grouped to exactly the set of objects that\nappear at a given path (no more, no less) but then it _also_ does the\nstandard name-hash sort to help look for delta bases using the name-hash\nlocality heuristic.\n\n >> One natural question to consider is to think about storing both the\n >> name-hash and the full-name-hash and doing two delta passes, each one\n >> sorting the objects by a different hash function. The first issue is that we\n >> don't want to store two hash values per object, as that will significantly\n >> increase the memory pressure during repacking.\n >\n > Is one more uint32_t per object really increasing the memory pressure\n > so much? Isn't there a way to pack bits together to avoid that?\n\nI hesitate to conclude that four bytes per object will not have a meaningful\nimpact. One thing that I'll be reporting on in my v2 of the --full-name-hash\nfeature is that I've gone and tried to prototype what would happen with this\nkind of approach.\n\nThe short version is that I failed to make the addition of more data to this\nstruct helpful in outperforming the --full-name-hash option. I thought that\na two-pass approach would work, but something about how the two sorts worked\ncaused problems that I could not overcome. (Maybe someone with a stronger\nhandle on this could make it work.) My WIP branch is here [2] for anyone\nwilling to try to succeed where I failed.\n\n[2] \nhttps://github.com/derrickstolee/git/compare/full-name...derrickstolee:git:full-name-wip\n\n >> This could be side-stepped by\n >> storing the full-name-hash in the packing list and then a second mapping\n >> from full-name-hash to name-hash. However, that still leads to the two\n >> passes taking extra time.\n >\n > Isn't there a way to sort using both hash functions in a single pass?\n > (That is to perform a single pass and when considering an object sort\n > it using both hash functions before considering a different object.)\n\nWe could sort the objects using both hash functions (say, name-hash then\nfull-name-hash to break ties) but then the full-name-hash values keep\nthe similar-sized objects with the same name-hash from being sorted near\neach other (at least, within the short default window, which I use for\nall of my testing). So this ends up being ineffective. In [2] above, this\nis something I tested along the way and am pretty confident that it does\nnot work as well as we'd like it to.\n\n >> The --path-walk approach is faster than even a\n >> single pass.\n >\n > Is there a reason for that?\n\nMy guess here is that we are finding the \"best\" deltas quickly, allowing\nus to short-circuit the possibility of other deltas due to file size\ndifferences. (If my object has size X, with a current delta of size D,\nthen any object smaller than X - D will not be a good base.)\n\n >> First, we can consider the total reachable objects in each scenario:\n >>\n >> TOTAL OBJECT SIZES BY TYPE\n >> ================================================\n >> Object Type | Count | Disk Size | Inflated Size\n >> ------------+--------+-----------+--------------\n >> Commits | 20579 | 10443669 | 15092790\n >> Trees | 276503 | 40212070 | 244429615\n >> Blobs | 294500 | 635365661 | 10791187920\n >>\n >> TOTAL OBJECT SIZES BY TYPE\n >> ================================================\n >> Object Type | Count | Disk Size | Inflated Size\n >> ------------+--------+-----------+--------------\n >> Commits | 20579 | 10450605 | 15092790\n >> Trees | 276503 | 31136263 | 244429615\n >> Blobs | 294500 | 94442401 | 10791187920\n >\n > Using % of size reduction or increase might help make it a bit clearer here too.\n\nTrue. I could compute that manually, as this data is not available in the\nsame process. I'll try to do that in the future.\n\n >> Now, we can consider the top 10 file paths before and after repacking with\n >> the --path-walk feature:\n...\n >> The nice thing about this result is that we can point to files that are\n >> taking up space because there is no other way around it, not that the naming\n >> convention for the files is causing confusion during packing.\n >\n > Yeah, nice result. I guess the result is the same or very similar when\n > the improved name-hash algorithm is used.\n\nYes, similar results happen there. I haven't dug into them very much to see\nif it helps point out anything about inefficiencies in --full-name-hash, but\nI don't expect any of the big differences between --full-name-hash and\n--path-walk to appear in these tables.\n\n >> WHAT TO DO NOW?\n >> ===============\n >>\n >> Thank you for reading this far. I hope that this has added context on the\n >> patch series for the --full-name-hash option, but also provided the right\n >> context for when I come back in a week or so with a review-ready version of\n >> the --path-walk option.\n >>\n >> These patches are rough and I want to make sure everyone knows that.\n >> Reviewing them for style or even basic organization may lead to some wasted\n >> time. I know that at least one of the patches got mangled and its diff does\n >> not match its description (I'm thinking specifically about \"pack-objects:\n >> extract should_attempt_deltas()\" but this could apply elsewhere).\n >\n > Ok, I will wait for the next iteration before reviewing the patches then.\n\nYes, I only meant for them to be available for those who were curious to\nexplore. Please do review v2 of the --full-name-hash series [3].\n\n[3] https://lore.kernel.org/git/pull.1785.v2.git.1726692381.gitgitgadget@gmail.com/\n\n >> But I think that interested parties could take my branch, build it, and give\n >> these features a try on their favorite repos. I'd love to hear feedback on\n >> the usability and effectiveness, especially if someone finds a case where\n >> the --path-walk option is less effective at packing data.\n >\n > I might do that when reviewing the patch series later. I think it can\n > still be valuable for you to get some first feedback from just reading\n > this RFC.\n\nThank you! And thanks for the thoughts on this very long cover letter.\n\n-Stolee\n"},{"id":"503224","messageId":"xmqqplov7cw8.fsf@gitster.g","threadId":"62091","inReplyTo":"53dc17f8-82e5-40fa-81b7-af89f987928b@gmail.com","subject":"Re: [PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-22T18:37:43Z","receivedAt":"2024-09-22T18:37:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> Combining the two features actually ends up with very similar performance\n> to what `--full-name-hash` already does. It's actually important that the\n> `--path-walk` option does a full pass of the objects via the standard\n> name-hash after its first pass in groups based on the path.\n> ...\n> I was not clear about this, but the RFC is 30 patches so it's possible to see\n> the big picture, but I will be breaking it into at least four series in\n> sequence for actual review. They match the four sections described above, but\n> will be in the opposite order:\n>\n> A. `git repack --full-name-hash`\n> B. `git pack-objects --path-walk`\n> C. `git survey`\n> D. `git backfill`\n>\n> (It's possible that `git survey` and `git backfill` may be orthogonal enough\n> that they could be under review at the same time. Alternatively, `git backfill`\n> may jump the line because it's so simple to implement once the path-walk API\n> is established.)\n\nI actually was hoping to hear something like \"since it turns out\nthat --path-walk gives a better performance and it does not regress\nsmall incremental transfer like --full-name-hash does, the real\nseries drops --full-name hash\", i.e. without part (A). That reduces\nthings we need to worry about (like having to either keep track of\ntwo \"hashes\" per object, or making small incremental transfer more\ncostly) greatly.\n\nThanks.\n"},{"id":"503228","messageId":"81bc5d69-cf50-409d-ac64-5b9b3f722ace@app.fastmail.com","threadId":"62091","inReplyTo":"pull.1786.git.1725935335.gitgitgadget@gmail.com","subject":"Re: [PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Kristoffer Haugsbakk","fromEmail":"kristofferhaugsbakk@fastmail.com","sentAt":"2024-09-22T21:08:45Z","receivedAt":"2024-09-22T21:09:21Z","isPatch":true,"sender":{"key":"kristofferhaugsbakk@fastmail.com","avatar":null},"body":"On Tue, Sep 10, 2024, at 04:28, Derrick Stolee via GitGitGadget wrote:\n> This RFC is ultimately about introducing a new way to walk objects, called\n> the \"path-walk API\" in the new path-walk.[ch] files. Before digging into the\n> details of the API, let's discuss the applications which will hint at the\n> API's design.\n\nThis series is superbly well-presented. I’m in \nawe here from the peanut gallery.\n\n-- \nKristoffer Haugsbakk\n\n"},{"id":"503229","messageId":"6b672771-4016-49e8-a045-0a48bc8c1522@gmail.com","threadId":"62091","inReplyTo":"xmqqplov7cw8.fsf@gitster.g","subject":"Re: [PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-09-23T01:22:59Z","receivedAt":"2024-09-23T01:23:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 9/22/24 2:37 PM, Junio C Hamano wrote:\n > Derrick Stolee writes:\n >\n >> Combining the two features actually ends up with very similar performance\n >> to what `--full-name-hash` already does. It's actually important that the\n >> `--path-walk` option does a full pass of the objects via the standard\n >> name-hash after its first pass in groups based on the path.\n >> ...\n >> I was not clear about this, but the RFC is 30 patches so it's possible to see\n >> the big picture, but I will be breaking it into at least four series in\n >> sequence for actual review. They match the four sections described above, but\n >> will be in the opposite order:\n >>\n >> A. `git repack --full-name-hash`\n >> B. `git pack-objects --path-walk`\n >> C. `git survey`\n >> D. `git backfill`\n >>\n >> (It's possible that `git survey` and `git backfill` may be orthogonal enough\n >> that they could be under review at the same time. Alternatively, `git backfill`\n >> may jump the line because it's so simple to implement once the path-walk API\n >> is established.)\n >\n > I actually was hoping to hear something like \"since it turns out\n > that --path-walk gives a better performance and it does not regress\n > small incremental transfer like --full-name-hash does, the real\n > series drops --full-name hash\", i.e. without part (A). That reduces\n > things we need to worry about (like having to either keep track of\n > two \"hashes\" per object, or making small incremental transfer more\n > costly) greatly.\n\nI believe that the --full-name-hash version still has some benefits, in\nthat it could better integrate with reachability bitmaps and delta\nislands:\n\n 1. The .bitmap file format would need a modification in order to signal\n which hash function is being used for compatibility reasons, but\n this does seem within reach without too much work.\n\n 2. The delta islands feature integrates seamlessly with\n --full-name-hash and seems difficult to integrate with the\n --path-walk feature. Either we would need to have a second object\n walk to get the delta island markers, or somehow put the passing of\n the object markers into the path-walk API itself (similar to how it\n needs to push the UNINTERESTING bit around during the walk).\n\nI'm not recommending any version that requires tracking two hash values\nper object, as I have not been able to demonstrate any improvement when\ndoing so.\n\nBut, it would be helpful to know if the --full-name-hash feature should\nnot be pursued due to the --path-walk feature being prepared shortly\nafter it. I can see an argument for either direction: having a new hash\nalgorithm provides a smaller change to get most of the results for the\nfull repack case, but gets worse performance in many push scenarios.\nThis is the point of an RFC, to get questions like this worked out based\non the \"big picture\" view of everything.\n\nPerhaps I should pause the --full-name-hash topic and focus on getting\nthe --path-walk topic up and running. I am curious to hear from folks\nwho are currently running Git servers about their thoughts on these\ntrade-offs and potential uses in their environment. My needs on the\nclient side are solved by the --path-walk approach.\n\nThanks,\n-Stolee\n"},{"id":"503267","messageId":"xmqq4j6648cr.fsf@gitster.g","threadId":"62091","inReplyTo":"6b672771-4016-49e8-a045-0a48bc8c1522@gmail.com","subject":"Re: [PATCH 00/30] [RFC] Path-walk API and applications","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-23T16:56:20Z","receivedAt":"2024-09-23T16:56:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> ... I can see an argument for either direction: having a new hash\n> algorithm provides a smaller change to get most of the results for the\n> full repack case, but gets worse performance in many push scenarios.\n> This is the point of an RFC, to get questions like this worked out based\n> on the \"big picture\" view of everything.\n\nExactly. We might want to use the series as an example in our\ndeveloper docs on how to propose a large-ish effort.\n\n> Perhaps I should pause the --full-name-hash topic and focus on getting\n> the --path-walk topic up and running. I am curious to hear from folks\n> who are currently running Git servers about their thoughts on these\n> trade-offs and potential uses in their environment. My needs on the\n> client side are solved by the --path-walk approach.\n\nYeah, such third-party inputs would be very useful.\n\nThanks.\n"}]}