[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20130716135646.GP15323@port70.net>
Date: Tue, 16 Jul 2013 15:56:47 +0200
From: Szabolcs Nagy <nsz@...t70.net>
To: musl@...ts.openwall.com
Subject: Re: embedded newbies site.
* LM <lmemsm@...il.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)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
