有没有办法直接在堆上分配标准的Rust数组，完全跳过堆栈？-Java 学习之路

Stack Overflow上已经有几个关于在堆上分配数组（比如 [i32] ）的问题 . 一般建议是拳击，例如 Box<[i32]> . 但是虽然拳击对于较小的阵列工作得很好，但问题是被装箱的阵列必须首先在堆栈上分配 .

因此，如果数组太大（比如1000万个元素），你会 - 甚至用拳击 - 得到一个堆栈溢出（一个不太可能有一个大的堆栈） .

然后建议使用 Vec<T> ，在我们的例子中是 Vec<i32> . 虽然这确实起到了作用，但确实会对性能产生影响 .

考虑以下程序：

fn main() {
    const LENGTH: usize = 10_000;
    let mut a: [i32; LENGTH] = [0; LENGTH];
    for j in 0..LENGTH {
        for i in 0..LENGTH {
            a[i] = j as i32;
        }
    }
}

time 告诉我这个程序运行大约需要2.9秒 . 我在这个例子中使用10'000，所以我可以在堆栈上分配它，但我真的想要一个1000万 .

现在考虑相同的程序，但使用 Vec<T> 代替：

fn main() {
    const LENGTH: usize = 10_000;
    let mut a: Vec<i32> = vec![0; LENGTH];
    for j in 0..LENGTH {
        for i in 0..LENGTH {
            a[i] = j as i32;
        }
    }
}

time 告诉我这个程序大约需要5秒钟才能运行 . 现在 time 并不是非常精确，但对于这样一个简单的程序来说差异大约2秒并不是一个微不足道的影响 .

存储是存储，当阵列装箱时，带阵列的程序也一样快 . 所以不是堆慢了 Vec<T> 版本，而是 Vec<T> 结构本身 .

我也尝试使用 HashMap （特别是 HashMap<usize, i32> 来模仿数组结构），但这比 Vec<T> 解决方案要慢得多 .

如果我的 LENGTH 已经是1000万，那么第一个版本甚至都没有运行 .

如果那是不可能的，那么堆上的结构是否类似于数组（和 Vec<T> ），但是可以匹配数组的速度和性能吗？

1 回答

7
Summary: your benchmark is flawed; just use a Vec (as described here), possibly with into_boxed_slice, as it is incredibly unlikely to be slower than a heap allocated array.

不幸的是，你的基准是有缺陷的 . 首先，您可能没有使用优化进行编译（货物为 --release ，rustc为 -O ） . 因为如果你有，Rust编译器会删除你的所有代码 . 见the assembly here . 为什么？因为你从不观察矢量/数组，所以首先不需要做所有工作 .

此外，您的基准测试不会测试您实际想要测试的内容 . 您正在将堆栈分配的数组与堆分配的向量进行比较 . 您应该将 Vec 与堆分配的数组进行比较 .

不过不要感到难过：由于很多原因，编写基准测试难度很大 . 请记住：如果你对编写基准知识不是很了解，最好不要先信任自己的基准而不先问别人 .

我修复了你的基准测试并包含了所有三种可能性： Vec ，堆栈上的数组和堆上的数组 . 你可以找到完整的代码here . 结果是：
```
running 3 tests
test array_heap  ... bench:   9,600,979 ns/iter (+/- 1,438,433)
test array_stack ... bench:   9,232,623 ns/iter (+/- 720,699)
test vec_heap    ... bench:   9,259,912 ns/iter (+/- 691,095)
```
惊喜：版本之间的差异小于测量的方差 . 所以我们可以假设它们都非常快 .

请注意，此基准测试仍然非常糟糕 . 这两个循环可以被一个循环替换，将所有数组元素设置为 LENGTH - 1 . 从快速查看程序集（以及9ms的相当长的时间），我认为LLVM不够智能，无法实际执行此优化 . 但是这样的事情很重要，人们应该意识到这一点 .

最后，让我们讨论为什么两种解决方案应该同样快速以及速度是否存在实际差异 .

Vec<T> 的数据部分与 [T] 具有完全相同的内存布局：在内存中连续存在许多 T . 超级简单 . 这也意味着两者都表现出相同的缓存行为（特别是对缓存非常友好） .

唯一的区别是 Vec 可能比元素具有更多容量 . 所以 Vec 本身存储 (pointer, length, capacity) . 这比单个（盒装）切片（存储 (pointer, length) ）多一个字 . 盒装数组在类型中已经没有't need to store the length, as it'，所以它只是一个简单的指针 . 无论如何，当你拥有数百万个元素时，我们是否存储一个，两个或三个单词并不重要 .

对于所有三个元素，访问一个元素是相同的：我们先进行边界检查，然后通过 base_pointer + size_of::<T>() * index 计算目标指针 . 但重要的是要注意，在类型中存储其长度的数组意味着优化器可以更轻松地删除边界检查！这可能是一个真正的优势 .

但是，智能优化器通常已经删除了边界检查 . 在我上面发布的基准代码中，程序集中没有边界检查 . 因此，通过移除边界检查，盒装数组可以更快一些，（a）这将是一个较小的性能差异，（b）你很可能会遇到很多情况，其中删除了数组的绑定检查但不适用于Vec /切片 .
回复于 2024-04-25T20:58:45+08:00

有没有办法直接在堆上分配标准的Rust数组，完全跳过堆栈？

1 回答

相关问题