3 ms·

This is pretty old, from 2003, and I think modern Intel processors nullify the purported benefits of "indirect branching" (aka "computed goto") versus switch st

This is pretty old, from 2003, and I think modern Intel processors nullify the purported benefits of "indirect branching" (aka "computed goto") versus switch statements. A few years ago I learned of gcc's computed goto (also supported by clang, IIRC) and I reimplemented lightgrep's core regex engine with computed gotos instead of the indirect switch statement. I could not measure a difference, and I went back to the clearer, more portable switch statement.

jonstewart 10y ago
That said, it's not too surprising that it would be faster on MIPS. MIPS would have far, far fewer transistors working on branch prediction than x86.
lacampbell 10y ago
That's actually really interesting. All the literature I've read suggested that switch statements were some horrible performance killer and you had to speed or portability. Cool to see that it's changed. I think even the Lua Paper had a bit about that.
glangdale 10y ago
What it comes down to is that predictable indirect branches are well-predicted. It does not require any insider information to verify this about Intel architecture processors. I built a "fake interpreter" a while back and found that branch misses in predictable sequences of interpreter code are very unlikely unless there is a longish common prefix of interpreter indirect branches in two interpreter sequences (i.e. one sequence goes ABCDEFGH and the other goes ABCDEFGZ). This led us down a path of also using an interpreter within our own regex engine (Hyperscan) - not for individual engines like NFA/DFA/literal match but for the overall orchestration layer. It's been quite an improvement of code cleanliness and generally has been either performance-neutral or even good. When you replace a great big ugly clagged "if this rare thing happens, go do this code, or else if this happens, go do this other things, then ..." with an interpreter you can get nice performance benefits in the common case - even though there are not branch misses in the "giant clagged pile of code" anti-pattern.

jonstewart 10y ago

That said, it's not too surprising that it would be faster on MIPS. MIPS would have far, far fewer transistors working on branch prediction than x86.

lacampbell 10y ago

That's actually really interesting. All the literature I've read suggested that switch statements were some horrible performance killer and you had to speed or portability. Cool to see that it's changed. I think even the Lua Paper had a bit about that.

glangdale 10y ago

What it comes down to is that predictable indirect branches are well-predicted. It does not require any insider information to verify this about Intel architecture processors. I built a "fake interpreter" a while back and found that branch misses in predictable sequences of interpreter code are very unlikely unless there is a longish common prefix of interpreter indirect branches in two interpreter sequences (i.e. one sequence goes ABCDEFGH and the other goes ABCDEFGZ). This led us down a path of also using an interpreter within our own regex engine (Hyperscan) - not for individual engines like NFA/DFA/literal match but for the overall orchestration layer. It's been quite an improvement of code cleanliness and generally has been either performance-neutral or even good. When you replace a great big ugly clagged "if this rare thing happens, go do this code, or else if this happens, go do this other things, then ..." with an interpreter you can get nice performance benefits in the common case - even though there are not branch misses in the "giant clagged pile of code" anti-pattern.