unpack-trees: fix accidentally quadratic behavior
authorDavid Turner <redacted>
Fri, 22 Jan 2016 19:58:43 +0000 (14:58 -0500)
committerJunio C Hamano <redacted>
Fri, 22 Jan 2016 21:03:10 +0000 (13:03 -0800)
commita6720955f19ea10bf9569d04480deed25b1bccf7
treea1278d3dd1d02f69605e3d123cca6929fa9462a5
parentd9c2bd560e1e7a3d4654fb6ef3f9037ad337eb01
unpack-trees: fix accidentally quadratic behavior

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 <redacted>
Signed-off-by: Junio C Hamano <redacted>
unpack-trees.c
git clone https://git.99rst.org/PROJECT