[PATCH 0/8] Cleanups around index operations

[PATCH 0/8] Cleanups around index operations

[Derrick Stolee via 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. Removing an unnecessary loop from verify_cache() (Patch 8).

Thanks, -Stolee

[1]
https://lore.kernel.org/git/pull.828.git.1609302714183.gitgitgadget@gmail.com/

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

[PATCH 1/8] tree-walk: report recursion counts

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 tree-walk.c    | 33 +++++++++++++++++++++++++++++++++
 unpack-trees.c |  1 -
 2 files changed, 33 insertions(+), 1 deletion(-)

diff --git a/tree-walk.c b/tree-walk.c
index 0160294712b..2d6226d5f18 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -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;
 }
 
diff --git a/unpack-trees.c b/unpack-trees.c
index 323280dd48b..02f484604ac 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -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

[PATCH 2/8] unpack-trees: add trace2 regions

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 unpack-trees.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/unpack-trees.c b/unpack-trees.c
index 02f484604ac..7dbd006ac56 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -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

[PATCH 3/8] cache-tree: use trace2 in cache_tree_update()

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/cache-tree.c b/cache-tree.c
index a537a806c16..9efb6748662 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH 4/8] cache-tree: trace regions for I/O

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/cache-tree.c b/cache-tree.c
index 9efb6748662..45fb57b17f3 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH 5/8] cache-tree: trace regions for prime_cache_tree

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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().

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/cache-tree.c b/cache-tree.c
index 45fb57b17f3..f135bb77af5 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH 6/8] index-format: update preamble to cached tree extension

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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?

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----
 1 file changed, 30 insertions(+), 6 deletions(-)

diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index 69edf46c031..c614e136e24 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -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

[PATCH 7/8] index-format: discuss recursion of cached-tree better

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/index-format.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index c614e136e24..2ebe88b9d46 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -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

[PATCH 8/8] cache-tree: avoid path comparison loop when silent

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index f135bb77af5..c6c084463bd 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

Re: [PATCH 1/8] tree-walk: report recursion counts

[Elijah Newren]

On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> The traverse_trees() method recusively walks through trees, but also

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

> 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.

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

> 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.
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  tree-walk.c    | 33 +++++++++++++++++++++++++++++++++
>  unpack-trees.c |  1 -
>  2 files changed, 33 insertions(+), 1 deletion(-)

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.

>
> diff --git a/tree-walk.c b/tree-walk.c
> index 0160294712b..2d6226d5f18 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -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);
> +}

Yeah, I don't know the json_writer or trace2 stuff; might be nice to
cc Josh Steadmon or someone to review this patch.  (Or perhaps he
already reviewed internally?)

> +
>  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--;

I double-checked to see if there were any other return sites in this
function.  There aren't, which is nice and keeps this clean.

>         return error;
>  }
>
> diff --git a/unpack-trees.c b/unpack-trees.c
> index 323280dd48b..02f484604ac 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -1559,7 +1559,6 @@ static void populate_from_existing_patterns(struct unpack_trees_options *o,
>         free(sparse);
>  }
>
> -

Did you mean to combine this cleanup with some other patch?  If not,
could it be put into its own patch?

>  static int verify_absent(const struct cache_entry *,
>                          enum unpack_trees_error_types,
>                          struct unpack_trees_options *);
> --
> gitgitgadget

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.

Re: [PATCH 2/8] unpack-trees: add trace2 regions

[Elijah Newren]

On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> 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.

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

> We already have trace2 regions in unpack_trees.c:clear_ce_flags(), which
> uses a linear scan through the index without recursing into trees.
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  unpack-trees.c | 5 +++++
>  1 file changed, 5 insertions(+)
>
> diff --git a/unpack-trees.c b/unpack-trees.c
> index 02f484604ac..7dbd006ac56 100644
> --- a/unpack-trees.c
> +++ b/unpack-trees.c
> @@ -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

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

Re: [PATCH 5/8] cache-tree: trace regions for prime_cache_tree

[Elijah Newren]

On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> 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().
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  cache-tree.c | 3 +++
>  1 file changed, 3 insertions(+)
>
> diff --git a/cache-tree.c b/cache-tree.c
> index 45fb57b17f3..f135bb77af5 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -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);

Shouldn't this be at the start of the function, a few lines up?

>         prime_cache_tree_rec(r, istate->cache_tree, tree);
> +       trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);

...and this be one more line down?  (or the string "prime_cache_tree"
have a "_rec" added to it?)

>         istate->cache_changed |= CACHE_TREE_CHANGED;
>  }
>
> --
> gitgitgadget
>

Re: [PATCH 1/8] tree-walk: report recursion counts

[Derrick Stolee]

On 12/30/2020 2:42 PM, Elijah Newren wrote:
> On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
>>
>> From: Derrick Stolee <dstolee@microsoft.com>
>>
>> The traverse_trees() method recusively walks through trees, but also
> 
> recursively -- you're missing the second 'r'.

Thanks.

>> 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.
> 
> Not sure it belongs in the commit message, but you do have me curious
> what you're digging in to...

I'm still testing whether my idea will work out. Hopefully soon. ;)
 
>> 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.
>>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>> ---
>>  tree-walk.c    | 33 +++++++++++++++++++++++++++++++++
>>  unpack-trees.c |  1 -
>>  2 files changed, 33 insertions(+), 1 deletion(-)
> 
> 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.

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

>> diff --git a/tree-walk.c b/tree-walk.c
>> index 0160294712b..2d6226d5f18 100644
>> --- a/tree-walk.c
>> +++ b/tree-walk.c
>> @@ -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);
>> +}
> 
> Yeah, I don't know the json_writer or trace2 stuff; might be nice to
> cc Josh Steadmon or someone to review this patch.  (Or perhaps he
> already reviewed internally?)

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).

>> +
>>  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--;
> 
> I double-checked to see if there were any other return sites in this
> function.  There aren't, which is nice and keeps this clean.
> 
>>         return error;
>>  }
>>
>> diff --git a/unpack-trees.c b/unpack-trees.c
>> index 323280dd48b..02f484604ac 100644
>> --- a/unpack-trees.c
>> +++ b/unpack-trees.c
>> @@ -1559,7 +1559,6 @@ static void populate_from_existing_patterns(struct unpack_trees_options *o,
>>         free(sparse);
>>  }
>>
>> -
> 
> Did you mean to combine this cleanup with some other patch?  If not,
> could it be put into its own patch?

It should be dropped! Thanks.

>>  static int verify_absent(const struct cache_entry *,
>>                          enum unpack_trees_error_types,
>>                          struct unpack_trees_options *);
>> --
>> gitgitgadget
> 
> 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.

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

Re: [PATCH 5/8] cache-tree: trace regions for prime_cache_tree

[Derrick Stolee]

On 12/30/2020 2:48 PM, Elijah Newren wrote:
> On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
>>
>> From: Derrick Stolee <dstolee@microsoft.com>
>>
>> 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().
>>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>> ---
>>  cache-tree.c | 3 +++
>>  1 file changed, 3 insertions(+)
>>
>> diff --git a/cache-tree.c b/cache-tree.c
>> index 45fb57b17f3..f135bb77af5 100644
>> --- a/cache-tree.c
>> +++ b/cache-tree.c
>> @@ -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);
> 
> Shouldn't this be at the start of the function, a few lines up?
> 
>>         prime_cache_tree_rec(r, istate->cache_tree, tree);
>> +       trace2_region_leave("cache-tree", "prime_cache_tree", the_repository);
> 
> ...and this be one more line down?  (or the string "prime_cache_tree"
> have a "_rec" added to it?)

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

Re: [PATCH 6/8] index-format: update preamble to cached tree extension

[Elijah Newren]

On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> 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?
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----
>  1 file changed, 30 insertions(+), 6 deletions(-)
>
> diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
> index 69edf46c031..c614e136e24 100644
> --- a/Documentation/technical/index-format.txt
> +++ b/Documentation/technical/index-format.txt
> @@ -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.

Ooh, I really like it; this probably would have helped me.  However,
we'll need to get someone else to take a look at this, because I don't
know enough to say whether any part of it is incorrect, misleading, or
incomplete or whether it's all good.  My knowledge in the area is
limited to moving a function from merge-recursive.c to cache-tree.c in
commit 724dd767b2 ("cache-tree: share code between functions writing
an index as a tree", 2019-08-17), but I seem to recall that I had to
rely on Junio's reviews and guidance to make the minor adaptations
found in that commit.

Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[Elijah Newren]

On Wed, Dec 30, 2020 at 11:27 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Derrick Stolee <dstolee@microsoft.com>
>
> 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.

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)

> 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.

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

>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  cache-tree.c | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)
>
> diff --git a/cache-tree.c b/cache-tree.c
> index f135bb77af5..c6c084463bd 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -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

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

Re: [PATCH 0/8] Cleanups around index operations

[Elijah Newren]

On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> 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).

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.

Re: [PATCH 0/8] Cleanups around index operations

[Derrick Stolee]

On 12/30/2020 3:19 PM, Elijah Newren wrote:
> On Wed, Dec 30, 2020 at 11:26 AM Derrick Stolee via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
>>
>> 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).
> 
> 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

Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[René Scharfe]

Am 30.12.20 um 20:26 schrieb Derrick Stolee via GitGitGadget:
> From: Derrick Stolee <dstolee@microsoft.com>
>
> 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.

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.

> 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.

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

diff --git a/cache-tree.c b/cache-tree.c
index a537a806c1..1105cfe6b7 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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;

Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[Derrick Stolee]

On 12/31/2020 7:34 AM, René Scharfe wrote:
> Am 30.12.20 um 20:26 schrieb Derrick Stolee via GitGitGadget:
>> From: Derrick Stolee <dstolee@microsoft.com>
>>
>> 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.
> 
> 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.

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()".

>> 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.>> Could you please check the performance impact of the following code
> simplification?

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.)

> diff --git a/cache-tree.c b/cache-tree.c
> index a537a806c1..1105cfe6b7 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -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;
 
This performs consistently worse than both cases (see performance test
later in this message). I think the strlen is saving us some time here.

In fact, I think the compiler is doing some magic to save our strlen
results, as I get identical performance results when doing this:

diff --git a/cache-tree.c b/cache-tree.c
index c6c084463b..a076e7cec5 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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;

To get more consistent results, I modified my benchmark to be the following:

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

I also adjusted the test suite to use 5 warmup rounds. Here are the numbers:

  Benchmark #1: v2.30.0
    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
 
So, 756.5ms average for v2.30.0.

  Benchmark #2: skipping the second loop
    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
 
Here, I just deleted the second loop to see what is the potential minimum.

  Benchmark #3: storing this_name during second loop
    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

The diff I provided earlier reduces the number of strlen() computations
by storing them across the loop iterations. There is no effect, which
makes me think the compiler is being smart.

  Benchmark #4: check for '/' before strncmp()
    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 

HOWEVER, if we swap the order of the conditionals to be

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

then we _do_ get a measurable, consistent speedup.

  Benchmark #5: using skip_prefix
    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

This final benchmark stores the results for your skip_prefix diff.

Including the full ranges of the 10 runs hopefully assists in demonstrating
that the performance changes are (mostly) consistent.

To wrap up, I'm going to eject this patch from my v2 since more investigation
must be done to see if this second loop _can_ be dropped. At minimum, it isn't
properly silent when requested and there _is_ a performance boost possible,
even if we keep the check.

Thanks,
-Stolee

Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[René Scharfe]

Am 31.12.20 um 17:46 schrieb Derrick Stolee:
> On 12/31/2020 7:34 AM, René Scharfe wrote:
>> diff --git a/cache-tree.c b/cache-tree.c
>> index a537a806c1..1105cfe6b7 100644
>> --- a/cache-tree.c
>> +++ b/cache-tree.c
>> @@ -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;
>
> This performs consistently worse than both cases (see performance test
> later in this message). I think the strlen is saving us some time here.
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.

> In fact, I think the compiler is doing some magic to save our strlen
> results, as I get identical performance results when doing this:
>
> diff --git a/cache-tree.c b/cache-tree.c
> index c6c084463b..a076e7cec5 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -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;
>

The compiler can do that because strlen() is a pure function; glibc
declares it like this:

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

> HOWEVER, if we swap the order of the conditionals to be
>
> 		if (this_len < next_len &&
> 		    strncmp(this_name, next_name, this_len) == 0 &&
> 		    next_name[this_len] == '/') {
>
> then we _do_ get a measurable, consistent speedup.

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é

[PATCH] cache-tree: use ce_namelen() instead of strlen()

[René Scharfe]

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

Signed-off-by: René Scharfe <l.s.r@web.de>
---
Not sure why it took me so long to spot this.. o_O

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

diff --git a/cache-tree.c b/cache-tree.c
index a537a806c1..57cacab195 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[René Scharfe]

Am 31.12.20 um 17:46 schrieb Derrick Stolee:
> To wrap up, I'm going to eject this patch from my v2 since more investigation
> must be done to see if this second loop _can_ be dropped. At minimum, it isn't
> properly silent when requested and there _is_ a performance boost possible,
> even if we keep the check.

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é

Re: [PATCH] cache-tree: use ce_namelen() instead of strlen()

[Derrick Stolee]

On 1/2/2021 10:19 AM, René Scharfe wrote:
> Use the name length field of cache entries instead of calculating its
> value anew.

Thanks! I didn't know about this macro.

-Stolee

> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
> Not sure why it took me so long to spot this.. o_O
> 
>  cache-tree.c | 10 ++++++----
>  1 file changed, 6 insertions(+), 4 deletions(-)
> 
> diff --git a/cache-tree.c b/cache-tree.c
> index a537a806c1..57cacab195 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -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) {

For what it's worth, this caching of the lengths lowers my test
time from 854ms to 833ms. It goes down again to 816ms with the
swapped conditional, so I'll include that patch here:

-- >8 --

From 8f303000030bd8f9db3466c90eb0d9fea11a7c3b Mon Sep 17 00:00:00 2001
From: Derrick Stolee <dstolee@microsoft.com>
Date: Sun, 3 Jan 2021 20:20:05 -0500
Subject: [PATCH] cache-tree: speed up consecutive path comparisons
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 57cacab195..6eaef21145 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v2 0/9] Cleanups around index operations

[Derrick Stolee via 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/pull.828.git.1609302714183.gitgitgadget@gmail.com/


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).
     +
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## 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

[PATCH v2 1/9] tree-walk: report recursion counts

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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).

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 tree-walk.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/tree-walk.c b/tree-walk.c
index 0160294712b..2d6226d5f18 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -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

[PATCH v2 2/9] unpack-trees: add trace2 regions

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 unpack-trees.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/unpack-trees.c b/unpack-trees.c
index 323280dd48b..af6e9b9c2fd 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -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

[PATCH v2 3/9] cache-tree: use trace2 in cache_tree_update()

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/cache-tree.c b/cache-tree.c
index a537a806c16..9efb6748662 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v2 4/9] cache-tree: trace regions for I/O

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/cache-tree.c b/cache-tree.c
index 9efb6748662..45fb57b17f3 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v2 5/9] cache-tree: trace regions for prime_cache_tree

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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().

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/cache-tree.c b/cache-tree.c
index 45fb57b17f3..7da59b2aa07 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v2 6/9] index-format: update preamble to cached tree extension

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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?

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/index-format.txt | 36 ++++++++++++++++++++----
 1 file changed, 30 insertions(+), 6 deletions(-)

diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index 69edf46c031..c614e136e24 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -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

[PATCH v2 7/9] index-format: discuss recursion of cached-tree better

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/index-format.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index c614e136e24..2ebe88b9d46 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -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

[PATCH v2 8/9] cache-tree: use ce_namelen() instead of strlen()

[René Scharfe via GitGitGadget]

From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= <l.s.r@web.de>

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

Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 7da59b2aa07..4274de75bac 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v2 9/9] cache-tree: speed up consecutive path comparisons

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 4274de75bac..3f1a8d4f1b7 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

Re: [PATCH] cache-tree: use ce_namelen() instead of strlen()

[Junio C Hamano]

René Scharfe <l.s.r@web.de> writes:

> Use the name length field of cache entries instead of calculating its
> value anew.
>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
> Not sure why it took me so long to spot this.. o_O

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.

>
>  cache-tree.c | 10 ++++++----
>  1 file changed, 6 insertions(+), 4 deletions(-)
>
> diff --git a/cache-tree.c b/cache-tree.c
> index a537a806c1..57cacab195 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -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

Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> 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)

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.

Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[Derrick Stolee]

On 1/6/2021 3:55 AM, Junio C Hamano wrote:
> Elijah Newren <newren@gmail.com> writes:
> 
>> 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)
> 
> 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

Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> Subject: Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension

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/'

> 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?

Thanks.  Describing them is a worthy goal.

> +  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 original motivation was the above one.  A cache of tree objects
that correspond to unmodified part of the directory structure helps
writing out a new tree out of modified index.

We later found out that we rather often compare the index against
the tree of HEAD (think: "git status"), and diff-lib.c::diff_cache()
does take advantage of the fact that an entire directory can be
skipped if the tree object taken from the HEAD side exactly matches
the tree recorded for the subdirectory in the cache tree extension.

> +  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.

OK.

> +  Note that the path for a given tree is part of the parent node in-memory

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.

> +  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.

It's more like we could have consistently used cache_tree_sub
instances to represent each and every level (i.e. I consider that
cache_tree_sub is what represents a directory, with cache_tree being
a record of just one aspect of it) including the root of the
hierarchy, but because there wasn't much point in giving a name to
the root level, I cheated and avoided wasting a cache_tree_sub for
it.  So from that point of view, the path belongs to the node in
each level in both in-core and on-disk representations.

> +  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.

Correct.

> +  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.

I wonder if the above is sufficiently clear, or "Git only has to
walk the spans of index entries that corresponds to the invalid
trees, while reusing the ..." is too long and detailed.

> +  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' }.

Looks good.  Thanks for working on this.

Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension

[Derrick Stolee]

On 1/6/2021 9:10 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> Subject: Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension
> 
> 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/'

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

>> +  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 original motivation was the above one.  A cache of tree objects
> that correspond to unmodified part of the directory structure helps
> writing out a new tree out of modified index.
> 
> We later found out that we rather often compare the index against
> the tree of HEAD (think: "git status"), and diff-lib.c::diff_cache()
> does take advantage of the fact that an entire directory can be
> skipped if the tree object taken from the HEAD side exactly matches
> the tree recorded for the subdirectory in the cache tree extension.

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

>> +  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.

s/exising/existing/

> 
> OK.
> 
>> +  Note that the path for a given tree is part of the parent node in-memory
> 
> 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.
> 
>> +  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.
> 
> It's more like we could have consistently used cache_tree_sub
> instances to represent each and every level (i.e. I consider that
> cache_tree_sub is what represents a directory, with cache_tree being
> a record of just one aspect of it) including the root of the
> hierarchy, but because there wasn't much point in giving a name to
> the root level, I cheated and avoided wasting a cache_tree_sub for
> it.  So from that point of view, the path belongs to the node in
> each level in both in-core and on-disk representations.

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

>> +  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.
> 
> Correct.

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

>> +  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.
> 
> I wonder if the above is sufficiently clear, or "Git only has to
> walk the spans of index entries that corresponds to the invalid
> trees, while reusing the ..." is too long and detailed.

I will try to simplify.

Thanks,
-Stolee

[PATCH v3 00/10] Cleanups around index operations

[Derrick Stolee via 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/pull.828.git.1609302714183.gitgitgadget@gmail.com/


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 <dstolee@microsoft.com>
      
       ## 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 <gitster@pobox.com>
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
      
       ## 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

[PATCH v3 01/10] tree-walk: report recursion counts

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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).

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 tree-walk.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/tree-walk.c b/tree-walk.c
index 0160294712b..2d6226d5f18 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -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

[PATCH v3 02/10] unpack-trees: add trace2 regions

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 unpack-trees.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/unpack-trees.c b/unpack-trees.c
index 323280dd48b..af6e9b9c2fd 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -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

[PATCH v3 03/10] cache-tree: use trace2 in cache_tree_update()

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/cache-tree.c b/cache-tree.c
index a537a806c16..9efb6748662 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v3 04/10] cache-tree: trace regions for I/O

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/cache-tree.c b/cache-tree.c
index 9efb6748662..45fb57b17f3 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v3 05/10] cache-tree: trace regions for prime_cache_tree

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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().

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/cache-tree.c b/cache-tree.c
index 45fb57b17f3..7da59b2aa07 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v3 06/10] index-format: use 'cache tree' over 'cached tree'

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Reported-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/index-format.txt | 6 +++---
 t/t7104-reset-hard.sh                    | 2 +-
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index 69edf46c031..c71314731ec 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -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.
 
diff --git a/t/t7104-reset-hard.sh b/t/t7104-reset-hard.sh
index 16faa078137..7948ec392b3 100755
--- a/t/t7104-reset-hard.sh
+++ b/t/t7104-reset-hard.sh
@@ -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

[PATCH v3 07/10] index-format: update preamble to cache tree extension

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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?

Helped-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/index-format.txt | 33 +++++++++++++++++++-----
 1 file changed, 27 insertions(+), 6 deletions(-)

diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index c71314731ec..65dcfa570df 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -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

[PATCH v3 08/10] index-format: discuss recursion of cached-tree better

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 Documentation/technical/index-format.txt | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt
index 65dcfa570df..b633482b1bd 100644
--- a/Documentation/technical/index-format.txt
+++ b/Documentation/technical/index-format.txt
@@ -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

[PATCH v3 09/10] cache-tree: use ce_namelen() instead of strlen()

[René Scharfe via GitGitGadget]

From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= <l.s.r@web.de>

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

Signed-off-by: René Scharfe <l.s.r@web.de>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 7da59b2aa07..4274de75bac 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

[PATCH v3 10/10] cache-tree: speed up consecutive path comparisons

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

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.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache-tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 4274de75bac..3f1a8d4f1b7 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -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

Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

>> We later found out that we rather often compare the index against
>> the tree of HEAD (think: "git status"), and diff-lib.c::diff_cache()
>> does take advantage of the fact that an entire directory can be
>> skipped if the tree object taken from the HEAD side exactly matches
>> the tree recorded for the subdirectory in the cache tree extension.
>
> I need to read more about this. traverse_by_cache_tree() seems to
> be a good place to start. Thanks.

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.

Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

>> We later found out that we rather often compare the index against
>> the tree of HEAD (think: "git status"), and diff-lib.c::diff_cache()
>> does take advantage of the fact that an entire directory can be
>> skipped if the tree object taken from the HEAD side exactly matches
>> the tree recorded for the subdirectory in the cache tree extension.
>
> I need to read more about this. traverse_by_cache_tree() seems to
> be a good place to start. Thanks.

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.

Re: [PATCH v3 00/10] Cleanups around index operations

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> 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

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.