One of the design goals of Option is to be a library-level replacement for the language-level null value found in languages like C. Furthermore, one of the design goals for Rust itself is to have its abstractions be zero-overhead. With a naive implementation of Option, these goals would be in opposition.
To illustrate why these goals would be in opposition, look at a trivial example of a tagged union (enum) in Rust:
enum Foo {
Bar(i32),
Qux(u32)
}
At runtime, any value of type Foo will either be in the Bar state, or it will be in the Qux state. Both Bar and Qux hold types that are 32 bits in size, and since only one of those states can be active at a time, we know that Foo only needs 32 bits of storage to satisfy both these states. But additionally, it needs extra storage to store the runtime information telling us which state it's currently in. The smallest "extra" amount of storage that can be added to a type is 8 bits, so we would expect every value of type Foo to be 40 bits in size at runtime. In fact it's larger, due to alignment and padding, so Foo will be 64 bits in size at runtime.
Let's bring it back around to Option, which is an enum that looks like this:
enum Option<T> {
Some(T),
None
}
A null pointer in C will be the same size as a non-null pointer in C: 64 bits, assuming a 64-bit platform. A Rust reference would also be 64 bits, and these cannot be null. If we were to try to use Option on a reference to "opt-in" to nullability, what size would that "nullable reference" be assuming a naive implementation of Option? Well, firstly we'd need storage for the value of the reference itself (64 bits), and then, as per above, we'd need our "extra" storage to tell us at runtime whether our Option is a Some or a None. And again, because of alignment and padding, this would theoretically result in a type that is 128 bits in size in total, which is real shame since in theory distinguishing between two states only takes a single bit of storage. Overall this would be a performance regression from C, where nullability does not impose any space overhead.
Fortunately, Rust's implementation is not naive. Remember: Rust references cannot be null. That means that the Rust compiler knows that any type that is a reference will not contain a value that is all zeroes at runtime. Rust leverages this knowledge for optimization: for any Option containing a reference, only a single pointer-sized piece of memory is needed, and the None case will be represented by a value of all zeroes. This means that the Option is now a zero-overhead abstraction for this use case, because Option<&Foo> will be the same size as &Foo.
And this smart logic isn't hardcoded for the Option enum. Any enum, written by anyone, can automatically benefit from the ability to "hide" the enum tag in such "uninhabited" values. The OP's example of NonNull<T> is, like references, an example of of a type that has an uninhabited value that permits this optimization. Others include the NonZeroU8 type and its friends, where Option<NonZeroU8> will be the same size as a standard u8, though which give up the ability to represent zero (in the future this may be extended to allow arbitrary user-defined types which can make whatever values they want act as uninhabited for the purposes of enum size optimization, but it will take some work to get there).
An interesting question! Let's start this nerd-snipe by thinking about easier cases first.
1. Could Option<f64> be optimized to be 64 bits in size? This would imply that the implementation can guarantee that a particular one of the zillions of possible NaN values will never be generated as a result of a legal operation. I want to say that this is probably true in practice, though it will be implementation-dependent; I don't know how LLVM handles this, but I suspect that it only uses one or a handful of the possible NaN values to represent NaN in practice. So while it's probably feasible, it would make part of Rust's ABI dependent on implementation details of the backend (consider: is it likely that every possible backend reserves, and will always reserve, one NaN value that will never be used?).
2. Could the following enum be 64 bits in size?
enum NanBox {
Number(f64),
Pointer(u32)
}
A 64-bit float should have 2^53-1 possible values for NaN, which means that theoretically that should give us plenty of space to hide an entire 32-bit integer in the significand. This still presents the same worries as the prior point, except 4.2 billion times more severe. :) Furthermore, now you might have a new problem: consider that an Option<&Foo> that is Some is already a valid pointer, with no bit twiddling required. Additionally, above in point 1, a theoretical 64-bit Option<f64> is already a valid f64 in the Some case, with no bit-twiddling required. But here in our NanBox case, while Number is always a valid f64, the bit pattern of Pointer is not automatically a valid u32! At best, we'd have to mask out the irrelevant upper 32 bits, but now we're assuming something very specific about what bit patterns LLVM will never use for NaN. And in the worst case, we might have to do a nontrivial amount of extra work at runtime to make the Pointer look like a valid value. It might still work, for all I know, but it's another thing that requires careful thought.
In the end it boils down to what sort of guarantees LLVM wants to provide about its FP code generation (and maybe it's even architecture-dependent?), and whether Rust wants to risk irrevocably making its ABI nonportable. In contrast, there's no risk in assuming that references have an uninhabited value at 0x0, because Rust is in full control of that.
That would require Rust to convert all NaNs to a single "canonical" NaN. I don't think it does that, in fact you don't want Rust to do that, since it would make it impossible to do these NaN-boxing tricks by hand.
On the other hand, a CanonicalNaN<T> could be created in the future to allow these tricks, similar to the NonNull<T>/NonZeroU8/etc mentioned above.
(As an interesting aside, for the RISC-V ISA, all floating-point operations generate a single canonical NaN: "Except when otherwise stated, if the result of a floating-point operation is NaN, it is the canonical NaN. The canonical NaN has a positive sign and all significand bits clear except the MSB, a.k.a. the quiet bit. For single-precision floating-point, this corresponds to the pattern 0x7fc00000." So this scheme would work even better on RISC-V, since after any floating-point operation, it's guaranteed that any NaN is the canonical NaN.)
What I do instead (given the excellent sibling replies about how it's not that simple) is store the value in a `u64` and then provide a method to decode it into a non-layout-optimized enum. Since that enum is not stored anywhere but the stack, it can be optimized out if the decoding is inlined: https://github.com/rpjohnst/dejavu/blob/a768ce515b3a110542aa...
There really should be a ”normal” f32 and f64 type with guarantees for non-NaN, similar to the nonzero integers. More importantly than size, these floats would be totally ordered unlike the partially ordered regular ieee floats.
Edit: turns out these exist in various forms e.g “noisy float”
This sounds interesting, can anyone elaborate on this?