Re: Git performance on OS X

[David Kastrup <dak@gnu.org>]

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

> 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