Optimized enum sizes in Rust

Of the many ideas that Rust borrows from other languages, its enums are one that people seem to get the most excited about. They are sometimes referred to as sum types, algebraic data types, or tagged unions, and although they are typically associated with functional programming languages there’s nothing that precludes them from being used in other paradigms as well.

Lots of people seem to agree that they’re useful, because we’re seeing them pop up everywhere. Other new languages - like Elm, Swift, and Typescript - also have them, and C++17 has std::variant in the standard library (which, like a number of other things in the standard library, began its life in Boost as boost::variant).

In this article I’m going to assume just a little bit of familiarity with Rust’s enums, although if you’ve used the analogous features in another language then you should be fine. If this is completely new to you, then the enum chapter in the Rust book is a good place to start.

Memory layout of an enum

Of the various names they go by, I think tagged union best describes the way an enum is represented in memory. Rust’s representation of an enum is exactly that - the union of all the possible variants, which takes up space equal to the size of the largest payload (much like a C union), and the tag, which tells us which variant we have. Consider the following enum:

enum Name {
    Anonymous, // 0 byte payload
    Nickname(String), // 24 byte payload
    FullName{ first: String, last: String }, // 48 byte payload
}

In this case the largest variant is the FullName. Rust’s String is 24 bytes (a pointer, size, and capacity), so the payload is 48 bytes. We need one more byte for the tag, but for alignment reasons it’s going to cost us 8 bytes. Therefore, std::mem::size_of::<Name>() == 56:

[ tag (8 bytes) ][ empty OR String OR { String, String } (48 bytes) ]

Using up 8 bytes for something that can only have three different values seems pretty wasteful. For this reason, Rust has an optimization for some common cases involving references. The null pointer optimization takes advantage of the fact that a reference can never be null, and instead uses that as a special value to represent the tag. If you have an Option<&T>, then instead of

[ tag (8 bytes) ][ pointer (8 bytes) ]

an Option<&T> is represented as

[ pointer (8 bytes) ]

and if the pointer happens to be null then we know that our Option was None, but if it’s a valid pointer then we know we have Some(&T).

Tradeoffs in Stylo

At Rust Belt Rust 2017, Josh Matthews gave an excellent talk about integrating the Stylo CSS engine, which is written in Rust, into Firefox, which is largely C++. One of the pain points he described in his slides was that when you start nesting enums, the tags accumulate and can quickly snowball into some fairly large types. The example he gave was this:

enum BorderStyleValue {
    Solid, Dashed(Option<u32>)
}
type BorderStyle = Option<BorderStyleValue>;

BorderStyle has enums nested three layers deep, and winds up being quite heavy at 16 bytes (a 4 byte payload, plus three tags that are each 4 bytes due to alignment). In their case, they decided to go for something a little less ergonomic, but more memory efficient:

enum BorderStyle {
    None, Solid, DashedNone, Dashed(u32)
}

This type is only 8 bytes, and while it can represent exactly the same things as the first version, it’s not as nice to work with. Everything is a tradeoff, and in this case memory usage was more important.

Have your cake and eat it too

Did I just say that everything is a tradeoff? Well, it doesn’t have to be.

Remember the null pointer optimization? It turns out that there are lots of other cases where all the possible values of a type can fit into less bits that it’s been allocated, and those extra bits can be used for the tag. For example, a bool really only needs one bit, but it gets padded to a full byte. There are seven bits that can be filled with more information!

A recent PR to the Rust compiler refactored how types are layed out in memory, which makes some new optimizations possible. Whereas in Rust 1.22 an Option<bool> is two bytes, in 1.23 it fits into one byte.

Another place where we find extra bits that aren’t being used is in the tags of other enums. In the original definition of BorderStyleValue from Josh’s talk, each of the nested enums was only discriminating between two variants. Each tag was padded to four bytes, even though each one only carried a single bit of useful information. In Rust 1.23 all of that information can be packed into a much tighter space, and BorderStyleValue can be represented like this:

[ all the tags (4 bytes) ][ u32 (4 bytes) ]

Now it’s 8 bytes, just like the less-ergonomic-but-more-memory-friendly version. Going forward, the Stylo developers won’t have to make tradeoffs like this anymore.

There’s still some padding in this type - the tags aren’t making use of all four of those bytes - but that just means that if one were to wrap this in another enum then its size won’t snowball like it did before. A Result<BorderStyleValue, i32> will still only be 8 bytes.

Conclusion

This is an example of how leaving implementation details unspecified gives flexibility to make great optimizations.

Although I think the ASCII memory layout diagrams in this article are a useful mental model, they might be not be correct. If Rust had guaranteed that the memory layout of an enum is always a tag followed by a union then it wouldn’t be possible to make this optimization without breaking somebody’s code. Instead, the compiler retains the freedom to optimize the layout of your types, and your code will automatically be more memory efficient, simply by updating to a newer version of the compiler.