This is the mail archive of the
libc-alpha@sources.redhat.com
mailing list for the glibc project.
[BZ558] Part 1: more efficient lowering of {m,n}
- From: Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>
- To: Glibc Development <libc-alpha at sources dot redhat dot com>
- Date: Tue, 23 Nov 2004 13:33:11 +0100
- Subject: [BZ558] Part 1: more efficient lowering of {m,n}
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