为什么堆MUCH上的内存分配比堆栈上慢?

问题描述 投票:45回答:4

我已经被告知很多次了。但是我不知道为什么...从堆分配内存时会涉及哪些额外费用?与硬件相关吗?它与CPU周期有关吗?这么多的猜测,但没有确切的答案...有人可以给我一些阐述吗?

就像“展开”所述,Heap数据结构比Stack更复杂。在我看来,当线程开始运行时,会将一些内存空间分配给该线程作为其堆栈,而进程中的所有线程都将共享堆。此范例需要一些额外的机制来管理每个线程对共享堆的使用,例如垃圾回收。我对吗?

c memory-management stack
4个回答
52
投票

因为堆是比堆栈要复杂得多的数据结构。

对于许多体系结构,在堆栈上分配内存只是更改堆栈指针的问题,即它是一条指令。在堆上分配内存涉及寻找足够大的块,对其进行拆分,以及管理“簿记”,该簿记允许诸如free()之类的内容以不同的顺序进行。

当范围(通常是函数)退出时,保证分配在堆栈上的内存将被释放,并且不可能只释放其中的一部分。


25
投票

[在您重新陈述展开答案的编辑中,您提到了“堆数据结构”。要非常小心,因为称为heap的数据结构与动态内存分配没有关系。很清楚,我将使用免费商店的更多语言律师术语。

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

相反,免费商店要复杂得多。我什至不打算开始讨论垃圾收集系统,因为那是一个完全不同的话题,这个问题是关于C语言的。通常,免费存储区中的分配和解除分配涉及几种不同的数据结构,例如空闲列表或块池。这些数据结构和簿记也需要内存,因此浪费了空间。此外,簿记记录经常与分配混合,从而损害了其他分配的数据局部性。从免费存储区中进行分配可能会涉及从底层操作系统请求更多的进程内存,通常是从某种形式的平板分配器中获取。]为了进行简单比较,并使用jemalloc-2.2.5和sloccount中的数字作为参考,jemalloc实现包含超过8800行C语言的源代码和另外700行以上的测试代码。这应该使您很好地了解免费存储分配和堆栈分配之间的复杂性差异:数千行C代码与一条指令。

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

    碎片会损害数据局部性。
  • 碎片浪费内存。
  • 碎片使得为大型分配寻找可用空间的工作更加困难。
  • [在现代系统上,与免费商店相比,堆栈通常相对较小,因此最终,免费商店正在管理更多空间,从而解决了更棘手的问题。而且,由于堆栈大小的限制,免费存储区通常用于较大的分配,必须同时处理非常大和非常小的分配之间的这种差异也使得免费存储区的工作也变得更加困难。通常,堆栈分配很小,只有几千字节或更小的数量级,并且堆栈的总大小仅为几兆字节。通常在程序中为免费存储提供

    整个过程空间的其余部分

  • 。在现代机器上,这可能是数百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实现的描述的附加链接:
  • 堆栈和堆之间的主要区别在于,堆栈中的项目不能无序删除。如果将项目A,B,C添加到堆栈中,则必须先删除C才能删除B。这意味着将新项目添加到堆栈中始终意味着将其添加到堆栈的

    end中,这是非常简单的操作。您只需移动指向堆栈末尾的指针即可。另一方面,您

    可以

    乱序删除项目。并且只要您随后不将其他项目移动到内存中(就像一些垃圾回收堆一样),您的堆就会在中间有“空洞”。即如果将A,B,C添加到堆中并删除B,则堆在内存中的外观如下:A _ C其中_是一块未使用的(空闲)内存。如果现在添加一个新的项目D,则分配器必须找到一个足够大的连续可用空间以容纳D。根据内存中有多少个连续可用空间,这可能是一项昂贵的操作。而且,它几乎总是比仅移动堆栈的“最后一个元素”指针更为昂贵。
    在堆栈区域上创建数据:只需移动堆栈指针在头部区域创建数据:在满足给定要求的内存池中搜索区域(可以使用“最适合”,“最适合”或“最不适合”)。找到该区域后,存储信息(记账)

    删除堆栈:删除堆栈很容易。只需向下移动堆栈指针在堆区域上删除:查找元素在堆上的存储位置(使用簿记),并在必要时合并两个相邻的空闲块;


13
投票
堆栈和堆之间的主要区别在于,堆栈中的项目不能无序删除。如果将项目A,B,C添加到堆栈中,则必须先删除C才能删除B。这意味着将新项目添加到堆栈中始终意味着将其添加到堆栈的

end中,这是非常简单的操作。您只需移动指向堆栈末尾的指针即可。另一方面,您

可以


1
投票
在堆栈区域上创建数据:只需移动堆栈指针在头部区域创建数据:在满足给定要求的内存池中搜索区域(可以使用“最适合”,“最适合”或“最不适合”)。找到该区域后,存储信息(记账)

删除堆栈:删除堆栈很容易。只需向下移动堆栈指针在堆区域上删除:查找元素在堆上的存储位置(使用簿记),并在必要时合并两个相邻的空闲块;

© www.soinside.com 2019 - 2024. All rights reserved.