On Mon, Jan 28, 2013 at 06:09:57PM +0100, j. van den hoff wrote: > On Mon, 28 Jan 2013 17:34:44 +0100, Joerg Sonnenberger > <[email protected]> wrote: > > >On Mon, Jan 28, 2013 at 08:50:56AM -0500, Richard Hipp wrote: > >>The regular expression matching in > >>www.fossil-scm.org/fossil/artifact/c8fb75a1615f is also > >>lightweight and it > >>supports | and it is usually as fast or faster than grep in my tests > >>(though there are some cases for which grep is faster). The regexp.c in > >>fossil uses a NFA which gives worst case performance of O(NM) where N is > >>the size of the input text to be matched and M is the size of > >>the regular > >>expression. Perl regular expressions and lua-regexp.c take exponential > >>time for some (admittedly obscure) regular expressions. On the > >>other hand, > >>Perl regular expressions are more complete, and both Lua and > >>Perl allow you > >>to do substitutions, which the regexp.c file in Fossil does not. > > > >The Lua implementation starts to perform very badly as soon as you have > >wild cards at the beginning of the pattern. Those aren't even obscure... > > just a guess: you did not "anchor" the pattern, i.e. you used > something like ".*foo" instead of "^.*foo"?
Anchoring doesn't help if you want to explicitly match wild card chars at or near the beginning. With a NFA or DFA based implementation, it will add some processing time, but the linear performance is still guaranteed. Joerg _______________________________________________ fossil-users mailing list [email protected] http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
