C中静态内存分配与动态存储分配的成本

Question

当您知道C中对象/项的确切数量时，我很想知道内存分配静态与动态的首选方法是什么对性能（例如，运行时间）有好处Linux。少量对象（少量内存）和大量对象（大量内存）的成本。

例如，类型A【N】vs类型*A=malloc（sizeof（type）*N）

请让我知道。非常感谢。

注意：我们可以对此进行基准测试，并可能知道答案。但我想知道解释这两种分配方法之间性能差异的概念。

Answer 1

全局内存通常是在程序（或共享模块/dll）加载并预先填充其初始值时分配的。这通常有自己的内存部分。

堆栈是在创建新线程时由内核分配的内存块（一系列内存页）。在堆栈上分配堆栈内存通常是通过减少堆栈指针来完成的（一条机器指令-（堆栈a通常完全描述-较新的分配具有较低的地址）。删除堆栈对象时，堆栈指针将递增）。因此，堆栈具有严格的先进先出语义。堆栈的大小也是固定的，所以当用完时会出现堆栈溢出。

当使用malloc（在C中）或new（在C中）时，内存在堆/空闲存储上分配。这是任意数量的内存块。当需要比已经分配的内存更多的内存时，malloc会向内核请求更多的内存。通常，malloc将使用已经从系统获得的释放内存。

必须假设对malloc的调用很慢，并且对于任何性能关键或实时例程都应该避免调用。这有两个原因。

1. 堆需要以任何顺序分配和释放任何大小的内存。以前的算法用于遍历已释放块的列表，直到找到合适大小的块。由于内存可能高度碎片化，这可能会很慢。如果堆用于多个线程，则需要提供某种类型的锁定。为了改善这种情况，已经进行了大量的研究，现代堆jemalloc和tcmalloc确实改善了情况。然而，不要指望这一点

因此，如果需要执行任何性能关键型处理，请预先分配所有内存，然后重用已分配的内存。总是假设对malloc和free的调用会很慢。

Answer 2

真正的静态分配（全局变量和标记为静态的局部变量）被粘贴到节中，并使用mmap在加载时（execve）与节的其余部分一起加载。它们基本上是免费的，已经包含在加载程序的成本中。

静态大小已知的自动数组可以与其他局部变量粘合在一起，并通过调整堆栈指针进行分配。在现代处理器上，这本质上是一个整数减法（堆栈向下增长）或接近1ns的值。

可变长度数组不能粘在其他变量上，因此每个数组的成本约为1 ns。

我尝试在一个单线程进程中测量不同大小的malloc，我得到了这个结果，这意味着无malloc对的分配成本大约是堆栈变量的50-100倍

不过，这些只是获取指针的成本。实际访问可能会导致页面错误，从而进一步增加内存块的成本。页面错误在堆栈分配中应该非常罕见，但在首次访问动态分配的内存时可能会出现。

此外，许多小的动态分配会对缓存造成很大的压力，因为您的内存将被碎片化。（您可以通过使用内存池（您自己的或作为glibc的一部分提供的obstack功能）来减少此碎片。）

Answer 3

静态分配会快得多。静态分配可以发生在全局范围内，也可以发生在堆栈上。

在全局范围内，静态分配的内存内置在二进制映像中。这是所需内存的总大小，它在运行的二进制文件中的位置是在编译时计算的。然后当程序加载时，操作系统加载器将为所有全局静态数组分配足够的内存。我很确定它在所有分配的恒定时间内发生。（例如，更多的分配不会花费更多的时间）

在本地范围中，静态分配是在堆栈上分配的。这只需要在堆栈上保留固定数量的字节，并且每次分配的时间不变。堆栈空间非常有限。

动态内存必须从堆中分配，即使在最好的情况下，大多数分配也会花费时间，这些时间会随着每次分配而扩展，如n log n time或其他。

实际上，动态分配比静态分配慢很多倍。

@更新：正如下面的评论所指出的：堆栈分配在技术上不是静态分配（但它们是使用OP问题中使用的语法形式的分配）。

此外，当谈到“分配时间”时，我正在考虑管理内存的总时间（alloc和free）。

在某些动态分配器中，分配时间比释放时间快。

一些快速分配器确实以内存效率换取分配速度。在这些情况下，static仍然“更好”，因为在分配精确大小的块时，static和stack alloc分别是无时间和恒定时间。

要快速使用的动态分配器要权衡显著的内存效率（例如，伙伴分配器将取整到两个大小块的下一次幂，如33k alloc将使用64k）