{"thread":{"id":"48210","subject":"[PATCH 0/3] Lazy-load trees when reading commit-graph","startedAt":"2018-04-03T12:01:29Z","lastAt":"2018-04-11T20:41:31Z","messageCount":26,"participants":["Derrick Stolee","Jeff King","Stefan Beller","Jakub Narebski","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"343680","messageId":"20180403120057.173849-1-dstolee@microsoft.com","threadId":"48210","inReplyTo":null,"subject":"[PATCH 0/3] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-03T12:00:54Z","receivedAt":"2018-04-03T12:01:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"There are several commit-graph walks that require loading many commits\nbut never walk the trees reachable from those commits. However, the\ncurrent logic in parse_commit() requires the root tree to be loaded.\nThis only uses lookup_tree(), but when reading commits from the commit-\ngraph file, the hashcpy() to load the root tree hash and the time spent\nchecking the object cache take more time than parsing the rest of the\ncommit.\n\nIn this patch series, all direct references to accessing the 'tree'\nmember of struct commit are replaced instead by one of the following\nmethods:\n\n\tstruct tree *get_commit_tree(struct commit *)\n\tstruct object_id *get_commit_tree_oid(struct commit *)\n\nThis replacement was assisted by a Coccinelle script, but the 'tree'\nmember is overloaded in other types, so the script gave false-positives\nthat were removed from the diff.\n\nAfter all access is restricted to use these methods, we can then\nchange the postcondition of parse_commit_in_graph() to allow 'tree'\nto be NULL. If the tree is accessed later, we can load the tree's\nOID from the commit-graph in constant time and perform the lookup_tree().\n\nOn the Linux repository, performance tests were run for the following\ncommand:\n\n    git log --graph --oneline -1000\n\nBefore: 0.83s\nAfter:  0.65s\nRel %: -21.6%\n\nAdding '-- kernel/' to the command requires loading the root tree\nfor every commit that is walked. There was no measureable performance\nchange as a result of this patch.\n\nThis patch series depends on v7 of ds/commit-graph.\n\nDerrick Stolee (3):\n  commit: create get_commit_tree() method\n  treewide: use get_commit_tree() for tree access\n  commit-graph: lazy-load trees\n\n blame.c               | 18 +++++++++---------\n builtin/checkout.c    | 17 +++++++++--------\n builtin/diff.c        |  2 +-\n builtin/fast-export.c |  6 +++---\n builtin/log.c         |  4 ++--\n builtin/reflog.c      |  2 +-\n commit-graph.c        | 27 +++++++++++++++++++++++----\n commit-graph.h        |  7 +++++++\n commit.c              | 16 ++++++++++++++++\n commit.h              |  3 +++\n fsck.c                |  8 +++++---\n http-push.c           |  2 +-\n line-log.c            |  4 ++--\n list-objects.c        | 10 +++++-----\n log-tree.c            |  6 +++---\n merge-recursive.c     |  3 ++-\n notes-merge.c         |  8 ++++----\n packfile.c            |  2 +-\n pretty.c              |  5 +++--\n ref-filter.c          |  2 +-\n revision.c            |  8 ++++----\n sequencer.c           | 12 ++++++------\n sha1_name.c           |  2 +-\n tree.c                |  4 ++--\n walker.c              |  2 +-\n 25 files changed, 115 insertions(+), 65 deletions(-)\n\n-- \n2.17.0.20.g9f30ba16e1\n\n"},{"id":"343681","messageId":"20180403120057.173849-2-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180403120057.173849-1-dstolee@microsoft.com","subject":"[PATCH 1/3] commit: create get_commit_tree() method","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-03T12:00:55Z","receivedAt":"2018-04-03T12:01:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"While walking the commit graph, we load struct commit objects into\nthe object cache. During this process, we also load struct tree\nobjects for the root tree of each of these commits. We load these\nobjects even if we are only computing commit reachability information,\nsuch as a merge base or ahead/behind information.\n\nCreate get_commit_tree() as a first step to removing direct\nreferences to the 'tree' member of struct commit.\n\nCreate get_commit_tree_oid() as a shortcut for several references\nto \"&commit->tree->object.oid\" in the codebase.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n commit.c | 10 ++++++++++\n commit.h |  3 +++\n 2 files changed, 13 insertions(+)\n\ndiff --git a/commit.c b/commit.c\nindex 3e39c86abf..d65c7b3b47 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -296,6 +296,16 @@ void free_commit_buffer(struct commit *commit)\n \t}\n }\n \n+struct tree *get_commit_tree(const struct commit *commit)\n+{\n+\treturn commit->tree;\n+}\n+\n+struct object_id *get_commit_tree_oid(const struct commit *commit)\n+{\n+\treturn &commit->tree->object.oid;\n+}\n+\n const void *detach_commit_buffer(struct commit *commit, unsigned long *sizep)\n {\n \tstruct commit_buffer *v = buffer_slab_peek(&buffer_slab, commit);\ndiff --git a/commit.h b/commit.h\nindex e57ae4b583..fa79cc4d1f 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -102,6 +102,9 @@ void unuse_commit_buffer(const struct commit *, const void *buffer);\n  */\n void free_commit_buffer(struct commit *);\n \n+struct tree *get_commit_tree(const struct commit *);\n+struct object_id *get_commit_tree_oid(const struct commit *);\n+\n /*\n  * Disassociate any cached object buffer from the commit, but do not free it.\n  * The buffer (or NULL, if none) is returned.\n-- \n2.17.0.20.g9f30ba16e1\n\n"},{"id":"343682","messageId":"20180403120057.173849-4-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180403120057.173849-1-dstolee@microsoft.com","subject":"[PATCH 3/3] commit-graph: lazy-load trees","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-03T12:00:57Z","receivedAt":"2018-04-03T12:01:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The commit-graph file provides quick access to commit data, including\nthe OID of the root tree for each commit in the graph. When performing\na deep commit-graph walk, we may not need to load most of the trees\nfor these commits.\n\nDelay loading the tree object for a commit loaded from the graph\nuntil requested via get_commit_tree(). Do not lazy-load trees for\ncommits not in the graph, since that requires duplicate parsing\nand the relative peformance improvement when trees are not needed\nis small.\n\nOn the Linux repository, performance tests were run for the following\ncommand:\n\n\tgit log --graph --oneline -1000\n\nBefore: 0.83s\nAfter:  0.65s\nRel %: -21.6%\n\nAdding '-- kernel/' to the command requires loading the root tree\nfor every commit that is walked. There was no measureable performance\nchange as a result of this patch.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n commit-graph.c | 25 ++++++++++++++++++++++---\n commit-graph.h |  7 +++++++\n commit.c       | 10 ++++++++--\n 3 files changed, 37 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 3080a87940..a3eeb25f22 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -247,7 +247,6 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,\n \n static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t pos)\n {\n-\tstruct object_id oid;\n \tuint32_t edge_value;\n \tuint32_t *parent_data_ptr;\n \tuint64_t date_low, date_high;\n@@ -257,8 +256,7 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin\n \titem->object.parsed = 1;\n \titem->graph_pos = pos;\n \n-\thashcpy(oid.hash, commit_data);\n-\titem->tree = lookup_tree(&oid);\n+\titem->tree = NULL;\n \n \tdate_high = get_be32(commit_data + g->hash_len + 8) & 0x3;\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n@@ -317,6 +315,27 @@ int parse_commit_in_graph(struct commit *item)\n \treturn 0;\n }\n \n+static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c)\n+{\n+\tstruct object_id oid;\n+\tconst unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * (c->graph_pos);\n+\n+\thashcpy(oid.hash, commit_data);\n+\tc->tree = lookup_tree(&oid);\n+\n+\treturn c->tree;\n+}\n+\n+struct tree *get_commit_tree_in_graph(const struct commit *c)\n+{\n+\tif (c->tree)\n+\t\treturn c->tree;\n+\tif (c->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\t\tBUG(\"get_commit_tree_in_graph called from non-commit-graph commit\");\n+\n+\treturn load_tree_for_commit(commit_graph, (struct commit *)c);\n+}\n+\n static void write_graph_chunk_fanout(struct hashfile *f,\n \t\t\t\t     struct commit **commits,\n \t\t\t\t     int nr_commits)\ndiff --git a/commit-graph.h b/commit-graph.h\nindex e1d8580c98..3ab45818e2 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -17,6 +17,13 @@ char *get_commit_graph_filename(const char *obj_dir);\n  */\n int parse_commit_in_graph(struct commit *item);\n \n+/*\n+ * For performance reasons, a commit loaded from the graph does not\n+ * have a tree loaded until trying to consume it for the first time.\n+ * Load that tree into the commit and return the object.\n+ */\n+struct tree *get_commit_tree_in_graph(const struct commit *c);\n+\n struct commit_graph {\n \tint graph_fd;\n \ndiff --git a/commit.c b/commit.c\nindex d65c7b3b47..d4293ae8f6 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -298,12 +298,18 @@ void free_commit_buffer(struct commit *commit)\n \n struct tree *get_commit_tree(const struct commit *commit)\n {\n-\treturn commit->tree;\n+\tif (commit->tree || !commit->object.parsed)\n+\t\treturn commit->tree;\n+\n+\tif (commit->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\t\tBUG(\"commit has NULL tree, but was not loaded from commit-graph\");\n+\n+\treturn get_commit_tree_in_graph(commit);\n }\n \n struct object_id *get_commit_tree_oid(const struct commit *commit)\n {\n-\treturn &commit->tree->object.oid;\n+\treturn &get_commit_tree(commit)->object.oid;\n }\n \n const void *detach_commit_buffer(struct commit *commit, unsigned long *sizep)\n-- \n2.17.0.20.g9f30ba16e1\n\n"},{"id":"343683","messageId":"20180403120057.173849-3-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180403120057.173849-1-dstolee@microsoft.com","subject":"[PATCH 2/3] treewide: use get_commit_tree() for tree access","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-03T12:00:56Z","receivedAt":"2018-04-03T12:01:44Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Replace all direct accesses of the 'tree' member in 'struct commit'\nwith calls to get_commit_tree() or get_commit_tree_oid().\n\nThis patch was constructed starting with the following Coccinelle\nscript, then removing false-positives:\n\n@@\nexpression c;\n@@\n- &c->tree->object.oid\n+ get_commit_tree_oid(c)\n\n@@\nexpression c;\nsymbol m;\n@@\n- c->tree->object.oid.m\n+ get_commit_tree_oid(c)->m\n\n@@\nexpression c;\n@@\n- c->tree\n+ get_commit_tree(c)\n\nTo ensure all references were removed, the 'tree' member was renamed\nto 'tree_renamed' along with the few allowed accessors. A successful\ncompilation demonstrated a correct transformation.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n blame.c               | 18 +++++++++---------\n builtin/checkout.c    | 17 +++++++++--------\n builtin/diff.c        |  2 +-\n builtin/fast-export.c |  6 +++---\n builtin/log.c         |  4 ++--\n builtin/reflog.c      |  2 +-\n commit-graph.c        |  2 +-\n fsck.c                |  8 +++++---\n http-push.c           |  2 +-\n line-log.c            |  4 ++--\n list-objects.c        | 10 +++++-----\n log-tree.c            |  6 +++---\n merge-recursive.c     |  3 ++-\n notes-merge.c         |  8 ++++----\n packfile.c            |  2 +-\n pretty.c              |  5 +++--\n ref-filter.c          |  2 +-\n revision.c            |  8 ++++----\n sequencer.c           | 12 ++++++------\n sha1_name.c           |  2 +-\n tree.c                |  4 ++--\n walker.c              |  2 +-\n 22 files changed, 67 insertions(+), 62 deletions(-)\n\ndiff --git a/blame.c b/blame.c\nindex 200e0ad9a2..7f5700b324 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -553,10 +553,10 @@ static struct blame_origin *find_origin(struct commit *parent,\n \tdiff_setup_done(&diff_opts);\n \n \tif (is_null_oid(&origin->commit->object.oid))\n-\t\tdo_diff_cache(&parent->tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n-\t\t\t      &origin->commit->tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t      get_commit_tree_oid(origin->commit),\n \t\t\t      \"\", &diff_opts);\n \tdiffcore_std(&diff_opts);\n \n@@ -622,10 +622,10 @@ static struct blame_origin *find_rename(struct commit *parent,\n \tdiff_setup_done(&diff_opts);\n \n \tif (is_null_oid(&origin->commit->object.oid))\n-\t\tdo_diff_cache(&parent->tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n-\t\t\t      &origin->commit->tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t      get_commit_tree_oid(origin->commit),\n \t\t\t      \"\", &diff_opts);\n \tdiffcore_std(&diff_opts);\n \n@@ -1257,10 +1257,10 @@ static void find_copy_in_parent(struct blame_scoreboard *sb,\n \t\tdiff_opts.flags.find_copies_harder = 1;\n \n \tif (is_null_oid(&target->commit->object.oid))\n-\t\tdo_diff_cache(&parent->tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n-\t\t\t      &target->commit->tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t      get_commit_tree_oid(target->commit),\n \t\t\t      \"\", &diff_opts);\n \n \tif (!diff_opts.flags.find_copies_harder)\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex d76e13c852..0b448fd179 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -484,7 +484,8 @@ static int merge_working_tree(const struct checkout_opts *opts,\n \n \tresolve_undo_clear();\n \tif (opts->force) {\n-\t\tret = reset_tree(new_branch_info->commit->tree, opts, 1, writeout_error);\n+\t\tret = reset_tree(get_commit_tree(new_branch_info->commit),\n+\t\t\t\t opts, 1, writeout_error);\n \t\tif (ret)\n \t\t\treturn ret;\n \t} else {\n@@ -570,19 +571,19 @@ static int merge_working_tree(const struct checkout_opts *opts,\n \t\t\to.verbosity = 0;\n \t\t\twork = write_tree_from_memory(&o);\n \n-\t\t\tret = reset_tree(new_branch_info->commit->tree, opts, 1,\n-\t\t\t\t\t writeout_error);\n+\t\t\tret = reset_tree(get_commit_tree(new_branch_info->commit),\n+\t\t\t\t\t opts, 1, writeout_error);\n \t\t\tif (ret)\n \t\t\t\treturn ret;\n \t\t\to.ancestor = old_branch_info->name;\n \t\t\to.branch1 = new_branch_info->name;\n \t\t\to.branch2 = \"local\";\n-\t\t\tret = merge_trees(&o, new_branch_info->commit->tree, work,\n-\t\t\t\told_branch_info->commit->tree, &result);\n+\t\t\tret = merge_trees(&o, get_commit_tree(new_branch_info->commit),\n+\t\t\t\t\t  work, get_commit_tree(old_branch_info->commit), &result);\n \t\t\tif (ret < 0)\n \t\t\t\texit(128);\n-\t\t\tret = reset_tree(new_branch_info->commit->tree, opts, 0,\n-\t\t\t\t\t writeout_error);\n+\t\t\tret = reset_tree(get_commit_tree(new_branch_info->commit),\n+\t\t\t\t\t opts, 0, writeout_error);\n \t\t\tstrbuf_release(&o.obuf);\n \t\t\tif (ret)\n \t\t\t\treturn ret;\n@@ -1002,7 +1003,7 @@ static int parse_branchname_arg(int argc, const char **argv,\n \t\t*source_tree = parse_tree_indirect(rev);\n \t} else {\n \t\tparse_commit_or_die(new_branch_info->commit);\n-\t\t*source_tree = new_branch_info->commit->tree;\n+\t\t*source_tree = get_commit_tree(new_branch_info->commit);\n \t}\n \n \tif (!*source_tree)                   /* case (1): want a tree */\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 16bfb22f73..bfefff3a84 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -398,7 +398,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t\tif (!obj)\n \t\t\tdie(_(\"invalid object '%s' given.\"), name);\n \t\tif (obj->type == OBJ_COMMIT)\n-\t\t\tobj = &((struct commit *)obj)->tree->object;\n+\t\t\tobj = &get_commit_tree(((struct commit *)obj))->object;\n \n \t\tif (obj->type == OBJ_TREE) {\n \t\t\tobj->flags |= flags;\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 27b2cc138e..c1304234cd 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -578,11 +578,11 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,\n \t    get_object_mark(&commit->parents->item->object) != 0 &&\n \t    !full_tree) {\n \t\tparse_commit_or_die(commit->parents->item);\n-\t\tdiff_tree_oid(&commit->parents->item->tree->object.oid,\n-\t\t\t      &commit->tree->object.oid, \"\", &rev->diffopt);\n+\t\tdiff_tree_oid(get_commit_tree_oid(commit->parents->item),\n+\t\t\t      get_commit_tree_oid(commit), \"\", &rev->diffopt);\n \t}\n \telse\n-\t\tdiff_root_tree_oid(&commit->tree->object.oid,\n+\t\tdiff_root_tree_oid(get_commit_tree_oid(commit),\n \t\t\t\t   \"\", &rev->diffopt);\n \n \t/* Export the referenced blobs, and remember the marks. */\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 94ee177d56..25b4cb3347 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1067,8 +1067,8 @@ static void make_cover_letter(struct rev_info *rev, int use_stdout,\n \n \tdiff_setup_done(&opts);\n \n-\tdiff_tree_oid(&origin->tree->object.oid,\n-\t\t      &head->tree->object.oid,\n+\tdiff_tree_oid(get_commit_tree_oid(origin),\n+\t\t      get_commit_tree_oid(head),\n \t\t      \"\", &opts);\n \tdiffcore_std(&opts);\n \tdiff_flush(&opts);\ndiff --git a/builtin/reflog.c b/builtin/reflog.c\nindex 4719a5354c..88d0c8378c 100644\n--- a/builtin/reflog.c\n+++ b/builtin/reflog.c\n@@ -154,7 +154,7 @@ static int commit_is_complete(struct commit *commit)\n \t\tfor (i = 0; i < found.nr; i++) {\n \t\t\tstruct commit *c =\n \t\t\t\t(struct commit *)found.objects[i].item;\n-\t\t\tif (!tree_is_complete(&c->tree->object.oid)) {\n+\t\t\tif (!tree_is_complete(get_commit_tree_oid(c))) {\n \t\t\t\tis_incomplete = 1;\n \t\t\t\tc->object.flags |= INCOMPLETE;\n \t\t\t}\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 1fc63d541b..3080a87940 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -369,7 +369,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n \t\tuint32_t packedDate[2];\n \n \t\tparse_commit(*list);\n-\t\thashwrite(f, (*list)->tree->object.oid.hash, hash_len);\n+\t\thashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);\n \n \t\tparent = (*list)->parents;\n \ndiff --git a/fsck.c b/fsck.c\nindex 5c8c12dde3..695fd71b13 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -396,9 +396,11 @@ static int fsck_walk_commit(struct commit *commit, void *data, struct fsck_optio\n \n \tname = get_object_name(options, &commit->object);\n \tif (name)\n-\t\tput_object_name(options, &commit->tree->object, \"%s:\", name);\n+\t\tput_object_name(options, &get_commit_tree(commit)->object,\n+\t\t\t\t\"%s:\", name);\n \n-\tresult = options->walk((struct object *)commit->tree, OBJ_TREE, data, options);\n+\tresult = options->walk((struct object *)get_commit_tree(commit),\n+\t\t\t       OBJ_TREE, data, options);\n \tif (result < 0)\n \t\treturn result;\n \tres = result;\n@@ -772,7 +774,7 @@ static int fsck_commit_buffer(struct commit *commit, const char *buffer,\n \terr = fsck_ident(&buffer, &commit->object, options);\n \tif (err)\n \t\treturn err;\n-\tif (!commit->tree) {\n+\tif (!get_commit_tree(commit)) {\n \t\terr = report(options, &commit->object, FSCK_MSG_BAD_TREE, \"could not load commit's tree %s\", sha1_to_hex(tree_sha1));\n \t\tif (err)\n \t\t\treturn err;\ndiff --git a/http-push.c b/http-push.c\nindex 7dcd9daf62..53a217291e 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1330,7 +1330,7 @@ static int get_delta(struct rev_info *revs, struct remote_lock *lock)\n \tint count = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tp = process_tree(commit->tree, p);\n+\t\tp = process_tree(get_commit_tree(commit), p);\n \t\tcommit->object.flags |= LOCAL;\n \t\tif (!(commit->object.flags & UNINTERESTING))\n \t\t\tcount += add_send_request(&commit->object, lock);\ndiff --git a/line-log.c b/line-log.c\nindex cdc2257db5..437d44c00a 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -817,8 +817,8 @@ static void queue_diffs(struct line_log_data *range,\n \tassert(commit);\n \n \tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n-\tdiff_tree_oid(parent ? &parent->tree->object.oid : NULL,\n-\t\t      &commit->tree->object.oid, \"\", opt);\n+\tdiff_tree_oid(parent ? get_commit_tree_oid(parent) : NULL,\n+\t\t      get_commit_tree_oid(commit), \"\", opt);\n \tif (opt->detect_rename) {\n \t\tfilter_diffs_for_paths(range, 1);\n \t\tif (diff_might_be_rename())\ndiff --git a/list-objects.c b/list-objects.c\nindex 168bef688a..3eec510357 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -195,7 +195,7 @@ static void mark_edge_parents_uninteresting(struct commit *commit,\n \t\tstruct commit *parent = parents->item;\n \t\tif (!(parent->object.flags & UNINTERESTING))\n \t\t\tcontinue;\n-\t\tmark_tree_uninteresting(parent->tree);\n+\t\tmark_tree_uninteresting(get_commit_tree(parent));\n \t\tif (revs->edge_hint && !(parent->object.flags & SHOWN)) {\n \t\t\tparent->object.flags |= SHOWN;\n \t\t\tshow_edge(parent);\n@@ -212,7 +212,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\tstruct commit *commit = list->item;\n \n \t\tif (commit->object.flags & UNINTERESTING) {\n-\t\t\tmark_tree_uninteresting(commit->tree);\n+\t\t\tmark_tree_uninteresting(get_commit_tree(commit));\n \t\t\tif (revs->edge_hint_aggressive && !(commit->object.flags & SHOWN)) {\n \t\t\t\tcommit->object.flags |= SHOWN;\n \t\t\t\tshow_edge(commit);\n@@ -227,7 +227,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\t\tstruct commit *commit = (struct commit *)obj;\n \t\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n \t\t\t\tcontinue;\n-\t\t\tmark_tree_uninteresting(commit->tree);\n+\t\t\tmark_tree_uninteresting(get_commit_tree(commit));\n \t\t\tif (!(obj->flags & SHOWN)) {\n \t\t\t\tobj->flags |= SHOWN;\n \t\t\t\tshow_edge(commit);\n@@ -300,8 +300,8 @@ static void do_traverse(struct rev_info *revs,\n \t\t * an uninteresting boundary commit may not have its tree\n \t\t * parsed yet, but we are not going to show them anyway\n \t\t */\n-\t\tif (commit->tree)\n-\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (get_commit_tree(commit))\n+\t\t\tadd_pending_tree(revs, get_commit_tree(commit));\n \t\tshow_commit(commit, show_data);\n \n \t\tif (revs->tree_blobs_in_commit_order)\ndiff --git a/log-tree.c b/log-tree.c\nindex bdf23c5f7b..c106bd70df 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -806,7 +806,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\treturn 0;\n \n \tparse_commit_or_die(commit);\n-\toid = &commit->tree->object.oid;\n+\toid = get_commit_tree_oid(commit);\n \n \t/* Root commit? */\n \tparents = get_saved_parents(opt, commit);\n@@ -831,7 +831,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\t\t * we merged _in_.\n \t\t\t */\n \t\t\tparse_commit_or_die(parents->item);\n-\t\t\tdiff_tree_oid(&parents->item->tree->object.oid,\n+\t\t\tdiff_tree_oid(get_commit_tree_oid(parents->item),\n \t\t\t\t      oid, \"\", &opt->diffopt);\n \t\t\tlog_tree_diff_flush(opt);\n \t\t\treturn !opt->loginfo;\n@@ -846,7 +846,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\tstruct commit *parent = parents->item;\n \n \t\tparse_commit_or_die(parent);\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n \t\t\t      oid, \"\", &opt->diffopt);\n \t\tlog_tree_diff_flush(opt);\n \ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 869092f7b9..050729665f 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -2154,7 +2154,8 @@ int merge_recursive(struct merge_options *o,\n \t\tread_cache();\n \n \to->ancestor = \"merged common ancestors\";\n-\tclean = merge_trees(o, h1->tree, h2->tree, merged_common_ancestors->tree,\n+\tclean = merge_trees(o, get_commit_tree(h1), get_commit_tree(h2),\n+\t\t\t    get_commit_tree(merged_common_ancestors),\n \t\t\t    &mrtree);\n \tif (clean < 0) {\n \t\tflush_output(o);\ndiff --git a/notes-merge.c b/notes-merge.c\nindex c09c5e0e47..65cf731106 100644\n--- a/notes-merge.c\n+++ b/notes-merge.c\n@@ -600,14 +600,14 @@ int notes_merge(struct notes_merge_options *o,\n \t\t\tprintf(\"No merge base found; doing history-less merge\\n\");\n \t} else if (!bases->next) {\n \t\tbase_oid = &bases->item->object.oid;\n-\t\tbase_tree_oid = &bases->item->tree->object.oid;\n+\t\tbase_tree_oid = get_commit_tree_oid(bases->item);\n \t\tif (o->verbosity >= 4)\n \t\t\tprintf(\"One merge base found (%.7s)\\n\",\n \t\t\t       oid_to_hex(base_oid));\n \t} else {\n \t\t/* TODO: How to handle multiple merge-bases? */\n \t\tbase_oid = &bases->item->object.oid;\n-\t\tbase_tree_oid = &bases->item->tree->object.oid;\n+\t\tbase_tree_oid = get_commit_tree_oid(bases->item);\n \t\tif (o->verbosity >= 3)\n \t\t\tprintf(\"Multiple merge bases found. Using the first \"\n \t\t\t\t\"(%.7s)\\n\", oid_to_hex(base_oid));\n@@ -634,8 +634,8 @@ int notes_merge(struct notes_merge_options *o,\n \t\tgoto found_result;\n \t}\n \n-\tresult = merge_from_diffs(o, base_tree_oid, &local->tree->object.oid,\n-\t\t\t\t  &remote->tree->object.oid, local_tree);\n+\tresult = merge_from_diffs(o, base_tree_oid, get_commit_tree_oid(local),\n+\t\t\t\t  get_commit_tree_oid(remote), local_tree);\n \n \tif (result != 0) { /* non-trivial merge (with or without conflicts) */\n \t\t/* Commit (partial) result */\ndiff --git a/packfile.c b/packfile.c\nindex b1d33b646a..88ba819151 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1925,7 +1925,7 @@ static int add_promisor_object(const struct object_id *oid,\n \t\tstruct commit *commit = (struct commit *) obj;\n \t\tstruct commit_list *parents = commit->parents;\n \n-\t\toidset_insert(set, &commit->tree->object.oid);\n+\t\toidset_insert(set, get_commit_tree_oid(commit));\n \t\tfor (; parents; parents = parents->next)\n \t\t\toidset_insert(set, &parents->item->object.oid);\n \t} else if (obj->type == OBJ_TAG) {\ndiff --git a/pretty.c b/pretty.c\nindex f7ce490230..74d6f69605 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -1161,10 +1161,11 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n \t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n-\t\tstrbuf_addstr(sb, oid_to_hex(&commit->tree->object.oid));\n+\t\tstrbuf_addstr(sb, oid_to_hex(get_commit_tree_oid(commit)));\n \t\treturn 1;\n \tcase 't':\t\t/* abbreviated tree hash */\n-\t\tstrbuf_add_unique_abbrev(sb, commit->tree->object.oid.hash,\n+\t\tstrbuf_add_unique_abbrev(sb,\n+\t\t\t\t\t get_commit_tree(commit)->object.oid.hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n \t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 45fc56216a..e201bf60c6 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -815,7 +815,7 @@ static void grab_commit_values(struct atom_value *val, int deref, struct object\n \t\tif (deref)\n \t\t\tname++;\n \t\tif (!strcmp(name, \"tree\")) {\n-\t\t\tv->s = xstrdup(oid_to_hex(&commit->tree->object.oid));\n+\t\t\tv->s = xstrdup(oid_to_hex(get_commit_tree_oid(commit)));\n \t\t}\n \t\telse if (!strcmp(name, \"numparent\")) {\n \t\t\tv->value = commit_list_count(commit->parents);\ndiff --git a/revision.c b/revision.c\nindex b42c836d7a..496db63b4b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -440,8 +440,8 @@ static void file_change(struct diff_options *options,\n static int rev_compare_tree(struct rev_info *revs,\n \t\t\t    struct commit *parent, struct commit *commit)\n {\n-\tstruct tree *t1 = parent->tree;\n-\tstruct tree *t2 = commit->tree;\n+\tstruct tree *t1 = get_commit_tree(parent);\n+\tstruct tree *t2 = get_commit_tree(commit);\n \n \tif (!t1)\n \t\treturn REV_TREE_NEW;\n@@ -477,7 +477,7 @@ static int rev_compare_tree(struct rev_info *revs,\n static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n {\n \tint retval;\n-\tstruct tree *t1 = commit->tree;\n+\tstruct tree *t1 = get_commit_tree(commit);\n \n \tif (!t1)\n \t\treturn 0;\n@@ -615,7 +615,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tif (!revs->prune)\n \t\treturn;\n \n-\tif (!commit->tree)\n+\tif (!get_commit_tree(commit))\n \t\treturn;\n \n \tif (!commit->parents) {\ndiff --git a/sequencer.c b/sequencer.c\nindex f9d1001dee..a5798b16d3 100644\n--- a/sequencer.c\n+++ b/sequencer.c\n@@ -499,8 +499,8 @@ static int do_recursive_merge(struct commit *base, struct commit *next,\n \to.show_rename_progress = 1;\n \n \thead_tree = parse_tree_indirect(head);\n-\tnext_tree = next ? next->tree : empty_tree();\n-\tbase_tree = base ? base->tree : empty_tree();\n+\tnext_tree = next ? get_commit_tree(next) : empty_tree();\n+\tbase_tree = base ? get_commit_tree(base) : empty_tree();\n \n \tfor (xopt = opts->xopts; xopt != opts->xopts + opts->xopts_nr; xopt++)\n \t\tparse_merge_opt(&o, *xopt);\n@@ -561,7 +561,7 @@ static int is_index_unchanged(void)\n \t\t\treturn error(_(\"unable to update cache tree\"));\n \n \treturn !oidcmp(&active_cache_tree->oid,\n-\t\t       &head_commit->tree->object.oid);\n+\t\t       get_commit_tree_oid(head_commit));\n }\n \n static int write_author_script(const char *message)\n@@ -1118,7 +1118,7 @@ static int try_to_commit(struct strbuf *msg, const char *author,\n \t}\n \n \tif (!(flags & ALLOW_EMPTY) && !oidcmp(current_head ?\n-\t\t\t\t\t      &current_head->tree->object.oid :\n+\t\t\t\t\t      get_commit_tree_oid(current_head) :\n \t\t\t\t\t      &empty_tree_oid, &tree)) {\n \t\tres = 1; /* run 'git commit' to display error message */\n \t\tgoto out;\n@@ -1216,12 +1216,12 @@ static int is_original_commit_empty(struct commit *commit)\n \t\tif (parse_commit(parent))\n \t\t\treturn error(_(\"could not parse parent commit %s\"),\n \t\t\t\toid_to_hex(&parent->object.oid));\n-\t\tptree_oid = &parent->tree->object.oid;\n+\t\tptree_oid = get_commit_tree_oid(parent);\n \t} else {\n \t\tptree_oid = the_hash_algo->empty_tree; /* commit is root */\n \t}\n \n-\treturn !oidcmp(ptree_oid, &commit->tree->object.oid);\n+\treturn !oidcmp(ptree_oid, get_commit_tree_oid(commit));\n }\n \n /*\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 735c1c0b8e..1608b51c3c 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -896,7 +896,7 @@ struct object *peel_to_type(const char *name, int namelen,\n \t\tif (o->type == OBJ_TAG)\n \t\t\to = ((struct tag*) o)->tagged;\n \t\telse if (o->type == OBJ_COMMIT)\n-\t\t\to = &(((struct commit *) o)->tree->object);\n+\t\t\to = &get_commit_tree((struct commit *) o)->object;\n \t\telse {\n \t\t\tif (name)\n \t\t\t\terror(\"%.*s: expected %s type, but the object \"\ndiff --git a/tree.c b/tree.c\nindex b224115e0f..dec53f3eca 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -109,7 +109,7 @@ static int read_tree_1(struct tree *tree, struct strbuf *base,\n \t\t\t\t    oid_to_hex(entry.oid),\n \t\t\t\t    base->buf, entry.path);\n \n-\t\t\toidcpy(&oid, &commit->tree->object.oid);\n+\t\t\toidcpy(&oid, get_commit_tree_oid(commit));\n \t\t}\n \t\telse\n \t\t\tcontinue;\n@@ -248,7 +248,7 @@ struct tree *parse_tree_indirect(const struct object_id *oid)\n \t\tif (obj->type == OBJ_TREE)\n \t\t\treturn (struct tree *) obj;\n \t\telse if (obj->type == OBJ_COMMIT)\n-\t\t\tobj = &(((struct commit *) obj)->tree->object);\n+\t\t\tobj = &(get_commit_tree(((struct commit *)obj))->object);\n \t\telse if (obj->type == OBJ_TAG)\n \t\t\tobj = ((struct tag *) obj)->tagged;\n \t\telse\ndiff --git a/walker.c b/walker.c\nindex dffb9c8e37..f51b855872 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -87,7 +87,7 @@ static int process_commit(struct walker *walker, struct commit *commit)\n \twalker_say(walker, \"walk %s\\n\", oid_to_hex(&commit->object.oid));\n \n \tif (walker->get_tree) {\n-\t\tif (process(walker, &commit->tree->object))\n+\t\tif (process(walker, &get_commit_tree(commit)->object))\n \t\t\treturn -1;\n \t\tif (!walker->get_all)\n \t\t\twalker->get_tree = 0;\n-- \n2.17.0.20.g9f30ba16e1\n\n"},{"id":"343684","messageId":"00d5cd22-3492-73cf-3493-1f6f1ec15922@gmail.com","threadId":"48210","inReplyTo":"20180403120057.173849-1-dstolee@microsoft.com","subject":"Re: [PATCH 0/3] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-04-03T12:15:09Z","receivedAt":"2018-04-03T12:15:16Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/3/2018 8:00 AM, Derrick Stolee wrote:\n> There are several commit-graph walks that require loading many commits\n> but never walk the trees reachable from those commits. However, the\n> current logic in parse_commit() requires the root tree to be loaded.\n> This only uses lookup_tree(), but when reading commits from the commit-\n> graph file, the hashcpy() to load the root tree hash and the time spent\n> checking the object cache take more time than parsing the rest of the\n> commit.\n>\n> In this patch series, all direct references to accessing the 'tree'\n> member of struct commit are replaced instead by one of the following\n> methods:\n>\n> \tstruct tree *get_commit_tree(struct commit *)\n> \tstruct object_id *get_commit_tree_oid(struct commit *)\n>\n> This replacement was assisted by a Coccinelle script, but the 'tree'\n> member is overloaded in other types, so the script gave false-positives\n> that were removed from the diff.\n>\n> After all access is restricted to use these methods, we can then\n> change the postcondition of parse_commit_in_graph() to allow 'tree'\n> to be NULL. If the tree is accessed later, we can load the tree's\n> OID from the commit-graph in constant time and perform the lookup_tree().\n>\n> On the Linux repository, performance tests were run for the following\n> command:\n>\n>      git log --graph --oneline -1000\n>\n> Before: 0.83s\n> After:  0.65s\n> Rel %: -21.6%\n>\n> Adding '-- kernel/' to the command requires loading the root tree\n> for every commit that is walked. There was no measureable performance\n> change as a result of this patch.\n>\n> This patch series depends on v7 of ds/commit-graph.\n>\n> Derrick Stolee (3):\n>    commit: create get_commit_tree() method\n>    treewide: use get_commit_tree() for tree access\n>    commit-graph: lazy-load trees\n>\n\nThis patch series is also available as a GitHub pull request [1]\n\n[1] https://github.com/derrickstolee/git/pull/4\n"},{"id":"343687","messageId":"20180403130615.GA18824@sigill.intra.peff.net","threadId":"48210","inReplyTo":"20180403120057.173849-1-dstolee@microsoft.com","subject":"Re: [PATCH 0/3] Lazy-load trees when reading commit-graph","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-04-03T13:06:15Z","receivedAt":"2018-04-03T13:06:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 03, 2018 at 08:00:54AM -0400, Derrick Stolee wrote:\n\n> There are several commit-graph walks that require loading many commits\n> but never walk the trees reachable from those commits. However, the\n> current logic in parse_commit() requires the root tree to be loaded.\n> This only uses lookup_tree(), but when reading commits from the commit-\n> graph file, the hashcpy() to load the root tree hash and the time spent\n> checking the object cache take more time than parsing the rest of the\n> commit.\n> \n> In this patch series, all direct references to accessing the 'tree'\n> member of struct commit are replaced instead by one of the following\n> methods:\n> \n> \tstruct tree *get_commit_tree(struct commit *)\n> \tstruct object_id *get_commit_tree_oid(struct commit *)\n\nThis seems like a pretty sane thing to do. There may still be a few\nparts of the code, notably fsck, that are reliant on a \"struct object\"\nhaving been instantiated to determine whether an object is \"used\".  I\ntried to clean that up around the time of c2d17b3b6e (fsck: check\nHAS_OBJ more consistently, 2017-01-16), but I won't be surprised if\nthere's still some hidden assumptions.\n\nI peeked at the fsck.c parts of patch 2, and it looks like we may be OK,\nsince you use get_commit_tree() during the walk.\n\n> This replacement was assisted by a Coccinelle script, but the 'tree'\n> member is overloaded in other types, so the script gave false-positives\n> that were removed from the diff.\n\nThat catches any existing in-tree callers, but not any topics in flight.\nWe could add the Coccinelle script and re-run it to catch any future\nones. But perhaps simpler still: can we rename the \"tree\" member to\n\"maybe_tree\" or something, since nobody should be accessing it directly?\nThat will give us a compile error if an older topic is merged.\n\n> On the Linux repository, performance tests were run for the following\n> command:\n> \n>     git log --graph --oneline -1000\n> \n> Before: 0.83s\n> After:  0.65s\n> Rel %: -21.6%\n\nNeat.\n\nNot strictly related, but I happened across another thing today that\nmight be worth investigating here. We allocate \"struct commit\" in these\nnice big allocation blocks. But then for every commit we allocate at\nleast one \"struct commit_list\" to store the parent pointer.\n\nI was looking at this from a memory consumption angle (I found a\npathological repository full of single-parent commits, and this wastes\nan extra 16 bytes plus malloc overhead for every 64-byte \"struct\ncommit\").\n\nBut I wonder if it could also have non-negligible overhead in calling\nmalloc() for your case, since you've optimized out so much of the rest\nof the work.\n\nI'm not sure what the exact solution would be, but I imagine something\nlike variable-sized \"struct commit\"s with the parent pointers embedded,\nwith some kind of flag to indicate the number of parents (and probably\nsome fallback to break out to a linked list for extreme cases of more\nthan 2 parents).  It may end up pretty invasive, though, as there's a\nlot of open-coded traversals of that parent list.\n\nAnyway, not anything to do with this patch, but food for thought as you\nmicro-optimize these traversals.\n\n-Peff\n"},{"id":"343690","messageId":"007c630a-0df8-803c-b637-fb5ccefa7b7c@gmail.com","threadId":"48210","inReplyTo":"20180403130615.GA18824@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-04-03T13:14:50Z","receivedAt":"2018-04-03T13:15:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/3/2018 9:06 AM, Jeff King wrote:\n> On Tue, Apr 03, 2018 at 08:00:54AM -0400, Derrick Stolee wrote:\n>\n>> There are several commit-graph walks that require loading many commits\n>> but never walk the trees reachable from those commits. However, the\n>> current logic in parse_commit() requires the root tree to be loaded.\n>> This only uses lookup_tree(), but when reading commits from the commit-\n>> graph file, the hashcpy() to load the root tree hash and the time spent\n>> checking the object cache take more time than parsing the rest of the\n>> commit.\n>>\n>> In this patch series, all direct references to accessing the 'tree'\n>> member of struct commit are replaced instead by one of the following\n>> methods:\n>>\n>> \tstruct tree *get_commit_tree(struct commit *)\n>> \tstruct object_id *get_commit_tree_oid(struct commit *)\n> This seems like a pretty sane thing to do. There may still be a few\n> parts of the code, notably fsck, that are reliant on a \"struct object\"\n> having been instantiated to determine whether an object is \"used\".  I\n> tried to clean that up around the time of c2d17b3b6e (fsck: check\n> HAS_OBJ more consistently, 2017-01-16), but I won't be surprised if\n> there's still some hidden assumptions.\n>\n> I peeked at the fsck.c parts of patch 2, and it looks like we may be OK,\n> since you use get_commit_tree() during the walk.\n>\n>> This replacement was assisted by a Coccinelle script, but the 'tree'\n>> member is overloaded in other types, so the script gave false-positives\n>> that were removed from the diff.\n> That catches any existing in-tree callers, but not any topics in flight.\n> We could add the Coccinelle script and re-run it to catch any future\n> ones. But perhaps simpler still: can we rename the \"tree\" member to\n> \"maybe_tree\" or something, since nobody should be accessing it directly?\n> That will give us a compile error if an older topic is merged.\n\nThat's a good idea. I can reorg in v2 to rename 'tree' to 'maybe_tree' \n(and add an explicit comment that 'maybe_tree' could be NULL, so don't \nreference it directly). The check that the rename patch is correct is \nsimply \"does it compile?\" Then Coccinelle could do the transfer of \n\"c->maybe_tree\" to \"get_commit_tree(c)\" safely, and can be added to the \nscripts.\n\nI guess one caveat is to not include the mutators (c->maybe_tree = ...), \nbut that's probably something Coccinelle can do.\n\n>\n>> On the Linux repository, performance tests were run for the following\n>> command:\n>>\n>>      git log --graph --oneline -1000\n>>\n>> Before: 0.83s\n>> After:  0.65s\n>> Rel %: -21.6%\n> Neat.\n>\n> Not strictly related, but I happened across another thing today that\n> might be worth investigating here. We allocate \"struct commit\" in these\n> nice big allocation blocks. But then for every commit we allocate at\n> least one \"struct commit_list\" to store the parent pointer.\n>\n> I was looking at this from a memory consumption angle (I found a\n> pathological repository full of single-parent commits, and this wastes\n> an extra 16 bytes plus malloc overhead for every 64-byte \"struct\n> commit\").\n>\n> But I wonder if it could also have non-negligible overhead in calling\n> malloc() for your case, since you've optimized out so much of the rest\n> of the work.\n\nThat is a pattern I'm seeing: we strip out one bit and something else \nshows up as a hot spot. This game of whack-a-mole is quite productive.\n\n> I'm not sure what the exact solution would be, but I imagine something\n> like variable-sized \"struct commit\"s with the parent pointers embedded,\n> with some kind of flag to indicate the number of parents (and probably\n> some fallback to break out to a linked list for extreme cases of more\n> than 2 parents).  It may end up pretty invasive, though, as there's a\n> lot of open-coded traversals of that parent list.\n>\n> Anyway, not anything to do with this patch, but food for thought as you\n> micro-optimize these traversals.\n\nOne other thing that I've been thinking about is that 'struct commit' is \nso much bigger than the other structs in 'union any_object'. This means \nthat the object cache, which I think creates blocks of 'union \nany_object' for memory-alignment reasons, is overly bloated. This would \nbe especially true when walking many more trees than commits.\n\nPerhaps there are other memory concerns in that case (such as cached \nbuffers) that the 'union any_object' is not a concern, but it is worth \nthinking about as we brainstorm how to reduce the parent-list memory.\n\nThanks,\n-Stolee\n"},{"id":"343733","messageId":"CAGZ79kZ0XZRiKcJG-5Ckd=XjE-3GfGHkNuyu4590OyfGPve4Rg@mail.gmail.com","threadId":"48210","inReplyTo":"20180403120057.173849-4-dstolee@microsoft.com","subject":"Re: [PATCH 3/3] commit-graph: lazy-load trees","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-04-03T18:00:21Z","receivedAt":"2018-04-03T18:00:28Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Apr 3, 2018 at 5:00 AM, Derrick Stolee <dstolee@microsoft.com> wrote:\n> The commit-graph file provides quick access to commit data, including\n> the OID of the root tree for each commit in the graph. When performing\n> a deep commit-graph walk, we may not need to load most of the trees\n> for these commits.\n>\n> Delay loading the tree object for a commit loaded from the graph\n> until requested via get_commit_tree(). Do not lazy-load trees for\n> commits not in the graph, since that requires duplicate parsing\n> and the relative peformance improvement when trees are not needed\n> is small.\n>\n> On the Linux repository, performance tests were run for the following\n> command:\n>\n>         git log --graph --oneline -1000\n>\n> Before: 0.83s\n> After:  0.65s\n> Rel %: -21.6%\n\nThis is an awesome speedup.\n\n>\n> Adding '-- kernel/' to the command requires loading the root tree\n> for every commit that is walked.\n\nand as the walk prunes those commits that do not touch kernel/\nwhich from my quick glance is the real core thing. Linus' announcements\nclaim that > 50% is drivers, networking and documentation[1].\nSo the \"-- kernel/\" walk needs to walk twice as many commits to find\na thousand commits that actually touch kernel/ ?\n\n[1] http://lkml.iu.edu/hypermail/linux/kernel/1801.3/02794.html\nhttp://lkml.iu.edu/hypermail/linux/kernel/1803.3/00580.html\n\n> There was no measureable performance\n> change as a result of this patch.\n\n... which means that the walking itself is really fast now and the\ndominating effects are setup and checking the tree?\n\nIs git smart enough to not load the root tree for \"log -- ./\" or\nwould we get the desired performance numbers from that?\n\n> @@ -317,6 +315,27 @@ int parse_commit_in_graph(struct commit *item)\n>         return 0;\n>  }\n>\n> +static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c)\n> +{\n> +       struct object_id oid;\n> +       const unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * (c->graph_pos);\n\nWhat is 16? (I imagine it is the \"length of the row\" - g->hash_len ?)\nWould it make sense to have a constant/define for an entire row instead?\n(By any chance what is the meaning of GRAPH_DATA_WIDTH, which is 36?\nThat is defined but never used.)\n\n> +struct tree *get_commit_tree_in_graph(const struct commit *c)\n> +{\n> +       if (c->tree)\n> +               return c->tree;\n\nThis double checking is defensive programming, in case someone\ndoesn't check themselves (as get_commit_tree does below).\n\nok.\n\n> @@ -17,6 +17,13 @@ char *get_commit_graph_filename(const char *obj_dir);\n>   */\n>  int parse_commit_in_graph(struct commit *item);\n>\n> +/*\n> + * For performance reasons, a commit loaded from the graph does not\n> + * have a tree loaded until trying to consume it for the first time.\n\nThat is the theme of this series/patch, but do we need to write it down\ninto the codebase? I'd be inclined to omit this part and only go with:\n\n  Load the root tree of a commit and return the tree.\n\n>  struct tree *get_commit_tree(const struct commit *commit)\n>  {\n> -       return commit->tree;\n> +       if (commit->tree || !commit->object.parsed)\n\nI understand to return the tree from the commit\nwhen we have the tree in the commit object (the first\npart).\n\nBut 'when we have not (yet) parsed the commit object',\nwe also just return its tree? Could you explain the\nsecond part of the condition?\nIs that for commits that are not part of the commit graph?\n(But then why does it need to be negated?)\n\nThanks,\nStefan\n"},{"id":"343737","messageId":"aa3340e8-dbd9-7cf7-1711-a6f675bf6b8c@gmail.com","threadId":"48210","inReplyTo":"CAGZ79kZ0XZRiKcJG-5Ckd=XjE-3GfGHkNuyu4590OyfGPve4Rg@mail.gmail.com","subject":"Re: [PATCH 3/3] commit-graph: lazy-load trees","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-04-03T18:22:23Z","receivedAt":"2018-04-03T18:23:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/3/2018 2:00 PM, Stefan Beller wrote:\n> On Tue, Apr 3, 2018 at 5:00 AM, Derrick Stolee <dstolee@microsoft.com> wrote:\n>> The commit-graph file provides quick access to commit data, including\n>> the OID of the root tree for each commit in the graph. When performing\n>> a deep commit-graph walk, we may not need to load most of the trees\n>> for these commits.\n>>\n>> Delay loading the tree object for a commit loaded from the graph\n>> until requested via get_commit_tree(). Do not lazy-load trees for\n>> commits not in the graph, since that requires duplicate parsing\n>> and the relative peformance improvement when trees are not needed\n>> is small.\n>>\n>> On the Linux repository, performance tests were run for the following\n>> command:\n>>\n>>          git log --graph --oneline -1000\n>>\n>> Before: 0.83s\n>> After:  0.65s\n>> Rel %: -21.6%\n> This is an awesome speedup.\n>\n>> Adding '-- kernel/' to the command requires loading the root tree\n>> for every commit that is walked.\n> and as the walk prunes those commits that do not touch kernel/\n> which from my quick glance is the real core thing. Linus' announcements\n> claim that > 50% is drivers, networking and documentation[1].\n> So the \"-- kernel/\" walk needs to walk twice as many commits to find\n> a thousand commits that actually touch kernel/ ?\n>\n> [1] http://lkml.iu.edu/hypermail/linux/kernel/1801.3/02794.html\n> http://lkml.iu.edu/hypermail/linux/kernel/1803.3/00580.html\n>\n>> There was no measureable performance\n>> change as a result of this patch.\n> ... which means that the walking itself is really fast now and the\n> dominating effects are setup and checking the tree?\n\nYeah. I was concerned that since we take two accesses into the \ncommit-graph file that we could measurably slow down cases where we need \nto load the trees. That is not an issue since we will likely parse the \ntree after loading, and parsing is much slower than these commit-graph \naccesses.\n\n\n> Is git smart enough to not load the root tree for \"log -- ./\" or\n> would we get the desired performance numbers from that?\n\nI wonder, since it only really needs the OID of the root tree to \ndetermine TREESAME. If it cares about following TREESAME relationships \non ./, then it should do that.\n\n>\n>> @@ -317,6 +315,27 @@ int parse_commit_in_graph(struct commit *item)\n>>          return 0;\n>>   }\n>>\n>> +static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c)\n>> +{\n>> +       struct object_id oid;\n>> +       const unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * (c->graph_pos);\n> What is 16? (I imagine it is the \"length of the row\" - g->hash_len ?)\n> Would it make sense to have a constant/define for an entire row instead?\n> (By any chance what is the meaning of GRAPH_DATA_WIDTH, which is 36?\n> That is defined but never used.)\n\nYeah, I should use GRAPH_DATA_WIDTH here instead.\n\n>\n>> +struct tree *get_commit_tree_in_graph(const struct commit *c)\n>> +{\n>> +       if (c->tree)\n>> +               return c->tree;\n> This double checking is defensive programming, in case someone\n> doesn't check themselves (as get_commit_tree does below).\n>\n> ok.\n>\n>> @@ -17,6 +17,13 @@ char *get_commit_graph_filename(const char *obj_dir);\n>>    */\n>>   int parse_commit_in_graph(struct commit *item);\n>>\n>> +/*\n>> + * For performance reasons, a commit loaded from the graph does not\n>> + * have a tree loaded until trying to consume it for the first time.\n> That is the theme of this series/patch, but do we need to write it down\n> into the codebase? I'd be inclined to omit this part and only go with:\n>\n>    Load the root tree of a commit and return the tree.\n\nOK.\n\n>\n>>   struct tree *get_commit_tree(const struct commit *commit)\n>>   {\n>> -       return commit->tree;\n>> +       if (commit->tree || !commit->object.parsed)\n> I understand to return the tree from the commit\n> when we have the tree in the commit object (the first\n> part).\n>\n> But 'when we have not (yet) parsed the commit object',\n> we also just return its tree? Could you explain the\n> second part of the condition?\n> Is that for commits that are not part of the commit graph?\n> (But then why does it need to be negated?)\n\nSome callers check the value of 'commit->tree' without a guarantee that \nthe commit was parsed. In this case, the way to preserve the existing \nbehavior is to continue returning NULL. If I remove the \"|| \n!commit->object.parsed\" then the BUG(\"commit has NULL tree, but was not \nloaded from commit-graph\") is hit in these two tests:\n\nt6012-rev-list-simplify.sh\nt6110-rev-list-sparse.sh\n\nI prefer to keep the BUG() statement and instead use this if statement. \nIf someone has more clarity on why this is a good existing behavior, \nthen please chime in.\n\nThanks,\n-Stolee\n"},{"id":"343748","messageId":"CAGZ79kZTbDFBcw1MJeYyc_Ge1ZGZzRMVG7dhXEt9MjM9YAcTVA@mail.gmail.com","threadId":"48210","inReplyTo":"aa3340e8-dbd9-7cf7-1711-a6f675bf6b8c@gmail.com","subject":"Re: [PATCH 3/3] commit-graph: lazy-load trees","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-04-03T18:37:18Z","receivedAt":"2018-04-03T18:37:24Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":">>> +/*\n>>> + * For performance reasons, a commit loaded from the graph does not\n>>> + * have a tree loaded until trying to consume it for the first time.\n>>\n>> That is the theme of this series/patch, but do we need to write it down\n>> into the codebase? I'd be inclined to omit this part and only go with:\n>>\n>>    Load the root tree of a commit and return the tree.\n>\n>\n> OK.\n\nThis was just a suggestion, others may want to chime in on the terseness.\n\n>\n>>\n>>>   struct tree *get_commit_tree(const struct commit *commit)\n>>>   {\n>>> -       return commit->tree;\n>>> +       if (commit->tree || !commit->object.parsed)\n>>\n>> I understand to return the tree from the commit\n>> when we have the tree in the commit object (the first\n>> part).\n>>\n>> But 'when we have not (yet) parsed the commit object',\n>> we also just return its tree? Could you explain the\n>> second part of the condition?\n>> Is that for commits that are not part of the commit graph?\n>> (But then why does it need to be negated?)\n>\n>\n> Some callers check the value of 'commit->tree' without a guarantee that the\n> commit was parsed. In this case, the way to preserve the existing behavior\n> is to continue returning NULL. If I remove the \"|| !commit->object.parsed\"\n> then the BUG(\"commit has NULL tree, but was not loaded from commit-graph\")\n\nOh. That totally makes sense now. I should have more coffee (got up extra\nearly to see a dentist before going into work)\n\n> is hit in these two tests:\n>\n> t6012-rev-list-simplify.sh\n> t6110-rev-list-sparse.sh\n>\n> I prefer to keep the BUG() statement and instead use this if statement. If\n> someone has more clarity on why this is a good existing behavior, then\n> please chime in.\n>\n\nI would also keep the BUG statement; I am unsure if we'd want to\nhave a comment explaining the situation, or if it is obvious enough\nand I was just not focused enough.\n\nThis totally makes sense now and I'd keep the code as is.\n\nThanks,\nStefan\n"},{"id":"343764","messageId":"20180403202030.GA15157@sigill.intra.peff.net","threadId":"48210","inReplyTo":"007c630a-0df8-803c-b637-fb5ccefa7b7c@gmail.com","subject":"Re: [PATCH 0/3] Lazy-load trees when reading commit-graph","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-04-03T20:20:30Z","receivedAt":"2018-04-03T20:20:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 03, 2018 at 09:14:50AM -0400, Derrick Stolee wrote:\n\n> > I'm not sure what the exact solution would be, but I imagine something\n> > like variable-sized \"struct commit\"s with the parent pointers embedded,\n> > with some kind of flag to indicate the number of parents (and probably\n> > some fallback to break out to a linked list for extreme cases of more\n> > than 2 parents).  It may end up pretty invasive, though, as there's a\n> > lot of open-coded traversals of that parent list.\n> > \n> > Anyway, not anything to do with this patch, but food for thought as you\n> > micro-optimize these traversals.\n> \n> One other thing that I've been thinking about is that 'struct commit' is so\n> much bigger than the other structs in 'union any_object'. This means that\n> the object cache, which I think creates blocks of 'union any_object' for\n> memory-alignment reasons, is overly bloated. This would be especially true\n> when walking many more trees than commits.\n> \n> Perhaps there are other memory concerns in that case (such as cached\n> buffers) that the 'union any_object' is not a concern, but it is worth\n> thinking about as we brainstorm how to reduce the parent-list memory.\n\nIt definitely bloats any_object, but I don't think we typically allocate\ntoo many of those. Those should only come from lookup_unknown_object(),\nbut typically we'll come across objects by traversing the graph, in\nwhich case we have an expectation of the type (and use the appropriate\nlookup_foo() function, which uses the type-specific block allocators).\n\n-Peff\n"},{"id":"343785","messageId":"73e884cb-ff75-9f1d-f5d1-1624371ab15e@gmail.com","threadId":"48210","inReplyTo":"20180403202030.GA15157@sigill.intra.peff.net","subject":"Re: [PATCH 0/3] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-04-04T12:08:34Z","receivedAt":"2018-04-04T12:08:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/3/2018 4:20 PM, Jeff King wrote:\n> On Tue, Apr 03, 2018 at 09:14:50AM -0400, Derrick Stolee wrote:\n>\n>>> I'm not sure what the exact solution would be, but I imagine something\n>>> like variable-sized \"struct commit\"s with the parent pointers embedded,\n>>> with some kind of flag to indicate the number of parents (and probably\n>>> some fallback to break out to a linked list for extreme cases of more\n>>> than 2 parents).  It may end up pretty invasive, though, as there's a\n>>> lot of open-coded traversals of that parent list.\n>>>\n>>> Anyway, not anything to do with this patch, but food for thought as you\n>>> micro-optimize these traversals.\n>> One other thing that I've been thinking about is that 'struct commit' is so\n>> much bigger than the other structs in 'union any_object'. This means that\n>> the object cache, which I think creates blocks of 'union any_object' for\n>> memory-alignment reasons, is overly bloated. This would be especially true\n>> when walking many more trees than commits.\n>>\n>> Perhaps there are other memory concerns in that case (such as cached\n>> buffers) that the 'union any_object' is not a concern, but it is worth\n>> thinking about as we brainstorm how to reduce the parent-list memory.\n> It definitely bloats any_object, but I don't think we typically allocate\n> too many of those. Those should only come from lookup_unknown_object(),\n> but typically we'll come across objects by traversing the graph, in\n> which case we have an expectation of the type (and use the appropriate\n> lookup_foo() function, which uses the type-specific block allocators).\n\nThanks for the clarification here. I'm glad I was wrong about how often \nany_object is used.\n\nThanks,\n-Stolee\n"},{"id":"343985","messageId":"20180406190919.167092-1-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180403120057.173849-1-dstolee@microsoft.com","subject":"[PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-06T19:09:30Z","receivedAt":"2018-04-06T19:09:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"There are several commit-graph walks that require loading many commits\nbut never walk the trees reachable from those commits. However, the\ncurrent logic in parse_commit() requires the root tree to be loaded.\nThis only uses lookup_tree(), but when reading commits from the commit-\ngraph file, the hashcpy() to load the root tree hash and the time spent\nchecking the object cache take more time than parsing the rest of the\ncommit.\n\nIn this patch series, all direct references to accessing the 'tree'\nmember of struct commit are replaced instead by one of the following\nmethods:\n\n        struct tree *get_commit_tree(struct commit *)\n        struct object_id *get_commit_tree_oid(struct commit *)\n\nThis replacement was assisted by a Coccinelle script, but the 'tree'\nmember is overloaded in other types, so we first rename the 'tree'\nmember to 'maybe_tree' and use the compiler to ensure we caught all\nexamples. Then, contrib/coccinelle/commit.cocci generates the patch\nto replace all accessors of 'maybe_tree' to the methods above.\n\nAfter all access is restricted to use these methods, we can then\nchange the postcondition of parse_commit_in_graph() to allow 'maybe_tree'\nto be NULL. If the tree is accessed later, we can load the tree's\nOID from the commit-graph in constant time and perform the lookup_tree().\n\nOn the Linux repository, performance tests were run for the following\ncommand:\n\n    git log --graph --oneline -1000\n\n    Before: 0.92s\n    After:  0.66s\n    Rel %: -28.3%\n\nAdding '-- kernel/' to the command requires loading the root tree\nfor every commit that is walked. There was no measureable performance\nchange as a result of this patch.\n\nThis patch series depends on v7 of ds/commit-graph.\n\nDerrick Stolee (4):\n  treewide: rename tree to maybe_tree\n  commit: create get_commit_tree() method\n  treewide: replace maybe_tree with accessor methods\n  commit-graph: lazy-load trees for commits\n\n blame.c                         | 18 +++++++++---------\n builtin/checkout.c              | 18 ++++++++++++------\n builtin/diff.c                  |  2 +-\n builtin/fast-export.c           |  6 +++---\n builtin/log.c                   |  4 ++--\n builtin/reflog.c                |  2 +-\n commit-graph.c                  | 27 +++++++++++++++++++++++----\n commit-graph.h                  |  7 +++++++\n commit.c                        | 18 +++++++++++++++++-\n commit.h                        |  5 ++++-\n contrib/coccinelle/commit.cocci | 30 ++++++++++++++++++++++++++++++\n fsck.c                          |  8 +++++---\n http-push.c                     |  2 +-\n line-log.c                      |  4 ++--\n list-objects.c                  | 10 +++++-----\n log-tree.c                      |  6 +++---\n merge-recursive.c               |  5 +++--\n notes-merge.c                   |  9 +++++----\n packfile.c                      |  2 +-\n pretty.c                        |  5 +++--\n ref-filter.c                    |  2 +-\n revision.c                      |  8 ++++----\n sequencer.c                     | 12 ++++++------\n sha1_name.c                     |  2 +-\n tree.c                          |  4 ++--\n walker.c                        |  2 +-\n 26 files changed, 152 insertions(+), 66 deletions(-)\n create mode 100644 contrib/coccinelle/commit.cocci\n\n-- \n2.17.0\n\n"},{"id":"343986","messageId":"20180406190919.167092-3-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180406190919.167092-1-dstolee@microsoft.com","subject":"[PATCH v2 2/4] commit: create get_commit_tree() method","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-06T19:09:34Z","receivedAt":"2018-04-06T19:09:43Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"While walking the commit graph, we load struct commit objects into\nthe object cache. During this process, we also load struct tree\nobjects for the root tree of each of these commits. We load these\nobjects even if we are only computing commit reachability information,\nsuch as a merge base or ahead/behind information.\n\nCreate get_commit_tree() as a first step to removing direct\nreferences to the 'maybe_tree' member of struct commit.\n\nCreate get_commit_tree_oid() as a shortcut for several references\nto \"&commit->maybe_tree->object.oid\" in the codebase.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n commit.c | 10 ++++++++++\n commit.h |  3 +++\n 2 files changed, 13 insertions(+)\n\ndiff --git a/commit.c b/commit.c\nindex fbc092808c..aea2ca1f8b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -296,6 +296,16 @@ void free_commit_buffer(struct commit *commit)\n \t}\n }\n \n+struct tree *get_commit_tree(const struct commit *commit)\n+{\n+\treturn commit->maybe_tree;\n+}\n+\n+struct object_id *get_commit_tree_oid(const struct commit *commit)\n+{\n+\treturn &get_commit_tree(commit)->object.oid;\n+}\n+\n const void *detach_commit_buffer(struct commit *commit, unsigned long *sizep)\n {\n \tstruct commit_buffer *v = buffer_slab_peek(&buffer_slab, commit);\ndiff --git a/commit.h b/commit.h\nindex c4d6e6e064..dc4bf97d9f 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -102,6 +102,9 @@ void unuse_commit_buffer(const struct commit *, const void *buffer);\n  */\n void free_commit_buffer(struct commit *);\n \n+struct tree *get_commit_tree(const struct commit *);\n+struct object_id *get_commit_tree_oid(const struct commit *);\n+\n /*\n  * Disassociate any cached object buffer from the commit, but do not free it.\n  * The buffer (or NULL, if none) is returned.\n-- \n2.17.0\n\n"},{"id":"343987","messageId":"20180406190919.167092-2-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180406190919.167092-1-dstolee@microsoft.com","subject":"[PATCH v2 1/4] treewide: rename tree to maybe_tree","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-06T19:09:32Z","receivedAt":"2018-04-06T19:09:46Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"Using the commit-graph file to walk commit history removes the large\ncost of parsing commits during the walk. This exposes a performance\nissue: lookup_tree() takes a large portion of the computation time,\neven when Git never uses those trees.\n\nIn anticipation of lazy-loading these trees, rename the 'tree' member\nof struct commit to 'maybe_tree'. This serves two purposes: it hints\nat the future role of possibly being NULL even if the commit has a\nvalid tree, and it allows for unambiguous transformation from simple\nmember access (i.e. commit->maybe_tree) to method access.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n blame.c               | 18 +++++++++---------\n builtin/checkout.c    | 12 ++++++------\n builtin/diff.c        |  2 +-\n builtin/fast-export.c |  6 +++---\n builtin/log.c         |  4 ++--\n builtin/reflog.c      |  2 +-\n commit-graph.c        |  4 ++--\n commit.c              |  2 +-\n commit.h              |  2 +-\n fsck.c                |  6 +++---\n http-push.c           |  2 +-\n line-log.c            |  4 ++--\n list-objects.c        | 10 +++++-----\n log-tree.c            |  6 +++---\n merge-recursive.c     |  5 +++--\n notes-merge.c         |  8 ++++----\n packfile.c            |  2 +-\n pretty.c              |  4 ++--\n ref-filter.c          |  2 +-\n revision.c            |  8 ++++----\n sequencer.c           | 12 ++++++------\n sha1_name.c           |  2 +-\n tree.c                |  4 ++--\n walker.c              |  2 +-\n 24 files changed, 65 insertions(+), 64 deletions(-)\n\ndiff --git a/blame.c b/blame.c\nindex 200e0ad9a2..b78e649cac 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -553,10 +553,10 @@ static struct blame_origin *find_origin(struct commit *parent,\n \tdiff_setup_done(&diff_opts);\n \n \tif (is_null_oid(&origin->commit->object.oid))\n-\t\tdo_diff_cache(&parent->tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(&parent->maybe_tree->object.oid, &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n-\t\t\t      &origin->commit->tree->object.oid,\n+\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n+\t\t\t      &origin->commit->maybe_tree->object.oid,\n \t\t\t      \"\", &diff_opts);\n \tdiffcore_std(&diff_opts);\n \n@@ -622,10 +622,10 @@ static struct blame_origin *find_rename(struct commit *parent,\n \tdiff_setup_done(&diff_opts);\n \n \tif (is_null_oid(&origin->commit->object.oid))\n-\t\tdo_diff_cache(&parent->tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(&parent->maybe_tree->object.oid, &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n-\t\t\t      &origin->commit->tree->object.oid,\n+\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n+\t\t\t      &origin->commit->maybe_tree->object.oid,\n \t\t\t      \"\", &diff_opts);\n \tdiffcore_std(&diff_opts);\n \n@@ -1257,10 +1257,10 @@ static void find_copy_in_parent(struct blame_scoreboard *sb,\n \t\tdiff_opts.flags.find_copies_harder = 1;\n \n \tif (is_null_oid(&target->commit->object.oid))\n-\t\tdo_diff_cache(&parent->tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(&parent->maybe_tree->object.oid, &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n-\t\t\t      &target->commit->tree->object.oid,\n+\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n+\t\t\t      &target->commit->maybe_tree->object.oid,\n \t\t\t      \"\", &diff_opts);\n \n \tif (!diff_opts.flags.find_copies_harder)\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex d76e13c852..b15fed5d85 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -484,7 +484,7 @@ static int merge_working_tree(const struct checkout_opts *opts,\n \n \tresolve_undo_clear();\n \tif (opts->force) {\n-\t\tret = reset_tree(new_branch_info->commit->tree, opts, 1, writeout_error);\n+\t\tret = reset_tree(new_branch_info->commit->maybe_tree, opts, 1, writeout_error);\n \t\tif (ret)\n \t\t\treturn ret;\n \t} else {\n@@ -570,18 +570,18 @@ static int merge_working_tree(const struct checkout_opts *opts,\n \t\t\to.verbosity = 0;\n \t\t\twork = write_tree_from_memory(&o);\n \n-\t\t\tret = reset_tree(new_branch_info->commit->tree, opts, 1,\n+\t\t\tret = reset_tree(new_branch_info->commit->maybe_tree, opts, 1,\n \t\t\t\t\t writeout_error);\n \t\t\tif (ret)\n \t\t\t\treturn ret;\n \t\t\to.ancestor = old_branch_info->name;\n \t\t\to.branch1 = new_branch_info->name;\n \t\t\to.branch2 = \"local\";\n-\t\t\tret = merge_trees(&o, new_branch_info->commit->tree, work,\n-\t\t\t\told_branch_info->commit->tree, &result);\n+\t\t\tret = merge_trees(&o, new_branch_info->commit->maybe_tree, work,\n+\t\t\t\told_branch_info->commit->maybe_tree, &result);\n \t\t\tif (ret < 0)\n \t\t\t\texit(128);\n-\t\t\tret = reset_tree(new_branch_info->commit->tree, opts, 0,\n+\t\t\tret = reset_tree(new_branch_info->commit->maybe_tree, opts, 0,\n \t\t\t\t\t writeout_error);\n \t\t\tstrbuf_release(&o.obuf);\n \t\t\tif (ret)\n@@ -1002,7 +1002,7 @@ static int parse_branchname_arg(int argc, const char **argv,\n \t\t*source_tree = parse_tree_indirect(rev);\n \t} else {\n \t\tparse_commit_or_die(new_branch_info->commit);\n-\t\t*source_tree = new_branch_info->commit->tree;\n+\t\t*source_tree = new_branch_info->commit->maybe_tree;\n \t}\n \n \tif (!*source_tree)                   /* case (1): want a tree */\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 16bfb22f73..34f18a5f3f 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -398,7 +398,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t\tif (!obj)\n \t\t\tdie(_(\"invalid object '%s' given.\"), name);\n \t\tif (obj->type == OBJ_COMMIT)\n-\t\t\tobj = &((struct commit *)obj)->tree->object;\n+\t\t\tobj = &((struct commit *)obj)->maybe_tree->object;\n \n \t\tif (obj->type == OBJ_TREE) {\n \t\t\tobj->flags |= flags;\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 27b2cc138e..91e526b30d 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -578,11 +578,11 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,\n \t    get_object_mark(&commit->parents->item->object) != 0 &&\n \t    !full_tree) {\n \t\tparse_commit_or_die(commit->parents->item);\n-\t\tdiff_tree_oid(&commit->parents->item->tree->object.oid,\n-\t\t\t      &commit->tree->object.oid, \"\", &rev->diffopt);\n+\t\tdiff_tree_oid(&commit->parents->item->maybe_tree->object.oid,\n+\t\t\t      &commit->maybe_tree->object.oid, \"\", &rev->diffopt);\n \t}\n \telse\n-\t\tdiff_root_tree_oid(&commit->tree->object.oid,\n+\t\tdiff_root_tree_oid(&commit->maybe_tree->object.oid,\n \t\t\t\t   \"\", &rev->diffopt);\n \n \t/* Export the referenced blobs, and remember the marks. */\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 94ee177d56..f603b53318 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1067,8 +1067,8 @@ static void make_cover_letter(struct rev_info *rev, int use_stdout,\n \n \tdiff_setup_done(&opts);\n \n-\tdiff_tree_oid(&origin->tree->object.oid,\n-\t\t      &head->tree->object.oid,\n+\tdiff_tree_oid(&origin->maybe_tree->object.oid,\n+\t\t      &head->maybe_tree->object.oid,\n \t\t      \"\", &opts);\n \tdiffcore_std(&opts);\n \tdiff_flush(&opts);\ndiff --git a/builtin/reflog.c b/builtin/reflog.c\nindex 4719a5354c..b17eabc009 100644\n--- a/builtin/reflog.c\n+++ b/builtin/reflog.c\n@@ -154,7 +154,7 @@ static int commit_is_complete(struct commit *commit)\n \t\tfor (i = 0; i < found.nr; i++) {\n \t\t\tstruct commit *c =\n \t\t\t\t(struct commit *)found.objects[i].item;\n-\t\t\tif (!tree_is_complete(&c->tree->object.oid)) {\n+\t\t\tif (!tree_is_complete(&c->maybe_tree->object.oid)) {\n \t\t\t\tis_incomplete = 1;\n \t\t\t\tc->object.flags |= INCOMPLETE;\n \t\t\t}\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 1fc63d541b..005b4a753e 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -258,7 +258,7 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin\n \titem->graph_pos = pos;\n \n \thashcpy(oid.hash, commit_data);\n-\titem->tree = lookup_tree(&oid);\n+\titem->maybe_tree = lookup_tree(&oid);\n \n \tdate_high = get_be32(commit_data + g->hash_len + 8) & 0x3;\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n@@ -369,7 +369,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n \t\tuint32_t packedDate[2];\n \n \t\tparse_commit(*list);\n-\t\thashwrite(f, (*list)->tree->object.oid.hash, hash_len);\n+\t\thashwrite(f, (*list)->maybe_tree->object.oid.hash, hash_len);\n \n \t\tparent = (*list)->parents;\n \ndiff --git a/commit.c b/commit.c\nindex 3e39c86abf..fbc092808c 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -335,7 +335,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s\n \tif (get_sha1_hex(bufptr + 5, parent.hash) < 0)\n \t\treturn error(\"bad tree pointer in commit %s\",\n \t\t\t     oid_to_hex(&item->object.oid));\n-\titem->tree = lookup_tree(&parent);\n+\titem->maybe_tree = lookup_tree(&parent);\n \tbufptr += tree_entry_len + 1; /* \"tree \" + \"hex sha1\" + \"\\n\" */\n \tpptr = &item->parents;\n \ndiff --git a/commit.h b/commit.h\nindex e57ae4b583..c4d6e6e064 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -22,7 +22,7 @@ struct commit {\n \tunsigned int index;\n \ttimestamp_t date;\n \tstruct commit_list *parents;\n-\tstruct tree *tree;\n+\tstruct tree *maybe_tree;\n \tuint32_t graph_pos;\n };\n \ndiff --git a/fsck.c b/fsck.c\nindex 5c8c12dde3..3228ca5bee 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -396,9 +396,9 @@ static int fsck_walk_commit(struct commit *commit, void *data, struct fsck_optio\n \n \tname = get_object_name(options, &commit->object);\n \tif (name)\n-\t\tput_object_name(options, &commit->tree->object, \"%s:\", name);\n+\t\tput_object_name(options, &commit->maybe_tree->object, \"%s:\", name);\n \n-\tresult = options->walk((struct object *)commit->tree, OBJ_TREE, data, options);\n+\tresult = options->walk((struct object *)commit->maybe_tree, OBJ_TREE, data, options);\n \tif (result < 0)\n \t\treturn result;\n \tres = result;\n@@ -772,7 +772,7 @@ static int fsck_commit_buffer(struct commit *commit, const char *buffer,\n \terr = fsck_ident(&buffer, &commit->object, options);\n \tif (err)\n \t\treturn err;\n-\tif (!commit->tree) {\n+\tif (!commit->maybe_tree) {\n \t\terr = report(options, &commit->object, FSCK_MSG_BAD_TREE, \"could not load commit's tree %s\", sha1_to_hex(tree_sha1));\n \t\tif (err)\n \t\t\treturn err;\ndiff --git a/http-push.c b/http-push.c\nindex 7dcd9daf62..d83479f32f 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1330,7 +1330,7 @@ static int get_delta(struct rev_info *revs, struct remote_lock *lock)\n \tint count = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tp = process_tree(commit->tree, p);\n+\t\tp = process_tree(commit->maybe_tree, p);\n \t\tcommit->object.flags |= LOCAL;\n \t\tif (!(commit->object.flags & UNINTERESTING))\n \t\t\tcount += add_send_request(&commit->object, lock);\ndiff --git a/line-log.c b/line-log.c\nindex cdc2257db5..e714969ca2 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -817,8 +817,8 @@ static void queue_diffs(struct line_log_data *range,\n \tassert(commit);\n \n \tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n-\tdiff_tree_oid(parent ? &parent->tree->object.oid : NULL,\n-\t\t      &commit->tree->object.oid, \"\", opt);\n+\tdiff_tree_oid(parent ? &parent->maybe_tree->object.oid : NULL,\n+\t\t      &commit->maybe_tree->object.oid, \"\", opt);\n \tif (opt->detect_rename) {\n \t\tfilter_diffs_for_paths(range, 1);\n \t\tif (diff_might_be_rename())\ndiff --git a/list-objects.c b/list-objects.c\nindex 168bef688a..bfd09f545c 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -195,7 +195,7 @@ static void mark_edge_parents_uninteresting(struct commit *commit,\n \t\tstruct commit *parent = parents->item;\n \t\tif (!(parent->object.flags & UNINTERESTING))\n \t\t\tcontinue;\n-\t\tmark_tree_uninteresting(parent->tree);\n+\t\tmark_tree_uninteresting(parent->maybe_tree);\n \t\tif (revs->edge_hint && !(parent->object.flags & SHOWN)) {\n \t\t\tparent->object.flags |= SHOWN;\n \t\t\tshow_edge(parent);\n@@ -212,7 +212,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\tstruct commit *commit = list->item;\n \n \t\tif (commit->object.flags & UNINTERESTING) {\n-\t\t\tmark_tree_uninteresting(commit->tree);\n+\t\t\tmark_tree_uninteresting(commit->maybe_tree);\n \t\t\tif (revs->edge_hint_aggressive && !(commit->object.flags & SHOWN)) {\n \t\t\t\tcommit->object.flags |= SHOWN;\n \t\t\t\tshow_edge(commit);\n@@ -227,7 +227,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\t\tstruct commit *commit = (struct commit *)obj;\n \t\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n \t\t\t\tcontinue;\n-\t\t\tmark_tree_uninteresting(commit->tree);\n+\t\t\tmark_tree_uninteresting(commit->maybe_tree);\n \t\t\tif (!(obj->flags & SHOWN)) {\n \t\t\t\tobj->flags |= SHOWN;\n \t\t\t\tshow_edge(commit);\n@@ -300,8 +300,8 @@ static void do_traverse(struct rev_info *revs,\n \t\t * an uninteresting boundary commit may not have its tree\n \t\t * parsed yet, but we are not going to show them anyway\n \t\t */\n-\t\tif (commit->tree)\n-\t\t\tadd_pending_tree(revs, commit->tree);\n+\t\tif (commit->maybe_tree)\n+\t\t\tadd_pending_tree(revs, commit->maybe_tree);\n \t\tshow_commit(commit, show_data);\n \n \t\tif (revs->tree_blobs_in_commit_order)\ndiff --git a/log-tree.c b/log-tree.c\nindex bdf23c5f7b..99499af57c 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -806,7 +806,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\treturn 0;\n \n \tparse_commit_or_die(commit);\n-\toid = &commit->tree->object.oid;\n+\toid = &commit->maybe_tree->object.oid;\n \n \t/* Root commit? */\n \tparents = get_saved_parents(opt, commit);\n@@ -831,7 +831,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\t\t * we merged _in_.\n \t\t\t */\n \t\t\tparse_commit_or_die(parents->item);\n-\t\t\tdiff_tree_oid(&parents->item->tree->object.oid,\n+\t\t\tdiff_tree_oid(&parents->item->maybe_tree->object.oid,\n \t\t\t\t      oid, \"\", &opt->diffopt);\n \t\t\tlog_tree_diff_flush(opt);\n \t\t\treturn !opt->loginfo;\n@@ -846,7 +846,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\tstruct commit *parent = parents->item;\n \n \t\tparse_commit_or_die(parent);\n-\t\tdiff_tree_oid(&parent->tree->object.oid,\n+\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n \t\t\t      oid, \"\", &opt->diffopt);\n \t\tlog_tree_diff_flush(opt);\n \ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 869092f7b9..67886a4ff8 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -101,7 +101,7 @@ static struct commit *make_virtual_commit(struct tree *tree, const char *comment\n \tstruct commit *commit = alloc_commit_node();\n \n \tset_merge_remote_desc(commit, comment, (struct object *)commit);\n-\tcommit->tree = tree;\n+\tcommit->maybe_tree = tree;\n \tcommit->object.parsed = 1;\n \treturn commit;\n }\n@@ -2154,7 +2154,8 @@ int merge_recursive(struct merge_options *o,\n \t\tread_cache();\n \n \to->ancestor = \"merged common ancestors\";\n-\tclean = merge_trees(o, h1->tree, h2->tree, merged_common_ancestors->tree,\n+\tclean = merge_trees(o, h1->maybe_tree, h2->maybe_tree,\n+\t\t\t    merged_common_ancestors->maybe_tree,\n \t\t\t    &mrtree);\n \tif (clean < 0) {\n \t\tflush_output(o);\ndiff --git a/notes-merge.c b/notes-merge.c\nindex c09c5e0e47..1d3edc8942 100644\n--- a/notes-merge.c\n+++ b/notes-merge.c\n@@ -600,14 +600,14 @@ int notes_merge(struct notes_merge_options *o,\n \t\t\tprintf(\"No merge base found; doing history-less merge\\n\");\n \t} else if (!bases->next) {\n \t\tbase_oid = &bases->item->object.oid;\n-\t\tbase_tree_oid = &bases->item->tree->object.oid;\n+\t\tbase_tree_oid = &bases->item->maybe_tree->object.oid;\n \t\tif (o->verbosity >= 4)\n \t\t\tprintf(\"One merge base found (%.7s)\\n\",\n \t\t\t       oid_to_hex(base_oid));\n \t} else {\n \t\t/* TODO: How to handle multiple merge-bases? */\n \t\tbase_oid = &bases->item->object.oid;\n-\t\tbase_tree_oid = &bases->item->tree->object.oid;\n+\t\tbase_tree_oid = &bases->item->maybe_tree->object.oid;\n \t\tif (o->verbosity >= 3)\n \t\t\tprintf(\"Multiple merge bases found. Using the first \"\n \t\t\t\t\"(%.7s)\\n\", oid_to_hex(base_oid));\n@@ -634,8 +634,8 @@ int notes_merge(struct notes_merge_options *o,\n \t\tgoto found_result;\n \t}\n \n-\tresult = merge_from_diffs(o, base_tree_oid, &local->tree->object.oid,\n-\t\t\t\t  &remote->tree->object.oid, local_tree);\n+\tresult = merge_from_diffs(o, base_tree_oid, &local->maybe_tree->object.oid,\n+\t\t\t\t  &remote->maybe_tree->object.oid, local_tree);\n \n \tif (result != 0) { /* non-trivial merge (with or without conflicts) */\n \t\t/* Commit (partial) result */\ndiff --git a/packfile.c b/packfile.c\nindex b1d33b646a..3eb9c4a36e 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1925,7 +1925,7 @@ static int add_promisor_object(const struct object_id *oid,\n \t\tstruct commit *commit = (struct commit *) obj;\n \t\tstruct commit_list *parents = commit->parents;\n \n-\t\toidset_insert(set, &commit->tree->object.oid);\n+\t\toidset_insert(set, &commit->maybe_tree->object.oid);\n \t\tfor (; parents; parents = parents->next)\n \t\t\toidset_insert(set, &parents->item->object.oid);\n \t} else if (obj->type == OBJ_TAG) {\ndiff --git a/pretty.c b/pretty.c\nindex f7ce490230..42095ea495 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -1161,10 +1161,10 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n \t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n-\t\tstrbuf_addstr(sb, oid_to_hex(&commit->tree->object.oid));\n+\t\tstrbuf_addstr(sb, oid_to_hex(&commit->maybe_tree->object.oid));\n \t\treturn 1;\n \tcase 't':\t\t/* abbreviated tree hash */\n-\t\tstrbuf_add_unique_abbrev(sb, commit->tree->object.oid.hash,\n+\t\tstrbuf_add_unique_abbrev(sb, commit->maybe_tree->object.oid.hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n \t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 45fc56216a..783a3ee6cf 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -815,7 +815,7 @@ static void grab_commit_values(struct atom_value *val, int deref, struct object\n \t\tif (deref)\n \t\t\tname++;\n \t\tif (!strcmp(name, \"tree\")) {\n-\t\t\tv->s = xstrdup(oid_to_hex(&commit->tree->object.oid));\n+\t\t\tv->s = xstrdup(oid_to_hex(&commit->maybe_tree->object.oid));\n \t\t}\n \t\telse if (!strcmp(name, \"numparent\")) {\n \t\t\tv->value = commit_list_count(commit->parents);\ndiff --git a/revision.c b/revision.c\nindex b42c836d7a..7d66e32e83 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -440,8 +440,8 @@ static void file_change(struct diff_options *options,\n static int rev_compare_tree(struct rev_info *revs,\n \t\t\t    struct commit *parent, struct commit *commit)\n {\n-\tstruct tree *t1 = parent->tree;\n-\tstruct tree *t2 = commit->tree;\n+\tstruct tree *t1 = parent->maybe_tree;\n+\tstruct tree *t2 = commit->maybe_tree;\n \n \tif (!t1)\n \t\treturn REV_TREE_NEW;\n@@ -477,7 +477,7 @@ static int rev_compare_tree(struct rev_info *revs,\n static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n {\n \tint retval;\n-\tstruct tree *t1 = commit->tree;\n+\tstruct tree *t1 = commit->maybe_tree;\n \n \tif (!t1)\n \t\treturn 0;\n@@ -615,7 +615,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tif (!revs->prune)\n \t\treturn;\n \n-\tif (!commit->tree)\n+\tif (!commit->maybe_tree)\n \t\treturn;\n \n \tif (!commit->parents) {\ndiff --git a/sequencer.c b/sequencer.c\nindex f9d1001dee..3b2823c8b5 100644\n--- a/sequencer.c\n+++ b/sequencer.c\n@@ -499,8 +499,8 @@ static int do_recursive_merge(struct commit *base, struct commit *next,\n \to.show_rename_progress = 1;\n \n \thead_tree = parse_tree_indirect(head);\n-\tnext_tree = next ? next->tree : empty_tree();\n-\tbase_tree = base ? base->tree : empty_tree();\n+\tnext_tree = next ? next->maybe_tree : empty_tree();\n+\tbase_tree = base ? base->maybe_tree : empty_tree();\n \n \tfor (xopt = opts->xopts; xopt != opts->xopts + opts->xopts_nr; xopt++)\n \t\tparse_merge_opt(&o, *xopt);\n@@ -561,7 +561,7 @@ static int is_index_unchanged(void)\n \t\t\treturn error(_(\"unable to update cache tree\"));\n \n \treturn !oidcmp(&active_cache_tree->oid,\n-\t\t       &head_commit->tree->object.oid);\n+\t\t       &head_commit->maybe_tree->object.oid);\n }\n \n static int write_author_script(const char *message)\n@@ -1118,7 +1118,7 @@ static int try_to_commit(struct strbuf *msg, const char *author,\n \t}\n \n \tif (!(flags & ALLOW_EMPTY) && !oidcmp(current_head ?\n-\t\t\t\t\t      &current_head->tree->object.oid :\n+\t\t\t\t\t      &current_head->maybe_tree->object.oid :\n \t\t\t\t\t      &empty_tree_oid, &tree)) {\n \t\tres = 1; /* run 'git commit' to display error message */\n \t\tgoto out;\n@@ -1216,12 +1216,12 @@ static int is_original_commit_empty(struct commit *commit)\n \t\tif (parse_commit(parent))\n \t\t\treturn error(_(\"could not parse parent commit %s\"),\n \t\t\t\toid_to_hex(&parent->object.oid));\n-\t\tptree_oid = &parent->tree->object.oid;\n+\t\tptree_oid = &parent->maybe_tree->object.oid;\n \t} else {\n \t\tptree_oid = the_hash_algo->empty_tree; /* commit is root */\n \t}\n \n-\treturn !oidcmp(ptree_oid, &commit->tree->object.oid);\n+\treturn !oidcmp(ptree_oid, &commit->maybe_tree->object.oid);\n }\n \n /*\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 735c1c0b8e..26b22cb628 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -896,7 +896,7 @@ struct object *peel_to_type(const char *name, int namelen,\n \t\tif (o->type == OBJ_TAG)\n \t\t\to = ((struct tag*) o)->tagged;\n \t\telse if (o->type == OBJ_COMMIT)\n-\t\t\to = &(((struct commit *) o)->tree->object);\n+\t\t\to = &(((struct commit *) o)->maybe_tree->object);\n \t\telse {\n \t\t\tif (name)\n \t\t\t\terror(\"%.*s: expected %s type, but the object \"\ndiff --git a/tree.c b/tree.c\nindex b224115e0f..dbc5e0be54 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -109,7 +109,7 @@ static int read_tree_1(struct tree *tree, struct strbuf *base,\n \t\t\t\t    oid_to_hex(entry.oid),\n \t\t\t\t    base->buf, entry.path);\n \n-\t\t\toidcpy(&oid, &commit->tree->object.oid);\n+\t\t\toidcpy(&oid, &commit->maybe_tree->object.oid);\n \t\t}\n \t\telse\n \t\t\tcontinue;\n@@ -248,7 +248,7 @@ struct tree *parse_tree_indirect(const struct object_id *oid)\n \t\tif (obj->type == OBJ_TREE)\n \t\t\treturn (struct tree *) obj;\n \t\telse if (obj->type == OBJ_COMMIT)\n-\t\t\tobj = &(((struct commit *) obj)->tree->object);\n+\t\t\tobj = &(((struct commit *) obj)->maybe_tree->object);\n \t\telse if (obj->type == OBJ_TAG)\n \t\t\tobj = ((struct tag *) obj)->tagged;\n \t\telse\ndiff --git a/walker.c b/walker.c\nindex dffb9c8e37..1d5f3059a2 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -87,7 +87,7 @@ static int process_commit(struct walker *walker, struct commit *commit)\n \twalker_say(walker, \"walk %s\\n\", oid_to_hex(&commit->object.oid));\n \n \tif (walker->get_tree) {\n-\t\tif (process(walker, &commit->tree->object))\n+\t\tif (process(walker, &commit->maybe_tree->object))\n \t\t\treturn -1;\n \t\tif (!walker->get_all)\n \t\t\twalker->get_tree = 0;\n-- \n2.17.0\n\n"},{"id":"343988","messageId":"20180406190919.167092-4-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180406190919.167092-1-dstolee@microsoft.com","subject":"[PATCH v2 3/4] treewide: replace maybe_tree with accessor methods","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-06T19:09:38Z","receivedAt":"2018-04-06T19:09:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"In anticipation of making trees load lazily, create a Coccinelle\nscript (contrib/coccinelle/commit.cocci) to ensure that all\nreferences to the 'maybe_tree' member of struct commit are either\nmutations or accesses through get_commit_tree() or\nget_commit_tree_oid().\n\nApply the Coccinelle script to create the rest of the patch.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n blame.c                         | 18 +++++++++---------\n builtin/checkout.c              | 18 ++++++++++++------\n builtin/diff.c                  |  2 +-\n builtin/fast-export.c           |  6 +++---\n builtin/log.c                   |  4 ++--\n builtin/reflog.c                |  2 +-\n commit-graph.c                  |  2 +-\n contrib/coccinelle/commit.cocci | 30 ++++++++++++++++++++++++++++++\n fsck.c                          |  8 +++++---\n http-push.c                     |  2 +-\n line-log.c                      |  4 ++--\n list-objects.c                  | 10 +++++-----\n log-tree.c                      |  6 +++---\n merge-recursive.c               |  4 ++--\n notes-merge.c                   |  9 +++++----\n packfile.c                      |  2 +-\n pretty.c                        |  5 +++--\n ref-filter.c                    |  2 +-\n revision.c                      |  8 ++++----\n sequencer.c                     | 12 ++++++------\n sha1_name.c                     |  2 +-\n tree.c                          |  4 ++--\n walker.c                        |  2 +-\n 23 files changed, 101 insertions(+), 61 deletions(-)\n create mode 100644 contrib/coccinelle/commit.cocci\n\ndiff --git a/blame.c b/blame.c\nindex b78e649cac..7f5700b324 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -553,10 +553,10 @@ static struct blame_origin *find_origin(struct commit *parent,\n \tdiff_setup_done(&diff_opts);\n \n \tif (is_null_oid(&origin->commit->object.oid))\n-\t\tdo_diff_cache(&parent->maybe_tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n-\t\t\t      &origin->commit->maybe_tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t      get_commit_tree_oid(origin->commit),\n \t\t\t      \"\", &diff_opts);\n \tdiffcore_std(&diff_opts);\n \n@@ -622,10 +622,10 @@ static struct blame_origin *find_rename(struct commit *parent,\n \tdiff_setup_done(&diff_opts);\n \n \tif (is_null_oid(&origin->commit->object.oid))\n-\t\tdo_diff_cache(&parent->maybe_tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n-\t\t\t      &origin->commit->maybe_tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t      get_commit_tree_oid(origin->commit),\n \t\t\t      \"\", &diff_opts);\n \tdiffcore_std(&diff_opts);\n \n@@ -1257,10 +1257,10 @@ static void find_copy_in_parent(struct blame_scoreboard *sb,\n \t\tdiff_opts.flags.find_copies_harder = 1;\n \n \tif (is_null_oid(&target->commit->object.oid))\n-\t\tdo_diff_cache(&parent->maybe_tree->object.oid, &diff_opts);\n+\t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n \telse\n-\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n-\t\t\t      &target->commit->maybe_tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t      get_commit_tree_oid(target->commit),\n \t\t\t      \"\", &diff_opts);\n \n \tif (!diff_opts.flags.find_copies_harder)\ndiff --git a/builtin/checkout.c b/builtin/checkout.c\nindex b15fed5d85..3c8b2d0c27 100644\n--- a/builtin/checkout.c\n+++ b/builtin/checkout.c\n@@ -484,7 +484,8 @@ static int merge_working_tree(const struct checkout_opts *opts,\n \n \tresolve_undo_clear();\n \tif (opts->force) {\n-\t\tret = reset_tree(new_branch_info->commit->maybe_tree, opts, 1, writeout_error);\n+\t\tret = reset_tree(get_commit_tree(new_branch_info->commit),\n+\t\t\t\t opts, 1, writeout_error);\n \t\tif (ret)\n \t\t\treturn ret;\n \t} else {\n@@ -570,18 +571,23 @@ static int merge_working_tree(const struct checkout_opts *opts,\n \t\t\to.verbosity = 0;\n \t\t\twork = write_tree_from_memory(&o);\n \n-\t\t\tret = reset_tree(new_branch_info->commit->maybe_tree, opts, 1,\n+\t\t\tret = reset_tree(get_commit_tree(new_branch_info->commit),\n+\t\t\t\t\t opts, 1,\n \t\t\t\t\t writeout_error);\n \t\t\tif (ret)\n \t\t\t\treturn ret;\n \t\t\to.ancestor = old_branch_info->name;\n \t\t\to.branch1 = new_branch_info->name;\n \t\t\to.branch2 = \"local\";\n-\t\t\tret = merge_trees(&o, new_branch_info->commit->maybe_tree, work,\n-\t\t\t\told_branch_info->commit->maybe_tree, &result);\n+\t\t\tret = merge_trees(&o,\n+\t\t\t\t\t  get_commit_tree(new_branch_info->commit),\n+\t\t\t\t\t  work,\n+\t\t\t\t\t  get_commit_tree(old_branch_info->commit),\n+\t\t\t\t\t  &result);\n \t\t\tif (ret < 0)\n \t\t\t\texit(128);\n-\t\t\tret = reset_tree(new_branch_info->commit->maybe_tree, opts, 0,\n+\t\t\tret = reset_tree(get_commit_tree(new_branch_info->commit),\n+\t\t\t\t\t opts, 0,\n \t\t\t\t\t writeout_error);\n \t\t\tstrbuf_release(&o.obuf);\n \t\t\tif (ret)\n@@ -1002,7 +1008,7 @@ static int parse_branchname_arg(int argc, const char **argv,\n \t\t*source_tree = parse_tree_indirect(rev);\n \t} else {\n \t\tparse_commit_or_die(new_branch_info->commit);\n-\t\t*source_tree = new_branch_info->commit->maybe_tree;\n+\t\t*source_tree = get_commit_tree(new_branch_info->commit);\n \t}\n \n \tif (!*source_tree)                   /* case (1): want a tree */\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 34f18a5f3f..bfefff3a84 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -398,7 +398,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t\tif (!obj)\n \t\t\tdie(_(\"invalid object '%s' given.\"), name);\n \t\tif (obj->type == OBJ_COMMIT)\n-\t\t\tobj = &((struct commit *)obj)->maybe_tree->object;\n+\t\t\tobj = &get_commit_tree(((struct commit *)obj))->object;\n \n \t\tif (obj->type == OBJ_TREE) {\n \t\t\tobj->flags |= flags;\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 91e526b30d..c1304234cd 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -578,11 +578,11 @@ static void handle_commit(struct commit *commit, struct rev_info *rev,\n \t    get_object_mark(&commit->parents->item->object) != 0 &&\n \t    !full_tree) {\n \t\tparse_commit_or_die(commit->parents->item);\n-\t\tdiff_tree_oid(&commit->parents->item->maybe_tree->object.oid,\n-\t\t\t      &commit->maybe_tree->object.oid, \"\", &rev->diffopt);\n+\t\tdiff_tree_oid(get_commit_tree_oid(commit->parents->item),\n+\t\t\t      get_commit_tree_oid(commit), \"\", &rev->diffopt);\n \t}\n \telse\n-\t\tdiff_root_tree_oid(&commit->maybe_tree->object.oid,\n+\t\tdiff_root_tree_oid(get_commit_tree_oid(commit),\n \t\t\t\t   \"\", &rev->diffopt);\n \n \t/* Export the referenced blobs, and remember the marks. */\ndiff --git a/builtin/log.c b/builtin/log.c\nindex f603b53318..25b4cb3347 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1067,8 +1067,8 @@ static void make_cover_letter(struct rev_info *rev, int use_stdout,\n \n \tdiff_setup_done(&opts);\n \n-\tdiff_tree_oid(&origin->maybe_tree->object.oid,\n-\t\t      &head->maybe_tree->object.oid,\n+\tdiff_tree_oid(get_commit_tree_oid(origin),\n+\t\t      get_commit_tree_oid(head),\n \t\t      \"\", &opts);\n \tdiffcore_std(&opts);\n \tdiff_flush(&opts);\ndiff --git a/builtin/reflog.c b/builtin/reflog.c\nindex b17eabc009..88d0c8378c 100644\n--- a/builtin/reflog.c\n+++ b/builtin/reflog.c\n@@ -154,7 +154,7 @@ static int commit_is_complete(struct commit *commit)\n \t\tfor (i = 0; i < found.nr; i++) {\n \t\t\tstruct commit *c =\n \t\t\t\t(struct commit *)found.objects[i].item;\n-\t\t\tif (!tree_is_complete(&c->maybe_tree->object.oid)) {\n+\t\t\tif (!tree_is_complete(get_commit_tree_oid(c))) {\n \t\t\t\tis_incomplete = 1;\n \t\t\t\tc->object.flags |= INCOMPLETE;\n \t\t\t}\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 005b4a753e..9f37d84209 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -369,7 +369,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n \t\tuint32_t packedDate[2];\n \n \t\tparse_commit(*list);\n-\t\thashwrite(f, (*list)->maybe_tree->object.oid.hash, hash_len);\n+\t\thashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);\n \n \t\tparent = (*list)->parents;\n \ndiff --git a/contrib/coccinelle/commit.cocci b/contrib/coccinelle/commit.cocci\nnew file mode 100644\nindex 0000000000..ac38525941\n--- /dev/null\n+++ b/contrib/coccinelle/commit.cocci\n@@ -0,0 +1,30 @@\n+@@\n+expression c;\n+@@\n+- &c->maybe_tree->object.oid\n++ get_commit_tree_oid(c)\n+\n+@@\n+expression c;\n+@@\n+- c->maybe_tree->object.oid.hash\n++ get_commit_tree_oid(c)->hash\n+\n+@@\n+expression c;\n+@@\n+- c->maybe_tree\n++ get_commit_tree(c)\n+\n+@@\n+expression c;\n+expression s;\n+@@\n+- get_commit_tree(c) = s\n++ c->maybe_tree = s\n+\n+@@\n+expression c;\n+@@\n+- return get_commit_tree(c);\n++ return c->maybe_tree;\ndiff --git a/fsck.c b/fsck.c\nindex 3228ca5bee..695fd71b13 100644\n--- a/fsck.c\n+++ b/fsck.c\n@@ -396,9 +396,11 @@ static int fsck_walk_commit(struct commit *commit, void *data, struct fsck_optio\n \n \tname = get_object_name(options, &commit->object);\n \tif (name)\n-\t\tput_object_name(options, &commit->maybe_tree->object, \"%s:\", name);\n+\t\tput_object_name(options, &get_commit_tree(commit)->object,\n+\t\t\t\t\"%s:\", name);\n \n-\tresult = options->walk((struct object *)commit->maybe_tree, OBJ_TREE, data, options);\n+\tresult = options->walk((struct object *)get_commit_tree(commit),\n+\t\t\t       OBJ_TREE, data, options);\n \tif (result < 0)\n \t\treturn result;\n \tres = result;\n@@ -772,7 +774,7 @@ static int fsck_commit_buffer(struct commit *commit, const char *buffer,\n \terr = fsck_ident(&buffer, &commit->object, options);\n \tif (err)\n \t\treturn err;\n-\tif (!commit->maybe_tree) {\n+\tif (!get_commit_tree(commit)) {\n \t\terr = report(options, &commit->object, FSCK_MSG_BAD_TREE, \"could not load commit's tree %s\", sha1_to_hex(tree_sha1));\n \t\tif (err)\n \t\t\treturn err;\ndiff --git a/http-push.c b/http-push.c\nindex d83479f32f..53a217291e 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1330,7 +1330,7 @@ static int get_delta(struct rev_info *revs, struct remote_lock *lock)\n \tint count = 0;\n \n \twhile ((commit = get_revision(revs)) != NULL) {\n-\t\tp = process_tree(commit->maybe_tree, p);\n+\t\tp = process_tree(get_commit_tree(commit), p);\n \t\tcommit->object.flags |= LOCAL;\n \t\tif (!(commit->object.flags & UNINTERESTING))\n \t\t\tcount += add_send_request(&commit->object, lock);\ndiff --git a/line-log.c b/line-log.c\nindex e714969ca2..437d44c00a 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -817,8 +817,8 @@ static void queue_diffs(struct line_log_data *range,\n \tassert(commit);\n \n \tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n-\tdiff_tree_oid(parent ? &parent->maybe_tree->object.oid : NULL,\n-\t\t      &commit->maybe_tree->object.oid, \"\", opt);\n+\tdiff_tree_oid(parent ? get_commit_tree_oid(parent) : NULL,\n+\t\t      get_commit_tree_oid(commit), \"\", opt);\n \tif (opt->detect_rename) {\n \t\tfilter_diffs_for_paths(range, 1);\n \t\tif (diff_might_be_rename())\ndiff --git a/list-objects.c b/list-objects.c\nindex bfd09f545c..3eec510357 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -195,7 +195,7 @@ static void mark_edge_parents_uninteresting(struct commit *commit,\n \t\tstruct commit *parent = parents->item;\n \t\tif (!(parent->object.flags & UNINTERESTING))\n \t\t\tcontinue;\n-\t\tmark_tree_uninteresting(parent->maybe_tree);\n+\t\tmark_tree_uninteresting(get_commit_tree(parent));\n \t\tif (revs->edge_hint && !(parent->object.flags & SHOWN)) {\n \t\t\tparent->object.flags |= SHOWN;\n \t\t\tshow_edge(parent);\n@@ -212,7 +212,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\tstruct commit *commit = list->item;\n \n \t\tif (commit->object.flags & UNINTERESTING) {\n-\t\t\tmark_tree_uninteresting(commit->maybe_tree);\n+\t\t\tmark_tree_uninteresting(get_commit_tree(commit));\n \t\t\tif (revs->edge_hint_aggressive && !(commit->object.flags & SHOWN)) {\n \t\t\t\tcommit->object.flags |= SHOWN;\n \t\t\t\tshow_edge(commit);\n@@ -227,7 +227,7 @@ void mark_edges_uninteresting(struct rev_info *revs, show_edge_fn show_edge)\n \t\t\tstruct commit *commit = (struct commit *)obj;\n \t\t\tif (obj->type != OBJ_COMMIT || !(obj->flags & UNINTERESTING))\n \t\t\t\tcontinue;\n-\t\t\tmark_tree_uninteresting(commit->maybe_tree);\n+\t\t\tmark_tree_uninteresting(get_commit_tree(commit));\n \t\t\tif (!(obj->flags & SHOWN)) {\n \t\t\t\tobj->flags |= SHOWN;\n \t\t\t\tshow_edge(commit);\n@@ -300,8 +300,8 @@ static void do_traverse(struct rev_info *revs,\n \t\t * an uninteresting boundary commit may not have its tree\n \t\t * parsed yet, but we are not going to show them anyway\n \t\t */\n-\t\tif (commit->maybe_tree)\n-\t\t\tadd_pending_tree(revs, commit->maybe_tree);\n+\t\tif (get_commit_tree(commit))\n+\t\t\tadd_pending_tree(revs, get_commit_tree(commit));\n \t\tshow_commit(commit, show_data);\n \n \t\tif (revs->tree_blobs_in_commit_order)\ndiff --git a/log-tree.c b/log-tree.c\nindex 99499af57c..c106bd70df 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -806,7 +806,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\treturn 0;\n \n \tparse_commit_or_die(commit);\n-\toid = &commit->maybe_tree->object.oid;\n+\toid = get_commit_tree_oid(commit);\n \n \t/* Root commit? */\n \tparents = get_saved_parents(opt, commit);\n@@ -831,7 +831,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\t\t * we merged _in_.\n \t\t\t */\n \t\t\tparse_commit_or_die(parents->item);\n-\t\t\tdiff_tree_oid(&parents->item->maybe_tree->object.oid,\n+\t\t\tdiff_tree_oid(get_commit_tree_oid(parents->item),\n \t\t\t\t      oid, \"\", &opt->diffopt);\n \t\t\tlog_tree_diff_flush(opt);\n \t\t\treturn !opt->loginfo;\n@@ -846,7 +846,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log\n \t\tstruct commit *parent = parents->item;\n \n \t\tparse_commit_or_die(parent);\n-\t\tdiff_tree_oid(&parent->maybe_tree->object.oid,\n+\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n \t\t\t      oid, \"\", &opt->diffopt);\n \t\tlog_tree_diff_flush(opt);\n \ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 67886a4ff8..a7e1938b8a 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -2154,8 +2154,8 @@ int merge_recursive(struct merge_options *o,\n \t\tread_cache();\n \n \to->ancestor = \"merged common ancestors\";\n-\tclean = merge_trees(o, h1->maybe_tree, h2->maybe_tree,\n-\t\t\t    merged_common_ancestors->maybe_tree,\n+\tclean = merge_trees(o, get_commit_tree(h1), get_commit_tree(h2),\n+\t\t\t    get_commit_tree(merged_common_ancestors),\n \t\t\t    &mrtree);\n \tif (clean < 0) {\n \t\tflush_output(o);\ndiff --git a/notes-merge.c b/notes-merge.c\nindex 1d3edc8942..4a73a2169b 100644\n--- a/notes-merge.c\n+++ b/notes-merge.c\n@@ -600,14 +600,14 @@ int notes_merge(struct notes_merge_options *o,\n \t\t\tprintf(\"No merge base found; doing history-less merge\\n\");\n \t} else if (!bases->next) {\n \t\tbase_oid = &bases->item->object.oid;\n-\t\tbase_tree_oid = &bases->item->maybe_tree->object.oid;\n+\t\tbase_tree_oid = get_commit_tree_oid(bases->item);\n \t\tif (o->verbosity >= 4)\n \t\t\tprintf(\"One merge base found (%.7s)\\n\",\n \t\t\t       oid_to_hex(base_oid));\n \t} else {\n \t\t/* TODO: How to handle multiple merge-bases? */\n \t\tbase_oid = &bases->item->object.oid;\n-\t\tbase_tree_oid = &bases->item->maybe_tree->object.oid;\n+\t\tbase_tree_oid = get_commit_tree_oid(bases->item);\n \t\tif (o->verbosity >= 3)\n \t\t\tprintf(\"Multiple merge bases found. Using the first \"\n \t\t\t\t\"(%.7s)\\n\", oid_to_hex(base_oid));\n@@ -634,8 +634,9 @@ int notes_merge(struct notes_merge_options *o,\n \t\tgoto found_result;\n \t}\n \n-\tresult = merge_from_diffs(o, base_tree_oid, &local->maybe_tree->object.oid,\n-\t\t\t\t  &remote->maybe_tree->object.oid, local_tree);\n+\tresult = merge_from_diffs(o, base_tree_oid,\n+\t\t\t\t  get_commit_tree_oid(local),\n+\t\t\t\t  get_commit_tree_oid(remote), local_tree);\n \n \tif (result != 0) { /* non-trivial merge (with or without conflicts) */\n \t\t/* Commit (partial) result */\ndiff --git a/packfile.c b/packfile.c\nindex 3eb9c4a36e..88ba819151 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1925,7 +1925,7 @@ static int add_promisor_object(const struct object_id *oid,\n \t\tstruct commit *commit = (struct commit *) obj;\n \t\tstruct commit_list *parents = commit->parents;\n \n-\t\toidset_insert(set, &commit->maybe_tree->object.oid);\n+\t\toidset_insert(set, get_commit_tree_oid(commit));\n \t\tfor (; parents; parents = parents->next)\n \t\t\toidset_insert(set, &parents->item->object.oid);\n \t} else if (obj->type == OBJ_TAG) {\ndiff --git a/pretty.c b/pretty.c\nindex 42095ea495..15997f5e01 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -1161,10 +1161,11 @@ static size_t format_commit_one(struct strbuf *sb, /* in UTF-8 */\n \t\tstrbuf_addstr(sb, diff_get_color(c->auto_color, DIFF_RESET));\n \t\treturn 1;\n \tcase 'T':\t\t/* tree hash */\n-\t\tstrbuf_addstr(sb, oid_to_hex(&commit->maybe_tree->object.oid));\n+\t\tstrbuf_addstr(sb, oid_to_hex(get_commit_tree_oid(commit)));\n \t\treturn 1;\n \tcase 't':\t\t/* abbreviated tree hash */\n-\t\tstrbuf_add_unique_abbrev(sb, commit->maybe_tree->object.oid.hash,\n+\t\tstrbuf_add_unique_abbrev(sb,\n+\t\t\t\t\t get_commit_tree_oid(commit)->hash,\n \t\t\t\t\t c->pretty_ctx->abbrev);\n \t\treturn 1;\n \tcase 'P':\t\t/* parent hashes */\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 783a3ee6cf..e201bf60c6 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -815,7 +815,7 @@ static void grab_commit_values(struct atom_value *val, int deref, struct object\n \t\tif (deref)\n \t\t\tname++;\n \t\tif (!strcmp(name, \"tree\")) {\n-\t\t\tv->s = xstrdup(oid_to_hex(&commit->maybe_tree->object.oid));\n+\t\t\tv->s = xstrdup(oid_to_hex(get_commit_tree_oid(commit)));\n \t\t}\n \t\telse if (!strcmp(name, \"numparent\")) {\n \t\t\tv->value = commit_list_count(commit->parents);\ndiff --git a/revision.c b/revision.c\nindex 7d66e32e83..496db63b4b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -440,8 +440,8 @@ static void file_change(struct diff_options *options,\n static int rev_compare_tree(struct rev_info *revs,\n \t\t\t    struct commit *parent, struct commit *commit)\n {\n-\tstruct tree *t1 = parent->maybe_tree;\n-\tstruct tree *t2 = commit->maybe_tree;\n+\tstruct tree *t1 = get_commit_tree(parent);\n+\tstruct tree *t2 = get_commit_tree(commit);\n \n \tif (!t1)\n \t\treturn REV_TREE_NEW;\n@@ -477,7 +477,7 @@ static int rev_compare_tree(struct rev_info *revs,\n static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n {\n \tint retval;\n-\tstruct tree *t1 = commit->maybe_tree;\n+\tstruct tree *t1 = get_commit_tree(commit);\n \n \tif (!t1)\n \t\treturn 0;\n@@ -615,7 +615,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tif (!revs->prune)\n \t\treturn;\n \n-\tif (!commit->maybe_tree)\n+\tif (!get_commit_tree(commit))\n \t\treturn;\n \n \tif (!commit->parents) {\ndiff --git a/sequencer.c b/sequencer.c\nindex 3b2823c8b5..a5798b16d3 100644\n--- a/sequencer.c\n+++ b/sequencer.c\n@@ -499,8 +499,8 @@ static int do_recursive_merge(struct commit *base, struct commit *next,\n \to.show_rename_progress = 1;\n \n \thead_tree = parse_tree_indirect(head);\n-\tnext_tree = next ? next->maybe_tree : empty_tree();\n-\tbase_tree = base ? base->maybe_tree : empty_tree();\n+\tnext_tree = next ? get_commit_tree(next) : empty_tree();\n+\tbase_tree = base ? get_commit_tree(base) : empty_tree();\n \n \tfor (xopt = opts->xopts; xopt != opts->xopts + opts->xopts_nr; xopt++)\n \t\tparse_merge_opt(&o, *xopt);\n@@ -561,7 +561,7 @@ static int is_index_unchanged(void)\n \t\t\treturn error(_(\"unable to update cache tree\"));\n \n \treturn !oidcmp(&active_cache_tree->oid,\n-\t\t       &head_commit->maybe_tree->object.oid);\n+\t\t       get_commit_tree_oid(head_commit));\n }\n \n static int write_author_script(const char *message)\n@@ -1118,7 +1118,7 @@ static int try_to_commit(struct strbuf *msg, const char *author,\n \t}\n \n \tif (!(flags & ALLOW_EMPTY) && !oidcmp(current_head ?\n-\t\t\t\t\t      &current_head->maybe_tree->object.oid :\n+\t\t\t\t\t      get_commit_tree_oid(current_head) :\n \t\t\t\t\t      &empty_tree_oid, &tree)) {\n \t\tres = 1; /* run 'git commit' to display error message */\n \t\tgoto out;\n@@ -1216,12 +1216,12 @@ static int is_original_commit_empty(struct commit *commit)\n \t\tif (parse_commit(parent))\n \t\t\treturn error(_(\"could not parse parent commit %s\"),\n \t\t\t\toid_to_hex(&parent->object.oid));\n-\t\tptree_oid = &parent->maybe_tree->object.oid;\n+\t\tptree_oid = get_commit_tree_oid(parent);\n \t} else {\n \t\tptree_oid = the_hash_algo->empty_tree; /* commit is root */\n \t}\n \n-\treturn !oidcmp(ptree_oid, &commit->maybe_tree->object.oid);\n+\treturn !oidcmp(ptree_oid, get_commit_tree_oid(commit));\n }\n \n /*\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 26b22cb628..0f408e9143 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -896,7 +896,7 @@ struct object *peel_to_type(const char *name, int namelen,\n \t\tif (o->type == OBJ_TAG)\n \t\t\to = ((struct tag*) o)->tagged;\n \t\telse if (o->type == OBJ_COMMIT)\n-\t\t\to = &(((struct commit *) o)->maybe_tree->object);\n+\t\t\to = &(get_commit_tree(((struct commit *)o))->object);\n \t\telse {\n \t\t\tif (name)\n \t\t\t\terror(\"%.*s: expected %s type, but the object \"\ndiff --git a/tree.c b/tree.c\nindex dbc5e0be54..dec53f3eca 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -109,7 +109,7 @@ static int read_tree_1(struct tree *tree, struct strbuf *base,\n \t\t\t\t    oid_to_hex(entry.oid),\n \t\t\t\t    base->buf, entry.path);\n \n-\t\t\toidcpy(&oid, &commit->maybe_tree->object.oid);\n+\t\t\toidcpy(&oid, get_commit_tree_oid(commit));\n \t\t}\n \t\telse\n \t\t\tcontinue;\n@@ -248,7 +248,7 @@ struct tree *parse_tree_indirect(const struct object_id *oid)\n \t\tif (obj->type == OBJ_TREE)\n \t\t\treturn (struct tree *) obj;\n \t\telse if (obj->type == OBJ_COMMIT)\n-\t\t\tobj = &(((struct commit *) obj)->maybe_tree->object);\n+\t\t\tobj = &(get_commit_tree(((struct commit *)obj))->object);\n \t\telse if (obj->type == OBJ_TAG)\n \t\t\tobj = ((struct tag *) obj)->tagged;\n \t\telse\ndiff --git a/walker.c b/walker.c\nindex 1d5f3059a2..f51b855872 100644\n--- a/walker.c\n+++ b/walker.c\n@@ -87,7 +87,7 @@ static int process_commit(struct walker *walker, struct commit *commit)\n \twalker_say(walker, \"walk %s\\n\", oid_to_hex(&commit->object.oid));\n \n \tif (walker->get_tree) {\n-\t\tif (process(walker, &commit->maybe_tree->object))\n+\t\tif (process(walker, &get_commit_tree(commit)->object))\n \t\t\treturn -1;\n \t\tif (!walker->get_all)\n \t\t\twalker->get_tree = 0;\n-- \n2.17.0\n\n"},{"id":"343989","messageId":"20180406190919.167092-5-dstolee@microsoft.com","threadId":"48210","inReplyTo":"20180406190919.167092-1-dstolee@microsoft.com","subject":"[PATCH v2 4/4] commit-graph: lazy-load trees for commits","fromName":"Derrick Stolee","fromEmail":"dstolee@microsoft.com","sentAt":"2018-04-06T19:09:46Z","receivedAt":"2018-04-06T19:09:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The commit-graph file provides quick access to commit data, including\nthe OID of the root tree for each commit in the graph. When performing\na deep commit-graph walk, we may not need to load most of the trees\nfor these commits.\n\nDelay loading the tree object for a commit loaded from the graph\nuntil requested via get_commit_tree(). Do not lazy-load trees for\ncommits not in the graph, since that requires duplicate parsing\nand the relative peformance improvement when trees are not needed\nis small.\n\nOn the Linux repository, performance tests were run for the following\ncommand:\n\n    git log --graph --oneline -1000\n\n    Before: 0.92s\n    After:  0.66s\n    Rel %: -28.3%\n\nAdding '-- kernel/' to the command requires loading the root tree\nfor every commit that is walked. There was no measureable performance\nchange as a result of this patch.\n\nSigned-off-by: Derrick Stolee <dstolee@microsoft.com>\n---\n commit-graph.c | 26 +++++++++++++++++++++++---\n commit-graph.h |  2 ++\n commit.c       |  8 +++++++-\n commit.h       |  6 ++++++\n 4 files changed, 38 insertions(+), 4 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 9f37d84209..a5de6f3102 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -247,7 +247,6 @@ static struct commit_list **insert_parent_or_die(struct commit_graph *g,\n \n static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t pos)\n {\n-\tstruct object_id oid;\n \tuint32_t edge_value;\n \tuint32_t *parent_data_ptr;\n \tuint64_t date_low, date_high;\n@@ -257,8 +256,7 @@ static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uin\n \titem->object.parsed = 1;\n \titem->graph_pos = pos;\n \n-\thashcpy(oid.hash, commit_data);\n-\titem->maybe_tree = lookup_tree(&oid);\n+\titem->maybe_tree = NULL;\n \n \tdate_high = get_be32(commit_data + g->hash_len + 8) & 0x3;\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n@@ -317,6 +315,28 @@ int parse_commit_in_graph(struct commit *item)\n \treturn 0;\n }\n \n+static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c)\n+{\n+\tstruct object_id oid;\n+\tconst unsigned char *commit_data = g->chunk_commit_data +\n+\t\t\t\t\t   GRAPH_DATA_WIDTH * (c->graph_pos);\n+\n+\thashcpy(oid.hash, commit_data);\n+\tc->maybe_tree = lookup_tree(&oid);\n+\n+\treturn c->maybe_tree;\n+}\n+\n+struct tree *get_commit_tree_in_graph(const struct commit *c)\n+{\n+\tif (c->maybe_tree)\n+\t\treturn c->maybe_tree;\n+\tif (c->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\t\tBUG(\"get_commit_tree_in_graph called from non-commit-graph commit\");\n+\n+\treturn load_tree_for_commit(commit_graph, (struct commit *)c);\n+}\n+\n static void write_graph_chunk_fanout(struct hashfile *f,\n \t\t\t\t     struct commit **commits,\n \t\t\t\t     int nr_commits)\ndiff --git a/commit-graph.h b/commit-graph.h\nindex e1d8580c98..260a468e73 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -17,6 +17,8 @@ char *get_commit_graph_filename(const char *obj_dir);\n  */\n int parse_commit_in_graph(struct commit *item);\n \n+struct tree *get_commit_tree_in_graph(const struct commit *c);\n+\n struct commit_graph {\n \tint graph_fd;\n \ndiff --git a/commit.c b/commit.c\nindex aea2ca1f8b..711f674c18 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -298,7 +298,13 @@ void free_commit_buffer(struct commit *commit)\n \n struct tree *get_commit_tree(const struct commit *commit)\n {\n-\treturn commit->maybe_tree;\n+\tif (commit->maybe_tree || !commit->object.parsed)\n+\t\treturn commit->maybe_tree;\n+\n+\tif (commit->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\t\tBUG(\"commit has NULL tree, but was not loaded from commit-graph\");\n+\n+\treturn get_commit_tree_in_graph(commit);\n }\n \n struct object_id *get_commit_tree_oid(const struct commit *commit)\ndiff --git a/commit.h b/commit.h\nindex dc4bf97d9f..23a3f364ed 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -22,6 +22,12 @@ struct commit {\n \tunsigned int index;\n \ttimestamp_t date;\n \tstruct commit_list *parents;\n+\n+\t/*\n+\t * If the commit is loaded from the commit-graph file, then this\n+\t * member may be NULL. Only access it through get_commit_tree()\n+\t * or get_commit_tree_oid().\n+\t */\n \tstruct tree *maybe_tree;\n \tuint32_t graph_pos;\n };\n-- \n2.17.0\n\n"},{"id":"343990","messageId":"20180406192146.GC921@sigill.intra.peff.net","threadId":"48210","inReplyTo":"20180406190919.167092-1-dstolee@microsoft.com","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-04-06T19:21:46Z","receivedAt":"2018-04-06T19:21:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 06, 2018 at 07:09:30PM +0000, Derrick Stolee wrote:\n\n> Derrick Stolee (4):\n>   treewide: rename tree to maybe_tree\n>   commit: create get_commit_tree() method\n>   treewide: replace maybe_tree with accessor methods\n>   commit-graph: lazy-load trees for commits\n\nI gave this only a cursory read, but it addresses my concern from the\nprevious round.\n\nIf I were doing it myself, I probably would have folded patches 1 and 3\ntogether. They are touching all the same spots, and it would be an error\nfor any case converted in patch 1 to not get converted in patch 3. I'm\nassuming you caught them all due to Coccinelle, though IMHO it is\nsomewhat overkill here. By folding them together the compiler could tell\nyou which spots you missed.\n\nAnd going forward, I doubt it is going to be a common error for people\nto use maybe_tree directly. Between the name and the warning comment,\nyou'd have to really try to shoot yourself in the foot with it. The\nprimary concern was catching people using the existing \"tree\" name,\nwhose semantics changed.\n\nAll that said, I'm fine with having it done this way, too.\n\n-Peff\n"},{"id":"343995","messageId":"f3a8b9ff-4aba-100f-e59e-613f6a094513@gmail.com","threadId":"48210","inReplyTo":"20180406192146.GC921@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-04-06T19:41:53Z","receivedAt":"2018-04-06T19:42:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/6/2018 3:21 PM, Jeff King wrote:\n> On Fri, Apr 06, 2018 at 07:09:30PM +0000, Derrick Stolee wrote:\n>\n>> Derrick Stolee (4):\n>>    treewide: rename tree to maybe_tree\n>>    commit: create get_commit_tree() method\n>>    treewide: replace maybe_tree with accessor methods\n>>    commit-graph: lazy-load trees for commits\n> I gave this only a cursory read, but it addresses my concern from the\n> previous round.\n>\n> If I were doing it myself, I probably would have folded patches 1 and 3\n> together. They are touching all the same spots, and it would be an error\n> for any case converted in patch 1 to not get converted in patch 3. I'm\n> assuming you caught them all due to Coccinelle, though IMHO it is\n> somewhat overkill here. By folding them together the compiler could tell\n> you which spots you missed.\n>\n> And going forward, I doubt it is going to be a common error for people\n> to use maybe_tree directly. Between the name and the warning comment,\n> you'd have to really try to shoot yourself in the foot with it. The\n> primary concern was catching people using the existing \"tree\" name,\n> whose semantics changed.\n>\n> All that said, I'm fine with having it done this way, too.\n\nThanks. As a double-check that I caught all of the 'maybe_tree' \naccesses, I ran the following:\n\n$ git grep maybe_tree | grep -v get_commit_tree\ncommit-graph.c: item->maybe_tree = NULL;\ncommit-graph.c: c->maybe_tree = lookup_tree(&oid);\ncommit-graph.c: return c->maybe_tree;\ncommit-graph.c: if (c->maybe_tree)\ncommit-graph.c:         return c->maybe_tree;\ncommit.c:       if (commit->maybe_tree || !commit->object.parsed)\ncommit.c:               return commit->maybe_tree;\ncommit.c:       item->maybe_tree = lookup_tree(&parent);\ncommit.h:       struct tree *maybe_tree;\ncontrib/coccinelle/commit.cocci:- &c->maybe_tree->object.oid\ncontrib/coccinelle/commit.cocci:- c->maybe_tree->object.oid.hash\ncontrib/coccinelle/commit.cocci:- c->maybe_tree\ncontrib/coccinelle/commit.cocci:+ c->maybe_tree = s\ncontrib/coccinelle/commit.cocci:+ return c->maybe_tree;\nmerge-recursive.c:      commit->maybe_tree = tree;\n\nThanks,\n-Stolee\n"},{"id":"343996","messageId":"CAGZ79kbrFRsnYQ-VJsUU5hXfKKVoHqE1BE3-4s4Q=QXvXJ4L3Q@mail.gmail.com","threadId":"48210","inReplyTo":"20180406192146.GC921@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-04-06T19:45:13Z","receivedAt":"2018-04-06T19:45:21Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Apr 6, 2018 at 12:21 PM, Jeff King <peff@peff.net> wrote:\n> On Fri, Apr 06, 2018 at 07:09:30PM +0000, Derrick Stolee wrote:\n>\n>> Derrick Stolee (4):\n>>   treewide: rename tree to maybe_tree\n>>   commit: create get_commit_tree() method\n>>   treewide: replace maybe_tree with accessor methods\n>>   commit-graph: lazy-load trees for commits\n>\n> I gave this only a cursory read, but it addresses my concern from the\n> previous round.\n\nSame here.\n\nThanks,\nStefan\n"},{"id":"344074","messageId":"86y3hyeu6c.fsf@gmail.com","threadId":"48210","inReplyTo":"20180406190919.167092-1-dstolee@microsoft.com","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-04-07T18:40:59Z","receivedAt":"2018-04-07T18:41:09Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <dstolee@microsoft.com> writes:\n\n[...]\n> On the Linux repository, performance tests were run for the following\n> command:\n>\n>     git log --graph --oneline -1000\n>\n>     Before: 0.92s\n>     After:  0.66s\n>     Rel %: -28.3%\n>\n> Adding '-- kernel/' to the command requires loading the root tree\n> for every commit that is walked. There was no measureable performance\n> change as a result of this patch.\n\nIn the \"Git Merge contributor summit notes\" [1] one can read that:\n\n> - VSTS adds bloom filters to know which paths have changed on the commit\n> - tree-same check in the bloom filter is fast; speeds up file history checks\n> - if the file history is _very_ sparse, then bloom filter is useful\n\nCould this method speed up also the second case mentioned here?  Can\nanyone explain how this \"path-changed bloom filter\" works in VSTS?\n\nCould we add something like this to the commit-graph file?\n\n[1]: https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/\n\nBest regards,\n--\nJakub Narębski\n"},{"id":"344083","messageId":"eb861bc6-b9f0-ccaa-7cb6-abdb0d343c3d@gmail.com","threadId":"48210","inReplyTo":"86y3hyeu6c.fsf@gmail.com","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-04-08T01:17:47Z","receivedAt":"2018-04-08T01:17:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/7/2018 2:40 PM, Jakub Narebski wrote:\n> Derrick Stolee <dstolee@microsoft.com> writes:\n>\n> [...]\n>> On the Linux repository, performance tests were run for the following\n>> command:\n>>\n>>      git log --graph --oneline -1000\n>>\n>>      Before: 0.92s\n>>      After:  0.66s\n>>      Rel %: -28.3%\n>>\n>> Adding '-- kernel/' to the command requires loading the root tree\n>> for every commit that is walked. There was no measureable performance\n>> change as a result of this patch.\n> In the \"Git Merge contributor summit notes\" [1] one can read that:\n>\n>> - VSTS adds bloom filters to know which paths have changed on the commit\n>> - tree-same check in the bloom filter is fast; speeds up file history checks\n>> - if the file history is _very_ sparse, then bloom filter is useful\n> Could this method speed up also the second case mentioned here?  Can\n> anyone explain how this \"path-changed bloom filter\" works in VSTS?\n>    \n\nThe idea is simple: for every commit, store a Bloom filter containing \nthe list of paths that are not TREESAME against the first parent. (A \nslight detail: have a max cap on the number of paths, and store simply \n\"TOO_BIG\" for commits with too many diffs.)\n\nWhen performing 'git log -- path' queries, the most important detail for \nconsidering how to advance the walk is whether the commit is TREESAME to \nits first parent. For a deep path in a large repo, this is almost always \ntrue. When a Bloom filter says \"TREESAME\" (i.e. \"this path is not in my \nset\") it is always correct, so we can set the treesame bit and continue \nwithout walking any trees. When a Bloom filter says \"MAYBE NOT TREESAME\" \n(i.e. \"this path is probably in my set\") you only need to do the same \nwork as before: walk the trees to compare against your first parent.\n\nIf a Bloom filter has a false-positive rate of X%, then you can possibly \ndrop your number of tree comparisons by (100-X)%. This is very important \nfor large repos where some paths were changed only ten times or so, the \nfull graph needs to be walked and it is helpful to avoid parsing too \nmany trees.\n\n\n> Could we add something like this to the commit-graph file? \n\nI'm not sure if it is necessary for client-side operations, but it is \none of the reasons the commit-graph file has the idea of an \"optional \nchunk\". It could be added to the file format (without changing version \nnumbers) and be ignored by clients that don't understand it. I could \nalso be gated by a config setting for computing them. My guess is that \nonly server-side operations will need the added response time, and can \nbear the cost of computing them when writing the commit-graph file. \nClients are less likely to be patient waiting for a lot of diff \ncalculations.\n\nIf we add commit-graph file downloads to the protocol, then the server \ncould do this computation and send the data to all clients. But that \nwould be \"secondary\" information that maybe clients want to verify, \nwhich is as difficult as computing it themselves.\n\nThanks,\n\n-Stolee\n\n"},{"id":"344126","messageId":"xmqqr2np70dl.fsf@gitster-ct.c.googlers.com","threadId":"48210","inReplyTo":"20180406192146.GC921@sigill.intra.peff.net","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-04-08T23:18:46Z","receivedAt":"2018-04-08T23:18:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> If I were doing it myself, I probably would have folded patches 1 and 3\n> together. They are touching all the same spots, and it would be an error\n> for any case converted in patch 1 to not get converted in patch 3. I'm\n> assuming you caught them all due to Coccinelle, though IMHO it is\n> somewhat overkill here. By folding them together the compiler could tell\n> you which spots you missed.\n\nYeah, that approach would probably be a more sensible way to assure\nthe safety/correctness of the result to readers better.\n\n>\n> And going forward, I doubt it is going to be a common error for people\n> to use maybe_tree directly. Between the name and the warning comment,\n> you'd have to really try to shoot yourself in the foot with it. The\n> primary concern was catching people using the existing \"tree\" name,\n> whose semantics changed.\n\nYup.\n"},{"id":"344190","messageId":"7930c9bf-4f24-2e76-b522-331a2e9ed5d5@gmail.com","threadId":"48210","inReplyTo":"xmqqr2np70dl.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-04-09T13:15:33Z","receivedAt":"2018-04-09T13:15:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/8/2018 7:18 PM, Junio C Hamano wrote:\n> Jeff King <peff@peff.net> writes:\n>\n>> If I were doing it myself, I probably would have folded patches 1 and 3\n>> together. They are touching all the same spots, and it would be an error\n>> for any case converted in patch 1 to not get converted in patch 3. I'm\n>> assuming you caught them all due to Coccinelle, though IMHO it is\n>> somewhat overkill here. By folding them together the compiler could tell\n>> you which spots you missed.\n> Yeah, that approach would probably be a more sensible way to assure\n> the safety/correctness of the result to readers better.\n\nI don't understand how folding the patches makes the correctness \nclearer, since the rename (1/4) is checked by the compiler and the \nCoccinelle script (3/4) only works after that rename is complete.\n\nThe only thing I can imagine is that it makes smaller patch emails, \nsince there is only one large patch instead of two. In this case, I \nprefer to make changes that are easier to check by automation (compiler \nand coccinelle).\n\nHowever, I will defer to the experts in this regard. If a v3 is \nnecessary, then I will fold the commits together.\n\nThanks,\n-Stolee\n"},{"id":"344215","messageId":"CAGZ79kbV3uM0mkOdnoUF+isGEg_uM-9SKQix96hyQOH1Mg9YNQ@mail.gmail.com","threadId":"48210","inReplyTo":"7930c9bf-4f24-2e76-b522-331a2e9ed5d5@gmail.com","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-04-09T17:25:55Z","receivedAt":"2018-04-09T17:26:01Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Mon, Apr 9, 2018 at 6:15 AM, Derrick Stolee <stolee@gmail.com> wrote:\n\n> I don't understand how folding the patches makes the correctness clearer,\n> since the rename (1/4) is checked by the compiler and the Coccinelle script\n> (3/4) only works after that rename is complete.\n>\n> The only thing I can imagine is that it makes smaller patch emails, since\n> there is only one large patch instead of two. In this case, I prefer to make\n> changes that are easier to check by automation (compiler and coccinelle).\n>\n\nI prefer the offloading to automation, too.\nSo I would vouch for keeping it as-is.\n"},{"id":"344488","messageId":"864lkh5vdj.fsf@gmail.com","threadId":"48210","inReplyTo":"eb861bc6-b9f0-ccaa-7cb6-abdb0d343c3d@gmail.com","subject":"Re: [PATCH v2 0/4] Lazy-load trees when reading commit-graph","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2018-04-11T20:41:12Z","receivedAt":"2018-04-11T20:41:31Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> On 4/7/2018 2:40 PM, Jakub Narebski wrote:\n>> Derrick Stolee <dstolee@microsoft.com> writes:\n>>\n>> [...]\n>>> On the Linux repository, performance tests were run for the following\n>>> command:\n>>>\n>>>      git log --graph --oneline -1000\n>>>\n>>>      Before: 0.92s\n>>>      After:  0.66s\n>>>      Rel %: -28.3%\n>>>\n>>> Adding '-- kernel/' to the command requires loading the root tree\n>>> for every commit that is walked. There was no measureable performance\n>>> change as a result of this patch.\n>>\n>> In the \"Git Merge contributor summit notes\" [1] one can read that:\n>>\n>>> - VSTS adds bloom filters to know which paths have changed on the commit\n>>> - tree-same check in the bloom filter is fast; speeds up file history checks\n>>> - if the file history is _very_ sparse, then bloom filter is useful\n>>\n>> Could this method speed up also the second case mentioned here?  Can\n>> anyone explain how this \"path-changed bloom filter\" works in VSTS?\n>>    \n>\n> The idea is simple: for every commit, store a Bloom filter containing\n> the list of paths that are not TREESAME against the first parent. (A\n> slight detail: have a max cap on the number of paths, and store simply\n> \"TOO_BIG\" for commits with too many diffs.)\n\nIsn't Bloom filter with all bits set to 1 equivalent of \"too big\"? It\nwould answer each query with \"possibly in set, check it\".\n\n> When performing 'git log -- path' queries, the most important detail\n> for considering how to advance the walk is whether the commit is\n> TREESAME to its first parent. For a deep path in a large repo, this is\n> almost always true. When a Bloom filter says \"TREESAME\" (i.e. \"this\n> path is not in my set\") it is always correct, so we can set the\n> treesame bit and continue without walking any trees. When a Bloom\n> filter says \"MAYBE NOT TREESAME\" (i.e. \"this path is probably in my\n> set\") you only need to do the same work as before: walk the trees to\n> compare against your first parent.\n>\n> If a Bloom filter has a false-positive rate of X%, then you can\n> possibly drop your number of tree comparisons by (100-X)%. This is\n> very important for large repos where some paths were changed only ten\n> times or so, the full graph needs to be walked and it is helpful to\n> avoid parsing too many trees.\n\nSo this works only for exact file pathnames, or does checking for\nsubdirectory also work?  I guess it cannot work for globbing patterns\n(like \"git log -- '*.c'\").\n\nI guess that it speeds up \"git log -- <pathname>\", but also \"git blame\n<pathname>\".\n\n\nSidenote: I have stumbled upon https://github.com/efficient/ffbf project\n(fast-forward Bllom filters - for exact matching of large number of\npatterns), where they invent cache-efficient version of Bloom filter\nalgorithm.  The paper that the project is based on also might be\ninteresting, if only because it points to other improvements of classic\nBloom filters.\n\n>> Could we add something like this to the commit-graph file? \n>\n> I'm not sure if it is necessary for client-side operations, but it is\n> one of the reasons the commit-graph file has the idea of an \"optional\n> chunk\". It could be added to the file format (without changing version\n> numbers) and be ignored by clients that don't understand it. I could\n> also be gated by a config setting for computing them. My guess is that\n> only server-side operations will need the added response time, and can\n> bear the cost of computing them when writing the commit-graph\n> file. Clients are less likely to be patient waiting for a lot of diff\n> calculations.\n\nSo the problem is performing large amount of diff calculations.  I\nwonder if it would be possible to add Bloom filters incrementally, when\nfor some reason we need to calculate diff anyway.\n\n>\n> If we add commit-graph file downloads to the protocol, then the server\n> could do this computation and send the data to all clients. But that\n> would be \"secondary\" information that maybe clients want to verify,\n> which is as difficult as computing it themselves.\n\nCan you tell us how much work (how much time) must spend the server to\ncalculate those per-commit \"files changed\" Bloom fillters?\n\nBest,\n--\nJakub Narębski\n"}]}