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.
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.
Attached patch applied by Ulrich.