{"thread":{"id":"41039","subject":"[PATCH] do_compare_entry: use already-computed path","startedAt":"2015-12-19T01:40:27Z","lastAt":"2015-12-21T17:17:23Z","messageCount":2,"participants":["David Turner","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"274738","messageId":"1450489227-4771-1-git-send-email-dturner@twopensource.com","threadId":"41039","inReplyTo":null,"subject":"[PATCH] do_compare_entry: use already-computed path","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-12-19T01:40:27Z","receivedAt":"2015-12-19T01:40:27Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"In traverse_trees, we generate the complete traverse path for a\ntraverse_info.  Later, in do_compare_entry, we used to go do a bunch\nof work to compare the traverse_info to a cache_entry's name without\ncomputing that path.  But since we already have that path, we don't\nneed to do all that work.  Instead, we can just stuff the generated\npath into the traverse_info, and do the comparison more directly.\nThis makes git checkout much faster -- about 25% on Twitter's\nmonorepo.  Deeper directory trees are likely to benefit more than\nshallower ones.\n\nSigned-off-by: David Turner <dturner@twopensource.com>\n---\n tree-walk.c    |  4 ++++\n tree-walk.h    |  1 +\n unpack-trees.c | 41 +++++++++++++++++++++++++++++++++++++++--\n 3 files changed, 44 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 6dccd2d..4cab3e1 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -329,6 +329,9 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)\n \t\tmake_traverse_path(base.buf, info->prev, &info->name);\n \t\tbase.buf[info->pathlen-1] = '/';\n \t\tstrbuf_setlen(&base, info->pathlen);\n+\t\tinfo->traverse_path = base.buf;\n+\t} else {\n+\t\tinfo->traverse_path = info->name.path;\n \t}\n \tfor (;;) {\n \t\tint trees_used;\n@@ -411,6 +414,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)\n \tfor (i = 0; i < n; i++)\n \t\tfree_extended_entry(tx + i);\n \tfree(tx);\n+\tinfo->traverse_path = NULL;\n \tstrbuf_release(&base);\n \treturn error;\n }\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 3b2f7bf..174eb61 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -59,6 +59,7 @@ enum follow_symlinks_result {\n enum follow_symlinks_result get_tree_entry_follow_symlinks(unsigned char *tree_sha1, const char *name, unsigned char *result, struct strbuf *result_path, unsigned *mode);\n \n struct traverse_info {\n+\tconst char *traverse_path;\n \tstruct traverse_info *prev;\n \tstruct name_entry name;\n \tint pathlen;\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 8e2032f..127dd4d 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -498,13 +498,14 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n  * itself - the caller needs to do the final check for the cache\n  * entry having more data at the end!\n  */\n-static int do_compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n+static int do_compare_entry_piecewise(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n {\n \tint len, pathlen, ce_len;\n \tconst char *ce_name;\n \n \tif (info->prev) {\n-\t\tint cmp = do_compare_entry(ce, info->prev, &info->name);\n+\t\tint cmp = do_compare_entry_piecewise(ce, info->prev,\n+\t\t\t\t\t\t     &info->name);\n \t\tif (cmp)\n \t\t\treturn cmp;\n \t}\n@@ -522,6 +523,42 @@ static int do_compare_entry(const struct cache_entry *ce, const struct traverse_\n \treturn df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);\n }\n \n+static int do_compare_entry(const struct cache_entry *ce,\n+\t\t\t    const struct traverse_info *info,\n+\t\t\t    const struct name_entry *n)\n+{\n+\tint len, pathlen, ce_len;\n+\tconst char *ce_name;\n+\tint cmp;\n+\n+\t/*\n+\t * If we have not precomputed the traverse path, it is quicker\n+\t * to avoid doing so.  But if we have precomputed it,\n+\t * it is quicker to use the precomputed version.\n+\t */\n+\tif (!info->traverse_path)\n+\t\treturn do_compare_entry_piecewise(ce, info, n);\n+\n+\tcmp = strncmp(ce->name, info->traverse_path, info->pathlen);\n+\tif (cmp)\n+\t\treturn cmp;\n+\n+\tpathlen = info->pathlen;\n+\tce_len = ce_namelen(ce);\n+\n+\tif (ce_len < pathlen) {\n+\t\tif (do_compare_entry_piecewise(ce, info, n) >= 0)\n+\t\t\tdie(\"pathlen\");\n+\t\treturn -1;\n+\t}\n+\n+\tce_len -= pathlen;\n+\tce_name = ce->name + pathlen;\n+\n+\tlen = tree_entry_len(n);\n+\treturn df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);\n+}\n+\n static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n {\n \tint cmp = do_compare_entry(ce, info, n);\n-- \n2.4.2.749.g730654d-twtrsrc\n"},{"id":"274808","messageId":"xmqqmvt3hgbg.fsf@gitster.mtv.corp.google.com","threadId":"41039","inReplyTo":"1450489227-4771-1-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH] do_compare_entry: use already-computed path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-21T17:17:23Z","receivedAt":"2015-12-21T17:17:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"David Turner <dturner@twopensource.com> writes:\n\n> In traverse_trees, we generate the complete traverse path for a\n> traverse_info.  Later, in do_compare_entry, we used to go do a bunch\n> of work to compare the traverse_info to a cache_entry's name without\n> computing that path.  But since we already have that path, we don't\n> need to do all that work.  Instead, we can just stuff the generated\n> path into the traverse_info, and do the comparison more directly.\n> This makes git checkout much faster -- about 25% on Twitter's\n> monorepo.  Deeper directory trees are likely to benefit more than\n> shallower ones.\n\nGreat work.\n\nIIRC, very early incarnation of the code avoided hard to build the\nfull path and that was why the path-component-wise comparison was\nused heavily in this codepath; at some point we just gave up, I\nthink.  If we can pass this flattened representation around to\ncallees that can make good use of it, that makes tons of sense.  I\nlike the basic idea of this change.\n\nI am bit worried that &base is passed to some function from here,\nand they do not take \"const struct strbuf *\", but a non-const one,\nallowing them to potentially modify its contents while this new\nfield in info struct wants to have the original base.buf, but I\ntrust you traced the callchain to make sure nothing wrong happens?\nEven if that is the case, I feel that this change is setting up a\ntrap somebody else would easily trigger unknowingly--I wonder how\nwe can avoid future breakages.\n\n\n> Signed-off-by: David Turner <dturner@twopensource.com>\n> ---\n>  tree-walk.c    |  4 ++++\n>  tree-walk.h    |  1 +\n>  unpack-trees.c | 41 +++++++++++++++++++++++++++++++++++++++--\n>  3 files changed, 44 insertions(+), 2 deletions(-)\n>\n> diff --git a/tree-walk.c b/tree-walk.c\n> index 6dccd2d..4cab3e1 100644\n> --- a/tree-walk.c\n> +++ b/tree-walk.c\n> @@ -329,6 +329,9 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)\n>  \t\tmake_traverse_path(base.buf, info->prev, &info->name);\n>  \t\tbase.buf[info->pathlen-1] = '/';\n>  \t\tstrbuf_setlen(&base, info->pathlen);\n> +\t\tinfo->traverse_path = base.buf;\n> +\t} else {\n> +\t\tinfo->traverse_path = info->name.path;\n>  \t}\n>  \tfor (;;) {\n>  \t\tint trees_used;\n> @@ -411,6 +414,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)\n>  \tfor (i = 0; i < n; i++)\n>  \t\tfree_extended_entry(tx + i);\n>  \tfree(tx);\n> +\tinfo->traverse_path = NULL;\n>  \tstrbuf_release(&base);\n>  \treturn error;\n>  }\n> diff --git a/tree-walk.h b/tree-walk.h\n> index 3b2f7bf..174eb61 100644\n> --- a/tree-walk.h\n> +++ b/tree-walk.h\n> @@ -59,6 +59,7 @@ enum follow_symlinks_result {\n>  enum follow_symlinks_result get_tree_entry_follow_symlinks(unsigned char *tree_sha1, const char *name, unsigned char *result, struct strbuf *result_path, unsigned *mode);\n>  \n>  struct traverse_info {\n> +\tconst char *traverse_path;\n>  \tstruct traverse_info *prev;\n>  \tstruct name_entry name;\n>  \tint pathlen;\n> diff --git a/unpack-trees.c b/unpack-trees.c\n> index 8e2032f..127dd4d 100644\n> --- a/unpack-trees.c\n> +++ b/unpack-trees.c\n> @@ -498,13 +498,14 @@ static int traverse_trees_recursive(int n, unsigned long dirmask,\n>   * itself - the caller needs to do the final check for the cache\n>   * entry having more data at the end!\n>   */\n> -static int do_compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n> +static int do_compare_entry_piecewise(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n>  {\n>  \tint len, pathlen, ce_len;\n>  \tconst char *ce_name;\n>  \n>  \tif (info->prev) {\n> -\t\tint cmp = do_compare_entry(ce, info->prev, &info->name);\n> +\t\tint cmp = do_compare_entry_piecewise(ce, info->prev,\n> +\t\t\t\t\t\t     &info->name);\n>  \t\tif (cmp)\n>  \t\t\treturn cmp;\n>  \t}\n> @@ -522,6 +523,42 @@ static int do_compare_entry(const struct cache_entry *ce, const struct traverse_\n>  \treturn df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);\n>  }\n>  \n> +static int do_compare_entry(const struct cache_entry *ce,\n> +\t\t\t    const struct traverse_info *info,\n> +\t\t\t    const struct name_entry *n)\n> +{\n> +\tint len, pathlen, ce_len;\n> +\tconst char *ce_name;\n> +\tint cmp;\n> +\n> +\t/*\n> +\t * If we have not precomputed the traverse path, it is quicker\n> +\t * to avoid doing so.  But if we have precomputed it,\n> +\t * it is quicker to use the precomputed version.\n> +\t */\n> +\tif (!info->traverse_path)\n> +\t\treturn do_compare_entry_piecewise(ce, info, n);\n> +\n> +\tcmp = strncmp(ce->name, info->traverse_path, info->pathlen);\n> +\tif (cmp)\n> +\t\treturn cmp;\n> +\n> +\tpathlen = info->pathlen;\n> +\tce_len = ce_namelen(ce);\n> +\n> +\tif (ce_len < pathlen) {\n> +\t\tif (do_compare_entry_piecewise(ce, info, n) >= 0)\n> +\t\t\tdie(\"pathlen\");\n> +\t\treturn -1;\n> +\t}\n> +\n> +\tce_len -= pathlen;\n> +\tce_name = ce->name + pathlen;\n> +\n> +\tlen = tree_entry_len(n);\n> +\treturn df_name_compare(ce_name, ce_len, S_IFREG, n->path, len, n->mode);\n> +}\n> +\n>  static int compare_entry(const struct cache_entry *ce, const struct traverse_info *info, const struct name_entry *n)\n>  {\n>  \tint cmp = do_compare_entry(ce, info, n);\n"}]}