{"thread":{"id":"41056","subject":"[PATCH v2 1/2] traverse_info: make mostly const","startedAt":"2015-12-21T22:34:18Z","lastAt":"2016-01-05T19:40:58Z","messageCount":9,"participants":["David Turner","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"274830","messageId":"1450737260-15965-1-git-send-email-dturner@twopensource.com","threadId":"41056","inReplyTo":null,"subject":"[PATCH v2 0/2] do_compare_entry: use already-computed path","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-12-21T22:34:18Z","receivedAt":"2015-12-21T22:34:18Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"This version strdups the path to avoid it getting mutated.  Problem\nnoted by Junio.\n\n\nDavid Turner (2):\n  traverse_info: make mostly const\n  do_compare_entry: use already-computed path\n\n builtin/merge-tree.c     |  2 +-\n cache-tree.c             |  4 ++--\n cache-tree.h             |  2 +-\n t/t4010-diff-pathspec.sh |  2 +-\n tree-walk.c              |  9 +++++++-\n tree-walk.h              |  5 +++--\n unpack-trees.c           | 55 ++++++++++++++++++++++++++++++++++++++++--------\n 7 files changed, 62 insertions(+), 17 deletions(-)\n\n-- \n2.4.2.749.g730654d-twtrsrc\n"},{"id":"274829","messageId":"1450737260-15965-2-git-send-email-dturner@twopensource.com","threadId":"41056","inReplyTo":"1450737260-15965-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v2 1/2] traverse_info: make mostly const","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-12-21T22:34:19Z","receivedAt":"2015-12-21T22:34:19Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"We don't usually modify traverse_info, so make it const across a wide\nrange of functions.\n\nSigned-off-by: David Turner <dturner@twopensource.com>\n---\n builtin/merge-tree.c     |  2 +-\n cache-tree.c             |  4 ++--\n cache-tree.h             |  2 +-\n t/t4010-diff-pathspec.sh |  2 +-\n tree-walk.c              |  2 +-\n tree-walk.h              |  4 ++--\n unpack-trees.c           | 14 +++++++-------\n 7 files changed, 15 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/merge-tree.c b/builtin/merge-tree.c\nindex d4f0cbd..6de2da9 100644\n--- a/builtin/merge-tree.c\n+++ b/builtin/merge-tree.c\n@@ -304,7 +304,7 @@ static void unresolved(const struct traverse_info *info, struct name_entry n[3])\n  * The successful merge rules are the same as for the three-way merge\n  * in git-read-tree.\n  */\n-static int threeway_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *info)\n+static int threeway_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, const struct traverse_info *info)\n {\n \t/* Same in both? */\n \tif (same_entry(entry+1, entry+2) || both_empty(entry+1, entry+2)) {\ndiff --git a/cache-tree.c b/cache-tree.c\nindex a59e6f1..0fd2ab5 100644\n--- a/cache-tree.c\n+++ b/cache-tree.c\n@@ -694,7 +694,7 @@ void prime_cache_tree(struct index_state *istate, struct tree *tree)\n  *     above us, and find ourselves in there.\n  */\n static struct cache_tree *find_cache_tree_from_traversal(struct cache_tree *root,\n-\t\t\t\t\t\t\t struct traverse_info *info)\n+\t\t\t\t\t\t\t const struct traverse_info *info)\n {\n \tstruct cache_tree *our_parent;\n \n@@ -706,7 +706,7 @@ static struct cache_tree *find_cache_tree_from_traversal(struct cache_tree *root\n \n int cache_tree_matches_traversal(struct cache_tree *root,\n \t\t\t\t struct name_entry *ent,\n-\t\t\t\t struct traverse_info *info)\n+\t\t\t\t const struct traverse_info *info)\n {\n \tstruct cache_tree *it;\n \ndiff --git a/cache-tree.h b/cache-tree.h\nindex 41c5746..7f99cc8 100644\n--- a/cache-tree.h\n+++ b/cache-tree.h\n@@ -50,6 +50,6 @@ int write_index_as_tree(unsigned char *sha1, struct index_state *index_state, co\n int write_cache_as_tree(unsigned char *sha1, int flags, const char *prefix);\n void prime_cache_tree(struct index_state *, struct tree *);\n \n-extern int cache_tree_matches_traversal(struct cache_tree *, struct name_entry *ent, struct traverse_info *info);\n+extern int cache_tree_matches_traversal(struct cache_tree *, struct name_entry *ent, const struct traverse_info *info);\n \n #endif\ndiff --git a/t/t4010-diff-pathspec.sh b/t/t4010-diff-pathspec.sh\nindex 43c488b..ad91130 100755\n--- a/t/t4010-diff-pathspec.sh\n+++ b/t/t4010-diff-pathspec.sh\n@@ -52,7 +52,7 @@ cat >expected <<\\EOF\n EOF\n test_expect_success \\\n     '\"*file1\" should show path1/file1' \\\n-    'git diff-index --cached $tree -- \"*file1\" >current &&\n+    'echo \"$tree\" && git diff-index --cached $tree -- \"*file1\" >current &&\n      compare_diff_raw current expected'\n \n cat >expected <<\\EOF\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 6dccd2d..5eee262 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -301,7 +301,7 @@ static void free_extended_entry(struct tree_desc_x *t)\n }\n \n static inline int prune_traversal(struct name_entry *e,\n-\t\t\t\t  struct traverse_info *info,\n+\t\t\t\t  const struct traverse_info *info,\n \t\t\t\t  struct strbuf *base,\n \t\t\t\t  int still_interesting)\n {\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 3b2f7bf..f0a457b 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -37,7 +37,7 @@ int tree_entry(struct tree_desc *, struct name_entry *);\n void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);\n \n struct traverse_info;\n-typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, struct traverse_info *);\n+typedef int (*traverse_callback_t)(int n, unsigned long mask, unsigned long dirmask, struct name_entry *entry, const struct traverse_info *);\n int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info);\n \n enum follow_symlinks_result {\n@@ -59,7 +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-\tstruct traverse_info *prev;\n+\tconst struct traverse_info *prev;\n \tstruct name_entry name;\n \tint pathlen;\n \tstruct pathspec *pathspec;\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 8e2032f..d4bedac 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -422,7 +422,7 @@ static int unpack_index_entry(struct cache_entry *ce,\n \treturn ret;\n }\n \n-static int find_cache_pos(struct traverse_info *, const struct name_entry *);\n+static int find_cache_pos(const struct traverse_info *, const struct name_entry *);\n \n static void restore_cache_bottom(struct traverse_info *info, int bottom)\n {\n@@ -453,7 +453,7 @@ static int switch_cache_bottom(struct traverse_info *info)\n static int traverse_trees_recursive(int n, unsigned long dirmask,\n \t\t\t\t    unsigned long df_conflicts,\n \t\t\t\t    struct name_entry *names,\n-\t\t\t\t    struct traverse_info *info)\n+\t\t\t\t    const struct traverse_info *info)\n {\n \tint i, ret, bottom;\n \tstruct tree_desc t[MAX_UNPACK_TREES];\n@@ -637,7 +637,7 @@ static int unpack_failed(struct unpack_trees_options *o, const char *message)\n  * anything, as we will want to match it when the traversal descends into\n  * the directory.\n  */\n-static int find_cache_pos(struct traverse_info *info,\n+static int find_cache_pos(const struct traverse_info *info,\n \t\t\t  const struct name_entry *p)\n {\n \tint pos;\n@@ -692,7 +692,7 @@ static int find_cache_pos(struct traverse_info *info,\n \treturn -1;\n }\n \n-static struct cache_entry *find_cache_entry(struct traverse_info *info,\n+static struct cache_entry *find_cache_entry(const struct traverse_info *info,\n \t\t\t\t\t    const struct name_entry *p)\n {\n \tint pos = find_cache_pos(info, p);\n@@ -704,7 +704,7 @@ static struct cache_entry *find_cache_entry(struct traverse_info *info,\n \t\treturn NULL;\n }\n \n-static void debug_path(struct traverse_info *info)\n+static void debug_path(const struct traverse_info *info)\n {\n \tif (info->prev) {\n \t\tdebug_path(info->prev);\n@@ -725,7 +725,7 @@ static void debug_unpack_callback(int n,\n \t\t\t\t  unsigned long mask,\n \t\t\t\t  unsigned long dirmask,\n \t\t\t\t  struct name_entry *names,\n-\t\t\t\t  struct traverse_info *info)\n+\t\t\t\t  const struct traverse_info *info)\n {\n \tint i;\n \tprintf(\"* unpack mask %lu, dirmask %lu, cnt %d \",\n@@ -736,7 +736,7 @@ static void debug_unpack_callback(int n,\n \t\tdebug_name_entry(i, names + i);\n }\n \n-static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, struct traverse_info *info)\n+static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, struct name_entry *names, const struct traverse_info *info)\n {\n \tstruct cache_entry *src[MAX_UNPACK_TREES + 1] = { NULL, };\n \tstruct unpack_trees_options *o = info->data;\n-- \n2.4.2.749.g730654d-twtrsrc\n"},{"id":"274831","messageId":"1450737260-15965-3-git-send-email-dturner@twopensource.com","threadId":"41056","inReplyTo":"1450737260-15965-1-git-send-email-dturner@twopensource.com","subject":"[PATCH v2 2/2] do_compare_entry: use already-computed path","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-12-21T22:34:20Z","receivedAt":"2015-12-21T22:34:20Z","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 put the generated\npath into the traverse_info, and do the comparison more directly.\n\nWe copy the path because prune_traversal might mutate `base`. This\ndoesn't happen in any codepaths where do_compare_entry is called,\nbut it's better to be safe.\n\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    |  7 +++++++\n tree-walk.h    |  1 +\n unpack-trees.c | 41 +++++++++++++++++++++++++++++++++++++++--\n 3 files changed, 47 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 5eee262..7a0419e 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -320,6 +320,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)\n \tstruct tree_desc_x *tx = xcalloc(n, sizeof(*tx));\n \tstruct strbuf base = STRBUF_INIT;\n \tint interesting = 1;\n+\tchar *traverse_path;\n \n \tfor (i = 0; i < n; i++)\n \t\ttx[i].d = t[i];\n@@ -329,7 +330,11 @@ 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\ttraverse_path = xstrndup(base.buf, info->pathlen);\n+\t} else {\n+\t\ttraverse_path = xstrndup(info->name.path, info->pathlen);\n \t}\n+\tinfo->traverse_path = traverse_path;\n \tfor (;;) {\n \t\tint trees_used;\n \t\tunsigned long mask, dirmask;\n@@ -411,6 +416,8 @@ 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+\tfree(traverse_path);\n+\tinfo->traverse_path = NULL;\n \tstrbuf_release(&base);\n \treturn error;\n }\ndiff --git a/tree-walk.h b/tree-walk.h\nindex f0a457b..a94357a 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 \tconst struct traverse_info *prev;\n \tstruct name_entry name;\n \tint pathlen;\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex d4bedac..37328de 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":"274832","messageId":"1450739714.3892.2.camel@twopensource.com","threadId":"41056","inReplyTo":"1450737260-15965-2-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH v2 1/2] traverse_info: make mostly const","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-12-21T23:15:14Z","receivedAt":"2015-12-21T23:15:14Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2015-12-21 at 17:34 -0500, David Turner wrote:\n> We don't usually modify traverse_info, so make it const across a wide\n> range of functions.\n> \n> Signed-off-by: David Turner <dturner@twopensource.com>\n> ---\n>  builtin/merge-tree.c     |  2 +-\n>  cache-tree.c             |  4 ++--\n>  cache-tree.h             |  2 +-\n>  t/t4010-diff-pathspec.sh |  2 +-\n\nno, that change was not necessary at all.  \n"},{"id":"274833","messageId":"xmqqzix3e61h.fsf@gitster.mtv.corp.google.com","threadId":"41056","inReplyTo":"1450737260-15965-1-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH v2 0/2] do_compare_entry: use already-computed path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-21T23:27:38Z","receivedAt":"2015-12-21T23:27:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thanks.  Does the number still stay at 25% improvement?\n"},{"id":"274834","messageId":"1450740784.3892.3.camel@twopensource.com","threadId":"41056","inReplyTo":"xmqqzix3e61h.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH v2 0/2] do_compare_entry: use already-computed path","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-12-21T23:33:04Z","receivedAt":"2015-12-21T23:33:04Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2015-12-21 at 15:27 -0800, Junio C Hamano wrote:\n> Thanks.  Does the number still stay at 25% improvement?\n\nYes.\n"},{"id":"274841","messageId":"1450758362.3892.7.camel@twopensource.com","threadId":"41056","inReplyTo":"CAPc5daW4ru0j4Zd3ynnRcG8df7sZ9ZuVHu8mz2rxVonZpyE4Gw@mail.gmail.com","subject":"Re: [PATCH v2 0/2] do_compare_entry: use already-computed path","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2015-12-22T04:26:02Z","receivedAt":"2015-12-22T04:26:02Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2015-12-21 at 15:34 -0800, Junio C Hamano wrote:\n> Great. Thanks, will queue w/o 1/2 (though I do not think it would\n> hurt).\n> \n> On Mon, Dec 21, 2015 at 3:33 PM, David Turner <\n> dturner@twopensource.com> wrote:\n> > On Mon, 2015-12-21 at 15:27 -0800, Junio C Hamano wrote:\n> > > Thanks.  Does the number still stay at 25% improvement?\n> > \n> > Yes.\n\nBTW, that function, via ce_in_traverse_path, gets called about 40\nmillion times when switching (checking out) between master and a branch\nthat's a few months old (and that contains relatively small changes\nfrom master-as-of-then. Our repo only has approximately a quarter\n-million files.  This seems somewhat unreasonable to me, but I haven't\nreally looked into what's going on. Do you happen to know why this is\nand whether it is likely to be a bug?\n"},{"id":"274907","messageId":"xmqq60zqe2pu.fsf@gitster.mtv.corp.google.com","threadId":"41056","inReplyTo":"1450758362.3892.7.camel@twopensource.com","subject":"Re: [PATCH v2 0/2] do_compare_entry: use already-computed path","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-12-22T18:51:41Z","receivedAt":"2015-12-22T18:51:41Z","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> On Mon, 2015-12-21 at 15:34 -0800, Junio C Hamano wrote:\n>> Great. Thanks, will queue w/o 1/2 (though I do not think it would\n>> hurt).\n>> \n>> On Mon, Dec 21, 2015 at 3:33 PM, David Turner <\n>> dturner@twopensource.com> wrote:\n>> > On Mon, 2015-12-21 at 15:27 -0800, Junio C Hamano wrote:\n>> > > Thanks.  Does the number still stay at 25% improvement?\n>> > \n>> > Yes.\n>\n> BTW, that function, via ce_in_traverse_path, gets called about 40\n> million times when switching (checking out) between master and a\n> branch that's a few months old (and that contains relatively small\n> changes from master-as-of-then. Our repo only has approximately a\n> quarter -million files.  This seems somewhat unreasonable to me,\n> but I haven't really looked into what's going on.  Do you happen\n> to know why this is and whether it is likely to be a bug?\n\nThat does sound excessive; smells like somebody is being overly\ncautious (i.e. a performance bug).\n\nWe might be seeing something similar to what e53e6b44 observed and\nattempted to correct.  I dunno.\n"},{"id":"275395","messageId":"1452022858.3892.48.camel@twopensource.com","threadId":"41056","inReplyTo":"1450737260-15965-3-git-send-email-dturner@twopensource.com","subject":"Re: [PATCH v2 2/2] do_compare_entry: use already-computed path","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-01-05T19:40:58Z","receivedAt":"2016-01-05T19:40:58Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"On Mon, 2015-12-21 at 17:34 -0500, David Turner wrote:\n> In traverse_trees, we generate the complete traverse path for a\n\nPlease replace with the attached version, which eliminates an\nunnecessary check.\n\nFrom 520cfbff15faa6de50d37b4a476b21dbe1598433 Mon Sep 17 00:00:00 2001\nFrom: David Turner <dturner@twopensource.com>\nDate: Mon, 21 Dec 2015 17:34:20 -0500\nSubject: [PATCH] do_compare_entry: use already-computed path\n\nIn 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 put the generated\npath into the traverse_info, and do the comparison more directly.\n\nWe copy the path because prune_traversal might mutate `base`. This\ndoesn't happen in any codepaths where do_compare_entry is called,\nbut it's better to be safe.\n\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>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n tree-walk.c    |  7 +++++++\n tree-walk.h    |  1 +\n unpack-trees.c | 38 ++++++++++++++++++++++++++++++++++++--\n 3 files changed, 44 insertions(+), 2 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 6dccd2d..cd4bb2c 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -320,6 +320,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)\n \tstruct tree_desc_x *tx = xcalloc(n, sizeof(*tx));\n \tstruct strbuf base = STRBUF_INIT;\n \tint interesting = 1;\n+\tchar *traverse_path;\n \n \tfor (i = 0; i < n; i++)\n \t\ttx[i].d = t[i];\n@@ -329,7 +330,11 @@ 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\ttraverse_path = xstrndup(base.buf, info->pathlen);\n+\t} else {\n+\t\ttraverse_path = xstrndup(info->name.path, info->pathlen);\n \t}\n+\tinfo->traverse_path = traverse_path;\n \tfor (;;) {\n \t\tint trees_used;\n \t\tunsigned long mask, dirmask;\n@@ -411,6 +416,8 @@ 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+\tfree(traverse_path);\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..5f541c2 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,39 @@ 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\treturn -1;\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\n"}]}