创建大型数组时,线程'<main>'溢出了它的堆栈

Question

staticA_INTERSECTS_A来自以下代码的变量返回错误.这段代码应该返回一个大的1356x1356 2D数组bool.

use lazy_static::lazy_static; // 1.2.0

#[derive(Debug, Copy, Clone, Default)]
pub struct A {
    pub field_a: [B; 2],
    pub ordinal: i32,
}

#[derive(Debug, Copy, Clone, Default)]
pub struct B {
    pub ordinal: i32,
}

pub const A_COUNT: i32 = 1356;

lazy_static! {
    pub static ref A_VALUES: [A; A_COUNT as usize] = { [A::default(); A_COUNT as usize] };

    pub static ref A_INTERSECTS_A: [[bool; A_COUNT as usize]; A_COUNT as usize] = {
        let mut result = [[false; A_COUNT as usize]; A_COUNT as usize];

        for item_one in A_VALUES.iter() {
            for item_two in A_VALUES.iter() {
                if item_one.field_a[0].ordinal == item_two.field_a[0].ordinal
                    || item_one.field_a[0].ordinal == item_two.field_a[1].ordinal
                    || item_one.field_a[1].ordinal == item_two.field_a[0].ordinal
                    || item_one.field_a[1].ordinal == item_two.field_a[1].ordinal
                {
                    result[item_one.ordinal as usize][item_two.ordinal as usize] = true;
                }
            }
        }
        result
    };
}

fn main() {
    A_INTERSECTS_A[1][1];
}

我已经看到人们通过Drop在大型列表中实现结构来处理这个问题,但是我的列表中没有任何结构,你不能为bool实现它.

如果我改变A_INTERSECTS_A: [[bool; A_COUNT as usize]; A_COUNT as usize]到A_INTERSECTS_A: Box<Vec<Vec<bool>>>的代码工作正常,但我真的想在这里使用数组.

Answer 1

这里的问题几乎可以肯定result是在A_INTERSECTS_A运行初始化代码时放在堆栈上的巨大数组.它是1356 ² ≈1.8 MB,这是幅度的类似的命令到堆栈的大小.实际上,它大于Windows的默认大小1 MB(我怀疑你是在Windows上,因为你有错误信息).

这里的解决方案是通过将堆栈大小移动到堆来减少堆栈大小,例如,使用Vec(当您指示工作时)或使用Box.这将带来额外的好处,即初始化代码不必从堆栈到A_INTERSECTS_A内存进行2MB复制(它只需要复制一些指针).

直接翻译使用Box:

pub static ref A_INTERSECTS_A: Box<[[bool; A_COUNT as usize]; A_COUNT as usize]> = {
    let mut result = Box::new([[false; A_COUNT as usize]; A_COUNT as usize]);
    // ...
}

遗憾的是,它不起作用:Box::new是一个普通的函数调用,因此它的参数直接放在堆栈上.

但是,如果您正在使用夜间编译器并且愿意使用不稳定的功能,则可以使用"放置框",它实际上是为此目的而设计的:它在堆上分配空间并将值直接构造到该内存中,从而避免中间副本,并避免需要在堆栈上有数据.这只需要替换Box::new为box:

let mut result = box [[false; A_COUNT as usize]; A_COUNT as usize];

如果你(非常明智地)更喜欢坚持稳定版本,那么直到稳定的替代方法是用以下代码替换数组的外层Vec:这保留了数组的所有数据局部优势(一切都在内存中连续布局)虽然在静态知识方面稍微弱一些(编译器不能确定长度是1356).既然[_; A_COUNT]没有实现Clone, this cannot use thevec!`宏,因此(不幸的是)看起来像:

pub static ref A_INTERSECTS_A: Vec<[bool; A_COUNT as usize]> = {
    let mut result =
        (0..A_COUNT as usize)
            .map(|_| [false; A_COUNT as usize])
            .collect::<Vec<_>>();
    // ...
}

如果你绝对需要所有的阵列,那么你可以做一些unsafe魔法将它Box<[[bool; ...]; ...]>从原型中提取出来Vec.它需要两个步骤(via into_boxed_slice),因为Box<T>需要有一个完美的分配大小T,而a Vec可能需要进行全面分配以实现其O(1)摊销.这个版本看起来像:

pub static ref A_INTERSECTS_A: Box<[[bool; A_COUNT as usize]; A_COUNT as usize]> = {
    let mut result =
        (0..A_COUNT as usize)
            .map(|_| [false; A_COUNT as usize])
            .collect::<Vec<_>>();

    // ...

    // ensure the allocation is correctly sized
    let mut slice: Box<[[bool; A_COUNT as usize]]> = result.into_boxed_slice();
    // pointer to the start of the slices in memory
    let ptr: *mut [bool; A_COUNT as usize] = slice.as_mut_ptr();
    // stop `slice`'s destructor deallocating the memory
    mem::forget(slice);

    // `ptr` is actually a pointer to exactly A_COUNT of the arrays! 
    let new_ptr = ptr as *mut [[bool; A_COUNT as usize]; A_COUNT as usize];
    unsafe {
        // let this `Box` manage that memory
        Box::from_raw(new_ptr)
    }
}

我添加了一些明确的类型,以便进行的更清晰.这是有效的,因为Vec<T>暴露into_boxed_slice,因此我们可以将Box<[T]>(即动态长度)变成Box<[T; len]>给定的我们知道编译时的确切长度.