[ragel-users] Re: optimization idea

[Adrian Thurston]

Ragel should be binary searching those tests. Can you produce some numbers that show custom code to be faster?

Or if you don't want to modify generated code conditions might be useful for experimenting with this. Try using any with a condition that tests *p.

-Adrian


-----Original Message-----
From: Andrei Polushin <polushin at gmail.com>

Date: Wed, 27 Feb 2008 17:16:30 
To:ragel-users at googlegroups.com
Subject: [ragel-users] Re: optimization idea



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