From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/3652 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: embedded newbies site. Date: Tue, 16 Jul 2013 15:56:47 +0200 Message-ID: <20130716135646.GP15323@port70.net> References: <1373940214.3719.5@driftwood> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1373983018 30510 80.91.229.3 (16 Jul 2013 13:56:58 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 16 Jul 2013 13:56:58 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-3656-gllmg-musl=m.gmane.org@lists.openwall.com Tue Jul 16 15:57:00 2013 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1Uz5kS-00024t-Im for gllmg-musl@plane.gmane.org; Tue, 16 Jul 2013 15:57:00 +0200 Original-Received: (qmail 10193 invoked by uid 550); 16 Jul 2013 13:56:59 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 10185 invoked from network); 16 Jul 2013 13:56:59 -0000 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:3652 Archived-At: * LM [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)