访问堆中的数据比栈中的数据更快吗?

106

我知道这听起来像是一个普遍的问题,我看到了许多类似的问题(在这里和网络上),但没有一个真正像我的困境。

假设我有这段代码:

void GetSomeData(char* buffer)
{
    // put some data in buffer
}

int main()
{
     char buffer[1024];
     while(1)
     {
          GetSomeData(buffer);
          // do something with the data
     }
     return 0;
}

如果我将buffer[1024]声明为全局变量,会获得更好的性能吗?

我在Unix上通过time命令运行了一些测试,并没有发现执行时间之间有明显的差异。

但我并不是完全信服...

理论上,这种改变是否应该有所影响呢?


9
除非我们谈论像NUMA这样的东西,否则访问的内存位置对速度没有影响,而是取决于你通过多少级间接寻址来访问它。 - PlasmaHH
3
由于需要间接寻址,从堆中访问会稍微慢一些,请参考@PlasmaHH的评论。栈内存和堆内存之间没有区别,它们都存在于RAM中。 - 101010
11
这句话的意思是:“当问题涉及到访问性能(access performance)时,不应该将其标记为关于分配性能(allocation performance)的重复问题。”请注意,翻译过程中不能添加解释或其他额外信息,必须保持原意并提高可读性。 - Felix Glas
1
我很惊讶地发现,有时堆栈分配的性能比堆分配要差得多 - 特别是在多线程程序中。我相信这可能与不同的访问模式有关,有时会导致更多的缓存未命中。 - Rafael Baptista
根据维护和生产力方面的考虑,堆栈更快,因为不会有任何内存泄漏。我建议使用按值参数传递和返回的代码,然后在一切正常运行时编写一个执行堆分配并使用大量指针的版本。然后针对您特定的应用程序测量性能。也许您可以使用Python脚本将所有内容转换为指针和内存分配。如果您正在制作用户友好的库,则应该使用智能指针。在大多数应用程序中,我发现不清楚哪个对象应该拥有什么指针。 - D Left Adjoint to U
显示剩余4条评论
7个回答

121
访问堆中的数据是否比访问栈中的数据更快?
并不是固有的……在我工作的每个架构上,可以预期所有进程“内存”以相同的速度运行,这取决于哪个级别的CPU缓存/RAM/交换文件保存当前数据,并且任何硬件级别的同步延迟都可能触发对该内存的操作,使之对其他进程可见,合并其他进程/ CPU(核)的更改等。 (使用非一致性内存架构(NUMA)的多CPU插槽主板,一个CPU访问“更靠近”另一个CPU的内存所需的时间往往不同,但这超出了本问题的范围。)
操作系统(负责页面故障/交换)和硬件(CPU)在尚未访问或交换出的页面上捕获访问时,甚至不会跟踪哪些页面是“全局”、“堆栈”、“堆”……存储器页面是存储器页面。
虽然操作系统和硬件不知道内存用于全局、堆栈还是堆,而且它们都由具有相同性能特征的相同类型的内存支持,但还有其他微妙的考虑因素(在此列表后面详细描述):
分配 - 程序花费的时间“分配”和“释放”内存,包括随着堆使用增长而偶尔进行的sbrk(或类似)虚拟地址分配
访问 - 程序用于访问全局、堆栈和堆的CPU指令的差异,并通过运行时指针使用基于堆的数据的额外间接寻址。
布局 - 某些数据结构(“容器”/“集合”)更加高速缓存友好(因此更快),而某些的通用实现需要堆分配,可能不太高速缓存友好。
对于全局数据(包括C++命名空间数据成员),虚拟地址通常会在编译时计算和硬编码(可能是绝对值或从段寄存器的偏移;有时在进程由操作系统加载时需要调整)。
对于基于堆栈的数据,堆栈指针寄存器相关地址也可以在编译时计算和硬编码。然后,在函数输入和返回时,堆栈指针寄存器可以根据函数参数、本地变量、返回地址和保存的CPU寄存器的总大小进行调整(即在运行时)。添加更多基于堆栈的变量只会改变用于调整堆栈指针寄存器的总大小,而不会产生越来越严重的影响。
以上两种都基本上没有运行时分配/释放开销,而基于堆的开销非常真实,并且对某些应用程序可能具有重要影响……对于基于堆的数据,运行时堆分配库必须查询并更新其内部的数据结构,以跟踪该库提供给应用程序的特定指针所关联的堆内存块或池的哪些部分,直到应用程序释放或删除了内存。如果虚拟地址空间不足以容纳堆内存,则可能需要调用类似于sbrk的操作系统函数来请求更多内存(Linux也可以调用mmap来创建大内存请求的后备内存,然后在free/delete上取消映射该内存)。
访问方面,对于全局和基于栈的数据,可以在编译时计算出绝对虚拟地址或段或堆栈指针寄存器相对地址,因此运行时访问非常快速。对于基于堆的数据,程序必须通过运行时确定的持有堆上虚拟内存地址的指针来访问数据,有时需要在运行时将一个偏移量应用于指向特定数据成员的指针。在某些架构上,这可能需要一些时间。
对于堆访问,指针和堆内存都必须在寄存器中才能访问数据(因此对CPU缓存有更高的需求,在规模上需要更多的缓存未命中/故障开销)。注意:这些成本通常微不足道 - 除非您正在编写延迟或吞吐量非常重要的东西,否则根本不值一提。
在源代码的连续行中列出全局变量时,它们将被排列在相邻的内存位置中(尽管可能会有填充以进行对齐),在同一函数中列出的基于栈的变量也是如此。这很好:如果你有X字节的数据,你可能会发现它们对于N字节缓存行而言,可以被紧密地打包到可以使用X/N或X/N + 1个缓存行访问的内存中。其他附近的堆栈内容,如函数参数、返回地址等等,很可能在程序需要时同时用到,因此缓存非常高效。
当使用基于堆的内存时,堆分配库的连续调用可以轻松返回指向不同缓存行的内存的指针,特别是如果分配大小差异较大(例如3字节分配后跟13字节分配)或者已经进行了大量的分配和释放(导致“碎片化”)。这意味着当您要访问一组小的堆分配内存时,最坏的情况是您可能需要故障多个缓存行(除了需要加载包含指向堆的指针的内存)。堆分配内存将不会与堆栈分配的数据共享缓存行 - 没有协同作用。此外,C++标准库未提供更复杂的数据结构(例如链表、平衡二叉树或散列表),用于在基于堆栈的内存中使用。因此,在使用堆栈时,程序员往往会尽力使用数组,即使这意味着需要进行一些暴力搜索。缓存效率可能会使这种方法整体上更好,而堆基数据容器中元素分布在更多的缓存行中。当然,堆栈使用不适用于大量元素,并且 - 如果没有至少使用堆备份选项 - 将创建在处理超出预期的更多数据时停止工作的程序。
在您的示例程序中,您正在将全局变量与函数本地(堆栈/自动)变量进行对比…没有涉及堆。堆内存来自 new 或 malloc/realloc。对于堆内存,值得注意的性能问题是应用程序本身正在跟踪哪些地址使用了多少内存 - 所有这些记录需要花费一些时间来更新,因为指向内存的指针由 new/malloc/realloc 分配,删除或释放它们时也需要花费一些时间来更新它们。
对于全局变量,内存分配可能实际上在编译时完成,而对于基于堆栈的变量,通常有一个堆栈指针,每次调用函数时都会增加编译时计算的本地变量大小之和(以及一些管理数据)。因此,当调用 main()时,可能需要一些时间来修改堆栈指针,但它可能仅被不同数量的修改而不是没有 buffer 时修改,因此在运行时性能上没有任何差异。
注意:我省略了上面一些乏味且基本无关紧要的细节。例如,某些CPU使用寄存器的“窗口”将一个函数的状态保存为它们进入另一个函数的调用;一些函数状态将保存在寄存器而不是堆栈中;一些函数参数将传递到寄存器而不是堆栈中;并非所有操作系统都使用虚拟寻址;某些非PC级硬件可能具有更复杂的内存架构,具有不同的影响...

2
关于您的第一句话:我开始写同样的事情,但正如您在接下来的内容中指出的那样,它是不正确的;在大多数处理器上,真正的情况是速度并不取决于内存位于何处,而是取决于之前访问了什么。 - James Kanze
@JamesKanze “这并不是真的” - 好吧,这取决于观点 - 可以肯定的是,缓存未命中比缓存命中慢(无论在哪个级别上缓存),而且相同的阶梯状性能曲线适用于内存所被应用程序用于全局变量+静态变量/堆栈/堆/线程特定性/共享等用途...那是我的本意,尽管我同意它可能可以更好地措辞,并会尝试改进它。 - Tony Delroy
1
@Tony D:你能帮我澄清一下疑惑吗?所以栈通过访问(写入/加载)大致与堆相同,但在分配方面应该更快,因为它已经在编译时完成,这不会给运行时增加太多开销,对吗?谢谢。 - dragonxlwang
2
@dragonxlwang:大概就是这样,没错。谢谢。 - Tony Delroy
5
这是一个非常出色和详尽的回答,非常感谢。它真正解决了我在为什么栈和堆尽管都分配在内存中但性能特征不同方面存在许多困惑的问题。特别是关于栈指针可以在编译时确定这一点,这是一个巨大的见解! - Nicholas Montaño

47

引用 Jeff Hill 的回答

栈更快,因为它的访问模式使得从其中分配和释放内存变得非常简单 (只需递增或递减指针/整数),而堆在一个分配或释放中涉及了更复杂的簿记。此外,栈中的每个字节往往会被频繁重用,这意味着它往往会被映射到处理器的缓存中,从而使其非常快速。对于堆来说,另一个性能问题是,堆大多数情况下都是全局资源,通常需要支持多线程,即每个分配和释放通常需要与程序中的“所有”其他堆访问同步。

enter image description here


28
“在堆中访问数据比在栈中访问数据更快吗?” 这是问题,实际上你的强调是错误的,如果具有相同的数据和相同的访问模式,则理论上堆应该与栈一样快。 如果您的数据是一个数组,访问应该花费相同的时间,只要数据是连续的。 如果您有几个小的数据位于内存中的各个位置,则栈将具有更快的速度。 - Krupip

18
这个主题有一篇博客文章可供参考stack-allocation-vs-heap-allocation-performance-benchmark,其中展示了分配策略的基准测试。测试以C语言编写,对比了纯粹的分配尝试和带有内存初始化的分配。在不同的总数据大小下,执行了不同数量的循环并测量时间。每次分配都包含10个不同大小的alloc/init/free块(图表显示了总大小)。
测试在Intel(R) Core(TM) i7-6600U CPU, Linux 64 bit, 4.15.0-50-generic平台上运行,关闭了Spectre和Meltdown补丁。
没有初始化的情况下: Memory allocation with out data init 有初始化的情况下: Memory allocations with data init 结果显示,在没有数据初始化的条件下,纯分配有显著差异。栈比堆快,但请注意循环计数非常高。

当处理已分配的数据时,栈和堆之间的性能差异似乎会减少。在进行1M malloc/init/free(或栈分配)循环时,每个循环尝试10次分配,总时间方面,栈仅领先于堆8%。


重要提示: 如果分配和释放按正确顺序进行,许多malloc/heap实际上就像堆栈一样运行,只有很少的开销。如果分配是半随机的,则簿记成本显着增加。 - mczarnek

9

就我所知,下面代码中的循环 - 它只是从一个大数组中读取并写入每个元素 - 当数组在堆栈上时,与在堆上时相比,在我的机器上始终运行得更快(GCC,Windows 10,-O3标志),即使在重新启动后(当堆碎片最小化):

const int size = 100100100;
int vals[size]; // STACK
// int *vals = new int[size]; // HEAP
startTimer();
for (int i = 1; i < size; ++i) {
    vals[i] = vals[i - 1];
}
stopTimer();
std::cout << vals[size - 1];
// delete[] vals; // HEAP

当然,我首先必须将堆栈大小增加到400 MB。请注意,在结尾打印最后一个元素是必要的,以防止编译器优化掉所有东西。


我们如何增加堆栈大小? - Paiman Roointan
2
在Linux下,您可以使用ulimit -s - Chen Li

8
你的问题没有一个确切的答案;它取决于其他你正在做的事情。一般来说,大多数机器在整个过程中使用相同的“内存”结构,因此无论变量位于哪里(堆、栈或全局内存),访问时间都将是相同的。另一方面,大多数现代机器都具有分层的内存结构,包括内存管道、几个级别的缓存、主内存和虚拟内存。根据处理器之前发生了什么,实际访问可能是其中的任何一个(无论是堆、栈还是全局),这里的访问时间差异巨大,如果内存位于管道的正确位置,则访问时间仅需一个时钟周期,如果系统必须访问磁盘上的虚拟内存,则需要约10毫秒。
在所有情况下,关键是局部性。如果访问“靠近”先前的访问,就极大地提高了在更快的位置(例如缓存)中找到它的机会。在这方面,在栈上放置较小的对象可能更快,因为当您访问函数的参数时,您正在访问堆栈内存(至少对于英特尔32位处理器而言——对于设计更好的处理器,参数更有可能位于寄存器中)。但当涉及到数组时,这可能不是问题。

基本上,为了准确比较堆栈速度和堆速度,我们应该禁用CPU缓存吗? - Gabriel

5

当在堆栈上分配缓冲区时,优化范围不是访问内存的成本,而是消除堆上通常非常昂贵的动态内存分配(堆栈缓冲区分配可以被认为是瞬间完成的,因为整个堆栈在线程启动时分配)。


-2

在堆上声明变量和变量数组会使程序运行变慢,这是事实。可以这样考虑:

全局创建的变量只分配一次,并在程序关闭时释放一次。对于堆对象,每次运行函数时都必须在现场分配变量,并在函数结束时释放。

曾经尝试在函数内分配对象指针吗?最好在函数退出之前释放/删除它,否则您将拥有一个内存泄漏,除非您在类对象中执行此操作,在那里它在析构函数中被释放/删除。

当涉及访问数组时,它们都是相同的,首先通过sizeof(DataType) * elements分配内存块。稍后可以通过->访问。

1 2 3 4 5 6 
^ entry point [0]
      ^ entry point [0]+3

堆和栈分配是完全不同的东西。栈分配几乎是免费的,所以你需要做多少次都无所谓。 - Karoly Horvath
1
被踩了三次,但没有人解释这个答案有什么问题。所以我给它点了一个赞。 - Gabriel
对于堆对象,每次运行函数时都必须在现场分配变量,并在函数结束时释放。这并不正确(您是不是指“栈对象”?)堆分配返回一个指针,可以在任何以后的时间用于解除分配 - 分配和解除分配代码与单个函数的进入或退出没有必要的联系; 它们甚至可以发生在所有函数之外(即全局指针可以跟踪堆内存)。函数可以返回指针供调用者管理。这里有很多错误信息。 - Tony Delroy

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接