From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 27942 invoked by alias); 22 Nov 2004 09:15:52 -0000 Mailing-List: contact glibc-bugs-regex-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Post: List-Help: , Sender: glibc-bugs-regex-owner@sources.redhat.com Received: (qmail 27857 invoked by uid 48); 22 Nov 2004 09:15:37 -0000 Date: Mon, 22 Nov 2004 09:15:00 -0000 Message-ID: <20041122091537.27856.qmail@sourceware.org> From: "bonzini at gnu dot org" To: glibc-bugs-regex@sources.redhat.com In-Reply-To: <20041118020600.558.vprodan.hosting@artstyle.ru> References: <20041118020600.558.vprodan.hosting@artstyle.ru> Reply-To: sourceware-bugzilla@sources.redhat.com Subject: [Bug regex/558] regcomp and regexec bug X-Bugzilla-Reason: CC X-SW-Source: 2004-11/txt/msg00053.txt.bz2 List-Id: ------- Additional Comments From bonzini at gnu dot org 2004-11-22 09:15 ------- It can be fixed by lowering for example .{1,5} to (.(.(.(..?)?)?)?)? instead of .?.?.?.?.? --- of course the brackets are not capturing, they're only there to show what is the question mark applied to. This has the property of making all the period nodes epsilon-transit to the end of the braced expression, rather than to the next period. The epsilon closure thus is much smaller. Another improvement is to use a special version of re_node_set_insert in calc_inveclosure, since we know that the node is being added at the end of the set. I have a patch to do that and it obtains a 30% improvement on this test case. It does not cure the complexity problem though, so I am not submitting it yet. -- What |Removed |Added ---------------------------------------------------------------------------- AssignedTo|gotom at debian dot or dot |bonzini at gnu dot org |jp | Status|NEW |ASSIGNED http://sources.redhat.com/bugzilla/show_bug.cgi?id=558 ------- You are receiving this mail because: ------- You are on the CC list for the bug, or are watching someone who is.