Add a note about uninhabited-struct layout optimization#346
Add a note about uninhabited-struct layout optimization#346scottmcm wants to merge 3 commits intorust-lang:masterfrom
Conversation
| that never reaching the `assume_init` part, it's still unlikely that this occurs frequently. | ||
|
|
||
| There *is* still interest in doing optimizations like this on *sum* types, however. There's more | ||
| to potentially be gained there since one variant of a `union` or `enum` being uninhabited doesn't |
There was a problem hiding this comment.
I am very surprised to see union mentioned here. As far as I am concerned those are syntactic sugar for transmutes, and I would be very surprised if we could now start doing such optimizations without breaking tons of code. (I think even the train for "fields not at offset 0" may have sailed, many people forget to set repr(C).)
There was a problem hiding this comment.
Yeah, I wrote that without thinking about it that hard, and looking again you're right, I don't see this happening on unions.
Co-authored-by: Jacob Lifshay <programmerjake@gmail.com>
|
|
||
| There *is* still interest in maybe doing optimizations like this on *sum* types, however. There's more | ||
| to potentially be gained there since one variant of an `enum` being uninhabited doesn't | ||
| keep the whole *value* from being uninhabited the way an uninhabited field does in a `struct`. |
There was a problem hiding this comment.
I think this might be a typo?
| keep the whole *value* from being uninhabited the way an uninhabited field does in a `struct`. | |
| keep the whole *value* from being inhabited, the way an uninhabited field does in a `struct`. |
| * https://github.com/rust-lang/rust/issues/17027 | ||
| * https://github.com/rust-lang/unsafe-code-guidelines/issues/176 | ||
|
|
||
| ## Uninhabited `struct`s should all be ZSTs |
There was a problem hiding this comment.
I think the name “ZST” does not capture the underlying idea very well. The real thing we want is a -∞ sized type, ZST is just one specific way of implementing it. Although I don’t have a better title yet.
Also, do you think it’s a good idea to also add the discussion of Inhabitted trait here? In case someone reading this come up with that idea again.
There was a problem hiding this comment.
The real thing we want is a -∞ sized type
That's not as clear as you'd think. Rust has unsafe, and types need a layout, so "a ZST with always-false validity invariant" actually has some important benefits. With a -∞ sized/aligned type you can't even start executing a function that has a ! variable in it because its whole stack frame would be uninhabited; yet it's easy to write such a function: just panic!().
There was a problem hiding this comment.
Size is a natural number, so a size of -∞ doesn't even make sense. (One could define notions of size where that does make sense, but that's not the discussion we are having here. The notion of size here is the notion currently used in Rust. Given the proposed resolution for this question, it's also not useful to consider these other notions of size.)
Therefore, ZST is exactly the right term here. There's no way a type can be smaller than that.
There was a problem hiding this comment.
Currently size is (at the very least) the amount of bytes required to uniquely represent an arbitrary member of the set of a type, in the Information Theory sense.
The minimum value possible there is zero: if person A needs to describe an element x of type T to person B, and in order to do so, no bytes need to be sent to B, that's because B already knows all it needs to know about x.
And that can only happen when T is either a singleton set or the empty set.
I'm guessing that the -oo notion comes from the logarithm in the Information Theory definition. If we take the logarithm of the size of the set described by the type T, we get:
- 0 if
|T| = 1 - -oo if
|T| = 0
But another restriction we impose over sizes is that they be positive. This (I believe) is because we need sizes to describe a layout budget.
Thus, on one hand the logarithm tells us the number of bits is at least -oo, but on the other hand we know it to also be at least 0. So it ends up being 0.
A ZST :)
There was a problem hiding this comment.
Those two concerns get put together by the use of the ceiling operator; the logarithm of an integer is not necessarily an integer, even when it's not -∞, so we actually do ⌈log₂|T|⌉ where we choose to define ⌈-∞⌉=0.
|
Hey @scottmcm 🙂 I have a question: does the "field projection during initialization" example have an analog for structs? I'm wondering if this problem only appears when trying to initialize tuples, or if it's actually a general issue of the initialization of product types. |
|
Yeah the example works the same with a 2-field struct. That seems obvious so I wonder if I am missing something in what you are asking about. |
Nope, I just don't know the nitty gritty details of unsafe and of memory initialization. And not knowing the exact full picture has managed to make wild differences in past questions I've had. So sometimes I ask the seemingly-obvious things, just in case they are not. (Also tuples are slightly weird to think about sometimes. Since the example has two generic parameters, one for each part of the tuple, it can attempt to create uninhabitable tuples by selecting one such type. But to do the same with a struct, the struct itself would have to be uninhabitable... and I'm not sure I could convince the compiler that this struct that I'm partially initializing is perfectly fine to write to even though all possible generic instantiations of my code can only be creating invalid objects. I dunno.) |
| * https://github.com/rust-lang/rust/issues/17027 | ||
| * https://github.com/rust-lang/unsafe-code-guidelines/issues/176 | ||
|
|
||
| ## Uninhabited `struct`s should all be ZSTs |
There was a problem hiding this comment.
Just from reading this initially it's not immediately clear what ZSTs are. Maybe make this from
Uninhabited
structs should all be ZSTs
to
Uninhabited
structs should all be zero-sized types (ZSTs)
I think this is pretty settled but don't know that we had a good link about it, so figured I'd write this up.