GoKawiilReplacing a Rust Enum with a 64-bit Word Made My Interpreter 17% Faster
This blog post is the sixth in a series about my work building and optimizing the Plush language interpreter and virtual machine. The previous one was Speeding Up the Plush Garbage Collector. In the last post, I explained how a few simple changes made the copying GC over 16x faster, and brought the collection time for a million objects down to around 7 ms. I'm having a lot of fun optimizing Plush just for the sake of it, but I'm also doing it with the goal in mind of being able to make the language fast enough to render 3D animations in real-time, even though it's interpreted.
Plush is a dynamically-typed language, in the same family as Python, JavaScript, Ruby, Lua, and Lox. Dynamic languages like this have the property that types are attached to values rather than variables, and so to propagate values around programs, an interpreter typically has a Value type that can represent any value that could exist in the language. What I did with the original version of Plush is that I used a plain Rust tagged enum. This is nice because Rust makes working with tagged enums very convenient, as we can dispatch to different Value subtypes using the match statement:
// The old Rust Value type as a tagged enum enum Value { Undef, // Uninitialized var or field, reading triggers an error Nil, False, True, Int64(i64), Float64(f64), String(*const Str), // Immutable string HostFn(&'static HostFn), // Function exposed by host VM Fun(FunId), // Non-closure Plush function Closure(*mut Closure), // Closure that captures variables Cell(*mut Value), // Mutable variable captured by a closure Object(*mut Object), // Class instances Array(*mut Array), // JS/Python style array/list ByteArray(*mut ByteArray), // Fast raw byte array (e.g. frame buffer) Dict(*mut Dict), // JS/Python style dict Class(ClassId), }
As you can see above, Plush, even though I still consider it a toy language, has many different value types. The language has objects which are class instances, which are efficient to access, but it also has JS/Python style dictionaries, which make JSON-style syntax possible. There are also two distinct numerical types, Int64 and Float64 . I made this choice because it always kind of bothered me that JavaScript pretends everything is a double, while JS engines will actually keep track of what's an integer behind the scenes. The thing that's most unfortunate though is not the number of enum variants here, it's that this enum is a whole 16 bytes (128 bits) wide. Each enum variant needs only 64 bits, and the enum tag that Rust creates only needs 8 bits, but because of memory alignment constraints, Rust may need to use a whole 128 bits for each value. It might seem like no big deal, but if you have a large array of values, that array will end up with a ton of empty, wasted bytes inside of it. This is the kind of thing that makes VM engineers cry themselves to sleep at night.
For a little while now, I've been thinking that I could design a more efficient low-bit tagging scheme to make it so that the Value type fits inside of 64-bits. There's a classic trick which is derived from the fact that on a 64-bit system, heap object addresses are typically aligned to 8-byte boundaries, which means that the lowest 3 bits of the address must be zero. That means you can essentially steal these bits to pack extra information in there. You can also borrow the two lowest bits of integer values, with the assumption that integer values will very rarely need to use the full 64-bit range, because for reference 2^64 ~= 1.84 * 10^19 . That's a very large value. If you have a variable that represents say, the number of lines in a text file, or the number of enemies in your game, or any other numerical quantity, it's very unlikely to reach that value. With a modern CPU that can dispatch multiple instructions per clock cycle, if you were to execute a loop such as for (uint64_t i = 0; i < UINT64_MAX; ++i) , the loop would likely take over a decade to finish executing.
A more sophisticated tagging scheme can clearly reduce memory usage, but it also means that we have to introduce bitwise operations to be able to tell what's an integer, a pointer or a float. We also need extra bitwise operations to unpack some values to operate on them. That means extra instructions the CPU has to run. A skilled VM engineer once told me that 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. Packing and unpacking floats though is more complex and requires several instructions. I was a bit worried about the performance impact, and needing to trade memory efficiency for a bit of a performance loss. As it turns out, my fear was completely unfounded, as we'll see later in this post.
An Efficient Low-Bit Tagging Scheme
Claude and I co-designed and iterated on the value representation found in this source file. It fits nicely in a Rust newtype wrapping a u64 . As you can see, it has many convenience methods to make it easy to work with, compensating for the loss of the Rust enum. Most of the methods are marked as always inline for performance, since they're used everywhere in the interpreter loop. The diagram below illustrates how the value representation is structured in more detail:
The tagged value representation.
... continue reading