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>在堆上表现得像一个数组(和),但是可以匹配数组的速度和性能？
总结:您的基准存在缺陷; 只使用一个Vec(如所描述的在这里),可能具有into_boxed_slice的,因为它是非常不太可能比堆上分配阵列慢.
不幸的是,你的基准是有缺陷的.首先,您可能没有使用优化--release进行编译(对于货物,-O对于rustc).因为如果你有,Rust编译器会删除你的所有代码.在这里查看组件.为什么？因为你从不观察矢量/数组,所以首先不需要做所有工作.
此外,您的基准测试不会测试您实际想要测试的内容.您正在将堆栈分配的数组与堆分配的向量进行比较.您应该将它Vec与堆分配的数组进行比较.
不过不要感到难过:出于多种原因,编写基准测试难以置信.请记住:如果你对编写基准知识不是很了解,最好不要先问问别人,不要相信自己的基准.
我修复了你的基准测试并包含了所有三种可能性:Vec堆栈上的数组和堆上的数组.你可以在这里找到完整的代码.结果是:
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不够智能,无法实际执行此优化.但是这样的事情很重要,人们应该意识到这一点.
最后,让我们讨论为什么两个解决方案应该同样快速以及速度是否存在实际差异.
a的数据部分Vec<T>具有与以下内存完全相同的内存布局[T]:内存中只有许多Ts连续存在.超级简单.这也意味着两者都表现出相同的缓存行为(特别是对缓存非常友好).
唯一的区别是a Vec可能比元素具有更多的容量.所以Vec自己存储(pointer, length, capacity).这比一个简单的(盒装)切片(存储(pointer, length))更胜一个字.盒装数组不需要存储长度,因为它已经在类型中,所以它只是一个简单的指针.无论如何,当你拥有数百万个元素时,我们是否存储一个,两个或三个单词并不重要.
对于所有三个元素,访问一个元素是相同的:我们首先进行边界检查,然后通过计算目标指针base_pointer + size_of::<T>() * index.但重要的是要注意,在类型中存储其长度的数组意味着优化器可以更容易地删除边界检查!这可能是一个真正的优势.
但是,智能优化器通常已经删除了边界检查.在我上面发布的基准代码中,程序集中没有边界检查.因此,通过移除边界检查,盒装数组可能会更快一些,(a)这将是一个较小的性能差异,(b)你很可能会遇到很多情况,其中删除了数组的绑定检查但不适用于Vec /切片.