Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
