Building Fast Interpreters in Rust
blog.cloudflare.com
blog.cloudflare.com
This was one of the first major components to use Rust at our edge and we've been really happy with it.
The flexibility this approach (to matching traffic) has given us... whilst we also get the speed, memory safety... is just great. The speed at which we're iterating on the firewall and other systems that use this is a joy to behold. A lot of that speed derives from the confidence in this component.
We're also really pleased that whilst we have several proposals for optimisations, none have yet needed to be prioritised as the performance is great.
How much of this do you attribute directly to Rust versus other factors like seniority of engineering talent, clear communicated requirements, organizational empowerment, etc? If you swapped out Rust for C, what would be the impact on velocity? Is it a 1-4x multiplier, or larger?
Before making this in Rust we experimented with a Go and also a Lua implementation as we investigated the approach. The Rust code took the same time to initially produce and was production ready very early and has been rock solid and required virtually no maintenance since it was put into production.
That frees up that engineer to work on other things, whilst also reducing ongoing maintenance that was anticipated and so those engineers are also working on other stuff.
I'd attribute a chunk of that to Rust... though it helps if you have great engineers who are familiar with the concepts of parsers, etc working on these things. The same may not be true if someone new to Rust was also new to the concepts needed.
But actually I was excited by Rust too. The memory safety, performance (the Rust was faster) and the degree of control over how we could present the FFI to the languages we needed to integrate with, in addition to how readable the Rust was by comparison to the Go code (readable, but so much of it), and then avoiding the GC... the Rust implementation was a convincing winner.
Rust on the other hand with first-class ADT and pattern matching makes it a pleasure! You also have all the nice advantages of the compiler checking that all branches have been satisfied which catches a lot of bugs at compile time.
Go has it's place, and works great in those places, but I don't think this is one of them. I'm pleased we chose Rust and this feels like a great use for it!
It's worth keeping in mind that in some other language or with some other library or using some other toolkit, you'll still wind up with a bottleneck. It'll just be a different one (and maybe a worse one).
Delphi/Ada/D/.NET Native like compile times are still on the horizon.
The downside: I used to use the "waiting for the compiler" time to think about what I'd written, consider alternatives, think about refactoring, etc.
Suddenly I had to block out time for that :-)
At least most of the unit tests were run under java - e.g. the "business" (ui) logic.
I know that when I am trying to find a bug (any bug, it could be logical or data) that I am slowing down a simulation of the interaction of components in my head. This helps one understand all of the abstractions and evolutions of processes within the program. Maybe that very act is the power of C++.
Yes. So if one is going to do anything (optimize, write a new server, whatever) one should focus effort where it gets the most bang for the buck.
Before making this in Rust we experimented with a Go and also a Lua implementation as we investigated the approach.
This is excellent! More companies need to be willing to spike & experiment and change directions on effort up front. In general, the sooner you know, the more money you save.
1. Cloudflare has an unusual structure in that we have a three engineering groups: the core engineering group that builds things that the product management team specify, a totally separate disruption group that works on riskier bets, and a crypto research group.
2. I strongly believe that letting people work in languages they love has a huge advantage. Engineers want to learn new skills (and those that don't we don't want to hire) and so letting them do that means they are happier and do better work.
3. Small teams do more than large ones. The teams that work on Cloudflare products are very small and agile.
Lua or LuaJIT?
it seems the philosophy behind it is very similar
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?
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.
Has the Rust team considered that choosing cute names like "crate" might turn away some of the target audience?
The same applies to other ecosystems like homebrew, but in the case of Rust some of the target audience certainly includes C/C++ programmers.
Beyond that, “crate” specifically has utility. The closest existing name is “compilation unit,” but with things like incremental compilation, that’s a bit of a misnomer. We need some kind of name.
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".
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.
Did you profile your bytecode implementation to see where the time is going?
[0]: https://en.wikipedia.org/wiki/Threaded_code#Subroutine_threa...
If you're curious, you can find Inko's interpreter loop here: https://gitlab.com/inko-lang/inko/blob/master/vm/src/vm/mach...
This is the case with closure-based approach too, and indeed was one of the main motivations to switch away from AST interpretation.
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.
Here's a production version from OpenJ9's JVM ByteCode Interpreter. [2]
[1] https://kseo.github.io/posts/2017-01-09-continuation-passing...
[2] https://github.com/eclipse/openj9/blob/01be53f659a8190959c16...
The source code: https://github.com/cloudflare/wirefilter
Of particular interest are Continuation Style Passing Interpreters [2] and how much of a speedup you can get by going to raw assembly.
The talk has lessons Cliff learned from his years on the JVM but those can be adapted easily to other runtimes.
[1] https://youtu.be/Hqw57GJSrac?t=341
[2] https://kseo.github.io/posts/2017-01-09-continuation-passing...
Essentially, capture clauses are a design pattern in Rust whereas they're a language feature in C++: http://smallcultfollowing.com/babysteps/blog/2018/04/24/rust...
In terms of capture clauses, what I really like are Swift's, as they allow you to bind identifiers to expressions in the capture clause itself (as opposed to just doing capture-by-value vs capture-by-reference). Having capture clauses in Rust that have the same capability would be great.
I don't know how common the knowledge of nikomatsakis's pattern is though, and thus if crates could be automatically searched for it.
let settings = thing_it_wants_to_take_by_reference;
let channel = thing_it_needs_to_take_ownership_of;
let closure_that_takes_everything_by_reference =
|| { some_code(settings, channel) };
let closure_that_takes_everything_by_move =
move || { some_code(settings, channel) };
let closure_that_does_what_I_want = {
let ref_settings = &settings;
move || { some_code(ref_settings, channel) }
};
let closure_with_hypothetical_syntax =
|| [move channel] { some_code(settings, channel) };You don't even need it in this case; this will compile, for example:
fn main() {
let settings = String::new();
let channel = String::new();
let closure_with_hypothetical_syntax =
|| { some_code(&settings, channel) };
}
fn some_code(settings: &String, channel: String) {
}
The arguments against JIT aren't backed by any prototypes or proofs. it felt like the author has a bias towards dynamic dispatch and walked backwards towards it.
There is no mention how frequently these filters change nor the possible perf advantage that you'd get from running compiled expressions that would compensate for the accumulated compile time of these filters over time.
Often you need 2 approaches together and you switch from interpretation to JIT after a condition. (in db case after the same query shows up multiple times for example). In their case it can be something as simple as if filter hasn't updated in x time then consider it stable and compile it.
On the other hand, PGs dynamic dispatch is a fun read just like any other code in PGs repo.
https://github.com/postgres/postgres/blob/master/src/backend...
That said, it seems obvious to us that now we have a Rust library that can parse a Wireshark-like syntax into an AST... that we don't have to just perform the matching in Rust. i.e. that we can ask the library to produce translations of the expression as SQL (for our ClickHouse), GraphQL (for our analytics API), or even eBPF.
We can't run everything in eBPF, but we could check the list of the fields within an expression to see whether it could be run in eBPF, and then look at heavy hitter rules and promote the ones doing the most work inside L7 to be eBPF and to run in XDP.
Even if we don't do this for customer configured rules, this might be something we do for handling denial of service attacks using the same Wireshark-like expression syntax throughout our system.
Amortizing the cost of dispatch over multiple packets means that under heavy load, the performance of the system should be fairly close to what you could JIT, but the system would be much more simple.
Of course, this only helps with the worst case where a backlog is starting to build, but it at least reduces the worst case.
What’s the good reason, if I may ask?
And of course there's a very fine line in C++ between "ensure boundary safety" (s.at) and "here comes a buffer over-read" (s[]).
In Rust by contrast, the latter is spelt `unsafe { s.get_unchecked() }` so it's a bit harder to miss / fat finger it in.
Since it fails to detect common lifetime errors, it's not surprising it's more "flexible" than Rust NLL, which prevents all lifetime errors.
Not detecting issues being more flexible than detecting issues surprises no one. Raw pointers are also "more flexible" than smart pointers let alone borrow-checked references.
This is likely to be a particular problem for strings (as supposed to any other structure), due to the long and complicated history of strings in C and C++. There are likely to be many string functions across the codebase, and null termination in some contexts confuses the issue even more.
1. not exactly, you're now doubling your allocations as you're allocating a native object which has to create sub-structues representing the guest object, unless you're using the rpython technique of the interpreter being fed into a magical thing of magic which spits out a "native" runtime
2. the GC of the host language doesn't necessarily match what you want for the guest
3. and not being able to manipulate and interact with the GC can make efficiently implementing the guest difficult
Those sub structures can live within the same allocation. And in many cases, the object passed to the interpreter can be the undecorated native object.
> 2. the GC of the host language doesn't necessarily match what you want for the guest
It's almost certainly better than recounting or naive mark and sweep, which is what you get when someone reimplements a GC for an interpreter.
That's great if the language you're using has the same GC semantics as the language you're implementing, and a pretty major problem if it doesn't.
What languages have materially different GC semantics, other than Python on the cpython vm? (PyPy loses the fast collection at the end of scope for efficiency reasons)
Ruby also exposes parts of its GC, and allows it to be hooked by C extensions, so when I implemented it on top of the JVM I had to basically reimplement half of it in Java in order to implement those parts of the language.
Others have mentioned a few, and I'll mention another: GC support for concurrency.
Try writing a performant Go interpreter in OCaml, for instance.
Javascript is much easier to do in the JVM because the language makes no assumptions on how memory is stored (AFAIK).
- Giant switch statements are not optimized as well as C. - In C you can do tricks like NaN encoding to create a union between floats and pointers. In Go, this doesn't work and you have to use an interface.
There might be a garbage-collected language that lets you write efficient interpreters (perhaps Julia?) but I don't think you can take this for granted.
There have been Smalltalk implementations written in other Smalltalk implementations which have used this approach. In those cases, the GC is very appropriate for the language implemented.