Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Representation of structs #11

Closed
nikomatsakis opened this issue Aug 30, 2018 · 51 comments
Closed

Representation of structs #11

nikomatsakis opened this issue Aug 30, 2018 · 51 comments
Assignees
Labels
A-layout Topic: Related to data structure layout (`#[repr]`) S-writeup-assigned Status: Ready for a writeup and someone is assigned to it

Comments

@nikomatsakis
Copy link
Contributor

nikomatsakis commented Aug 30, 2018

Discussion topic about how structs are represented in Rust. Some things to work out:

  • Do we ever say anything about how a #[repr(rust)] struct is laid out
    (and/or treated by the ABI)?
    - e.g., what about different structs with same definition
    - across executions of the same program?
  • For example, rkruppe writes that we might "want to guarantee (some subset of) newtype unpacking and relegate #[repr(transparent)] to being the way to guarantee to other crates that a type with private fields is and will remain a newtype?"
  • When is interop with #[rust(C)] guaranteed and what can we say there?
@nikomatsakis
Copy link
Contributor Author

I for one would like someone to talk a bit about what #[repr(C)] really means anyway. It seems to play a number of roles for us, at once defining a kind of fixed layout strategy but maybe also having other effects?

Is it worth maybe trying to tease those out into distinct repr flags (any lang changes would require an RFC, of course).

There may also be lesser variants that are useful: for example, I think it would be useful to be able to say that "the first field appears at offset 0" but say nothing about the positions or layouts of other fields within a struct.

It'd be good -- while we're thinking about this stuff -- to think about the kinds of things we might want to say but currently cannot.

@avadacatavra avadacatavra added A-layout Topic: Related to data structure layout (`#[repr]`) active discussion topic and removed A-layout Topic: Related to data structure layout (`#[repr]`) labels Aug 31, 2018
@joshtriplett
Copy link
Member

The C11 spec provides some fairly detailed guidance on structure layout, which we could apply to repr(C) structs.

@gnzlbg
Copy link
Contributor

gnzlbg commented Aug 31, 2018

The C17 standard is here: http://www.open-std.org/jtc1/sc22/wg14/www/abq/c17_updated_proposed_fdis.pdf

The struct layout is specified in 6.7.2.1 Structure and union specifiers (starting at paragraph 3). Ignoring bitfields and other things that do not apply to Rust, things that might be relevant are:

  1. A structure or union shall not contain a member with incomplete or function type (hence, a structure shall not contain an instance of itself, but may contain a pointer to an instance of itself), except that the last member of a structure with more than one named member may have incomplete array type; such a structure (and any union containing, possibly recursively, a member that is such a structure) shall not be a member of a structure or an element of an array.

  2. As discussed in 6.2.5, a structure is a type consisting of a sequence of members, whose storage is allocated in an ordered sequence.

  3. Within a structure object, the non-bit-field members and the units in which bit-fields reside have
    addresses that increase in the order in which they are declared. A pointer to a structure object,
    suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in
    which it resides), and vice versa. There may be unnamed padding within a structure object, but not
    at its beginning.

  4. There may be unnamed padding at the end of a structure or union.

  5. As a special case, the last element of a structure with more than one named member may have an
    incomplete array type; this is called a flexible array member. In most situations, the flexible array
    member is ignored. In particular, the size of the structure is as if the flexible array member were
    omitted except that it may have more trailing padding than the omission would imply. However,
    when a . (or-> ) operator has a left operand that is (a pointer to) a structure with a flexible array
    member and the right operand names that member, it behaves as if that member were replaced with the longest array (with the same element type) that would not make the structure larger than the object being accessed; the offset of the array shall remain that of the flexible array member, even if this would differ from that of the replacement array. If this array would have no elements, it behaves as if it had one element but the behavior is undefined if any attempt is made to access that element or to generate a pointer one past it.


I think that we should just say that #[repr(C)] Rust's structs have the same layout as C structs as specified in some C standard version and call it a day. Newer C standards are (often) backwards compatible with older ones, so as long as the changes are backwards compatible, we could upgrade the spec as new standards are released to point to these without issues.

@the8472
Copy link
Member

the8472 commented Aug 31, 2018

Let's say the compiler keeps the freedom to choose arbitrary layouts at compile time, would punning be valid after checking that the layout just happens to be identical (via some offset_of construct)?

E.g. as an optimization to just cast between repr(C) and repr(rust) where things match and otherwise shoveling data from one type the other field by field?

@joshtriplett
Copy link
Member

joshtriplett commented Aug 31, 2018 via email

@nikomatsakis
Copy link
Contributor Author

nikomatsakis commented Aug 31, 2018

I'm going to stake out a tentative position:

  • I think we may well want the freedom to reorder distinct #[repr(Rust)] structs independently, for example based on PGO information.
    • The only real thing this seems to rule out is people using transmute to gain "unauthorized" access to private fields of data structures, right?
    • That is definitely a real thing, but also a pretty sketchy one.
  • I think that the following repr options might be useful:
    • #[repr(prefix)], which would force the first field to be at offset 0, but not constrain the rest
      • useful for guaranteeing "prefix" properties
    • #[repr(in_order)], whihc would force fields to be laid out in order, but not otherwise require full #[repr(C)] compatibility
      • though maybe not: what else does #[repr(C)] even do?

@hanna-kruppe
Copy link

hanna-kruppe commented Sep 2, 2018

My quick two cents on easy questions before I tackle the big issue of what to do about repr(Rust):

@the8472

Let's say the compiler keeps the freedom to choose arbitrary layouts at compile time, would punning be valid after checking that the layout just happens to be identical (via some offset_of construct)?

Yes, this should definitely be valid if done properly. The checks can get quite involved though, if we truly guarantee nothing about repr(Rust) layout, one would have to check at minimum:

  • alignment of the whole struct (since the compiler would be allowed to raise the alignment requirements of the repr(Rust) struct)
  • offsets of all fields, as you say
  • size of the whole struct (even if the offsets of all fields are identical, tail padding would be a possibility)

@nikomatsakis

  • #[repr(in_order)], whihc would force fields to be laid out in order, but not otherwise require full #[repr(C)] compatibility
    • though maybe not: what else does #[repr(C)] even do?

repr(C) also prescribes the amount and locations of padding, but I don't think this makes repr(in_order) useful: we can't lower the alignment requirements of the fields, and raising it (edit: or alignment of the struct itself) is basically useless. It can theoretically facilitate the use of instructions with higher alignment requirements (e.g., SIMD) or prevent false sharing, but both of those are very tricky and niche even when done by a programmer, and automatically detecting when these opportunities are present and justifying them against the increased padding (and the cache misses, memory bandwidth, peak rss, etc. implied by it) seems infeasible to me.

@joshtriplett
Copy link
Member

I personally feel that we shouldn't add repr(inorder), or any other "some but not all of what repr(Rust) is free to do", until we have a specific, concrete use case for it.

I also hope we don't need repr(prefix) to ensure that initial fields stay in place.

Personally, I would greatly prefer that we handle structure ordering issues by helping developers reorder the actual structure order in the source, rather than deciding to reorder it at compile time. If you write a struct with a u8, u32, and u8, in that order, and it isn't repr(C), why don't we emit a warning rather than just reordering? (If you use repr(C) then you might need that exact layout for compatibility.)

@nikomatsakis
Copy link
Contributor Author

nikomatsakis commented Sep 5, 2018

I also hope we don't need repr(prefix) to ensure that initial fields stay in place.

Just to make sure I understand you: you would prefer that we respect the field ordering that the user gave? Or you hope that users never care about prefix?

Personally, I would greatly prefer that we handle structure ordering issues by helping developers reorder the actual structure order in the source, rather than deciding to reorder it at compile time.

Interesting. I feel the opposite. If the developer wants field order to be preserved, I would rather they say so, as I think it's an exceptional case and I'd like my attention to be drawn to it. Otherwise, I would prefer that I have the freedom to order my fields in a way that maximizes readability of my source, and without regard for "bitpacking" or other things.

@gnzlbg
Copy link
Contributor

gnzlbg commented Sep 5, 2018

I think that the following repr options might be useful:

I think we already talked about this on IRC, but for the record, I do find these ideas for new reprs interesting, but think we should try to avoid introducing new reprs and features in the unsafe code guidelines if possible. There is so much to do already, that if we try to also specify features that Rust does not have yet, we might end up achieving nothing.

Once we have the guidelines closer to a finished state, if someone wants to fill an issue in the rfc repo to discuss these, or fill in a rfc, then we can discuss these and how to incorporate them into the guidelines there. Maybe the issues could be filled there already so that we don't forget?

@the8472
Copy link
Member

the8472 commented Sep 5, 2018

Otherwise, I would prefer that I have the freedom to order my fields in a way that maximizes readability of my source, and without regard for "bitpacking" or other things.

Preserving order by default does make even less sense when generic fields are present.

@joshtriplett
Copy link
Member

I do agree that we shouldn't invent new features as part of the unsafe code guidelines, though we certainly might use the process to inform the design of new language features.

@nikomatsakis I would hope that users could have multiple structs with a common prefix and read that common prefix without needing a special directive to do so.

Regarding the second point: structure order can matter sometimes, and I'd prefer that code be self-documenting about that. It's one thing if you don't already lay out your structure for optimal packing. But if you do, it'd be surprising to have the compiler reorder for other reasons, such as expected locality optimizations or profiling. I'd much rather have that information used to guide the developer into making such changes.

@alercah
Copy link

alercah commented Sep 8, 2018

I absolutely agree that repr(Rust) should not make guarantees about ordering, because doing that is saying "here's some thing that the compiler has a lot of ability to do really well, and we're going to go force the programmer to do it." @the8472's example of generics are particularly important: there's no way for the author of a generic struct to always pick the best layout.

But if you do, it'd be surprising to have the compiler reorder for other reasons, such as expected locality optimizations or profiling. I'd much rather have that information used to guide the developer into making such changes.

It's not surprising to me, as a developer who rarely in practice has to concern myself with low-level bit manipulation, that no guarantees are made other than those explicitly promised. If I am writing code that cares about common prefixes or field order, I'm already off the beaten path. And I'm in unsafe code, which means that I have to be watching myself carefully. I know that there are many pitfalls and caveats, and that I can't just make assumptions.

If you write a struct with a u8, u32, and u8, in that order, and it isn't repr(C), why don't we emit a warning rather than just reordering?

Because the vast majority of users do not want to ever have to think about this stuff. They want the compiler to just do the optimization. There will be questions in #rust-beginners to the effect of "why doesn't the compiler just do it itself?" and "because some unsafe code people prefer it this way" is very far from a satisfactory answer. It will become a serious turn-off for new users, particularly when they add a new field to an existing struct and get ceremoniously informed that they have done so in the wrong place. It will hold up code reviews as people have to go "Sorry, the build failed because we have deny(warnings) and you put your fields in the wrong order."

If users care about field order in source code, they want it to be in some logical order. Maybe it's alphabetical, maybe it's grouped by purpose. Whatever it is, it definitely not "the order that leads to the least packing".

@hanna-kruppe
Copy link

@nikomatsakis wrote:

I think we may well want the freedom to reorder distinct #[repr(Rust)] structs independently, for example based on PGO information.

  • The only real thing this seems to rule out is people using transmute to gain "unauthorized" access to private fields of data structures, right?
  • That is definitely a real thing, but also a pretty sketchy one.

There are some cases where one can legitimately know and exploit that two distinct repr(Rust) structs have identical contents, without breaking privacy/abstraction barriers and without being otherwise "sketchy". Most commonly, there are "plain old data" types with all fields public and a Copy impl (for example, Vec3 style types in computer graphics libraries, of which there's a ton of different but structually identical ones, and not all of them are repr(C)).

Another example might be writing a compatibility shim between two different crates (or major versions of the same crate) solving a common problem with different APIs. If the author of this shim is also the author of the other crates involved, they can know that some relevant data structure is defined the same in both crates and will remain so in future releases, even if it's not public.

Given the knowledge that two types are layout compatible, what can we use it for? For one, we can receive a large collection containing items of one type, and pass it to other code expecting a collection of the other type without copying. We can also implement AsRef and AsMut traits to faciliate interoperability. And of course, if we know the exact layout and not just that two types have the same unknown layout, we can apply all the usual unsafe tricks that rely on knowing the layout, without having to add repr(C) to a type that one does not fully control.

I'm sure there's more examples, but I hope this establishes type punning of other crates' types is not limited to sketchy rule-breaking.

To top it off, here's a concrete example of something I might want to do: Suppose I load a 3D model from disk using the obj-rs crate. For the geometry, this gives me a vector of Vertex -- a repr(Rust) struct containing the per-vertex position and normal. Both fields are public and themselves have defined layout, so if only I could be sure that the position and normal are not swapped, I would know the memory layout of the entire geometry data. I could then pass this data to a renderer that knows nothing about obj-rs (assuming the format the renderer does expect happens to be identical to what obj-rs gives me), without having to allocate a new Vec and copy the data (or write very subtle unsafe code to opportunistically detect that the layout is as I would expect, as discussed earlier in this thread).

@nikomatsakis
Copy link
Contributor Author

@rkruppe

I'm sure there's more examples, but I hope this establishes type punning of other crates' types is not limited to sketchy rule-breaking.

Fair enough!

I think an example of where PGO might be useful that would break some of these invariants is adding padding to reduce false sharing for things that cross threads.

But perhaps this ought to be handled by informing the user where to add annotations, instead, as @joshtriplett suggested. I find that appealing, particularly since it means that one could compile again (without profile data) and still see the same optimizations.

So this is a concrete thing we could decide here:

  • Can we enumerate what inputs the compiler might use to decide on the layout of a struct (even if we don't want to define the function)?

In particular, are we willing to say that the layout of a struct is a function of the types of its fields?

Or do we want the freedom to examine how the struct is used?

Does anybody even do PGO of the kind I am talking about? (I have no real idea)

@nikomatsakis
Copy link
Contributor Author

@gnzlbg

There is so much to do already, that if we try to also specify features that Rust does not have yet, we might end up achieving nothing.

I don't thikn we can "specify features that Rust doesn't have yet", but I definitely think we should take note of gaps that exist and file them for future follow-up.

@nikomatsakis
Copy link
Contributor Author

@joshtriplett

I would hope that users could have multiple structs with a common prefix and read that common prefix without needing a special directive to do so.

I think I feel quite differently here. Even when I was a "young C hacker", I always found myself writing comments when I was writing a struct where field ordering was important -- it seems like a subtle thing that is worth documenting! (And I second @alercah's arguments as well.)

I think this is the position I currently favor:

  • We should not guarantee #[repr(Rust)] layout
  • But I would be amendable to guaranteeing that it is a deterministic function of the types of the fields
  • And it seems like any sort of PGO or other optimization tool would be better off suggesting annotations that users can use
    • This makes the optimization repeatable but also serves as a kind of documentation for the future

But I'm curious to hear from people who have experience using PGO-like optimizations in the wild. I'd also be curious to hear what @eddyb thinks on the particular point of whether layout should be deterministic.

@the8472
Copy link
Member

the8472 commented Sep 10, 2018

@rkruppe

But if you wanted to rely on such things then the order of fields would suddenly become part of the API contract of crates, i.e. someone just reordering their fields for code formatting reasons would suddenly become an API break if punnability were guaranteed for repr(Rust) types.

At a minimum you'd still need some compile-time verification that they are layout-compatible.

@joshtriplett
Copy link
Member

But I would be amendable to guaranteeing that it is a deterministic function of the types of the fields

This seems like a bare minimum, yes.

I'd also love to provide enough information that people can know when their structs get reordered, and at the very least some way to explicitly enable a lint to get the compiler to say when it reorders so that the developer can incorporate that.

And it seems like any sort of PGO or other optimization tool would be better off suggesting annotations that users can use

This makes the optimization repeatable but also serves as a kind of documentation for the future

This is precisely what I meant when I said that the compiler should tell you rather than just doing it.

@alercah
Copy link

alercah commented Sep 11, 2018

PGO:

Related to false sharing, there are other classes of optimizations that the compiler could make by rearranging fields. For instance, suppose we have a struct containing 3 halfwords, one which is written to much more frequently then the others (note that Vec is an example in terms of the profile, though it's the wrong size). In such a case, if the architecture punishes undersized memory access, the compiler may well decide that it is best to put the data field in the same word as the halfword of padding, allowing it to do full-word write at all times, happily clobbering the padding.

Even without resorting to strange architectural properties, it is probably faster to load two subword variables in a single load and then mask them out. So the compiler may want to move fields frequently accessed together into offsets where it can minimize the total number of loads and stores.

The possibility that this is architecture-dependent makes me think that any manual input to this process may be better off in the form of annotations on fields, rather than asking for specific layouts, as the optimal layout may be architecture-dependent.

It's possible that our technology today is not really at the point where we can take advantage of this. But we're also in a world where machine-learning-optimized compiles may be a thing in the near future, so I'm inclined to say that we should not close the door to these sorts of improvements.

Punning:

It seems to me that we can separate punning into three cases: a) where the user owns both types b) where the user owns only one type and c) where the user owns neither type.

Case a) doesn't worry me too much. Especially if, as I suggested in the tuples thread, we allow the user to explicitly specify that the layout of a struct matches the tuple with the same fields, then it's easy enough for the user to so annotate both of the types involved (and there may be benefit to letting them do so in a way other than repr(C), since repr(C) may add padding that repr(Rust) does not).

As for b) and c), I realized something just today: if we say that layout is deterministic, then field order becomes part of a type's API. If we provide a guarantee that you can take some repr(Rust) type that someone else wrote, write your own type with the same fields in the same order, and pun between them, then this requires them to never decide that they like the fields better in another order. RFC 1105 is silent as to this, but it seems to me that almost every Rust user would be surprised that reordering fields of a non-tuple-like struct would constitute a breaking change and, scarily, a potentially memory-safety-violating one. I think that this is a guarantee that crate authors should have to opt into giving by specifying a repr attribute.

This implies to me that scenario c) is something we can never guarantee in general, unless we add some additional information than field type to the process (e.g. lay out all fields of the same size in lexicographic order by name). Although we could in theory do so for tuple-like structs, I think that most of the things people are interested in punning have nominal fields anyway.

This made me wonder: why are we asking users to do type punning themselves, anyway? There's two reasons: either they really care about performance, or they just don't want to write out the fields. We can solve the latter through better language features (or even just better optimizations: if the compiler was capable of recognizing when a move/copy was being done fieldwise between two identically-laid out types, it could just optimize to a single wide move/copy and this would work for data that was owned, although not for punning a reference or pointer to unowned data), and those features would benefit all conversions between similar types. For the former, we could either flat-out say that we do not support this, or we could offer safe APIs that allow for punning. For instance, we could have one

For b), we're in a boat where we can't safely make any such guarantee today, but we could in theory add a way to say "my type is laid out the same as this other one", which would be robust against changes to the remote type's layout. Furthermore, any language features or optimizations like the above would apply here.

@alercah
Copy link

alercah commented Sep 11, 2018

Apropos of none of the above things: I think we can probably safely guarantee that a DST appears last in memory.

@the8472
Copy link
Member

the8472 commented Sep 11, 2018

But I would be amendable to guaranteeing that it is a deterministic function of the types of the fields

This seems like a bare minimum, yes.

Considering that PGO is frequently mentioned and struct-layout-randomization could conceivably also be used as some form of testing that does not seem all that self-evident.

@hanna-kruppe
Copy link

@nikomatsakis

Does anybody even do PGO of the kind I am talking about? (I have no real idea)

In #12 (comment) @ChrisJefferson linked these two papers:

Neither is directly applicable, though. The first is about Java where allocations tend to have different shapes than in Rust (and reports mixed results, indicating to me that this should be opt-in), the latter does much more aggressive transformations that we can't allow in Rust except under the as-if rule.

@hanna-kruppe
Copy link

@the8472

But if you wanted to rely on such things then the order of fields would suddenly become part of the API contract of crates, i.e. someone just reordering their fields for code formatting reasons would suddenly become an API break if punnability were guaranteed for repr(Rust) types.

Good point, though this still leaves tuple structs where order is already significant.

At a minimum you'd still need some compile-time verification that they are layout-compatible.

One should have that in any case so that a semver break (uncool but happens) does not turn into a memory safety issue (very bad).

@hanna-kruppe
Copy link

hanna-kruppe commented Sep 12, 2018

@joshtriplett

I'd also love to provide enough information that people can know when their structs get reordered, and at the very least some way to explicitly enable a lint to get the compiler to say when it reorders so that the developer can incorporate that.

As has been pointed out before, for generic types the optimal order may be different depending on type parameters, making it impossible to even write down the optimal order in the source code. I'll add that the optimal order can also vary by target platform, e.g. due to:

  • differences in the size/alignment of pointers and usize
  • differences in the alignment requirements of large primitives like u64 and u128

Additionally, for the metric "minimize overall structure size" or "minimize padding while aligning this field to K", it is quite feasible to find optimal solutions quickly, reliably and automatically. It's silly to force programmers to think about and put into their source code an optimization that the compiler can handle 100%

In contrast, for metrics such as "reduce false sharing", "reduce cache misses", etc. an "optimal" solution is very hard to find for many reasons (e.g. it depends on runtime memory layout and uarch details, and even ignoring those the idealized mathematical optimization problem is computationally hard). Add in that a PGO build is more expensive than a normal optimized build and it's quite obvious to me why a programmer might want to invest time once to learn about layout changes that seem profitable, investigate them, and then put them in writing if they seem good.

@ChrisJefferson
Copy link

Just wanted to say, with regards the papers I mentioned in earlier, I agree these papers don't directly apply to Rust, but they show that people do do research into layout in various ways -- it's not surprising there isn't (yet) research into layout in Rust, the language isn't old enough yet! Anything we fix today will be, in practice, fixed forever (at least experience with past languages suggest this will be the case), so I'd very much prefer we not fix anything, just because people think varying it won't be useful for optimisation. At the moment we have #[repr(C)] for people who want a well-defined ABI (although different for each OS of course, and maybe not the ABI they want).

On the other hand, I know academics who haven't bothered doing research into layout of C and C++, because as the languages define the layout, any system which automatically changed layouts for all structs in a program would have a good chance of breaking things, and trying to detect which structs/classes can have their layout changed is a non-trivial activity.

I personally don't want to investigate which layout changes might be profitable, in the same way i'm not interested in which functions are worth inling. I'd prefer a PGO to just "go forth" and do it's best attempt at speeding up my program.

@alercah
Copy link

alercah commented Sep 12, 2018

Sure, but that doesn't matter across crate versions.

@avadacatavra avadacatavra added the S-writeup-assigned Status: Ready for a writeup and someone is assigned to it label Sep 13, 2018
@nikomatsakis
Copy link
Contributor Author

nikomatsakis commented Sep 25, 2018

@rkruppe

Good point, though this still leaves tuple structs where order is already significant.

It seems to me that changing the order of (public) fields in a tuple struct is already a breaking change (particularly if those fields have the same type, which I believe is the only case where we said that we might want field order to matter).

In particular, if the fields are public, your clients can write:

let Foo(name, age) = bar();

and now they have extracted out a name and an age. If you arbitrarily reordered those, this code would be semantically invalid.

The only way that it wouldn't be a breaking change would be if the order doesn't matter, in which case.. it doesn't matter.

Right?

(I think this is maybe what @alercah was getting at? Not sure.)

EDIT: Re-reading, I think this was exactly @rkruppe's point and I was just confusing myself...

@hanna-kruppe
Copy link

EDIT: Re-reading, I think this was exactly @rkruppe's point and I was just confusing myself...

Yes, that was exactly my point, but since two people have replied restating this at me, I clearly must have worded it very badly 🤔

@ChrisJefferson
Copy link

I'm not clear why changing the order in memory of these things would effect the behaviour of tupper structs. As long as rust maps the first element of the struct to (in this case) name, it doesn't matter how the valuee are padded, or their order?

@nikomatsakis
Copy link
Contributor Author

I opened #31 which contains my attempt to summarize our tentative consensus here. Please give feedback! (In particular, let me know if there is anything you think is incorrect.)

@rodrimati1992
Copy link

Are there any guarantees about how changing a type parameter affect the memory layout of a struct when it is only ever used in a PhantomData<fn()->TypeParam> field ?

Example:

use std::marker::PhantomData;

struct Value<T,C>{
    value_0:T,
    value_1:usize,
    value_2:T,
    _marker:PhantomData<fn()->C>,
}

I am currently relying on the layout of Value not changing when its C type parameter does.

@asajeffrey
Copy link

@rodrimati1992 Good point, can we mandate that the layout of PhantomData<T> is the same as () in all type contexts?

@the8472
Copy link
Member

the8472 commented Oct 3, 2018

Wouldn't those types be compiled separately due to monomorphization and thus be subject to independent optimization choices by the compiler.

@asajeffrey
Copy link

@the8472 that's the question, should different zero-size types affect representation? Josephine is unsafe if different PhantomData have different memory layouts.

@hanna-kruppe
Copy link

The reasons for wanting to reserve the right to lay out structurally-identical but nominally-different types differently (different types may be used differently incentivizing different layouts, "if you need layout compatibility you can add an attribute") apply here unaltered.

I for one do think we should guarantee PhantomData to be irrelevant to layout, but I am also in favor of guaranteeing a lot more than there was consensus for in this thread.

@the8472
Copy link
Member

the8472 commented Oct 3, 2018

I think if a special-case were provided for zero-sized types in generics this would result in spooky action at a distance where sometimes you would be guaranteed that a generic type with different parameters are layout-identical until someone changes one of the types to be non-zero-sized and suddenly your layouts are not compatible anymore.

Instead you could say something like

#[repr(as(Value<T, ()>))]
struct Value<T,C>{
    value_0:T,
    value_1:usize,
    value_2:T,
    _marker:PhantomData<fn()->C>,
}

Which puts the guarantees or compile time checks at the level where you need them.

@rodrimati1992
Copy link

rodrimati1992 commented Oct 3, 2018

I think if a special-case were provided for zero-sized types in generics this would result in spooky action at a distance where sometimes you would be guaranteed that a generic type with different parameters are layout-identical until someone changes one of the types to be non-zero-sized and suddenly your layouts are not compatible anymore.

Instead you could say something like

#[repr(as(Value<T, ()>))]
struct Value<T,C>{
    value_0:T,
    value_1:usize,
    value_2:T,
    _marker:PhantomData<fn()->C>,
}

Which puts the guarantees or compile time checks at the level where you need them.

This type parameter passes through multiple layers,and requiring every user of type_level_values to annotate their own types with #[repr(as(TypeName<T, ()>))] is a lot to ask.

I would prefer a trait-based solution,in which I can require that two types have compatible memory layout,
rulling out cases where such thing could accidentally happen.This would require no annotations by the user in the common case

I forgot to mention that I generate a type alias to pass a PhantomData-like type as the C type parameter,
guaranteeing that C cannot be anything but zero-sized.
I also have a trait that guarantees that different versions of the same type have same memory layout so long as the fields that mention C are themselves zero-sized or implement that trait.

@asajeffrey
Copy link

Can we say something like we guarantee that the layout for a struct is only dependent on certain properties of its fields? Off the top of my head those are size, alignment and non-zero-ness, but there may be others. This would avoid having to propose an RFC with a language extension.

@the8472
Copy link
Member

the8472 commented Oct 3, 2018

That is an option in principle but the current position is that different types with the same properties should allow maximal layout freedom for various kinds of optimization, randomization and similar compiletime decisions. So pretty much any guarantee at all for repr(Rust) types would have to be opt-in. It also avoids layout unintentionally becoming part of the contract of crates.

See the summary in #31

@rodrimati1992
Copy link

rodrimati1992 commented Oct 3, 2018

Ok,if we go with the annotation based approach,how about something like this:

#[no_effect_on_layout(C)]
struct Value<T,C>{
    value_0:T,
    value_1:usize,
    value_2:T,
    _marker:PhantomData<fn()->C>,
}

This attribute would guarantee that the type parameter C would not change the layout of the type regardless of what it is,requiring it to be stored in a zero-sized-type or a type with the same attribute.

This attribute could also be detected by derive macros that depend on the type parameter,not changing the layout of the type,and would be usable with any #[repr(..)].

@the8472
Copy link
Member

the8472 commented Oct 3, 2018

The intended effect would be the same. You would just be telling the compiler that layout should behave as if C were set to a fixed value and thus all instances of Value<T, C> collapse to Value<T>, but again, only for layout purposes.

This would basically be a special case of the as() constraint where as points to an anonymous generic type with one less generic parameter that contains all the same fields except _marker: ().

@rodrimati1992
Copy link

rodrimati1992 commented Oct 3, 2018

The effect would be that the attribute would be easier to parse by macros.

An alternative if one uses the repr(..) syntax is to extend syn to parse #[repr(as(Value<T, ()>))] so that macro authors don't have to.

@the8472
Copy link
Member

the8472 commented Oct 3, 2018

Ah, I have not put much thought into that specific syntax. It could also be expressed in different ways, e.g. T = () to say that a single generic argument behaves as if it were fixed instead of specifying the layout of the whole struct. The details have to be worked out once additional repr annotations are introduced.

@RalfJung
Copy link
Member

So, after all this talk about layout guarantees for structs... could we do a little practical exercise and see if rust-lang/rust#54922 if within bounds of the guarantees, or exceeding them? This does some manual layout computation that is supposed to recompute the layout of a repr(Rust) struct with an unsized tail.

@Gankra
Copy link

Gankra commented Oct 11, 2018

Quickly chiming in with a +1 for restricting repr(rust) to only reordering and still mandating natural/greedy c-style padding. This would make (align=1,size=0) types not affect layout, newtypes not affect layout, alignment predictable, and the size of heterohomogeneous types predictable. At the same time it would still allow us to do the only really relevant optimization of ordering the fields optimally. The fact that a theoretical field fuzzer wouldn't be allowed to be as powerful as it could be is not especially concerning to me.

(also cc me)

@gnzlbg
Copy link
Contributor

gnzlbg commented Oct 11, 2018

@asajeffrey

Can we say something like we guarantee that the layout for a struct is only dependent on certain properties of its fields? Off the top of my head those are size, alignment and non-zero-ness,

I don't know. For example, consider the repr(Rust) struct F { x: f32, y: f32, z: f32, w: f32 }, under the assumption that f32 has an alignment of 4 in the platform being targeted - the maximum alignment of a field of F is then 4. Would it be ok for the compiler to increase the alignment of F to say, 16, to facilitate SIMD operations?

We have been talking about guaranteeing the layout of homogenous tuples / structs, but I also imagine that this could happen somewhere else, e.g., struct G { a: u64, x: f32, y: f32, z: f32, w: f32, b: u64 } where {xyzw} get re-ordered at the front and the alignment increased to 16 to facilitate SIMD operations.

@nikomatsakis
Copy link
Contributor Author

We've called final-comment-period on #31.

@nikomatsakis
Copy link
Contributor Author

Actually, I see some of the latest comments here -- these are great. Perhaps we can redirect them to #35, which is a subissue on this topic? I'll copy over some of those now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-layout Topic: Related to data structure layout (`#[repr]`) S-writeup-assigned Status: Ready for a writeup and someone is assigned to it
Projects
None yet
Development

No branches or pull requests