{"thread":{"id":"54906","subject":"[PATCH 0/8] Cleanups around index operations","startedAt":"2020-12-30T19:27:53Z","lastAt":"2021-01-16T07:02:18Z","messageCount":53,"participants":["Derrick Stolee via GitGitGadget","Elijah Newren","Derrick Stolee","René Scharfe","René Scharfe via GitGitGadget","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":8},"messages":[{"id":"413181","messageId":"pull.829.git.1609356413.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":null,"subject":"[PATCH 0/8] Cleanups around index operations","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:45Z","receivedAt":"2020-12-30T19:27:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"I've taken a professional interest in the index lately, and I've been trying\nmostly to learn about it and measure different operations. Along the way,\nI've seen some possible improvements in documentation, behavior, and\ntracing.\n\nThis series collects most of my thoughts so far, including:\n\n 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches\n 1-5).\n 2. Update documentation about the cached tree extension (Patches 6-7).\n 3. Removing an unnecessary loop from verify_cache() (Patch 8).\n\nThanks, -Stolee\n\n[1]\nhttps://lore.kernel.org/git/pull.828.git.1609302714183.gitgitgadget@gmail.com/\n\nDerrick Stolee (8):\n tree-walk: report recursion counts\n unpack-trees: add trace2 regions\n cache-tree: use trace2 in cache_tree_update()\n cache-tree: trace regions for I/O\n cache-tree: trace regions for prime_cache_tree\n index-format: update preamble to cached tree extension\n index-format: discuss recursion of cached-tree better\n cache-tree: avoid path comparison loop when silent\n\n Documentation/technical/index-format.txt | 39 +++++++++++++++++++-----\n cache-tree.c | 25 +++++++++++++--\n tree-walk.c | 33 ++++++++++++++++++++\n unpack-trees.c | 6 +++-\n 4 files changed, 92 insertions(+), 11 deletions(-)\n\n\nbase-commit: 71ca53e8125e36efbda17293c50027d31681a41f\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-829%2Fderrickstolee%2Fcache-tree%2Fbasics-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-829/derrickstolee/cache-tree/basics-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/829\n-- \ngitgitgadget\n"},{"id":"413182","messageId":"f727880add6e0380248279e1ad79f80762868a6c.1609356413.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 1/8] tree-walk: report recursion counts","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:46Z","receivedAt":"2020-12-30T19:27:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe traverse_trees() method recusively walks through trees, but also\nprunes the tree-walk based on a callback. Some callers, such as\nunpack_trees(), are quite complicated and can have wildly different\nperformance between two different commands.\n\nCreate constants that count these values and then report the results at\nthe end of a process. These counts are cumulative across multiple \"root\"\ninstances of traverse_trees(), but they provide reproducible values for\ndemonstrating improvements to the pruning algorithm when possible.\n\nSigned-off-by: Derrick Stolee \n---\n tree-walk.c | 33 +++++++++++++++++++++++++++++++++\n unpack-trees.c | 1 -\n 2 files changed, 33 insertions(+), 1 deletion(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 0160294712b..2d6226d5f18 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -4,6 +4,7 @@\n #include \"object-store.h\"\n #include \"tree.h\"\n #include \"pathspec.h\"\n+#include \"json-writer.h\"\n \n static const char *get_mode(const char *str, unsigned int *modep)\n {\n@@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)\n \treturn 1;\n }\n \n+static int traverse_trees_atexit_registered;\n+static int traverse_trees_count;\n+static int traverse_trees_cur_depth;\n+static int traverse_trees_max_depth;\n+\n+static void trace2_traverse_trees_statistics_atexit(void)\n+{\n+\tstruct json_writer jw = JSON_WRITER_INIT;\n+\n+\tjw_object_begin(&jw, 0);\n+\tjw_object_intmax(&jw, \"traverse_trees_count\", traverse_trees_count);\n+\tjw_object_intmax(&jw, \"traverse_trees_max_depth\", traverse_trees_max_depth);\n+\tjw_end(&jw);\n+\n+\ttrace2_data_json(\"traverse_trees\", the_repository, \"statistics\", &jw);\n+\n+\tjw_release(&jw);\n+}\n+\n void setup_traverse_info(struct traverse_info *info, const char *base)\n {\n \tsize_t pathlen = strlen(base);\n@@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n \tinfo->namelen = pathlen;\n \tif (pathlen)\n \t\tinfo->prev = &dummy;\n+\n+\tif (trace2_is_enabled() && !traverse_trees_atexit_registered) {\n+\t\tatexit(trace2_traverse_trees_statistics_atexit);\n+\t\ttraverse_trees_atexit_registered = 1;\n+\t}\n }\n \n char *make_traverse_path(char *path, size_t pathlen,\n@@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,\n \tint interesting = 1;\n \tchar *traverse_path;\n \n+\ttraverse_trees_count++;\n+\ttraverse_trees_cur_depth++;\n+\n+\tif (traverse_trees_cur_depth > traverse_trees_max_depth)\n+\t\ttraverse_trees_max_depth = traverse_trees_cur_depth;\n+\n \tif (n >= ARRAY_SIZE(entry))\n \t\tBUG(\"traverse_trees() called with too many trees (%d)\", n);\n \n@@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,\n \tfree(traverse_path);\n \tinfo->traverse_path = NULL;\n \tstrbuf_release(&base);\n+\n+\ttraverse_trees_cur_depth--;\n \treturn error;\n }\n \ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 323280dd48b..02f484604ac 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -1559,7 +1559,6 @@ static void populate_from_existing_patterns(struct unpack_trees_options *o,\n \tfree(sparse);\n }\n \n-\n static int verify_absent(const struct cache_entry *,\n \t\t\t enum unpack_trees_error_types,\n \t\t\t struct unpack_trees_options *);\n-- \ngitgitgadget\n\n"},{"id":"413183","messageId":"802718084a7266429ddf0f5b836bd3fecd55400c.1609356413.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 3/8] cache-tree: use trace2 in cache_tree_update()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:48Z","receivedAt":"2020-12-30T19:27:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis matches a trace_performance_enter()/trace_performance_leave() pair\nadded by 0d1ed59 (unpack-trees: add performance tracing, 2018-08-18).\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex a537a806c16..9efb6748662 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -442,7 +442,9 @@ int cache_tree_update(struct index_state *istate, int flags)\n \tif (i)\n \t\treturn i;\n \ttrace_performance_enter();\n+\ttrace2_region_enter(\"cache_tree\", \"update\", the_repository);\n \ti = update_one(it, cache, entries, \"\", 0, &skip, flags);\n+\ttrace2_region_leave(\"cache_tree\", \"update\", the_repository);\n \ttrace_performance_leave(\"cache_tree_update\");\n \tif (i < 0)\n \t\treturn i;\n-- \ngitgitgadget\n\n"},{"id":"413184","messageId":"6923e6211aaa9e1e144db747c971c6fe35fb4d41.1609356413.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 2/8] unpack-trees: add trace2 regions","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:47Z","receivedAt":"2020-12-30T19:27:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe unpack_trees() method is quite complicated and its performance can\nchange dramatically depending on how it is used. We already have some\nperformance tracing regions, but they have not been updated to the\ntrace2 API. Do so now.\n\nWe already have trace2 regions in unpack_trees.c:clear_ce_flags(), which\nuses a linear scan through the index without recursing into trees.\n\nSigned-off-by: Derrick Stolee \n---\n unpack-trees.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 02f484604ac..7dbd006ac56 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -1579,6 +1579,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\tdie(\"unpack_trees takes at most %d trees\", MAX_UNPACK_TREES);\n \n \ttrace_performance_enter();\n+\ttrace2_region_enter(\"unpack_trees\", \"unpack_trees\", the_repository);\n+\n \tif (!core_apply_sparse_checkout || !o->update)\n \t\to->skip_sparse_checkout = 1;\n \tif (!o->skip_sparse_checkout && !o->pl) {\n@@ -1652,7 +1654,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\t}\n \n \t\ttrace_performance_enter();\n+\t\ttrace2_region_enter(\"unpack_trees\", \"traverse_trees\", the_repository);\n \t\tret = traverse_trees(o->src_index, len, t, &info);\n+\t\ttrace2_region_leave(\"unpack_trees\", \"traverse_trees\", the_repository);\n \t\ttrace_performance_leave(\"traverse_trees\");\n \t\tif (ret < 0)\n \t\t\tgoto return_failed;\n@@ -1740,6 +1744,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n done:\n \tif (free_pattern_list)\n \t\tclear_pattern_list(&pl);\n+\ttrace2_region_leave(\"unpack_trees\", \"unpack_trees\", the_repository);\n \ttrace_performance_leave(\"unpack_trees\");\n \treturn ret;\n \n-- \ngitgitgadget\n\n"},{"id":"413185","messageId":"65feaa497b23b314ed9faa0452408c237f02b197.1609356414.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 4/8] cache-tree: trace regions for I/O","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:49Z","receivedAt":"2020-12-30T19:27:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAs we write or read the cached tree index extension, it can be good to\nisolate how much of the file I/O time is spent constructing this\nin-memory tree from the existing index or writing it out again to the\nnew index file. Use trace2 regions to indicate that we are spending time\non this operation.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 11 ++++++++++-\n 1 file changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 9efb6748662..45fb57b17f3 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -494,7 +494,9 @@ static void write_one(struct strbuf *buffer, struct cache_tree *it,\n \n void cache_tree_write(struct strbuf *sb, struct cache_tree *root)\n {\n+\ttrace2_region_enter(\"cache_tree\", \"write\", the_repository);\n \twrite_one(sb, root, \"\", 0);\n+\ttrace2_region_leave(\"cache_tree\", \"write\", the_repository);\n }\n \n static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)\n@@ -583,9 +585,16 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)\n \n struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)\n {\n+\tstruct cache_tree *result;\n+\n \tif (buffer[0])\n \t\treturn NULL; /* not the whole tree */\n-\treturn read_one(&buffer, &size);\n+\n+\ttrace2_region_enter(\"cache_tree\", \"read\", the_repository);\n+\tresult = read_one(&buffer, &size);\n+\ttrace2_region_leave(\"cache_tree\", \"read\", the_repository);\n+\n+\treturn result;\n }\n \n static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)\n-- \ngitgitgadget\n\n"},{"id":"413186","messageId":"fb9d5468184c4cbb3d80569f685743b9a5b45c8e.1609356414.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 6/8] index-format: update preamble to cached tree extension","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:51Z","receivedAt":"2020-12-30T19:28:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nI had difficulty in my efforts to learn about the cached tree extension\nbased on the documentation and code because I had an incorrect\nassumption about how it behaved. This might be due to some ambiguity in\nthe documentation, so this change modifies the beginning of the cached\ntree format by expanding the description of the feature.\n\nMy hope is that this documentation clarifies a few things:\n\n1. There is an in-memory recursive tree structure that is constructed\n from the extension data. This structure has a few differences, such\n as where the name is stored.\n\n2. What does it mean for an entry to be invalid?\n\n3. When exactly are \"new\" trees created?\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----\n 1 file changed, 30 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex 69edf46c031..c614e136e24 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -138,12 +138,36 @@ Git index format\n \n === Cached tree\n \n- Cached tree extension contains pre-computed hashes for trees that can\n- be derived from the index. It helps speed up tree object generation\n- from index for a new commit.\n-\n- When a path is updated in index, the path must be invalidated and\n- removed from tree cache.\n+ Since the index does not record entries for directories, the cache\n+ entries cannot describe tree objects that already exist in the object\n+ database for regions of the index that are unchanged from an existing\n+ commit. The cached tree extension stores a recursive tree structure that\n+ describes the trees that already exist and completely match sections of\n+ the cache entries. This speeds up tree object generation from the index\n+ for a new commit by only computing the trees that are \"new\" to that\n+ commit.\n+\n+ The recursive tree structure uses nodes that store a number of cache\n+ entries, a list of subnodes, and an object ID (OID). The OID references\n+ the exising tree for that node, if it is known to exist. The subnodes\n+ correspond to subdirectories that themselves have cached tree nodes. The\n+ number of cache entries corresponds to the number of cache entries in\n+ the index that describe paths within that tree's directory.\n+\n+ Note that the path for a given tree is part of the parent node in-memory\n+ but is part of the child in the file format. The root tree has an empty\n+ string for its name and its name does not exist in-memory.\n+\n+ When a path is updated in index, Git invalidates all nodes of the\n+ recurisive cached tree corresponding to the parent directories of that\n+ path. We store these tree nodes as being \"invalid\" by using \"-1\" as the\n+ number of cache entries. To create trees corresponding to the current\n+ index, Git only walks the invalid tree nodes and uses the cached OIDs\n+ for the valid trees to construct new trees. In this way, Git only\n+ constructs trees on the order of the number of changed paths (and their\n+ depth in the working directory). This comes at a cost of tracking the\n+ full directory structure in the cached tree extension, but this is\n+ generally smaller than the full cache entry list in the index.\n \n The signature for this extension is { 'T', 'R', 'E', 'E' }.\n \n-- \ngitgitgadget\n\n"},{"id":"413187","messageId":"20ea7050324cdd78b0966f54366b26224dfc7814.1609356414.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:53Z","receivedAt":"2020-12-30T19:28:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe verify_cache() method is used both for debugging issues with the\ncached tree extension but also to avoid using the extension when there\nare unmerged entries. It also checks for cache entries out of order with\nrespect to file-versus-directory sorting.\n\nIn 996277c (Refactor cache_tree_update idiom from commit, 2011-12-06),\nthe silent option was added to remove the progress indicators from the\ninitial loop looking for unmerged entries. This was changed to be a flag\nin e859c69 (cache-tree: update API to take abitrary flags, 2012-01-16).\n\nIn both cases, the silent option is ignored for the second loop that\nchecks for file-versus-directory sorting. It must be that this loop is\nintended only for debugging purposes and is not actually helpful in\npractice.\n\nSince verify_cache() is called in cache_tree_update(), which is run\nduring 'git commit', we could speed up 'git commit' operations by not\niterating through this loop another time. Of course, noticing this loop\nrequires an incredibly large index.\n\nTo get a measurable difference, I needed to run this test on the\nMicrosoft Office monorepo, which has over three million entries in its\nindex. I used 'git commit --amend --no-edit' as my command and saw the\nperformance go from 752ms to 739ms with this change.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex f135bb77af5..c6c084463bd 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -175,10 +175,15 @@ static int verify_cache(struct cache_entry **cache,\n \tif (funny)\n \t\treturn -1;\n \n-\t/* Also verify that the cache does not have path and path/file\n+\t/*\n+\t * Also verify that the cache does not have path and path/file\n \t * at the same time. At this point we know the cache has only\n-\t * stage 0 entries.\n+\t * stage 0 entries. In silent mode, we do not want these messages,\n+\t * and they should not exist unless a bug was introduced along\n+\t * the way.\n \t */\n+\tif (silent)\n+\t\treturn 0;\n \tfunny = 0;\n \tfor (i = 0; i < entries - 1; i++) {\n \t\t/* path/file always comes after path because of the way\n-- \ngitgitgadget\n"},{"id":"413188","messageId":"5d1c9c8a356b9003be21059c7ed6232732fd26c0.1609356414.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 5/8] cache-tree: trace regions for prime_cache_tree","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:50Z","receivedAt":"2020-12-30T19:28:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nCommands such as \"git reset --hard\" rebuild the in-memory representation\nof the cached tree index extension by parsing tree objects starting at a\nknown root tree. The performance of this operation can vary widely\ndepending on the width and depth of the repository's working directory\nstructure. Measure the time in this operation using trace2 regions in\nprime_cache_tree().\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 45fb57b17f3..f135bb77af5 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -746,7 +746,10 @@ void prime_cache_tree(struct repository *r,\n {\n \tcache_tree_free(&istate->cache_tree);\n \tistate->cache_tree = cache_tree();\n+\n+\ttrace2_region_enter(\"cache-tree\", \"prime_cache_tree\", the_repository);\n \tprime_cache_tree_rec(r, istate->cache_tree, tree);\n+\ttrace2_region_leave(\"cache-tree\", \"prime_cache_tree\", the_repository);\n \tistate->cache_changed |= CACHE_TREE_CHANGED;\n }\n \n-- \ngitgitgadget\n\n"},{"id":"413189","messageId":"65fb9f722519c50419d29930aa92d8ae660bdf2b.1609356414.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH 7/8] index-format: discuss recursion of cached-tree better","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-12-30T19:26:52Z","receivedAt":"2020-12-30T19:28:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe end of the cached tree index extension format trails off with\nellipses ever since 23fcc98 (doc: technical details about the index\nfile format, 2011-03-01). While an intuitive reader could gather what\nthis means, it could be better to use \"and so on\" instead.\n\nReally, this is only justified because I also wanted to point out that\nthe number of subtrees in the index format is used to determine when the\nrecursive depth-first-search stack should be \"popped.\" This should help\nto add clarity to the format.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/index-format.txt | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex c614e136e24..2ebe88b9d46 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -198,7 +198,8 @@ Git index format\n first entry represents the root level of the repository, followed by the\n first subtree--let's call this A--of the root level (with its name\n relative to the root level), followed by the first subtree of A (with\n- its name relative to A), ...\n+ its name relative to A), and so on. The specified number of subtrees\n+ indicates when the current level of the recursive stack is complete.\n \n === Resolve undo\n \n-- \ngitgitgadget\n\n"},{"id":"413190","messageId":"CABPp-BHQY0v2GwmV6dokkTPGuJKmFYKJ7NCe2kes0pQbZgBGQQ@mail.gmail.com","threadId":"54906","inReplyTo":"f727880add6e0380248279e1ad79f80762868a6c.1609356413.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/8] tree-walk: report recursion counts","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-30T19:42:24Z","receivedAt":"2020-12-30T19:43:32Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> The traverse_trees() method recusively walks through trees, but also\n\nrecursively -- you're missing the second 'r'.\n\n> prunes the tree-walk based on a callback. Some callers, such as\n> unpack_trees(), are quite complicated and can have wildly different\n> performance between two different commands.\n\nNot sure it belongs in the commit message, but you do have me curious\nwhat you're digging in to...\n\n> Create constants that count these values and then report the results at\n> the end of a process. These counts are cumulative across multiple \"root\"\n> instances of traverse_trees(), but they provide reproducible values for\n> demonstrating improvements to the pruning algorithm when possible.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> tree-walk.c | 33 +++++++++++++++++++++++++++++++++\n> unpack-trees.c | 1 -\n> 2 files changed, 33 insertions(+), 1 deletion(-)\n\nFrom the subject, you are changing tree-walk. unpack-trees depends on\ntree-walk, but why is something exposed to it with this kind of\nchange? Maybe I'll see when I get to it.\n\n>\n> diff --git a/tree-walk.c b/tree-walk.c\n> index 0160294712b..2d6226d5f18 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -4,6 +4,7 @@\n> #include \"object-store.h\"\n> #include \"tree.h\"\n> #include \"pathspec.h\"\n> +#include \"json-writer.h\"\n>\n> static const char *get_mode(const char *str, unsigned int *modep)\n> {\n> @@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)\n> return 1;\n> }\n>\n> +static int traverse_trees_atexit_registered;\n> +static int traverse_trees_count;\n> +static int traverse_trees_cur_depth;\n> +static int traverse_trees_max_depth;\n> +\n> +static void trace2_traverse_trees_statistics_atexit(void)\n> +{\n> + struct json_writer jw = JSON_WRITER_INIT;\n> +\n> + jw_object_begin(&jw, 0);\n> + jw_object_intmax(&jw, \"traverse_trees_count\", traverse_trees_count);\n> + jw_object_intmax(&jw, \"traverse_trees_max_depth\", traverse_trees_max_depth);\n> + jw_end(&jw);\n> +\n> + trace2_data_json(\"traverse_trees\", the_repository, \"statistics\", &jw);\n> +\n> + jw_release(&jw);\n> +}\n\nYeah, I don't know the json_writer or trace2 stuff; might be nice to\ncc Josh Steadmon or someone to review this patch. (Or perhaps he\nalready reviewed internally?)\n\n> +\n> void setup_traverse_info(struct traverse_info *info, const char *base)\n> {\n> size_t pathlen = strlen(base);\n> @@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n> info->namelen = pathlen;\n> if (pathlen)\n> info->prev = &dummy;\n> +\n> + if (trace2_is_enabled() && !traverse_trees_atexit_registered) {\n> + atexit(trace2_traverse_trees_statistics_atexit);\n> + traverse_trees_atexit_registered = 1;\n> + }\n> }\n>\n> char *make_traverse_path(char *path, size_t pathlen,\n> @@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,\n> int interesting = 1;\n> char *traverse_path;\n>\n> + traverse_trees_count++;\n> + traverse_trees_cur_depth++;\n> +\n> + if (traverse_trees_cur_depth > traverse_trees_max_depth)\n> + traverse_trees_max_depth = traverse_trees_cur_depth;\n> +\n> if (n >= ARRAY_SIZE(entry))\n> BUG(\"traverse_trees() called with too many trees (%d)\", n);\n>\n> @@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,\n> free(traverse_path);\n> info->traverse_path = NULL;\n> strbuf_release(&base);\n> +\n> + traverse_trees_cur_depth--;\n\nI double-checked to see if there were any other return sites in this\nfunction. There aren't, which is nice and keeps this clean.\n\n> return error;\n> }\n>\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 323280dd48b..02f484604ac 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -1559,7 +1559,6 @@ static void populate_from_existing_patterns(struct unpack_trees_options *o,\n> free(sparse);\n> }\n>\n> -\n\nDid you mean to combine this cleanup with some other patch? If not,\ncould it be put into its own patch?\n\n> static int verify_absent(const struct cache_entry *,\n> enum unpack_trees_error_types,\n> struct unpack_trees_options *);\n> --\n> gitgitgadget\n\nSeems like a good change other than a few small nits. I don't know\nthe json_writer/trace2 stuff, so you might want another reviewer, but\nit's only a few lines and seems relatively straightforward.\n"},{"id":"413191","messageId":"CABPp-BGrTcr2q10ppuEML3N1imV_PMm8zzB5SGTQPFWtyUUzEA@mail.gmail.com","threadId":"54906","inReplyTo":"6923e6211aaa9e1e144db747c971c6fe35fb4d41.1609356413.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/8] unpack-trees: add trace2 regions","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-30T19:45:38Z","receivedAt":"2020-12-30T19:46:31Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> The unpack_trees() method is quite complicated and its performance can\n> change dramatically depending on how it is used. We already have some\n> performance tracing regions, but they have not been updated to the\n> trace2 API. Do so now.\n\nSomewhat of a curious side comment: Any idea at what scale the perf\nissues show up? Or are you still digging into that?\n\n> We already have trace2 regions in unpack_trees.c:clear_ce_flags(), which\n> uses a linear scan through the index without recursing into trees.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> unpack-trees.c | 5 +++++\n> 1 file changed, 5 insertions(+)\n>\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 02f484604ac..7dbd006ac56 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -1579,6 +1579,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n> die(\"unpack_trees takes at most %d trees\", MAX_UNPACK_TREES);\n>\n> trace_performance_enter();\n> + trace2_region_enter(\"unpack_trees\", \"unpack_trees\", the_repository);\n> +\n> if (!core_apply_sparse_checkout || !o->update)\n> o->skip_sparse_checkout = 1;\n> if (!o->skip_sparse_checkout && !o->pl) {\n> @@ -1652,7 +1654,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n> }\n>\n> trace_performance_enter();\n> + trace2_region_enter(\"unpack_trees\", \"traverse_trees\", the_repository);\n> ret = traverse_trees(o->src_index, len, t, &info);\n> + trace2_region_leave(\"unpack_trees\", \"traverse_trees\", the_repository);\n> trace_performance_leave(\"traverse_trees\");\n> if (ret < 0)\n> goto return_failed;\n> @@ -1740,6 +1744,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n> done:\n> if (free_pattern_list)\n> clear_pattern_list(&pl);\n> + trace2_region_leave(\"unpack_trees\", \"unpack_trees\", the_repository);\n> trace_performance_leave(\"unpack_trees\");\n> return ret;\n>\n> --\n> gitgitgadget\n\nSeems simple and straightforward, and I like having more trace2\nmeasurements since I used it so much in merge-ort.\n"},{"id":"413192","messageId":"CABPp-BGTXvNjwQkqSzqLJwL6T2a_Ly_9=wiejqpt-3sq6oPGEw@mail.gmail.com","threadId":"54906","inReplyTo":"5d1c9c8a356b9003be21059c7ed6232732fd26c0.1609356414.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 5/8] cache-tree: trace regions for prime_cache_tree","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-30T19:48:37Z","receivedAt":"2020-12-30T19:49:30Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> Commands such as \"git reset --hard\" rebuild the in-memory representation\n> of the cached tree index extension by parsing tree objects starting at a\n> known root tree. The performance of this operation can vary widely\n> depending on the width and depth of the repository's working directory\n> structure. Measure the time in this operation using trace2 regions in\n> prime_cache_tree().\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> cache-tree.c | 3 +++\n> 1 file changed, 3 insertions(+)\n>\n> diff --git a/cache-tree.c b/cache-tree.c\n> index 45fb57b17f3..f135bb77af5 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -746,7 +746,10 @@ void prime_cache_tree(struct repository *r,\n> {\n> cache_tree_free(&istate->cache_tree);\n> istate->cache_tree = cache_tree();\n> +\n> + trace2_region_enter(\"cache-tree\", \"prime_cache_tree\", the_repository);\n\nShouldn't this be at the start of the function, a few lines up?\n\n> prime_cache_tree_rec(r, istate->cache_tree, tree);\n> + trace2_region_leave(\"cache-tree\", \"prime_cache_tree\", the_repository);\n\n...and this be one more line down? (or the string \"prime_cache_tree\"\nhave a \"_rec\" added to it?)\n\n> istate->cache_changed |= CACHE_TREE_CHANGED;\n> }\n>\n> --\n> gitgitgadget\n>\n"},{"id":"413193","messageId":"b81e853a-64ef-dbe5-77d3-f3a2cf87c9bc@gmail.com","threadId":"54906","inReplyTo":"CABPp-BHQY0v2GwmV6dokkTPGuJKmFYKJ7NCe2kes0pQbZgBGQQ@mail.gmail.com","subject":"Re: [PATCH 1/8] tree-walk: report recursion counts","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-30T19:51:36Z","receivedAt":"2020-12-30T19:52:19Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/30/2020 2:42 PM, Elijah Newren wrote:\n> On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> From: Derrick Stolee \n>>\n>> The traverse_trees() method recusively walks through trees, but also\n> \n> recursively -- you're missing the second 'r'.\n\nThanks.\n\n>> prunes the tree-walk based on a callback. Some callers, such as\n>> unpack_trees(), are quite complicated and can have wildly different\n>> performance between two different commands.\n> \n> Not sure it belongs in the commit message, but you do have me curious\n> what you're digging in to...\n\nI'm still testing whether my idea will work out. Hopefully soon. ;)\n \n>> Create constants that count these values and then report the results at\n>> the end of a process. These counts are cumulative across multiple \"root\"\n>> instances of traverse_trees(), but they provide reproducible values for\n>> demonstrating improvements to the pruning algorithm when possible.\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> tree-walk.c | 33 +++++++++++++++++++++++++++++++++\n>> unpack-trees.c | 1 -\n>> 2 files changed, 33 insertions(+), 1 deletion(-)\n> \n> From the subject, you are changing tree-walk. unpack-trees depends on\n> tree-walk, but why is something exposed to it with this kind of\n> change? Maybe I'll see when I get to it.\n\nOops. I originally reported the stats at the end of unpack_trees(), but\nit seems I didn't completely back out that change.\n\n>> diff --git a/tree-walk.c b/tree-walk.c\n>> index 0160294712b..2d6226d5f18 100644\n>> --- a/tree-walk.c\n>> +++ b/tree-walk.c\n>> @@ -4,6 +4,7 @@\n>> #include \"object-store.h\"\n>> #include \"tree.h\"\n>> #include \"pathspec.h\"\n>> +#include \"json-writer.h\"\n>>\n>> static const char *get_mode(const char *str, unsigned int *modep)\n>> {\n>> @@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)\n>> return 1;\n>> }\n>>\n>> +static int traverse_trees_atexit_registered;\n>> +static int traverse_trees_count;\n>> +static int traverse_trees_cur_depth;\n>> +static int traverse_trees_max_depth;\n>> +\n>> +static void trace2_traverse_trees_statistics_atexit(void)\n>> +{\n>> + struct json_writer jw = JSON_WRITER_INIT;\n>> +\n>> + jw_object_begin(&jw, 0);\n>> + jw_object_intmax(&jw, \"traverse_trees_count\", traverse_trees_count);\n>> + jw_object_intmax(&jw, \"traverse_trees_max_depth\", traverse_trees_max_depth);\n>> + jw_end(&jw);\n>> +\n>> + trace2_data_json(\"traverse_trees\", the_repository, \"statistics\", &jw);\n>> +\n>> + jw_release(&jw);\n>> +}\n> \n> Yeah, I don't know the json_writer or trace2 stuff; might be nice to\n> cc Josh Steadmon or someone to review this patch. (Or perhaps he\n> already reviewed internally?)\n\nI guess I could have pointed out that this change is modeled after\na similar statistics reporting in 42e50e78 (revision.c: add trace2\nstats around Bloom filter usage, 2020-04-06).\n\n>> +\n>> void setup_traverse_info(struct traverse_info *info, const char *base)\n>> {\n>> size_t pathlen = strlen(base);\n>> @@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n>> info->namelen = pathlen;\n>> if (pathlen)\n>> info->prev = &dummy;\n>> +\n>> + if (trace2_is_enabled() && !traverse_trees_atexit_registered) {\n>> + atexit(trace2_traverse_trees_statistics_atexit);\n>> + traverse_trees_atexit_registered = 1;\n>> + }\n>> }\n>>\n>> char *make_traverse_path(char *path, size_t pathlen,\n>> @@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,\n>> int interesting = 1;\n>> char *traverse_path;\n>>\n>> + traverse_trees_count++;\n>> + traverse_trees_cur_depth++;\n>> +\n>> + if (traverse_trees_cur_depth > traverse_trees_max_depth)\n>> + traverse_trees_max_depth = traverse_trees_cur_depth;\n>> +\n>> if (n >= ARRAY_SIZE(entry))\n>> BUG(\"traverse_trees() called with too many trees (%d)\", n);\n>>\n>> @@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,\n>> free(traverse_path);\n>> info->traverse_path = NULL;\n>> strbuf_release(&base);\n>> +\n>> + traverse_trees_cur_depth--;\n> \n> I double-checked to see if there were any other return sites in this\n> function. There aren't, which is nice and keeps this clean.\n> \n>> return error;\n>> }\n>>\n>> diff --git a/unpack-trees.c b/unpack-trees.c\n>> index 323280dd48b..02f484604ac 100644\n>> --- a/unpack-trees.c\n>> +++ b/unpack-trees.c\n>> @@ -1559,7 +1559,6 @@ static void populate_from_existing_patterns(struct unpack_trees_options *o,\n>> free(sparse);\n>> }\n>>\n>> -\n> \n> Did you mean to combine this cleanup with some other patch? If not,\n> could it be put into its own patch?\n\nIt should be dropped! Thanks.\n\n>> static int verify_absent(const struct cache_entry *,\n>> enum unpack_trees_error_types,\n>> struct unpack_trees_options *);\n>> --\n>> gitgitgadget\n> \n> Seems like a good change other than a few small nits. I don't know\n> the json_writer/trace2 stuff, so you might want another reviewer, but\n> it's only a few lines and seems relatively straightforward.\n\nI should point out that an easy way to test this locally is\nto run\n\n GIT_TRACE2_PERF=1 git read-tree -mu HEAD\n\nto trigger a full recursive walk. The output JSON payload looks\nlike this:\n\n statistics:{\"traverse_trees_count\":203,\"traverse_trees_max_depth\":7}\n\nThanks,\n-Stolee\n"},{"id":"413194","messageId":"97488332-a24e-889c-0114-ff54b12e573b@gmail.com","threadId":"54906","inReplyTo":"CABPp-BGTXvNjwQkqSzqLJwL6T2a_Ly_9=wiejqpt-3sq6oPGEw@mail.gmail.com","subject":"Re: [PATCH 5/8] cache-tree: trace regions for prime_cache_tree","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-30T19:53:45Z","receivedAt":"2020-12-30T19:54:43Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/30/2020 2:48 PM, Elijah Newren wrote:\n> On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> From: Derrick Stolee \n>>\n>> Commands such as \"git reset --hard\" rebuild the in-memory representation\n>> of the cached tree index extension by parsing tree objects starting at a\n>> known root tree. The performance of this operation can vary widely\n>> depending on the width and depth of the repository's working directory\n>> structure. Measure the time in this operation using trace2 regions in\n>> prime_cache_tree().\n>>\n>> Signed-off-by: Derrick Stolee \n>> ---\n>> cache-tree.c | 3 +++\n>> 1 file changed, 3 insertions(+)\n>>\n>> diff --git a/cache-tree.c b/cache-tree.c\n>> index 45fb57b17f3..f135bb77af5 100644\n>> --- a/cache-tree.c\n>> +++ b/cache-tree.c\n>> @@ -746,7 +746,10 @@ void prime_cache_tree(struct repository *r,\n>> {\n>> cache_tree_free(&istate->cache_tree);\n>> istate->cache_tree = cache_tree();\n>> +\n>> + trace2_region_enter(\"cache-tree\", \"prime_cache_tree\", the_repository);\n> \n> Shouldn't this be at the start of the function, a few lines up?\n> \n>> prime_cache_tree_rec(r, istate->cache_tree, tree);\n>> + trace2_region_leave(\"cache-tree\", \"prime_cache_tree\", the_repository);\n> \n> ...and this be one more line down? (or the string \"prime_cache_tree\"\n> have a \"_rec\" added to it?)\n\nI guess my focus was on creating changes around the \"bulk\"\nof the operation, keeping the region enter/leave pair close\ntogether. But perhaps enclosing the full block will be\nbetter for full coverage in case this method became more\ncomplicated (but not within prime_cache_tree_rec()).\n\nThanks,\n-Stolee\n"},{"id":"413195","messageId":"CABPp-BFdn-CBWMPeAKoPvuSqwkeHnAPMZovAEaiNquz_JKaPkA@mail.gmail.com","threadId":"54906","inReplyTo":"fb9d5468184c4cbb3d80569f685743b9a5b45c8e.1609356414.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 6/8] index-format: update preamble to cached tree extension","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-30T20:00:41Z","receivedAt":"2020-12-30T20:02:05Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> I had difficulty in my efforts to learn about the cached tree extension\n> based on the documentation and code because I had an incorrect\n> assumption about how it behaved. This might be due to some ambiguity in\n> the documentation, so this change modifies the beginning of the cached\n> tree format by expanding the description of the feature.\n>\n> My hope is that this documentation clarifies a few things:\n>\n> 1. There is an in-memory recursive tree structure that is constructed\n> from the extension data. This structure has a few differences, such\n> as where the name is stored.\n>\n> 2. What does it mean for an entry to be invalid?\n>\n> 3. When exactly are \"new\" trees created?\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----\n> 1 file changed, 30 insertions(+), 6 deletions(-)\n>\n> diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\n> index 69edf46c031..c614e136e24 100644\n> --- a/Documentation/technical/index-format.txt\n> +++ b/Documentation/technical/index-format.txt\n> @@ -138,12 +138,36 @@ Git index format\n>\n> === Cached tree\n>\n> - Cached tree extension contains pre-computed hashes for trees that can\n> - be derived from the index. It helps speed up tree object generation\n> - from index for a new commit.\n> -\n> - When a path is updated in index, the path must be invalidated and\n> - removed from tree cache.\n> + Since the index does not record entries for directories, the cache\n> + entries cannot describe tree objects that already exist in the object\n> + database for regions of the index that are unchanged from an existing\n> + commit. The cached tree extension stores a recursive tree structure that\n> + describes the trees that already exist and completely match sections of\n> + the cache entries. This speeds up tree object generation from the index\n> + for a new commit by only computing the trees that are \"new\" to that\n> + commit.\n> +\n> + The recursive tree structure uses nodes that store a number of cache\n> + entries, a list of subnodes, and an object ID (OID). The OID references\n> + the exising tree for that node, if it is known to exist. The subnodes\n> + correspond to subdirectories that themselves have cached tree nodes. The\n> + number of cache entries corresponds to the number of cache entries in\n> + the index that describe paths within that tree's directory.\n> +\n> + Note that the path for a given tree is part of the parent node in-memory\n> + but is part of the child in the file format. The root tree has an empty\n> + string for its name and its name does not exist in-memory.\n> +\n> + When a path is updated in index, Git invalidates all nodes of the\n> + recurisive cached tree corresponding to the parent directories of that\n> + path. We store these tree nodes as being \"invalid\" by using \"-1\" as the\n> + number of cache entries. To create trees corresponding to the current\n> + index, Git only walks the invalid tree nodes and uses the cached OIDs\n> + for the valid trees to construct new trees. In this way, Git only\n> + constructs trees on the order of the number of changed paths (and their\n> + depth in the working directory). This comes at a cost of tracking the\n> + full directory structure in the cached tree extension, but this is\n> + generally smaller than the full cache entry list in the index.\n\nOoh, I really like it; this probably would have helped me. However,\nwe'll need to get someone else to take a look at this, because I don't\nknow enough to say whether any part of it is incorrect, misleading, or\nincomplete or whether it's all good. My knowledge in the area is\nlimited to moving a function from merge-recursive.c to cache-tree.c in\ncommit 724dd767b2 (\"cache-tree: share code between functions writing\nan index as a tree\", 2019-08-17), but I seem to recall that I had to\nrely on Junio's reviews and guidance to make the minor adaptations\nfound in that commit.\n"},{"id":"413196","messageId":"CABPp-BFp5=C+6B1WUarXzabo0fU4xotP5UG91-hYahCHDA6Cng@mail.gmail.com","threadId":"54906","inReplyTo":"20ea7050324cdd78b0966f54366b26224dfc7814.1609356414.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-30T20:14:25Z","receivedAt":"2020-12-30T20:15:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 30, 2020 at 11:27 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> From: Derrick Stolee \n>\n> The verify_cache() method is used both for debugging issues with the\n> cached tree extension but also to avoid using the extension when there\n> are unmerged entries. It also checks for cache entries out of order with\n> respect to file-versus-directory sorting.\n>\n> In 996277c (Refactor cache_tree_update idiom from commit, 2011-12-06),\n> the silent option was added to remove the progress indicators from the\n> initial loop looking for unmerged entries. This was changed to be a flag\n> in e859c69 (cache-tree: update API to take abitrary flags, 2012-01-16).\n>\n> In both cases, the silent option is ignored for the second loop that\n> checks for file-versus-directory sorting. It must be that this loop is\n> intended only for debugging purposes and is not actually helpful in\n> practice.\n\nLooking through that code, I come to the same conclusion, though it\nmight be nice to have Junio confirm (and to explain the \"if (10 <\n++funny)\" section; did that help debugging too?). The second part of\nthe loop was part of his initial commit adding the cache-tree\nextension in commit 749864627c (\"Add cache-tree.\", 2006-04-23)\n\n> Since verify_cache() is called in cache_tree_update(), which is run\n> during 'git commit', we could speed up 'git commit' operations by not\n> iterating through this loop another time. Of course, noticing this loop\n> requires an incredibly large index.\n>\n> To get a measurable difference, I needed to run this test on the\n> Microsoft Office monorepo, which has over three million entries in its\n> index. I used 'git commit --amend --no-edit' as my command and saw the\n> performance go from 752ms to 739ms with this change.\n\nNice catch; I always appreciate when we can speed up a section of code\nby just not running it. :-)\n\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> cache-tree.c | 9 +++++++--\n> 1 file changed, 7 insertions(+), 2 deletions(-)\n>\n> diff --git a/cache-tree.c b/cache-tree.c\n> index f135bb77af5..c6c084463bd 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -175,10 +175,15 @@ static int verify_cache(struct cache_entry **cache,\n> if (funny)\n> return -1;\n>\n> - /* Also verify that the cache does not have path and path/file\n> + /*\n> + * Also verify that the cache does not have path and path/file\n> * at the same time. At this point we know the cache has only\n> - * stage 0 entries.\n> + * stage 0 entries. In silent mode, we do not want these messages,\n> + * and they should not exist unless a bug was introduced along\n> + * the way.\n> */\n> + if (silent)\n> + return 0;\n> funny = 0;\n> for (i = 0; i < entries - 1; i++) {\n> /* path/file always comes after path because of the way\n> --\n> gitgitgadget\n\nChange seems simple enough. Thanks for adding the comment explaining\nthe early return.\n"},{"id":"413197","messageId":"CABPp-BG6iiQ=_SvGEFCGnYe+z57op+b6vWfJmw=w_0eikzpvCA@mail.gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/8] Cleanups around index operations","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2020-12-30T20:19:43Z","receivedAt":"2020-12-30T20:20:52Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n wrote:\n>\n> I've taken a professional interest in the index lately, and I've been trying\n> mostly to learn about it and measure different operations. Along the way,\n> I've seen some possible improvements in documentation, behavior, and\n> tracing.\n>\n> This series collects most of my thoughts so far, including:\n>\n> 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches\n> 1-5).\n> 2. Update documentation about the cached tree extension (Patches 6-7).\n> 3. Removing an unnecessary loop from verify_cache() (Patch 8).\n\nThe series seems pretty simple and clean to me. As I mentioned on\npatch 6, though, I don't know much about the cache-tree extension\nmyself (I show up in blame/log due to moving a function there with\njust some slight tweaks), so it'd be nice if someone who does can take\na look at the documentation added in patch 6.\n"},{"id":"413198","messageId":"11b79eab-6a4d-ee80-3761-e5ff3dac08cd@gmail.com","threadId":"54906","inReplyTo":"CABPp-BG6iiQ=_SvGEFCGnYe+z57op+b6vWfJmw=w_0eikzpvCA@mail.gmail.com","subject":"Re: [PATCH 0/8] Cleanups around index operations","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-30T20:24:17Z","receivedAt":"2020-12-30T20:25:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/30/2020 3:19 PM, Elijah Newren wrote:\n> On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget\n> wrote:\n>>\n>> I've taken a professional interest in the index lately, and I've been trying\n>> mostly to learn about it and measure different operations. Along the way,\n>> I've seen some possible improvements in documentation, behavior, and\n>> tracing.\n>>\n>> This series collects most of my thoughts so far, including:\n>>\n>> 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches\n>> 1-5).\n>> 2. Update documentation about the cached tree extension (Patches 6-7).\n>> 3. Removing an unnecessary loop from verify_cache() (Patch 8).\n> \n> The series seems pretty simple and clean to me. As I mentioned on\n> patch 6, though, I don't know much about the cache-tree extension\n> myself (I show up in blame/log due to moving a function there with\n> just some slight tweaks), so it'd be nice if someone who does can take\n> a look at the documentation added in patch 6.\n\nThanks for the quick review. And I've CC'd Junio since I forgot that\nGitGitGadget no longer auto-CCs him.\n\nThanks,\n-Stolee\n\n"},{"id":"413219","messageId":"daeb59ee-861d-9c8d-3601-6aef1ac3fc94@web.de","threadId":"54906","inReplyTo":"20ea7050324cdd78b0966f54366b26224dfc7814.1609356414.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-12-31T12:34:22Z","receivedAt":"2020-12-31T12:38:38Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 30.12.20 um 20:26 schrieb Derrick Stolee via GitGitGadget:\n> From: Derrick Stolee \n>\n> The verify_cache() method is used both for debugging issues with the\n> cached tree extension but also to avoid using the extension when there\n> are unmerged entries. It also checks for cache entries out of order with\n> respect to file-versus-directory sorting.\n>\n> In 996277c (Refactor cache_tree_update idiom from commit, 2011-12-06),\n> the silent option was added to remove the progress indicators from the\n> initial loop looking for unmerged entries. This was changed to be a flag\n> in e859c69 (cache-tree: update API to take abitrary flags, 2012-01-16).\n>\n> In both cases, the silent option is ignored for the second loop that\n> checks for file-versus-directory sorting. It must be that this loop is\n> intended only for debugging purposes and is not actually helpful in\n> practice.\n\nSo you're saying that the directory/file conflict check not honoring the\nWRITE_TREE_SILENT flag would have been noticed as a bug and therefore\ndoesn't happen?\n\nI'm not sure I can follow that logic. I don't know how important that\ncheck is, how often it found a conflict and how likely such a find is\noverlooked or ignored, but disabling a check in silent mode that\naffects the return code instead of only suppressing its messages seems\nrisky.\n\nIf we are sure that the check cannot trigger then we should remove it.\nIf we are not so sure, but a conflict would be Git's fault (and not the\nuser's) then we should always do the check and BUG out. And otherwise\nwe should keep it.\n\n> Since verify_cache() is called in cache_tree_update(), which is run\n> during 'git commit', we could speed up 'git commit' operations by not\n> iterating through this loop another time. Of course, noticing this loop\n> requires an incredibly large index.\n>\n> To get a measurable difference, I needed to run this test on the\n> Microsoft Office monorepo, which has over three million entries in its\n> index. I used 'git commit --amend --no-edit' as my command and saw the\n> performance go from 752ms to 739ms with this change.\n\nCould you please check the performance impact of the following code\nsimplification?\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex a537a806c1..1105cfe6b7 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -187,10 +187,8 @@ static int verify_cache(struct cache_entry **cache,\n \t\t */\n \t\tconst char *this_name = cache[i]->name;\n \t\tconst char *next_name = cache[i+1]->name;\n-\t\tint this_len = strlen(this_name);\n-\t\tif (this_len < strlen(next_name) &&\n-\t\t strncmp(this_name, next_name, this_len) == 0 &&\n-\t\t next_name[this_len] == '/') {\n+\t\tconst char *p;\n+\t\tif (skip_prefix(next_name, this_name, &p) && *p == '/') {\n \t\t\tif (10 < ++funny) {\n \t\t\t\tfprintf(stderr, \"...\\n\");\n \t\t\t\tbreak;\n"},{"id":"413223","messageId":"3ed37ae6-1f09-bd6b-c9d9-c8089da1af92@gmail.com","threadId":"54906","inReplyTo":"daeb59ee-861d-9c8d-3601-6aef1ac3fc94@web.de","subject":"Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-31T16:46:19Z","receivedAt":"2020-12-31T16:47:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/31/2020 7:34 AM, René Scharfe wrote:\n> Am 30.12.20 um 20:26 schrieb Derrick Stolee via GitGitGadget:\n>> From: Derrick Stolee \n>>\n>> The verify_cache() method is used both for debugging issues with the\n>> cached tree extension but also to avoid using the extension when there\n>> are unmerged entries. It also checks for cache entries out of order with\n>> respect to file-versus-directory sorting.\n>>\n>> In 996277c (Refactor cache_tree_update idiom from commit, 2011-12-06),\n>> the silent option was added to remove the progress indicators from the\n>> initial loop looking for unmerged entries. This was changed to be a flag\n>> in e859c69 (cache-tree: update API to take abitrary flags, 2012-01-16).\n>>\n>> In both cases, the silent option is ignored for the second loop that\n>> checks for file-versus-directory sorting. It must be that this loop is\n>> intended only for debugging purposes and is not actually helpful in\n>> practice.\n> \n> So you're saying that the directory/file conflict check not honoring the\n> WRITE_TREE_SILENT flag would have been noticed as a bug and therefore\n> doesn't happen?\n> \n> I'm not sure I can follow that logic. I don't know how important that\n> check is, how often it found a conflict and how likely such a find is\n> overlooked or ignored, but disabling a check in silent mode that\n> affects the return code instead of only suppressing its messages seems\n> risky.\n> \n> If we are sure that the check cannot trigger then we should remove it.\n> If we are not so sure, but a conflict would be Git's fault (and not the\n> user's) then we should always do the check and BUG out. And otherwise\n> we should keep it.\n\nI think this method was originally designed for debugging issues with\nthe index, and it still serves that purpose when someone is working on\nit. The check for out-of-order directory/file conflicts probably exists\nonly for that case.\n\nHowever, this method also got repurposed to (silently) check for the\nreal scenario of unmerged entries. Perhaps it would be better to split\nthese into two cases and move the silent case into a new method,\n\"has_unmerged_entries()\".\n\n>> Since verify_cache() is called in cache_tree_update(), which is run\n>> during 'git commit', we could speed up 'git commit' operations by not\n>> iterating through this loop another time. Of course, noticing this loop\n>> requires an incredibly large index.\n>>\n>> To get a measurable difference, I needed to run this test on the\n>> Microsoft Office monorepo, which has over three million entries in its\n>> index. I used 'git commit --amend --no-edit' as my command and saw the\n>> performance go from 752ms to 739ms with this change.>> Could you please check the performance impact of the following code\n> simplification?\n\nThank you for sending this. I started comparing the performance and\ndiscovered that the performance difference I had measured before was\nNOT consistent! I went back and debugged and found that 'git commit'\ndoesn't actually pass the silent flag, and my performance tests were\nskewed by the filesystem cache. (A warmup of 3 runs was not sufficient\nto get consistent numbers, it seemed. Perhaps the threaded index reads\nare too inconsistent.)\n\n> diff --git a/cache-tree.c b/cache-tree.c\n> index a537a806c1..1105cfe6b7 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -187,10 +187,8 @@ static int verify_cache(struct cache_entry **cache,\n> \t\t */\n> \t\tconst char *this_name = cache[i]->name;\n> \t\tconst char *next_name = cache[i+1]->name;\n> -\t\tint this_len = strlen(this_name);\n> -\t\tif (this_len < strlen(next_name) &&\n> -\t\t strncmp(this_name, next_name, this_len) == 0 &&\n> -\t\t next_name[this_len] == '/') {\n> +\t\tconst char *p;\n> +\t\tif (skip_prefix(next_name, this_name, &p) && *p == '/') {\n> \t\t\tif (10 < ++funny) {\n> \t\t\t\tfprintf(stderr, \"...\\n\");\n> \t\t\t\tbreak;\n \nThis performs consistently worse than both cases (see performance test\nlater in this message). I think the strlen is saving us some time here.\n\nIn fact, I think the compiler is doing some magic to save our strlen\nresults, as I get identical performance results when doing this:\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex c6c084463b..a076e7cec5 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,\n {\n int i, funny;\n int silent = flags & WRITE_TREE_SILENT;\n+ const char *this_name;\n+ size_t this_len;\n \n /* Verify that the tree is merged */\n funny = 0;\n@@ -182,18 +184,21 @@ static int verify_cache(struct cache_entry **cache,\n * and they should not exist unless a bug was introduced along\n * the way.\n */\n- if (silent)\n- return 0;\n funny = 0;\n- for (i = 0; i < entries - 1; i++) {\n+\n+ if (!entries)\n+ return 0;\n+ this_name = cache[0]->name;\n+ this_len = strlen(this_name);\n+\n+ for (i = 1; i < entries; i++) {\n /* path/file always comes after path because of the way\n * the cache is sorted. Also path can appear only once,\n * which means conflicting one would immediately follow.\n */\n- const char *this_name = cache[i]->name;\n- const char *next_name = cache[i+1]->name;\n- int this_len = strlen(this_name);\n- if (this_len < strlen(next_name) &&\n+ const char *next_name = cache[i]->name;\n+ size_t next_len = strlen(next_name);\n+ if (this_len < next_len &&\n strncmp(this_name, next_name, this_len) == 0 &&\n next_name[this_len] == '/') {\n if (10 < ++funny) {\n@@ -203,6 +208,8 @@ static int verify_cache(struct cache_entry **cache,\n fprintf(stderr, \"You have both %s and %s\\n\",\n this_name, next_name);\n }\n+ this_name = next_name;\n+ this_len = next_len;\n }\n if (funny)\n return -1;\n\nTo get more consistent results, I modified my benchmark to be the following:\n\n\tgit -c index.threads=1 commit --amend --allow-empty --no-edit\n\nI also adjusted the test suite to use 5 warmup rounds. Here are the numbers:\n\n Benchmark #1: v2.30.0\n Time (mean ± σ): 856.6 ms ± 18.0 ms [User: 807.9 ms, System: 198.4 ms]\n Range (min … max): 832.1 ms … 882.2 ms 10 runs\n \nSo, 756.5ms average for v2.30.0.\n\n Benchmark #2: skipping the second loop\n Time (mean ± σ): 805.5 ms ± 15.8 ms [User: 758.0 ms, System: 197.1 ms]\n Range (min … max): 783.4 ms … 835.2 ms 10 runs\n \nHere, I just deleted the second loop to see what is the potential minimum.\n\n Benchmark #3: storing this_name during second loop\n Time (mean ± σ): 855.6 ms ± 14.1 ms [User: 804.5 ms, System: 194.6 ms]\n Range (min … max): 835.9 ms … 875.2 ms 10 runs\n\nThe diff I provided earlier reduces the number of strlen() computations\nby storing them across the loop iterations. There is no effect, which\nmakes me think the compiler is being smart.\n\n Benchmark #4: check for '/' before strncmp()\n Time (mean ± σ): 834.1 ms ± 18.0 ms [User: 786.6 ms, System: 196.7 ms]\n Range (min … max): 803.5 ms … 860.4 ms 10 runs \n\nHOWEVER, if we swap the order of the conditionals to be\n\n\t\tif (this_len < next_len &&\n\t\t strncmp(this_name, next_name, this_len) == 0 &&\n\t\t next_name[this_len] == '/') {\n\nthen we _do_ get a measurable, consistent speedup.\n\n Benchmark #5: using skip_prefix\n Time (mean ± σ): 877.3 ms ± 16.1 ms [User: 839.1 ms, System: 187.5 ms]\n Range (min … max): 847.7 ms … 900.4 ms 10 runs\n\nThis final benchmark stores the results for your skip_prefix diff.\n\nIncluding the full ranges of the 10 runs hopefully assists in demonstrating\nthat the performance changes are (mostly) consistent.\n\nTo wrap up, I'm going to eject this patch from my v2 since more investigation\nmust be done to see if this second loop _can_ be dropped. At minimum, it isn't\nproperly silent when requested and there _is_ a performance boost possible,\neven if we keep the check.\n\nThanks,\n-Stolee\n"},{"id":"413303","messageId":"c9427a35-b2e0-0142-e5c2-4d1baf97315a@web.de","threadId":"54906","inReplyTo":"3ed37ae6-1f09-bd6b-c9d9-c8089da1af92@gmail.com","subject":"Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-01-01T13:30:02Z","receivedAt":"2021-01-01T13:32:31Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 31.12.20 um 17:46 schrieb Derrick Stolee:\n> On 12/31/2020 7:34 AM, René Scharfe wrote:\n>> diff --git a/cache-tree.c b/cache-tree.c\n>> index a537a806c1..1105cfe6b7 100644\n>> --- a/cache-tree.c\n>> +++ b/cache-tree.c\n>> @@ -187,10 +187,8 @@ static int verify_cache(struct cache_entry **cache,\n>> \t\t */\n>> \t\tconst char *this_name = cache[i]->name;\n>> \t\tconst char *next_name = cache[i+1]->name;\n>> -\t\tint this_len = strlen(this_name);\n>> -\t\tif (this_len < strlen(next_name) &&\n>> -\t\t strncmp(this_name, next_name, this_len) == 0 &&\n>> -\t\t next_name[this_len] == '/') {\n>> +\t\tconst char *p;\n>> +\t\tif (skip_prefix(next_name, this_name, &p) && *p == '/') {\n>> \t\t\tif (10 < ++funny) {\n>> \t\t\t\tfprintf(stderr, \"...\\n\");\n>> \t\t\t\tbreak;\n>\n> This performs consistently worse than both cases (see performance test\n> later in this message). I think the strlen is saving us some time here.\nThanks for checking! I was expecting skip_prefix to be faster, because\nit stops as soon as it reaches a non-matching character, while strlen\nhas to always walk to the end. But consecutive entries of a sorted list\nof paths can share long prefixes, in particular if there are long\ndirectory names and directories contain lots of files.\n\n> In fact, I think the compiler is doing some magic to save our strlen\n> results, as I get identical performance results when doing this:\n>\n> diff --git a/cache-tree.c b/cache-tree.c\n> index c6c084463b..a076e7cec5 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,\n> {\n> int i, funny;\n> int silent = flags & WRITE_TREE_SILENT;\n> + const char *this_name;\n> + size_t this_len;\n>\n> /* Verify that the tree is merged */\n> funny = 0;\n> @@ -182,18 +184,21 @@ static int verify_cache(struct cache_entry **cache,\n> * and they should not exist unless a bug was introduced along\n> * the way.\n> */\n> - if (silent)\n> - return 0;\n> funny = 0;\n> - for (i = 0; i < entries - 1; i++) {\n> +\n> + if (!entries)\n> + return 0;\n> + this_name = cache[0]->name;\n> + this_len = strlen(this_name);\n> +\n> + for (i = 1; i < entries; i++) {\n> /* path/file always comes after path because of the way\n> * the cache is sorted. Also path can appear only once,\n> * which means conflicting one would immediately follow.\n> */\n> - const char *this_name = cache[i]->name;\n> - const char *next_name = cache[i+1]->name;\n> - int this_len = strlen(this_name);\n> - if (this_len < strlen(next_name) &&\n> + const char *next_name = cache[i]->name;\n> + size_t next_len = strlen(next_name);\n> + if (this_len < next_len &&\n> strncmp(this_name, next_name, this_len) == 0 &&\n> next_name[this_len] == '/') {\n> if (10 < ++funny) {\n> @@ -203,6 +208,8 @@ static int verify_cache(struct cache_entry **cache,\n> fprintf(stderr, \"You have both %s and %s\\n\",\n> this_name, next_name);\n> }\n> + this_name = next_name;\n> + this_len = next_len;\n> }\n> if (funny)\n> return -1;\n>\n\nThe compiler can do that because strlen() is a pure function; glibc\ndeclares it like this:\n\n extern size_t strlen (const char *__s)\n __THROW __attribute_pure__ __nonnull ((1));\n\n> HOWEVER, if we swap the order of the conditionals to be\n>\n> \t\tif (this_len < next_len &&\n> \t\t strncmp(this_name, next_name, this_len) == 0 &&\n> \t\t next_name[this_len] == '/') {\n>\n> then we _do_ get a measurable, consistent speedup.\n\nThat's the original order there, but I get it. The trailing slash has\nonly a low probability of being present, so in the common case the\nstrncmp call can be skipped. And I guess that check is easier to\nhandle for the branch predictor as well.\n\nSince we know the length of both strings we can use memcmp instead of\nstrncmp. It can compare words instead of bytes, so I'd expect it to\nbe faster. Checking the slash first should make that difference moot,\nthough, as it probably eliminates most of the strncmp calls anyway.\n\nRené\n"},{"id":"413311","messageId":"a8b5bb13-5c88-d744-b47e-7204e12ad05d@web.de","threadId":"54906","inReplyTo":"3ed37ae6-1f09-bd6b-c9d9-c8089da1af92@gmail.com","subject":"[PATCH] cache-tree: use ce_namelen() instead of strlen()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-01-02T15:19:11Z","receivedAt":"2021-01-02T15:22:21Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use the name length field of cache entries instead of calculating its\nvalue anew.\n\nSigned-off-by: René Scharfe \n---\nNot sure why it took me so long to spot this.. o_O\n\n cache-tree.c | 10 ++++++----\n 1 file changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex a537a806c1..57cacab195 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,\n \t\t * the cache is sorted. Also path can appear only once,\n \t\t * which means conflicting one would immediately follow.\n \t\t */\n-\t\tconst char *this_name = cache[i]->name;\n-\t\tconst char *next_name = cache[i+1]->name;\n-\t\tint this_len = strlen(this_name);\n-\t\tif (this_len < strlen(next_name) &&\n+\t\tconst struct cache_entry *this_ce = cache[i];\n+\t\tconst struct cache_entry *next_ce = cache[i + 1];\n+\t\tconst char *this_name = this_ce->name;\n+\t\tconst char *next_name = next_ce->name;\n+\t\tint this_len = ce_namelen(this_ce);\n+\t\tif (this_len < ce_namelen(next_ce) &&\n \t\t strncmp(this_name, next_name, this_len) == 0 &&\n \t\t next_name[this_len] == '/') {\n \t\t\tif (10 < ++funny) {\n--\n2.30.0\n"},{"id":"413312","messageId":"30ddf1bd-b315-a399-3016-dcc4f9d7d3b5@web.de","threadId":"54906","inReplyTo":"3ed37ae6-1f09-bd6b-c9d9-c8089da1af92@gmail.com","subject":"Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-01-02T15:31:01Z","receivedAt":"2021-01-02T15:33:13Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 31.12.20 um 17:46 schrieb Derrick Stolee:\n> To wrap up, I'm going to eject this patch from my v2 since more investigation\n> must be done to see if this second loop _can_ be dropped. At minimum, it isn't\n> properly silent when requested and there _is_ a performance boost possible,\n> even if we keep the check.\n\nOK. It *is* suspicious that the test suite doesn't exercise the check done by\nthat second loop. Removing it completely would rob us of so many ways to\noptimize it, though. ;-)\n\nRené\n"},{"id":"413356","messageId":"247e3c34-6190-c9e4-2a82-0f4b71249bdb@gmail.com","threadId":"54906","inReplyTo":"a8b5bb13-5c88-d744-b47e-7204e12ad05d@web.de","subject":"Re: [PATCH] cache-tree: use ce_namelen() instead of strlen()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-04T01:26:45Z","receivedAt":"2021-01-04T01:27:56Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/2/2021 10:19 AM, René Scharfe wrote:\n> Use the name length field of cache entries instead of calculating its\n> value anew.\n\nThanks! I didn't know about this macro.\n\n-Stolee\n\n> Signed-off-by: René Scharfe \n> ---\n> Not sure why it took me so long to spot this.. o_O\n> \n> cache-tree.c | 10 ++++++----\n> 1 file changed, 6 insertions(+), 4 deletions(-)\n> \n> diff --git a/cache-tree.c b/cache-tree.c\n> index a537a806c1..57cacab195 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,\n> \t\t * the cache is sorted. Also path can appear only once,\n> \t\t * which means conflicting one would immediately follow.\n> \t\t */\n> -\t\tconst char *this_name = cache[i]->name;\n> -\t\tconst char *next_name = cache[i+1]->name;\n> -\t\tint this_len = strlen(this_name);\n> -\t\tif (this_len < strlen(next_name) &&\n> +\t\tconst struct cache_entry *this_ce = cache[i];\n> +\t\tconst struct cache_entry *next_ce = cache[i + 1];\n> +\t\tconst char *this_name = this_ce->name;\n> +\t\tconst char *next_name = next_ce->name;\n> +\t\tint this_len = ce_namelen(this_ce);\n> +\t\tif (this_len < ce_namelen(next_ce) &&\n> \t\t strncmp(this_name, next_name, this_len) == 0 &&\n> \t\t next_name[this_len] == '/') {\n> \t\t\tif (10 < ++funny) {\n\nFor what it's worth, this caching of the lengths lowers my test\ntime from 854ms to 833ms. It goes down again to 816ms with the\nswapped conditional, so I'll include that patch here:\n\n-- >8 --\n\nFrom 8f303000030bd8f9db3466c90eb0d9fea11a7c3b Mon Sep 17 00:00:00 2001\nFrom: Derrick Stolee \nDate: Sun, 3 Jan 2021 20:20:05 -0500\nSubject: [PATCH] cache-tree: speed up consecutive path comparisons\nMIME-Version: 1.0\nContent-Type: text/plain; charset=UTF-8\nContent-Transfer-Encoding: 8bit\n\nThe previous change reduced time spent in strlen() while comparing\nconsecutive paths in verify_cache(), but we can do better. The\nconditional checks the existence of a directory separator at the correct\nlocation, but only after doing a string comparison. Swap the order to be\nlogically equivalent but perform fewer string comparisons.\n\nTo test the effect on performance, I used a repository with over three\nmillion paths in the index. I then ran the following command on repeat:\n\n git -c index.threads=1 commit --amend --allow-empty --no-edit\n\nHere are the measurements over 10 runs after a 5-run warmup:\n\n Benchmark #1: v2.30.0\n Time (mean ± σ): 854.5 ms ± 18.2 ms\n Range (min … max): 825.0 ms … 892.8 ms\n\n Benchmark #2: Previous change\n Time (mean ± σ): 833.2 ms ± 10.3 ms\n Range (min … max): 815.8 ms … 849.7 ms\n\n Benchmark #3: This change\n Time (mean ± σ): 815.5 ms ± 18.1 ms\n Range (min … max): 795.4 ms … 849.5 ms\n\nThis change is 2% faster than the previous change and 5% faster than\nv2.30.0.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 57cacab195..6eaef21145 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache,\n \t\tconst char *next_name = next_ce->name;\n \t\tint this_len = ce_namelen(this_ce);\n \t\tif (this_len < ce_namelen(next_ce) &&\n-\t\t strncmp(this_name, next_name, this_len) == 0 &&\n-\t\t next_name[this_len] == '/') {\n+\t\t next_name[this_len] == '/' &&\n+\t\t strncmp(this_name, next_name, this_len) == 0) {\n \t\t\tif (10 < ++funny) {\n \t\t\t\tfprintf(stderr, \"...\\n\");\n \t\t\t\tbreak;\n-- \nv2.30.0\n\n\n"},{"id":"413359","messageId":"4157b91acf8009ef2136c0856b6b61833d82873e.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 2/9] unpack-trees: add trace2 regions","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:11Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe unpack_trees() method is quite complicated and its performance can\nchange dramatically depending on how it is used. We already have some\nperformance tracing regions, but they have not been updated to the\ntrace2 API. Do so now.\n\nWe already have trace2 regions in unpack_trees.c:clear_ce_flags(), which\nuses a linear scan through the index without recursing into trees.\n\nSigned-off-by: Derrick Stolee \n---\n unpack-trees.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 323280dd48b..af6e9b9c2fd 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -1580,6 +1580,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\tdie(\"unpack_trees takes at most %d trees\", MAX_UNPACK_TREES);\n \n \ttrace_performance_enter();\n+\ttrace2_region_enter(\"unpack_trees\", \"unpack_trees\", the_repository);\n+\n \tif (!core_apply_sparse_checkout || !o->update)\n \t\to->skip_sparse_checkout = 1;\n \tif (!o->skip_sparse_checkout && !o->pl) {\n@@ -1653,7 +1655,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\t}\n \n \t\ttrace_performance_enter();\n+\t\ttrace2_region_enter(\"unpack_trees\", \"traverse_trees\", the_repository);\n \t\tret = traverse_trees(o->src_index, len, t, &info);\n+\t\ttrace2_region_leave(\"unpack_trees\", \"traverse_trees\", the_repository);\n \t\ttrace_performance_leave(\"traverse_trees\");\n \t\tif (ret < 0)\n \t\t\tgoto return_failed;\n@@ -1741,6 +1745,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n done:\n \tif (free_pattern_list)\n \t\tclear_pattern_list(&pl);\n+\ttrace2_region_leave(\"unpack_trees\", \"unpack_trees\", the_repository);\n \ttrace_performance_leave(\"unpack_trees\");\n \treturn ret;\n \n-- \ngitgitgadget\n\n"},{"id":"413360","messageId":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.git.1609356413.gitgitgadget@gmail.com","subject":"[PATCH v2 0/9] Cleanups around index operations","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:09Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"I've taken a professional interest in the index lately, and I've been trying\nmostly to learn about it and measure different operations. Along the way,\nI've seen some possible improvements in documentation, behavior, and\ntracing.\n\nThis series collects most of my thoughts so far, including:\n\n 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches\n 1-5).\n 2. Update documentation about the cached tree extension (Patches 6-7).\n 3. Improved the performance of verify_cache() (Patches 8-9).\n\nThanks, -Stolee\n\n[1]\nhttps://lore.kernel.org/git/pull.828.git.1609302714183.gitgitgadget@gmail.com/\n\n\nUPDATES IN V2\n=============\n\n * Instead of completely dropping the second loop in verify_cache(), improve\n the performance. I include René's patch (unaltered except for my\n sign-off) in this series for clarity.\n\n * Fixed the unnecessary whitespace change in patch 1. Updated the commit\n message to refer to a similar effort in changed-path Bloom filters.\n\n * The range enter/leave block in patch 5 now spans the entire method.\n\nDerrick Stolee (8):\n tree-walk: report recursion counts\n unpack-trees: add trace2 regions\n cache-tree: use trace2 in cache_tree_update()\n cache-tree: trace regions for I/O\n cache-tree: trace regions for prime_cache_tree\n index-format: update preamble to cached tree extension\n index-format: discuss recursion of cached-tree better\n cache-tree: speed up consecutive path comparisons\n\nRené Scharfe (1):\n cache-tree: use ce_namelen() instead of strlen()\n\n Documentation/technical/index-format.txt | 39 +++++++++++++++++++-----\n cache-tree.c | 30 +++++++++++++-----\n tree-walk.c | 33 ++++++++++++++++++++\n unpack-trees.c | 5 +++\n 4 files changed, 93 insertions(+), 14 deletions(-)\n\n\nbase-commit: 71ca53e8125e36efbda17293c50027d31681a41f\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-829%2Fderrickstolee%2Fcache-tree%2Fbasics-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-829/derrickstolee/cache-tree/basics-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/829\n\nRange-diff vs v1:\n\n 1: f727880add6 ! 1: 0e500c86f39 tree-walk: report recursion counts\n @@ Metadata\n ## Commit message ##\n tree-walk: report recursion counts\n \n - The traverse_trees() method recusively walks through trees, but also\n + The traverse_trees() method recursively walks through trees, but also\n prunes the tree-walk based on a callback. Some callers, such as\n unpack_trees(), are quite complicated and can have wildly different\n performance between two different commands.\n @@ Commit message\n instances of traverse_trees(), but they provide reproducible values for\n demonstrating improvements to the pruning algorithm when possible.\n \n + This change is modeled after a similar statistics reporting in 42e50e78\n + (revision.c: add trace2 stats around Bloom filter usage, 2020-04-06).\n +\n Signed-off-by: Derrick Stolee \n \n ## tree-walk.c ##\n @@ tree-walk.c: int traverse_trees(struct index_state *istate,\n \treturn error;\n }\n \n -\n - ## unpack-trees.c ##\n -@@ unpack-trees.c: static void populate_from_existing_patterns(struct unpack_trees_options *o,\n - \tfree(sparse);\n - }\n - \n --\n - static int verify_absent(const struct cache_entry *,\n - \t\t\t enum unpack_trees_error_types,\n - \t\t\t struct unpack_trees_options *);\n 2: 6923e6211aa = 2: 4157b91acf8 unpack-trees: add trace2 regions\n 3: 802718084a7 = 3: 8959d57abdd cache-tree: use trace2 in cache_tree_update()\n 4: 65feaa497b2 = 4: 1d8a797ee26 cache-tree: trace regions for I/O\n 5: 5d1c9c8a356 ! 5: 2b2e70bb77c cache-tree: trace regions for prime_cache_tree\n @@ Commit message\n \n ## cache-tree.c ##\n @@ cache-tree.c: void prime_cache_tree(struct repository *r,\n + \t\t struct index_state *istate,\n + \t\t struct tree *tree)\n {\n ++\ttrace2_region_enter(\"cache-tree\", \"prime_cache_tree\", the_repository);\n \tcache_tree_free(&istate->cache_tree);\n \tistate->cache_tree = cache_tree();\n +\n -+\ttrace2_region_enter(\"cache-tree\", \"prime_cache_tree\", the_repository);\n \tprime_cache_tree_rec(r, istate->cache_tree, tree);\n -+\ttrace2_region_leave(\"cache-tree\", \"prime_cache_tree\", the_repository);\n \tistate->cache_changed |= CACHE_TREE_CHANGED;\n ++\ttrace2_region_leave(\"cache-tree\", \"prime_cache_tree\", the_repository);\n }\n \n + /*\n 6: fb9d5468184 = 6: 75b51483d3c index-format: update preamble to cached tree extension\n 7: 65fb9f72251 = 7: b2bb141a254 index-format: discuss recursion of cached-tree better\n 8: 20ea7050324 < -: ----------- cache-tree: avoid path comparison loop when silent\n -: ----------- > 8: 5298694786e cache-tree: use ce_namelen() instead of strlen()\n -: ----------- > 9: 72edd7bb427 cache-tree: speed up consecutive path comparisons\n\n-- \ngitgitgadget\n"},{"id":"413361","messageId":"1d8a797ee2650e8c815281b0c672301c7f24a724.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 4/9] cache-tree: trace regions for I/O","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:13Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAs we write or read the cached tree index extension, it can be good to\nisolate how much of the file I/O time is spent constructing this\nin-memory tree from the existing index or writing it out again to the\nnew index file. Use trace2 regions to indicate that we are spending time\non this operation.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 11 ++++++++++-\n 1 file changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 9efb6748662..45fb57b17f3 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -494,7 +494,9 @@ static void write_one(struct strbuf *buffer, struct cache_tree *it,\n \n void cache_tree_write(struct strbuf *sb, struct cache_tree *root)\n {\n+\ttrace2_region_enter(\"cache_tree\", \"write\", the_repository);\n \twrite_one(sb, root, \"\", 0);\n+\ttrace2_region_leave(\"cache_tree\", \"write\", the_repository);\n }\n \n static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)\n@@ -583,9 +585,16 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)\n \n struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)\n {\n+\tstruct cache_tree *result;\n+\n \tif (buffer[0])\n \t\treturn NULL; /* not the whole tree */\n-\treturn read_one(&buffer, &size);\n+\n+\ttrace2_region_enter(\"cache_tree\", \"read\", the_repository);\n+\tresult = read_one(&buffer, &size);\n+\ttrace2_region_leave(\"cache_tree\", \"read\", the_repository);\n+\n+\treturn result;\n }\n \n static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)\n-- \ngitgitgadget\n\n"},{"id":"413362","messageId":"0e500c86f397987c4d03beac52b1e91f683e4d11.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 1/9] tree-walk: report recursion counts","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:10Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe traverse_trees() method recursively walks through trees, but also\nprunes the tree-walk based on a callback. Some callers, such as\nunpack_trees(), are quite complicated and can have wildly different\nperformance between two different commands.\n\nCreate constants that count these values and then report the results at\nthe end of a process. These counts are cumulative across multiple \"root\"\ninstances of traverse_trees(), but they provide reproducible values for\ndemonstrating improvements to the pruning algorithm when possible.\n\nThis change is modeled after a similar statistics reporting in 42e50e78\n(revision.c: add trace2 stats around Bloom filter usage, 2020-04-06).\n\nSigned-off-by: Derrick Stolee \n---\n tree-walk.c | 33 +++++++++++++++++++++++++++++++++\n 1 file changed, 33 insertions(+)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 0160294712b..2d6226d5f18 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -4,6 +4,7 @@\n #include \"object-store.h\"\n #include \"tree.h\"\n #include \"pathspec.h\"\n+#include \"json-writer.h\"\n \n static const char *get_mode(const char *str, unsigned int *modep)\n {\n@@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)\n \treturn 1;\n }\n \n+static int traverse_trees_atexit_registered;\n+static int traverse_trees_count;\n+static int traverse_trees_cur_depth;\n+static int traverse_trees_max_depth;\n+\n+static void trace2_traverse_trees_statistics_atexit(void)\n+{\n+\tstruct json_writer jw = JSON_WRITER_INIT;\n+\n+\tjw_object_begin(&jw, 0);\n+\tjw_object_intmax(&jw, \"traverse_trees_count\", traverse_trees_count);\n+\tjw_object_intmax(&jw, \"traverse_trees_max_depth\", traverse_trees_max_depth);\n+\tjw_end(&jw);\n+\n+\ttrace2_data_json(\"traverse_trees\", the_repository, \"statistics\", &jw);\n+\n+\tjw_release(&jw);\n+}\n+\n void setup_traverse_info(struct traverse_info *info, const char *base)\n {\n \tsize_t pathlen = strlen(base);\n@@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n \tinfo->namelen = pathlen;\n \tif (pathlen)\n \t\tinfo->prev = &dummy;\n+\n+\tif (trace2_is_enabled() && !traverse_trees_atexit_registered) {\n+\t\tatexit(trace2_traverse_trees_statistics_atexit);\n+\t\ttraverse_trees_atexit_registered = 1;\n+\t}\n }\n \n char *make_traverse_path(char *path, size_t pathlen,\n@@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,\n \tint interesting = 1;\n \tchar *traverse_path;\n \n+\ttraverse_trees_count++;\n+\ttraverse_trees_cur_depth++;\n+\n+\tif (traverse_trees_cur_depth > traverse_trees_max_depth)\n+\t\ttraverse_trees_max_depth = traverse_trees_cur_depth;\n+\n \tif (n >= ARRAY_SIZE(entry))\n \t\tBUG(\"traverse_trees() called with too many trees (%d)\", n);\n \n@@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,\n \tfree(traverse_path);\n \tinfo->traverse_path = NULL;\n \tstrbuf_release(&base);\n+\n+\ttraverse_trees_cur_depth--;\n \treturn error;\n }\n \n-- \ngitgitgadget\n\n"},{"id":"413363","messageId":"8959d57abddd620f4b597e4c43c5d2545c666e97.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 3/9] cache-tree: use trace2 in cache_tree_update()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:12Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis matches a trace_performance_enter()/trace_performance_leave() pair\nadded by 0d1ed59 (unpack-trees: add performance tracing, 2018-08-18).\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex a537a806c16..9efb6748662 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -442,7 +442,9 @@ int cache_tree_update(struct index_state *istate, int flags)\n \tif (i)\n \t\treturn i;\n \ttrace_performance_enter();\n+\ttrace2_region_enter(\"cache_tree\", \"update\", the_repository);\n \ti = update_one(it, cache, entries, \"\", 0, &skip, flags);\n+\ttrace2_region_leave(\"cache_tree\", \"update\", the_repository);\n \ttrace_performance_leave(\"cache_tree_update\");\n \tif (i < 0)\n \t\treturn i;\n-- \ngitgitgadget\n\n"},{"id":"413364","messageId":"2b2e70bb77c8dafbf2cfedd9e68f834f02deb4a2.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 5/9] cache-tree: trace regions for prime_cache_tree","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:14Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nCommands such as \"git reset --hard\" rebuild the in-memory representation\nof the cached tree index extension by parsing tree objects starting at a\nknown root tree. The performance of this operation can vary widely\ndepending on the width and depth of the repository's working directory\nstructure. Measure the time in this operation using trace2 regions in\nprime_cache_tree().\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 45fb57b17f3..7da59b2aa07 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -744,10 +744,13 @@ void prime_cache_tree(struct repository *r,\n \t\t struct index_state *istate,\n \t\t struct tree *tree)\n {\n+\ttrace2_region_enter(\"cache-tree\", \"prime_cache_tree\", the_repository);\n \tcache_tree_free(&istate->cache_tree);\n \tistate->cache_tree = cache_tree();\n+\n \tprime_cache_tree_rec(r, istate->cache_tree, tree);\n \tistate->cache_changed |= CACHE_TREE_CHANGED;\n+\ttrace2_region_leave(\"cache-tree\", \"prime_cache_tree\", the_repository);\n }\n \n /*\n-- \ngitgitgadget\n\n"},{"id":"413365","messageId":"75b51483d3c7088d0cfae36544966672374c50f9.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 6/9] index-format: update preamble to cached tree extension","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:15Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nI had difficulty in my efforts to learn about the cached tree extension\nbased on the documentation and code because I had an incorrect\nassumption about how it behaved. This might be due to some ambiguity in\nthe documentation, so this change modifies the beginning of the cached\ntree format by expanding the description of the feature.\n\nMy hope is that this documentation clarifies a few things:\n\n1. There is an in-memory recursive tree structure that is constructed\n from the extension data. This structure has a few differences, such\n as where the name is stored.\n\n2. What does it mean for an entry to be invalid?\n\n3. When exactly are \"new\" trees created?\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----\n 1 file changed, 30 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex 69edf46c031..c614e136e24 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -138,12 +138,36 @@ Git index format\n \n === Cached tree\n \n- Cached tree extension contains pre-computed hashes for trees that can\n- be derived from the index. It helps speed up tree object generation\n- from index for a new commit.\n-\n- When a path is updated in index, the path must be invalidated and\n- removed from tree cache.\n+ Since the index does not record entries for directories, the cache\n+ entries cannot describe tree objects that already exist in the object\n+ database for regions of the index that are unchanged from an existing\n+ commit. The cached tree extension stores a recursive tree structure that\n+ describes the trees that already exist and completely match sections of\n+ the cache entries. This speeds up tree object generation from the index\n+ for a new commit by only computing the trees that are \"new\" to that\n+ commit.\n+\n+ The recursive tree structure uses nodes that store a number of cache\n+ entries, a list of subnodes, and an object ID (OID). The OID references\n+ the exising tree for that node, if it is known to exist. The subnodes\n+ correspond to subdirectories that themselves have cached tree nodes. The\n+ number of cache entries corresponds to the number of cache entries in\n+ the index that describe paths within that tree's directory.\n+\n+ Note that the path for a given tree is part of the parent node in-memory\n+ but is part of the child in the file format. The root tree has an empty\n+ string for its name and its name does not exist in-memory.\n+\n+ When a path is updated in index, Git invalidates all nodes of the\n+ recurisive cached tree corresponding to the parent directories of that\n+ path. We store these tree nodes as being \"invalid\" by using \"-1\" as the\n+ number of cache entries. To create trees corresponding to the current\n+ index, Git only walks the invalid tree nodes and uses the cached OIDs\n+ for the valid trees to construct new trees. In this way, Git only\n+ constructs trees on the order of the number of changed paths (and their\n+ depth in the working directory). This comes at a cost of tracking the\n+ full directory structure in the cached tree extension, but this is\n+ generally smaller than the full cache entry list in the index.\n \n The signature for this extension is { 'T', 'R', 'E', 'E' }.\n \n-- \ngitgitgadget\n\n"},{"id":"413366","messageId":"b2bb141a254ab3aa0b91886be3fe8efe52732783.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 7/9] index-format: discuss recursion of cached-tree better","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:16Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe end of the cached tree index extension format trails off with\nellipses ever since 23fcc98 (doc: technical details about the index\nfile format, 2011-03-01). While an intuitive reader could gather what\nthis means, it could be better to use \"and so on\" instead.\n\nReally, this is only justified because I also wanted to point out that\nthe number of subtrees in the index format is used to determine when the\nrecursive depth-first-search stack should be \"popped.\" This should help\nto add clarity to the format.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/index-format.txt | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex c614e136e24..2ebe88b9d46 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -198,7 +198,8 @@ Git index format\n first entry represents the root level of the repository, followed by the\n first subtree--let's call this A--of the root level (with its name\n relative to the root level), followed by the first subtree of A (with\n- its name relative to A), ...\n+ its name relative to A), and so on. The specified number of subtrees\n+ indicates when the current level of the recursive stack is complete.\n \n === Resolve undo\n \n-- \ngitgitgadget\n\n"},{"id":"413367","messageId":"72edd7bb4278a8ce6823752a3142b14a05bbea58.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 9/9] cache-tree: speed up consecutive path comparisons","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:18Z","receivedAt":"2021-01-04T03:11:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change reduced time spent in strlen() while comparing\nconsecutive paths in verify_cache(), but we can do better. The\nconditional checks the existence of a directory separator at the correct\nlocation, but only after doing a string comparison. Swap the order to be\nlogically equivalent but perform fewer string comparisons.\n\nTo test the effect on performance, I used a repository with over three\nmillion paths in the index. I then ran the following command on repeat:\n\n git -c index.threads=1 commit --amend --allow-empty --no-edit\n\nHere are the measurements over 10 runs after a 5-run warmup:\n\n Benchmark #1: v2.30.0\n Time (mean ± σ): 854.5 ms ± 18.2 ms\n Range (min … max): 825.0 ms … 892.8 ms\n\n Benchmark #2: Previous change\n Time (mean ± σ): 833.2 ms ± 10.3 ms\n Range (min … max): 815.8 ms … 849.7 ms\n\n Benchmark #3: This change\n Time (mean ± σ): 815.5 ms ± 18.1 ms\n Range (min … max): 795.4 ms … 849.5 ms\n\nThis change is 2% faster than the previous change and 5% faster than\nv2.30.0.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 4274de75bac..3f1a8d4f1b7 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache,\n \t\tconst char *next_name = next_ce->name;\n \t\tint this_len = ce_namelen(this_ce);\n \t\tif (this_len < ce_namelen(next_ce) &&\n-\t\t strncmp(this_name, next_name, this_len) == 0 &&\n-\t\t next_name[this_len] == '/') {\n+\t\t next_name[this_len] == '/' &&\n+\t\t strncmp(this_name, next_name, this_len) == 0) {\n \t\t\tif (10 < ++funny) {\n \t\t\t\tfprintf(stderr, \"...\\n\");\n \t\t\t\tbreak;\n-- \ngitgitgadget\n"},{"id":"413368","messageId":"5298694786e2c76fb08a0b37890e3183d788ff10.1609729758.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v2 8/9] cache-tree: use ce_namelen() instead of strlen()","fromName":"René Scharfe via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-04T03:09:17Z","receivedAt":"2021-01-04T03:11:03Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= \n\nUse the name length field of cache entries instead of calculating its\nvalue anew.\n\nSigned-off-by: René Scharfe \nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 10 ++++++----\n 1 file changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 7da59b2aa07..4274de75bac 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,\n \t\t * the cache is sorted. Also path can appear only once,\n \t\t * which means conflicting one would immediately follow.\n \t\t */\n-\t\tconst char *this_name = cache[i]->name;\n-\t\tconst char *next_name = cache[i+1]->name;\n-\t\tint this_len = strlen(this_name);\n-\t\tif (this_len < strlen(next_name) &&\n+\t\tconst struct cache_entry *this_ce = cache[i];\n+\t\tconst struct cache_entry *next_ce = cache[i + 1];\n+\t\tconst char *this_name = this_ce->name;\n+\t\tconst char *next_name = next_ce->name;\n+\t\tint this_len = ce_namelen(this_ce);\n+\t\tif (this_len < ce_namelen(next_ce) &&\n \t\t strncmp(this_name, next_name, this_len) == 0 &&\n \t\t next_name[this_len] == '/') {\n \t\t\tif (10 < ++funny) {\n-- \ngitgitgadget\n\n"},{"id":"413446","messageId":"xmqqlfd7zj0d.fsf@gitster.c.googlers.com","threadId":"54906","inReplyTo":"a8b5bb13-5c88-d744-b47e-7204e12ad05d@web.de","subject":"Re: [PATCH] cache-tree: use ce_namelen() instead of strlen()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-05T12:05:22Z","receivedAt":"2021-01-05T12:06:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Use the name length field of cache entries instead of calculating its\n> value anew.\n>\n> Signed-off-by: René Scharfe \n> ---\n> Not sure why it took me so long to spot this.. o_O\n\nThat probably is because this does not cause behaviour change.\n\nIt used to be that use of ce_namelen() was more important in\nlearning the length of the string before 7a51ed66 (Make on-disk\nindex representation separate from in-core one, 2008-01-14) and\n7fec10b7 (index: be careful when handling long names, 2008-01-18).\nThe on-disk field to store the name length has only 12 bits, and\nbefore b60e188c (Strip namelen out of ce_flags into a ce_namelen\nfield, 2012-07-11), the convention to learn the length of the name\nof an in-core cache entry was to see the field and then if it fully\noccupies the full 12-bit field, ask the name string itself its\nlength with strlen().\n\nThese days, ce->namelen is a separate field that always gives the\nfull length after the on-disk index is read, so with this change,\nyou won't be running strlen() in this part of the function even with\nan entry with a long pathname.\n\n>\n> cache-tree.c | 10 ++++++----\n> 1 file changed, 6 insertions(+), 4 deletions(-)\n>\n> diff --git a/cache-tree.c b/cache-tree.c\n> index a537a806c1..57cacab195 100644\n> --- a/cache-tree.c\n> +++ b/cache-tree.c\n> @@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,\n> \t\t * the cache is sorted. Also path can appear only once,\n> \t\t * which means conflicting one would immediately follow.\n> \t\t */\n> -\t\tconst char *this_name = cache[i]->name;\n> -\t\tconst char *next_name = cache[i+1]->name;\n> -\t\tint this_len = strlen(this_name);\n> -\t\tif (this_len < strlen(next_name) &&\n> +\t\tconst struct cache_entry *this_ce = cache[i];\n> +\t\tconst struct cache_entry *next_ce = cache[i + 1];\n> +\t\tconst char *this_name = this_ce->name;\n> +\t\tconst char *next_name = next_ce->name;\n> +\t\tint this_len = ce_namelen(this_ce);\n> +\t\tif (this_len < ce_namelen(next_ce) &&\n> \t\t strncmp(this_name, next_name, this_len) == 0 &&\n> \t\t next_name[this_len] == '/') {\n> \t\t\tif (10 < ++funny) {\n> --\n> 2.30.0\n"},{"id":"413546","messageId":"xmqqble2sav9.fsf@gitster.c.googlers.com","threadId":"54906","inReplyTo":"CABPp-BFp5=C+6B1WUarXzabo0fU4xotP5UG91-hYahCHDA6Cng@mail.gmail.com","subject":"Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-06T08:55:22Z","receivedAt":"2021-01-06T08:56:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> Looking through that code, I come to the same conclusion, though it\n> might be nice to have Junio confirm (and to explain the \"if (10 <\n> ++funny)\" section; did that help debugging too?). The second part of\n> the loop was part of his initial commit adding the cache-tree\n> extension in commit 749864627c (\"Add cache-tree.\", 2006-04-23)\n\nThis is not about debugging our implementation. The verification\nwas done to protect against the on-disk index file left by broken\nimplementations of other people. Either JGit or Dulwich (I do not\nrecall which one) used to have such a broken sort long time ago,\nIIRC, and the thing is, a broken implementation can be internally\nconsistent.\n\nI do not think we've heard problem reports discovered by this check\nabout other peoples' broken implementation, but a chicken-and-egg is\ncertainly in action here. The check would have caught any new and\nbroken implementation of Git before it got released to the wild to\ncause harm and that is probably we haven't heard.\n\n"},{"id":"413575","messageId":"9df34ae5-2be0-40b8-b1e3-0198e3dcef53@gmail.com","threadId":"54906","inReplyTo":"xmqqble2sav9.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-06T12:08:06Z","receivedAt":"2021-01-06T12:08:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/6/2021 3:55 AM, Junio C Hamano wrote:\n> Elijah Newren writes:\n> \n>> Looking through that code, I come to the same conclusion, though it\n>> might be nice to have Junio confirm (and to explain the \"if (10 <\n>> ++funny)\" section; did that help debugging too?). The second part of\n>> the loop was part of his initial commit adding the cache-tree\n>> extension in commit 749864627c (\"Add cache-tree.\", 2006-04-23)\n> \n> This is not about debugging our implementation. The verification\n> was done to protect against the on-disk index file left by broken\n> implementations of other people. Either JGit or Dulwich (I do not\n> recall which one) used to have such a broken sort long time ago,\n> IIRC, and the thing is, a broken implementation can be internally\n> consistent.\n> \n> I do not think we've heard problem reports discovered by this check\n> about other peoples' broken implementation, but a chicken-and-egg is\n> certainly in action here. The check would have caught any new and\n> broken implementation of Git before it got released to the wild to\n> cause harm and that is probably we haven't heard.\n Thanks for the additional context. I think the performance\nenhancements in v2 are enough to satisfy me for now without\ncompletely removing the functionality.\n\nThanks,\n-Stolee\n"},{"id":"413636","messageId":"xmqqble1o5sc.fsf@gitster.c.googlers.com","threadId":"54906","inReplyTo":"75b51483d3c7088d0cfae36544966672374c50f9.1609729758.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-07T02:10:59Z","receivedAt":"2021-01-07T02:12:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> Subject: Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension\n\nBy the way, the name of the extension is \"cache tree\".\n\n\tgit grep -i 'cached[- ]tree' ':!po/'\n \nreveals there are a handful of mistakes already present but their\nnumber is dwarfed when we check:\n\n\tgit grep -i 'cache tree' ':!po/'\n\n> I had difficulty in my efforts to learn about the cached tree extension\n> based on the documentation and code because I had an incorrect\n> assumption about how it behaved. This might be due to some ambiguity in\n> the documentation, so this change modifies the beginning of the cached\n> tree format by expanding the description of the feature.\n>\n> My hope is that this documentation clarifies a few things:\n>\n> 1. There is an in-memory recursive tree structure that is constructed\n> from the extension data. This structure has a few differences, such\n> as where the name is stored.\n>\n> 2. What does it mean for an entry to be invalid?\n>\n> 3. When exactly are \"new\" trees created?\n\nThanks. Describing them is a worthy goal.\n\n> + Since the index does not record entries for directories, the cache\n> + entries cannot describe tree objects that already exist in the object\n> + database for regions of the index that are unchanged from an existing\n> + commit. The cached tree extension stores a recursive tree structure that\n> + describes the trees that already exist and completely match sections of\n> + the cache entries. This speeds up tree object generation from the index\n> + for a new commit by only computing the trees that are \"new\" to that\n> + commit.\n\nThe original motivation was the above one. A cache of tree objects\nthat correspond to unmodified part of the directory structure helps\nwriting out a new tree out of modified index.\n\nWe later found out that we rather often compare the index against\nthe tree of HEAD (think: \"git status\"), and diff-lib.c::diff_cache()\ndoes take advantage of the fact that an entire directory can be\nskipped if the tree object taken from the HEAD side exactly matches\nthe tree recorded for the subdirectory in the cache tree extension.\n\n> + The recursive tree structure uses nodes that store a number of cache\n> + entries, a list of subnodes, and an object ID (OID). The OID references\n> + the exising tree for that node, if it is known to exist. The subnodes\n> + correspond to subdirectories that themselves have cached tree nodes. The\n> + number of cache entries corresponds to the number of cache entries in\n> + the index that describe paths within that tree's directory.\n\nOK.\n\n> + Note that the path for a given tree is part of the parent node in-memory\n\nSorry, I am not sure if I follow. The top-level in-core cache_tree\nobject records the number of entries, tree object name for the\nentire tree (if valid), and cache_tree_sub structures, one for each\nsubdirectory. Each of the cache_tree_sub structure describes the\n\"child\" directory, including the path to it.\n\n> + but is part of the child in the file format. The root tree has an empty\n> + string for its name and its name does not exist in-memory.\n\nIt's more like we could have consistently used cache_tree_sub\ninstances to represent each and every level (i.e. I consider that\ncache_tree_sub is what represents a directory, with cache_tree being\na record of just one aspect of it) including the root of the\nhierarchy, but because there wasn't much point in giving a name to\nthe root level, I cheated and avoided wasting a cache_tree_sub for\nit. So from that point of view, the path belongs to the node in\neach level in both in-core and on-disk representations.\n\n> + When a path is updated in index, Git invalidates all nodes of the\n> + recurisive cached tree corresponding to the parent directories of that\n> + path. We store these tree nodes as being \"invalid\" by using \"-1\" as the\n> + number of cache entries.\n\nCorrect.\n\n> + To create trees corresponding to the current\n> + index, Git only walks the invalid tree nodes and uses the cached OIDs\n> + for the valid trees to construct new trees.\n\nI wonder if the above is sufficiently clear, or \"Git only has to\nwalk the spans of index entries that corresponds to the invalid\ntrees, while reusing the ...\" is too long and detailed.\n\n> + In this way, Git only\n> + constructs trees on the order of the number of changed paths (and their\n> + depth in the working directory). This comes at a cost of tracking the\n> + full directory structure in the cached tree extension, but this is\n> + generally smaller than the full cache entry list in the index.\n> \n> The signature for this extension is { 'T', 'R', 'E', 'E' }.\n\nLooks good. Thanks for working on this.\n"},{"id":"413683","messageId":"5a1a51c1-7ada-6f66-a6d0-2fc01303d334@gmail.com","threadId":"54906","inReplyTo":"xmqqble1o5sc.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-07T11:51:03Z","receivedAt":"2021-01-07T11:51:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/6/2021 9:10 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> Subject: Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension\n> \n> By the way, the name of the extension is \"cache tree\".\n> \n> \tgit grep -i 'cached[- ]tree' ':!po/'\n> \n> reveals there are a handful of mistakes already present but their\n> number is dwarfed when we check:\n> \n> \tgit grep -i 'cache tree' ':!po/'\n\nI will fix my own additions and add a patch that fixes these mistakes.\n\n>> + Since the index does not record entries for directories, the cache\n>> + entries cannot describe tree objects that already exist in the object\n>> + database for regions of the index that are unchanged from an existing\n>> + commit. The cached tree extension stores a recursive tree structure that\n>> + describes the trees that already exist and completely match sections of\n>> + the cache entries. This speeds up tree object generation from the index\n>> + for a new commit by only computing the trees that are \"new\" to that\n>> + commit.\n> \n> The original motivation was the above one. A cache of tree objects\n> that correspond to unmodified part of the directory structure helps\n> writing out a new tree out of modified index.\n> \n> We later found out that we rather often compare the index against\n> the tree of HEAD (think: \"git status\"), and diff-lib.c::diff_cache()\n> does take advantage of the fact that an entire directory can be\n> skipped if the tree object taken from the HEAD side exactly matches\n> the tree recorded for the subdirectory in the cache tree extension.\n\nI need to read more about this. traverse_by_cache_tree() seems to\nbe a good place to start. Thanks.\n\n>> + The recursive tree structure uses nodes that store a number of cache\n>> + entries, a list of subnodes, and an object ID (OID). The OID references\n>> + the exising tree for that node, if it is known to exist. The subnodes\n>> + correspond to subdirectories that themselves have cached tree nodes. The\n>> + number of cache entries corresponds to the number of cache entries in\n>> + the index that describe paths within that tree's directory.\n\ns/exising/existing/\n\n> \n> OK.\n> \n>> + Note that the path for a given tree is part of the parent node in-memory\n> \n> Sorry, I am not sure if I follow. The top-level in-core cache_tree\n> object records the number of entries, tree object name for the\n> entire tree (if valid), and cache_tree_sub structures, one for each\n> subdirectory. Each of the cache_tree_sub structure describes the\n> \"child\" directory, including the path to it.\n> \n>> + but is part of the child in the file format. The root tree has an empty\n>> + string for its name and its name does not exist in-memory.\n> \n> It's more like we could have consistently used cache_tree_sub\n> instances to represent each and every level (i.e. I consider that\n> cache_tree_sub is what represents a directory, with cache_tree being\n> a record of just one aspect of it) including the root of the\n> hierarchy, but because there wasn't much point in giving a name to\n> the root level, I cheated and avoided wasting a cache_tree_sub for\n> it. So from that point of view, the path belongs to the node in\n> each level in both in-core and on-disk representations.\n\nThat's a good point. I'll retract my statement here.\n\n>> + When a path is updated in index, Git invalidates all nodes of the\n>> + recurisive cached tree corresponding to the parent directories of that\n>> + path. We store these tree nodes as being \"invalid\" by using \"-1\" as the\n>> + number of cache entries.\n> \n> Correct.\n\nMaking note of my s/recurisive/recursive/ typo here.\n\n>> + To create trees corresponding to the current\n>> + index, Git only walks the invalid tree nodes and uses the cached OIDs\n>> + for the valid trees to construct new trees.\n> \n> I wonder if the above is sufficiently clear, or \"Git only has to\n> walk the spans of index entries that corresponds to the invalid\n> trees, while reusing the ...\" is too long and detailed.\n\nI will try to simplify.\n\nThanks,\n-Stolee\n"},{"id":"413703","messageId":"0e500c86f397987c4d03beac52b1e91f683e4d11.1610037131.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 01/10] tree-walk: report recursion counts","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:02Z","receivedAt":"2021-01-07T16:33:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe traverse_trees() method recursively walks through trees, but also\nprunes the tree-walk based on a callback. Some callers, such as\nunpack_trees(), are quite complicated and can have wildly different\nperformance between two different commands.\n\nCreate constants that count these values and then report the results at\nthe end of a process. These counts are cumulative across multiple \"root\"\ninstances of traverse_trees(), but they provide reproducible values for\ndemonstrating improvements to the pruning algorithm when possible.\n\nThis change is modeled after a similar statistics reporting in 42e50e78\n(revision.c: add trace2 stats around Bloom filter usage, 2020-04-06).\n\nSigned-off-by: Derrick Stolee \n---\n tree-walk.c | 33 +++++++++++++++++++++++++++++++++\n 1 file changed, 33 insertions(+)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 0160294712b..2d6226d5f18 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -4,6 +4,7 @@\n #include \"object-store.h\"\n #include \"tree.h\"\n #include \"pathspec.h\"\n+#include \"json-writer.h\"\n \n static const char *get_mode(const char *str, unsigned int *modep)\n {\n@@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)\n \treturn 1;\n }\n \n+static int traverse_trees_atexit_registered;\n+static int traverse_trees_count;\n+static int traverse_trees_cur_depth;\n+static int traverse_trees_max_depth;\n+\n+static void trace2_traverse_trees_statistics_atexit(void)\n+{\n+\tstruct json_writer jw = JSON_WRITER_INIT;\n+\n+\tjw_object_begin(&jw, 0);\n+\tjw_object_intmax(&jw, \"traverse_trees_count\", traverse_trees_count);\n+\tjw_object_intmax(&jw, \"traverse_trees_max_depth\", traverse_trees_max_depth);\n+\tjw_end(&jw);\n+\n+\ttrace2_data_json(\"traverse_trees\", the_repository, \"statistics\", &jw);\n+\n+\tjw_release(&jw);\n+}\n+\n void setup_traverse_info(struct traverse_info *info, const char *base)\n {\n \tsize_t pathlen = strlen(base);\n@@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)\n \tinfo->namelen = pathlen;\n \tif (pathlen)\n \t\tinfo->prev = &dummy;\n+\n+\tif (trace2_is_enabled() && !traverse_trees_atexit_registered) {\n+\t\tatexit(trace2_traverse_trees_statistics_atexit);\n+\t\ttraverse_trees_atexit_registered = 1;\n+\t}\n }\n \n char *make_traverse_path(char *path, size_t pathlen,\n@@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,\n \tint interesting = 1;\n \tchar *traverse_path;\n \n+\ttraverse_trees_count++;\n+\ttraverse_trees_cur_depth++;\n+\n+\tif (traverse_trees_cur_depth > traverse_trees_max_depth)\n+\t\ttraverse_trees_max_depth = traverse_trees_cur_depth;\n+\n \tif (n >= ARRAY_SIZE(entry))\n \t\tBUG(\"traverse_trees() called with too many trees (%d)\", n);\n \n@@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,\n \tfree(traverse_path);\n \tinfo->traverse_path = NULL;\n \tstrbuf_release(&base);\n+\n+\ttraverse_trees_cur_depth--;\n \treturn error;\n }\n \n-- \ngitgitgadget\n\n"},{"id":"413704","messageId":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v2.git.1609729758.gitgitgadget@gmail.com","subject":"[PATCH v3 00/10] Cleanups around index operations","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:01Z","receivedAt":"2021-01-07T16:33:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"I've taken a professional interest in the index lately, and I've been trying\nmostly to learn about it and measure different operations. Along the way,\nI've seen some possible improvements in documentation, behavior, and\ntracing.\n\nThis series collects most of my thoughts so far, including:\n\n 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches\n 1-5).\n 2. Update documentation about the cached tree extension (Patches 6-7).\n 3. Improved the performance of verify_cache() (Patches 8-9).\n\nThanks, -Stolee\n\n[1]\nhttps://lore.kernel.org/git/pull.828.git.1609302714183.gitgitgadget@gmail.com/\n\n\nUPDATES IN V3\n=============\n\n * Added a patch that fixes previous uses of \"cached tree\"\n\n * Updated preamble patch with typos and semantic corrections.\n\nDerrick Stolee (9):\n tree-walk: report recursion counts\n unpack-trees: add trace2 regions\n cache-tree: use trace2 in cache_tree_update()\n cache-tree: trace regions for I/O\n cache-tree: trace regions for prime_cache_tree\n index-format: use 'cache tree' over 'cached tree'\n index-format: update preamble to cache tree extension\n index-format: discuss recursion of cached-tree better\n cache-tree: speed up consecutive path comparisons\n\nRené Scharfe (1):\n cache-tree: use ce_namelen() instead of strlen()\n\n Documentation/technical/index-format.txt | 42 ++++++++++++++++++------\n cache-tree.c | 30 +++++++++++++----\n t/t7104-reset-hard.sh | 2 +-\n tree-walk.c | 33 +++++++++++++++++++\n unpack-trees.c | 5 +++\n 5 files changed, 94 insertions(+), 18 deletions(-)\n\n\nbase-commit: 71ca53e8125e36efbda17293c50027d31681a41f\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-829%2Fderrickstolee%2Fcache-tree%2Fbasics-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-829/derrickstolee/cache-tree/basics-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/829\n\nRange-diff vs v2:\n\n 1: 0e500c86f39 = 1: 0e500c86f39 tree-walk: report recursion counts\n 2: 4157b91acf8 = 2: 4157b91acf8 unpack-trees: add trace2 regions\n 3: 8959d57abdd = 3: 8959d57abdd cache-tree: use trace2 in cache_tree_update()\n 4: 1d8a797ee26 = 4: 1d8a797ee26 cache-tree: trace regions for I/O\n 5: 2b2e70bb77c = 5: 2b2e70bb77c cache-tree: trace regions for prime_cache_tree\n -: ----------- > 6: 2d7b18c2e0b index-format: use 'cache tree' over 'cached tree'\n 6: 75b51483d3c ! 7: c5cffb5956e index-format: update preamble to cached tree extension\n @@ Metadata\n Author: Derrick Stolee \n \n ## Commit message ##\n - index-format: update preamble to cached tree extension\n + index-format: update preamble to cache tree extension\n \n - I had difficulty in my efforts to learn about the cached tree extension\n + I had difficulty in my efforts to learn about the cache tree extension\n based on the documentation and code because I had an incorrect\n assumption about how it behaved. This might be due to some ambiguity in\n the documentation, so this change modifies the beginning of the cached\n @@ Commit message\n \n 3. When exactly are \"new\" trees created?\n \n + Helped-by: Junio C Hamano \n Signed-off-by: Derrick Stolee \n \n ## Documentation/technical/index-format.txt ##\n @@ Documentation/technical/index-format.txt: Git index format\n \n - === Cached tree\n + === Cache tree\n \n -- Cached tree extension contains pre-computed hashes for trees that can\n +- Cache tree extension contains pre-computed hashes for trees that can\n - be derived from the index. It helps speed up tree object generation\n - from index for a new commit.\n -\n @@ Documentation/technical/index-format.txt: Git index format\n + Since the index does not record entries for directories, the cache\n + entries cannot describe tree objects that already exist in the object\n + database for regions of the index that are unchanged from an existing\n -+ commit. The cached tree extension stores a recursive tree structure that\n ++ commit. The cache tree extension stores a recursive tree structure that\n + describes the trees that already exist and completely match sections of\n + the cache entries. This speeds up tree object generation from the index\n + for a new commit by only computing the trees that are \"new\" to that\n -+ commit.\n ++ commit. It also assists when comparing the index to another tree, such\n ++ as `HEAD^{tree}`, since sections of the index can be skipped when a tree\n ++ comparison demonstrates equality.\n +\n + The recursive tree structure uses nodes that store a number of cache\n + entries, a list of subnodes, and an object ID (OID). The OID references\n -+ the exising tree for that node, if it is known to exist. The subnodes\n -+ correspond to subdirectories that themselves have cached tree nodes. The\n ++ the existing tree for that node, if it is known to exist. The subnodes\n ++ correspond to subdirectories that themselves have cache tree nodes. The\n + number of cache entries corresponds to the number of cache entries in\n + the index that describe paths within that tree's directory.\n +\n -+ Note that the path for a given tree is part of the parent node in-memory\n -+ but is part of the child in the file format. The root tree has an empty\n -+ string for its name and its name does not exist in-memory.\n ++ The extension tracks the full directory structure in the cache tree\n ++ extension, but this is generally smaller than the full cache entry list.\n +\n + When a path is updated in index, Git invalidates all nodes of the\n -+ recurisive cached tree corresponding to the parent directories of that\n ++ recursive cache tree corresponding to the parent directories of that\n + path. We store these tree nodes as being \"invalid\" by using \"-1\" as the\n -+ number of cache entries. To create trees corresponding to the current\n -+ index, Git only walks the invalid tree nodes and uses the cached OIDs\n -+ for the valid trees to construct new trees. In this way, Git only\n -+ constructs trees on the order of the number of changed paths (and their\n -+ depth in the working directory). This comes at a cost of tracking the\n -+ full directory structure in the cached tree extension, but this is\n -+ generally smaller than the full cache entry list in the index.\n ++ number of cache entries. Invalid nodes still store a span of index\n ++ entries, allowing Git to focus its efforts when reconstructing a full\n ++ cache tree.\n \n The signature for this extension is { 'T', 'R', 'E', 'E' }.\n \n 7: b2bb141a254 = 8: 97c06c80a85 index-format: discuss recursion of cached-tree better\n 8: 5298694786e = 9: 2532f5cc189 cache-tree: use ce_namelen() instead of strlen()\n 9: 72edd7bb427 = 10: 7c1c206a0bc cache-tree: speed up consecutive path comparisons\n\n-- \ngitgitgadget\n"},{"id":"413705","messageId":"4157b91acf8009ef2136c0856b6b61833d82873e.1610037131.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 02/10] unpack-trees: add trace2 regions","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:03Z","receivedAt":"2021-01-07T16:33:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe unpack_trees() method is quite complicated and its performance can\nchange dramatically depending on how it is used. We already have some\nperformance tracing regions, but they have not been updated to the\ntrace2 API. Do so now.\n\nWe already have trace2 regions in unpack_trees.c:clear_ce_flags(), which\nuses a linear scan through the index without recursing into trees.\n\nSigned-off-by: Derrick Stolee \n---\n unpack-trees.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 323280dd48b..af6e9b9c2fd 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -1580,6 +1580,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\tdie(\"unpack_trees takes at most %d trees\", MAX_UNPACK_TREES);\n \n \ttrace_performance_enter();\n+\ttrace2_region_enter(\"unpack_trees\", \"unpack_trees\", the_repository);\n+\n \tif (!core_apply_sparse_checkout || !o->update)\n \t\to->skip_sparse_checkout = 1;\n \tif (!o->skip_sparse_checkout && !o->pl) {\n@@ -1653,7 +1655,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n \t\t}\n \n \t\ttrace_performance_enter();\n+\t\ttrace2_region_enter(\"unpack_trees\", \"traverse_trees\", the_repository);\n \t\tret = traverse_trees(o->src_index, len, t, &info);\n+\t\ttrace2_region_leave(\"unpack_trees\", \"traverse_trees\", the_repository);\n \t\ttrace_performance_leave(\"traverse_trees\");\n \t\tif (ret < 0)\n \t\t\tgoto return_failed;\n@@ -1741,6 +1745,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options\n done:\n \tif (free_pattern_list)\n \t\tclear_pattern_list(&pl);\n+\ttrace2_region_leave(\"unpack_trees\", \"unpack_trees\", the_repository);\n \ttrace_performance_leave(\"unpack_trees\");\n \treturn ret;\n \n-- \ngitgitgadget\n\n"},{"id":"413706","messageId":"8959d57abddd620f4b597e4c43c5d2545c666e97.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 03/10] cache-tree: use trace2 in cache_tree_update()","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:04Z","receivedAt":"2021-01-07T16:33:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThis matches a trace_performance_enter()/trace_performance_leave() pair\nadded by 0d1ed59 (unpack-trees: add performance tracing, 2018-08-18).\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex a537a806c16..9efb6748662 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -442,7 +442,9 @@ int cache_tree_update(struct index_state *istate, int flags)\n \tif (i)\n \t\treturn i;\n \ttrace_performance_enter();\n+\ttrace2_region_enter(\"cache_tree\", \"update\", the_repository);\n \ti = update_one(it, cache, entries, \"\", 0, &skip, flags);\n+\ttrace2_region_leave(\"cache_tree\", \"update\", the_repository);\n \ttrace_performance_leave(\"cache_tree_update\");\n \tif (i < 0)\n \t\treturn i;\n-- \ngitgitgadget\n\n"},{"id":"413707","messageId":"1d8a797ee2650e8c815281b0c672301c7f24a724.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 04/10] cache-tree: trace regions for I/O","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:05Z","receivedAt":"2021-01-07T16:33:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAs we write or read the cached tree index extension, it can be good to\nisolate how much of the file I/O time is spent constructing this\nin-memory tree from the existing index or writing it out again to the\nnew index file. Use trace2 regions to indicate that we are spending time\non this operation.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 11 ++++++++++-\n 1 file changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 9efb6748662..45fb57b17f3 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -494,7 +494,9 @@ static void write_one(struct strbuf *buffer, struct cache_tree *it,\n \n void cache_tree_write(struct strbuf *sb, struct cache_tree *root)\n {\n+\ttrace2_region_enter(\"cache_tree\", \"write\", the_repository);\n \twrite_one(sb, root, \"\", 0);\n+\ttrace2_region_leave(\"cache_tree\", \"write\", the_repository);\n }\n \n static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)\n@@ -583,9 +585,16 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)\n \n struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)\n {\n+\tstruct cache_tree *result;\n+\n \tif (buffer[0])\n \t\treturn NULL; /* not the whole tree */\n-\treturn read_one(&buffer, &size);\n+\n+\ttrace2_region_enter(\"cache_tree\", \"read\", the_repository);\n+\tresult = read_one(&buffer, &size);\n+\ttrace2_region_leave(\"cache_tree\", \"read\", the_repository);\n+\n+\treturn result;\n }\n \n static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)\n-- \ngitgitgadget\n\n"},{"id":"413708","messageId":"2d7b18c2e0b351e98e687126fc067dc4fcd7a498.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 06/10] index-format: use 'cache tree' over 'cached tree'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:07Z","receivedAt":"2021-01-07T16:33:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe index has a \"cache tree\" extension. This corresponds to a\nsignificant API implemented in cache-tree.[ch]. However, there are a few\nplaces that refer to this erroneously as \"cached tree\". These are rare,\nbut notably the index-format.txt file itself makes this error.\n\nThe only other reference is in t7104-reset-hard.sh.\n\nReported-by: Junio C Hamano \nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/index-format.txt | 6 +++---\n t/t7104-reset-hard.sh | 2 +-\n 2 files changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex 69edf46c031..c71314731ec 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -26,7 +26,7 @@ Git index format\n Extensions are identified by signature. Optional extensions can\n be ignored if Git does not understand them.\n \n- Git currently supports cached tree and resolve undo extensions.\n+ Git currently supports cache tree and resolve undo extensions.\n \n 4-byte extension signature. If the first byte is 'A'..'Z' the\n extension is optional and can be ignored.\n@@ -136,9 +136,9 @@ Git index format\n \n == Extensions\n \n-=== Cached tree\n+=== Cache tree\n \n- Cached tree extension contains pre-computed hashes for trees that can\n+ Cache tree extension contains pre-computed hashes for trees that can\n be derived from the index. It helps speed up tree object generation\n from index for a new commit.\n \ndiff --git a/t/t7104-reset-hard.sh b/t/t7104-reset-hard.sh\nindex 16faa078137..7948ec392b3 100755\n--- a/t/t7104-reset-hard.sh\n+++ b/t/t7104-reset-hard.sh\n@@ -33,7 +33,7 @@ test_expect_success 'reset --hard should restore unmerged ones' '\n \n '\n \n-test_expect_success 'reset --hard did not corrupt index or cached-tree' '\n+test_expect_success 'reset --hard did not corrupt index or cache-tree' '\n \n \tT=$(git write-tree) &&\n \trm -f .git/index &&\n-- \ngitgitgadget\n\n"},{"id":"413709","messageId":"97c06c80a8543d29bf9390fc8ae5b73ae140c057.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 08/10] index-format: discuss recursion of cached-tree better","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:09Z","receivedAt":"2021-01-07T16:33:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe end of the cached tree index extension format trails off with\nellipses ever since 23fcc98 (doc: technical details about the index\nfile format, 2011-03-01). While an intuitive reader could gather what\nthis means, it could be better to use \"and so on\" instead.\n\nReally, this is only justified because I also wanted to point out that\nthe number of subtrees in the index format is used to determine when the\nrecursive depth-first-search stack should be \"popped.\" This should help\nto add clarity to the format.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/index-format.txt | 3 ++-\n 1 file changed, 2 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex 65dcfa570df..b633482b1bd 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -195,7 +195,8 @@ Git index format\n first entry represents the root level of the repository, followed by the\n first subtree--let's call this A--of the root level (with its name\n relative to the root level), followed by the first subtree of A (with\n- its name relative to A), ...\n+ its name relative to A), and so on. The specified number of subtrees\n+ indicates when the current level of the recursive stack is complete.\n \n === Resolve undo\n \n-- \ngitgitgadget\n\n"},{"id":"413710","messageId":"2532f5cc1898fa1652e828f26fb83c8b211a18f0.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 09/10] cache-tree: use ce_namelen() instead of strlen()","fromName":"René Scharfe via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:10Z","receivedAt":"2021-01-07T16:33:52Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= \n\nUse the name length field of cache entries instead of calculating its\nvalue anew.\n\nSigned-off-by: René Scharfe \nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 10 ++++++----\n 1 file changed, 6 insertions(+), 4 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 7da59b2aa07..4274de75bac 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,\n \t\t * the cache is sorted. Also path can appear only once,\n \t\t * which means conflicting one would immediately follow.\n \t\t */\n-\t\tconst char *this_name = cache[i]->name;\n-\t\tconst char *next_name = cache[i+1]->name;\n-\t\tint this_len = strlen(this_name);\n-\t\tif (this_len < strlen(next_name) &&\n+\t\tconst struct cache_entry *this_ce = cache[i];\n+\t\tconst struct cache_entry *next_ce = cache[i + 1];\n+\t\tconst char *this_name = this_ce->name;\n+\t\tconst char *next_name = next_ce->name;\n+\t\tint this_len = ce_namelen(this_ce);\n+\t\tif (this_len < ce_namelen(next_ce) &&\n \t\t strncmp(this_name, next_name, this_len) == 0 &&\n \t\t next_name[this_len] == '/') {\n \t\t\tif (10 < ++funny) {\n-- \ngitgitgadget\n\n"},{"id":"413711","messageId":"7c1c206a0bccd25842e49b282d64432d61e879d8.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 10/10] cache-tree: speed up consecutive path comparisons","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:11Z","receivedAt":"2021-01-07T16:33:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change reduced time spent in strlen() while comparing\nconsecutive paths in verify_cache(), but we can do better. The\nconditional checks the existence of a directory separator at the correct\nlocation, but only after doing a string comparison. Swap the order to be\nlogically equivalent but perform fewer string comparisons.\n\nTo test the effect on performance, I used a repository with over three\nmillion paths in the index. I then ran the following command on repeat:\n\n git -c index.threads=1 commit --amend --allow-empty --no-edit\n\nHere are the measurements over 10 runs after a 5-run warmup:\n\n Benchmark #1: v2.30.0\n Time (mean ± σ): 854.5 ms ± 18.2 ms\n Range (min … max): 825.0 ms … 892.8 ms\n\n Benchmark #2: Previous change\n Time (mean ± σ): 833.2 ms ± 10.3 ms\n Range (min … max): 815.8 ms … 849.7 ms\n\n Benchmark #3: This change\n Time (mean ± σ): 815.5 ms ± 18.1 ms\n Range (min … max): 795.4 ms … 849.5 ms\n\nThis change is 2% faster than the previous change and 5% faster than\nv2.30.0.\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 4274de75bac..3f1a8d4f1b7 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache,\n \t\tconst char *next_name = next_ce->name;\n \t\tint this_len = ce_namelen(this_ce);\n \t\tif (this_len < ce_namelen(next_ce) &&\n-\t\t strncmp(this_name, next_name, this_len) == 0 &&\n-\t\t next_name[this_len] == '/') {\n+\t\t next_name[this_len] == '/' &&\n+\t\t strncmp(this_name, next_name, this_len) == 0) {\n \t\t\tif (10 < ++funny) {\n \t\t\t\tfprintf(stderr, \"...\\n\");\n \t\t\t\tbreak;\n-- \ngitgitgadget\n"},{"id":"413712","messageId":"2b2e70bb77c8dafbf2cfedd9e68f834f02deb4a2.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 05/10] cache-tree: trace regions for prime_cache_tree","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:06Z","receivedAt":"2021-01-07T16:33:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nCommands such as \"git reset --hard\" rebuild the in-memory representation\nof the cached tree index extension by parsing tree objects starting at a\nknown root tree. The performance of this operation can vary widely\ndepending on the width and depth of the repository's working directory\nstructure. Measure the time in this operation using trace2 regions in\nprime_cache_tree().\n\nSigned-off-by: Derrick Stolee \n---\n cache-tree.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/cache-tree.c b/cache-tree.c\nindex 45fb57b17f3..7da59b2aa07 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -744,10 +744,13 @@ void prime_cache_tree(struct repository *r,\n \t\t struct index_state *istate,\n \t\t struct tree *tree)\n {\n+\ttrace2_region_enter(\"cache-tree\", \"prime_cache_tree\", the_repository);\n \tcache_tree_free(&istate->cache_tree);\n \tistate->cache_tree = cache_tree();\n+\n \tprime_cache_tree_rec(r, istate->cache_tree, tree);\n \tistate->cache_changed |= CACHE_TREE_CHANGED;\n+\ttrace2_region_leave(\"cache-tree\", \"prime_cache_tree\", the_repository);\n }\n \n /*\n-- \ngitgitgadget\n\n"},{"id":"413713","messageId":"c5cffb5956ee2f8e55210b64b6686c4cd1c839b6.1610037132.git.gitgitgadget@gmail.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"[PATCH v3 07/10] index-format: update preamble to cache tree extension","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-01-07T16:32:08Z","receivedAt":"2021-01-07T16:33:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nI had difficulty in my efforts to learn about the cache tree extension\nbased on the documentation and code because I had an incorrect\nassumption about how it behaved. This might be due to some ambiguity in\nthe documentation, so this change modifies the beginning of the cached\ntree format by expanding the description of the feature.\n\nMy hope is that this documentation clarifies a few things:\n\n1. There is an in-memory recursive tree structure that is constructed\n from the extension data. This structure has a few differences, such\n as where the name is stored.\n\n2. What does it mean for an entry to be invalid?\n\n3. When exactly are \"new\" trees created?\n\nHelped-by: Junio C Hamano \nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/index-format.txt | 33 +++++++++++++++++++-----\n 1 file changed, 27 insertions(+), 6 deletions(-)\n\ndiff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt\nindex c71314731ec..65dcfa570df 100644\n--- a/Documentation/technical/index-format.txt\n+++ b/Documentation/technical/index-format.txt\n@@ -138,12 +138,33 @@ Git index format\n \n === Cache tree\n \n- Cache tree extension contains pre-computed hashes for trees that can\n- be derived from the index. It helps speed up tree object generation\n- from index for a new commit.\n-\n- When a path is updated in index, the path must be invalidated and\n- removed from tree cache.\n+ Since the index does not record entries for directories, the cache\n+ entries cannot describe tree objects that already exist in the object\n+ database for regions of the index that are unchanged from an existing\n+ commit. The cache tree extension stores a recursive tree structure that\n+ describes the trees that already exist and completely match sections of\n+ the cache entries. This speeds up tree object generation from the index\n+ for a new commit by only computing the trees that are \"new\" to that\n+ commit. It also assists when comparing the index to another tree, such\n+ as `HEAD^{tree}`, since sections of the index can be skipped when a tree\n+ comparison demonstrates equality.\n+\n+ The recursive tree structure uses nodes that store a number of cache\n+ entries, a list of subnodes, and an object ID (OID). The OID references\n+ the existing tree for that node, if it is known to exist. The subnodes\n+ correspond to subdirectories that themselves have cache tree nodes. The\n+ number of cache entries corresponds to the number of cache entries in\n+ the index that describe paths within that tree's directory.\n+\n+ The extension tracks the full directory structure in the cache tree\n+ extension, but this is generally smaller than the full cache entry list.\n+\n+ When a path is updated in index, Git invalidates all nodes of the\n+ recursive cache tree corresponding to the parent directories of that\n+ path. We store these tree nodes as being \"invalid\" by using \"-1\" as the\n+ number of cache entries. Invalid nodes still store a span of index\n+ entries, allowing Git to focus its efforts when reconstructing a full\n+ cache tree.\n \n The signature for this extension is { 'T', 'R', 'E', 'E' }.\n \n-- \ngitgitgadget\n\n"},{"id":"413741","messageId":"xmqqv9c8ld5h.fsf@gitster.c.googlers.com","threadId":"54906","inReplyTo":"5a1a51c1-7ada-6f66-a6d0-2fc01303d334@gmail.com","subject":"Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-07T20:12:26Z","receivedAt":"2021-01-07T20:13:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> We later found out that we rather often compare the index against\n>> the tree of HEAD (think: \"git status\"), and diff-lib.c::diff_cache()\n>> does take advantage of the fact that an entire directory can be\n>> skipped if the tree object taken from the HEAD side exactly matches\n>> the tree recorded for the subdirectory in the cache tree extension.\n>\n> I need to read more about this. traverse_by_cache_tree() seems to\n> be a good place to start. Thanks.\n\nAh, that one I forgot about.\n\nWhat I had in mind was a different optimization that is far more\naggressive in unpack-trees.c::unpack_callback(); look for a comment\nthat begins with \"Everything under the name matches\". The block\nallows us to skip an entire subdirectory hierarchy.\n\n"},{"id":"413745","messageId":"xmqq8s94l9qs.fsf@gitster.c.googlers.com","threadId":"54906","inReplyTo":"5a1a51c1-7ada-6f66-a6d0-2fc01303d334@gmail.com","subject":"Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-07T21:26:03Z","receivedAt":"2021-01-07T21:27:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> We later found out that we rather often compare the index against\n>> the tree of HEAD (think: \"git status\"), and diff-lib.c::diff_cache()\n>> does take advantage of the fact that an entire directory can be\n>> skipped if the tree object taken from the HEAD side exactly matches\n>> the tree recorded for the subdirectory in the cache tree extension.\n>\n> I need to read more about this. traverse_by_cache_tree() seems to\n> be a good place to start. Thanks.\n\nAh, that one I forgot about.\n\nWhat I had in mind was a different optimization that is far more\naggressive in unpack-trees.c::unpack_callback(); look for a comment\nthat begins with \"Everything under the name matches\". The block\nallows us to skip an entire subdirectory hierarchy.\n\n"},{"id":"414492","messageId":"xmqqr1mlpdv4.fsf@gitster.c.googlers.com","threadId":"54906","inReplyTo":"pull.829.v3.git.1610037131.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 00/10] Cleanups around index operations","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-16T06:58:23Z","receivedAt":"2021-01-16T07:02:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> I've taken a professional interest in the index lately, and I've been trying\n> mostly to learn about it and measure different operations. Along the way,\n> I've seen some possible improvements in documentation, behavior, and\n> tracing.\n>\n> This series collects most of my thoughts so far, including:\n>\n> 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches\n> 1-5).\n> 2. Update documentation about the cached tree extension (Patches 6-7).\n> 3. Improved the performance of verify_cache() (Patches 8-9).\n>\n> Thanks, -Stolee\n\nI've given all the patches in the series another reading, and found\nthem to be nicely done.\n\nLet's merge it down to 'next'.\n\nThanks.\n"}]}