{"thread":{"id":"41243","subject":"[PATCH v3] unpack-trees: fix accidentally quadratic behavior","startedAt":"2016-01-22T19:58:43Z","lastAt":"2016-01-22T19:58:43Z","messageCount":1,"participants":["David Turner"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"276572","messageId":"1453492723-4907-1-git-send-email-dturner@twopensource.com","threadId":"41243","inReplyTo":null,"subject":"[PATCH v3] unpack-trees: fix accidentally quadratic behavior","fromName":"David Turner","fromEmail":"dturner@twopensource.com","sentAt":"2016-01-22T19:58:43Z","receivedAt":"2016-01-22T19:58:43Z","isPatch":true,"sender":{"key":"novalis@novalis.org","avatar":"https://avatars.githubusercontent.com/u/77003?v=4"},"body":"While unpacking trees (e.g. during git checkout), when we hit a cache\nentry that's past and outside our path, we cut off iteration.\n\nThis provides about a 45% speedup on git checkout between master and\nmaster^20000 on Twitter's monorepo.  Speedup in general will depend on\nrepostitory structure, number of changes, and packfile packing\ndecisions.\n\nSigned-off-by: David Turner <dturner@twopensource.com>\n---\nA colleague pointed out that the info->prev test was unnecessary as\nce_in_traverse_path already does that.\n---\n unpack-trees.c | 13 ++++++++++++-\n 1 file changed, 12 insertions(+), 1 deletion(-)\n\ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 5f541c2..9f55cc2 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -695,8 +695,19 @@ static int find_cache_pos(struct traverse_info *info,\n \t\t\t\t++o->cache_bottom;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!ce_in_traverse_path(ce, info))\n+\t\tif (!ce_in_traverse_path(ce, info)) {\n+\t\t\t/*\n+\t\t\t * Check if we can skip future cache checks\n+\t\t\t * (because we're already past all possible\n+\t\t\t * entries in the traverse path).\n+\t\t\t */\n+\t\t\tif (info->traverse_path) {\n+\t\t\t\tif (strncmp(ce->name, info->traverse_path,\n+\t\t\t\t\t    info->pathlen) > 0)\n+\t\t\t\t\tbreak;\n+\t\t\t}\n \t\t\tcontinue;\n+\t\t}\n \t\tce_name = ce->name + pfxlen;\n \t\tce_slash = strchr(ce_name, '/');\n \t\tif (ce_slash)\n-- \n2.4.2.749.g730654d-twtrsrc\n"}]}