如果对其元素的引用次数过多，我应该使用全局堆分配数组还是局部堆栈分配一个？

计算科学 正则
2021-11-28 01:07:36

实际上，我将这个数据局部性作为我的 fortran 程序运行速度有些慢的一个可能问题。在这个程序的一部分中，我有嵌套循环，并且在这些循环中，一个大数组的给定部分被多次引用。伪代码是这样的

subroutine foo()
  use mymodule, only : big_array

  ...

  do i = 1, n1
     do j = 1, n2
        ! invoke big_array(i,j)
     end 
  end
end subroutine

n1和的价值n2可以是数万。由于 big_array 是在堆上分配的（它是一个可分配的数组），我一直怀疑上述循环中对 big_array 元素的重复引用可能会导致程序变慢。但我一直无法明确对此表示怀疑，因为我对堆栈和堆内存的工作方式只有非常基本的了解。如果我要使用堆栈分配的数据，我可以在嵌套循环之前声明一个本地自动数组，并将 big_array 的所需部分存储在这个堆栈分配的本地数组中，以便新数组在内存中更接近嵌套循环，但这当程序需要分配本地数组时，还会产生额外的 cpu 时间。所以，我不知道哪个比哪个好。

有人还可以给我一个想法，如果程序涉及读取和写入距引用点足够远的内存地址，程序会变慢多少？

1个回答

TL，DR：将其留在堆上，但切换循环顺序。

对于初学者来说，程序堆栈的空间相当有限。如果您要制作那么大的数组，如果它适合堆栈，我会感到非常惊讶。

更重要的是：您以促进内存局部性的方式进行编程是绝对正确的。要记住的重要部分是内存位置始终与最近访问的内存相关，而不是该内存在堆栈或堆上的绝对位置。这是因为CPU 缓存的工作方式。当您访问内存中的某个位置时，您不仅会读取或写入该地址中的数据，还会将附近的内存地址加载到缓存中。缓存存在的原因是，如果你接触一些内存，你很可能很快也会接触到附近的位置。现在，如果您可以按顺序读取或写入内存的方式编写代码，您将最大程度地利用 CPU 缓存。

Fortran 中的一个典型示例是多维数组按列优先顺序排列——一列中的数组元素在内存中按顺序排列。这与 C 中的多维数组（通过什么）形成对比，其中单行中的数组元素在内存中按顺序排列。现在编写程序的方式，内存访问将n1在每次内部循环迭代时按地址跳转。如果你想让你的代码运行得更快，你可以切换循环的顺序：

do j = 1, n2
    do i = 1, n1
        ! invoke big_array(i, j)
    end 
end

通过重新排序，您将在每次迭代中仅前进一个地址，而不是n1地址。这应该表现得更好，至少在 1996 年左右制造的任何机器上。

如果您正在认真地进行性能调优，那么了解一下现代内存层次结构是值得的。这里有一个很好的演示，说明访问内存层次结构的不同层需要多长时间，以及自 1990 年代以来它是如何演变的。

最后，您询问实际分配内存需要多长时间。据我了解，分配所需的时间与您分配的内存量不成正比——它实际上是每次分配的常数——因为虚拟内存是如何工作的。像密集线性代数这样的大数组计算在访问内存和计算事物上花费的时间比在分配上花费的时间要多几个数量级。如果您使用树数据结构之类的东西，您真的只需要担心分配成本，但是内存碎片在那里更多是一个问题，无论如何内存池可以解决这两个问题。

其它你可能感兴趣的问题
上一篇经典的线性弹性平衡方程组是如何推导出来的？ 下一篇为什么稀疏矩阵的“scipy.sparse.linalg.spilu”效率低于“scipy.linalg.lu”？