[PATCH] unpack-trees: fix accidentally quadratic behavior

[David Turner <dturner@twopensource.com>]

While unpacking trees (e.g. during git checkout), when we hit a cache
entry that's past and outside our path, we cut off iteration.

This provides about a 45% speedup on git checkout between master and
master^20000 on Twitter's monorepo.  Speedup in general will depend on
repostitory structure, number of changes, and packfile packing
decisions.

Signed-off-by: David Turner <dturner@twopensource.com>
---
 unpack-trees.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index 5f541c2..b18a611 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -695,8 +695,25 @@ static int find_cache_pos(struct traverse_info *info,
 				++o->cache_bottom;
 			continue;
 		}
-		if (!ce_in_traverse_path(ce, info))
+		if (!ce_in_traverse_path(ce, info)) {
+			/*
+			 * Check if we can skip future cache checks
+			 * (because we're already past all possible
+			 * entries in the traverse path).
+			 */
+			if (info->prev && info->traverse_path) {
+				int prefix_cmp = strncmp(ce->name, info->traverse_path, info->pathlen);
+				if (prefix_cmp > 0)
+					break;
+				else if (prefix_cmp == 0 &&
+					 ce_namelen(ce) >= info->pathlen &&
+					 strcmp(ce->name + info->pathlen,
+						 info->name.path) > 0) {
+					break;
+				}
+			}
 			continue;
+		}
 		ce_name = ce->name + pfxlen;
 		ce_slash = strchr(ce_name, '/');
 		if (ce_slash)
-- 
2.4.2.749.g730654d-twtrsrc