哪个更快：堆栈分配或堆分配

Question

这个问题听起来可能相当初级，但这是我与另一位共事的开发人员进行的辩论。

我小心翼翼地在可能的地方堆栈分配东西，而不是堆分配它们。他正在和我说话，看着我的肩膀并评论说这没有必要，因为它们在性能方面是相同的。

我一直认为堆的增长是恒定的时间，堆分配的性能取决于堆的当前复杂性，用于分配（找到适当大小的孔）和取消分配（折叠孔以减少碎片，如如果我没记错的话，许多标准库实现在删除期间需要时间来执行此操作）。

这让我觉得可能非常依赖编译器。特别是对于这个项目，我将 Metrowerks 编译器用于 PPC 架构。了解这种组合会很有帮助，但总的来说，对于 GCC 和 MSVC++，情况如何？堆分配的性能不如堆栈分配吗？没有区别吗？或者差异如此之小以至于变得毫无意义的微优化。

原文由 Adam 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

堆栈分配要快得多，因为它真正所做的只是移动堆栈指针。使用内存池，您可以从堆分配中获得相当的性能，但这会稍微增加复杂性并带来一些麻烦。

此外，堆栈与堆不仅是性能考虑因素；它还告诉你很多关于对象的预期生命周期的信息。

原文由 Torbjörn Gyllebring 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

特定于 C++ 语言的问题

首先， C++ 没有规定所谓的“堆栈”或“堆”分配。如果您谈论的是块作用域中的自动对象，它们甚至没有“分配”。 （顺便说一句，C 中的自动存储持续时间绝对不同于“已分配”；后者在 C++ 用语中是“动态”的。）动态分配的内存在 空闲存储 区，不一定在“堆”上，尽管后者通常是（默认） _实现_。

尽管根据 抽象机器 语义规则，自动对象仍会占用内存，但允许符合 C++ 的实现在可以证明这无关紧要时忽略这一事实（当它不改变程序的可观察行为时）。此权限由 ISO C++ 中 的 as-if 规则 授予，这也是启用常规优化的一般条款（ISO C 中也有几乎相同的规则）。除了 as-if 规则，ISO C++ 还具有 复制省略规则 以允许省略对象的特定创建。因此省略了所涉及的构造函数和析构函数调用。结果，与源代码隐含的幼稚抽象语义相比，这些构造函数和析构函数中的自动对象（如果有的话）也被消除了。

另一方面，免费商店分配绝对是设计上的“分配”。在 ISO C++ 规则下，这样的分配可以通过调用 分配函数 来实现。但是，从 ISO C++14 开始，有 一个新的（非假设）规则 允许在特定情况下合并全局分配函数（即 ::operator new ）调用。所以动态分配操作的一部分也可以像自动对象的情况一样是无操作的。

分配函数分配内存资源。可以使用分配器基于分配进一步分配对象。对于自动对象，它们是直接呈现的——虽然可以访问底层内存并用于为其他对象提供内存（通过放置 new ），但这作为免费存储没有多大意义，因为没有办法将资源转移到其他地方。

所有其他问题都超出了 C++ 的范围。尽管如此，它们仍然很重要。

关于 C++ 的实现

C++ 没有暴露具体化的激活记录或某种一流的延续（例如著名的 call/cc ），没有办法直接操作激活记录帧 - 实现需要放置自动对象至。一旦与底层实现（“本机”不可移植代码，例如内联汇编代码）没有（不可移植的）互操作，则忽略底层的帧分配可能是非常微不足道的。例如，当被调用的函数被内联时，可以有效地将帧合并到其他帧中，因此无法显示什么是“分配”。

但是，一旦尊重互操作性，事情就会变得复杂。 C++ 的典型实现将公开在 ISA（指令集架构）上的互操作能力，其中一些 调用约定 作为与本机（ISA 级机器）代码共享的二进制边界。这显然会很昂贵，特别是在维护 堆栈指针 时，堆栈指针通常直接由 ISA 级寄存器保存（可能需要访问特定的机器指令）。堆栈指针指示（当前活动的）函数调用的顶部帧的边界。当进入一个函数调用时，需要一个新的帧并且堆栈指针被添加或减去一个不小于所需帧大小的值（取决于 ISA 的约定）。然后当堆栈指针在操作之后 分配 帧。函数的参数也可以传递到堆栈帧上，具体取决于调用所使用的调用约定。框架可以保存由 C++ 源代码指定的自动对象（可能包括参数）的内存。在这种实现的意义上，这些对象是“分配的”。当控件退出函数调用时，不再需要该帧，通常通过将堆栈指针恢复到调用前的状态来释放它（根据调用约定之前保存的）。这可以被视为“解除分配”。这些操作使激活记录有效地成为一个 LIFO 数据结构，因此它通常被称为“ （调用）堆栈”。堆栈指针有效地指示堆栈的顶部位置。

因为大多数 C++ 实现（尤其是针对 ISA 级别的本机代码并使用汇编语言作为其直接输出的那些）都使用类似的策略，所以这种令人困惑的“分配”方案很受欢迎。这样的分配（以及释放）确实会花费机器周期，并且当（未优化的）调用频繁发生时可能会很昂贵，即使现代 CPU 微架构可以通过硬件为通用代码模式实现复杂的优化（例如使用 堆栈引擎 在执行 PUSH / POP 指令）。

但无论如何，总的来说， 堆栈帧分配的成本确实比调用一个操作自由存储区的分配函数的成本要低得多（除非它被完全优化掉） ，它本身可以有数百个（如果不是数百万个） :-) 维护堆栈指针和其他状态的操作。分配功能通常基于托管环境提供的 API（例如操作系统提供的运行时）。与为函数调用保存自动对象的目的不同，这种分配是通用的，因此它们不会像堆栈那样具有框架结构。传统上，它们从称为 堆（或多个堆）的池存储中分配空间。与“栈”不同，这里的“堆”概念并不表示所使用的数据结构； 它源自几十年前的早期语言实现。 （顺便说一句，调用堆栈通常由程序/线程启动中的环境从堆中分配固定或用户指定的大小。）用例的性质使得从堆中分配和释放要复杂得多（比推送/弹出堆栈帧），并且几乎不可能通过硬件直接优化。

对内存访问的影响

通常的堆栈分配总是将新帧放在顶部，因此它具有相当好的局部性。这对缓存很友好。 OTOH，在免费存储中随机分配的内存没有这样的属性。从 ISO C++17 开始，有 <memory_resource> 提供的池资源模板。这种接口的直接目的是允许连续分配的结果在内存中靠近在一起。这承认了这样一个事实，即这种策略通常有利于当代实现的性能，例如对现代架构中的缓存友好。不过，这是关于 访问 而不是 分配 的性能。

并发

对内存的并发访问的预期在堆栈和堆之间可能会产生不同的影响。在典型的 C++ 实现中，调用堆栈通常由一个执行线程独占。 OTOH，堆通常在进程中的线程之间 _共享_。对于这样的堆，分配和释放功能必须保护共享的内部管理数据结构免受数据竞争的影响。因此，由于内部同步操作，堆分配和释放可能会产生额外的开销。

空间效率

由于用例和内部数据结构的性质，堆可能会受到内部 内存碎片 的影响，而堆栈则不会。这对内存分配的性能没有直接影响，但是在具有 虚拟内存 的系统中，低空间效率可能会降低内存访问的整体性能。当 HDD 用作物理内存的交换时，这尤其糟糕。它可能会导致相当长的延迟——有时是数十亿个周期。

堆栈分配的限制

尽管实际上堆栈分配在性能上通常优于堆分配，但这并不意味着堆栈分配总是可以代替堆分配。

首先，无法使用 ISO C++ 以可移植的方式在运行时指定大小的堆栈上分配空间。 alloca 和 G++ 的 VLA（可变长度数组）等实现提供了扩展，但有理由避免使用它们。 （IIRC，Linux 源代码最近删除了 VLA 的使用。）（另请注意 ISO C99 确实有强制 VLA，但 ISO C11 将支持变为可选。）

其次，没有可靠且可移植的方法来检测堆栈空间耗尽。这通常称为堆栈溢出（嗯，本网站的词源） ，但更准确地说，可能是 _堆栈溢出_。实际上，这通常会导致无效的内存访问，然后程序的状态就会被破坏（……或者更糟糕的是，一个安全漏洞）。事实上，ISO C++ 没有“堆栈”的概念，并且 在资源耗尽时使其行为未定义。请注意应该为自动对象留出多少空间。

如果堆栈空间用完，则堆栈中分配的对象过多，这可能是由于函数的主动调用过多或自动对象使用不当造成的。这种情况可能表明存在错误，例如没有正确退出条件的递归函数调用。

然而，有时需要深度递归调用。在需要支持未绑定活动调用的语言实现中（其中调用深度仅受总内存限制）， 不可能 像典型的 C++ 实现那样直接使用（当代）本机调用堆栈作为目标语言激活记录。为了解决这个问题，需要构建激活记录的替代方法。例如， SML/NJ 在堆上显式分配帧并使用 仙人掌堆栈。这种激活记录帧的复杂分配通常不如调用堆栈帧快。但是，如果在保证 适当的尾递归 的情况下进一步实现此类语言，则对象语言中的直接堆栈分配（即语言中的“对象”不存储为引用，而是存储为原生原始值）一对一映射到非共享的 C++ 对象）更复杂，通常会带来更多的性能损失。在使用 C++ 实现此类语言时，很难估计性能影响。

原文由 FrankHB 发布，翻译遵循 CC BY-SA 4.0 许可协议