Repository navigation
optimize state machine inside loop into computed goto #2162
Description
Related issues:
One remaining use case for computed goto is performance. This pattern:
const State = enum {
one,
two,
};
while (true) {
switch (state) {
.one => {
state = .two;
},
.two => {
// ...
},
}
}Here the code relies on setting the state variable and a loop iteration. In C the code could directly goto another switch label. In Zig this is not available, and the code generated is worse than in C due to the optimizer's inability to detect this pattern.
Upstream bug, reported by @shawnl: https://bugs.llvm.org/show_bug.cgi?id=39043
Potential solutions include:
- (ideal) send upstream patch to LLVM making it able to detect this pattern and optimize it. It seems reasonable that this should work, given that both gcc and icc are able to do it.
- make zig detect this pattern and emit different LLVM IR
I don't consider this to be blocking a 1.0.0 release.
Activity
PavelVozenilek commentedon Apr 2, 2019
Performance of computed goto highly depends on processor and the task. It is not always faster then the ordinary switch.
Perhaps the compiler should be given a hint in form of designated tests. Depending on timing of these tests, it would then pick up the best performing implementation.
This topic gets sometimes discussed on Forth forums, they found that the old truths are not absolute, as they once were.
shawnl commentedon Apr 2, 2019
@PavelVozenilek
There are times where a state only leads to an error condition, or to the next state, however, and clang is incapable of in-lining these cases.
andrewrk commentedon Apr 2, 2019
Profile guided optimization is #237
tgschultz commentedon Apr 2, 2019
I personally am not a fan of having to rely on the optimizer to do the right thing, and then trying to fool it into doing the right thing when it doesn't. While allowing the compiler to make this optimization is a good idea, I feel that that is not sufficient to cover the computed goto use case and some explicit mechanism should still be available.
PavelVozenilek commentedon Apr 2, 2019
@shawnl: as I understand it, computed goto performance advantage depends on ability of the processor to predict which code path would be executed next (and start speculative execution of this path in advance). With one big switch such prediction is not feasible.
In Forth interpreter code paths are few and short, and common patterns of code are frequent. The processor prediction could then make a big difference.
I do not see how inlining could play a role here, but could be easily wrong.
shawnl commentedon Jun 20, 2020
A good benchmark for this issue would be a
re2clexer.andrewrk commentedon Oct 1, 2023
Closing in favor of #8220