Replacing a Rust Enum with a 64-Bit Word Made My Interpreter 17% Faster

Join the discussion

• Hacker News
• That's very unpleasant to hear. It's sad to be reminded that Rust compiler is not magic and cannot just... do these things somehow. Sure, all abstractions do have some cost, but, man, 17% performance gain by virtue of replacing enum with this monstrosity? That's very annoying.
  by krick
• It's so funny to see a "compiler is magic" people encountering reality in the wild. No, an algorithm that must work for every single user of the language cannot possibly optimize for every individual's use case. It is trivial for hand-written code to outperform a compiler on bespoke use cases. That anyone perpetuated otherwise was a lie they told themselves to feel secure in their ignorance and incompetence, because it's more comfortable to excuse your lack of skill if you believe that no human could ever out-perform a compiler. The saddest part is the barrier isn't even that high. You, and the rest of the magical compiler religious believers, could learn to do this, if only you tried instead of believing in your fairy tale.
  by applfanboysbgon
• A 64-bit sum type can't magically combine an i64, f64, and several raw pointers, each of which carry a full 64 bits themselves. You have to change the semantics of the code. Some semantics could be expressed more easily with compiler improvements, allowing eg `Aligned<T>` like `NonNull<T>`, or `FiniteF64` like `NonZeroU64`, or even `#[range(0..1<<60)] u64`, but you still couldn't overlap two `Aligned`s in one enum, because only one can be stored unchanged, the others need masking off before usage. Even if the enum semantics allowed this, I'm not sure the compiler should do this kind of compute/memory tradeoff automagically. Which doesn't mean you can't write nice abstractions over it, there's a few tagged ptr crates which aim to do it for you
  by speedstyle
• It can't do these things because it's not wanted. Say you have the following:

    enum Value {
        Float(f64),
        Ptr(*const T),
    }
  

  Do you want the compiler to disallow certain bit patterns in the Float variant simply so that it can implement NanBoxing?
  by maplant
• "the smart thing to do is to give integers zeros as their tag bits, because then, adding or subtracting two shifted integers remains a plain add or sub machine instruction"

  this is brilliant, love it. stealing this idea immediately.

  by nwhitehead
• Yep, felt quite stupid when I heard this ages ago and hadn't thought of it (Iirc in an old IRC chat about Maximes old Higgs runtime), from my memory V8 did this from day 1.
  by whizzter
• Ocalm also has 63bit integers in case you want other implementations in the wild.
  by wmedrano
• But isn’t the enum far more readable and maintainable than having to do bit operations on things?
  by gigatexal
• It can be worth sacrificing readability and maintainability for better performance in hot code.
  by wat10000
• If you add "fits in a register" to your list of correctness requirements, then it's no-go even if the source has less cognitive overhead.
  by mwkaufma
• Highly optimized code in hot paths is rarely readable.
  by diath
• The computer's the one running the code, and it'll be running it a lot (or so its author hopes), so it's probably worth bearing its limitations in mind in the interests of making its life easier (so to speak) rather than prioritising the people who will modify the interpreter - a far less common occurrence.

  The bit operations involved are pretty simple and won't take you long to figure out even if you've never done them before.

  by tom_
• > As you can see, it has many convenience methods to make it easy to work with, compensating for the loss of the Rust enum.

  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!

  by steveklabnik
• The reason the enum is so nice is that it works as a terrific language-supplied abstraction that covers up those bit manipulations. It's very nice to get those abstractions for free like you do in Rust, but it can't be optimal for every specialized use case.

  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.

  by compiler-guy
• Take a look at triomphe's ArcUnion and extrapolate from there. Basically make a crate for just your 64bit union type, do it unsafe there, test with miri, and now you have a safe 64bit type you can use with match. You're happy digging around assembly so this is well within your wheelhouse. The only challenge will be if you do use miri to verify then you need to use the 'provenance-preserving' pointer adjusting functions. Worth the learning experience in my opinion. I did one for my system and it was super fun and had the performance impact you describe.
  by lowbloodsugar
• The article title is misleading. It is not that Rust compiler was not able to optimize some low-level operations. Rather the author came up with encoding schema that fit most things the interpreter dealt with into 64 bit. This replaced the previous schema that used 128 bit for everything but that can be directly mapped into Rust enums. The catch was that it was necessary to allocate some things on the heap and use pointer indirection but that was used for rare values so on average the new schema provided nice win.

  One cannot expect a compiler to come up with such encoding.

  by fpoling
• When I think of how a "compiler" could make these optimizations, I think the right place is an optimizing LLM (so, just a regular coding agent that you prompted to find optimizations like this one), making the changes in source at the request of the developer. That provides the dev with adequate input on whether they would like to opt-in to an unsafe optimization like this one. The compiler can continue to do deterministically-safe optimizations.
  by pbiggar
• What is misleading about the title? A custom encoding scheme is exactly what it suggests. Maybe it has been edited since your comment was posted?
  by win311fwg
• > One cannot expect a compiler to come up with such encoding.

  One could, however, imagine a sufficiently expressive language that allows the developer to specify the encoding schema without resorting to raw 64-bit words.

  by RossBencina
• I'm not convinced the performance benefits are entirely the result of the more compact object representation. It definitely would help, but looking at the code snippets the author provides for the add instruction there's an important structural change that would be making a huge difference.

  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.

  by MindSpunk
• But CPU branch predictor should have figured out hot paths in the original implementation?
  by vbezhenar
• This was probably 15-20 years ago at this point but I was doing a lot of micro-tests in terms of dynlang->C/C++ transpilers (in relation to my MsC thesis) to see the effects of different value-models, GC strategies and the win of compiled code vs interpretation/JIT (Some might say that a transpiler via C skews the result but it did more or less optionally generated code without delving into writing a good lowlevel codegen).

  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.

  by whizzter
• Author here. The disassembly for the old enum handling had many spills, simply because the old value enum can't fit in a single register. If you have an instruction that two operands with two of those big value enums, it needs 4 registers instead of 2. That, coupled with better cache-friendliness, explains a lot.
  by maxime_cb