Extend null-pointer enum optimization to nested enums

[bstrie]

fn main() {
    println!("{}", std::mem::size_of::<(Box<u8>, Box<u8>, Box<u8>)>());  // 24
    println!("{}", std::mem::size_of::<Option<Option<Option<(Box<u8>, Box<u8>, Box<u8>)>>>>());  // 40
}

Theoretically, Option<Option<Option<(Box<u8>, Box<u8>, Box<u8>)>>> should be able to leverage the null-pointer optimization such that it takes up no more space than (Box<u8>, Box<u8>, Box<u8>). Implement this for arbitrary levels of nesting.

[bstrie]

cc @luqmana, @gankro, @cmr, @eddyb

[Gankra]

Oh dang I thought this worked today. Been listening to too many pipedreams on internals.

[eddyb]

@gankro well, actually, we already cover structural nesting, and the null-pointer enum optimization produces structures, so what's left is to also recurse through those - might be a bit hard to keep track of fields that are already "taken" - but everything else is there.
This might have contributed to vague or exaggerated claims.

[mdinger]

Are these optimizations documented somewhere aside from the compiler internals? It seems like something that might come up fairly often though the list might get extremely long. I'm not sure.

[killercup]

@mdinger The books has a paragraph on "nullable pointer optimization" in the FFI chapter.

[mdinger]

@killercup Okay good.

[steveklabnik]

Triage: no change.

[Emerentius]

With rustc 1.26
std::mem::size_of::<Option<Option<Option<(Box<u8>, Box<u8>, Box<u8>)>>>>()
is now one word smaller at 32 bytes because of #45225

@eddyb You've stated in rust-lang/rfcs#1230 (comment) that further changes have tradeoffs that require RFCs.
This issue falls under two points in the closed one:

• Use Multiple Invalid-Value Fields
• Use all other fields as free bits when there exists another forbidden field

This should probably be closed then, right?

[SimonSapin]

CC @rust-lang/wg-codegen

[nox]

This requires more words to be initialised even in the case of None, and as far as I know that may lead to worse performance.

[bstrie]

I'm perfectly willing to have this closed if someone on the compiler team confirms that this specific optimization requires too many tradeoffs to be valuable. Part of my original intent in filing this issue was to spur people to consider the theoretical limits of enum optimization, which was limited in 2015 but much more capable today.

[bstrie]

Closing as per the rationale in my previous comment; Rust is far more capable of doing niche optimizations where it makes sense than back when this issue was originally filed in 2015, and it's unclear that this specific memory optimization is actually desirable.