[ragel-users] optimization idea

Andrei Polushin polus... at gmail.com
Wed Feb 27 11:16:30 UTC 2008


Gaspard Bucher wrote:
> When there is a bug regex, we end up with huge switch statements. From 
> what I understand from these statements, in the worst case, the 
> process must execute every instruction of type (jump not equal).
 >
 > We could reduce this by implementing a simple binary tree when the
 > case statements get too big:

I have a more practical use case that requires a similar optimization.

For the xdigit transition, Ragel generates something like:

   if ('0' <= *p && *p <= '9' || 'a' <= *p && *p <= 'f'
                              || 'A' <= *p && *p <= 'F') {
       // ...
   }

In C, it could be replaced with the quite efficient table lookup code:

   if (isxdigit(*p)) {
       // ...
   }

The general idea is that there should be something in the Ragel code 
generator that would allow us to selectively group transitions and 
optimize the code generated for them.

The problem is that we don't know in advance what transitions would be 
there after FSM minimization. So there should be a possibility to 
associate the optimization with something like "transition pattern", 
then rlgen-xx would recognize the "transition pattern" and generate the 
manually optimized code instead of its own.

-- 
Andrei Polushin



More information about the ragel-users mailing list