Re: embedded newbies site.

[Szabolcs Nagy <nsz@port70.net>]

* LM <lmemsm@gmail.com> [2013-07-16 07:50:29 -0400]:
> design.  For instance, there are some negative mentions about the PCRE
> library, but when I tried to track down the cons for using it, I only found
> dated performance comparisons showing how poorly it worked if you don't use
> the newer JIT implementation.  What might be a positive for a system that's

the pcre thing is a design decision that makes the worst
case asymptotic complexity exponential, the jit does not
help and benchmarks are irrelevant: they are about the
common case

russ cox gave a clear explanation:

http://swtch.com/~rsc/regexp/regexp1.html
http://swtch.com/~rsc/regexp/regexp2.html
http://swtch.com/~rsc/regexp/regexp3.html
http://swtch.com/~rsc/regexp/regexp4.html

jit can only speed up the execution of a compiled pattern
by some constant factor, it is also much more complex and
has greater startup cost than a classic nfa based engine

to fix the problem you need a different algorithm
(of course then many of the pcre features would be hard
to support)

if the regex input source is not in your control then
you should worry about worst-case performance, not the
average case one

if you check out the pcre benchmarks you can note that
it explicitly states that no "pathological" patterns were
used (ie ones which would make backtracking exponential)

http://sljit.sourceforge.net/regex_perf.html

and this is where the issue turns into an ideological debate:
should we train people how to avoid pathological cases or
should the algorithm guarantee good worst case performance on
any bounded input
(ppl seems to prefer instant gratification and common case
performance usually, but in a safety critical environment
you care about the worst-case more)