3 ms·

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:

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 2y 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 2y 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 2y ago
    Updating an aligned pointer is atomic. If you haven’t tagged it by moving bits to a neighboring word.
    - packetlost 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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.
      - 2y ago

hinkley 2y 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 2y 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 2y ago
  Updating an aligned pointer is atomic. If you haven’t tagged it by moving bits to a neighboring word.
  - packetlost 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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 2y 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.
    - 2y ago