Idea: guaranteed-zero padding for niches

[RalfJung]

As suggested here, one option to gain more layout optimizations would be (either for all repr(Rust) types or with per-type opt-in) to use a different kind of padding.

Right now, padding bytes may contain arbitrary data, and can be omitted when copying as they are "unstable" in a typed copy. Instead, we could also imagine a kind of padding ("zero-padding") that is guaranteed to be zero. This has the disadvantage that padding bytes need to be initialized on struct creation and copied when the struct is copied, but it has the advantage that padding bytes can become "niches" for layout optimizations.

LLVM's padding is of the "unstable" kind, but we could just add explicit fields ourselves (fields that are guaranteed to be zero) when translating zero-padded types to LLVM.

Cc @eddyb

[eddyb]

LLVM's padding is of the "unstable" kind, but we could just add explicit fields ourselves (fields that are guaranteed to be zero) when translating zero-padded types to LLVM.

LLVM has no concept of "padding" outside of "first-class aggregates", which we only use for multiple (well, 2) return values (via ScalarPair), and nothing else (no values in functions, no global initializers). And really, it's basically like loading/storing the fields individually.

As long a type is Abi::Aggregate, and it's not copied by explicit field-by-field accesses, LLVM only sees a memcpy (so size and alignment), nothing else.

EDIT: oh and there's passing values around in calls - that's also not LLVM, it's us, we'd have to make sure we don't apply architecture-specific call ABI rules (for e.g. extern "C" fns) that introspect the field structure of the type, and treat it like an opaque blob instead.

[RalfJung]

LLVM has no concept of "padding" outside of "first-class aggregates", which we only use for multiple (well, 2) return values (via ScalarPair), and nothing else (no values in functions, no global initializers). And really, it's basically like loading/storing the fields individually.

I don't know what you mean. When I define a struct/union in LLVM, won't it add padding in between the fields?

LLVM is permitted to turn a copy of struct-type into a field-by-field copy, and AFAIK we had examples where it did that? This is the kind of transformation that becomes illegal with "zero-padding" (unless we somehow already know that the target memory is zero, e.g. because it is already valid at the given type).

[bjorn3]

What would be the overhead of the actual zeroing of the padding? Especially for cg_clif, which barely performs any memory optimizations I imagine this will have a significant overhead. The only memory optimization performed by cg_clif results in a ~15% improvement. However that optimization is currently so dumb that I think zeroing padding will prevent performing this optimization. For cg_llvm it will just result in more ir to churn through with optimizations (=compiletime slowdown), or a runtime slowdown without optimizations.

[RalfJung]

Assuming the backend does naive copying (i.e., it always copies the entire struct and doesn't try to be clever by only copying the fields and ignoring padding), then the only overhead is in the constructor: Struct { f1, f2 } would have to compile to code that also writes zeroes to padding between and after the fields.

[bjorn3]

Assuming the backend does naive copying (i.e., it always copies the entire struct and doesn't try to be clever by only copying the fields and ignoring padding)

Yes

then the only overhead is in the constructor

That is exactly what I am afraid of having a >5% overhead on compile time and, when not using optimizations, runtime. Especially for enums it may result in a lot more stores being generated.

[bjorn3]

Also for the mir returned by instance_mir, the constructor is desugared into individual field assignments. This means that you either have to zero the full local in the prelude, or you have to do a complex analysis to find which bytes will be overwritten later. For the later you can't just take the field offsets, as different enum variants may have different padding.

[RalfJung]

I was thinking of struct padding only so far, where it should be pretty trivial to write some zeroes between the fields.

But I also don't see the issue with enums. In a constructor, the enum variant is statically known. So you just look at the fields of the initial variant, and zero the gaps between them.

That is exactly what I am afraid of having a >5% overhead on compile time and, when not using optimizations, runtime.

That sounds like a wild guess to me -- do you have any foundation for it being 5% rather than, say, 0.5%? I'd expect the impact to be tiny, since most structs will have way more data bytes than padding bytes and most code is not running constructors.

[bjorn3]

But I also don't see the issue with enums. In a constructor, the enum variant is statically known. So you just look at the fields of the initial variant, and zero the gaps between them.

I guess zeroing during the codegen of SetDiscriminator will work. That will unnecessarily duplicate zeroing in some cases though.

That sounds like a wild guess to me -- do you have any foundation for it being 5% rather than, say, 0.5%? I'd expect the impact to be tiny, since most structs will have way more data bytes than padding bytes and most code is not running constructors.

Not much, but given the huge speed win of the very very dumb memory optimization I implemented (bail out on address taken, more than one store possibly preceding a load, ...) I expect the cost to be relatively high. I can try to benchmark it for cg_clif though.

[upsuper]

Assuming the backend does naive copying (i.e., it always copies the entire struct and doesn't try to be clever by only copying the fields and ignoring padding), then the only overhead is in the constructor: Struct { f1, f2 } would have to compile to code that also writes zeroes to padding between and after the fields.

Another potential optimization is that if reading the padding is undefined, the compiler might be able to utilize it to vectorize some writing even if such writing would overwrite the padding area, but if pading is defined to be zero then such optimization may be less feasible.

Not sure whether that's something really happening, though.

[eddyb]

I don't know what you mean. When I define a struct/union in LLVM, won't it add padding in between the fields?

Only if you use those types as "first class aggregates", as in, by-value.
Oh and Abi::Scalar should be fine since we use it only when there is no padding after the scalar, so only Abi::ScalarPair and Abi::Vector lose padding (outside of non-Rust call ABIs).

When used for field access only, like we do, it's just a silly way to specify a field offset, nothing more.

llvm.memcpy calls don't see a type, they just know how many bytes to copy, and we pass the full size (aka "stride"), not the smaller unpadded size, anyway (mostly because we don't track the latter).

---

Also, if you look at this example's LLVM IR, this is how we lower non-unions:

#[repr(C)] // To avoid field reorder.
pub struct S(i16, i32, i64);

%S = type { [0 x i16], i16, [1 x i16], i32, [0 x i32], i64, [0 x i64] }

Note how we've made the padding fields explicit, and fill it in even when LLVM would compute the right offsets without it anyway? Well, it's because LLVM has no way to specify a custom alignment.

And without tracking "alignment from LLVM leaves" for every layout, we can't easily know in the general case whether LLVM will compute the correct offset or not, so we always force it with explicit padding.

Anyway, all that "padding" is just to make LLVM compute the right offset numbers, we should seriously consider just using one zero-length array to force an alignment and one byte array for offsets.

---

@RalfJung I suppose the only way LLVM knows something like S above has padding, especially in the local stack frame, is that some byte ranges are never written to.

If they were, it wouldn't matter how you expressed the offsets, and unless used by value (which you shouldn't do because support is dismal) LLVM struct (tuple) "types" are a red herring.

[RalfJung]

Note how we've made the padding fields explicit, and fill it in even when LLVM would compute the right offsets without it anyway? Well, it's because LLVM has no way to specify a custom alignment.

Oh I see, so LLVM itself couldn't even do the "replace copy of struct by copy of fields skipping padding" transformation, because it does not know which fields are padding. Nothing would have to change here for guaranteed-zero padding.

---

Btw, with nightly features we can already "manually" zero-pad a struct, and layout optimizations can exploit that:

#![feature(rustc_attrs)]

#[rustc_layout_scalar_valid_range_start(0)]
#[rustc_layout_scalar_valid_range_end(0)]
struct ZeroPad(u8);

impl ZeroPad {
    const ZERO: ZeroPad = unsafe { ZeroPad(0) };
}

struct Test(u8, ZeroPad, u16);
fn main() {
    println!("{}", std::mem::size_of::<Option<Test>>());
}

Playground

[RustyYato]

@RalfJung We can get even simpler, just use an enum!

#[repr(u8)]
enum ZeroPad {
    Zero = 0
}