Replacing a Rust Enum with a 64-Bit Word Made My Interpreter 17% Faster(pointersgonewild.com) |
Replacing a Rust Enum with a 64-Bit Word Made My Interpreter 17% Faster(pointersgonewild.com) |
The old, enum based value type used a single big match statement to dispatch between all possible type combinations. Their assembler output looks like the match gets compiled to something like a big stack of nested if statements.
The new code uses an explicit fast path check with a dispatch into a tagged 'cold' path when the common case isn't hit. The generated code is a single upfront branch for the fast path that exits immediately, with a dispatch into the slow path in a separate function.
This would be contributing significantly to the performance improvements. The old path requires taking several branches even on the hot path. The new code has a single, highly predictable branch that skips all the messy dispatch for the other types.
This could have been implemented for the enum based value type, and I would expect to see a jump in performance there too even without the new compact value type. There will be a much higher branch predictor hit rate with the explicit fast path.
Separating the hot path into a prefix before calling into a separate cold function should still generate better code. Your prefix only needs to allocate registers and stack space for just that single path. You would only pay the spilling costs in the old code off the hot path rather than every instruction. And I would expect the branch prediction accuracy of that prefix check to be higher than having the hot and cold paths all dispatching through the same tree of branches.
However it's speculation until you measure so I could be wrong.
Good article in any case, I enjoyed reading along.
Don't remember exact results but you could clearly see the stages that made up the raw computation performance differential (12x at the time iirc) between CPython and V8(JS).
Each of the above steps made up for a 2x-4x differential (don't remember the ratios exactly but combined about 12x or the V8 / CPython differential).
- Interpretation vs JIT (surprisingly a smaller than expected benefit)
- Memory model, moving from naive referece counting (very frequent per-operation bookkeeping operations) vs GC (GC does work, but compared with a GC doing small/incremental work it's miniscule compared to a naive ref-counter)
- Moving to tagged primitive integers from a "fat" tagged type (ie tag+ptr/value), biggest surprise to me, a bit like in this article.
Like the article mentions in the end, you have twice the number of values to move around, with singular values they just ride along in registers but also the fatter representation will make it far harder for the compiler to manage register allocations, remember a dynamic runtime doesn't only move around values, there's often GC or other context objects being kept around that contribute to register pressure.
On top of that, I don't remember the exact author, probably referenced in the old 90s Agesen type inference papers, but a very high percentage of operations in compiler code is just related to moving around values (think function arguments,etc), every instance of those becomes moving around 2 values instead of just a single register.
Tl;Dr; If it's not your first rodeo in compilers, IMHO just design your runtime primarly for register-passable values from day one, it might feel like premature optimization, but since the value model will permeate so much of the runtime, the knock-on effects once you do decide to fix it probably makes it worth to go with it from day 1.
One cannot expect a compiler to come up with such encoding.
this is brilliant, love it. stealing this idea immediately.
One could, however, imagine a sufficiently expressive language that allows the developer to specify the encoding schema without resorting to raw 64-bit words.
I'm not sure being this pedantic is particularly useful in titles though...
1. Do you really want the rust compiler to run at the speed of an llm?
2. Compiler optimisations are already extremely unpredictable with deterministic compilers[1], I hate to think how unpredictable your compiler would be.
3. What if someone else wants to build the software, do they have to decide on optimisations now? What if the optimisation depends on your features not available on old generations of CPU? (There is a reason we don’t compile with -march=native)
4. Compilers already have “unsafe” optimisations, but people rarely enable them (-ffast-math)
This new code also supplies similar abstractions. That actual specific code is much harder to reason about, but most users--and even the next person who works on the interpreter--simply won't care, or even know what is going on underneath the hood. The abstractions provided by the author do that work and apparently do it cleanly.
For most use-cases, that extra hand-written code isn't worth it. But in specific cases it can be, and the author has actually measured the value and determined that it is.
Also, Rust does try to do some of these optimizations itself. These aren't exposed in the stable language to let you do some more advanced things, but it wouldn't be impossible for you to get the best of both worlds by letting you communicate this stuff more directly to the compiler. Right now those things are more like "this value is where you should put the tag" than the more advanced stuff here, though. Would be cool to see someday!
The bit operations involved are pretty simple and won't take you long to figure out even if you've never done them before.
In the case of a tagged object in Rust, depending on how well the compiler can wrangle through it, you might even be able to add a `.unpack()` method that returns a pretty enum from a packed value, that you can pattern-match on or whatever, and let the compiler remove all the code of unpacking unused cases.
(using that directly for the addition example would end up less efficient of course, but still most likely beneficial. It's after this when there's a potential true readability vs performance tradeoff)
...unless it's supported by the language as a first class feature. See for example C++ and RVO.
enum Value {
Float(f64),
Ptr(*const T),
}
That being said, the optimization is complex that may be insufficient:
> For my boxing scheme, I picked a bias value such that the lowest two bits end up being 10. That 1 in bit index 1 indicates that doubles can't be directly compared for equality. Amazingly, we only lose two bits of exponent, and we keep the full precision of the mantissa, meaning we lose no significant digits in the flonum representation.
This suggests the optimization needs more information about specifically how you want to box the float. There probably is some primitives worth considering standardizing to make this kind of optimization possible so that the tunable parameters are passed as const generic values.
enum Value {
SimpleFloat(64bit value),
ComplexNan(Heap pointer)
Ptr(*const T)
}
I'd be very unhappy if a compiler silently did this to me - it would make performance extremely hard to reason about. But it's not quite as bad as changing the semantics.
That... might actually be an improvement?
Like just open Claude Code and ask it to find optimizations. That's the right place for this kind of optimization.
(also; if anything, the title is implying the exact opposite of "Rust compiler was able to optimize ...", "Replacing a Rust [...] with [...]" is clearly moving away from Rust-magic to something else)
FWIW this post was very well received on the Rust subreddit. They loved it and it got over 350 upvotes, so that community definitely didn't receive it as some sort of attack on Rust.
Unless, again, the title was edited at some point?
Rust provides for example NonZeroU8 which is an 8-bit unsigned integer that's never zero, leaving it with 255 possible values and a convenient niche. You cannot make one of these yourself directly, because the mechanism used by Rust itself is a deliberately perma-unstable compiler-only proc macro which says "Hey compiler, I promise I only ever use bit patterns 0x01 through 0xFF inclusive".
Today you can either - hide a NonZero type inside your type and use that to get the niche, or, use an enum itself which automatically knows ever pattern it didn't use is a niche. In the future a hypothetical "Pattern Types" feature would let you make such types yourself as easily as Rust does
Personally I would like to make a Balanced set of types, like BalanacedI8 (the 8-bit integers except the most negative, so -127 to +127 inclusive) because I think lots of people have a use for types like i8 or i32 but don't need their unbalanaced most-negative value and could re-purpose it this way. And you can make such types... indeed I have... but it's only really practical in unstable Rust.
For a system language I wish Rust would support such things rather than coming with NonZero hacks.
NonZero isn't a hack: it's an example of a common pattern. If pattern types were available today, you'd still want NonZero, as an example of a pretty standard pattern.
The idea is, as always: prove out the specific version, then generalize.
(typep 3 '(or (integer 0 10) (integer 50 100)));; => TI don't think it's fair to write a misleading title then tell people "they're reading too much into it".
Implying one thing then walking it back in the article or having the article be about something totally different, then saying people should read the article and not pay attention to the title is just manipulative to your audience.
What appears to be happening as we see in several comments is that some users cannot find any technical reason to use Rust so they rely on a belief that it is somehow magically perfect to justify using it and and the idea that it hasn't perfectly found some creative packing solution, despite the rest of us wondering why one would expect any compiler to – it not really being its job, is felt as an attack on their use of Rust. Someone developing irrational feelings towards an inanimate tool isn't on the article's author.
Like I said in the first place, you can remove the word rust, and nothing changes. That's how you know what's wrong.
It's like a news report saying "black man caught embezzeling". It might be a fact, but it's an irrelevant fact, and it begs the question why it was pointed out. He was probably also a vegetarian, Jewish, a bird watcher, an uncle...
And it's not that there is some weird rule that you have to avoid saying black or rust or whatever. It's simply that if you say something, then the _only_ reasonable way to interpret it is that there was some reason to say it.
You state an equation or give a list of items, it is irrational to assume anything other than that all of the terms or items are relevant.
In this case, rust is just the language being used, which is happenstance. It doesn't matter what language was used. You don't have to go out of your way to hide the language or any silly suggestion like that, but reading the title alone says that there is something about rust and enums. There only 3 items in the title, rust, enum, 64bit word. You can't fault anyone for defaulting to the conclusion that rust, enum, and 64bit word are the essential concepts that will be discussed.
The article isn't bad, and frankly the title isn't even so bad as to be a moral failing or anything. They ARE happening to be working in rust while developing this optimization.
It's simply that it's also entirely correct and reasonable to read the title as saying the words that it says. And the title says something that the content does not.
You wouldn't be able to reasonably use something like "Replacing an Enum with ..." because, especially where enum in Rust means what other languages call sum types, the data representation can be anything. But even the more traditional use of enum isn't defined by any particular data representation. The whole point of an enum is that any value used in implementation is treated as being opaque! Whereas in this case the value is significant.
I mean, you wouldn't be able to no more than you could replace the title with "Hey you, yes you, read this". Which obviously you could do. But it would be a poor title as you wouldn't be able to figure out what the article is about. This title is great because you can predict exactly what the article is about before reading it. I'd even go as far as to say that this is one of the better titles I've seen on HN in a long time.
Granted, it does require technical familiarity to be able to grok it. I can appreciate those who have developed irrational feelings for an inanimate tool aren't coming with a very strong technical background, but who cares about them? The intended audience is clearly technical folk.