[BZ558] Part 1: more efficient lowering of {m,n}
Paolo Bonzini
paolo.bonzini@lu.unisi.ch
Tue Nov 23 12:33:00 GMT 2004
BZ558's profile shows that most of the time is taken by node set
operations in calc_eclosure and calc_inveclosure.
The calc_eclosure part is fixed by this patch. Braced groups are
lowered differently: for example .{1,5} can become (.(.(.(..?)?)?)?)?
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. On a .{1,2048} testcase, you can
see that memory consumption and time is cut by 50%.
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. The best thing to do would be to compute the inverse
epsilon closure lazily, but I have not gotten round to doing that yet.
Patch at
http://sources.redhat.com/bugzilla/attachment.cgi?id=289&action=view
Paolo
More information about the Libc-alpha
mailing list