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

这个问题可能听起来相当简单,但这是我和另一位与我合作的开发人员的辩论。

我正在考虑堆栈分配的东西,而不是分配给他们。 他正在跟我说话,看着我的肩膀,说这是没有必要的,因为他们的表现是一样的。

我始终认为堆栈的增长是一个固定的时间,堆分配的性能取决于堆的当前复杂性,以便分配(找到合适大小的空洞)和解除分配(减少空洞以减少分段)如果我没有弄错的话,许多标准库实现在删除期间需要时间来做这件事)。

这让我觉得这可能是非常依赖编译器的东西。 对于这个项目,我特别使用了一个Metrowerks编译器来实现PPC架构。 洞察这个组合将是最有帮助的,但一般来说,对于GCC和MSVC ++,情况如何? 堆分配不是堆栈分配的高性能吗? 有没有区别? 或者差异如此微小,就变成毫无意义的微观优化。

堆栈分配速度要快得多,因为所有的操作都是移动堆栈指针。 使用内存池,您可以从堆分配中获得可比较的性能,但是稍微增加了一些复杂性和自己的麻烦。

另外,堆栈与堆不仅仅是性能的考虑因素; 它也会告诉你很多事物的预期寿命。

堆栈要快得多。 在大多数情况下,在大多数体系结构中,字面上只使用单个指令,例如在x86上:

sub esp, 0x10 

(这将栈指针向下移动0x10字节,从而“分配”这些字节以供变量使用)。

当然,堆栈的大小是非常非常有限的,因为您会很快发现是否过度使用堆栈分配或尝试递归:-)

而且,没有什么理由可以优化不需要验证的代码的性能,例如性能分析。 “不成熟的优化”往往会导致更多的问题,而不是价值。

我的经验法则是:如果我知道在编译时需要一些数据,并且它的大小在几百个字节之 ,那么我会对它进行堆栈分配。 否则我堆分配它。

老实说,编写一个程序来比较性能是微不足道的:

 #include <ctime> #include <iostream> namespace { class empty { }; // even empty classes take up 1 byte of space, minimum } int main() { std::clock_t start = std::clock(); for (int i = 0; i < 100000; ++i) empty e; std::clock_t duration = std::clock() - start; std::cout << "stack allocation took " << duration << " clock ticks\n"; start = std::clock(); for (int i = 0; i < 100000; ++i) { empty* e = new empty; delete e; }; duration = std::clock() - start; std::cout << "heap allocation took " << duration << " clock ticks\n"; } 

据说愚蠢的一致性是小心灵的大地精 。 显然,优化编译器是许多程序员头脑中的大块头。 这个讨论曾经是答案的底部,但是显然人们不会为这个问题烦恼,所以我把它移到这里来避免提出我已经回答的问题。

一个优化的编译器可能会注意到这个代码什么都不做,可能会优化它。 优化者的工作就是做这样的事情,与优化器作斗争是愚蠢的。

我建议编译这个代码时关闭优化,因为没有好的方法来欺骗当前正在使用的或将来会被使用的优化器。

任何人优化器,然后抱怨打击它应该受到公众的嘲笑。

如果我关心纳秒精度,我不会使用std::clock() 。 如果我想公布结果作为博士论文,我会做一个更大的处理,我可能会比较GCC,Tendra / Ten15,LLVM,Watcom,Borland,Visual C ++,数字火星,ICC和其他编译器。 实际上,堆分配比堆栈分配花费的时间要长数百倍,而且我没有看到任何进一步调查问题的有用信息。

优化器的任务是摆脱我正在测试的代码。 我没有看到任何理由告诉优化器运行,然后试图欺骗优化器不实际优化。 但是如果我看到这样做的价值,我会做以下一项或多项:

  1. 添加一个数据成员为empty ,并在循环中访问该数据成员; 但如果我只从数据成员读取优化器可以做不断折叠和删除循环; 如果我只写过数据成员,优化器可能会跳过循环的最后一次迭代。 另外,问题不是“堆栈分配和数据访问与堆分配和数据访问”。

  2. 声明volatile , 但volatile通常编译不正确 (PDF)。

  3. 取循环内的e地址(也可以把它分配给一个声明为extern的变量,并在另一个文件中定义)。 但即使在这种情况下,编译器可能会注意到 – 至少在堆栈上 – e将始终分配在相同的内存地址,然后像上面(1)中那样进行常量折叠。 我得到了循环的所有迭代,但是对象从来没有真正分配过。

除了显而易见的,这个测试是有缺陷的,因为它测量了分配和释放,原来的问题没有问及释放。 当然,在堆栈上分配的变量会自动在其作用域的末尾解除分配,所以不会调用delete (1)将数字歪曲(堆栈释放包含在关于堆栈分配的数字中,所以测量堆的重新分配是公平的) (2)导致一个相当糟糕的内存泄漏,除非我们保留一个对新指针的引用,并在我们进行了时间测量之后调用delete

在我的机器上,在Windows上使用g ++ 3.4.4,对于小于100000分配的堆栈和堆分配,我得到“0时钟滴答”,即使这样我也得到了“0时钟滴答”的堆栈分配和“15时钟滴答“为堆分配。 当我测量10,000,000个分配时,堆栈分配需要31个时钟滴答并且堆分配需要1562个时钟滴答。


是的,优化编译器可能会删除创建空对象。 如果我理解正确的话,甚至可能会把整个第一个循环取消。 当我碰到迭代到10,000,000堆栈分配花了31时钟滴答和堆分配花了1562时钟滴答。 我认为可以肯定地说,没有告诉g ++优化可执行文件,g ++并没有忽略构造函数。


自从我写这篇文章以来,Stack Overflow的偏好就是从优化构建中发布性能。 一般来说,我认为这是正确的。 不过,我仍然认为,当你实际上不希望代码优化时,要求编译器优化代码是愚蠢的。 这让我觉得和代客泊车额外付费很相似,但拒绝交钥匙。 在这种特殊情况下,我不希望优化器运行。

使用稍微修改的基准测试版(以解决原始程序每次通过循环时都没有在堆栈上分配某些内容的有效性),并且不进行优化就编译,而是链接到发布库(以解决我们的有效问题不想包含链接到调试库引起的任何减速):

 #include <cstdio> #include <chrono> namespace { void on_stack() { int i; } void on_heap() { int* i = new int; delete i; } } int main() { auto begin = std::chrono::system_clock::now(); for (int i = 0; i < 1000000000; ++i) on_stack(); auto end = std::chrono::system_clock::now(); std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count()); begin = std::chrono::system_clock::now(); for (int i = 0; i < 1000000000; ++i) on_heap(); end = std::chrono::system_clock::now(); std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count()); return 0; } 

显示:

 on_stack took 2.070003 seconds on_heap took 57.980081 seconds 

在我的系统上使用命令行cl foo.cc /Od /MT /EHsc

你可能不同意我的方法来获得非优化的构建。 这很好:随意修改基准,就像你想的那样。 当我打开优化,我得到:

 on_stack took 0.000000 seconds on_heap took 51.608723 seconds 

不是因为堆栈分配实际上是瞬时的,而是因为任何半正式的编译器都可以注意到, on_stack没有做任何有用的事情,并且可以被优化掉。 我的Linux笔记本电脑上的GCC也注意到on_heap没有做任何有用的事情,并优化它:

 on_stack took 0.000003 seconds on_heap took 0.000002 seconds 

我在Xbox 360 Xenon处理​​器上学到的一个有趣的事情是Xbox 360 Xenon处理​​器上的堆栈与堆分配,这也可能适用于其他多核系统,在堆上分配会导致临界区进入暂停所有其他内核,以便alloc不冲突。 因此,在一个紧密的循环中,堆栈分配是固定大小的阵列的方式,因为它阻止了摊位。

如果你正在编写多核/多进程,这可能是另一个加速,因为你的堆栈分配只能被运行你的作用域函数的内核看到,而不会影响任何其他核心/ CPU。

您可以为特定大小的对象编写特殊的堆分配器,这是非常高效的。 但是, 一般的堆分配器并不是特别的高性能。

另外我同意TorbjörnGyllebring关于对象的预期寿命。 好点子!

除了堆分配的数量级性能优势之外,对于长时间运行的服务器应用程序,堆栈分配更可取。 即使是最好的托管堆最终也会变得如此分散,以至于应用程序性能下降。

我不认为堆栈分配和堆分配通常是可以互换的。 我也希望两者的表现足以供一般使用。

我强烈建议小项目,哪一个更适合分配的范围。 对于大件物品,堆可能是必要的。

在具有多线程的32位操作系统上,堆栈通常相当有限(尽管一般至少为几个MB),因为需要分割地址空间,迟早一个线程堆栈将会运行到另一个线程堆栈。 在单线程系统(无论如何,Linux glibc单线程),这个限制要少得多,因为堆栈可以增长和增长。

在64位操作系统上有足够的地址空间来使线程堆栈非常大。

通常堆栈分配只包括从堆栈指针寄存器中减去。 这比搜索堆快了很多。

有时堆栈分配需要添加一个虚拟内存页面。 添加一个新的归零内存页面不需要从磁盘读取一个页面,所以通常这比搜索堆栈要快很多(特别是如果堆中的一部分被分页了)。 在罕见的情况下,你可以构造这样一个例子,在已经在RAM中的堆的一部分中恰好有足够的空间,但是为堆栈分配新的页面必须等待其他页面被写出到磁盘。 在这种罕见的情况下,堆速度更快。

我认为一生至关重要,分配的东西是否要以复杂的方式来构建。 例如,在事务驱动建模中,通常必须填写一个事务结构,并将一堆字段传递给操作函数。 以OSCI SystemC TLM-​​2.0标准为例。

在接近调用操作的堆栈上分配这些操作往往会造成巨大的开销,因为这种结构很昂贵。 在堆上分配的好方法是通过池或像“这个模块只需要一个事务对象”这样简单的策略来重用事务对象。

这比在每个操作调用上分配对象要快很多倍。

原因很简单,就是物体的结构昂贵,使用寿命相当长。

我会说:试一试,看看你的情况最好,因为它可以真正取决于你的代码的行为。

堆分配与堆栈分配可能是最大的问题,在一般情况下堆分配是一个无限制的操作,因此在定时是一个问题的时候你不能使用堆分配。

对于时间不是问题的其他应用程序来说,这可能并不重要,但是如果堆分配了很多,这将影响执行速度。 总是尝试使用短暂的堆栈并经常分配内存(例如在循环中),并且尽可能长 – 在应用程序启动过程中进行堆分配。

一个堆栈的容量有限,而一个堆栈没有。 一个进程或线程的典型堆栈大约是8K。 一旦分配完毕,您将无法更改大小。

一个堆栈变量遵循范围规则,而一个堆栈变量则不遵守。 如果你的指令指针超出一个函数,所有与该函数相关的新变量都会消失。

最重要的是,你不能预测整个功能调用链。 所以你的部分只有200字节的分配可能会引起堆栈溢出。 如果你正在编写一个库,而不是一个应用程序,这一点尤其重要。

这不是更快的堆栈分配。 你也赢了很多使用堆栈变量。 他们有更好的参考地点。 最后,取消分配也便宜很多。

堆分配几乎总是和堆分配一样快或者更快,尽管堆分配器当然可以简单地使用基于堆的分配技术。

但是,在处理基于堆栈和基于堆栈的分配(或稍微好一点的,本地分配和外部分配)的整体性能时,会遇到更大的问题。 通常,堆(外部)分配是缓慢的,因为它处理许多不同类型的分配和分配模式。 减少你正在使用的分配器的范围(使其在算法/代码中是本地的)将倾向于在没有任何重大改变的情况下提高性能。 为分配模式添加更好的结构,例如,强制LIFO对分配和取消分配对的排序也可以通过以更简单和更结构化的方式使用分配器来提高分配器的性能。 或者,你可以使用或编写一个分配器来调整你的特定分配模式; 大多数程序经常分配几个不连续的大小,所以基于几个固定(最好是已知)大小的后备缓冲区的堆将表现得非常好。 由于这个原因,Windows使用低碎片堆。

另一方面,如果线程过多,则基于堆栈的32位内存分配也将充满危险。 堆栈需要一个连续的内存范围,所以你拥有的线程越多,它们所需的虚拟地址空间就越大,而不会发生堆栈溢出。 这不会是一个64位的问题(现在),但它肯定会在长时间运行的程序中产生大量线程的破坏。 虚拟地址空间由于碎片而耗尽总是很痛苦。

堆栈分配是一对夫妇指令,而我所知的最快的rtos堆分配器(TLSF)平均使用150个指令。 另外栈分配不需要锁,因为它们使用线程本地存储,这是另一个巨大的性能胜利。 因此堆栈分配的速度可能会快2-3个数量级,具体取决于您的环境是多么多线程。

一般来说,如果你关心性能,堆分配是最后的选择。 一个可行的中间选项可以是一个固定的池分配器,这也是一对夫妇的指令,每个分配的开销很小,所以对于小的固定大小的对象来说是非常好的。 缺点是它仅适用于固定大小的对象,本质上不是线程安全的,并具有块碎片问题。

这样的优化有一个总体的要点。

您得到的优化与程序计数器实际在代码中的时间成正比。

如果你对程序计数器进行采样,你会发现它花费的时间,这通常是在代码的一小部分,而且通常在你无法控制的库例程中。

只有当你发现在堆对象的堆分配中花费很多时间时,堆栈分配它们的速度才会明显加快。

堆栈分配要快得多。

 class Foo { public: Foo(int a) { } } int func() { int a1, a2; std::cin >> a1; std::cin >> a2; Foo f1(a1); __asm push a1; __asm lea ecx, [this]; __asm call Foo::Foo(int); Foo* f2 = new Foo(a2); __asm push sizeof(Foo); __asm call operator new;//there's a lot instruction here(depends on system) __asm push a2; __asm call Foo::Foo(int); delete f2; } 

这将是在这样的asm。 当你在funcf1和指针f2已经被分配在堆栈上(自动存储)。 顺便说一下,Foo f1(a1)对堆栈指针( esp )没有指令作用,如果func想获得成员f1 ,它就被分配了,它的指令是这样的: lea ecx [ebp+f1], call Foo::SomeFunc() 。 堆栈分配的另一件事情可能会让某人认为内存是像FIFO一样的东西,当你进入一些函数时, FIFO就发生了,如果你在函数中,并且像int i = 0那样分配,那么就不会发生推动。

之前已经提到,堆栈分配只是简单地移动堆栈指针,即在大多数架构上的单一指令。 比较一下在堆分配的情况下通常会发生什么。

操作系统将空闲存储器的部分保持为链接列表,有效载荷数据由指向空闲部分的起始地址的指针和空闲部分的大小组成。 为了分配X字节的内存,遍历链表并遍历每个音符,检查其大小是否至少为X.当找到大小为P> = X的部分时,将P分成两部分尺寸X和PX。 链表被更新,并返回指向第一部分的指针。

正如你所看到的,堆的分配取决于可能的因素,比如你请求多少内存,内存是多少碎片等等。

一般来说,堆栈分配比堆分配要快,正如上面几乎所有的答案所提到的。 堆栈推送或弹出是O(1),而从堆中分配或释放可能需要先前的分配。 但是,您通常不应该在紧密的性能密集型循环中进行分配,因此通常会选择其他因素。

做出这种区分可能是件好事:您可以在堆上使用“堆栈分配器”。 严格地说,我认为堆栈分配是指分配的实际方法,而不是分配的位置。 如果你在实际的程序堆栈上分配了很多东西,这可能是由于各种原因造成的。 另一方面,如果可能,使用堆栈方法在堆上分配是您可以为分配方法所做的最佳选择。

既然你提到Metrowerks和PPC,我猜你的意思是Wii。 在这种情况下,内存是非常重要的,尽可能使用堆栈分配方法可以保证您不会浪费内存碎片。 当然,这样做需要比“正常”的堆分配方法更多的关心。 评估每种情况的权衡是明智的。

正如其他人所说,堆栈分配通常要快得多。

但是,如果你的对象拷贝的代价很高,那么当你使用这些对象的时候,如果你不小心的话,在堆栈上分配可能会导致巨大的性能。

例如,如果你在堆栈中分配了一些东西,然后把它放到一个容器中,那么在堆上分配并将指针存储在容器中(例如使用std :: shared_ptr <>)会更好。 如果按价值传递或返回对象,以及其他类似的情况,也是如此。

重点是,尽管在很多情况下堆栈分配通常比堆分配要好,但是有时如果您不太适合计算模型的时候,为了堆栈分配而出问题,那么可能会导致比解决问题更多的问题。

注意在选择堆栈与堆分配时,考虑的通常不是速度和性能。 堆栈就像一个堆栈,这意味着它非常适合于推块,并再次弹出,持续,首先。 程序的执行也是堆栈式的,最后输入的程序首先退出。 在大多数编程语言中,过程中所需的所有变量只能在过程执行期间可见,因此在进入过程时被推入,并在退出或返回时弹出堆栈。

现在举一个堆栈不能使用的例子:

 Proc P { pointer x; Proc S { pointer y; y = allocate_some_data(); x = y; } } 

如果你在程序S中分配了一些内存,并把它放在堆栈上,然后退出S,分配的数据将从堆栈中弹出。 但是P中的变量x也指向这个数据,所以x现在指向堆栈指针下面的某个地方(假定堆栈向下增长),并带有未知内容。 如果堆栈指针只是向上移动而不清除下面的数据,那么内容可能仍然存在,但是如果开始在堆栈上分配新数据,则指针x实际上可能指向新数据。

不要过早地假设其他应用程序代码和用法会影响您的功能。 所以看功能隔离是没有用的。

如果你认真的应用程序,然后VTune它或使用任何类似的分析工具,看看热点。

科坦

我想说的实际上由GCC生成的代码(我记得VS也) 没有开销做堆栈分配

为以下功能说:

  int f(int i) { if (i > 0) { int array[1000]; } } 

以下是代码生成:

  __Z1fi: Leh_func_begin1: pushq %rbp Ltmp0: movq %rsp, %rbp Ltmp1: subq $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited. Ltmp2: movl %edi, -4(%rbp) movl -8(%rbp), %eax addq $3880, %rsp popq %rbp ret Leh_func_end1: 

因此,你有多少局部变量(甚至在内部如果或切换),只是3880将改变为另一个值。 除非你没有局部变量,否则这个指令只需要执行。 所以分配本地变量没有开销。