Allocating array on heap using Box::new([;]) results in stack overflow

[FOO_DEBUG]

A similar question was asked before:

HELP: heap allocation, stack overflow error?

Hello There, I am actually new by Rust and I am trying to learn it. When I try to allocate an array on the heap, I get that error "thread 'main' has overflowed its stack". What is wrong here? fn main() { let arr = Box::new([0i32; 5_000_000]); println!("{}", arr[1_000_000]) }

But it doesn't look like anybody is able to justify why this is the case despite rust book specifying that this is a way to allocate on heap:

Using Box to Point to Data on the Heap - The Rust Programming Language

If this is indeed compiler "magic" as some other forums seem to suggest, can someone please point out in source code where that "magic" is happening?

[jumpnbrownweasel]

@FOO_DEBUG

But it doesn't look like anybody is able to justify why this is the case despite rust book specifying that this is a way to allocate on heap:

Using that simple technique in the book can be used in many cases, but not in cases where the size of the value is large enough to cause stack overflow -- for those cases, follow the advice in the other topic you linked.

[khimru]

@FOO_DEBUG

But it doesn't look like anybody is able to justify why this is the case

There are no need to have any justification for a bug.

You may ask “why such an obvious bug wasn't fixed”, and the answer here is, essentially: “it's not easy to fix on one hand, and if size of your data structure is large enough for the size of stack to become a problem, then overhead from use of Vec instead of array would, probably, be acceptable, on the other hand”.

And you may even create data structures directly on heap with unsafe code, if you really-really-really need them.

@FOO_DEBUG

If this is indeed compiler "magic" as some other forums seem to suggest, can someone please point out in source code where that "magic" is happening?

What “magic” are you talking about? Rust book says how to put data on heap, it doesn't say anything about not putting it on stack, first.

[FOO_DEBUG]

The "magic" I am talking about (and asking to point to in the source code), is the code that, after creating the data structure on stack, moves it to the heap.

[jumpnbrownweasel]

@FOO_DEBUG

the code that, after creating the data structure on stack, moves it to the heap

If it did that, it would cause stack overflow for a large data structure or (more likely) array, because the data structure would first be created on the stack. Doing it that way is the cause of the problem. To solve the problem, the data structure needs to be created directly on the heap after allocating space for it there.

The vec! macro does this when using the syntax that specifies an array of values. How it does it exactly, I don't know, but it looks like the relevant code is here (see the 3rd case of the macro that uses compiler intrinsics):

macros.rs - source

[quinedot]

@jumpnbrownweasel

The vec! macro does this when using the syntax that specifies an array of values.

Currently vec![val; len] uses from_elem which by default places clones into the heap directly one by one (pre-optimization). And it's also specialized for a few cases to e.g. just allocate zeroed memory or use memset.

The box_new intrinsic is what is also used by Box::new. Though vec! is more amenable to optimization on unoptimized builds, apparently.

@FOO_DEBUG

and asking to point to in the source code

More implementation details, but here's what box_new eventually becomes currently, before being turned into some sort of LLVM IR. exchange_malloc is just an allocation now I guess. So it allocates some memory and does a move into the allocation. The data being moved can still end up on the stack before the move (especially with no optimizations).

There is a lack of magic -- no guarantee that the stack isn't used -- even when optimizations are enabled. box syntax was supposed to do that, but it wasn't actually guaranteed, so it was scrapped. box_new is what remains of that attempt. Another attempt at emplacement has yet to emerge. So when you don't get the stack usage, it's due to optimizations, not guaranteed magic.

You could use vec![CONST; LEN].into() instead of Box::new([CONST; LEN]) specifically. There's no guarantee that will continue to act like it does today AFAIK, but it seems unlikely that it would be changed to start using lots of stack.

[scottmcm]

And the general answer for containers is just iter::repeat_n(x, n).collect() (repeat_n in std::iter - Rust). That can even go directly to Box<[T]>.

(Though IIRC that can't do the calloc trick, so if you know you're using a Vec the vec![x; n] is the way to go there.)

[simonbuchan]

Keeping in mind the Vec<T> to Box<[T]> transform is simply dropping the capacity field (in the case where len equals capacity, which I believe is guaranteed for a fresh vec![]?)

Edit: yep:

If len == capacity, (as is the case for the vec! macro), then a Vec can be converted to and from a Box<[T]> without reallocating or moving the elements.

-- Vec docs

[scottmcm]

Yeah, collecting into a boxed-slice actually uses Vec internally.

In fact, collecting into a VecDeque does too now: https://doc.rust-lang.org/std/collections/struct.VecDeque.html#impl-From<Vec<T,+A>>-for-VecDeque<T,+A>.

[simonbuchan]

You can't really do better given the types, but it's probably worth further noting that if you don't have an iterator with exact length (eg you're using filter or the like), collecting to a boxed slice will likely add another reallocation; that is, it's not a "go faster" button.

[khimru]

@FOO_DEBUG

The "magic" I am talking about (and asking to point to in the source code), is the code that, after creating the data structure on stack, moves it to the heap.

As was shown that's just the function that is provided by a compiler.

In general Rust tries to ensure that all “magic” only ever happens during compilation, not in runtime.

Type checking is magical (as in: complicated, convoluted and not fully specified), type inference is magical (is in: complicated, convoluted and not fully specified), borrow checking is magical (: complicated, convoluted and not fully specified), but everything that happens in rutime is not magical.

This is actually very practical approach: the one consistent thing that magic consistently does… in most books where it's involved… is inconsistency.

All that magic that Rust (and other languages) does have the same problem: when magic (like garabage collection) works – it's nice and cool, when it fails – it's… not so nice.

With all magic moved to compilation time Rust may ensure that in Runtime everything is predictable.

It doesn't work 100% reliably, even simple malloc/free pair may misbehave (people often complain about the fact that on glibc this leads to fragmentation and jemalloc or tcmalloc are common cures), removing all magic is, apparently, more or less impossible. But Rust tries to minimize it.

[FOO_DEBUG]

Thankyou. So does this line specifically macros.rs - source call the heap allocator? If yes, how? Could you please point that out in compiler source code?

[jumpnbrownweasel]

Yes, it must because boxing always does a heap allocation.

[FOO_DEBUG]

Thanks for your quick response. Didn't see it before my edit - Could you please point that out in compiler source code?

[jumpnbrownweasel]

Please see @quinedot's response for links to the implementation.

[FOO_DEBUG]

Thanks @quinedot . I am still unable to see how from_elem or box_new is actually calling glibc's malloc(). Could you please help with that?

[quinedot]

It doesn't have to call malloc. It calls the global allocator, which can be overrode. Even when that is the system default allocator, you can't intermix Global allocations with direct calls to the system default allocator.

In the source code... well in the exchange_malloc function I linked, you can see

• it calls Global.allocate
• in the same file that calls alloc_impl
• in the same file that calls alloc (or alloc_zeroed but I'll ignore that)
• in the same file that calls __rust_alloc
• in the same file we see that is a magic symbol
• the comment leads over to here which calls System.alloc (a GlobalAlloc method)
• looking in the docs we see the implementation is platform specific
• and in the unix case it calls libc::malloc or aligned_malloc
• in the same file aligned_malloc calls libc::memalign or libc::posix_memalign
• and the libc (FFI binder) crate can be found here

I didn't know any of these source code details before writing this comment, it's all just vanilla code exploration.

These aren't details your typical Rust programmer ever cares about. Embedded programmers are more likely to be aware of global_allocator and friends. FFI programmers need to be aware to not attempt to mix allocators. Even those groups usually don't care about how the compiler goes about lowering the source code to the system API (or beyond).

[FOO_DEBUG]

Thanks for your quick response @quinedot . I care about those details at the bare-metal level. Hence, the curiosity

I will look into your answer more deeply and get back. Thanks for taking the time!

[philomathic_life]

@simonbuchan

in the case where len equals capacity, which I believe is guaranteed for a fresh vec![]

Technically it is not "guaranteed for a fresh vec![]". Vec::<T>::capacity is always usize::MAX if T is a zero-sized type (ZST); thus something like vec![(); 4] has length of 4 but capacity of usize::MAX.

[simonbuchan]

Weird! But ZST Vecs are exceptions in lots of ways.