Re: Git performance on OS X

Linus Torvalds [off-list ref] writes:

On Sat, 19 Apr 2008, Linus Torvalds wrote:

quoted

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