Niche placement heuristic: place at beginning or end of type

[dtolnay]

I noticed that #102750 regressed the size of some types in the syn crate. I minimized the difference to the following:

pub enum Enum {
    A(A),
    B(B),
}

pub struct A {
    pub x: Thing,
    pub y: u16,
    pub z: u16,
}

pub struct B {
    pub x: Thing,
    pub y: u16,
}

pub enum Thing {
    C(u16, u16),
    D(u16, u16),
}

fn main() {
    println!("{}", std::mem::size_of::<Enum>());
}

$ cargo +nightly-2022-11-23 run --quiet && cargo +nightly-2022-11-24 run --quiet
10
12

The type layout in nightly-2022-11-23 is:

print-type-size type: `Enum`: 10 bytes, alignment: 2 bytes
print-type-size     variant `A`: 10 bytes
print-type-size         field `.0`: 10 bytes
print-type-size     variant `B`: 10 bytes
print-type-size         padding: 2 bytes
print-type-size         field `.0`: 8 bytes, alignment: 2 bytes
print-type-size type: `A`: 10 bytes, alignment: 2 bytes
print-type-size     field `.x`: 6 bytes
print-type-size     field `.y`: 2 bytes
print-type-size     field `.z`: 2 bytes
print-type-size type: `B`: 8 bytes, alignment: 2 bytes
print-type-size     field `.x`: 6 bytes
print-type-size     field `.y`: 2 bytes
print-type-size type: `Thing`: 6 bytes, alignment: 2 bytes
print-type-size     discriminant: 2 bytes
print-type-size     variant `C`: 4 bytes
print-type-size         field `.0`: 2 bytes
print-type-size         field `.1`: 2 bytes
print-type-size     variant `D`: 4 bytes
print-type-size         field `.0`: 2 bytes
print-type-size         field `.1`: 2 bytes

and in nightly-2022-11-24:

print-type-size type: `Enum`: 12 bytes, alignment: 2 bytes
print-type-size     discriminant: 2 bytes
print-type-size     variant `A`: 10 bytes
print-type-size         field `.0`: 10 bytes
print-type-size     variant `B`: 8 bytes
print-type-size         field `.0`: 8 bytes
print-type-size type: `A`: 10 bytes, alignment: 2 bytes
print-type-size     field `.y`: 2 bytes
print-type-size     field `.z`: 2 bytes
print-type-size     field `.x`: 6 bytes
print-type-size type: `B`: 8 bytes, alignment: 2 bytes
print-type-size     field `.y`: 2 bytes
print-type-size     field `.x`: 6 bytes
print-type-size type: `Thing`: 6 bytes, alignment: 2 bytes
print-type-size     discriminant: 2 bytes
print-type-size     variant `C`: 4 bytes
print-type-size         field `.0`: 2 bytes
print-type-size         field `.1`: 2 bytes
print-type-size     variant `D`: 4 bytes
print-type-size         field `.0`: 2 bytes
print-type-size         field `.1`: 2 bytes

Graphically, the layout of Enum::A and Enum::B before and after are:

	Before	After
Enum::A	+-----+-----+-----+-----+-----+ | dsc | u16 | u16 | u16 | u16 | +-----+-----+-----+-----+-----+ ^~~Thing~~~~~~~~~~^ ^~~A~~~~~~~~~~~~~~~~~~~~~~~~~~^	+-----+-----+-----+-----+-----+-----+ | dsc | u16 | u16 | dsc | u16 | u16 | +-----+-----+-----+-----+-----+-----+ ^~~Thing~~~~~~~~~~^ ^~~A~~~~~~~~~~~~~~~~~~~~~~~~~~^
Enum::B	+-----+-----+-----+-----+ ..... | dsc | u16 | u16 | u16 | +-----+-----+-----+-----+ ^~~Thing~~~~~~~~~~^ ^~~B~~~~~~~~~~~~~~~~~~~~^	+-----+-----+-----+-----+-----+ | dsc | u16 | dsc | u16 | u16 | ..... +-----+-----+-----+-----+-----+ ^~~Thing~~~~~~~~~~^ ^~~B~~~~~~~~~~~~~~~~~~~~^

Notice how the old layout is putting Thing at the beginning of A and B, while the new layout is putting Thing at the end of A and B. The reason the new layout is worse is that now, when building Enum, there is no way to line up A's existing niche with the B case's padding. Instead a whole new discriminant needs to be added.

From reading the description of #102750, I don't get the impression that the justification of that PR applies to the difference in this placement of Thing inside A and B in the code above. It seems like just a coincidence of the implementation that the PR affected this code.

My observation is that, other things being equal, we should prefer to locate niches in the very beginning or very end of a type, not in the middle near the beginning or end of a type, as far from the middle of the type as possible. This will allow them to get lined up with the padding of smaller enum variants. Placing a niche as far from the middle of the type as possible makes room for the largest possible other type to line up before or after the niche.

Mentioning @the8472 @wesleywiser since you were recently working on layout.

[the8472]

Besides the type-size #102750 also added a secondary sort key to move the field with the largest niche in a alignment-group to the end of a alignment-group to not break a test-case introduced by #94075 which is an optimization that benefits from having niches towards the end.

So within A and B it moves Thing to the end because it's the field with the largest niche. From their perspective the niche is at the end because it's the last field. It only sorts on the field-level, it doesn't look at byte offsets of the inner type.

Maybe the sort can be made more sophisticated to only try to move things towards the end when there already is another discriminant in the beginning. Or maybe we can add the information where it's located to the niche data.

[dtolnay]

I think it would be necessary for the secondary sort to consider where the niche is located inside each field type. #94075 benefits when the largest niche gets placed as far from the middle of the type as possible.

By just looking at which field has the largest niche, your PR ended up placing the niche in A exactly in the middle of the type, which is inadvertently the worst place for it.

[the8472]

"Middle" and "End" (i.e. the relative placement) doesn't really matter. What matters it's far enough back that it's further than shorter enum variants in the outer enum. If the variant lengths are sufficiently different then even moving it back a little will help, it doesn't need to be at the absolute end.
On the other hand the prefix nich use needs them to be strictly at the front (I think).

I don't think any heuristics will be optimal in all cases. But maybe there's room for improvement for some subset.

[the8472]

See #46213 which lead to #94075. It explicitly has a niche in the middle as motivating example.

[dtolnay]

On the other hand the prefix niche use needs them to be strictly at the front (I think).

This is not accurate as far as I can tell. For example see playground in which A's niche is used by Enum's discriminant despite not being strictly at the front of A.

This is reinforced by the description of #46213 as well: "As long as B and C can fit before or after A's Niche, we can still apply the optimization."

The relevant thing is that the niche goes as far from the middle of the type as possible (my suggestion), so that the largest possible other type can line up "before or after" the niche.

If the variant lengths are sufficiently different then even moving it back a little will help, it doesn't need to be at the absolute end.

We should not be moving niches back if that means moving them toward the middle of the type, because that ends up being a worse placement.

In fact if there's a niche in the first half of a field's type, we should typically be trying to place that field as far forward as possible, not back.