Bug 8 - Quadratic behavior on regex with * at the beginning
Summary: Quadratic behavior on regex with * at the beginning
Status: RESOLVED FIXED
Alias: None
Product: glibc
Classification: Unclassified
Component: regex (show other bugs)
Version: unspecified
: P2 normal
Target Milestone: ---
Assignee: Paolo Bonzini
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2004-02-02 14:59 UTC by Paolo Bonzini
Modified: 2019-04-10 12:35 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:
fweimer: security+


Attachments
Proposed patch (1.42 KB, patch)
2004-02-02 15:00 UTC, Paolo Bonzini
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Paolo Bonzini 2004-02-02 14:59:59 UTC
perl -e 'print ("a" x 10000) . "b\n"' | (time sed -n 's/a*b//') 
real    0m1.986s 
user    0m1.900s 
sys     0m0.010s 
 
perl -e 'print ("a" x 20000) . "b\n"' | (time sed -n 's/a*b//') 
real    0m7.977s 
user    0m7.720s 
sys     0m0.030s 
 
When searching forward, the fastmap should be complemented by some heuristic 
to skip optional parts of the regex, like the "a"s in the above testcase.
Comment 1 Paolo Bonzini 2004-02-02 15:00:48 UTC
Created attachment 2 [details]
Proposed patch


2004-02-02  Paolo Bonzini  <bonzini@gnu.org>

	* posix/regexec.c (check_matching): Add P_MATCH_FIRST
	parameter.
	(re_search_internal): Pass new parameter to check_matching.
	(check_matching): Unless a parenthesized group is found at the
	beginning of the regexp, advance P_MATCH_FIRST until we entered
	a state different from the initial state.
Comment 2 Paolo Bonzini 2004-02-03 09:02:13 UTC
Attached patch applied by Ulrich.