Re: Git performance on OS X

From: David Kastrup <dak@gnu.org>
Date: Apr 20, 2008, 16:17 UTC
Message-ID: <85tzhwv6tt.fsf@lola.goethe.zz>
In-Reply-To: <alpine.LFD.1.10.0804191422480.2779@woody.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

Show 16 quoted lines

> On Sat, 19 Apr 2008, Linus Torvalds wrote:
>> 
>> Notice how this patch doesn' actually change the fundamental O(n^2) 
>> behaviour, but it makes it much cheaper by generally avoiding the 
>> expensive 'fnmatch' and 'strlen/strncmp' when they are obviously not 
>> needed.
>
> Side note: on the kenrel tree, it makes the (insane!) operation 
>
> 	git add $(git ls-files)
>
> go from 49 seconds down to 17 sec. So it does make a huge difference
> for me, but I also want to point out that this really isn't a sane
> operation to do (I also think that 17 sec is totally unacceptable, but
> I cannot find it in me to care, since I don't think this is an
> operation that anybody should ever do!)

It is my opinion that git should likely presort the patterns (not just here), and should traverse the trees alphabetically. In that case, a merge-like algorithm will pretty much do the trick in O(n), with O(n lg n) preprocessing cost.

Presorting can only be done approximately in the case of wildcards: for those, we have two relevant points in the sort order: one where it can start matching, one where it can't match anymore.

The easiest way to make this more efficient would be to retain the O(n*m) algorithm, but presort the patterns and let them trickle head-first into the O(m) pattern list only when they start having a chance of matching, and remove them from the O(m) list once a non-match has passed them alphabetically for good.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum