8 ms·

A surprising enum size optimization in the Rust compiler

148 points by returningfory2 1y ago

packetlost 1y ago
I don't think it's actually "flattening" the enums discriminant spaces (though maybe it is). My guess is this is just 32-bit alignment requirement (ie. bytes 1:4 are padding) + sub-byte discriminant sizes. The surprising thing here is that the ordering of Outer's variants doesn't match the ordering as defined, instead having variant D's discriminant be 0 (0 << size_of::<Inner's discriminant>). size_of::<Inner> is actually 33 bits and size_of::<Outer> is 34 bits and then you just apply alignment requirements to each field. Actual size_of calls will account for alignment and padding, but the compiler knows the truth. What's cool about this in general is nested match statements can be flattened into a jumplist (idk if rustc does this, but it's possible in theory).
- hinkley 1y ago
  In a lot of languages space optimizing Optional Types without using a reserved enum value or pointer tags would lead to memory model problems with atomically writing two values at once which might be more easily solved in a borrow semantics world. I hope there is someone out there mining research papers for the implementation strategies that were abandoned as unworkable due to bookkeeping issues, which Rust has already paid. But in the case of Options they tend to be both write-once and short-lived, so that removes a lot of necessity. Options are going to stay mostly on the stack and in async callbacks, unless they go into caches. But for other data structures where multiples fields need a tag, I suspect Rust could use some bitfields for representing them. You’d need a fairly big win to make it worth implementing however.
  - packetlost 1y ago
    I'm honestly not exactly sure what you're talking about, but the fundamental limit for atomic writes is usually the register-size for a CPU which is usually 64 or 32 bits. Considering enum variants are often larger than a single register in size, I don't see how atomic writes would ever be sane expectation.
    - hinkley 1y ago
      Updating an aligned pointer is atomic. If you haven’t tagged it by moving bits to a neighboring word.
      - packetlost 1y ago
        I see. Yeah, you would either have to add the tagging to the upper bits of the pointer itself or concede that updates to a tagged type is not atomic. I feel like the latter is fine in most every scenario I've encountered in Rust (thanks to borrow checker rules) but in other languages the same cannot be said.
    - dataflow 1y ago
      > the fundamental limit for atomic writes is usually the register-size for a CPU which is usually 64 or 32 bits CPUs nowadays support double the largest general-purpose register width. Unofficially, some CPUs can also do twice that: https://rigtorp.se/isatomic/ https://rigtorp.se/isatomic/
  - Georgelemental 1y ago
    > In a lot of languages space optimizing Optional Types without using a reserved enum value or pointer tags would lead to memory model problems with atomically writing two values at once which might be more easily solved in a borrow semantics world. Yes, Rust suppresses the niche optimization for values wrapped in an `UnsafeCell` (which is how you signal to the compiler that “atomically writing two values at once” might happen). https://github.com/rust-lang/rust/pull/68491 https://github.com/rust-lang/rust/pull/68491
- LegionMammal978 1y ago
  > I don't think it's actually "flattening" the enums discriminant spaces (though maybe it is). It is. One easy way to see this is with an Option<Option<bool>> [0]: if both options are Some, it takes the value 0 or 1 depending on the boolean; if the inner Option is None, it takes the value 2; and if the outer Option is None, it takes the value 3. And as you keep adding more Options, they take values 4, 5, 6, etc. to represent None, while still only taking up 1 byte. [0] https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=6bc8f4971842fe29fcc703c872517816 https://play.rust-lang.org/?version=stable&mode=debug&editio...
  - packetlost 1y ago
    I think that's just niche optimization. If you change from bool to a u8 it doesn't use the invalid bit pattern as a discriminant even though it could: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=cdfd44cebbd77cfee6a113e94ca560a7 https://play.rust-lang.org/?version=stable&mode=debug&editio...
    - LegionMammal978 1y ago
      What invalid bit pattern? A u8 can be anything from 0 to 255, so the Option necessarily has to put its discriminant into another byte. If you replace it with a NonZeroU8, then the compiler will duly use the forbidden 0 value for the first Option level, and a separate byte for all further levels. (Granted, in the None variant, the byte used for the u8 is not usable, but if we're already using a separate discriminant byte, 256 variants should be plenty.)
      - packetlost 1y ago
        The same way as it does in the bool case? The u8 bits are invalid if either of the Options are None, but in particular if the Outer option is Some the Inner is None the bit that would otherwise be used for the bool (in the first example) is used to discriminate Outer, but doesn't do so in the case of the u8.
        1y ago
mmastrac 1y ago
This is a great way to see why invalid UTF-8 strings and unicode chars cause undefined behaviour in Rust. `char` is a special integer type, known to have a valid range which is a sub-range of its storage type. Outside of dataless enums, this is the only datatype with this behaviour (EDIT: I neglected NonZero<...>/NonZeroXXX and some other zero-niche types). If you manage to construct an invalid char from an invalid string or any other way, you can defeat the niche optimization code and accidentally create yourself an unsound transmute, which is game over for soundness.
- NoTeslaThrow 1y ago
  > This is a great way to see why invalid UTF-8 strings and unicode chars cause undefined behaviour in Rust. What does "undefined behavior" mean without a spec? Wouldn't the behavior rustc produces today be de-facto defined behavior? It seems like the contention is violating some transmute constraint, but does this not result in reproducible runtime behavior? In what context are you framing "soundness"? EDIT: I'm honestly befuddled why anyone would downvote this. I certainly don't think this is detracting from the conversation at all—how can you understand the semantics of the above comment without understanding what the intended meaning of "undefined behavior" or "soundness" is?
  - mmastrac 1y ago
    > What does "undefined behavior" mean without a spec? While not as formalized as C/C++, Rust's "spec" exists in the reference, nomicon, RFCs and documentation. I believe that there is a desire for a spec, but enough resources exist that the community can continue without one with no major negative side-effects (unless you want to re-implement the compiler from scratch, I suppose). The compiler may exploit "lack of UB" for optimizations, e.g., using a known-invalid value as a niche, optimizing away safety checks, etc. > Wouldn't the behavior rustc produces today be de-facto defined behavior? Absolutely not. Bugs are fixed and the behaviour changes. Not often, but it happens. This post probably answers a lot of your reply as well: https://jacko.io/safety_and_soundness.html https://jacko.io/safety_and_soundness.html
    - 1y ago
pitaj 1y ago
This actually is niche optimization. The outer enum is using the niches available in the tag of the inner enum for its own discriminant. The author seems to have a limited understanding of niche optimization.
- returningfory2 1y ago
  In the strictly technical sense I agree, however in the Rust community when people say "the niche optimization" they usually are referring only to the simplest case. For example in the book Rust For Rustaceans (written by a pretty serious Rust expert and aimed at intermediate-level Rust programmers) the nice optimization is described as "the Rust compiler using invalid bit patterns to represent enum variants that hold no data". Note the "hold no data" part - it doesn't incorporate the case in the blog. In any case, the definition of what is exactly niche optimization is besides the point. The point of the post is: the literature gives you the impression that there's one limited form of enum size optimization in the Rust compiler, but in fact there are other optimizations too. And knowing this is useful!
  - Dylan16807 1y ago
    > In any case, the definition of what is exactly niche optimization is besides the point. The point of the post is: the literature gives you the impression that there's one limited form of enum size optimization in the Rust compiler, but in fact there are other optimizations too. And knowing this is useful! It's useful if you got that specific impression. But I didn't. So I was disappointed and unenlightened because I was promised a non-niche optimization and I didn't get one.
lordnacho 1y ago
Does the niche optimization require the compiler to know things about the type? So that only certain specializations will work? Also, how do I get some code to do the memory layout vizualizer, perhaps one that is a bit more advanced and knows what pointers are?
- pornel 1y ago
  Internally the compiler tracks what "niches" exist in types, like minimum and maximum valid values, and takes the unused values for enum tags. One thing it can't use is padding in structs, because references to individual fields must remain valid, and they don't guarantee that padding will be preserved.
  - deleted 1y ago
    [deleted]
  - deleted 1y ago
    [deleted]
subarctic 1y ago
When was this implemented? I remember when people used to have to manually flatten nested enums in order to save space
- returningfory2 1y ago
  Many years ago I think, here: https://github.com/rust-lang/rust/issues/46213 https://github.com/rust-lang/rust/issues/46213. (Found this via https://lobste.rs/s/w3jjb2/surprising_enum_size_optimization_rust#c_cdosot https://lobste.rs/s/w3jjb2/surprising_enum_size_optimization...)
kazinator 1y ago
This seems like it could be summarized as tag merging. When the member of an enum is another enum, then the two can be effectively merged, rather than tested, so that there is one discriminant tag. The tag values have to be displaced/renumbered so that their ranges do not overlap.
Joker_vD 1y ago
Yeah, there are all sorts of nifty little tricks about compressing the enums, Appel dedicates a huge chunk of section "4.1. Data representation" on it in his "Compiling with Continuations" book about the internals of the SML/NJ compiler for the Standard ML, and ultimately concludes that the returns are quickly getting really diminishing with those, and since datatypes can actually be abstract in ML (in pretty much the same way they can be in Rust), the applicability of those tricks is generally restricted to unexported, intramodular datatypes.
- kristianp 1y ago
  I like how Appel's book is still being referenced despite being first published in 1992!
ComputerGuru 1y ago
I have actually requested an even more intelligent/aggressive size optimization for nested enums, where values are automatically reassigned to not coincide/conflict to enable tag-less differentiation. Consensus was that it’s a big ask though doable, but maybe possible to implement in a more restrictive version. https://rust-lang.zulipchat.com/#narrow/channel/131828-t-compiler/topic/Suboptimal.20size.20of.20nested.20discriminated.20unions.2Fnested.20e.2E.2E.2E/near/440676847 https://rust-lang.zulipchat.com/#narrow/channel/131828-t-com...
- infogulch 1y ago
  Good idea! I like the solution of an explicit annotation setting the first variant's discriminant (the rest autoicrement?), which enables you to manually coordinate your enums to not overlap. Then an optimization for nested enums where if all cases are other enums with no overlapping discriminants they can all share one field. This seems achievable. The "but do it automatically" part seems rather problematic. Requiring global analysis is a big ask indeed. Say, if you change a variant's discriminant value, does that count as a semver breaking change? Probably. Would it be an ABI breaking change? Probably.
pcwalton 1y ago
That's a great article. Niche optimization might seem minor, but it actually results in substantial memory usage savings in real-world Rust applications, because idiomatic Rust uses enums everywhere.

I don't think it's actually "flattening" the enums discriminant spaces (though maybe it is). My guess is this is just 32-bit alignment requirement (ie. bytes 1:4 are padding) + sub-byte discriminant sizes. The surprising thing here is that the ordering of Outer's variants doesn't match the ordering as defined, instead having variant D's discriminant be 0 (0 << size_of::<Inner's discriminant>). size_of::<Inner> is actually 33 bits and size_of::<Outer> is 34 bits and then you just apply alignment requirements to each field. Actual size_of calls will account for alignment and padding, but the compiler knows the truth. What's cool about this in general is nested match statements can be flattened into a jumplist (idk if rustc does this, but it's possible in theory).

hinkley 1y ago
In a lot of languages space optimizing Optional Types without using a reserved enum value or pointer tags would lead to memory model problems with atomically writing two values at once which might be more easily solved in a borrow semantics world. I hope there is someone out there mining research papers for the implementation strategies that were abandoned as unworkable due to bookkeeping issues, which Rust has already paid. But in the case of Options they tend to be both write-once and short-lived, so that removes a lot of necessity. Options are going to stay mostly on the stack and in async callbacks, unless they go into caches. But for other data structures where multiples fields need a tag, I suspect Rust could use some bitfields for representing them. You’d need a fairly big win to make it worth implementing however.
- packetlost 1y ago
  I'm honestly not exactly sure what you're talking about, but the fundamental limit for atomic writes is usually the register-size for a CPU which is usually 64 or 32 bits. Considering enum variants are often larger than a single register in size, I don't see how atomic writes would ever be sane expectation.
  - hinkley 1y ago
    Updating an aligned pointer is atomic. If you haven’t tagged it by moving bits to a neighboring word.
    - packetlost 1y ago
      I see. Yeah, you would either have to add the tagging to the upper bits of the pointer itself or concede that updates to a tagged type is not atomic. I feel like the latter is fine in most every scenario I've encountered in Rust (thanks to borrow checker rules) but in other languages the same cannot be said.
  - dataflow 1y ago
    > the fundamental limit for atomic writes is usually the register-size for a CPU which is usually 64 or 32 bits CPUs nowadays support double the largest general-purpose register width. Unofficially, some CPUs can also do twice that: https://rigtorp.se/isatomic/ https://rigtorp.se/isatomic/
- Georgelemental 1y ago
  > In a lot of languages space optimizing Optional Types without using a reserved enum value or pointer tags would lead to memory model problems with atomically writing two values at once which might be more easily solved in a borrow semantics world. Yes, Rust suppresses the niche optimization for values wrapped in an `UnsafeCell` (which is how you signal to the compiler that “atomically writing two values at once” might happen). https://github.com/rust-lang/rust/pull/68491 https://github.com/rust-lang/rust/pull/68491
LegionMammal978 1y ago
> I don't think it's actually "flattening" the enums discriminant spaces (though maybe it is). It is. One easy way to see this is with an Option<Option<bool>> [0]: if both options are Some, it takes the value 0 or 1 depending on the boolean; if the inner Option is None, it takes the value 2; and if the outer Option is None, it takes the value 3. And as you keep adding more Options, they take values 4, 5, 6, etc. to represent None, while still only taking up 1 byte. [0] https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=6bc8f4971842fe29fcc703c872517816 https://play.rust-lang.org/?version=stable&mode=debug&editio...
- packetlost 1y ago
  I think that's just niche optimization. If you change from bool to a u8 it doesn't use the invalid bit pattern as a discriminant even though it could: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=cdfd44cebbd77cfee6a113e94ca560a7 https://play.rust-lang.org/?version=stable&mode=debug&editio...
  - LegionMammal978 1y ago
    What invalid bit pattern? A u8 can be anything from 0 to 255, so the Option necessarily has to put its discriminant into another byte. If you replace it with a NonZeroU8, then the compiler will duly use the forbidden 0 value for the first Option level, and a separate byte for all further levels. (Granted, in the None variant, the byte used for the u8 is not usable, but if we're already using a separate discriminant byte, 256 variants should be plenty.)
    - packetlost 1y ago
      The same way as it does in the bool case? The u8 bits are invalid if either of the Options are None, but in particular if the Outer option is Some the Inner is None the bit that would otherwise be used for the bool (in the first example) is used to discriminate Outer, but doesn't do so in the case of the u8.
      - 1y ago

mmastrac 1y ago

This is a great way to see why invalid UTF-8 strings and unicode chars cause undefined behaviour in Rust. `char` is a special integer type, known to have a valid range which is a sub-range of its storage type. Outside of dataless enums, this is the only datatype with this behaviour (EDIT: I neglected NonZero<...>/NonZeroXXX and some other zero-niche types). If you manage to construct an invalid char from an invalid string or any other way, you can defeat the niche optimization code and accidentally create yourself an unsound transmute, which is game over for soundness.

NoTeslaThrow 1y ago
> This is a great way to see why invalid UTF-8 strings and unicode chars cause undefined behaviour in Rust. What does "undefined behavior" mean without a spec? Wouldn't the behavior rustc produces today be de-facto defined behavior? It seems like the contention is violating some transmute constraint, but does this not result in reproducible runtime behavior? In what context are you framing "soundness"? EDIT: I'm honestly befuddled why anyone would downvote this. I certainly don't think this is detracting from the conversation at all—how can you understand the semantics of the above comment without understanding what the intended meaning of "undefined behavior" or "soundness" is?
- mmastrac 1y ago
  > What does "undefined behavior" mean without a spec? While not as formalized as C/C++, Rust's "spec" exists in the reference, nomicon, RFCs and documentation. I believe that there is a desire for a spec, but enough resources exist that the community can continue without one with no major negative side-effects (unless you want to re-implement the compiler from scratch, I suppose). The compiler may exploit "lack of UB" for optimizations, e.g., using a known-invalid value as a niche, optimizing away safety checks, etc. > Wouldn't the behavior rustc produces today be de-facto defined behavior? Absolutely not. Bugs are fixed and the behaviour changes. Not often, but it happens. This post probably answers a lot of your reply as well: https://jacko.io/safety_and_soundness.html https://jacko.io/safety_and_soundness.html
  - 1y ago

pitaj 1y ago

This actually is niche optimization. The outer enum is using the niches available in the tag of the inner enum for its own discriminant. The author seems to have a limited understanding of niche optimization.

returningfory2 1y ago
In the strictly technical sense I agree, however in the Rust community when people say "the niche optimization" they usually are referring only to the simplest case. For example in the book Rust For Rustaceans (written by a pretty serious Rust expert and aimed at intermediate-level Rust programmers) the nice optimization is described as "the Rust compiler using invalid bit patterns to represent enum variants that hold no data". Note the "hold no data" part - it doesn't incorporate the case in the blog. In any case, the definition of what is exactly niche optimization is besides the point. The point of the post is: the literature gives you the impression that there's one limited form of enum size optimization in the Rust compiler, but in fact there are other optimizations too. And knowing this is useful!
- Dylan16807 1y ago
  > In any case, the definition of what is exactly niche optimization is besides the point. The point of the post is: the literature gives you the impression that there's one limited form of enum size optimization in the Rust compiler, but in fact there are other optimizations too. And knowing this is useful! It's useful if you got that specific impression. But I didn't. So I was disappointed and unenlightened because I was promised a non-niche optimization and I didn't get one.

lordnacho 1y ago

Does the niche optimization require the compiler to know things about the type? So that only certain specializations will work? Also, how do I get some code to do the memory layout vizualizer, perhaps one that is a bit more advanced and knows what pointers are?

pornel 1y ago
Internally the compiler tracks what "niches" exist in types, like minimum and maximum valid values, and takes the unused values for enum tags. One thing it can't use is padding in structs, because references to individual fields must remain valid, and they don't guarantee that padding will be preserved.
- deleted 1y ago
  [deleted]
- deleted 1y ago
  [deleted]

subarctic 1y ago

When was this implemented? I remember when people used to have to manually flatten nested enums in order to save space

returningfory2 1y ago
Many years ago I think, here: https://github.com/rust-lang/rust/issues/46213 https://github.com/rust-lang/rust/issues/46213. (Found this via https://lobste.rs/s/w3jjb2/surprising_enum_size_optimization_rust#c_cdosot https://lobste.rs/s/w3jjb2/surprising_enum_size_optimization...)

kazinator 1y ago

This seems like it could be summarized as tag merging. When the member of an enum is another enum, then the two can be effectively merged, rather than tested, so that there is one discriminant tag. The tag values have to be displaced/renumbered so that their ranges do not overlap.

Joker_vD 1y ago

Yeah, there are all sorts of nifty little tricks about compressing the enums, Appel dedicates a huge chunk of section "4.1. Data representation" on it in his "Compiling with Continuations" book about the internals of the SML/NJ compiler for the Standard ML, and ultimately concludes that the returns are quickly getting really diminishing with those, and since datatypes can actually be abstract in ML (in pretty much the same way they can be in Rust), the applicability of those tricks is generally restricted to unexported, intramodular datatypes.

kristianp 1y ago
I like how Appel's book is still being referenced despite being first published in 1992!

ComputerGuru 1y ago

I have actually requested an even more intelligent/aggressive size optimization for nested enums, where values are automatically reassigned to not coincide/conflict to enable tag-less differentiation. Consensus was that it’s a big ask though doable, but maybe possible to implement in a more restrictive version. https://rust-lang.zulipchat.com/#narrow/channel/131828-t-compiler/topic/Suboptimal.20size.20of.20nested.20discriminated.20unions.2Fnested.20e.2E.2E.2E/near/440676847 https://rust-lang.zulipchat.com/#narrow/channel/131828-t-com...

infogulch 1y ago
Good idea! I like the solution of an explicit annotation setting the first variant's discriminant (the rest autoicrement?), which enables you to manually coordinate your enums to not overlap. Then an optimization for nested enums where if all cases are other enums with no overlapping discriminants they can all share one field. This seems achievable. The "but do it automatically" part seems rather problematic. Requiring global analysis is a big ask indeed. Say, if you change a variant's discriminant value, does that count as a semver breaking change? Probably. Would it be an ABI breaking change? Probably.

pcwalton 1y ago

That's a great article. Niche optimization might seem minor, but it actually results in substantial memory usage savings in real-world Rust applications, because idiomatic Rust uses enums everywhere.