线程“<main>”在创建大型数组时溢出了堆栈

Question

static 变量 A_INTERSECTS_A 来自以下代码 return 的错误。这段代码应该 return 一个 bool.

的大 1356x1356 二维数组

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

这里的问题几乎可以肯定是 A_INTERSECTS_A 的初始化代码运行时被放置在堆栈上的巨大 result 数组。它是 1356² ≈ 1.8 MB，与堆栈大小的数量级相似。事实上，它大于 Windows' 默认大小 1 MB（并且我怀疑你在 Windows，因为你收到了错误消息）。

此处的解决方案是通过将堆栈移动到堆中来减小堆栈大小，例如，使用 Vec 代替（如您指出的那样），或使用 Box。这将有一个额外的好处，即初始化代码不必从堆栈复制 2MB 到 A_INTERSECTS_A 的内存（它只需要复制一些指针）。

直接翻译为使用 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 是一个普通的函数调用，因此它的参数直接放在堆栈上。

但是，如果您使用的是夜间编译器并且愿意使用不稳定的功能，则可以使用 "placement box"，它就是为此目的而设计的：它在堆上分配 space并将值直接构建到该内存中，避免了中间副本，也避免了将数据放在堆栈上的需要。这只需要将 Box::new 替换为 box:

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

如果您（非常明智地）更喜欢坚持使用稳定版本，那么在稳定之前的另一种选择是用 Vec 替换阵列的 outer 层：这保留了数组的所有数据局部性优势（所有内容都在内存中连续布局），尽管在静态知识方面稍弱（编译器无法确定长度为 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 魔法将其从 Vec 提取到原始的 Box<[[bool; ...]; ...]>。它需要两个步骤（通过 into_boxed_slice），因为 Box<T> 需要为 T 完美分配大小，而 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]>，因为我们知道编译时的确切长度。

线程“<main>”在创建大型数组时溢出了堆栈

thread '<main>' has overflowed its stack when creating a large array

stack-overflow

arrays

rust