Why can't this enum be niche optimized?

1

Hi there, I'm implementing a toy doubly-linked list and instead of keeping Options of head and tail around, I wanted to do it a little more functionally with this enum:

enum ListState<T> {
    // No elements
    Empty,
    // One element (head == tail)
    Singleton(NonNull<Node<T>>),
    // Normal list
    TwoOrMore {
        head: NonNull<Node<T>>,
        tail: NonNull<Node<T>>,
    },
}

I was expecting this to be 16 bytes (on a 64-bit system): Neither head nor tail of TwoOrMore can be null, so I thought Empty could be all zeroes, Singleton could be the the non-null pointer and then eight 0-bytes (or the other way around), and TwoOrMore would be two non-null pointers. But actually std::mem::size_of::<ListState<T>>() == 24 (for any T) which really hurts because the single tag byte apparently has to be padded to eight bytes.

If my assumptions are right, can I give a hint to the compiler about this, or do I need to do some custom union bit hacking (which would be fun as well)?

Thanks!

2

You can't give hints to the compiler, no. You could do something like this:

type ListState<T> = Option<ListStateInner<T>>;

struct ListStateInner<T> {
    left: NonNull<T>,
    right: Option<NonNull<T>>,
}
2 Likes
3

Wow, that's clever!

4

Thanks for the reply! That's more or less what I'm working with currently. Do you agree with my assumptions? Should ListState soundly fit into 16 bytes?

5

Niche optimization is not guaranteed to happen for this enum because it has three variants.

1 Like
6

Correct me if I'm wrong but optimal layout optimization would take exponential time in the worst case right? I think right now rustc just looks for a few common patterns like Option

7

To go into the “why” question: Niche optimization currently always wants to have a single place in the enum that’s the tag. Things like Option<usize> have the whole value as the tag (where 0 is one variant and non-0 is the other), but the whole value is only a word, so still a single place; or e.g. Option<Vec<T>> could have the offset of the pointer in Vec as the tag. In particular, this way, matching on the enum does only need to look at a single number. I suspect that everything beyond looking-at-a-single-number quickly gets into “less performant than expected” land, so it’s not necessarily a bad thing that you explicitly need to restructure your data in your example, where a 2 words representation is only possible of both words are inspected to find out the right enum variant.

I do however also feel like Rust should provide a way to allow you to, syntactically, handle the solution @alice provided with the syntax/patterns that the original data structure comes with. I.e. opting into some more complex “tag representation” explicitly. This could come in the form of either some way of specifying the layout of your original enum definition, or alternatively some form of “pattern synonyms” could be useful as-well. The latter would mean some way of using @alice’s code but defining patterns Empty = None, and Singleton(x) = Some(ListStateInner{left: x, right: None}), etc.

3 Likes
8

Thanks for the insight! And I agree: I don't actually mind taking care of laying out my type manually. Writing the enum as a union isn't all that hard, but you immediately lose the benefit of pattern matching and destructuring which is the whole point of the exercise to begin with, so some sort of explicit pattern specification would be very cool.

Now I wonder, could that be done with some proc macro magic...?

9

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.