Idea: "compact" enums and structs

Issue by glaebhoerl
Saturday Mar 01, 2014 at 12:33 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/12642

This issue was labelled with: B-RFC in the Rust repository

TL;DR By optionally taking away interior references, enums and structs can be represented much more compactly, potentially taking over most of the current use cases for manual bit twiddling code.

Rust leaves the layout of its enum types undefined for optimization purposes, but in practice most optimization possibilities are ruled out by the fact that interior references need to work. For instance, if you have an enum which contains another enum, you may want to collapse their discriminants together into a single field:

enum X { Foo(Option<bool>), Bar(bool) }

Here we could use a single discrimant field for both X and Option, so that it ranges 0..2, e.g. 0 => Foo(None), 1 => Foo(Some), 2 => Bar. Going further, we could pack in the bools as well, and represent X as a single u8: 0 => Foo(None), 1 => Foo(Some(false)), 2 => Foo(Some(true)), 3 => Bar(false), 4 => Bar(true). But in both cases, this makes interior references, e.g. match some_x { Foo(ref opt_bool) => ..., _ => ... } impossible, so we must refrain.

The idea would be to allow annotating an enum as "compact", in which case interior references are made illegal (but see below), and these optimization possibilities are opened back up: the compiler would be free to use any magic it wants to make the representation of the enum as compact as it is able, combining discriminants as above, taking advantage of tag bits in pointers, NaN-boxing, and so on. When generating code, the compiler would insert the necessary bit twiddling operations to pack the original values into this representation, and to take them back out again.

The same thing is possible for structs. For instance, a struct of bools could be represented as a bunch of bits:

compact struct Flags { 
    is_big: bool,
    is_red: bool,
    is_quick: bool,
    is_hungry: bool,
    ...
}

Now size_of::<Flags>() == size_of::<u8>()! If we let our imagination run further ahead, given types like i31, i30 and so on, we could also take advantage of those extra bits.

(It's important to note that this "compactifying" could always be deep, because the restriction against interior references would also be deep. If we have a non-compact struct type and store it in a compact one, references to the interior of the inner struct would likewise be forbidden, so it could be compacted as well. The example from above of representing enum X as a single u8 also relies on this property.)

I think this feature could be a much nicer solution for most of the use cases where manual bit twiddling code is currently necessary (and also most of the use cases for bitfields in C).

Up until now, for simplicity's sake I've been assuming that interior references would be forbidden. But it may be possible to allow them. The idea is that when you take an interior reference:

let hungry: &bool = &my_flags.is_hungry;

the value would first be copied out onto the stack (only physically, not semantically!), and then the reference would point to the stack value. This is not dissimilar to what happens if you write let nine = &9;. Because & is an immutable reference, the difference would not be observable.

Going deeper into the woods, assuming #12624, &mut borrows could also be represented by copying out the value at the beginning of the borrow, and then copying it back at the end. Again, because &mut would have exclusive access to the given object, the difference should not be observable.

I'm not sure if this would definitely work, but it seems like it might. Whether this is feasible has repercussions for syntax: if compact enums/structs are semantically identical to normal ones, and differ only in representation and performance, #[compact] could just be an attribute. If, however, the semantics differ, it would be more appropriate to use actual syntax to mark the difference.

Start by reading this issue and the earlier discussion in #12642, then review the implications of #12624 mentioned in the proposal. The work would need to resolve compact enum and struct representation, interior-reference semantics, and whether the feature belongs in attribute syntax or dedicated syntax before an implementation can be scoped.