Towards even smaller structs

Would something like

use std::dropper::DropFlags;
struct Fn {
  is_async: (),
  is_const: (),
  is_default: (),
  is_unsafe: (),
}
type FnBitfield = DropFlags<Fn>;

where DropFlags is a special type, solve your problem?

I don't understand how that would work. Maybe I am mistaken, but I don't think a library based solution can be substantially more ergonomic than bitfalgs.

In C, perhaps. In C++ they complicate the language by a stupefying degree. The amount of space required to detail all the exceptions they require in the C++ standard makes me think compiler implementers would rather prefer they don't exist.

4 Likes

Similar to how you can have

let x: Fn;
x.is_async = ();

you'd be able to have

let x: DropFlags<Fn> = DropFlags::new();
putinto!(x, is_async, ());

with the main difference being that the latter can be moved around, even in such a partially initialized state. (with takefrom!(x, is_async) -> Option<()> to unset it.)

I'm not sure that "well, WG21 got it spectacularly wrong" is a reason not to do it. =P We can do far, far better than the C++ committee here, because Rust does not have many of the... exciting features that make bitfields hard in C++.

(I have had to glare at people in the past for getting fresh with volatile uint8_t x : 4; and such.)

I think the key thing here is that you want to be able to get a reference into a flat Option<T>. I want to make it possible to perform all the compression tricks you could think of on enums, while making them mostly behave like regular enums and avoiding any unsafe union tricks.

2 Likes

(oh fun I'm about to suggest using ref patterns)

For this post I'm using #[flatten], but it could also be #[repr(flatten)], #[repr(inline)], or whatever else.

Let's consider the following:

struct Option8<T>(
    #[flatten] pub Option<T>,
    #[flatten] pub Option<T>,
    #[flatten] pub Option<T>,
    #[flatten] pub Option<T>,
    #[flatten] pub Option<T>,
    #[flatten] pub Option<T>,
    #[flatten] pub Option<T>,
    #[flatten] pub Option<T>,
);

We want to be able to optimize it into:

struct Option8<T> {
    init_flags: u8,
    0: MaybeUninit<T>,
    1: MaybeUninit<T>,
    2: MaybeUninit<T>,
    3: MaybeUninit<T>,
    4: MaybeUninit<T>,
    5: MaybeUninit<T>,
    6: MaybeUninit<T>,
    7: MaybeUninit<T>,
}

And ideally we'd be able to use it equivalently to the expanded version, but safely. I believe we can specify this succinctly enough:


Guide Level

A field of a #[repr(Rust)] struct may be marked as #[flatten]. If a field is marked as #[flatten], you are not allowed to take a reference to it, nor to take its address with ptr::addr_of!. The only legal operations, enforced by the compiler, are to 1) move into the field, potentially dropping the value that was already there; 2) move out of the field, potentially performing a copy, otherwise performing a destructive move; or finally 3) pattern match the field, so long as the pattern match does not require taking a reference to the field.

To illustrate:

let option8: Option8<_> = /* ... */; 

match &option8.0 {} // already illegal, takes reference to flattened field

match &option8 {
    Option8(a, ..) => {} // illegal, takes reference to flattened field (via default by-ref binding mode)
    Option8(Some(a), ..) => {} // legal, takes reference to contained value
    Option8(None, ..) => {} // legal, no references taken
    Option8(a @ Some(b), ..) => {} // illegal, takes reference to flattened field
}

match option8 {
    Option8(a, ..) => {} // legal, moves out the field
    Option8(ref a, ..) => {} // illegal, takes reference to flattened field
    Option8(Some(a), ..) => {} // legal, moves out the field
    Option8(Some(ref a), ..) => {} // legal, takes reference to contained value
}

match option8.0 {
    Some(a) => {} // legal, moves out contained value
    Some(ref a) => {} // legal, takes reference to contained value
    a => {} // legal, moves out the field
    ref a => {} // illegal, takes reference to flattened field
}

These restrictions allow the compiler to more aggressively niche values together to produce smaller structure layouts. For example, the compiler would be allowed to (but is not required to) store the eight Option discriminants in Option8 in a singular byte, as there is no requirement to be able to manifest a reference to a full Option<T>.

Implementation Concerns

There are two main concerns for implementation: 1) built-in derive support, and 2) drop glue generation. The former is simple enough: do the same as is done for #[repr(packed)]: make a temporary stack copy and call methods on that. As with #[repr(packed)], more complicated cases will just provide custom trait implementations. The problematic concern is the latter.

For types with a Drop implementation, we need to manifest &mut T in order to call Drop::drop(&mut self). This is identical (again) to #[repr(packed)], and again we take the same solution: move the value out onto the stack. This is somewhat unfortunate, as the we would prefer avoiding the copy of possible, but unavoidable.

For types with drop glue but no Drop implementation, a smarter implementation is possible. The drop glue could be enhanced to comply with the restrictions added by #[flatten] (in all cases, if it doesn't already), and thus avoid the extra copy required to manifest the &mut.


I particularly enjoy how this avoids any interaction with whether a type is Copy or not, beyond type checking of emitted #[derive]d trait implementations. Going into this I was expecting to suggest limiting #[flatten] to Copy types, but I think this specified behavior is clean enough to support all types equivalently.

I do not know if the existing pattern matching machinery is set up in such a way that it could support matching types with flattened fields as I've described here. If not, then it could make sense to implement flattening only within Copy types initially.

11 Likes

If this were to be added how could it account for sub-byte-sized fields? eg. suppose I want to write a type to represent a TCP header. Using #[repr(C)] and #[flatten] fields I could almost do this. I could make all the flag fields flattened bools for instance, but there still wouldn't be a way to represent the data offset field as a 4-bit integer.

One possible suggestion: It might be nice if we had a uint<N> type for N: usize. These would have next-power-of-two size and alignment normally but would be treated specially by the compiler when used as a #[flatten] field. This probably has a bunch of complications though and might be stretching the weirdness budget :confused:.

Edit: it would also be nice to be able to represent the 3 bits of padding as a flattened [bool; 3] rather than as three bool fields. But if flattening is non-transitive then the array would take up three bytes rather than three bits.

1 Like

For first pass #[flatten] support, I'm strongly in favor of only supporting it for fields of #[repr(Rust)] types. Extending it to #[repr(C)] and more controlled layout, as well as nonstandard width integers, can and should be left to a future extension, as it's all of an additional source of nontrivial complexity, not required for #[flatten] to be meaningfully useful, and cleanly sectioned off, not impacting initial support.

12 Likes

repr(inline) (or repr(flat)) sounds promising, but as written in that RFC, I'm not sure what semantic you're proposing for applying it to a whole struct; does that mean that all the fields are flat, or does that also mean that you can't have references to the whole type either (and it may get flattened into its parent struct)? I'd expect the former.

Other than that ambiguity, and naming, that RFC looks 98% ready to me.

I think I'd also drop the suggestion that "bit shifting and masking" is all that might be required, because we might sometimes add/subtract an offset rather than just shifting bits.

Would you be up for updating that RFC, giving some examples both of applying it to fields and to a whole struct, and submitting it?

Complete agreement there. The attribute gives the compiler control over the layout, so it's incompatible with something like repr(C).

2 Likes

I am opposed to any "flattening" that would apply to the struct as a whole and is not field-by-field. At the absolute minimum, flattening should take into account that some types have niche values, negating the need for an additional bit of storage.

1 Like

This is kind of an odd restriction, but would it make sense to say that flattening is recursive, only for #[repr(Rust)] types with exclusively pub fields?

So basically, this should be able to two bytes:

#[compact]
struct S {
    pub pair: (bool, u8),
    pub bit: bool,
}

This would not be compresable without recursively tagging as compact, because otherwise you could take a reference as &mut s.pair.0.

Personally, I value the ability to write and use Option8<T> over a recursive compacting. At a minimum, recursive #[compact] makes it unusable for types with non-pub fields, as there's no way to get at them.

Now what is valuable is for a #[compact]ed type to be transparent to a #[compact]ed parent type, so that any remaining niche space can be filled in.

I just think that being able to retroactively #[compact] someone else's type is less valuable (and prone to problems) than a nonrecursive #[compact] that allows Option8.

Indeed the former. But as I was extending the draft to cover (as I named it) #[repr(inline)] as well, it occurred to me that the shorthand might cause this very confusion. For a moment I considered removing it, but then I remembered it’s probably better kept, as I intend this feature to also cover stuffing enum discriminants in pointer alignment bits; having to annotate each individual reference in the enum would be quite burdensome.

It’s supposed to be an implementation detail anyway. I might add what other transformations are also possible; but I won’t be removing it entirely, since I think it’s useful to explore the various optimisation possibilities in order to assess what this feature actually affords us.

struct Foo {
    #[repr(inline)]
    a: Option<bool>,
    #[repr(inline)]
    b: Option<bool>,
}

If it has to remain possible to borrow the interior of either a or b, then they cannot share a memory address. Transitive compactness allows you to squeeze that structure down to a single byte.

Another possible use case is when you have a data structure for which you need different layouts during actual use versus in transit/longish-term storage. The latter can be annotated #[repr(compact)] for tighter bit packing, while the former will have no ABI-packing attributes for faster access.

Yet another reason is probably best illustrated by an example. Suppose you have this structure:

struct A(u32);

struct B(A);

struct C(#[repr(compact)] B);

Now suppose the definition of A changes to:

#[repr(align(16))]
struct A(u32);

This will change the ABI of B (since B incorporates A), but not necessarily that of C. This might become advantageous if we ever develop a system which remembers the ABI of a crate when compiling in order to maintain compatibility with that ABI in future versions of the crate. (A sort of automated generalised symbol versioning, if you will.)

Instead of adding new attributes, how about creating a new (language-level) special wrapper Packable<T>? You will not be able to get &T out of it, but compiler will be free to modify its layout depending on structure of types in which it will be used. Since a packable type can require tracking of a parent type, you will not be able to have it in a owned form. To work with it methods like store(&mut self, val: T), replace(&mut self, val: T) -> T, clone(&self) -> T where T: Clone, etc. It would make such types a bit tedious to work with, but conversion points would be explicit.

I guess it should be possible to pass around &Packable<T> and &mut Packable<T>, compiler will replace those with a pointer to the parent value and generate code accordingly (although it would mean that for functions which accept such types, they would behave as a sort-of generic arguments, so I am not sure if it's worth the trouble).

To make types with packable fields a bit more convinient, it could be worth to allow them behave as T in de-structuring and pattern matching scenarios. One of drawbacks is that it will create a bunch of implicit conversion points. For example:

struct Foo {
    a: Packable<Option<u32>>,
    b: Packable<Option<u32>>,
}

// initialization can be done using `T` with implicit conversion
let f: Foo = Foo { a: Some(1), b: None };
match f {
    // this match arm will perform implecit conversion,
    // so `b` will have type `Option<u32>`
    Foo { a: Option<a>, b } => { ... }
    _ => { ... }
}

let f: Foo = ...;
// `a` and `b` will be of type `Option<u32>`
let (a, b) = f;

But matching references will be a bit more restricted:

et f: Foo = ...;
match &f {
    // works
    Foo { a: None, b: Option<1> } => { ... }
    // could work if are to allow passing around `&Packable<T>`,
    // otherwise will cause a compilation error
   Foo { a, b: None } => { ... }
   _ => { ... },
}

The main issue is interaction between several &mut Packable<T> which track the same struct. They effectively will break the aliasing guarantees provided by &mut, since such references should be able to read and modify the same region of memory (well, of course they will operate on separate bits, but our computers do not work with bit granularity). So probably we would have to restrict creation of mutable references to packable fields to only one per parent value.

2 Likes

Actually what I was referring to was Option<NonZeroU8> alongside other fields. Said type is fully capable of storing the None value without increasing size, and as such should not have its discriminant extracted to the bitflag field.

Option<NonZeroUN> is already perfectly niche filled, so I would expect #[compact] for a field of a niche-optimal type wouldn't rearrange it, ever. Nominally the compiler would be allowed to, but it would have no reason to.

The problem that compact isn't really a property of the type of the field, it's a property of the containing type. And the whole point is that you can't take a reference to it, and you can't compose over Packable<T>. In general I agree that things should be proper types, but compact clearly isn't a type. It's less magic to make it a property of the containing type than a special not-quite-a-normal-type type for the fields.

I see the problem statement here. It definitely is desirable to be able to pack this into a single byte. I think my answer would be that, for generic types, you can write #[compact] Option<bool>, which will monomorphize the type #[compact]ly rather than with the standard layout. This makes some amount of sense for generic types specifically, since you're monomorphizing them anyway.

I don't know, though. I'm at my logic's end for figuring this out. I'll just be over here on the side to bounce ideas off of and to remind people to keep Option8 useful.

2 Likes
enum OurBoolean {
    LolNoGenerics(bool),
    FileNotFound,
}

struct Foo {
    #[repr(inline)]
    a: OurBoolean,
    #[repr(inline)]
    b: OurBoolean,
}

An advantage of Packable<T> is that you will be able to take "references" to such fields, which in some cases may be useful (e.g. if you decompose your code into separate functions working with different fields). Plus explicit methods for changing such fields will be more visible and probably less surprising than various restrictions around #[repr(inline)] fields. But I agree that such wrapper feels quite magical.

Why should the Packable go on the fields vs the whole struct?

What's the advantage of

struct Foo {
  a: Packable<...>,
  b: Packable<...>,
}

vs

struct Foo {
  a: ...,
  b: ...,
}
// ...
let x: Packable<Foo> = ...;

?

(or OptionalFields<Foo> maybe)

Because we may want to leave some fields as-is, e.g.:

struct Foo {
    a: Packable<Option<u32>>,
    b: Packable<Option<u32>>,
    c: Option<u32>,
}
1 Like

Is the goal here size or speed? We might need a way for the user to say "don't allow references to these fields, so that the struct is as small as possible" versus "don't allow references to these fields, so that the compiler is free to pack fields if it thinks it would be faster"