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