I learned a little bit about Rust Enum today, and before you start reading, you can guess what the output of the following Rust code is on a common 64 bit machine.
In this Rust Playground you can see the result.
Rust enum is essentially a tagged union, which corresponds to the sum type of the algebraic data type, and is not expanded upon here. In Rust enum implementations, a byte is usually used to store the type tag, which means that ideally the following two structures are equivalent.
Under this implementation, enum is not zero overhead in many scenarios. Fortunately, Rust has never defined an ABI, and enum with data cannot even be represented by
repr(C), which gives Rust plenty of room for fine-grained optimizations of enum memory layout. This article will cover some of the relevant optimizations under
Before we start exploring the details, we need to prepare a helper function that will help us look at the memory structure of our variables.
Take the above
Attr as an example.
P is a common smart pointer type, including
Box. This is probably the best known example of enum layout optimization. rust recommends using
Option<P<T>> for nullable pointers, which implements null safety.
Option<T> is represented in rust as an enum.
Without any optimization, it is clear that there is an unnecessary overhead, and that a null pointer can fully represent the semantics of
None. Since this is too common, rustc not only makes targeted optimizations, but also standardizes them.
If T is an FFI-safe non-nullable pointer type, Option is guaranteed to have the same layout and ABI as T and is therefore also FFI-safe. As of this writing, this covers &, &mut, and function pointers, all of which can never be null.
One tip is that this hack is not specific to
Option, but to pointer types. Any custom enum that satisfies the condition can achieve the same effect.
The fundamental reason why
Option<P<T>> can be optimized is that there is an always illegal value under the in-memory representation of P, and the corresponding enum only needs to represent an extra value to express the redundant type. Exceeding this constraint causes this optimization to fail.
bool in rust occupies one byte and has only two legal values,
False, which correspond to the memory representations
0u08. We can interpret this to mean that
bool has 254 illegal values available for the type tag.
To take it a step further, we can be a little more forceful.
Correspondingly, Ordering has three legal values that also apply to this optimization.
In fact, the compiler does not make special judgments for bool, Ordering, and any enum of less than 256 kinds itself satisfies the condition to be optimized, i.e., there will be (256 - kinds) empty bits in the type tag.
Struct, Tuple, etc. are all Product types, and are often implemented by storing all the fields in order and making extra padding, so it is a logical optimization that if one of the fields of the struct has an empty space, then the enum tag can be stuffed into it.
Let’s go back to the example at the beginning of the article.
A and B both take 16 bytes due to padding, while
Option<B> only takes 16 bytes due to the presence of a bool field
.2, which is optimized into the bool, and
Option<A> uses 24 bytes.
An easy optimization to think of is to use undefined memory in the padding to store the type tag. unfortunately, the layout of A is determined when compiling A itself, and the data stored in
Option<A> in the padding of
A is undefined behavior. This also leads to the funny result that by storing an extra field,
Option takes up less space.
Of course, it is perfectly possible to use padding to store data, but only if it does not affect the memory layout of the child data structures. if we put
Option manually expand.
In this case, since the data of OptionA is stored directly inside Some, it is perfectly possible to use padding to store the type tag when instantiating without causing potentially undefined behavior.
Optimization possibilities for custom structs
Currently, all enum layout-related optimizations are suitable for type-specific hacking by the compiler, and we have no control over the layout of our custom structs in the enum. To optimize some common scenarios, rust also provides
NonZero* to represent non-zero integers, while the compiler makes
size_of::<Option<NonZeroU8>> == size_of::<u8>. But this can only be handled by the standard library case by case, and real requirements are very complex, e.g. sometimes we may need
NonMaxU64, or for example use a third-party library
Option<ordered_float::NotNan<f64>> will not be optimized.
Optimizing for custom interfaces requires introducing very complex mechanisms to tell the compiler at compile time what memory structures are illegal for a type. I currently feel that a possible implementation would be const trait + const iterator, giving the compiler an iterator over potentially illegal values. However, I don’t see an RFC for this at the moment.
All the examples in this article can be found at Rust Playground.