osa1 / lexgen

A fully-featured lexer generator, implemented as a proc macro
MIT License
63 stars 7 forks source link

Compile DFAs as lookup tables instead of linear if-elses #6

Closed osa1 closed 3 years ago

osa1 commented 3 years ago

It's not uncommon for a lexer state to be compiled to dozens of states. Currently we generate code like this:

match self.state {
    0 -> ...,
    1 -> ...,
    ...
    _ -> ...,
}

For N states this means N-1 comparisons in the worst case to the take last branch.

Instead we should compile each state to a function, then put them all in an array:

static STATES: [fn(...) -> ...; N] = [...];

Then just do STATES[self.state](...);.

osa1 commented 3 years ago

I implemented this in state_functions but cargo bench reports 5% regression in the Lua benchmark, and even worse in a micro benchmark.

osa1 commented 3 years ago

I implemented this in state_functions but cargo bench reports 5% regression in the Lua benchmark, and even worse in a micro benchmark.

This is because the current code is compiled to a jump table. Closing.