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

osa1 · 2021-06-01T06:34:18Z

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](...);.

The text was updated successfully, but these errors were encountered:

osa1 · 2021-06-04T09:03:44Z

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

osa1 · 2021-06-17T16:22:23Z

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.

osa1 added the perf Related to runtime performance label Jun 1, 2021

osa1 closed this as completed Jun 17, 2021

Provide feedback