7 ms·

> Some types in Rust have specific limitations on what is considered a valid value, which may not cover the entire range of possible memory values. We call any

> Some types in Rust have specific limitations on what is considered a valid value, which may not cover the entire range of possible memory values. We call any remaining invalid value a niche, and this space may be used for type layout optimizations. For example, in Rust 1.28 we introduced NonZero integer types (like NonZeroU8) where 0 is a niche, and this allowed Option<NonZero> to use 0 to represent None with no extra memory. I didn't know about this, and it's super cool. It's part of a broader pattern where the rigid constraints Rust can impose on code allow both the compiler and the user to do things that would be wildly dangerous in a less-strict language.

TazeTSchnitzel 6y ago
Not only is it more efficient, it aligns with a safety principle I like: “make invalid states unrepresentable”.
steveklabnik 6y ago
For some history here, the most famous example is Option<&T>. References cannot be null, and so the Option can use the null pointer to represent None. At first, this was special cased in the compiler, but then generalized.
- k__ 6y ago
  Do C/C++ use such optimizations or is their type system too brittle?
  - steveklabnik 6y ago
    I am a non-expert in the exact semantics of C and C++ layout, but as far as I can recall off the top of my head, they do not, because the general semantics are "lay out the struct in the order as declared, add padding for alignment reasons, done." Whereas the semantics in Rust are "we can do whatever we want unless you add an explicit #[repr] attribute, in which case you choose the semantics of layout and we don't mess with it." It's not about the strength of the type system, it's about history.
    - k__ 6y ago
      I see, thanks. Pretty cool to see that Rust can do more optimizations than other languages. And it seems to play out well. I fondly remember Java being touted as being superior to C/C++ because it can do runtime optimizations, which will outperform C/C++. Somehow this never happened.
    - MereInterest 6y ago
      Sort of. You're right on what the abstract C++ machine does, but C++ also has the "as if" rule. A compiler can make whatever changes it wants so long as all observable effects are as if it had generated exactly the program as requested. This is the rule that allows for compiler optimizations to be done. Values stored in memory are not considered to be observable effects, so the compiler is allowed to make whatever changes it wants on that end. However, to the best of my understanding, most types are exposed to other compilation units, so it is hard to establish invariants about how they are used. Unless the compiler can verify that nowhere in the program ever takes the address of a boolean variable in a struct, it isn't allowed to rearrange the struct to avoid having that extra boolean. That might be possible at link-time for statically linked programs, but I'm not sure. Also, my knowledge is mostly from programming in C++ and watching CppCon talks, so I may be out of date from the latest optimization techniques.
    - MaulingMonkey 6y ago
      Theoretically you could roll your own such optimizations manually in a C++ codebase by abusing partial specialization. That is, you could write: template < typename T > class optional< std::vector<T> > { // ... }; And write an implementation that (ab)uses knowledge of the exact layout of `std::vector<T>` to avoid an extra bool. This would of course be a breaking change to the ABI of optional<std::vector<T>> if implemented by std::optional, so compiler vendors tend to avoid such things. There is one stdlib example of this, but sadly it's more infamous than inspirational: std::vector<bool>. The standard relaxes several guarantees of std::vector<T> in the case of T == bool, to allow it to bit-pack the booleans instead of using sizeof(bool) - e.g. an entire byte - per element. Some of those relaxed guarantees make std::vector<T> unsuitable for interop with C style APIs taking pointers + lengths if T might be a bool. Worse still, many (most?) implementations don't even implement the space optimization those guarantees were relaxed for - a worst of both worlds situation. If you actually need such space optimizations, you'll reach for an alternative such as boost::dynamic_bitset which provides them consistently.
  - lpapez 6y ago
    When it comes to std::optional, the answer is no. In fact, std::optional<T&> is explicitly forbidden (see here: https://www.fluentcpp.com/2018/10/05/pros-cons-optional-references/ https://www.fluentcpp.com/2018/10/05/pros-cons-optional-refe...) It is used in some other places though. For instance, std::string implementations typically employ small-string optimization (SSO) which means that there might be a limit on string::size() since some of the bits inside that value are used for different purposes (example: https://akrzemi1.wordpress.com/2014/04/14/common-optimizations/ https://akrzemi1.wordpress.com/2014/04/14/common-optimizatio...). The "niche" in this case is the realization that strings are unlikely to be exabytes in size, so there is no reason to always store zeros in high bits of _size.
    - steveklabnik 6y ago
      Fun trivia fact: Rust's stdlib String type cannot, and therefore does not, support SSO.
      - drran 6y ago
        If you need [no_std] version, use SmallString/SmallVec. Otherwise, use SmartString, SmolStr, etc.
      - pdimitar 6y ago
        I recently wondered if a library like `smol_str` will be upstreamed one day. I feel people would rejoice if they can use stack-allocated strings (up to a certain size). Do you think that's possible?
        steveklabnik 6y ago
        Anything is possible, but it's not clear to me what advantage being in the standard library would actually bring. It is a pretty niche use-case (and I work in embedded these days), and it is pretty trivial to use a package. Only the libs team can really say, and I'm not on that team.
        6y ago
  - brundolf 6y ago
    There are some cases, like the Option<&T>::None case, where C/C++ do roughly the same thing just without any type guards. So in this case: pointers in C/C++ can simply be null, which is not expressed at a type level but is lumped in as a special case of the pointer value itself instead of being a separate bit. i.e. the optimization in this case is only necessary for Rust because it normally represents the enum variant as a separate component of the value in addition to its contents. The optimization brings it back in line with C/C++ from a memory usage standpoint. However, because there are no type guards for this stuff in C/C++ you're generally constrained by convention/intuitiveness, when picking these special values, in order to (hopefully) guard against accidental misuse. So in the NonZero case above, you probably wouldn't do that because it's pretty unusual, and you'd therefore use more memory. And then, even when the "special values" are chosen "reasonably", they sometimes get misused anyway and we end up with bugs like last year's trivial sudo exploit: https://bit-sentinel.com/to-sudo-or-not-to-sudo-demystifying-cve-2019-14287/ https://bit-sentinel.com/to-sudo-or-not-to-sudo-demystifying... > Reading the manual for those functions we learn that -1 is a special value > Supplying a value of -1 for either the real or effective user ID forces the system to leave that ID unchanged. > If one of the arguments equals -1, the corresponding value is not changed. > So, what happens when we send -1 as a parameter? Well, somewhere along the underlying code lines is a convention that -1 is represented as 4294967295, thus either values will get the wanted result. Edit: In practice the above may be more common in C than modern C++
- drran 6y ago
  Sadly, it's not generalized enough to represent C-like enums in Rust, which can be declared as (in _theory_): enum Foo { A = 0, B = 1, C = 2, Unknown(i32), } where Unknown field cannot contain values 0, 1, or 2, thus Rust compiler will be able to pack this enum into single i32, like in C.
  - steveklabnik 6y ago
    Yes, if you look at the actual PR for this change, you'll see that doing this is using a rustc-specific interface, for similar reasons.
  - azornathogron 6y ago
    For that use-case can you get away with just setting #[repr(i32)] on the enum and leaving Unknown out of the list? I guess the compiler can't help you keep known and unknown values separate with that structure though, so maybe it's not enough.
    - kzrdude 6y ago
      If you do that, then 3 etc is not a valid value for the enum. Only valid values for that type are the variants.
  - johnsoft 6y ago
    It's not really an enum if you can't enumerate all the values at compile time. Rust enums are not C enums. I'd represent it like this: #[repr(transparent)] struct Foo(i32); impl Foo { const A: Foo = Foo(0); const B: Foo = Foo(1); const C: Foo = Foo(2); }
    - drran 6y ago
      1) Enums in C are implemented that way, so C-like enums in Rust must implement it in the same way to be compatible with C. 2) This is required for forward compatibility. For example protobuf explicitly requires it. 3) Your code is not forward compatible. The proper way is to implement it is as i32 and then unwrap it, or: enum Foo { A = 0, B = 1, C = 2, _UNKNOWN_3 = 3, _UNKNOWN_4 = 4, _UNKNOWN_5 = 5, _UNKNOWN_6 = 6, // ... repeat few dozen times, to be forward compatible } Example: https://github.com/apoelstra/rust-bitcoin/blob/c37ab1f9c2392125a492115c1d2c7a8a77cfff36/src/blockdata/opcodes.rs#L415 https://github.com/apoelstra/rust-bitcoin/blob/c37ab1f9c2392... P.S. IMHO, Rust should allow to define enums as: enum Foo { A = 0, B = 1, C = 2, _ , // Unknown values which must be handled by default case } or enum Foo { A = 0, B = 1, C = 2, _OTHER , // Unknown values which must be handled } because current workaround is usable for i8, maybe even for i16, but not for i32.
- Drup 6y ago
  Hi steve, since you are around: is there a (formal?) description of how this "niche" layout optimization behaves on ADTs in general, or any documented work on the topic?
  - steveklabnik 6y ago
    I think there is, but I cannot find it right now. If you make a post on internals.rust-lang.org, I bet someone can point you to the right place.
volta83 6y ago
I write a lot of code using the #[rustc_layout_scalar_valid_range_start(x)] #[rustc_layout_sclaar_valid_range_end(y)] struct MyInt(i32); to create integers with only valid values in range [x, y) that benefit from the niche optimizations. Like, have literally a project with almost 100k LOC which is all built on top of this.
- brundolf 6y ago
  Wow, I did not know about those! I'm surprised how little a Google search turns up for them; the best I found was a mention (but no description or examples) in docs.rs: https://docs.rs/rustc-ap-syntax_pos/634.0.0/rustc_ap_syntax_pos/symbol/sym/constant.rustc_layout_scalar_valid_range_start.html https://docs.rs/rustc-ap-syntax_pos/634.0.0/rustc_ap_syntax_... Do these enforce against out-of-bounds values by panicking, the way arrays do? Or are they unsafe?
  - jleahy 6y ago
    They're not only unsafe, but as far as I'm aware they're a compiler implementation detail that isn't really supposed to be used in user code (along with rustc_nonnull_optimization_guaranteed). It's actually how NonZero is implemented. See https://github.com/rust-lang/rust/blob/master/library/core/src/num/nonzero.rs https://github.com/rust-lang/rust/blob/master/library/core/s...
    - brundolf 6y ago
      Ah, that explains things
  - tmzt 6y ago
    It would be nice to have a #[range(a..b)] version of this that could be standardized.
  - volta83 6y ago
    > Or are they unsafe? They are unsafe. The safe API of your type must prevent constructing invalid values.
johnisgood 6y ago
You may want to check out Ada, then: https://docs.adacore.com/spark2014-docs/html/ug/en/source/type_contracts.html https://docs.adacore.com/spark2014-docs/html/ug/en/source/ty... You can catch a hell lot of things at compile-time. Correctness is huge in Ada/SPARK. You write safety-critical software in it. I have a comment on Ada/SPARK in great detail, but I do not have the time to find it sadly. :( Consider this: Total : Integer range 0 .. Integer'Last "Any attempt to assign a negative value to variable Total results in raising an exception at run time. During analysis, GNATprove checks that all values assigned to Total are positive or null." Analysis here means static analysis. You can do stuff like this, too, for example: subtype Natural is Integer range 0 .. Integer'Last; subtype Positive is Integer range 1 .. Integer'Last; The above is actually declared in the visible part of package Standard.
- volta83 6y ago
  Does Ada perform layout optimizations on the niches ?
  - johnisgood 6y ago
    I think the terminology is completely different, so I am not quite sure. Perhaps someone who knows Ada/SPARK and its compiler better may be able to answer you.

TazeTSchnitzel 6y ago

Not only is it more efficient, it aligns with a safety principle I like: “make invalid states unrepresentable”.

steveklabnik 6y ago

For some history here, the most famous example is Option<&T>. References cannot be null, and so the Option can use the null pointer to represent None. At first, this was special cased in the compiler, but then generalized.

k__ 6y ago
Do C/C++ use such optimizations or is their type system too brittle?
- steveklabnik 6y ago
  I am a non-expert in the exact semantics of C and C++ layout, but as far as I can recall off the top of my head, they do not, because the general semantics are "lay out the struct in the order as declared, add padding for alignment reasons, done." Whereas the semantics in Rust are "we can do whatever we want unless you add an explicit #[repr] attribute, in which case you choose the semantics of layout and we don't mess with it." It's not about the strength of the type system, it's about history.
  - k__ 6y ago
    I see, thanks. Pretty cool to see that Rust can do more optimizations than other languages. And it seems to play out well. I fondly remember Java being touted as being superior to C/C++ because it can do runtime optimizations, which will outperform C/C++. Somehow this never happened.
  - MereInterest 6y ago
    Sort of. You're right on what the abstract C++ machine does, but C++ also has the "as if" rule. A compiler can make whatever changes it wants so long as all observable effects are as if it had generated exactly the program as requested. This is the rule that allows for compiler optimizations to be done. Values stored in memory are not considered to be observable effects, so the compiler is allowed to make whatever changes it wants on that end. However, to the best of my understanding, most types are exposed to other compilation units, so it is hard to establish invariants about how they are used. Unless the compiler can verify that nowhere in the program ever takes the address of a boolean variable in a struct, it isn't allowed to rearrange the struct to avoid having that extra boolean. That might be possible at link-time for statically linked programs, but I'm not sure. Also, my knowledge is mostly from programming in C++ and watching CppCon talks, so I may be out of date from the latest optimization techniques.
  - MaulingMonkey 6y ago
    Theoretically you could roll your own such optimizations manually in a C++ codebase by abusing partial specialization. That is, you could write: template < typename T > class optional< std::vector<T> > { // ... }; And write an implementation that (ab)uses knowledge of the exact layout of `std::vector<T>` to avoid an extra bool. This would of course be a breaking change to the ABI of optional<std::vector<T>> if implemented by std::optional, so compiler vendors tend to avoid such things. There is one stdlib example of this, but sadly it's more infamous than inspirational: std::vector<bool>. The standard relaxes several guarantees of std::vector<T> in the case of T == bool, to allow it to bit-pack the booleans instead of using sizeof(bool) - e.g. an entire byte - per element. Some of those relaxed guarantees make std::vector<T> unsuitable for interop with C style APIs taking pointers + lengths if T might be a bool. Worse still, many (most?) implementations don't even implement the space optimization those guarantees were relaxed for - a worst of both worlds situation. If you actually need such space optimizations, you'll reach for an alternative such as boost::dynamic_bitset which provides them consistently.
- lpapez 6y ago
  When it comes to std::optional, the answer is no. In fact, std::optional<T&> is explicitly forbidden (see here: https://www.fluentcpp.com/2018/10/05/pros-cons-optional-references/ https://www.fluentcpp.com/2018/10/05/pros-cons-optional-refe...) It is used in some other places though. For instance, std::string implementations typically employ small-string optimization (SSO) which means that there might be a limit on string::size() since some of the bits inside that value are used for different purposes (example: https://akrzemi1.wordpress.com/2014/04/14/common-optimizations/ https://akrzemi1.wordpress.com/2014/04/14/common-optimizatio...). The "niche" in this case is the realization that strings are unlikely to be exabytes in size, so there is no reason to always store zeros in high bits of _size.
  - steveklabnik 6y ago
    Fun trivia fact: Rust's stdlib String type cannot, and therefore does not, support SSO.
    - drran 6y ago
      If you need [no_std] version, use SmallString/SmallVec. Otherwise, use SmartString, SmolStr, etc.
    - pdimitar 6y ago
      I recently wondered if a library like `smol_str` will be upstreamed one day. I feel people would rejoice if they can use stack-allocated strings (up to a certain size). Do you think that's possible?
      - steveklabnik 6y ago
        Anything is possible, but it's not clear to me what advantage being in the standard library would actually bring. It is a pretty niche use-case (and I work in embedded these days), and it is pretty trivial to use a package. Only the libs team can really say, and I'm not on that team.
        6y ago
- brundolf 6y ago
  There are some cases, like the Option<&T>::None case, where C/C++ do roughly the same thing just without any type guards. So in this case: pointers in C/C++ can simply be null, which is not expressed at a type level but is lumped in as a special case of the pointer value itself instead of being a separate bit. i.e. the optimization in this case is only necessary for Rust because it normally represents the enum variant as a separate component of the value in addition to its contents. The optimization brings it back in line with C/C++ from a memory usage standpoint. However, because there are no type guards for this stuff in C/C++ you're generally constrained by convention/intuitiveness, when picking these special values, in order to (hopefully) guard against accidental misuse. So in the NonZero case above, you probably wouldn't do that because it's pretty unusual, and you'd therefore use more memory. And then, even when the "special values" are chosen "reasonably", they sometimes get misused anyway and we end up with bugs like last year's trivial sudo exploit: https://bit-sentinel.com/to-sudo-or-not-to-sudo-demystifying-cve-2019-14287/ https://bit-sentinel.com/to-sudo-or-not-to-sudo-demystifying... > Reading the manual for those functions we learn that -1 is a special value > Supplying a value of -1 for either the real or effective user ID forces the system to leave that ID unchanged. > If one of the arguments equals -1, the corresponding value is not changed. > So, what happens when we send -1 as a parameter? Well, somewhere along the underlying code lines is a convention that -1 is represented as 4294967295, thus either values will get the wanted result. Edit: In practice the above may be more common in C than modern C++
drran 6y ago
Sadly, it's not generalized enough to represent C-like enums in Rust, which can be declared as (in _theory_): enum Foo { A = 0, B = 1, C = 2, Unknown(i32), } where Unknown field cannot contain values 0, 1, or 2, thus Rust compiler will be able to pack this enum into single i32, like in C.
- steveklabnik 6y ago
  Yes, if you look at the actual PR for this change, you'll see that doing this is using a rustc-specific interface, for similar reasons.
- azornathogron 6y ago
  For that use-case can you get away with just setting #[repr(i32)] on the enum and leaving Unknown out of the list? I guess the compiler can't help you keep known and unknown values separate with that structure though, so maybe it's not enough.
  - kzrdude 6y ago
    If you do that, then 3 etc is not a valid value for the enum. Only valid values for that type are the variants.
- johnsoft 6y ago
  It's not really an enum if you can't enumerate all the values at compile time. Rust enums are not C enums. I'd represent it like this: #[repr(transparent)] struct Foo(i32); impl Foo { const A: Foo = Foo(0); const B: Foo = Foo(1); const C: Foo = Foo(2); }
  - drran 6y ago
    1) Enums in C are implemented that way, so C-like enums in Rust must implement it in the same way to be compatible with C. 2) This is required for forward compatibility. For example protobuf explicitly requires it. 3) Your code is not forward compatible. The proper way is to implement it is as i32 and then unwrap it, or: enum Foo { A = 0, B = 1, C = 2, _UNKNOWN_3 = 3, _UNKNOWN_4 = 4, _UNKNOWN_5 = 5, _UNKNOWN_6 = 6, // ... repeat few dozen times, to be forward compatible } Example: https://github.com/apoelstra/rust-bitcoin/blob/c37ab1f9c2392125a492115c1d2c7a8a77cfff36/src/blockdata/opcodes.rs#L415 https://github.com/apoelstra/rust-bitcoin/blob/c37ab1f9c2392... P.S. IMHO, Rust should allow to define enums as: enum Foo { A = 0, B = 1, C = 2, _ , // Unknown values which must be handled by default case } or enum Foo { A = 0, B = 1, C = 2, _OTHER , // Unknown values which must be handled } because current workaround is usable for i8, maybe even for i16, but not for i32.
Drup 6y ago
Hi steve, since you are around: is there a (formal?) description of how this "niche" layout optimization behaves on ADTs in general, or any documented work on the topic?
- steveklabnik 6y ago
  I think there is, but I cannot find it right now. If you make a post on internals.rust-lang.org, I bet someone can point you to the right place.

volta83 6y ago

I write a lot of code using the #[rustc_layout_scalar_valid_range_start(x)] #[rustc_layout_sclaar_valid_range_end(y)] struct MyInt(i32); to create integers with only valid values in range [x, y) that benefit from the niche optimizations. Like, have literally a project with almost 100k LOC which is all built on top of this.

brundolf 6y ago
Wow, I did not know about those! I'm surprised how little a Google search turns up for them; the best I found was a mention (but no description or examples) in docs.rs: https://docs.rs/rustc-ap-syntax_pos/634.0.0/rustc_ap_syntax_pos/symbol/sym/constant.rustc_layout_scalar_valid_range_start.html https://docs.rs/rustc-ap-syntax_pos/634.0.0/rustc_ap_syntax_... Do these enforce against out-of-bounds values by panicking, the way arrays do? Or are they unsafe?
- jleahy 6y ago
  They're not only unsafe, but as far as I'm aware they're a compiler implementation detail that isn't really supposed to be used in user code (along with rustc_nonnull_optimization_guaranteed). It's actually how NonZero is implemented. See https://github.com/rust-lang/rust/blob/master/library/core/src/num/nonzero.rs https://github.com/rust-lang/rust/blob/master/library/core/s...
  - brundolf 6y ago
    Ah, that explains things
- tmzt 6y ago
  It would be nice to have a #[range(a..b)] version of this that could be standardized.
- volta83 6y ago
  > Or are they unsafe? They are unsafe. The safe API of your type must prevent constructing invalid values.

johnisgood 6y ago

You may want to check out Ada, then: https://docs.adacore.com/spark2014-docs/html/ug/en/source/type_contracts.html https://docs.adacore.com/spark2014-docs/html/ug/en/source/ty... You can catch a hell lot of things at compile-time. Correctness is huge in Ada/SPARK. You write safety-critical software in it. I have a comment on Ada/SPARK in great detail, but I do not have the time to find it sadly. :( Consider this: Total : Integer range 0 .. Integer'Last "Any attempt to assign a negative value to variable Total results in raising an exception at run time. During analysis, GNATprove checks that all values assigned to Total are positive or null." Analysis here means static analysis. You can do stuff like this, too, for example: subtype Natural is Integer range 0 .. Integer'Last; subtype Positive is Integer range 1 .. Integer'Last; The above is actually declared in the visible part of package Standard.

volta83 6y ago
Does Ada perform layout optimizations on the niches ?
- johnisgood 6y ago
  I think the terminology is completely different, so I am not quite sure. Perhaps someone who knows Ada/SPARK and its compiler better may be able to answer you.