3 ms·
It may be worth pointing out that the `Option<T>` type in Rust doesn't inherently involve any pointers at all, assuming `T` is not a pointer type itself. For e
by jblandy 11y ago
It may be worth pointing out that the `Option<T>` type in Rust doesn't inherently involve any pointers at all, assuming `T` is not a pointer type itself.
For example, `Option<i32>` is probably (the compiler gets to choose) going to be represented as two four-byte values: the discriminant, which distinguishes the `Some` and `None` cases, and then a space for the value `v`, for when the discriminant says we have `Some(v)`. Since zero is a perfectly fine value for an `i32`, we have to store the discriminant separately.
But note that this is just a flat eight-byte value. There's no heap allocation involved. It's just as if you'd written in C:
struct O { enum { Some, None } discriminant; int32_t value };
I compiled a program that uses `Option<Option<i32>>`, and looked at the DWARF debugging info to see what the compiler did with it. It seems to represent this as a twelve-byte value: four bytes for the discriminant for the outer `Option`, followed an eight-byte `Option<i32>` value laid out as before. Since you can get the address of a value held by an enum, I guess this makes sense; the compiler can't combine the discriminants or do anything clever like that.
- SamReidHughes 11y agoIt could combine the discriminants, I think: Option<i32> could have discriminant values 0 or 1, and Option<Option<i32>> could use discriminant value 2 for None, and 0 or 1 mean the object's an Option<i32>.
- dllthomas 11y agoYeah, while the ability to provide a pointer seems meaningful, it might be illusory. If our value is None, then a pointer to the inside Option<i32> is... what? Edited to add: With your proposed encoding, the memory contents of an Option<Option<i32>> is identical to an Option<i32> precisely when there is an Option<i32> to speak about. And when there is no Option<i32>, you can tell that with one comparison, rather than by backing out an unknown number of levels. I like it.
- deleted 11y ago[deleted]
- jblandy 11y agoYeah, that's a nice trick. I wonder how general it is, though.
- SamReidHughes 11y agoIf one alternative is larger than the others and it has an enum tag or pointer inside of it, such that you can squeeze the other alternatives before/after that tag word, you're good to go. If you had multiple alternatives of maximum size, they'd need some word in them, at the same offset/size, such that they don't have conflicting representations. An enum tag could overlap with a non-null pointer, and two enum tags with user-declared tag values (such that they do not overlap) could work too. Or if you're crazy you could discard having each type's representation be computed solely as a function of what the type is made of, choosing their representations based on how well they pack into other types. (Or worse yet, if you've got a borrow checker and your types are memcpyable, you could pack things and rejigger bytes however you wanted and then unfurl them into a temporary whenever something uses the interior value, unless I'm overlooking something. So if you had Either<Either<u32, u32>, Either<u32, u32>>, you could represent that with a single tag whose value is 0, 1, 2, or 3, and when if the tag's 2 or 3 and you make a reference to the interior value, either fix the tag in-place and fix it back when you're done (if you're the sole owner of the Either<Either...>), or copy the value out and let the borrower borrow that (and copy it back in when it's done, if it was a mutable borrow).)