[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