为什么堆上的内存分配比堆栈上慢？
我已经多次被告知。 但我不知道为什么…从堆中分配内存需要多less额外的成本？ 与硬件相关吗？ 它与CPU周期有关吗？ 这么多的猜测，但没有确切的答案…有人可以给我一些阐述？
就像“放松”一样，堆数据结构比堆栈更复杂。 而在我看来，一些内存空间在开始运行时被分配给一个线程作为它的堆栈，而堆被一个进程内的所有线程共享。 这种范例需要一些额外的机制来pipe理每个线程对共享堆的使用，比如垃圾收集。 我对吗？
因为堆是一个比堆栈复杂得多的数据结构。
对于许多体系结构来说，在堆栈上分配内存只是改变堆栈指针的问题，也就是一个指令。 在堆上分配内存包括寻找一个足够大的块，将其分开，并pipe理允许像不同顺序的free()这样的“簿记”。
在堆栈中分配的内存保证在范围（通常是函数）退出时被释放，并且不可能仅释放其中的一部分内存。
在你编辑的地方，你可以提到“堆数据结构”。 因为被称为堆的数据结构与dynamic内存分配没有关系，所以要非常小心。 要非常清楚，我会用更多的语言律师的免费商店术语。
正如已经指出的那样，堆栈分配需要增加一个指针，在大多数架构上通常都有专用的寄存器，并且释放需要相同的工作量。 堆栈分配的范围也是一个特定的function。 这使得它们更适合编译器优化，例如预先计算堆栈所需的总空间，并为整个堆栈帧做单个增量。 同样，堆栈也有更好的保证数据局部性。 堆栈顶部几乎总是保证在caching行内，正如我已经提到的，堆栈指针通常存储在寄存器中。 在某些体系结构上优化编译器甚至可以通过重用先前堆栈帧的参数，将参数作为parameter passing给更深的堆栈帧中的调用函数，从而完全消除堆栈上的分配。 同样，堆栈分配的variables通常也可以被提升为避免分配的寄存器。
相反，免费店面要复杂得多 。 我甚至不会开始涉及垃圾收集系统，因为这是一个完全不同的主题，而且这个问题被问及C语言。 通常，从免费商店分配和取消分配涉及到几个不同的数据结构，如空闲列表或块池。 这些数据结构和簿记也需要内存，因此浪费了空间。 而且，簿记logging经常与分配混合在一起，从而损害了其他分配的数据局部性。 来自免费商店的分配可能涉及通常从某种forms的板分配器向底层操作系统请求更多的进程内存。
为了简单比较，使用jemalloc-2.2.5和sloccount中的数字作为参考，jemalloc实现包含超过8,800行C语言源代码和另外700多行testing代码。 这应该给你一个关于免费商店分配和堆栈分配之间的复杂性差异的好主意：成千上万行的C代码和单个指令。
此外，由于免费商店分配不限于单个词汇范围，因此必须跟踪每个分配的生命周期。 同样，这些分配可以跨线程传递，因此线程同步问题进入问题空间。 免费商店分配的另一个大问题是碎片化。 碎片化导致许多问题：
- 碎片损害数据本地化。
- 碎片浪费内存。
- 碎片化使得寻找更大分配空间的工作变得更困难。
在现代系统中，与免费店铺相比，店铺往往相对较小，所以最终免费店铺pipe理更多的空间，从而解决了一个更难的问题。 此外，由于堆栈大小的限制，免费商店通常用于更大的分配，这种处理非常大和非常小的分配之间的差异使得免费商店的工作也变得困难。 通常，堆栈分配很小，只有几千字节或更less，堆栈的总大小只有几兆字节。 免费商店通常在程序中将整个剩余的进程空间给予。 在现代机器上，这可能是几百GB，并且自由存储分配的大小从几个字节（如短string）到兆字节甚至千兆字节的任意数据的大小不一。 这意味着免费商店分配者必须处理底层操作系统的虚拟内存pipe理。 堆栈分配本质上是内置于计算机硬件的。
如果你想真正了解免费的商店分配，我强烈推荐阅读一些关于各种malloc实现发表的文章和文章，甚至阅读代码。 这里有几个链接，让你开始：
- dlmalloc – Doug Lea的malloc，一个在一个时间点用于GNU C ++的历史参考malloc实现
- phkmalloc – 由Poul-Henning Kamp撰写的Varnish Webcaching的FreeBSD实现
- tcmalloc – 一些Google开发者实现的线程cachingMalloc
- jemalloc – Jason Evan的FreeBSD实现（phkmalloc的继任者）
这里有一些额外的链接和tcmalloc实现的描述：
堆栈和堆之间的主要区别在于堆栈中的项不能无序地移除。 如果将项目A，B，C添加到堆栈，则无法首先删除C而无法删除B. 这意味着向堆栈添加新项目总是意味着将其添加到堆栈的末尾 ，这是一个非常简单的操作。 您只需将指向该堆栈结尾的指针移动即可。
另一方面，在堆上，您可以删除无序的项目。 而且只要你在记忆之后不要移动其他物品（就像一些垃圾收集堆一样），你的堆就会在中间出现“漏洞”。 也就是说，如果将A，B，C添加到堆中并删除B，则堆在内存中将如下所示：A _ C其中_是未使用（空闲）内存块。 如果现在添加一个新的项目D，分配器必须find一个足够大的连续可用空间以适应D.根据内存中有多less个连续的可用空间，这可能是一个昂贵的操作。 而且几乎总是比移动堆栈的“最后一个元素”指针更昂贵。
