I 10x'd a TI-84 emulator's speed by replacing a switch-case
artemis.sh
artemis.sh
Related: Matt Godbolt’s talk on emulating 6502 in JS. He also mentions the poor performance of switch for opcodes: https://youtu.be/7WuRq-Wmw5o
I think you've slightly misunderstood TFA. The issue there wasn't that the switch statement was slow, per se - it was that V8's optimizing compiler didn't yet support such statements, so V8 was bailing out of its JIT step and executing the function via a (dog-slow) interpreter. In other words the function would have run painfully slow even if it returned before reaching the switch statement.
It's also maybe worth adding that gotchas like this were super common way back in the early days TFA describes, but AFAIK they are no longer a concern now. Back when V8's optimizer was primitive it used to bail out for all kinds of reasons - because it saw a "try()" statement, because a function was too long, or even just because it got confused. Nowadays it's a different world - I do a lot of JS perf work, but it's probably been two years since I've seen V8 deopt anything for any reason.
(Mind you I'm not saying switch statements are fast - they may well be slower than the alternatives even after being optimized. I'm just pointing out that TFA isn't about the performance of switch statements, it's about avoiding deopts.)
To optimize the runtime first has to figure out that all case values are constants (and insert guards to de-opt if it doesn't hold anymore), so in essence the machinery for running this code optimized has to be very conservative (and probably why they placed arbitrary limits that really aren't suited for emulators).
https://tc39.es/ecma262/multipage/ecmascript-language-statem...
Famously, function inlining decisions were based on the size of the function, not the size of the AST of the function, which lead to situations where removing inline comments allowed a function to be faster.
Interpreters and basic compilers are remarkably similar, and it's easy to transform between them if you do some extra busy work. Once you have your final AST, instead of outputting bytecode instructions, output the implementation of each instruction. Or vice versa.
You have code that handles different types in the interpreter? Great, bake it into the compiled code.
The transform from bytecode interpreter to compiler is always pretty simple, but the other way around gets more difficult the smarter the compiler is. So yes it is very possible to have a baseline javascript compiler and no interpreter.
It wasn’t a very advanced compiler in the sense that it generated very inefficient machine code. But it still ran circles around a tree-walking or bytecode interpreter. Over time the compiler became more advanced and multi-tiered, but at the cost of startup time, and mobile was taking off, where memory was more scarce than on desktop. x86 or ARM code is a lot bigger than a specialized bytecode that is optimized for space efficiency. So eventually the Ignition interpreter was added. But unlike some of the other Javascript engines that started as an interpreter and later added native code generation, V8 started out generating native code and only later added a bytecode interpreter.
For a hand-waving theoretical example, if you have code like:
var a = { foo:1 }
var b = { foo:2 }
var c = { foo:3 }
doSomething(a)
doSomething(b)
doSomething(c)
If you want to know more, searching on "V8 hidden classes" should turn up relevant articles.
Can you explain why this is?
Intuitively it would seem like optimizing a switch statement would be really low-hanging fruit. I would have thought it would be optimized into something almost exactly like what the author hand rolled.
switch(3) {
case true: break;
case "ab" + "c": break;
case Math.random() >= 0.5 ? "heads" : new Error("tails") : break;
}
> @LGB actually in V8 (JS engine used by google chrome) you need to jump through a lot of hoops to get switch case optimized: All the cases must be of same type. All the cases must either be string literals or 31-bit signed integer literals. And there must be less than 128 cases. And even after all those hoops, all you get is what you would have gotten with if-elses anyway (I.E. no jump tables or sth like that). True story.
In the case of this emulator, it wasn’t being optimized because it had more than 128 cases.
Now that makes sense. Thank you.
E.g. Random.random() will have to be called each time that case branch is evaluated, because that function could be overloaded or change its returned value.
Me too, but I try to keep the set of values dense and use a mask (op & 0xff) to help the compiler know it doesn't need to do bounds checking. Verify these changes help of course.
But, (maybe this is an invalid test), checking today my results suggest a switch is faster than a function table in 2022? At least at a base level. Maybe the more complicated the code for each case gets the less likely it is to get optimized.... which is true in general? large code blocks are less likely to get optimized and a switch is considered one large code block.
In the meantime the entire v8 execution pipeline has been rewritten: a new optimising compiler was swapped in, a baseline interpreter was added, and the baseline compiler was removed (in more or less that order iirc).
Wouldn’t at all be surprising if that lack of optimisation had been long fixed.
Isn't switch-case simple because it is available as a construct in the language?
Essentially he was forced to manually code what should've been done under the hood anyway.
But it doesn't; so I don't.
Sure, I mean more in terms of producing a compiled form with O(1) rather than O(n) performance.
> Massive switch statements are also not reasonable situations from the perspective of a compiler, as they see little use outside of VMs.
I'm not really following this logic, massive switch statements are those that can benefit most significantly from the generation of jump tables.
And what needs to be done to generate them doesn't differ significantly based upon the branch count (when you hit case 0x100 you'll need to switch to 16-bit, so binary size will be impacted).
The fact that it's primary use case is reasonably niche is fairly irrelevant given there's bugger all compiler overhead required for support.
Now from a code perspective, I would say that a statement that large probably isn't ideal (depending on the size of your case blocks).
This is what I had meant, yes. Optimizing such large blocks is quite difficult. A case label in C and C-like languages does not even need a block, making it harder.
> The fact that it's primary use case is reasonably niche is fairly irrelevant given there's bugger all compiler overhead required for support.
Even static C compilers still struggle with optimizing the switch-in-for-loop pattern, let alone a JIT compiler. Clang does the best job nowadays, but it still lags behind other methods like computed goto or continuation-passing. The Python VM will switch to computed goto if it's available on the C compiler.
Best primer on the subject I have found, even if old: https://www.complang.tuwien.ac.at/forth/threaded-code.html
My own benchmarks from last year (note that these toy VMs may not be applicable to larger ones): https://github.com/shadowofneptune/threaded-code-benchmark
It does take work to make a faster VM, it feels unreasonable to expect a compiler to do a good job at optimizing it without effort on the writer's side.
My only nitpick with a great read is that I want to know a little more gory details of how the automation was done, it could easily have involved a third or even fourth VM!
No, it can be quite harmful: you could end up overoptimizing for one engine and ruin performance on another engine, or even a different version of the same engine. When making non-trivial optimizations that are designed around the quirks of the optimizing compiler you should be very careful about the tradeoffs and also what the penalty will be if the optimization breaks in the future.
What is fast in clang might be totally crap on xlC, or even plain clang vNext, for example.
I'm curious what the performance is like. I run it on my phone as a basic calculator, haven't messed with running binaries at all.
[1]: https://www.thirtythreeforty.net/posts/2021/10/ti-calculator...
E.g, it doesn't already work in Go, https://stackoverflow.com/questions/46789259/map-vs-switch-p...
But if there are too many switch-cases, the codes may be ugly to read, so maybe using a map or array is a better choice here.
1.18:
BenchmarkMap-10 13388006 77.38 ns/op
BenchmarkSwitch-10 50482033 23.00 ns/op
BenchmarkSlice-10 100000000 10.90 ns/op
BenchmarkMap-10 14947908 76.78 ns/op
BenchmarkSwitch-10 49444435 23.01 ns/op
BenchmarkSlice-10 100000000 10.74 ns/op
Somewhat tangential, but one of the most informative thread on interpreter performance optimization.
https://observablehq.com/@tech30k/6502
Written as a convenient way to try to explore the ISA and hoping to try the same approach with other early ISAs soon (6800 in progress).
(Please be kind with the code. I'm not a JS programmer - its my first JS beyond a handful of lines - and there are lots of issues!)
I wonder how common this is for engineers. I’ve been in industry for the last 4-5 years or so, and it was how I got a pretty big jump into programming. Talked to a few similarly aged engineers at FAANG and a couple others got into programming through Minecraft as well.
When I write Javascript, I expect function calls to be slow. So I see three possibilities:
- (unoptimized) switch statement is very slow in JS, so slow that function calls will be faster
- function calls are not that slow in the end.
- both
It's a shame that the switch statement cannot relied on to be fast though. They are very readable, and indeed, feel like code that can be highly optimized. I guess that would risk making the JIT compilation too slow, or that not enough code found on the web rely on switch statements for this to matter too much.
Is this still true today? (I've seen a comment that says the 128 limit is still in V8's code)
How is this handled in SpiderMonkey, JavascriptCore or other JS engines?
In modern compilers a switch-case may end up faster than a function-pointer jump table, because even though the compiler will turn the switch-case into a jump table as well, the code that's called through the jump table doesn't have the prologue/epilogue overhead of regular function call. In my emulators I also haven't seen a difference between a regular switch case, and 'computed goto' (but depending on how the decoder loop looks like, computed goto may still provide have an advantage, just not in my CPU emulators).
Is this converting 6502 assembly to R3000 - not recompiling the source?
Human beings still suck at code.
The ancient ritual persists.
TI has a bunch of info here also: https://education.ti.com/en/products/calculators/graphing-ca...
Have they? Do the 128 case limit and signed integer literals constraints still exist?
With a link to the V8 line of code defining the 128 limit: https://github.com/v8/v8/blob/596d0ce7b7a3900c529025aaa77e5f...
> The link into the V8 source code above is pretty old (2013), so I tried to find the modern equivalent. I didn't find a hard limit, but found several heuristics that decide between table lookups and tree (binary search) lookups (ia32, x86). When I plug in my numbers I don't quite get a borderline case where I found it, so I'm not sure this is the actual cause or whether there's another optimization not being triggered elsewhere.
- Qwerty
Cemetech is the largest (and now maybe the only) calculator forum around. There’s also a few IRC channels on EFNet