* [PATCH 0/8] Cleanups around index operations @ 2020-12-30 19:26 Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 1/8] tree-walk: report recursion counts Derrick Stolee via GitGitGadget ` (9 more replies) 0 siblings, 10 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee I've taken a professional interest in the index lately, and I've been trying mostly to learn about it and measure different operations. Along the way, I've seen some possible improvements in documentation, behavior, and tracing. This series collects most of my thoughts so far, including: 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches 1-5). 2. Update documentation about the cached tree extension (Patches 6-7). 3. 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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH 1/8] tree-walk: report recursion counts 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 19:42 ` Elijah Newren 2020-12-30 19:26 ` [PATCH 2/8] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget ` (8 subsequent siblings) 9 siblings, 1 reply; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH 1/8] tree-walk: report recursion counts 2020-12-30 19:26 ` [PATCH 1/8] tree-walk: report recursion counts Derrick Stolee via GitGitGadget @ 2020-12-30 19:42 ` Elijah Newren 2020-12-30 19:51 ` Derrick Stolee 0 siblings, 1 reply; 53+ messages in thread From: Elijah Newren @ 2020-12-30 19:42 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 1/8] tree-walk: report recursion counts 2020-12-30 19:42 ` Elijah Newren @ 2020-12-30 19:51 ` Derrick Stolee 0 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee @ 2020-12-30 19:51 UTC (permalink / raw) To: Elijah Newren, Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, 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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH 2/8] unpack-trees: add trace2 regions 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 1/8] tree-walk: report recursion counts Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 19:45 ` Elijah Newren 2020-12-30 19:26 ` [PATCH 3/8] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget ` (7 subsequent siblings) 9 siblings, 1 reply; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH 2/8] unpack-trees: add trace2 regions 2020-12-30 19:26 ` [PATCH 2/8] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget @ 2020-12-30 19:45 ` Elijah Newren 0 siblings, 0 replies; 53+ messages in thread From: Elijah Newren @ 2020-12-30 19:45 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH 3/8] cache-tree: use trace2 in cache_tree_update() 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 1/8] tree-walk: report recursion counts Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 2/8] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 4/8] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget ` (6 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH 4/8] cache-tree: trace regions for I/O 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget ` (2 preceding siblings ...) 2020-12-30 19:26 ` [PATCH 3/8] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 5/8] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget ` (5 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH 5/8] cache-tree: trace regions for prime_cache_tree 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget ` (3 preceding siblings ...) 2020-12-30 19:26 ` [PATCH 4/8] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 19:48 ` Elijah Newren 2020-12-30 19:26 ` [PATCH 6/8] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget ` (4 subsequent siblings) 9 siblings, 1 reply; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH 5/8] cache-tree: trace regions for prime_cache_tree 2020-12-30 19:26 ` [PATCH 5/8] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget @ 2020-12-30 19:48 ` Elijah Newren 2020-12-30 19:53 ` Derrick Stolee 0 siblings, 1 reply; 53+ messages in thread From: Elijah Newren @ 2020-12-30 19:48 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, Derrick Stolee 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 > ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 5/8] cache-tree: trace regions for prime_cache_tree 2020-12-30 19:48 ` Elijah Newren @ 2020-12-30 19:53 ` Derrick Stolee 0 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee @ 2020-12-30 19:53 UTC (permalink / raw) To: Elijah Newren, Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, 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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH 6/8] index-format: update preamble to cached tree extension 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget ` (4 preceding siblings ...) 2020-12-30 19:26 ` [PATCH 5/8] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 20:00 ` Elijah Newren 2020-12-30 19:26 ` [PATCH 7/8] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget ` (3 subsequent siblings) 9 siblings, 1 reply; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH 6/8] index-format: update preamble to cached tree extension 2020-12-30 19:26 ` [PATCH 6/8] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget @ 2020-12-30 20:00 ` Elijah Newren 0 siblings, 0 replies; 53+ messages in thread From: Elijah Newren @ 2020-12-30 20:00 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH 7/8] index-format: discuss recursion of cached-tree better 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget ` (5 preceding siblings ...) 2020-12-30 19:26 ` [PATCH 6/8] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent Derrick Stolee via GitGitGadget ` (2 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget ` (6 preceding siblings ...) 2020-12-30 19:26 ` [PATCH 7/8] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 ` Derrick Stolee via GitGitGadget 2020-12-30 20:14 ` Elijah Newren 2020-12-31 12:34 ` René Scharfe 2020-12-30 20:19 ` [PATCH 0/8] Cleanups around index operations Elijah Newren 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget 9 siblings, 2 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2020-12-30 19:26 UTC (permalink / raw) To: git; +Cc: newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2020-12-30 19:26 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent Derrick Stolee via GitGitGadget @ 2020-12-30 20:14 ` Elijah Newren 2021-01-06 8:55 ` Junio C Hamano 2020-12-31 12:34 ` René Scharfe 1 sibling, 1 reply; 53+ messages in thread From: Elijah Newren @ 2020-12-30 20:14 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2020-12-30 20:14 ` Elijah Newren @ 2021-01-06 8:55 ` Junio C Hamano 2021-01-06 12:08 ` Derrick Stolee 0 siblings, 1 reply; 53+ messages in thread From: Junio C Hamano @ 2021-01-06 8:55 UTC (permalink / raw) To: Elijah Newren Cc: Derrick Stolee via GitGitGadget, Git Mailing List, Derrick Stolee, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2021-01-06 8:55 ` Junio C Hamano @ 2021-01-06 12:08 ` Derrick Stolee 0 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee @ 2021-01-06 12:08 UTC (permalink / raw) To: Junio C Hamano, Elijah Newren Cc: Derrick Stolee via GitGitGadget, Git Mailing List, Derrick Stolee, 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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2020-12-30 19:26 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent Derrick Stolee via GitGitGadget 2020-12-30 20:14 ` Elijah Newren @ 2020-12-31 12:34 ` René Scharfe 2020-12-31 16:46 ` Derrick Stolee 1 sibling, 1 reply; 53+ messages in thread From: René Scharfe @ 2020-12-31 12:34 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget, git Cc: newren, Derrick Stolee, Derrick Stolee 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; ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2020-12-31 12:34 ` René Scharfe @ 2020-12-31 16:46 ` Derrick Stolee 2021-01-01 13:30 ` René Scharfe ` (2 more replies) 0 siblings, 3 replies; 53+ messages in thread From: Derrick Stolee @ 2020-12-31 16:46 UTC (permalink / raw) To: René Scharfe, Derrick Stolee via GitGitGadget, git Cc: newren, Derrick Stolee, 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2020-12-31 16:46 ` Derrick Stolee @ 2021-01-01 13:30 ` René Scharfe 2021-01-02 15:19 ` [PATCH] cache-tree: use ce_namelen() instead of strlen() René Scharfe 2021-01-02 15:31 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent René Scharfe 2 siblings, 0 replies; 53+ messages in thread From: René Scharfe @ 2021-01-01 13:30 UTC (permalink / raw) To: Derrick Stolee, Derrick Stolee via GitGitGadget, git Cc: newren, Derrick Stolee, Derrick Stolee 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é ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH] cache-tree: use ce_namelen() instead of strlen() 2020-12-31 16:46 ` Derrick Stolee 2021-01-01 13:30 ` René Scharfe @ 2021-01-02 15:19 ` René Scharfe 2021-01-04 1:26 ` Derrick Stolee 2021-01-05 12:05 ` Junio C Hamano 2021-01-02 15:31 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent René Scharfe 2 siblings, 2 replies; 53+ messages in thread From: René Scharfe @ 2021-01-02 15:19 UTC (permalink / raw) To: Derrick Stolee, Derrick Stolee via GitGitGadget, git Cc: newren, Derrick Stolee, Derrick Stolee, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH] cache-tree: use ce_namelen() instead of strlen() 2021-01-02 15:19 ` [PATCH] cache-tree: use ce_namelen() instead of strlen() René Scharfe @ 2021-01-04 1:26 ` Derrick Stolee 2021-01-05 12:05 ` Junio C Hamano 1 sibling, 0 replies; 53+ messages in thread From: Derrick Stolee @ 2021-01-04 1:26 UTC (permalink / raw) To: René Scharfe, Derrick Stolee via GitGitGadget, git Cc: newren, Derrick Stolee, Derrick Stolee, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH] cache-tree: use ce_namelen() instead of strlen() 2021-01-02 15:19 ` [PATCH] cache-tree: use ce_namelen() instead of strlen() René Scharfe 2021-01-04 1:26 ` Derrick Stolee @ 2021-01-05 12:05 ` Junio C Hamano 1 sibling, 0 replies; 53+ messages in thread From: Junio C Hamano @ 2021-01-05 12:05 UTC (permalink / raw) To: René Scharfe Cc: Derrick Stolee, Derrick Stolee via GitGitGadget, git, newren, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent 2020-12-31 16:46 ` Derrick Stolee 2021-01-01 13:30 ` René Scharfe 2021-01-02 15:19 ` [PATCH] cache-tree: use ce_namelen() instead of strlen() René Scharfe @ 2021-01-02 15:31 ` René Scharfe 2 siblings, 0 replies; 53+ messages in thread From: René Scharfe @ 2021-01-02 15:31 UTC (permalink / raw) To: Derrick Stolee, Derrick Stolee via GitGitGadget, git Cc: newren, Derrick Stolee, Derrick Stolee 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é ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 0/8] Cleanups around index operations 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget ` (7 preceding siblings ...) 2020-12-30 19:26 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent Derrick Stolee via GitGitGadget @ 2020-12-30 20:19 ` Elijah Newren 2020-12-30 20:24 ` Derrick Stolee 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget 9 siblings, 1 reply; 53+ messages in thread From: Elijah Newren @ 2020-12-30 20:19 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget; +Cc: Git Mailing List, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH 0/8] Cleanups around index operations 2020-12-30 20:19 ` [PATCH 0/8] Cleanups around index operations Elijah Newren @ 2020-12-30 20:24 ` Derrick Stolee 0 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee @ 2020-12-30 20:24 UTC (permalink / raw) To: Elijah Newren, Derrick Stolee via GitGitGadget Cc: Git Mailing List, Derrick Stolee, Junio C Hamano 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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH v2 0/9] Cleanups around index operations 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget ` (8 preceding siblings ...) 2020-12-30 20:19 ` [PATCH 0/8] Cleanups around index operations Elijah Newren @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 1/9] tree-walk: report recursion counts Derrick Stolee via GitGitGadget ` (9 more replies) 9 siblings, 10 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git; +Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee I've taken a professional interest in the index lately, and I've been trying mostly to learn about it and measure different operations. Along the way, I've seen some possible improvements in documentation, behavior, and tracing. This series collects most of my thoughts so far, including: 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches 1-5). 2. Update documentation about the cached tree extension (Patches 6-7). 3. Improved the performance of verify_cache() (Patches 8-9). Thanks, -Stolee [1] https://lore.kernel.org/git/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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH v2 1/9] tree-walk: report recursion counts 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 2/9] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget ` (8 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v2 2/9] unpack-trees: add trace2 regions 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 1/9] tree-walk: report recursion counts Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 3/9] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget ` (7 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v2 3/9] cache-tree: use trace2 in cache_tree_update() 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 1/9] tree-walk: report recursion counts Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 2/9] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 4/9] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget ` (6 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v2 4/9] cache-tree: trace regions for I/O 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget ` (2 preceding siblings ...) 2021-01-04 3:09 ` [PATCH v2 3/9] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 5/9] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget ` (5 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v2 5/9] cache-tree: trace regions for prime_cache_tree 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget ` (3 preceding siblings ...) 2021-01-04 3:09 ` [PATCH v2 4/9] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 6/9] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget ` (4 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v2 6/9] index-format: update preamble to cached tree extension 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget ` (4 preceding siblings ...) 2021-01-04 3:09 ` [PATCH v2 5/9] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-07 2:10 ` Junio C Hamano 2021-01-04 3:09 ` [PATCH v2 7/9] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget ` (3 subsequent siblings) 9 siblings, 1 reply; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension 2021-01-04 3:09 ` [PATCH v2 6/9] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget @ 2021-01-07 2:10 ` Junio C Hamano 2021-01-07 11:51 ` Derrick Stolee 0 siblings, 1 reply; 53+ messages in thread From: Junio C Hamano @ 2021-01-07 2:10 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget Cc: git, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee "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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension 2021-01-07 2:10 ` Junio C Hamano @ 2021-01-07 11:51 ` Derrick Stolee 2021-01-07 20:12 ` Junio C Hamano 2021-01-07 21:26 ` Junio C Hamano 0 siblings, 2 replies; 53+ messages in thread From: Derrick Stolee @ 2021-01-07 11:51 UTC (permalink / raw) To: Junio C Hamano, Derrick Stolee via GitGitGadget Cc: git, newren, René Scharfe, Derrick Stolee, 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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension 2021-01-07 11:51 ` Derrick Stolee @ 2021-01-07 20:12 ` Junio C Hamano 2021-01-07 21:26 ` Junio C Hamano 1 sibling, 0 replies; 53+ messages in thread From: Junio C Hamano @ 2021-01-07 20:12 UTC (permalink / raw) To: Derrick Stolee Cc: Derrick Stolee via GitGitGadget, git, newren, René Scharfe, Derrick Stolee, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* Re: [PATCH v2 6/9] index-format: update preamble to cached tree extension 2021-01-07 11:51 ` Derrick Stolee 2021-01-07 20:12 ` Junio C Hamano @ 2021-01-07 21:26 ` Junio C Hamano 1 sibling, 0 replies; 53+ messages in thread From: Junio C Hamano @ 2021-01-07 21:26 UTC (permalink / raw) To: Derrick Stolee Cc: Derrick Stolee via GitGitGadget, git, newren, René Scharfe, Derrick Stolee, Derrick Stolee 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. ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH v2 7/9] index-format: discuss recursion of cached-tree better 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget ` (5 preceding siblings ...) 2021-01-04 3:09 ` [PATCH v2 6/9] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 8/9] cache-tree: use ce_namelen() instead of strlen() René Scharfe via GitGitGadget ` (2 subsequent siblings) 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v2 8/9] cache-tree: use ce_namelen() instead of strlen() 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget ` (6 preceding siblings ...) 2021-01-04 3:09 ` [PATCH v2 7/9] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 ` René Scharfe via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 9/9] cache-tree: speed up consecutive path comparisons Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget 9 siblings, 0 replies; 53+ messages in thread From: René Scharfe via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, René Scharfe 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v2 9/9] cache-tree: speed up consecutive path comparisons 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget ` (7 preceding siblings ...) 2021-01-04 3:09 ` [PATCH v2 8/9] cache-tree: use ce_namelen() instead of strlen() René Scharfe via GitGitGadget @ 2021-01-04 3:09 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget 9 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-04 3:09 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 00/10] Cleanups around index operations 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget ` (8 preceding siblings ...) 2021-01-04 3:09 ` [PATCH v2 9/9] cache-tree: speed up consecutive path comparisons Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 01/10] tree-walk: report recursion counts Derrick Stolee via GitGitGadget ` (10 more replies) 9 siblings, 11 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git; +Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee I've taken a professional interest in the index lately, and I've been trying mostly to learn about it and measure different operations. Along the way, I've seen some possible improvements in documentation, behavior, and tracing. This series collects most of my thoughts so far, including: 1. Adding extra trace2 regions and statistics (similar to [1]) (Patches 1-5). 2. Update documentation about the cached tree extension (Patches 6-7). 3. Improved the performance of verify_cache() (Patches 8-9). Thanks, -Stolee [1] https://lore.kernel.org/git/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 ^ permalink raw reply [flat|nested] 53+ messages in thread
* [PATCH v3 01/10] tree-walk: report recursion counts 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 02/10] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget ` (9 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 02/10] unpack-trees: add trace2 regions 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 01/10] tree-walk: report recursion counts Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 03/10] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget ` (8 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 03/10] cache-tree: use trace2 in cache_tree_update() 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 01/10] tree-walk: report recursion counts Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 02/10] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 04/10] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget ` (7 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 04/10] cache-tree: trace regions for I/O 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (2 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 03/10] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 05/10] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget ` (6 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 05/10] cache-tree: trace regions for prime_cache_tree 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (3 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 04/10] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 06/10] index-format: use 'cache tree' over 'cached tree' Derrick Stolee via GitGitGadget ` (5 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 06/10] index-format: use 'cache tree' over 'cached tree' 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (4 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 05/10] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 07/10] index-format: update preamble to cache tree extension Derrick Stolee via GitGitGadget ` (4 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 07/10] index-format: update preamble to cache tree extension 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (5 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 06/10] index-format: use 'cache tree' over 'cached tree' Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 08/10] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget ` (3 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 08/10] index-format: discuss recursion of cached-tree better 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (6 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 07/10] index-format: update preamble to cache tree extension Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 09/10] cache-tree: use ce_namelen() instead of strlen() René Scharfe via GitGitGadget ` (2 subsequent siblings) 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 09/10] cache-tree: use ce_namelen() instead of strlen() 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (7 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 08/10] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 ` René Scharfe via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 10/10] cache-tree: speed up consecutive path comparisons Derrick Stolee via GitGitGadget 2021-01-16 6:58 ` [PATCH v3 00/10] Cleanups around index operations Junio C Hamano 10 siblings, 0 replies; 53+ messages in thread From: René Scharfe via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, René Scharfe 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* [PATCH v3 10/10] cache-tree: speed up consecutive path comparisons 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (8 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 09/10] cache-tree: use ce_namelen() instead of strlen() René Scharfe via GitGitGadget @ 2021-01-07 16:32 ` Derrick Stolee via GitGitGadget 2021-01-16 6:58 ` [PATCH v3 00/10] Cleanups around index operations Junio C Hamano 10 siblings, 0 replies; 53+ messages in thread From: Derrick Stolee via GitGitGadget @ 2021-01-07 16:32 UTC (permalink / raw) To: git Cc: gitster, newren, Derrick Stolee, René Scharfe, Derrick Stolee, Derrick Stolee 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 ^ permalink raw reply related [flat|nested] 53+ messages in thread
* Re: [PATCH v3 00/10] Cleanups around index operations 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget ` (9 preceding siblings ...) 2021-01-07 16:32 ` [PATCH v3 10/10] cache-tree: speed up consecutive path comparisons Derrick Stolee via GitGitGadget @ 2021-01-16 6:58 ` Junio C Hamano 10 siblings, 0 replies; 53+ messages in thread From: Junio C Hamano @ 2021-01-16 6:58 UTC (permalink / raw) To: Derrick Stolee via GitGitGadget Cc: git, newren, Derrick Stolee, René Scharfe, Derrick Stolee "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. ^ permalink raw reply [flat|nested] 53+ messages in thread
end of thread, other threads:[~2021-01-16 7:08 UTC | newest] Thread overview: 53+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-12-30 19:26 [PATCH 0/8] Cleanups around index operations Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 1/8] tree-walk: report recursion counts Derrick Stolee via GitGitGadget 2020-12-30 19:42 ` Elijah Newren 2020-12-30 19:51 ` Derrick Stolee 2020-12-30 19:26 ` [PATCH 2/8] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget 2020-12-30 19:45 ` Elijah Newren 2020-12-30 19:26 ` [PATCH 3/8] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 4/8] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 5/8] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget 2020-12-30 19:48 ` Elijah Newren 2020-12-30 19:53 ` Derrick Stolee 2020-12-30 19:26 ` [PATCH 6/8] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget 2020-12-30 20:00 ` Elijah Newren 2020-12-30 19:26 ` [PATCH 7/8] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget 2020-12-30 19:26 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent Derrick Stolee via GitGitGadget 2020-12-30 20:14 ` Elijah Newren 2021-01-06 8:55 ` Junio C Hamano 2021-01-06 12:08 ` Derrick Stolee 2020-12-31 12:34 ` René Scharfe 2020-12-31 16:46 ` Derrick Stolee 2021-01-01 13:30 ` René Scharfe 2021-01-02 15:19 ` [PATCH] cache-tree: use ce_namelen() instead of strlen() René Scharfe 2021-01-04 1:26 ` Derrick Stolee 2021-01-05 12:05 ` Junio C Hamano 2021-01-02 15:31 ` [PATCH 8/8] cache-tree: avoid path comparison loop when silent René Scharfe 2020-12-30 20:19 ` [PATCH 0/8] Cleanups around index operations Elijah Newren 2020-12-30 20:24 ` Derrick Stolee 2021-01-04 3:09 ` [PATCH v2 0/9] " Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 1/9] tree-walk: report recursion counts Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 2/9] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 3/9] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 4/9] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 5/9] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 6/9] index-format: update preamble to cached tree extension Derrick Stolee via GitGitGadget 2021-01-07 2:10 ` Junio C Hamano 2021-01-07 11:51 ` Derrick Stolee 2021-01-07 20:12 ` Junio C Hamano 2021-01-07 21:26 ` Junio C Hamano 2021-01-04 3:09 ` [PATCH v2 7/9] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 8/9] cache-tree: use ce_namelen() instead of strlen() René Scharfe via GitGitGadget 2021-01-04 3:09 ` [PATCH v2 9/9] cache-tree: speed up consecutive path comparisons Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 00/10] Cleanups around index operations Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 01/10] tree-walk: report recursion counts Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 02/10] unpack-trees: add trace2 regions Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 03/10] cache-tree: use trace2 in cache_tree_update() Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 04/10] cache-tree: trace regions for I/O Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 05/10] cache-tree: trace regions for prime_cache_tree Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 06/10] index-format: use 'cache tree' over 'cached tree' Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 07/10] index-format: update preamble to cache tree extension Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 08/10] index-format: discuss recursion of cached-tree better Derrick Stolee via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 09/10] cache-tree: use ce_namelen() instead of strlen() René Scharfe via GitGitGadget 2021-01-07 16:32 ` [PATCH v3 10/10] cache-tree: speed up consecutive path comparisons Derrick Stolee via GitGitGadget 2021-01-16 6:58 ` [PATCH v3 00/10] Cleanups around index operations Junio C Hamano
Code repositories for project(s) associated with this public inbox https://80x24.org/mirrors/git.git This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).