Re: [PATCH] unpack-trees: fix accidentally quadratic behavior

2016-01-21 Thread Junio C Hamano
David Turner writes: >> The first break is correct, but I am not sure about the "else if" >> part. Shouldn't it be doing something similar to the logic to "keep >> looking" that talks about "t-i", "t" and "t/a" at the end of the >> loop? > > Rather than doing more complicated logic, let's just d

Re: [PATCH] unpack-trees: fix accidentally quadratic behavior

2016-01-21 Thread David Turner
On Thu, 2016-01-21 at 11:51 -0800, Junio C Hamano wrote: > David Turner writes: > > > On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote: > > > David Turner writes: > > > > > > > While unpacking trees (e.g. during git checkout), when we hit a > > > > cache > > > > entry that's past and out

Re: [PATCH] unpack-trees: fix accidentally quadratic behavior

2016-01-21 Thread Junio C Hamano
David Turner writes: > On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote: >> David Turner writes: >> >> > 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% spee

Re: [PATCH] unpack-trees: fix accidentally quadratic behavior

2016-01-21 Thread David Turner
On Wed, 2016-01-20 at 20:58 -0800, Junio C Hamano wrote: > David Turner writes: > > > 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 mast

Re: [PATCH] unpack-trees: fix accidentally quadratic behavior

2016-01-20 Thread Junio C Hamano
David Turner writes: > 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^2 on Twitter's monorepo. Speedup in general will depe

[PATCH] unpack-trees: fix accidentally quadratic behavior

2016-01-20 Thread David Turner
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^2 on Twitter's monorepo. Speedup in general will depend on repostitory structure, num