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"?
I seem to recall that this is always a problem (not only with lua) since
it forces way to many checks for potential matches (because
short substrings in the middle of the line also match ".*" and all
possibilities are tested separately).
IIRC, anchoring the pattern solves the problem of excessive run time for
such patterns. but maybe my memory fails me and this is wrong ...
j.
Joerg
_______________________________________________
fossil-users mailing list
[email protected]
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
--
Using Opera's revolutionary email client: http://www.opera.com/mail/
_______________________________________________
fossil-users mailing list
[email protected]
http://lists.fossil-scm.org:8080/cgi-bin/mailman/listinfo/fossil-users
