Four levels of in-place initialization

Introduction

The goal of in-place initialization is to enable the construction of types directly into a memory location without any additional moves or copies. When working with big types this can be more efficient and even prevent stack overflows. But some types are what we call address sensitive and so cannot be moved for correctness reasons.

There is some disagreement about how we should encode in-place initialization in the language. There are conflicting requirements and constraints at play, and reconciling those is tricky. I believe that the right way to attack the problem space is not by introducing a single feature, but by introducing a 4-level feature hierarchy for in-place initialization.

Level 0: Raw pointers

At the lowest level we have raw pointers and MaybeUninit. This is by far the most flexible way to encode emplacement, but it comes at the cost of virtually everything else. This is both how the pin-init crate and placing crate are implemented internally. To read more about this see my post on placing functions where I work through a full desugaring.

The way I categorize this level is as: “It’s better than nothing”. It’s good that we have some way to encode emplacement in the ecosystem today, even if it leaves much to be desired. Here is a basic example using MaybeUninit, raw pointers, and unsafe to defer initialization:

use std::mem::MaybeUninit;

let mut x = MaybeUninit::<A>::uninit();  // 1. Create an uninit place `x` of type `A`
let y: *mut A = x.as_mut_ptr();          // 2. Take a raw pointer `y` to `x`
unsafe { y.write(A { .. }) };            // 3. Initialize all fields through `y`
let mut x = unsafe { x.assume_init() };  // 5. Notarize `x` as initialized
let y: &mut A = &mut x;                  // 6. `x` is initialized and can be used as normal

On step 5 we do move the value of x. If wanted to notarize x as initialized without moving it, we would need to call MaybeUninit::assume_init_mut, but this returns an &mut T rather than change T in-place. Without additional language features, it’s impossible to notarize an owned value as initialized without moving it or turning it into a reference.

Level 1: References

Raw pointers are very powerful, but the compiler cannot check their correctness which places an additional burden on the programmer. What we need is an abstraction that can encode most of what raw pointers can, but in a way that the compiler can statically check it within a reasonable amount of time.

My preferred proposal for this is Ding Xiang Fei’s &uninit / &own reference pair, but there are more proposals that could fill this slot. The idea of &uninit/&own that we can take an &uninit reference to a type, and once all of its fields have been initialized can then be notarized into an &own reference. There are four steps to the process here:

1. Create some uninit place x of type A.
2. Take a &uninit reference to x.
3. Initialize the value, giving you back an &own reference.
4. Notarize the initialization via assignment.

let x: A;                // 1. Create an uninit place `x` of type `A`
let y: &uninit A = &x;   // 2. Take an `&uninit` reference `y` to `x`
*y = A { .. };           // 3. Initialize all fields of `y`
let y: &own A = y;       // 4. The reference `y` is `&own` from here on out
x = y;                   // 5. Notarize `x` as initialized
let y: &mut A = &mut x;  // 6. `x` is now initialized and can be used as normal

The main innovation of this proposal is that it makes uninitialized places a first-class thing we can talk about and reference. The example above can already be written today without &uninit and &own by writing let a; a = A { ... };. But this doesn’t work across functions, which is something we can do with &uninit/&own:

// Convert an `&uninit A` into an `&own A`.
fn init_a<'a>(y: &'a uninit A) -> &'a own A {
    *y = A { ... };
    y
}

let x: A;                // 1. Create an uninit place `x` of type `A`
x = init_a(&x);          // 2. Initialize `x`
let y: &mut A = &mut x;  // 3. `x` is now initialized and can be used as normal

This is not a simple feature, but it’s not a simple problem either. This makes uninitialized values both first-class and safe to pass around and initialize. By design it wants to be as expressive as possible, which means prioritizing control above all else.

Level 2: Placing Functions

Where references prioritize control, placing functions prioritize ergonomics. Placing functions are functions which re-write the return keyword to write data to an out-pointer rather than copying. It can be implemented in terms of either raw pointers or &uninit/&own references. But unlike either of those features it doesn’t require any further changes to the function signature.

To show where this is useful we need to think about how we would transition existing code to emplace. Here is a typical function which returns a value of type A, and assigns it to the variable x.

// Create a value of type `A`
fn init_a() -> A {
    A { ... }
}

let x = init_a();  // 1. Create a value of type `A`

If you compare this to the in-place init example using &uninit and &own, you’ll notice just how much simpler this is. No fancy references, lifetimes, and notarization. But unfortunately it also copies, which if A contains many fields might be a problem. So ideally we’d have something that can emplace but without all the ceremony:

// Create a value of type `A` in-place
#[emplace]
fn init_a() -> A {
    A { ... }
}

let x = init_a();  // 1. Create a value of type `A` in-place

Not bad, right? Of course this isn’t as flexible as &uninit+&own. But for the common cases this should be plenty. Though we probably don’t just want this to be a one-off attribute, but probably its own keyword. My current thinking is that we should encode this as an effect like const, and expose all effects using the with keyword:

// Create a value of type `A` in-place
fn init_a() -> A with emplace {
    A { ... }
}

let x = init_a();  // 1. Create a value of type `A` in-place

A function annotated with the emplace effect guarantees that it will write its return value to an out-pointer rather than copy it. That makes it so these functions can “return” !Move types, which is a requirement for safe constructors of unconditionally self-referential types.

Level 3: Automatic Move Elimination

In RFC 3943 Amanieu is proposing the addition of MIR Move Eliminations. This enables the compiler to automatically eliminate moves at the MIR level as an optimization, which could apply to some of the examples we’ve looked at previously:

// Create a value of type `A`
fn init_a() -> A {
    A { ... } // assume `A` is 2kB in size
}

let x = init_a();  // 1. The optimizer ensures `x` is created in-place.

This looks very similar to the “placing functions” proposal, but encoded as an optimization. Optimizations should only affect the performance of a program and not the semantics, and so cannot be relied on. That means that for example returning !Move types from a MIR-move eliminated function would still be disallowed, since the elimination is an implementation detail of the compiler and not a part of the language.

If some novel behavior is important for the correctness of the language, it should be surfaced in the notation. Even if we could guarantee that certain expressions always emplace, as long as there are exceptions, then before long we’re finding ourselves explaining the differences between lvalues, rvalues, prvalues, glvalues, and xvalues ¹. I think it’s much better to write out requirements in code than expect programmers to infer them from context clues.

Perhaps there is a future where Rust can guarantee that every single expression in every single location can guarantee emplacement. At that point a notation to opt-in to emplacement would be superfluous, and we might choose to make that the default behavior of expressions over an edition ¹. But we can’t do this with a single feature straight away, so it’s better to start with two complementary features, which is not unlike what we’ve done with const.

Conclusion

We want in-place initialization so we can work with self-referential types, which require that they aren’t moved in memory. As well as to improve the overall performance of the language, by eliminating copies. Here are the four levels of in-place initialization features we’ve discussed in this post:

0. Raw pointers are the unsafe tool we have today and serve as a final escape hatch.
1. References are the safe subset of pointers that the compiler knows how to check.
2. Placing functions guarantee emplacement without changing function inputs or outputs, only effects.
3. MIR move elimination is a best-effort optimization to speed up existing code.

Rust tries to balance ergonomics with expressivity and control. We have pointers in the language today, and the compiler should always optimize whatever it can. By splitting the safe abstractions into a pair of high-level and low-level features we can ensure that the easy cases feel easy, but control is still there for those that need it.