比较堆和堆栈中数据的访问性能

Question

众所周知,对于大多数算法来说,在堆栈上分配和释放数据比在堆上这样做要快得多.在C++中,代码的区别就像

double foo[n*n]

与

double* foo = new int[n*n]

但是,当涉及到堆或堆栈上的数据访问和计算时,有任何显着的差异？也就是说有一个速度差异

foo[i]

代码应该在几种不同的体系结构上运行,因此尝试和测量将不起作用.

Answer 1

可能存在有关缓存局部性和读/写未命中的问题（高度依赖于系统）。如果您在堆栈和堆数据上运行程序，那么与完全在堆栈的一个连续区域上运行程序相比，可以想象（取决于您的缓存架构）您会遇到更多的缓存未命中。这是 Andrew Appel（来自 SML/NJ）和zhong Shao 针对这个问题的论文，他们在其中研究了这个问题，因为堆栈/堆分配是函数式语言实现的一个主题：

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3778

他们发现了一些与写入未命中有关的性能问题，但估计这些问题可以通过缓存的进步来解决。

因此，我对当代桌面/服务器计算机的猜测是，除非您正在运行经过高度优化的、架构特定的代码（沿着缓存线传输数据），否则您不会注意到堆栈和堆访问之间的任何差异。对于具有小型缓存的设备（例如 ARM/MIPS 控制器），情况可能会有所不同，忽略缓存无论如何都会对性能产生明显的影响。