[PATCH] speed up grouping subexpressions by ~30%

[Paolo Bonzini]

This patch includes several speedups that total to a 30% speedup of my 
new favorite test s|\(.*\)/\(.*\)|\1 \2|.  On a 48 MB test file, my 
results are (user times):

without patch    158.77 seconds
with patch       109.14 seconds (-31.26%)

There is also a measurable speedup in sed's `make check'.  These figures 
however include the time spent in sh, cmp etc.:

without patch    39.12 seconds
with patch       36.42 seconds (-7.23%)

The speedups are obtained by six smaller changes.  Items 1-5 are worth 
1-2% each (6.4% overall), while item 6 alone is responsible for the 
remaining 25% performance improvement.  All changes were timed 
separately (on top of each other).

1) Doing expensive checks in check_node_accept after trivial rejections. 
(saves over 50% of the time spent in check_node_accept).

2) Simplifying some hairy code in proceed_next_node (saves 25% of the 
time spent in proceed_next_node).

3) Marking several functions as pure.

4) Using unsigned iteration variables in re_node_set_contains to make 
division by 2 less expensive (this is because of C's rounding rules; 
yes, it is worth 15% of the time spent in re_node_set_contains).

5) Caching in each DFA state the non-epsilon nodes, and avoiding skips 
of epsilon nodes in build_sifted_states and check_arrival, again worth 
over 30% of the time spent in build_sifted_states (the other occurrence 
of this optimization is not high enough in the profile to be measurable).

6) Caching the overall inveclosure of several nodes: the top function in 
the profile is re_node_set_add_intersect, which is called from 
add_epsilon_src_nodes's loop.  If however we do the merges first and a 
single intersection later, we can kick it several places back: for this 
to be profitable we store these merges into a hash table, which I did 
using the same functions and table that is used to store DFA states. 
The initialization is done lazily.

Tested with the glibc and sed testsuites, respectively on powerpc-linux 
and powerpc-darwin.

The patch is on top of patch 1 from my previous submissions (i.e. 
speeding up OP_PERIOD in single-byte character sets) and on bug #501's 
attached patch.  It should however apply on CVS glibc cleanly except for 
offsets.

Paolo
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: misc-speedups.patch
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20041209/d866f3f3/attachment.ksh>