From owner-freebsd-questions@FreeBSD.ORG Thu Oct 9 14:31:37 2008 Return-Path: Delivered-To: freebsd-questions@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 683E0106568B for ; Thu, 9 Oct 2008 14:31:37 +0000 (UTC) (envelope-from talon@lpthe.jussieu.fr) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by mx1.freebsd.org (Postfix) with ESMTP id C71328FC08 for ; Thu, 9 Oct 2008 14:31:36 +0000 (UTC) (envelope-from talon@lpthe.jussieu.fr) Received: from parthe.lpthe.jussieu.fr (parthe.lpthe.jussieu.fr [134.157.10.1]) by shiva.jussieu.fr (8.14.3/jtpda-5.4) with ESMTP id m99EVBQI060791 for ; Thu, 9 Oct 2008 16:31:22 +0200 (CEST) X-Ids: 166 Received: from niobe.lpthe.jussieu.fr (niobe.lpthe.jussieu.fr [134.157.10.41]) by parthe.lpthe.jussieu.fr (Postfix) with ESMTP id 0FA2F8A054 for ; Thu, 9 Oct 2008 16:31:10 +0200 (CEST) Received: by niobe.lpthe.jussieu.fr (Postfix, from userid 2005) id F180110A; Thu, 9 Oct 2008 16:31:09 +0200 (CEST) Date: Thu, 9 Oct 2008 16:31:09 +0200 From: Michel Talon To: freebsd-questions@freebsd.org Message-ID: <20081009143109.GA64471@lpthe.jussieu.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.3i X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.0 (shiva.jussieu.fr [134.157.0.166]); Thu, 09 Oct 2008 16:31:22 +0200 (CEST) X-Virus-Scanned: ClamAV 0.93.3/8399/Thu Oct 9 14:27:14 2008 on shiva.jussieu.fr X-Virus-Status: Clean X-Miltered: at jchkmail.jussieu.fr with ID 48EE15AF.01D by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)! X-j-chkmail-Enveloppe: 48EE15AF.01D/134.157.10.1/parthe.lpthe.jussieu.fr/parthe.lpthe.jussieu.fr/ X-j-chkmail-Score: MSGID : 48EE15AF.01D on jchkmail.jussieu.fr : j-chkmail score : . : R=. U=. O=. B=0.027 -> S=0.027 X-j-chkmail-Status: Ham Subject: Re: performance problem in regex X-BeenThere: freebsd-questions@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: User questions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 09 Oct 2008 14:31:37 -0000 fulvio_esposito wrote: > I've got some performance hit using regex in libc on freebsd 6.3 Knowing that this regex implementation uses an NFA algorithm, while a DFA algorithm should be preferred, this is no big surprise. You can read the following references on the subject: http://swtch.com/~rsc/regexp/regexp1.html http://www.dmst.aueb.gr/dds/pubs/jrnl/2007-SPANDE-FIRE/html/KS07.html In particular the second is written by a FreeBSD developer and states: "The Spencer engine proved to have poor performance and was excluded from the graphs.", where the Spencer engine is precisely the one in FreeBSD. -- Michel TALON