10 ms·
I 10x'd a TI-84 emulator's speed by replacing a switch-case
- mysterydip 4y agoFrom the title, I expected to find one of the frequently called case statements was unoptimized and they fixed it. Instead, the fix was rewriting all case statements in a way the javascript engine would optimize. Very frustrating if you're unaware of the obscure rules around it.
- benreesman 4y agoThis kind of stuff is usually at least somewhat frustrating in the moment, but it’s just the nature of things: we’re always mapping some task onto some machine and it wouldn’t be such a great story if it wasn’t such an elegant hack. This one is particularly interesting because it’s one VM mapping onto a second VM and the impedance mismatch is very meta. 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!
- yarg 4y agoNot quite - the javascript engine failed to optimise reasonable situations, so the dude translated to a code structure (arrays of functions) that didn't require optimisation. Essentially he was forced to manually code what should've been done under the hood anyway.
- shadowofneptune 4y agoI'm unsure. They're different enough in structure that it feels to me that it should be a conscious decision. In a switch statememt, there's usually one large scope, while in the function table there's a lot of little scopes. The pathway through the code during execution is different ad well. Massive switch statements are also not reasonable situations from the perspective of a compiler, as they see little use outside of VMs.
- andreareina 4y agoVMs aren't exactly rare though, and are a case (heh) of when you really want all the optimization the compiler can give.
- naniwaduni 4y agoIn the grand scheme of things, VMs and interpreters are a class of program that tend toward perhaps surprisingly pathological behaviour, among programs people are likely to write.
- yarg 4y agoO(1 for small n; n otherwise) just seems like a poor decision.
- yarg 4y ago> They're different enough in structure... 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).
- shadowofneptune 4y ago> 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 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 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.
- xena 4y agoshe* the author is female.
- yarg 4y agoIf the sex of the author had any bearing on my interpretation of the article, I might actually give a damn. But it doesn't; so I don't.
- eyelidlessness 4y agoBut knowing how the JIT deoptimizes is a good thing for anyone programming perf-sensitive code for that JIT. Even developing a sense of where branchy logic might deopt is a good thing, even if your code might not be perf-sensitive but could be called in a perf-sensitive call stack, because it’ll give you a good heuristic for when optimization is premature. Optimizing for the JIT isn’t and shouldn’t be a guiding principle for every dev, but it’s harmless or good for us to be aware.
- saagarjha 4y ago> Optimizing for the JIT isn’t and shouldn’t be a guiding principle for every dev, but it’s harmless or good for us to be aware. 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.
- pjmlp 4y agoJust like it happens in C when driven by assembly output on a specific compiler version.
- saagarjha 4y agoYep, exactly. There are very few codebases that can actually write code directly to the optimizer and they are usually developed very closely with a specific compiler. For other cases usually you can trust that a number of basic optimizations can be performed and then be cautious about what the various compilers can do. As you gain more experience you can slowly expand the set of things you would expect to be "easy" for the compiler–when those passes don't run, they're generally considered to be bugs.
- deleted 4y ago[deleted]
- pjmlp 4y agoIt is no different from compiled languages, that is one of the reasons why most compilers regardless of the language, allow to look into the generated Assembly.
- IshKebab 4y agoIt's not fundamentally different but it is generally a lot easier to predict what will be fast with e.g. Clang than V8.
- anonymoushn 4y agoFor inner loops of interpreters in low-level languages, unless you are using some labels-are-values extension, it's often tough to convince the thing to generate the right code.
- pjmlp 4y agoOnly if one has a PhD in ISO C semantics and compiler optimization handling of UB. What is fast in clang might be totally crap on xlC, or even plain clang vNext, for example.
- mysterydip 4y agoThe difference is control. You can choose which compiler to use for your project, even an outdated version if it works for your use case. But you have no control over what JIT engine visits your site.
- pjmlp 4y agoPartially true, most of the time many dev teams don't control what is on the CI/CD servers, or what compilers are being used when shipping libraries.
- Eeems 4y agoI had pointed out this optimization years ago, but I never took the time to actually get it merged into the emulator.
- lern_too_spel 4y agoThis article is about a change merged 9 years ago.
- Eeems 4y agoJeez, has it really been that long?
- AlotOfReading 4y agoI get the same sensation too. It's kind of funny how these little reminders of people and interactions from cemetech and Omni pop up elsewhere in the tech community. I'm still proud of some of the stuff I wrote back in those days. - Qwerty
- siddontang 4y agoUsing map or array instead of switch-case is a common optimization way, but please do a benchmark if you have no confidence whether you need do or not. E.g, it doesn't already work in Go, https://stackoverflow.com/questions/46789259/map-vs-switch-performance-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.
- firloop 4y agoWonder if that benchmark still holds true for Golang. Go 1.19 (released last week) includes jump table optimizations for switch statements. https://go.dev/doc/go1.19#compiler https://go.dev/doc/go1.19#compiler
- jheuel 4y agoI just tested it: 1.18: BenchmarkMap-10 13388006 77.38 ns/op BenchmarkSwitch-10 50482033 23.00 ns/op BenchmarkSlice-10 100000000 10.90 ns/op 1.19: BenchmarkMap-10 14947908 76.78 ns/op BenchmarkSwitch-10 49444435 23.01 ns/op BenchmarkSlice-10 100000000 10.74 ns/op edit: If I understand the release notes correctly the switch optimisations are only new for large integers and strings.
- KMnO4 4y agoThis is one of those gotcha that trap senior devs way more than junior devs. Growing up with C being my first language, I intuitively associate switch with a jmp table (ie extremely fast). Even though I knew it’s unlikely to be as performant in JS, it never occurred to me that it would actually be slow, until I did a deep dive into low level JS optimization. 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 https://youtu.be/7WuRq-Wmw5o
- syntheweave 4y agoI don't know. Maybe it's because I've spent too long thinking about such things, but interpreter dispatch routines are one of those areas of code where micro-optimizations are very pernicious and one should expect to review the landscape each time to rediscover best practice. See all the ways of compiling and executing Forth words for examples.
- teruakohatu 4y ago> would actually be slow, until I did a deep dive into low level JS optimization 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.
- TAForObvReasons 4y agoYou can switch on arbitrary types in JS and you can add expressions: switch(3) { case true: break; case "ab" + "c": break; case Math.random() >= 0.5 ? "heads" : new Error("tails") : break; } The optimizer will have to be persuaded that the switch and each case is integral before optimizing with a jump table. On the other hand, Arrays typically have a fast path for integer indices.
- teruakohatu 4y agoThat explains it, but shouldn't a switch with string or numerical constants (or an expression made up of constants) just be optimized away anyway?
- game-of-throws 4y agoI wonder why the deopt cutoff is 128 and not a nice round number like 256. It seems like switching on the value of a byte would not be that uncommon.
- baobob 4y agoDon't know the guts of the optimization, but 128 64bit pointers is 1024, which is a round number. Could be to avoid memory or cache blowup, or maybe they're using that 8th bit for something internally
- marethyu 4y agoAny good resources for building my own TI-84 emulator?
- AreYouSirius 4y ago
- Dwedit 4y agoLook up the Z80, the ROM, and the IO ports.
- MaxLeiter 4y agohttps://wikiti.brandonw.net/index.php?title=WikiTI_Home https://wikiti.brandonw.net/index.php?title=WikiTI_Home Cemetech is the largest (and now maybe the only) calculator forum around. There’s also a few IRC channels on EFNet
- marwatk 4y agoFor anyone looking for an open source web-based TI emulator I just ported wxWabbitEmu (which I believe supports the TI-84) [1]. I only skinned the TI-85 since it's the calc I use, but the skins are just CSS. 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://github.com/marwatk/wasmwabbitemu https://github.com/marwatk/wasmwabbitemu
- thrtythreeforty 4y agoThis is really cool! It's a shame that jsTIfied isn't open source; I would have liked to use it for live demos in my roundup [1] of cool TI software projects. Your project with a skin would be perfect. [1]: https://www.thirtythreeforty.net/posts/2021/10/ti-calculator-innovation/ https://www.thirtythreeforty.net/posts/2021/10/ti-calculator...
- AreYouSirius 4y ago
- dado3212 4y ago> I was used to dealing with obfuscated code from Minecraft 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.
- bobsmooth 4y agoI imagine Roblox will have been a similar inspiration for developers in a few years.
- wiseowise 4y agoIsn’t Minecraft Java?
- a_t48 4y agoYup
- saagarjha 4y agoI know several people who are experts at reverse engineering, obfuscation, and runtime patching solely because they did Minecraft mods.
- sdflhasjd 4y agoMinecraft is too new for me, but I did get most of my pre-professional experience from modding in video games, other people I've worked with can say the same.
- machiaweliczny 4y agoFor me it was bots for RuneScape
- girvo 4y agoSame, and writing bespoke keyloggers for RuneScape GP
- 4y ago
- djmips 4y agoFYI - This article's from 2013 or the work was done in 2013.
- summerlight 4y agohttp://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html Somewhat tangential, but one of the most informative thread on interpreter performance optimization.
- james-redwood 4y agoI have this bookmarked. It's a great thread.
- justinlloyd 4y agoInterestingly I wrote a 6502 (actually Atari 6507) emulator and Z80 emulator for the MIPS R3000 in the original SONY PSX, and the only way to get the speed I needed was to use calculated jump tables rather than relying on a switch case. I know that C provides that calculated jump, but even that wasn't enough. Eventually I rewrote the entire emulator in R3000. And then I eventually switched to using CPU retargeting/recompilation from 6502 to R3000, and then used the same recompilation trick to get 6502 emulation running at a decent speed on the ARM CPU in the Nintendo Gameboy Advance.
- klelatti 4y ago> CPU retargeting/recompilation from 6502 to R3000 Is this converting 6502 assembly to R3000 - not recompiling the source?
- justinlloyd 4y agoJa. Take 2600 ROM dump and convert to R3000.
- flohofwoe 4y agoThat depends a lot on the compiler, I guess in the 90's compilers didn't optimize switch-case that well yet. 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).
- justinlloyd 4y agoThe old compilers optimized the switch/case, just not as well as something from 2022, and there were lots of edge cases too. And limited registers, and small caches and so forth. Plus, these were CPUs that were at the boundary of what could be done in terms of emulation of another CPU and everything else about the device being emulated too. Today we have the advantage of far more advanced compiler technology and far more advanced CPU technology that runs crazy fast, and a greater understanding of how to emulate the machines and best practices for creating those emulators. 25 years ago, not so much. The PS2 and the XBOX were the first consoles where you could just take MAME or the 2600 VCS emulator I wrote and compile it to the target console and "it just worked." I ported MAME to the PS2 and ran six different games on a tumbling cube, and then MAME to the XBOX shortly afterwards, and Dolphin emulator on XBOX and PS2 as well - though again, smacking up against what that generation of consoles could realistically emulate.
- klelatti 4y agoShameless plug for my 6502 JS emulator / assembler in an Observable notebook, which takes the opcode, converts into pseudo assembly and then uses a switch statement on the mnemonic. I expected it would be horribly slow but maybe this switch on the (50 something instructions) is OK? https://observablehq.com/@tech30k/6502 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!)
- rkagerer 4y ago2013 was a different time, and JS engines have come a long way since then. I really hope they’ve made this better than it was. Have they? Do the 128 case limit and signed integer literals constraints still exist?
- rkagerer 4y agoHere's a similar case from 2020: https://stackoverflow.com/a/59570825 https://stackoverflow.com/a/59570825 With a link to the V8 line of code defining the 128 limit: https://github.com/v8/v8/blob/596d0ce7b7a3900c529025aaa77e5fc39162c8c5/src/hydrogen.cc#L3350 https://github.com/v8/v8/blob/596d0ce7b7a3900c529025aaa77e5f...
- klelatti 4y agoInteresting thanks. Is there a good reason for a relatively low fixed limit like this?
- RichieAHB 4y agoWorth noting that SO comment calls out that the linked line points to the code as it was in 2013 and that there have been changes since then: > 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.
- fabioborellini 4y agoSo the writer is a 10x developer.
- amelius 4y agoNo, the compiler writer was a 0.1x developer.
- edf13 4y agoHas this been fixed in V8 now?
- jraph 4y agoI understand that switch-cases may not be optimized well in JS, but what surprises me is that all the instructions in the cases are now grouped into functions and this is faster than regular switch case. 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?
- fenomas 4y agoTFA is basically about a limitation in V8's compiler, circa 2013. Based on the bug report it looks like that limitation was gone a few years later, and either way V8 switched to a whole different compiler back in 2017 or so.
- Tehdasi 4y agoTangentially related, but I remember reading years ago a piece from a graphics driver developer (nvidia maybe?) that one of the reasons why the opengl driver was slower than their directx driver (I believe) was that the structure of OpenGL was such that you had to put a massive switch in the code which really hurt performance.
- flohofwoe 4y agoVery unlikely that an actual switch statement was the problem (if that actually exists, and wasn't just 'figure of speech'). OpenGL state is a huge collection of tiny knobs and toggles ('switches' if you like) and each state change may in turn influence other state, while D3D (since D3D10 at least) groups the same state into a small number of immutable state objects.
- teddyh 4y ago> I had to unminify it, but I was used to dealing with obfuscated code from Minecraft. The ancient ritual persists.
- nolist_policy 4y agoSee also the Nostradamus Distributor https://news.ycombinator.com/item?id=2593095 https://news.ycombinator.com/item?id=2593095
- stn_za 4y ago
- greggman3 4y agoI like function tables. I think they are cleaner than switch statements 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. https://jsbenchit.org/?src=5c1e5bcf62448b6d1750b12893b0f0a1 https://jsbenchit.org/?src=5c1e5bcf62448b6d1750b12893b0f0a1
- whent 4y agoAre function tables really all that cleaner? Honest question. If I can offer a counterpoint a function table requires us to code some function dispatch routine that looks at the intention (keywords in function table), then looks up the function, then finds a way to bind the arguments to the function (language specific) and finally call the function? Isn't this more complexity in code? Isn't switch-case simple because it is available as a construct in the language?
- deleted 4y ago[deleted]
- masklinn 4y agoThe article is a decade old. 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.
- vanderZwan 4y agoNitpicking on an otherwise insightful comment: the article is recent, but the period in which the optimization was made was decade ago.
- no_time 4y agoStaggering difference between Spidermonkey and JSCore. I hope the situation isn't as dire on linux :/
- y0ungarmanii 4y agoReminds me of when Terry Davis taught me that switch statements are just lookup tables and b/c of that more efficient. RIP to the king!
- jason_slack 4y agoCan anyone share their resources on how to write programs on TI calculators? What is the language option you chose? TI has a bunch of info here also: https://education.ti.com/en/products/calculators/graphing-calculators/ti-nspire-cx-ii-cx-ii-cas/programming-in-python https://education.ti.com/en/products/calculators/graphing-ca...