An Unusually Large Enum Union, or, Packing Pointers on 64-bit Systems

I have an enum, it looks something like this:

pub enum Large {
    This(Box<...>),
    That(Box<...>),
}

The documentation for std::mem::size_of::<...>() states that Box has the same size as usize. Union-style enums take on the size of the largest variant. In this case, both variants are of type Box, so we'd expect Large to be the same size as usize + some information (a byte?) to keep track of which variant of the enum it is.

On a 64 bit system, usize, and therefore Box, have a size of 8 bytes, so we'd expect Large to be 8-9 bytes in size. However, if you inspect the size of Large using size_of, you'd see that it's actually 16 bytes.

This makes sense - the compiler is padding the enum to be a multiple of 8 bytes. However, I still have a few questions. If I recall correctly, even 64 bit systems only use 48 bits (6 bytes) for addresses. Because of this, is there a way efficiently pack an enum of this sort into 64 bits? Such as:

Byte: 0       1       2       3       4 ... 8
Divs: |Variant--------|48-bit Pointer-- ... |

And if something like this isn't possible using an enum, how else could I do this? Would I have to resort to using a byte-array with some unsafe code or the like?

If there's a flaw in my logic, please point it out so I may revise the question to receive a more useful answer.

TL;DR: Is it possible to pack an enum around Box into usize bytes on a 64-bit system?

Not all 64 bit systems use only 48 bits for addressing. Those upper bits could be used for virtual addressing or pointer tagging, etc.

1 Like

64 bit x86 does (typically) use only 48 bits, but in a way that's designed to prevent people from accidentally using the other bits for anything else. A 64 bit pointer is required to be a sign-extended version of its 48-bit value, and CPUs actually enforce this. This "holds the door open" for CPUs to expand from 48-bit pointers to larger sizes, for scenarios that need a lot of address space.

So if you're willing to exclude your program from ever running in those scenarios, you can write code yourself to manually pack a tag into the extra bits, without using an enum. Javascript engines in browsers often do this, for example. You just have to be careful to re-set the bits to all 0s or all 1s to match bit 48 before you actually dereference the pointer.

I've done this myself here, if you'd like an example: https://github.com/rpjohnst/dejavu/blob/master/gml/src/vm/value.rs

3 Likes

Thank you for the answers. I'm attempting to implement values for a VM stack, and I would like them all to be 64 bits in size. Do you all know of any other potential solutions?

It seems like f64 nan-tagging is the way to go. Again, thanks for the help.

Aside from putting the tag in the upper bits of a pointer, you can also put the tag in the lower bits of the pointer, by ensuring that all pointers are aligned to some minimum value. For example, if everything is aligned to 8 bytes (a common default for the global allocator), you know the bottom 3 bits will always be 0.

A third option is simply to force every value to be allocated somewhere other than the VM stack itself, and put the tag in the value. You can do this without any unsafe code or pointer tricks just by using Box<SomeEnum>.

There's also a possibility of encoding the enum variant in the low-order bits if you know it contains only pointers to data with an alignment higher than 1 byte.

How might I use the lower bits to store the tag? Could you perhaps provide an example?

Basically the same way you would use the upper bits- cast the pointer to an integer, overwrite the relevant bits with the tag, and be sure to mask them out before converting back to a pointer.

If you do want to ensure the type has same size of the ptr, you can make it a box-of-enum not enum-of-boxes.

There’s a crate for hiding tag in the alignment bits: https://github.com/CAD97/pointer-utils/tree/master/crates/ptr-union.

We use this trick in rust-analyzer, where the element of a syntax tree is a pointer-sized enum of either interior node or a token.

2 Likes

I know we already have the concept of "niches" for things like the null pointer optimisation, but would it be possible for Rust to automatically do this sort of layout optimisation using a pointer's unused bits?

Assuming we have an enum below:

enum Foo {
    Bar(Box<u32>),
    Quux(Box<f32>),
}

If the discriminant is packed within the alignment of the box ptr, how can we get &Box<f32> from Foo with Quux variant?

3 Likes

Also, see the tagged-box crate.