3 ms·
In C, a common way to get good performance without JIT is with bytecode and a giant switch statement. It would be interesting to see if that's viable in Rust. H
by skybrian 8y ago
In C, a common way to get good performance without JIT is with bytecode and a giant switch statement. It would be interesting to see if that's viable in Rust. How does performance compare to an implementation using closures?
- RReverser 8y agoIt was even slightly worse than AST interpretation actually - as mentioned in the post, this is a much larger topic that deserves its own attention, but I did include the bytecode case in the linked slides. https://www.slideshare.net/RReverser/building-fast-interpreters-in-rust https://www.slideshare.net/RReverser/building-fast-interpret...
- skybrian 8y agoWell, that's disappointing. Any guesses about why?
- RReverser 8y agoIf you mean in a comparison against AST interpretation, then I'd say that Rust tagged enums (which C doesn't have) are already essentially a bytecode, except properly aligned, so it makes sense that they have same or slightly better performance than you would get with manual bytecode implementation.
- ridiculous_fish 8y agoC certainly has this via unions. It's more manual but provides more control, including choice of alignment. It's CPU dependent but in practice the cache benefits of packed instructions will probably dominate any misalignment penalty. It's not like x86 instructions are aligned after all. What's the best way to implement a variable-width bytecode interpreter in Rust?
- RReverser 8y agoMore control is, as usual, less ability for automatic optimisations. For example, Rust uses knowledge of tag + data combinations for niche-filling enums where possible (and more similar optimisations to come), while LLVM can use this information to more easily deduce which branches are unreachable. As for alignment - you can control it in Rust enums too, if you wish, by putting custom aligned structures as variant payloads. In general, I'm sure it would be possible to achieve same (or, who knows, maybe even slightly better) performance than AST interpretation with manual tweaking, but the closure-based approach proved to give significant wins out of the box, while being more elegant to maintain and extend over time.
- ridiculous_fish 8y agoIn a bytecode interpreter's loop, you want your language to be little more than a fancy assembler. Exotic techniques become viable and even critical for performance: computed goto, misaligned reads, pointer arithmetic, unchecked type conversions, etc. This is one place where you want to tightly control your machine code.
- RReverser 8y agoOh, sure, if you're willing to go to unsafe techniques, you can go straight to a template JIT as well. But, for us, the balance is important, and safety is probably even more important than further wins in performance (which we can still easily get with algorithm-level optimisations before doing anything unsafe).
- deleted 8y ago[deleted]
- pcwalton 8y agoRust has C unions now, but without safety. I would probably write manual parsing code via the byteorder crate.
- cqtoq 8y ago
- ufo 8y agoI am not sure if I understand this argument. The C "tagged union pattern" is very similar memory-wise to Rust tagged enums, it just is less pleasant to use due to no pattern matching and so on. I would expect that the advantage of the closure version of your AST interpreter is coming from somewhere else (at the end of the day it is still an AST interpreter). One possibility is that you are passing around the operands to your filters as Rust lexically-closed values instead of using a custom stack for your interpreter, which makes things a bit more "statically typed".
- RReverser 8y ago> at the end of the day it is still an AST interpreter In a pretty remote sense, I guess. > One possibility is that you are passing around the operands to your filters as Rust lexically-closed values instead of using a custom stack for your interpreter, which makes things a bit more "statically typed". Yes, that and using native dynamic dispatch instead of walking a tree structure with branching are making this technique much closer to template JITs than AST interpretation, with corresponding performance wins.
- ufo 8y agoThe reason I think it is fair to call it an AST interpreter is that there is roughly one function call for each AST node. This isn't necessarily a bad thing though -- AST interpreters are super simple and maintainable (as you have demonstrated) so if you got good performance out of one then it is great!
- munificent 8y agoMy understanding is that you're doing subroutine threaded code[0] instead of bytecode, which isn't a common choice. Maybe this has something to do with Rust's particular performance profile. Did you profile your bytecode implementation to see where the time is going? [0]: https://en.wikipedia.org/wiki/Threaded_code#Subroutine_threading https://en.wikipedia.org/wiki/Threaded_code#Subroutine_threa...
- YorickPeterse 8y agoInko (https://inko-lang.org/ https://inko-lang.org/) uses this approach for its bytecode interpreter. I can't speak about how well it performs compared to an AST interpreter since I never wrote one for Inko, but generally bytecode interpreters should be faster. I also think bytecode interpreters would be easier to optimise, as you're no longer directly tied to the AST of the input language. If you're curious, you can find Inko's interpreter loop here: https://gitlab.com/inko-lang/inko/blob/master/vm/src/vm/machine.rs#L294 https://gitlab.com/inko-lang/inko/blob/master/vm/src/vm/mach...
- RReverser 8y ago> as you're no longer directly tied to the AST of the input language This is the case with closure-based approach too, and indeed was one of the main motivations to switch away from AST interpretation.
- saagarjha 8y agoA better way to get good performance is to thread your switch statement, which is hard to do explicitly in Rust last time I tried (maybe you could do this if you mark functions as inlinable?).
- skybrian 8y agoWhat do you mean by "thread your switch statement"?
- anisppp 8y agohttps://en.wikipedia.org/wiki/Threaded_code https://en.wikipedia.org/wiki/Threaded_code
- smuser 8y agoI think he means have a different thread for each case or a subset of cases instead of having any explicit switch statement.
- ridiculous_fish 8y agoThe "big switch statement" approach is for each bytecode instruction to complete by jumping to a centralized dispatch location (i.e. the switch statement). The "threaded" approach is for each bytecode instruction to complete by decoding and jumping to the handler for the next instruction. Basically instead of "break" you have `goto handlers[nextIp->opcode].` The advantages of threading are fewer jumps and better branch prediction (since branch prediction is tied to IP). The disadvantages are slightly larger code and compilers struggle to optimize it, since the control flow is not structured.
- filereaper 8y agoThis method of design is called a Continuation Passing Style Interpreter. [1] Here's a production version from OpenJ9's JVM ByteCode Interpreter. [2] [1] https://kseo.github.io/posts/2017-01-09-continuation-passing-style-interpreter.html https://kseo.github.io/posts/2017-01-09-continuation-passing... [2] https://github.com/eclipse/openj9/blob/01be53f659a8190959c1641eac20b0488739e94c/runtime/vm/BytecodeInterpreter.hpp#L4872 https://github.com/eclipse/openj9/blob/01be53f659a8190959c16...
- kstenerud 8y agoThis is how ragel [1] does things. It basically compiles to giant-switch state machines, and is damn fast. [1] https://www.colm.net/open-source/ragel/ https://www.colm.net/open-source/ragel/
- jgrahamc 8y agoAgreed. We used to use Ragel for some tasks and it was fast.
- nicoburns 8y agoRagel was also the source of cloudbleed! So I would definitely understand if cloudflare were wary of using that kind of technique again.
- Matthias247 8y agoAs far as I remember not Ragel was the issue, but the code around it. If you use a Rust parser from inside broken C code which Leaks memory the same thing can happen.
- jgrahamc 8y agoThat's not the right way to talk about it. The error was in code that used Ragel but it was all on us. But as part of improving things we have moved away from non-memory safe languages and Ragel was using C.