Cleanups around index operations

I've taken a professional interest in the index lately, and I've been trying mostly to learn about it and measure different operations. Along the way, I've seen some possible improvements in documentation, behavior, and tracing.

This series collects most of my thoughts so far, including:

1. Adding extra trace2 regions and statistics (similar to [1]) (Patches

    1-5).

2. Update documentation about the cached tree extension (Patches 6-7).
3. Removing an unnecessary loop from verify_cache() (Patch 8).

Thanks, -Stolee

[1]
https://lore.kernel.org/git/[email protected]/

Derrick Stolee (8):
tree-walk: report recursion counts
unpack-trees: add trace2 regions
cache-tree: use trace2 in cache_tree_update()
cache-tree: trace regions for I/O
cache-tree: trace regions for prime_cache_tree
index-format: update preamble to cached tree extension
index-format: discuss recursion of cached-tree better
cache-tree: avoid path comparison loop when silent

 Documentation/technical/index-format.txt | 39 +++++++++++++++++++-----
 cache-tree.c                             | 25 +++++++++++++--
 tree-walk.c                              | 33 ++++++++++++++++++++
 unpack-trees.c                           |  6 +++-
 4 files changed, 92 insertions(+), 11 deletions(-)

base-commit: 71ca53e8125e36efbda17293c50027d31681a41f
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-829%2Fderrickstolee%2Fcache-tree%2Fbasics-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-829/derrickstolee/cache-tree/basics-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/829

gitgitgadget

From: Derrick Stolee <[email protected]>

The traverse_trees() method recusively walks through trees, but also prunes the tree-walk based on a callback. Some callers, such as unpack_trees(), are quite complicated and can have wildly different performance between two different commands.

Create constants that count these values and then report the results at the end of a process. These counts are cumulative across multiple "root" instances of traverse_trees(), but they provide reproducible values for demonstrating improvements to the pruning algorithm when possible.

---
 tree-walk.c    | 33 +++++++++++++++++++++++++++++++++
 unpack-trees.c |  1 -
 2 files changed, 33 insertions(+), 1 deletion(-)

index 0160294712b..2d6226d5f18 100644
@@ -4,6 +4,7 @@
 #include "object-store.h"
 #include "tree.h"
 #include "pathspec.h"
+#include "json-writer.h"
 
 static const char *get_mode(const char *str, unsigned int *modep)
 {

@@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
 	return 1;
 }
 
+static int traverse_trees_atexit_registered;
+static int traverse_trees_count;
+static int traverse_trees_cur_depth;
+static int traverse_trees_max_depth;
+
+static void trace2_traverse_trees_statistics_atexit(void)
+{
+	struct json_writer jw = JSON_WRITER_INIT;
+
+	jw_object_begin(&jw, 0);
+	jw_object_intmax(&jw, "traverse_trees_count", traverse_trees_count);
+	jw_object_intmax(&jw, "traverse_trees_max_depth", traverse_trees_max_depth);
+	jw_end(&jw);
+
+	trace2_data_json("traverse_trees", the_repository, "statistics", &jw);
+
+	jw_release(&jw);
+}
+
 void setup_traverse_info(struct traverse_info *info, const char *base)
 {
 	size_t pathlen = strlen(base);

@@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)
 	info->namelen = pathlen;
 	if (pathlen)
 		info->prev = &dummy;
+
+	if (trace2_is_enabled() && !traverse_trees_atexit_registered) {
+		atexit(trace2_traverse_trees_statistics_atexit);
+		traverse_trees_atexit_registered = 1;
+	}
 }
 
 char *make_traverse_path(char *path, size_t pathlen,

@@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,
 	int interesting = 1;
 	char *traverse_path;
 
+	traverse_trees_count++;
+	traverse_trees_cur_depth++;
+
+	if (traverse_trees_cur_depth > traverse_trees_max_depth)
+		traverse_trees_max_depth = traverse_trees_cur_depth;
+
 	if (n >= ARRAY_SIZE(entry))
 		BUG("traverse_trees() called with too many trees (%d)", n);
 

@@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,
 	free(traverse_path);
 	info->traverse_path = NULL;
 	strbuf_release(&base);
+
+	traverse_trees_cur_depth--;
 	return error;
 }
 

index 323280dd48b..02f484604ac 100644
@@ -1559,7 +1559,6 @@ static void populate_from_existing_patterns(struct unpack_trees_options *o,
 	free(sparse);
 }
 
-
 static int verify_absent(const struct cache_entry *,
 			 enum unpack_trees_error_types,
 			 struct unpack_trees_options *);

gitgitgadget

recursively -- you're missing the second 'r'.

Not sure it belongs in the commit message, but you do have me curious what you're digging in to...

From the subject, you are changing tree-walk. unpack-trees depends on tree-walk, but why is something exposed to it with this kind of change? Maybe I'll see when I get to it.

Seems like a good change other than a few small nits. I don't know the json_writer/trace2 stuff, so you might want another reviewer, but it's only a few lines and seems relatively straightforward.

Thanks.

I'm still testing whether my idea will work out. Hopefully soon. ;)

Oops. I originally reported the stats at the end of unpack_trees(), but it seems I didn't completely back out that change.

I guess I could have pointed out that this change is modeled after a similar statistics reporting in 42e50e78 (revision.c: add trace2 stats around Bloom filter usage, 2020-04-06).

It should be dropped! Thanks.

I should point out that an easy way to test this locally is to run

GIT_TRACE2_PERF=1 git read-tree -mu HEAD

to trigger a full recursive walk. The output JSON payload looks like this:

statistics:{"traverse_trees_count":203,"traverse_trees_max_depth":7}

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

The unpack_trees() method is quite complicated and its performance can change dramatically depending on how it is used. We already have some performance tracing regions, but they have not been updated to the trace2 API. Do so now.

We already have trace2 regions in unpack_trees.c:clear_ce_flags(), which uses a linear scan through the index without recursing into trees.

---
 unpack-trees.c | 5 +++++
 1 file changed, 5 insertions(+)

index 02f484604ac..7dbd006ac56 100644
@@ -1579,6 +1579,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES);
 
 	trace_performance_enter();
+	trace2_region_enter("unpack_trees", "unpack_trees", the_repository);
+
 	if (!core_apply_sparse_checkout || !o->update)
 		o->skip_sparse_checkout = 1;
 	if (!o->skip_sparse_checkout && !o->pl) {

@@ -1652,7 +1654,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		}
 
 		trace_performance_enter();
+		trace2_region_enter("unpack_trees", "traverse_trees", the_repository);
 		ret = traverse_trees(o->src_index, len, t, &info);
+		trace2_region_leave("unpack_trees", "traverse_trees", the_repository);
 		trace_performance_leave("traverse_trees");
 		if (ret < 0)
 			goto return_failed;

@@ -1740,6 +1744,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 done:
 	if (free_pattern_list)
 		clear_pattern_list(&pl);
+	trace2_region_leave("unpack_trees", "unpack_trees", the_repository);
 	trace_performance_leave("unpack_trees");
 	return ret;
 

gitgitgadget

Somewhat of a curious side comment: Any idea at what scale the perf issues show up? Or are you still digging into that?

Seems simple and straightforward, and I like having more trace2 measurements since I used it so much in merge-ort.

From: Derrick Stolee <[email protected]>

This matches a trace_performance_enter()/trace_performance_leave() pair added by 0d1ed59 (unpack-trees: add performance tracing, 2018-08-18).

---
 cache-tree.c | 2 ++
 1 file changed, 2 insertions(+)

index a537a806c16..9efb6748662 100644
@@ -442,7 +442,9 @@ int cache_tree_update(struct index_state *istate, int flags)
 	if (i)
 		return i;
 	trace_performance_enter();
+	trace2_region_enter("cache_tree", "update", the_repository);
 	i = update_one(it, cache, entries, "", 0, &skip, flags);
+	trace2_region_leave("cache_tree", "update", the_repository);
 	trace_performance_leave("cache_tree_update");
 	if (i < 0)
 		return i;

gitgitgadget

From: Derrick Stolee <[email protected]>

As we write or read the cached tree index extension, it can be good to isolate how much of the file I/O time is spent constructing this in-memory tree from the existing index or writing it out again to the new index file. Use trace2 regions to indicate that we are spending time on this operation.

---
 cache-tree.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

index 9efb6748662..45fb57b17f3 100644
@@ -494,7 +494,9 @@ static void write_one(struct strbuf *buffer, struct cache_tree *it,
 
 void cache_tree_write(struct strbuf *sb, struct cache_tree *root)
 {
+	trace2_region_enter("cache_tree", "write", the_repository);
 	write_one(sb, root, "", 0);
+	trace2_region_leave("cache_tree", "write", the_repository);
 }
 
 static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)

@@ -583,9 +585,16 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 
 struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
 {
+	struct cache_tree *result;
+
 	if (buffer[0])
 		return NULL; /* not the whole tree */
-	return read_one(&buffer, &size);
+
+	trace2_region_enter("cache_tree", "read", the_repository);
+	result = read_one(&buffer, &size);
+	trace2_region_leave("cache_tree", "read", the_repository);
+
+	return result;
 }
 
 static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)

gitgitgadget

From: Derrick Stolee <[email protected]>

Commands such as "git reset --hard" rebuild the in-memory representation of the cached tree index extension by parsing tree objects starting at a known root tree. The performance of this operation can vary widely depending on the width and depth of the repository's working directory structure. Measure the time in this operation using trace2 regions in prime_cache_tree().

---
 cache-tree.c | 3 +++
 1 file changed, 3 insertions(+)

index 45fb57b17f3..f135bb77af5 100644
@@ -746,7 +746,10 @@ void prime_cache_tree(struct repository *r,
 {
 	cache_tree_free(&istate->cache_tree);
 	istate->cache_tree = cache_tree();
+
+	trace2_region_enter("cache-tree", "prime_cache_tree", the_repository);
 	prime_cache_tree_rec(r, istate->cache_tree, tree);
+	trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);
 	istate->cache_changed |= CACHE_TREE_CHANGED;
 }
 

gitgitgadget

I guess my focus was on creating changes around the "bulk" of the operation, keeping the region enter/leave pair close together. But perhaps enclosing the full block will be better for full coverage in case this method became more complicated (but not within prime_cache_tree_rec()).

Thanks,
-Stolee

From: Derrick Stolee <[email protected]>

I had difficulty in my efforts to learn about the cached tree extension based on the documentation and code because I had an incorrect assumption about how it behaved. This might be due to some ambiguity in the documentation, so this change modifies the beginning of the cached tree format by expanding the description of the feature.

My hope is that this documentation clarifies a few things:

1. There is an in-memory recursive tree structure that is constructed from the extension data. This structure has a few differences, such as where the name is stored.

2. What does it mean for an entry to be invalid?

3. When exactly are "new" trees created?

---
 Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----
 1 file changed, 30 insertions(+), 6 deletions(-)

index 69edf46c031..c614e136e24 100644
@@ -138,12 +138,36 @@ Git index format
 
 === Cached tree
 
-  Cached tree extension contains pre-computed hashes for trees that can
-  be derived from the index. It helps speed up tree object generation
-  from index for a new commit.
-
-  When a path is updated in index, the path must be invalidated and
-  removed from tree cache.
+  Since the index does not record entries for directories, the cache
+  entries cannot describe tree objects that already exist in the object
+  database for regions of the index that are unchanged from an existing
+  commit. The cached tree extension stores a recursive tree structure that
+  describes the trees that already exist and completely match sections of
+  the cache entries. This speeds up tree object generation from the index
+  for a new commit by only computing the trees that are "new" to that
+  commit.
+
+  The recursive tree structure uses nodes that store a number of cache
+  entries, a list of subnodes, and an object ID (OID). The OID references
+  the exising tree for that node, if it is known to exist. The subnodes
+  correspond to subdirectories that themselves have cached tree nodes. The
+  number of cache entries corresponds to the number of cache entries in
+  the index that describe paths within that tree's directory.
+
+  Note that the path for a given tree is part of the parent node in-memory
+  but is part of the child in the file format. The root tree has an empty
+  string for its name and its name does not exist in-memory.
+
+  When a path is updated in index, Git invalidates all nodes of the
+  recurisive cached tree corresponding to the parent directories of that
+  path. We store these tree nodes as being "invalid" by using "-1" as the
+  number of cache entries. To create trees corresponding to the current
+  index, Git only walks the invalid tree nodes and uses the cached OIDs
+  for the valid trees to construct new trees. In this way, Git only
+  constructs trees on the order of the number of changed paths (and their
+  depth in the working directory). This comes at a cost of tracking the
+  full directory structure in the cached tree extension, but this is
+  generally smaller than the full cache entry list in the index.
 
   The signature for this extension is { 'T', 'R', 'E', 'E' }.
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The end of the cached tree index extension format trails off with ellipses ever since 23fcc98 (doc: technical details about the index file format, 2011-03-01). While an intuitive reader could gather what this means, it could be better to use "and so on" instead.

Really, this is only justified because I also wanted to point out that the number of subtrees in the index format is used to determine when the recursive depth-first-search stack should be "popped." This should help to add clarity to the format.

---
 Documentation/technical/index-format.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index c614e136e24..2ebe88b9d46 100644
@@ -198,7 +198,8 @@ Git index format
   first entry represents the root level of the repository, followed by the
   first subtree--let's call this A--of the root level (with its name
   relative to the root level), followed by the first subtree of A (with
-  its name relative to A), ...
+  its name relative to A), and so on. The specified number of subtrees
+  indicates when the current level of the recursive stack is complete.
 
 === Resolve undo
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The verify_cache() method is used both for debugging issues with the cached tree extension but also to avoid using the extension when there are unmerged entries. It also checks for cache entries out of order with respect to file-versus-directory sorting.

In 996277c (Refactor cache_tree_update idiom from commit, 2011-12-06), the silent option was added to remove the progress indicators from the initial loop looking for unmerged entries. This was changed to be a flag in e859c69 (cache-tree: update API to take abitrary flags, 2012-01-16).

In both cases, the silent option is ignored for the second loop that checks for file-versus-directory sorting. It must be that this loop is intended only for debugging purposes and is not actually helpful in practice.

Since verify_cache() is called in cache_tree_update(), which is run during 'git commit', we could speed up 'git commit' operations by not iterating through this loop another time. Of course, noticing this loop requires an incredibly large index.

To get a measurable difference, I needed to run this test on the Microsoft Office monorepo, which has over three million entries in its index. I used 'git commit --amend --no-edit' as my command and saw the performance go from 752ms to 739ms with this change.

---
 cache-tree.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

index f135bb77af5..c6c084463bd 100644
@@ -175,10 +175,15 @@ static int verify_cache(struct cache_entry **cache,
 	if (funny)
 		return -1;
 
-	/* Also verify that the cache does not have path and path/file
+	/*
+	 * Also verify that the cache does not have path and path/file
 	 * at the same time.  At this point we know the cache has only
-	 * stage 0 entries.
+	 * stage 0 entries. In silent mode, we do not want these messages,
+	 * and they should not exist unless a bug was introduced along
+	 * the way.
 	 */
+	if (silent)
+		return 0;
 	funny = 0;
 	for (i = 0; i < entries - 1; i++) {
 		/* path/file always comes after path because of the way

gitgitgadget

Looking through that code, I come to the same conclusion, though it might be nice to have Junio confirm (and to explain the "if (10 <
++funny)" section; did that help debugging too?). The second part of
the loop was part of his initial commit adding the cache-tree extension in commit 749864627c ("Add cache-tree.", 2006-04-23)

Nice catch; I always appreciate when we can speed up a section of code by just not running it. :-)

Change seems simple enough. Thanks for adding the comment explaining the early return.

This is not about debugging our implementation. The verification was done to protect against the on-disk index file left by broken implementations of other people. Either JGit or Dulwich (I do not recall which one) used to have such a broken sort long time ago, IIRC, and the thing is, a broken implementation can be internally consistent.

I do not think we've heard problem reports discovered by this check about other peoples' broken implementation, but a chicken-and-egg is certainly in action here. The check would have caught any new and broken implementation of Git before it got released to the wild to cause harm and that is probably we haven't heard.

Thanks for the additional context. I think the performance
enhancements in v2 are enough to satisfy me for now without completely removing the functionality.

Thanks,
-Stolee

Am 30.12.20 um 20:26 schrieb Derrick Stolee via GitGitGadget:

So you're saying that the directory/file conflict check not honoring the WRITE_TREE_SILENT flag would have been noticed as a bug and therefore doesn't happen?

I'm not sure I can follow that logic. I don't know how important that check is, how often it found a conflict and how likely such a find is overlooked or ignored, but disabling a check in silent mode that affects the return code instead of only suppressing its messages seems risky.

If we are sure that the check cannot trigger then we should remove it. If we are not so sure, but a conflict would be Git's fault (and not the user's) then we should always do the check and BUG out. And otherwise we should keep it.

Could you please check the performance impact of the following code simplification?

index a537a806c1..1105cfe6b7 100644
@@ -187,10 +187,8 @@ static int verify_cache(struct cache_entry **cache,
 		 */
 		const char *this_name = cache[i]->name;
 		const char *next_name = cache[i+1]->name;
-		int this_len = strlen(this_name);
-		if (this_len < strlen(next_name) &&
-		    strncmp(this_name, next_name, this_len) == 0 &&
-		    next_name[this_len] == '/') {
+		const char *p;
+		if (skip_prefix(next_name, this_name, &p) && *p == '/') {
 			if (10 < ++funny) {
 				fprintf(stderr, "...\n");
 				break;

I think this method was originally designed for debugging issues with the index, and it still serves that purpose when someone is working on it. The check for out-of-order directory/file conflicts probably exists only for that case.

However, this method also got repurposed to (silently) check for the real scenario of unmerged entries. Perhaps it would be better to split these into two cases and move the silent case into a new method, "has_unmerged_entries()".

Thank you for sending this. I started comparing the performance and discovered that the performance difference I had measured before was NOT consistent! I went back and debugged and found that 'git commit' doesn't actually pass the silent flag, and my performance tests were skewed by the filesystem cache. (A warmup of 3 runs was not sufficient to get consistent numbers, it seemed. Perhaps the threaded index reads are too inconsistent.)

index c6c084463b..a076e7cec5 100644
@@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,
 {
        int i, funny;
        int silent = flags & WRITE_TREE_SILENT;
+       const char *this_name;
+       size_t this_len;
 
        /* Verify that the tree is merged */
        funny = 0;

@@ -182,18 +184,21 @@ static int verify_cache(struct cache_entry **cache,
         * and they should not exist unless a bug was introduced along
         * the way.
         */
-       if (silent)
-               return 0;
        funny = 0;
-       for (i = 0; i < entries - 1; i++) {
+
+       if (!entries)
+               return 0;
+       this_name = cache[0]->name;
+       this_len = strlen(this_name);
+
+       for (i = 1; i < entries; i++) {
                /* path/file always comes after path because of the way
                 * the cache is sorted.  Also path can appear only once,
                 * which means conflicting one would immediately follow.
                 */
-               const char *this_name = cache[i]->name;
-               const char *next_name = cache[i+1]->name;
-               int this_len = strlen(this_name);
-               if (this_len < strlen(next_name) &&
+               const char *next_name = cache[i]->name;
+               size_t next_len = strlen(next_name);
+               if (this_len < next_len &&
                    strncmp(this_name, next_name, this_len) == 0 &&
                    next_name[this_len] == '/') {
                        if (10 < ++funny) {

@@ -203,6 +208,8 @@ static int verify_cache(struct cache_entry **cache,
                        fprintf(stderr, "You have both %s and %s\n",
                                this_name, next_name);
                }
+               this_name = next_name;
+               this_len = next_len;
        }
        if (funny)
                return -1;

	git -c index.threads=1 commit --amend --allow-empty --no-edit

    Time (mean ± σ):     856.6 ms ±  18.0 ms    [User: 807.9 ms, System: 198.4 ms]
    Range (min … max):   832.1 ms … 882.2 ms    10 runs

    Time (mean ± σ):     805.5 ms ±  15.8 ms    [User: 758.0 ms, System: 197.1 ms]
    Range (min … max):   783.4 ms … 835.2 ms    10 runs

    Time (mean ± σ):     855.6 ms ±  14.1 ms    [User: 804.5 ms, System: 194.6 ms]
    Range (min … max):   835.9 ms … 875.2 ms    10 runs

    Time (mean ± σ):     834.1 ms ±  18.0 ms    [User: 786.6 ms, System: 196.7 ms]
    Range (min … max):   803.5 ms … 860.4 ms    10 runs 

		if (this_len < next_len &&
		    strncmp(this_name, next_name, this_len) == 0 &&
		    next_name[this_len] == '/') {

    Time (mean ± σ):     877.3 ms ±  16.1 ms    [User: 839.1 ms, System: 187.5 ms]
    Range (min … max):   847.7 ms … 900.4 ms    10 runs

Am 31.12.20 um 17:46 schrieb Derrick Stolee:

Thanks for checking! I was expecting skip_prefix to be faster, because it stops as soon as it reaches a non-matching character, while strlen has to always walk to the end. But consecutive entries of a sorted list of paths can share long prefixes, in particular if there are long directory names and directories contain lots of files.

   extern size_t strlen (const char *__s)
        __THROW __attribute_pure__ __nonnull ((1));

That's the original order there, but I get it. The trailing slash has only a low probability of being present, so in the common case the strncmp call can be skipped. And I guess that check is easier to handle for the branch predictor as well.

Since we know the length of both strings we can use memcmp instead of strncmp. It can compare words instead of bytes, so I'd expect it to be faster. Checking the slash first should make that difference moot, though, as it probably eliminates most of the strncmp calls anyway.

René

Use the name length field of cache entries instead of calculating its value anew.

---
Not sure why it took me so long to spot this.. o_O

 cache-tree.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

index a537a806c1..57cacab195 100644
@@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,
 		 * the cache is sorted.  Also path can appear only once,
 		 * which means conflicting one would immediately follow.
 		 */
-		const char *this_name = cache[i]->name;
-		const char *next_name = cache[i+1]->name;
-		int this_len = strlen(this_name);
-		if (this_len < strlen(next_name) &&
+		const struct cache_entry *this_ce = cache[i];
+		const struct cache_entry *next_ce = cache[i + 1];
+		const char *this_name = this_ce->name;
+		const char *next_name = next_ce->name;
+		int this_len = ce_namelen(this_ce);
+		if (this_len < ce_namelen(next_ce) &&
 		    strncmp(this_name, next_name, this_len) == 0 &&
 		    next_name[this_len] == '/') {
 			if (10 < ++funny) {

--
2.30.0

Thanks! I didn't know about this macro.

-Stolee

  git -c index.threads=1 commit --amend --allow-empty --no-edit

    Time (mean ± σ):     854.5 ms ±  18.2 ms
    Range (min … max):   825.0 ms … 892.8 ms

    Time (mean ± σ):     833.2 ms ±  10.3 ms
    Range (min … max):   815.8 ms … 849.7 ms

    Time (mean ± σ):     815.5 ms ±  18.1 ms
    Range (min … max):   795.4 ms … 849.5 ms

---
 cache-tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index 57cacab195..6eaef21145 100644
@@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache,
 		const char *next_name = next_ce->name;
 		int this_len = ce_namelen(this_ce);
 		if (this_len < ce_namelen(next_ce) &&
-		    strncmp(this_name, next_name, this_len) == 0 &&
-		    next_name[this_len] == '/') {
+		    next_name[this_len] == '/' &&
+		    strncmp(this_name, next_name, this_len) == 0) {
 			if (10 < ++funny) {
 				fprintf(stderr, "...\n");
 				break;

v2.30.0

That probably is because this does not cause behaviour change.

It used to be that use of ce_namelen() was more important in learning the length of the string before 7a51ed66 (Make on-disk index representation separate from in-core one, 2008-01-14) and 7fec10b7 (index: be careful when handling long names, 2008-01-18). The on-disk field to store the name length has only 12 bits, and before b60e188c (Strip namelen out of ce_flags into a ce_namelen field, 2012-07-11), the convention to learn the length of the name of an in-core cache entry was to see the field and then if it fully occupies the full 12-bit field, ask the name string itself its length with strlen().

These days, ce->namelen is a separate field that always gives the full length after the on-disk index is read, so with this change, you won't be running strlen() in this part of the function even with an entry with a long pathname.

Am 31.12.20 um 17:46 schrieb Derrick Stolee:

OK. It *is* suspicious that the test suite doesn't exercise the check done by that second loop. Removing it completely would rob us of so many ways to optimize it, though. ;-)

René

The series seems pretty simple and clean to me. As I mentioned on patch 6, though, I don't know much about the cache-tree extension myself (I show up in blame/log due to moving a function there with just some slight tweaks), so it'd be nice if someone who does can take a look at the documentation added in patch 6.

Thanks for the quick review. And I've CC'd Junio since I forgot that GitGitGadget no longer auto-CCs him.

Thanks,
-Stolee

I've taken a professional interest in the index lately, and I've been trying mostly to learn about it and measure different operations. Along the way, I've seen some possible improvements in documentation, behavior, and tracing.

This series collects most of my thoughts so far, including:

1. Adding extra trace2 regions and statistics (similar to [1]) (Patches

    1-5).

2. Update documentation about the cached tree extension (Patches 6-7).
3. Improved the performance of verify_cache() (Patches 8-9).

Thanks, -Stolee

[1]
https://lore.kernel.org/git/[email protected]/

UPDATES IN V2
=============

* Instead of completely dropping the second loop in verify_cache(), improve the performance. I include René's patch (unaltered except for my sign-off) in this series for clarity.

* Fixed the unnecessary whitespace change in patch 1. Updated the commit message to refer to a similar effort in changed-path Bloom filters.

* The range enter/leave block in patch 5 now spans the entire method.

Derrick Stolee (8):
tree-walk: report recursion counts
unpack-trees: add trace2 regions
cache-tree: use trace2 in cache_tree_update()
cache-tree: trace regions for I/O
cache-tree: trace regions for prime_cache_tree
index-format: update preamble to cached tree extension
index-format: discuss recursion of cached-tree better
cache-tree: speed up consecutive path comparisons

René Scharfe (1):
cache-tree: use ce_namelen() instead of strlen()

 Documentation/technical/index-format.txt | 39 +++++++++++++++++++-----
 cache-tree.c                             | 30 +++++++++++++-----
 tree-walk.c                              | 33 ++++++++++++++++++++
 unpack-trees.c                           |  5 +++
 4 files changed, 93 insertions(+), 14 deletions(-)

base-commit: 71ca53e8125e36efbda17293c50027d31681a41f
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-829%2Fderrickstolee%2Fcache-tree%2Fbasics-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-829/derrickstolee/cache-tree/basics-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/829

Range-diff vs v1:

1: f727880add6 ! 1: 0e500c86f39 tree-walk: report recursion counts
@@ Metadata
## Commit message ##
tree-walk: report recursion counts

- The traverse_trees() method recusively walks through trees, but also
+ The traverse_trees() method recursively walks through trees, but also
prunes the tree-walk based on a callback. Some callers, such as unpack_trees(), are quite complicated and can have wildly different performance between two different commands.
@@ Commit message
instances of traverse_trees(), but they provide reproducible values for demonstrating improvements to the pruning algorithm when possible.

+ This change is modeled after a similar statistics reporting in 42e50e78
+ (revision.c: add trace2 stats around Bloom filter usage, 2020-04-06).
+

## tree-walk.c ##
@@ tree-walk.c: int traverse_trees(struct index_state *istate,
return error;
}

-
- ## unpack-trees.c ##
-@@ unpack-trees.c: static void populate_from_existing_patterns(struct unpack_trees_options *o,
- free(sparse);
- }
-
--
- static int verify_absent(const struct cache_entry *,
- enum unpack_trees_error_types,
- struct unpack_trees_options *);

  2:  6923e6211aa =  2:  4157b91acf8 unpack-trees: add trace2 regions
  3:  802718084a7 =  3:  8959d57abdd cache-tree: use trace2 in cache_tree_update()
  4:  65feaa497b2 =  4:  1d8a797ee26 cache-tree: trace regions for I/O
  5:  5d1c9c8a356 !  5:  2b2e70bb77c cache-tree: trace regions for prime_cache_tree
     @@ Commit message
      
       ## cache-tree.c ##
      @@ cache-tree.c: void prime_cache_tree(struct repository *r,
     + 		      struct index_state *istate,
     + 		      struct tree *tree)
       {
     ++	trace2_region_enter("cache-tree", "prime_cache_tree", the_repository);
       	cache_tree_free(&istate->cache_tree);
       	istate->cache_tree = cache_tree();
      +
     -+	trace2_region_enter("cache-tree", "prime_cache_tree", the_repository);
       	prime_cache_tree_rec(r, istate->cache_tree, tree);
     -+	trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);
       	istate->cache_changed |= CACHE_TREE_CHANGED;
     ++	trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);
       }
       
     + /*
  6:  fb9d5468184 =  6:  75b51483d3c index-format: update preamble to cached tree extension
  7:  65fb9f72251 =  7:  b2bb141a254 index-format: discuss recursion of cached-tree better
  8:  20ea7050324 <  -:  ----------- cache-tree: avoid path comparison loop when silent
  -:  ----------- >  8:  5298694786e cache-tree: use ce_namelen() instead of strlen()
  -:  ----------- >  9:  72edd7bb427 cache-tree: speed up consecutive path comparisons

gitgitgadget

From: Derrick Stolee <[email protected]>

The traverse_trees() method recursively walks through trees, but also prunes the tree-walk based on a callback. Some callers, such as unpack_trees(), are quite complicated and can have wildly different performance between two different commands.

Create constants that count these values and then report the results at the end of a process. These counts are cumulative across multiple "root" instances of traverse_trees(), but they provide reproducible values for demonstrating improvements to the pruning algorithm when possible.

This change is modeled after a similar statistics reporting in 42e50e78 (revision.c: add trace2 stats around Bloom filter usage, 2020-04-06).

---
 tree-walk.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

index 0160294712b..2d6226d5f18 100644
@@ -4,6 +4,7 @@
 #include "object-store.h"
 #include "tree.h"
 #include "pathspec.h"
+#include "json-writer.h"
 
 static const char *get_mode(const char *str, unsigned int *modep)
 {

@@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
 	return 1;
 }
 
+static int traverse_trees_atexit_registered;
+static int traverse_trees_count;
+static int traverse_trees_cur_depth;
+static int traverse_trees_max_depth;
+
+static void trace2_traverse_trees_statistics_atexit(void)
+{
+	struct json_writer jw = JSON_WRITER_INIT;
+
+	jw_object_begin(&jw, 0);
+	jw_object_intmax(&jw, "traverse_trees_count", traverse_trees_count);
+	jw_object_intmax(&jw, "traverse_trees_max_depth", traverse_trees_max_depth);
+	jw_end(&jw);
+
+	trace2_data_json("traverse_trees", the_repository, "statistics", &jw);
+
+	jw_release(&jw);
+}
+
 void setup_traverse_info(struct traverse_info *info, const char *base)
 {
 	size_t pathlen = strlen(base);

@@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)
 	info->namelen = pathlen;
 	if (pathlen)
 		info->prev = &dummy;
+
+	if (trace2_is_enabled() && !traverse_trees_atexit_registered) {
+		atexit(trace2_traverse_trees_statistics_atexit);
+		traverse_trees_atexit_registered = 1;
+	}
 }
 
 char *make_traverse_path(char *path, size_t pathlen,

@@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,
 	int interesting = 1;
 	char *traverse_path;
 
+	traverse_trees_count++;
+	traverse_trees_cur_depth++;
+
+	if (traverse_trees_cur_depth > traverse_trees_max_depth)
+		traverse_trees_max_depth = traverse_trees_cur_depth;
+
 	if (n >= ARRAY_SIZE(entry))
 		BUG("traverse_trees() called with too many trees (%d)", n);
 

@@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,
 	free(traverse_path);
 	info->traverse_path = NULL;
 	strbuf_release(&base);
+
+	traverse_trees_cur_depth--;
 	return error;
 }
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The unpack_trees() method is quite complicated and its performance can change dramatically depending on how it is used. We already have some performance tracing regions, but they have not been updated to the trace2 API. Do so now.

We already have trace2 regions in unpack_trees.c:clear_ce_flags(), which uses a linear scan through the index without recursing into trees.

---
 unpack-trees.c | 5 +++++
 1 file changed, 5 insertions(+)

index 323280dd48b..af6e9b9c2fd 100644
@@ -1580,6 +1580,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES);
 
 	trace_performance_enter();
+	trace2_region_enter("unpack_trees", "unpack_trees", the_repository);
+
 	if (!core_apply_sparse_checkout || !o->update)
 		o->skip_sparse_checkout = 1;
 	if (!o->skip_sparse_checkout && !o->pl) {

@@ -1653,7 +1655,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		}
 
 		trace_performance_enter();
+		trace2_region_enter("unpack_trees", "traverse_trees", the_repository);
 		ret = traverse_trees(o->src_index, len, t, &info);
+		trace2_region_leave("unpack_trees", "traverse_trees", the_repository);
 		trace_performance_leave("traverse_trees");
 		if (ret < 0)
 			goto return_failed;

@@ -1741,6 +1745,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 done:
 	if (free_pattern_list)
 		clear_pattern_list(&pl);
+	trace2_region_leave("unpack_trees", "unpack_trees", the_repository);
 	trace_performance_leave("unpack_trees");
 	return ret;
 

gitgitgadget

From: Derrick Stolee <[email protected]>

This matches a trace_performance_enter()/trace_performance_leave() pair added by 0d1ed59 (unpack-trees: add performance tracing, 2018-08-18).

---
 cache-tree.c | 2 ++
 1 file changed, 2 insertions(+)

index a537a806c16..9efb6748662 100644
@@ -442,7 +442,9 @@ int cache_tree_update(struct index_state *istate, int flags)
 	if (i)
 		return i;
 	trace_performance_enter();
+	trace2_region_enter("cache_tree", "update", the_repository);
 	i = update_one(it, cache, entries, "", 0, &skip, flags);
+	trace2_region_leave("cache_tree", "update", the_repository);
 	trace_performance_leave("cache_tree_update");
 	if (i < 0)
 		return i;

gitgitgadget

From: Derrick Stolee <[email protected]>

As we write or read the cached tree index extension, it can be good to isolate how much of the file I/O time is spent constructing this in-memory tree from the existing index or writing it out again to the new index file. Use trace2 regions to indicate that we are spending time on this operation.

---
 cache-tree.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

index 9efb6748662..45fb57b17f3 100644
@@ -494,7 +494,9 @@ static void write_one(struct strbuf *buffer, struct cache_tree *it,
 
 void cache_tree_write(struct strbuf *sb, struct cache_tree *root)
 {
+	trace2_region_enter("cache_tree", "write", the_repository);
 	write_one(sb, root, "", 0);
+	trace2_region_leave("cache_tree", "write", the_repository);
 }
 
 static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)

@@ -583,9 +585,16 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 
 struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
 {
+	struct cache_tree *result;
+
 	if (buffer[0])
 		return NULL; /* not the whole tree */
-	return read_one(&buffer, &size);
+
+	trace2_region_enter("cache_tree", "read", the_repository);
+	result = read_one(&buffer, &size);
+	trace2_region_leave("cache_tree", "read", the_repository);
+
+	return result;
 }
 
 static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)

gitgitgadget

From: Derrick Stolee <[email protected]>

Commands such as "git reset --hard" rebuild the in-memory representation of the cached tree index extension by parsing tree objects starting at a known root tree. The performance of this operation can vary widely depending on the width and depth of the repository's working directory structure. Measure the time in this operation using trace2 regions in prime_cache_tree().

---
 cache-tree.c | 3 +++
 1 file changed, 3 insertions(+)

index 45fb57b17f3..7da59b2aa07 100644
@@ -744,10 +744,13 @@ void prime_cache_tree(struct repository *r,
 		      struct index_state *istate,
 		      struct tree *tree)
 {
+	trace2_region_enter("cache-tree", "prime_cache_tree", the_repository);
 	cache_tree_free(&istate->cache_tree);
 	istate->cache_tree = cache_tree();
+
 	prime_cache_tree_rec(r, istate->cache_tree, tree);
 	istate->cache_changed |= CACHE_TREE_CHANGED;
+	trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);
 }
 
 /*

gitgitgadget

From: Derrick Stolee <[email protected]>

I had difficulty in my efforts to learn about the cached tree extension based on the documentation and code because I had an incorrect assumption about how it behaved. This might be due to some ambiguity in the documentation, so this change modifies the beginning of the cached tree format by expanding the description of the feature.

My hope is that this documentation clarifies a few things:

1. There is an in-memory recursive tree structure that is constructed from the extension data. This structure has a few differences, such as where the name is stored.

2. What does it mean for an entry to be invalid?

3. When exactly are "new" trees created?

---
 Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----
 1 file changed, 30 insertions(+), 6 deletions(-)

index 69edf46c031..c614e136e24 100644
@@ -138,12 +138,36 @@ Git index format
 
 === Cached tree
 
-  Cached tree extension contains pre-computed hashes for trees that can
-  be derived from the index. It helps speed up tree object generation
-  from index for a new commit.
-
-  When a path is updated in index, the path must be invalidated and
-  removed from tree cache.
+  Since the index does not record entries for directories, the cache
+  entries cannot describe tree objects that already exist in the object
+  database for regions of the index that are unchanged from an existing
+  commit. The cached tree extension stores a recursive tree structure that
+  describes the trees that already exist and completely match sections of
+  the cache entries. This speeds up tree object generation from the index
+  for a new commit by only computing the trees that are "new" to that
+  commit.
+
+  The recursive tree structure uses nodes that store a number of cache
+  entries, a list of subnodes, and an object ID (OID). The OID references
+  the exising tree for that node, if it is known to exist. The subnodes
+  correspond to subdirectories that themselves have cached tree nodes. The
+  number of cache entries corresponds to the number of cache entries in
+  the index that describe paths within that tree's directory.
+
+  Note that the path for a given tree is part of the parent node in-memory
+  but is part of the child in the file format. The root tree has an empty
+  string for its name and its name does not exist in-memory.
+
+  When a path is updated in index, Git invalidates all nodes of the
+  recurisive cached tree corresponding to the parent directories of that
+  path. We store these tree nodes as being "invalid" by using "-1" as the
+  number of cache entries. To create trees corresponding to the current
+  index, Git only walks the invalid tree nodes and uses the cached OIDs
+  for the valid trees to construct new trees. In this way, Git only
+  constructs trees on the order of the number of changed paths (and their
+  depth in the working directory). This comes at a cost of tracking the
+  full directory structure in the cached tree extension, but this is
+  generally smaller than the full cache entry list in the index.
 
   The signature for this extension is { 'T', 'R', 'E', 'E' }.
 

gitgitgadget

By the way, the name of the extension is "cache tree".

	git grep -i 'cached[- ]tree' ':!po/'

reveals there are a handful of mistakes already present but their number is dwarfed when we check:

git grep -i 'cache tree' ':!po/'

Thanks. Describing them is a worthy goal.

Sorry, I am not sure if I follow. The top-level in-core cache_tree object records the number of entries, tree object name for the entire tree (if valid), and cache_tree_sub structures, one for each subdirectory. Each of the cache_tree_sub structure describes the "child" directory, including the path to it.

I will fix my own additions and add a patch that fixes these mistakes.

I need to read more about this. traverse_by_cache_tree() seems to be a good place to start. Thanks.

s/exising/existing/

That's a good point. I'll retract my statement here.

Making note of my s/recurisive/recursive/ typo here.

I will try to simplify.

Thanks,
-Stolee

Ah, that one I forgot about.

What I had in mind was a different optimization that is far more aggressive in unpack-trees.c::unpack_callback(); look for a comment that begins with "Everything under the name matches". The block allows us to skip an entire subdirectory hierarchy.

Ah, that one I forgot about.

What I had in mind was a different optimization that is far more aggressive in unpack-trees.c::unpack_callback(); look for a comment that begins with "Everything under the name matches". The block allows us to skip an entire subdirectory hierarchy.

From: Derrick Stolee <[email protected]>

The end of the cached tree index extension format trails off with ellipses ever since 23fcc98 (doc: technical details about the index file format, 2011-03-01). While an intuitive reader could gather what this means, it could be better to use "and so on" instead.

Really, this is only justified because I also wanted to point out that the number of subtrees in the index format is used to determine when the recursive depth-first-search stack should be "popped." This should help to add clarity to the format.

---
 Documentation/technical/index-format.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index c614e136e24..2ebe88b9d46 100644
@@ -198,7 +198,8 @@ Git index format
   first entry represents the root level of the repository, followed by the
   first subtree--let's call this A--of the root level (with its name
   relative to the root level), followed by the first subtree of A (with
-  its name relative to A), ...
+  its name relative to A), and so on. The specified number of subtrees
+  indicates when the current level of the recursive stack is complete.
 
 === Resolve undo
 

gitgitgadget

From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= <[email protected]>

Use the name length field of cache entries instead of calculating its value anew.

---
 cache-tree.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

index 7da59b2aa07..4274de75bac 100644
@@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,
 		 * the cache is sorted.  Also path can appear only once,
 		 * which means conflicting one would immediately follow.
 		 */
-		const char *this_name = cache[i]->name;
-		const char *next_name = cache[i+1]->name;
-		int this_len = strlen(this_name);
-		if (this_len < strlen(next_name) &&
+		const struct cache_entry *this_ce = cache[i];
+		const struct cache_entry *next_ce = cache[i + 1];
+		const char *this_name = this_ce->name;
+		const char *next_name = next_ce->name;
+		int this_len = ce_namelen(this_ce);
+		if (this_len < ce_namelen(next_ce) &&
 		    strncmp(this_name, next_name, this_len) == 0 &&
 		    next_name[this_len] == '/') {
 			if (10 < ++funny) {

gitgitgadget

From: Derrick Stolee <[email protected]>

The previous change reduced time spent in strlen() while comparing consecutive paths in verify_cache(), but we can do better. The conditional checks the existence of a directory separator at the correct location, but only after doing a string comparison. Swap the order to be logically equivalent but perform fewer string comparisons.

To test the effect on performance, I used a repository with over three million paths in the index. I then ran the following command on repeat:

  git -c index.threads=1 commit --amend --allow-empty --no-edit

Here are the measurements over 10 runs after a 5-run warmup:

Benchmark #1: v2.30.0

    Time (mean ± σ):     854.5 ms ±  18.2 ms
    Range (min … max):   825.0 ms … 892.8 ms

Benchmark #2: Previous change

    Time (mean ± σ):     833.2 ms ±  10.3 ms
    Range (min … max):   815.8 ms … 849.7 ms

Benchmark #3: This change

    Time (mean ± σ):     815.5 ms ±  18.1 ms
    Range (min … max):   795.4 ms … 849.5 ms

This change is 2% faster than the previous change and 5% faster than v2.30.0.

---
 cache-tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index 4274de75bac..3f1a8d4f1b7 100644
@@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache,
 		const char *next_name = next_ce->name;
 		int this_len = ce_namelen(this_ce);
 		if (this_len < ce_namelen(next_ce) &&
-		    strncmp(this_name, next_name, this_len) == 0 &&
-		    next_name[this_len] == '/') {
+		    next_name[this_len] == '/' &&
+		    strncmp(this_name, next_name, this_len) == 0) {
 			if (10 < ++funny) {
 				fprintf(stderr, "...\n");
 				break;

gitgitgadget

I've taken a professional interest in the index lately, and I've been trying mostly to learn about it and measure different operations. Along the way, I've seen some possible improvements in documentation, behavior, and tracing.

This series collects most of my thoughts so far, including:

1. Adding extra trace2 regions and statistics (similar to [1]) (Patches

    1-5).

2. Update documentation about the cached tree extension (Patches 6-7).
3. Improved the performance of verify_cache() (Patches 8-9).

Thanks, -Stolee

[1]
https://lore.kernel.org/git/[email protected]/

UPDATES IN V3
=============

* Added a patch that fixes previous uses of "cached tree"

* Updated preamble patch with typos and semantic corrections.

Derrick Stolee (9):
tree-walk: report recursion counts
unpack-trees: add trace2 regions
cache-tree: use trace2 in cache_tree_update()
cache-tree: trace regions for I/O
cache-tree: trace regions for prime_cache_tree
index-format: use 'cache tree' over 'cached tree'
index-format: update preamble to cache tree extension
index-format: discuss recursion of cached-tree better
cache-tree: speed up consecutive path comparisons

René Scharfe (1):
cache-tree: use ce_namelen() instead of strlen()

 Documentation/technical/index-format.txt | 42 ++++++++++++++++++------
 cache-tree.c                             | 30 +++++++++++++----
 t/t7104-reset-hard.sh                    |  2 +-
 tree-walk.c                              | 33 +++++++++++++++++++
 unpack-trees.c                           |  5 +++
 5 files changed, 94 insertions(+), 18 deletions(-)

base-commit: 71ca53e8125e36efbda17293c50027d31681a41f
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-829%2Fderrickstolee%2Fcache-tree%2Fbasics-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-829/derrickstolee/cache-tree/basics-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/829

Range-diff vs v2:

  1:  0e500c86f39 =  1:  0e500c86f39 tree-walk: report recursion counts
  2:  4157b91acf8 =  2:  4157b91acf8 unpack-trees: add trace2 regions
  3:  8959d57abdd =  3:  8959d57abdd cache-tree: use trace2 in cache_tree_update()
  4:  1d8a797ee26 =  4:  1d8a797ee26 cache-tree: trace regions for I/O
  5:  2b2e70bb77c =  5:  2b2e70bb77c cache-tree: trace regions for prime_cache_tree
  -:  ----------- >  6:  2d7b18c2e0b index-format: use 'cache tree' over 'cached tree'
  6:  75b51483d3c !  7:  c5cffb5956e index-format: update preamble to cached tree extension

@@ Metadata
Author: Derrick Stolee <[email protected]>

## Commit message ##
- index-format: update preamble to cached tree extension
+ index-format: update preamble to cache tree extension

- I had difficulty in my efforts to learn about the cached tree extension
+ I had difficulty in my efforts to learn about the cache tree extension
based on the documentation and code because I had an incorrect assumption about how it behaved. This might be due to some ambiguity in the documentation, so this change modifies the beginning of the cached
@@ Commit message

3. When exactly are "new" trees created?

+ Helped-by: Junio C Hamano <[email protected]>

## Documentation/technical/index-format.txt ##
@@ Documentation/technical/index-format.txt: Git index format

- === Cached tree
+ === Cache tree

-- Cached tree extension contains pre-computed hashes for trees that can +- Cache tree extension contains pre-computed hashes for trees that can
- be derived from the index. It helps speed up tree object generation
- from index for a new commit.
-
@@ Documentation/technical/index-format.txt: Git index format
+ Since the index does not record entries for directories, the cache
+ entries cannot describe tree objects that already exist in the object
+ database for regions of the index that are unchanged from an existing
-+ commit. The cached tree extension stores a recursive tree structure that ++ commit. The cache tree extension stores a recursive tree structure that
+ describes the trees that already exist and completely match sections of
+ the cache entries. This speeds up tree object generation from the index
+ for a new commit by only computing the trees that are "new" to that
-+ commit.
++ commit. It also assists when comparing the index to another tree, such ++ as HEAD^{tree}, since sections of the index can be skipped when a tree ++ comparison demonstrates equality.
+
+ The recursive tree structure uses nodes that store a number of cache
+ entries, a list of subnodes, and an object ID (OID). The OID references
-+ the exising tree for that node, if it is known to exist. The subnodes -+ correspond to subdirectories that themselves have cached tree nodes. The ++ the existing tree for that node, if it is known to exist. The subnodes ++ correspond to subdirectories that themselves have cache tree nodes. The
+ number of cache entries corresponds to the number of cache entries in
+ the index that describe paths within that tree's directory. +
-+ Note that the path for a given tree is part of the parent node in-memory -+ but is part of the child in the file format. The root tree has an empty -+ string for its name and its name does not exist in-memory. ++ The extension tracks the full directory structure in the cache tree ++ extension, but this is generally smaller than the full cache entry list.
+
+ When a path is updated in index, Git invalidates all nodes of the
-+ recurisive cached tree corresponding to the parent directories of that ++ recursive cache tree corresponding to the parent directories of that
+ path. We store these tree nodes as being "invalid" by using "-1" as the
-+ number of cache entries. To create trees corresponding to the current -+ index, Git only walks the invalid tree nodes and uses the cached OIDs -+ for the valid trees to construct new trees. In this way, Git only -+ constructs trees on the order of the number of changed paths (and their -+ depth in the working directory). This comes at a cost of tracking the -+ full directory structure in the cached tree extension, but this is -+ generally smaller than the full cache entry list in the index. ++ number of cache entries. Invalid nodes still store a span of index ++ entries, allowing Git to focus its efforts when reconstructing a full ++ cache tree.

The signature for this extension is { 'T', 'R', 'E', 'E' }.

  7:  b2bb141a254 =  8:  97c06c80a85 index-format: discuss recursion of cached-tree better
  8:  5298694786e =  9:  2532f5cc189 cache-tree: use ce_namelen() instead of strlen()
  9:  72edd7bb427 = 10:  7c1c206a0bc cache-tree: speed up consecutive path comparisons

gitgitgadget

From: Derrick Stolee <[email protected]>

The traverse_trees() method recursively walks through trees, but also prunes the tree-walk based on a callback. Some callers, such as unpack_trees(), are quite complicated and can have wildly different performance between two different commands.

Create constants that count these values and then report the results at the end of a process. These counts are cumulative across multiple "root" instances of traverse_trees(), but they provide reproducible values for demonstrating improvements to the pruning algorithm when possible.

This change is modeled after a similar statistics reporting in 42e50e78 (revision.c: add trace2 stats around Bloom filter usage, 2020-04-06).

---
 tree-walk.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

index 0160294712b..2d6226d5f18 100644
@@ -4,6 +4,7 @@
 #include "object-store.h"
 #include "tree.h"
 #include "pathspec.h"
+#include "json-writer.h"
 
 static const char *get_mode(const char *str, unsigned int *modep)
 {

@@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry)
 	return 1;
 }
 
+static int traverse_trees_atexit_registered;
+static int traverse_trees_count;
+static int traverse_trees_cur_depth;
+static int traverse_trees_max_depth;
+
+static void trace2_traverse_trees_statistics_atexit(void)
+{
+	struct json_writer jw = JSON_WRITER_INIT;
+
+	jw_object_begin(&jw, 0);
+	jw_object_intmax(&jw, "traverse_trees_count", traverse_trees_count);
+	jw_object_intmax(&jw, "traverse_trees_max_depth", traverse_trees_max_depth);
+	jw_end(&jw);
+
+	trace2_data_json("traverse_trees", the_repository, "statistics", &jw);
+
+	jw_release(&jw);
+}
+
 void setup_traverse_info(struct traverse_info *info, const char *base)
 {
 	size_t pathlen = strlen(base);

@@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base)
 	info->namelen = pathlen;
 	if (pathlen)
 		info->prev = &dummy;
+
+	if (trace2_is_enabled() && !traverse_trees_atexit_registered) {
+		atexit(trace2_traverse_trees_statistics_atexit);
+		traverse_trees_atexit_registered = 1;
+	}
 }
 
 char *make_traverse_path(char *path, size_t pathlen,

@@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate,
 	int interesting = 1;
 	char *traverse_path;
 
+	traverse_trees_count++;
+	traverse_trees_cur_depth++;
+
+	if (traverse_trees_cur_depth > traverse_trees_max_depth)
+		traverse_trees_max_depth = traverse_trees_cur_depth;
+
 	if (n >= ARRAY_SIZE(entry))
 		BUG("traverse_trees() called with too many trees (%d)", n);
 

@@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate,
 	free(traverse_path);
 	info->traverse_path = NULL;
 	strbuf_release(&base);
+
+	traverse_trees_cur_depth--;
 	return error;
 }
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The unpack_trees() method is quite complicated and its performance can change dramatically depending on how it is used. We already have some performance tracing regions, but they have not been updated to the trace2 API. Do so now.

We already have trace2 regions in unpack_trees.c:clear_ce_flags(), which uses a linear scan through the index without recursing into trees.

---
 unpack-trees.c | 5 +++++
 1 file changed, 5 insertions(+)

index 323280dd48b..af6e9b9c2fd 100644
@@ -1580,6 +1580,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES);
 
 	trace_performance_enter();
+	trace2_region_enter("unpack_trees", "unpack_trees", the_repository);
+
 	if (!core_apply_sparse_checkout || !o->update)
 		o->skip_sparse_checkout = 1;
 	if (!o->skip_sparse_checkout && !o->pl) {

@@ -1653,7 +1655,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		}
 
 		trace_performance_enter();
+		trace2_region_enter("unpack_trees", "traverse_trees", the_repository);
 		ret = traverse_trees(o->src_index, len, t, &info);
+		trace2_region_leave("unpack_trees", "traverse_trees", the_repository);
 		trace_performance_leave("traverse_trees");
 		if (ret < 0)
 			goto return_failed;

@@ -1741,6 +1745,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 done:
 	if (free_pattern_list)
 		clear_pattern_list(&pl);
+	trace2_region_leave("unpack_trees", "unpack_trees", the_repository);
 	trace_performance_leave("unpack_trees");
 	return ret;
 

gitgitgadget

From: Derrick Stolee <[email protected]>

This matches a trace_performance_enter()/trace_performance_leave() pair added by 0d1ed59 (unpack-trees: add performance tracing, 2018-08-18).

---
 cache-tree.c | 2 ++
 1 file changed, 2 insertions(+)

index a537a806c16..9efb6748662 100644
@@ -442,7 +442,9 @@ int cache_tree_update(struct index_state *istate, int flags)
 	if (i)
 		return i;
 	trace_performance_enter();
+	trace2_region_enter("cache_tree", "update", the_repository);
 	i = update_one(it, cache, entries, "", 0, &skip, flags);
+	trace2_region_leave("cache_tree", "update", the_repository);
 	trace_performance_leave("cache_tree_update");
 	if (i < 0)
 		return i;

gitgitgadget

From: Derrick Stolee <[email protected]>

As we write or read the cached tree index extension, it can be good to isolate how much of the file I/O time is spent constructing this in-memory tree from the existing index or writing it out again to the new index file. Use trace2 regions to indicate that we are spending time on this operation.

---
 cache-tree.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

index 9efb6748662..45fb57b17f3 100644
@@ -494,7 +494,9 @@ static void write_one(struct strbuf *buffer, struct cache_tree *it,
 
 void cache_tree_write(struct strbuf *sb, struct cache_tree *root)
 {
+	trace2_region_enter("cache_tree", "write", the_repository);
 	write_one(sb, root, "", 0);
+	trace2_region_leave("cache_tree", "write", the_repository);
 }
 
 static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)

@@ -583,9 +585,16 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p)
 
 struct cache_tree *cache_tree_read(const char *buffer, unsigned long size)
 {
+	struct cache_tree *result;
+
 	if (buffer[0])
 		return NULL; /* not the whole tree */
-	return read_one(&buffer, &size);
+
+	trace2_region_enter("cache_tree", "read", the_repository);
+	result = read_one(&buffer, &size);
+	trace2_region_leave("cache_tree", "read", the_repository);
+
+	return result;
 }
 
 static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path)

gitgitgadget

From: Derrick Stolee <[email protected]>

Commands such as "git reset --hard" rebuild the in-memory representation of the cached tree index extension by parsing tree objects starting at a known root tree. The performance of this operation can vary widely depending on the width and depth of the repository's working directory structure. Measure the time in this operation using trace2 regions in prime_cache_tree().

---
 cache-tree.c | 3 +++
 1 file changed, 3 insertions(+)

index 45fb57b17f3..7da59b2aa07 100644
@@ -744,10 +744,13 @@ void prime_cache_tree(struct repository *r,
 		      struct index_state *istate,
 		      struct tree *tree)
 {
+	trace2_region_enter("cache-tree", "prime_cache_tree", the_repository);
 	cache_tree_free(&istate->cache_tree);
 	istate->cache_tree = cache_tree();
+
 	prime_cache_tree_rec(r, istate->cache_tree, tree);
 	istate->cache_changed |= CACHE_TREE_CHANGED;
+	trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);
 }
 
 /*

gitgitgadget

From: Derrick Stolee <[email protected]>

The index has a "cache tree" extension. This corresponds to a significant API implemented in cache-tree.[ch]. However, there are a few places that refer to this erroneously as "cached tree". These are rare, but notably the index-format.txt file itself makes this error.

The only other reference is in t7104-reset-hard.sh.

---
 Documentation/technical/index-format.txt | 6 +++---
 t/t7104-reset-hard.sh                    | 2 +-
 2 files changed, 4 insertions(+), 4 deletions(-)

index 69edf46c031..c71314731ec 100644
@@ -26,7 +26,7 @@ Git index format
      Extensions are identified by signature. Optional extensions can
      be ignored if Git does not understand them.
 
-     Git currently supports cached tree and resolve undo extensions.
+     Git currently supports cache tree and resolve undo extensions.
 
      4-byte extension signature. If the first byte is 'A'..'Z' the
      extension is optional and can be ignored.

@@ -136,9 +136,9 @@ Git index format
 
 == Extensions
 
-=== Cached tree
+=== Cache tree
 
-  Cached tree extension contains pre-computed hashes for trees that can
+  Cache tree extension contains pre-computed hashes for trees that can
   be derived from the index. It helps speed up tree object generation
   from index for a new commit.
 

index 16faa078137..7948ec392b3 100755
@@ -33,7 +33,7 @@ test_expect_success 'reset --hard should restore unmerged ones' '
 
 '
 
-test_expect_success 'reset --hard did not corrupt index or cached-tree' '
+test_expect_success 'reset --hard did not corrupt index or cache-tree' '
 
 	T=$(git write-tree) &&
 	rm -f .git/index &&

gitgitgadget

From: Derrick Stolee <[email protected]>

I had difficulty in my efforts to learn about the cache tree extension based on the documentation and code because I had an incorrect assumption about how it behaved. This might be due to some ambiguity in the documentation, so this change modifies the beginning of the cached tree format by expanding the description of the feature.

My hope is that this documentation clarifies a few things:

1. There is an in-memory recursive tree structure that is constructed from the extension data. This structure has a few differences, such as where the name is stored.

2. What does it mean for an entry to be invalid?

3. When exactly are "new" trees created?

---
 Documentation/technical/index-format.txt | 33 +++++++++++++++++++-----
 1 file changed, 27 insertions(+), 6 deletions(-)

index c71314731ec..65dcfa570df 100644
@@ -138,12 +138,33 @@ Git index format
 
 === Cache tree
 
-  Cache tree extension contains pre-computed hashes for trees that can
-  be derived from the index. It helps speed up tree object generation
-  from index for a new commit.
-
-  When a path is updated in index, the path must be invalidated and
-  removed from tree cache.
+  Since the index does not record entries for directories, the cache
+  entries cannot describe tree objects that already exist in the object
+  database for regions of the index that are unchanged from an existing
+  commit. The cache tree extension stores a recursive tree structure that
+  describes the trees that already exist and completely match sections of
+  the cache entries. This speeds up tree object generation from the index
+  for a new commit by only computing the trees that are "new" to that
+  commit. It also assists when comparing the index to another tree, such
+  as `HEAD^{tree}`, since sections of the index can be skipped when a tree
+  comparison demonstrates equality.
+
+  The recursive tree structure uses nodes that store a number of cache
+  entries, a list of subnodes, and an object ID (OID). The OID references
+  the existing tree for that node, if it is known to exist. The subnodes
+  correspond to subdirectories that themselves have cache tree nodes. The
+  number of cache entries corresponds to the number of cache entries in
+  the index that describe paths within that tree's directory.
+
+  The extension tracks the full directory structure in the cache tree
+  extension, but this is generally smaller than the full cache entry list.
+
+  When a path is updated in index, Git invalidates all nodes of the
+  recursive cache tree corresponding to the parent directories of that
+  path. We store these tree nodes as being "invalid" by using "-1" as the
+  number of cache entries. Invalid nodes still store a span of index
+  entries, allowing Git to focus its efforts when reconstructing a full
+  cache tree.
 
   The signature for this extension is { 'T', 'R', 'E', 'E' }.
 

gitgitgadget

From: Derrick Stolee <[email protected]>

The end of the cached tree index extension format trails off with ellipses ever since 23fcc98 (doc: technical details about the index file format, 2011-03-01). While an intuitive reader could gather what this means, it could be better to use "and so on" instead.

Really, this is only justified because I also wanted to point out that the number of subtrees in the index format is used to determine when the recursive depth-first-search stack should be "popped." This should help to add clarity to the format.

---
 Documentation/technical/index-format.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index 65dcfa570df..b633482b1bd 100644
@@ -195,7 +195,8 @@ Git index format
   first entry represents the root level of the repository, followed by the
   first subtree--let's call this A--of the root level (with its name
   relative to the root level), followed by the first subtree of A (with
-  its name relative to A), ...
+  its name relative to A), and so on. The specified number of subtrees
+  indicates when the current level of the recursive stack is complete.
 
 === Resolve undo
 

gitgitgadget

From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= <[email protected]>

Use the name length field of cache entries instead of calculating its value anew.

---
 cache-tree.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

index 7da59b2aa07..4274de75bac 100644
@@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,
 		 * the cache is sorted.  Also path can appear only once,
 		 * which means conflicting one would immediately follow.
 		 */
-		const char *this_name = cache[i]->name;
-		const char *next_name = cache[i+1]->name;
-		int this_len = strlen(this_name);
-		if (this_len < strlen(next_name) &&
+		const struct cache_entry *this_ce = cache[i];
+		const struct cache_entry *next_ce = cache[i + 1];
+		const char *this_name = this_ce->name;
+		const char *next_name = next_ce->name;
+		int this_len = ce_namelen(this_ce);
+		if (this_len < ce_namelen(next_ce) &&
 		    strncmp(this_name, next_name, this_len) == 0 &&
 		    next_name[this_len] == '/') {
 			if (10 < ++funny) {

gitgitgadget

From: Derrick Stolee <[email protected]>

The previous change reduced time spent in strlen() while comparing consecutive paths in verify_cache(), but we can do better. The conditional checks the existence of a directory separator at the correct location, but only after doing a string comparison. Swap the order to be logically equivalent but perform fewer string comparisons.

To test the effect on performance, I used a repository with over three million paths in the index. I then ran the following command on repeat:

  git -c index.threads=1 commit --amend --allow-empty --no-edit

Here are the measurements over 10 runs after a 5-run warmup:

Benchmark #1: v2.30.0

    Time (mean ± σ):     854.5 ms ±  18.2 ms
    Range (min … max):   825.0 ms … 892.8 ms

Benchmark #2: Previous change

    Time (mean ± σ):     833.2 ms ±  10.3 ms
    Range (min … max):   815.8 ms … 849.7 ms

Benchmark #3: This change

    Time (mean ± σ):     815.5 ms ±  18.1 ms
    Range (min … max):   795.4 ms … 849.5 ms

This change is 2% faster than the previous change and 5% faster than v2.30.0.

---
 cache-tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index 4274de75bac..3f1a8d4f1b7 100644
@@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache,
 		const char *next_name = next_ce->name;
 		int this_len = ce_namelen(this_ce);
 		if (this_len < ce_namelen(next_ce) &&
-		    strncmp(this_name, next_name, this_len) == 0 &&
-		    next_name[this_len] == '/') {
+		    next_name[this_len] == '/' &&
+		    strncmp(this_name, next_name, this_len) == 0) {
 			if (10 < ++funny) {
 				fprintf(stderr, "...\n");
 				break;

gitgitgadget

I've given all the patches in the series another reading, and found them to be nicely done.

Let's merge it down to 'next'.

Thanks.