Creating large nested array of struct using Box::new still blows stack?

help
1

Hi, in my first serious rust project I am trying to create a 3D array containing the struct Cell{activity:f64,timestamp:time::PrecisionTime}.
Since I have 128128128 cells, I tried to create this on the head using

let mut grid = Box::new([[[Cell::new();128];128];128])

I am using rust Stable and read in a google result that there was a Probelm with Box::new() still creating the variables on the stack and then bassing them into the Box. The guy asking for help was referred to the nightlies with the new "box var" syntax. Is this the same problem or am I doin something wrong? Will switching to the nightlies fix things for me?

2

Yes it's the same problem. You can use the nightlies with the feature gate box_syntax which is unstable because it's going to be generalized before it is stabilized. In the stable channel using a Vec or Box<[T]> is a good alternative, even if it loses the static size info of the outermost layer.

1 Like
3

Ok, thank you. Could you give me an example of using Box on this, or link me to one ? I thought is already used it, with T in this case being [[[Cell;120];128];128].

4

Well, you can do this:

    let grid = (0..128).map(|_| {
        (0..128).map(|_| {
            (0..128).map(|_| {
                vec![0i32; 128]
            }).collect::<Vec<_>>().into_boxed_slice()
        }).collect::<Vec<_>>().into_boxed_slice()
    }).collect::<Vec<_>>().into_boxed_slice();

But that still has 128*128 allocations and takes forever. If you want to be clever, you may be able to (@nikomatsakis?) abuse slices and do this (it only works for squares, cubes, etc...):

use std::ops::{Deref, DerefMut, Index, IndexMut};
use std::mem::transmute;
use std::slice::{from_raw_parts, from_raw_parts_mut};

struct Grid<T> {
    size: usize,
    data: Box<[T]>,
}

impl<T> Grid<T> where T: Clone {
    pub fn new_from(v: T, size: usize) -> Self {
        Grid {
            data: vec![v; size*size*size].into_boxed_slice(),
            size: size,
        }
    }
}

impl<T> Deref for Grid<T> {
    type Target = Cube<T>;
    fn deref(&self) -> &Cube<T> {
        unsafe { transmute(&self.data[..self.size]) }
    }
}

impl<T> DerefMut for Grid<T> {
    fn deref_mut(&mut self) -> &mut Cube<T> {
        unsafe { transmute(&mut self.data[..self.size]) }
    }
}

pub struct Cube<T>([T]);

impl<T> Index<usize> for Cube<T> {
    type Output = Square<T>;

    fn index(&self, idx: usize) -> &Self::Output {
        unsafe {
            let slice: &[T] = transmute(self);
            let len = slice.len();
            if idx >= len {
                panic!("index out of bounds: the len is {} but the index is {}", len, idx);
            }
            let offset = len*len*idx;
            let ptr = slice.as_ptr().offset(offset as isize);
            transmute(from_raw_parts(ptr, len))
        }
    }
}

impl<T> IndexMut<usize> for Cube<T> {
    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
        unsafe {
            // Me being careful about anti-aliasing rules.
            let (ptr, len) = {
                let slice: &mut [T] = transmute(self);
                let len = slice.len();
                if idx >= len {
                    panic!("index out of bounds: the len is {} but the index is {}", len, idx);
                }
                let offset = len*len*idx;
                let ptr = slice.as_mut_ptr().offset(offset as isize);
                (ptr, len)
            };
            transmute(from_raw_parts_mut(ptr, len))
        }
    }
}

pub struct Square<T>([T]);

impl<T> Index<usize> for Square<T> {
    type Output = [T];

    fn index(&self, idx: usize) -> &Self::Output {
        unsafe {
            let slice: &[T] = transmute(self);
            let len = slice.len();
            if idx >= len {
                panic!("index out of bounds: the len is {} but the index is {}", len, idx);
            }
            let offset = len*idx;
            let ptr = slice.as_ptr().offset(offset as isize);
            from_raw_parts(ptr, slice.len())
        }
    }
}

impl<T> IndexMut<usize> for Square<T> {
    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
        unsafe {
            // Me being careful about anti-aliasing rules.
            let (ptr, len) = {
                let slice: &mut [T] = transmute(self);
                let len = slice.len();
                if idx >= len {
                    panic!("index out of bounds: the len is {} but the index is {}", len, idx);
                }
                let offset = len*idx;
                let ptr = slice.as_mut_ptr().offset(offset as isize);
                (ptr, len)
            };
            transmute(from_raw_parts_mut(ptr, len))
        }
    }
}

fn main() {
    use std::cell::Cell;
    let g = Grid::new_from(Cell::new(0i32), 128);
    g[0][0][0].set(10);
    println!("{}", g[0][0][0].get());
    println!("{}", g[127][127][127].get());
}

This will allocate everything all at once and put it in one location. Basically, I'm encoding the size of the cube/square in the length of the slice so the slices are actually one-dimensional prefixes of the real slices.

If you know the size of the grid at compile time (or are willing to spend time calculating cube/square roots), you can just use normal slices and avoid this hack (although you'll still probably want to transmute your slices into custom DSTs).

5

I was kind of assuming that the 120 * 128 part will fit on the stack. Assuming that, you could use:

// grid typed for illustration.
let vec: Vec<_> = (0..128).map(|_| [[Cell::new(); 120]; 128]).collect();
let mut grid: Box<[[[Cell; 120]; 128]]> = vec.into_boxed_slice();

As I said, using either Vec or Box<[T]>> (both are built through Vec here), it "forgets" the static size of the outermost dimension.

With box syntax it should just be (assuming Cell is Copy then):

let mut grid = box [[[Cell::new(); 120]; 128]; 128];