Rust: Stack overflow with Boxed array

[opus111]

This is possibly the same bug as

https://github.com/rust-lang/rust/issues/40862

Using the latest version of Rust

rustc 1.27.2 (58cc626de 2018-07-18)

The following code causes a stack overflow

#[test]
fn test_boxed() {
    let a = Box::new([-1; 3000000]);
}

[nagisa]

Duplicate of https://github.com/rust-lang/rust/issues/28008.

[Havvy]

But #28008 is closed. So we should probably keep one issue open for this. Especially since box syntax isn't coming any time soon AFAICT.

[opus111]

Just 2 cents from the peanut gallery... This bug has been around for 3
years. Surely Rust needs a stable way to allocate large arrays.

On Sat, Sep 1, 2018, 3:58 AM Ryan Scheel [e-mail] wrote:

But #28008 https://github.com/rust-lang/rust/issues/28008 is closed. So
we should probably keep one issue open for this. Especially since box
syntax isn't coming any time soon AFAICT.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
https://github.com/rust-lang/rust/issues/53827#issuecomment-417841203,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AADUBIyLz22NknasbYL72xHVmMtxQTmpks5uWj4agaJpZM4WTto6
.

[nagisa]

We did make an attempt at solving this with placement-in, but that didn’t work out overall. Same problems are ailing the box syntax. An entirely different design is necessary.

[opus111]

If Box causes stack overflow, and box is not stable (and isn't coming soon), what is the recommended way to allocate a large block of memory in Rust?

[drewm1980]

@opus111 I am most certainly not a rust expert, but I bet the standard response would be to use the container types in the standard library, i.e. Vec. Depending on the application, increasing the allowable stack size may also be an option.

Is there a standard workaround for this (probably using unsafe for the cast) that works for any fixed size custom type?

[opus111]

@drewm1980 Thanks. I am also not an expert, but wouldn't a container also be allocated on the stack? My understanding is that Box or box is how one specifies that memory is not on the stack.

Surely, somebody is using Rust for large objects (e.g. images). How is it done? Does one have to be unsafe and call C?

[sfackler]

You could use a Vec rather than a fixed size array, or use the allocation APIs to have lower level control over initialization if you do need the fixed size: https://doc.rust-lang.org/std/alloc/index.html

[drewm1980]

@opus111 for images consider the ndarray crate. The standard libraries, and libraries like ndarray are doing heap allocations internally. They're probably using unsafe{} blocks internally, but it's OK, writers of standard libraries tend to know what they're doing.

Rust, like C, kept the core language very small. Like in C memory allocation is handled in a library, not at the language level. Syntactically speaking, to get an object on the heap, you have to first create it (on the stack like everything else in the core language) and pass it into a library function that does the heap allocation and a copy.

If you want to really double-down on using the stack for everything, I just found:

https://stackoverflow.com/questions/44003589/how-to-increase-the-stack-size-available-to-a-rust-library

It would be neat if rust had an ergonomic way to statically specify the max size of your stack (or have it automatically grow), and have the stack "just work" even for large objects for the main thread. If the rust devs focus on making the heap more ergonomic, people are going to use the heap more. If they focus on making the stack more ergonomic, people will use the stack more. Some people actually need to allocate their big objects on the heap, but some users are just being bitten by a default stack size limit that hasn't kept pace with the hardware, and a stack that can't grow transparently like the heap can.

[drewm1980]

I googled a bit more, and discussion around stack size issues in Rust's design unsurprisingly goes waaay back, i.e. :

https://github.com/rust-lang/rust/issues/8345

"The conclusion was that we would always use split stacks, but on 64-bit platforms with overcommit we would make the initial segment large enough that it doesn't need to grow in typical use. This was also already implemented in the old runtime."

They apparently ripped out the split stack stuff, but I guess the "make the initial segment large enough that it doesn't need to grow in typical use" didn't happen, since by default Rust's stack overflows long before you actually run out of physical RAM.

Another recently commented on ancient thread asking for configurable stack size:
https://github.com/rust-lang/rust/issues/5768

[opus111]

Thanks drew and steven. I am trying to avoid putting this object on the stack, because it is too big. I am surprised to learn that "to get an object on the heap, you have to first create it (on the stack...and pass it into a library function that does the heap allocation and a copy.". That doesn't sound very efficient :-(

Thanks for the pointer. Its not an image, but I'll try ndarray

[memoryruins]

Vec's method into_boxed_slice() returns a Box<[T]>, and does not overflow the stack for me.

vec![-1; 3000000].into_boxed_slice()

A note of difference with the vec! macro and array expressions from the docs:

This will use clone to duplicate an expression, so one should be careful using this with types having a nonstandard Clone implementation.

There is also the with_capacity() method on Vec, which is shown in the into_boxed_slice() examples.

[upsuper]

It seems that Box::new is implemented via box syntax, and the function is marked #[inline(always)], so theoretically using Box::new([0; 1_000_000]) should have the same result as box [0; 1_000_000]. But as shown in #58570, they produce different result even in release mode.

[ZiCog]

Anyone know how to do this:

let mut a = Box::new([[0; 2048]; 2048]);

Without blowing the stack?

[adamreichold]

At least on nightly you can do

let a = unsafe {
        let mut a = Box::<[[i32; 2048]; 2048]>::new_uninit();
        ptr::write_bytes(a.as_mut_ptr(), 0, 1);
        a.assume_init()
};

but it does require unsafe code.

[brundonsmith]

Is there a reason you don't use a 1D array and index into it as a 2D array? Your code will be simpler and I believe it results in some minor performance benefits. You'd be able to use @memoryruins' solution above:

let mut a = vec![-1; 2048 * 2048].into_boxed_slice();

fn get_item(x: usize, y: usize) -> i32 {
  a[x % 2048 + y / 2048] // a[x][y]
}

You could simplify a bit further by pulling out a constant:

const SIZE: usize = 2048;

let mut a = vec![-1; SIZE * SIZE].into_boxed_slice();

fn get_item(x: usize, y: usize) -> i32 {
  a[x % SIZE + y / SIZE] // a[x][y]
}

[ZiCog]

Don't you mean:

a[x * SIZE + y]

I thought about that. I wanted to avoid that ugly messing around. After all we have a high level language with a syntax for 2d indexing, we should be able to use it.
Anyway I ended up using:

let b = vec![[10; WIDTH]; HEIGHT];

Thanks all.

[brundonsmith]

Whoops, yes, I think I wrote that too fast and mixed it up with the reverse operation (index-to-x/y)

One thing you can do to at least hide that "ugly messing around" is to create a struct and hide the array behind a method that gets a mutable reference to the index. That way you can both get and set it like you normally would, and the code that uses it never has to know it's implemented as a 1D array.

[dchammond]

Just for reference another workaround that works on stable but requires unsafe is:

use std::alloc::{alloc, Layout}
let layout = Layout::new::<[u8; 0x7ffff000]>();
let mut buf = unsafe {
    let ptr = alloc(layout) as *mut [u8; 0x7ffff000];
    Box::from_raw(ptr)
};

This at least gives you the benefit that Box manages the memory. Also in this example, I didn't bother to initialize my array because I wanted a buffer that would immediately get overwritten.

[simias]

I might be missing something but since a "clean" solution to this problem is not going to happen any time soon since it's a tough nut to crack, why not work around the issue by having a macros similar to vec! that would return a boxed array? Something like this code I've been using for a while:

/// A macro similar to `vec![$elem; $size]` which returns a boxed array.
///
/// ```rustc
///     let _: Box<[u8; 1024]> = box_array![0; 1024];
/// ```
macro_rules! box_array {
    ($val:expr ; $len:expr) => {{
        // Use a generic function so that the pointer cast remains type-safe
        fn vec_to_boxed_array<T>(vec: Vec<T>) -> Box<[T; $len]> {
            let boxed_slice = vec.into_boxed_slice();

            let ptr = ::std::boxed::Box::into_raw(boxed_slice) as *mut [T; $len];

            unsafe { Box::from_raw(ptr) }
        }

        vec_to_boxed_array(vec![$val; $len])
    }};
}

Isn't it a common enough issue to warrant being provided in the standard? That would prevent everybody from coming up with their own solutions and the bugs that may come with it.

into_boxed_slice is a poor workaround because it obviously loses important static type information and makes code less explicit and, potentially, performing worse if the compiler doesn't manage to statically avoid bound checks for an arbitrarily-sized slice.

[quietlychris]

Not sure if I'm understanding everything here properly (one of the reasons I enjoy using Rust is because I don't need to worry to much about managing memory correctly or knowing too much about the underlying structures, since the compiler will have my back), but just wanted to chime in as someone who ran into this problem while trying to figure out a way to do image processing and passing image data structures between C++ and Rust. I believe a use case like this was mentioned by @opus111 earlier in this issue.

In particular, I was looking for a way to get an OpenCV Mat into Rust and convert into something that the image crate can use. Unfortunately, working through the #[repr(C)] FFI interface limits the availability of vectors and other dynamically-allocated memory, and because of the size of the images, I consistently run into an overflow issue while trying to do it all on the stack. I'm not entirely sure it would have worked anyway, but I was hoping I might be able to use Box to get around that by doing things on the heap instead, but believe I ran into the problem referenced in this issue due to the number of elements I was attempting to allocate.

I think I'll likely have to either drop back into doing some unsafe code referenced above and go from there, or stick with doing things in C++ instead.

[MSxDOS]

@quietlychris You may want to try copyless and use it until the compiler gets smart enough to eliminate all the unnecessary memory copying it currently does on various occasions.

[quietlychris]

@MSxDOS I hadn't seen that crate before, thanks for the tip!

[sjep]

Hi all - I've been dealing with this problem for allocating 2d arrays (probably a common problem) so I created a heap array that should work for many of the users above. I built it specifically to avoid blowing the stack, and for fast allocation. Of course it is very light weight - so if someone finds this useful we can surely expand on it :)

[Lokathor]

https://docs.rs/bytemuck/1.3.1/bytemuck/allocation/fn.zeroed_box.html is also an option for many of these cases.