c - 为什么堆上的内存分配比栈上慢得多？

在您重申展开的答案的编辑中，您提到了“堆数据结构”。要非常小心，因为称为堆的数据结构与动态内存分配无关。为了清楚起见，我将使用free store的更多语言律师术语。

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

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

为了进行简单的比较，并使用 jemalloc-2.2.5 和 sloccount 中的数字作为参考，jemalloc 实现包含超过 8,800 行 C 语言源代码和另外 700 多行测试代码。这应该让您很好地了解自由存储分配和堆栈分配之间的复杂性差异：数千行 C 代码与一条指令。

此外，由于免费存储分配不限于单个词法范围，因此必须跟踪每个分配的生命周期。同样，这些分配可能会跨线程传递，因此线程同步问题会进入问题空间。免费存储分配的另一个大问题是碎片化。碎片化会导致很多问题：

碎片化会损害数据的局部性。

碎片化浪费内存。

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

在现代系统中，与自由存储相比，堆栈通常相对较小，因此自由存储最终会管理更多空间，从而解决更难的问题。此外，由于堆栈大小的限制，空闲存储通常用于较大的分配，必须处理非常大和非常小的分配之间的这种差异也使得空闲存储的工作更加困难。通常堆栈分配很小，大约为几千字节或更少，堆栈的总大小只有几兆字节。免费存储通常被赋予整个剩余的进程空间在一个程序中。在现代机器上，这可能是几百 GB，并且免费存储分配的大小从几个字节（如短字符串）到 MB 甚至 GB 的任意数据不等，这种情况并不少见。这意味着自由存储分配器必须处理底层操作系统的虚拟内存管理。堆栈分配本质上是计算机硬件内置的。

如果您想真正了解免费存储分配，我强烈建议您阅读发表的有关各种 malloc 实现的许多论文和文章中的一些，甚至阅读代码。以下是一些帮助您入门的链接：

dlmalloc -Doug Lea 的 malloc，在某个时间点用于 GNU C++ 的历史参考 malloc 实现

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

tcmalloc - 一些 Google 开发人员实现的线程缓存 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