Split enum into discriminant and union

In the discussion where Zig was compared to Rust one trick was revealed which I don't know how to reproduce in Rust: split enum into discriminant and payload and merge them back.

Then you can store them separately and process separately. This may speed up certain graph algorithms and, in particular, can be very useful for compiler and JITs.

If course you can just use struct in place of enum which include discriminant as a variable and then includes union for the payload, but this is far from ergonomic Rust.

Safe API for that construct would be, by necessity, ugly and, in particular match would be ugly.

So… how to split enum and merge it back? I have tried to split out, at least, discriminant, but the following trivial program returns nonsense results:

pub enum Foo {
    A(i8),
    B(u8),
    C(i16),
    D(u16)
}

fn main() {
    println!("Size of enum: {}", core::mem::size_of::<Foo>());
    println!("Size of discriminant: {}", core::mem::size_of::<core::mem::Discriminant<Foo>>())
}
Size of enum: 4
Size of discriminant: 8```

Apparently discriminant for 32bit enum is 64bit-sized? How can that be? And how is that definition of discriminant used?

The core::mem::Discriminant<Foo> type is not guaranteed to be the same size as the discriminant for the Foo enum. The way to do this is something like this:

pub enum Foo {
    A(i8),
    B(u8),
    C(i16),
    D(u16)
}

union FooUnion {
    a: i8,
    b: u8,
    c: i16,
    d: u16,
}

enum FooDiscriminant {
    A, B, C, D,
}

enum FooRef<'a> {
    A(&'a i8),
    B(&'a u8),
    C(&'a i16),
    D(&'a u16),
}

impl FooUnion {
    unsafe fn get_ref(&self, disc: FooDiscriminant) -> FooRef<'_> {
        match disc {
            FooDiscriminant::A => FooRef::A(&self.a),
            FooDiscriminant::B => FooRef::B(&self.b),
            FooDiscriminant::C => FooRef::C(&self.c),
            FooDiscriminant::D => FooRef::D(&self.d),
        }
    }
}
1 Like

If I understood that discussion correctly, it was specifically about saving a list of such "enum"s as two arrays/vectors, where corresponding indices are corresponding discriminant / union pairs. Since a safe API cannot really force you to uphold the correct pairing, i.e. prevent you to mismatch one discriminant with an unrelated (untagged) union, a safe API would need to be created for the whole “one vector of enums represented as two vectors” construct. Accessing vectors happens either by copying a value out, or taking a reference into it. A safe API could, for copying values out, just re-assemble an ordinary enum (that ought to be efficient if done correctly); and for taking mutable references, you'd need to bundle up two references anyways, in some sort of combined handle type, if you want to be able to modify which variant you have, or you could return an enum of (mutable) references if you just want to be able to modify the fields and easily match in them. For shared references, an enum-of-references approach would be enough.

I suppose the code example that @alice provided above gives an example of the datatypes of such an enum-of-references approach. The way to convert between those would be with a straightforward match over all the cases. If the representations are similar enough (e.g. if the enum doesn't use any niches, which can be forced by repr(C) or repr(u...)), then the cases of such a match should be optimized away. E.g with repr(C), the enum is exactly equivalent (in memory representation) to a struct consisting of a tag and a union. (To the point that you'd be even allowed to just transmute it.)

I feel like the straightforward way to creating a general and safe API for such a vector-of-discriminant-and-union datastructure would be via macros.

That's exactly what I'm trying to achieve. And while get_ref is pretty efficient similar get_val is very far from optimal.

Since we are playing with fire here I hoped for some solution which may provide these 35% execution time savings, not just something that may help with memory usage.

Yeah, that's the most common case. And looks like it's working.

Still not sure how safe API can be built on top of that, but sounds promising.

The ability to actually deal with Foo directly would have been better, of course.

Indeed. That's why it works with references, but not with actual enums. Can be enough for many cases, I guess.

Yeah, that one is obvious. The question was how to split and merge parts of Foo, though.

That ability would have made it possible to create a much simpler API. But I guess beggars can not be choosers.

Well, if nothing else works well, the approach to use repr(C), define the equivalent struct, and transmute between struct and enum, is an alternative. Check out the link to the reference I put above:


I’ve also gotten some reasonably better assembly using this code; but it seems a bit unpredictable when this optimization does or doesn’t work. For example with a (self) argument instead of (&self) it goes back to a case distinction again.

On second thought, an unsafe trait, with a derive macro, should work well. The trait would define all the necessary operations, like splitting up the enum into 2 parts, or unifying 2 parts, getting an enum-of-references, etc.

Then safe datastructures to store a collection of such splittable enums can be built on top of the unsafe trait.

Yeah, I guess repr(C) and transmute is the way to go. In theory it may not be as fast as repr(rust) but I think in practice it should work well enough.

Actually, repr(Rust) can be inherently slower for your use case (at least as far a the conversion goes) since it’s not designed for supporting splitting up the thing into payload and discriminant. A repr(Rust) enum could do things like

  • use niches, like the null-pointer being used for Option-like enums containing references.
  • pack things differently, e.g.
    • an enum Foo { Bar(u8, u8, u8), Baz(u16) } could be of size 4 bytes, with a discriminant in leading position, but the u16 is padded for alignment so that it's either discr, padding, u16-first-part, u16-last-part or discr, u8, u8, u8 (depending on which variant you have). Then, for conversion between this and a union { x: [u8; 3], y: u16 }, you need a case distinction to get the right offset
    • similarly an enum Foo { A(u8), B(u16) } in repr(Rust) can be disc, pad, u16 vs disc, u8, pad, pad, so the same thing applies. This is - I think - why the code that I showed that happened to generate semi-good code only did so when I added repr(C) to the struct

This kind of optimization we're discussing is really only relevant for cases where you know “better” than the compiler and want absolute control over layout anyways; no need to avoid repr(C) in this case I guess

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.