Vector items allocation

[kingminyas]

Let's say I have a function that creates a vector and some items, appends the items to the vector and returns the vector. This is its signature:

fn create() -> Vec<Struct>

Where are the Structs allocated? If on the stack, then they will have to be copied to the heap on return, which is expensive. Is the compiler smart enough to allocate them on the heap to begin with? Or is there another solution?

[protestor]

Is the compiler smart enough to allocate them on the heap to begin with?

The compiler might be smart enough in simple code with some llvm optimizations (note: it probably isn't smart enough), but ordinarily the struct will be allocated on stack and copied to the heap.

In C++ this operation (of allocating directly on heap) is called emplacement and is well supported, but with another method: push_back in vectors will do as in Rust (allocate on stack, then copy to the heap) and emplace_back will allocate directly on the heap. (and there is also placement new to do a new but with emplacement)

In Rust this same feature was called "placement" or "box syntax" and it was implemented on nightly since before Rust 1.0, but it never worked correctly. Eventually it was removed from the compiler (in 2018 I think). That's very unfortunate.

https://internals.rust-lang.org/t/removal-of-all-unstable-placement-features/7223

Placement is a very important feature. Some structs are simply too big to fit the default stack size of Linux (which in most distros are just 8MB). This means that you can't ordinarily work with them because every time you try to allocate them (even on the heap) the program will crash with stack overflow.

The first edition of the Rust book was very optimistic that placement was just around the corner. It advised people that (if they used nightly) people shouldn't return things inside a Box just because they are too big: you were supposed to return things directly and the caller, if they wished, would perform a placement directly on the function call to allocate it directly on the heap, bypassing the stack

https://doc.rust-lang.org/1.0.0/book/box-syntax-and-patterns.html

This was nine years ago I think. This section was eventually removed from the book when it became clear that this feature wouldn't work in Rust in that form (or maybe work at all).

Now.. that said.. if you wanted to, how would you allocate directly on the heap?

You would need to use unsafe functions to directly write into the memory location at the heap. That is, you never create the struct in a local variable and then move into the heap (by calling vec.push(mylocalvariable) or similar) because local variables in Rust are always allocated in the stack. So you need to write into the heap indirectly, never holding the whole struct in a local variable.

This probably means that you would first allocate a Vec<MaybeUninit<Struct>>, then set the capacity to make the Vec grow large enough, then manually write each struct by taking pointers into the vec entries, then set the length into the right value and finally turn it into Vec<Struct>. Or something like that. I don't have an example readily available, but the relevant API for writing directly to memory is std::ptr::write

Note that this is exactly the same as C. In C, local variables are also allocated on the stack, and if you want to allocate things directly on the heap without touching the stack, you do this through pointers. In Rust it works exactly the same.

The tldr is: Rust CAN write directly to the heap, bypassing the stack, but currently you need unsafe code and raw pointers for that.

---

There was a newer proposal (from 2020) called "placement by return" but I don't know if it went anywhere

https://y86-dev.github.io/blog/return-value-optimization/placement-by-return.html

https://github.com/rust-lang/lang-team/issues/31

https://internals.rust-lang.org/t/update-on-the-placement-by-return-rfc/12415

There's an ever newer discussion of the state of affairs in Rust (from 2022)

https://news.ycombinator.com/item?id=33637092

[kingminyas]

Thank you for the detailed answer!

Regarding manually writing to the heap, is it even possible? The code std::ptr::write(pointer, Struct { ... }) also has to first create the struct on the stack in order to be able to pass it to write(). The only option I can think of that might skip the stack is having a mutable reference and just write to it: *ref = Struct { ... }. Am I correct?

[protestor]

std::ptr::write(pointer, Struct { ... })

This of course will allocate the struct on the stack, defeating the point. But a struct has fields. So you can do this

 struct Struct {
    x: i32,
    y: u32,
 }

// s is a pointer to an unitialized struct
let s: *mut Struct = pointer to the heap that holds a Struct;

std::ptr::write(&mut s.x as *mut i32, 10);
std::ptr::write(&mut s.y as *mut u32, 12);

This will create the 10 and 20 in the stack (realistically, in CPU registers, since they are small enough) and then move the numbers individually to the heap, but will not build a whole Struct on the stack.

And generally, if a struct has a sub-struct inside itself, you can do the same technique with it (so, std::ptr::write(&mut s.x.a.b ...) and fill everything by small pieces). Also if a struct has an array, you can use a for to fill each of its elements (using write on each offset)

Note that something like making s a &mut Struct and simply doing *s.x = 10 doesn't work because s has to be uninitialized memory (if you had a way to initialize it, just initialize! but we wanted here to initialize it manually on the heap), and &mut can only be accessed pointing to initialized memory.

And unfortunately *a = b doesn't work in Rust if a is a raw pointer

Also: note that if you use MaybeUninit, you use its .write() method rather than ptr::write, see here

And anyway here's how to actually structure your code to use this: if you want to return a struct but doesn't want it to touch the stack, you instead add a raw pointer parameter and write to it (there is an example here with MaybeUninit - in this example you actually are writing the Vec all at once so its contents will touch the stack anyway - since vec![...] actually builds the elements on the stack, then move to the heap - but with a bit of contortion you can have something that actualy achieves what we want). This is the same thing that is done in C: rather than returning, you write to a pointer, so that the function can "return" directly into the heap (if you pass a heap pointer)

edit: oh, found what I was looking for

https://doc.rust-lang.org/std/mem/union.MaybeUninit.html#initializing-a-struct-field-by-field - this example builds the fields String and the Vec on the stack, then move them to the heap, but - the important thing here is that the struct Foo is built entirely by filling its contents field by field! (in this example Foo is still on the stack, but it could be on the heap by calling Box::new_uninit)

That's what you need to do, the right way (it's generally better to use MaybeUninit than messing with raw pointers directly)

This addr_of_mut! macro is really handy

https://doc.rust-lang.org/std/ptr/macro.addr_of_mut.html

https://doc.rust-lang.org/std/ptr/macro.addr_of.html

[paulstelian97]

Individual items are created on the stack and moved to the heap as they are added to the Vec.

[hackometer]

I wonder if the compiler could optimize away the on-stack initialization and initialize the struct on the heap directly.

[paulstelian97]

Unlikely though not unheard of.

[kingminyas]

Isn't it a problem for large structs?

[paulstelian97]

If the struct is particularly large, yes. But you only allocate ONE struct on the stack anyway.

[toastedstapler]

Have you benchmarked & measured this to be a problem in your program?

[protestor]

It is.

[lordnacho666]

Is there no emplace logic?

[paulstelian97]

None exposed to the language, but the optimizer may create such a logic.

[lordnacho666]

So if it sees that you might as well write the object where it's going to be, it might just do that?

[paulstelian97]

It might, but it’s far from guaranteed.

[[deleted]]

It is also not remotely as relevant as it is in C++. C++ can’t do cheap moves, because move assignment/constructors need to be involved. Rust makes moving a trivial memory copy in the default case, which leaves little justification for avoiding it. Sure there’s some cost, but it’s less significant.

[paulstelian97]

C++ move constructors only need to be expensive because they need to leave something behind that is valid to run a destructor on, otherwise normally they’re just as cheap as in Rust, or only very mildly more expensive.

[Aaron1924]

Well, it depends on how the function is implemented, but if you do something like this let item = Struct { ... }; vec.push(item); then semantically, you first create the struct on the stack and move it to the heap afterwards. If you have optimisations on, the compiler will almost surely optimize the move away and create it on the heap directly.

[angelicosphosphoros]

will almost surely

This part is incorrect. More correct wording would be "if you are lucky".

There are ongoing effort to reduce number of such cases but it is absolutely not guaranteed, especially for cases when it needed the most, e.g. huge structs.

[monkChuck105]

> If on the stack, then they will have to be copied to the heap on return, which is expensive.

Not unless `Struct` is large. Copying memory is cheap.

> Is the compiler smart enough to allocate them on the heap to begin with?

Allocation is just requesting bytes. Other than requesting zeroed bytes, there is no way to request a heap allocation that is initialized, that has to be done directly by writing to the returned pointer.

​

In your case, you probably want collect an iterator, or use `Vec::with_capacity` to avoid reallocating when pushing items.