为什么堆上的内存分配比堆栈上的内存慢？

我多次被告知过这个问题.但我不知道为什么...从堆中分配内存时会涉及多少额外费用？它与硬件有关吗？它与CPU周期有关吗？如此多的猜测,但没有确切的答案......有人可以给我一些细节吗？

就像"放松"所说的那样,Heap数据结构比Stack更复杂.在我看来,一些内存空间在它开始运行时被分配给一个线程作为它的堆栈,而堆由进程内的所有线程共享.这种范例需要一些额外的机制来管理每个线程对共享堆的使用,例如垃圾收集.我对吗？

因为堆是一个比堆栈复杂得多的数据结构.

对于许多体系结构,在堆栈上分配内存只是更改堆栈指针的问题,即它是一条指令.在堆上分配内存涉及寻找足够大的块,拆分它,以及管理允许free()以不同顺序执行的事项的"簿记" .

当范围(通常是函数)退出时,保证在堆栈上分配的内存被释放,并且不可能仅释放其中一些内存.

在您重新编写unwind的答案的编辑中,您提到了"堆数据结构".要非常小心,因为称为堆的数据结构与动态内存分配无关.要非常清楚,我将使用免费商店的更多语言律师术语.

正如已经指出的,堆栈分配需要递增指针,该指针通常在大多数架构上具有专用寄存器,并且解除分配需要相同的工作量.堆栈分配也作用于特定功能.这使得它们成为编译器优化的更好选择,例如预先计算堆栈上所需的总空间并对整个堆栈帧执行单个增量.同样,堆栈具有更好的保证数据局部性.堆栈的顶部几乎总是保证在高速缓存行内,正如我所提到的,堆栈指针通常存储在寄存器中.在某些体系结构上优化编译器甚至可以通过重用先前堆栈帧中的参数来完全消除堆栈上的分配,这些参数作为参数传递给更深堆栈帧中的被调用函数.同样,堆栈分配的变量通常可以提升为寄存器,从而避免分配.

相比之下,免费商店要复杂得多.我甚至不打算开始涵盖垃圾收集系统,因为这是一个完全不同的主题,这个问题被问及关于C语言.通常,来自免费商店的分配和解除分配涉及几个不同的数据结构,如空闲列表或块池.这些数据结构和簿记也需要内存,因此浪费了空间.此外,簿记记录通常与分配混合在一起,从而损害了其他分配的数据局部性.来自免费商店的分配可能涉及通常从某种形式的slab分配器向底层操作系统询问更多的进程内存.

为了进行简单的比较,并使用jemalloc-2.2.5和sloccount中的数字作为参考,jemalloc实现包含C语言中的8,800多行源代码和另外700多行测试代码.这应该可以让您清楚地了解免费存储分配和堆栈分配之间的复杂性差异:数千行C代码与单个指令.

此外,由于免费商店分配不限于单个词法范围,因此必须跟踪每个分配的生命周期.同样,这些分配可以跨线程传递,因此线程同步问题进入问题空间.免费商店分配的另一个大问题是碎片化.碎片导致许多问题:

碎片会伤害数据局部性.

碎片浪费了记忆.

碎片化使得为大型分配寻找可用空间的工作更加困难.

在现代系统中,与免费商店相比,堆栈通常相对较小,因此最终免费商店管理更多空间,从而解决更难的问题.此外,由于堆栈大小的限制,免费存储通常用于更大的分配,这种必须处理非常大和非常小的分配之间的差异使得免费存储的工作也更难.通常,堆栈分配在几千字节或更少的数量级上很小,并且堆栈的总大小仅为几兆字节.免费商店通常在程序中提供整个剩余的处理空间.在现代机器上,这可能是几百千兆字节,并且免费存储分配的大小从几个字节(如短字符串到兆字节甚至千兆字节的任意数据)变化的情况并不少见.这意味着免费存储分配器必须处理底层操作系统的虚拟内存管理.堆栈分配基本上是内置于计算机硬件中的.

如果你想真正了解免费商店分配,我强烈建议你阅读一些关于各种malloc实现甚至阅读代码的论文和文章.这里有一些链接可以帮助您入门:

dlmalloc - Doug Lea的malloc,一个在GNU C++中使用的历史参考malloc实现

phkmalloc - 由Poul-Henning Kamp编写的malloc的FreeBSD实现,Varnish Web缓存的作者

tcmalloc - 由一些Google开发人员实现的Thread-Caching Malloc

jemalloc - Jason Evan为FreeBSD实现的malloc实现(phkmalloc的继任者)

这里有一些额外的链接,其中包含tcmalloc实现的描述:

http://jamesgolick.com/2013/5/15/memory-allocators-101.html

http://jamesgolick.com/2013/5/19/how-tcmalloc-works.html

堆栈和堆之间的主要区别在于堆栈中的项目无法按顺序删除.如果将项目A,B,C添加到堆栈,则无法在不先删除C的情况下删除B. 这意味着向堆栈添加新项总是意味着将它添加到堆栈的末尾,这是一个非常简单的操作.您只需移动指向堆栈末尾的指针即可.

另一方面,在堆上,您可以不按顺序删除项目.并且只要你之后不在内存中移动其他项目(就像一些垃圾收集堆那样),你的堆就会在中间有"洞".即如果你将A,B,C添加到堆并删除B,你的堆在内存中看起来像这样:A _ C其中_是未使用(免费)内存块.如果你现在添加一个新的项目D,分配器必须找到一个足够大的连续空闲空间来容纳D.根据你的内存中有多少连续的空闲空间,这可能是一个昂贵的操作.而且它几乎总是比移动堆栈的"最后一个元素"指针更昂贵.