静态内存分配的成本与C中的动态内存分配
sam*_*asa 16 c linux memory memory-management
我很有兴趣知道什么是内存分配的首选方法static vs dynamic是良好的性能(例如,运行时间),当你知道的对象/项目的确切数量C上Linux.少量对象(少量内存)以及大量对象(大量内存)的成本.
e.g., type A[N] VS type *A = malloc(sizeof(type) * N)
请告诉我.谢谢.
注意:我们可以对此进行基准测试,并可能知道答案.但我想知道解释这两种分配方法之间性能差异的概念.
Raf*_*sta 14
静态分配会快得多.静态分配可以在全局范围内发生,也可以在堆栈上发生.
在全局范围内,静态分配的内存内置于二进制映像中.这是所需内存的总大小,以及它在运行二进制文件中的位置是在编译时计算的.然后当程序加载时,操作系统加载器将为所有全局静态数组分配足够的内存.我很确定它会在所有分配的恒定时间内发生.(例如,更多的分配不会花费更多的时间)
在本地范围中,静态分配在堆栈上分配.这涉及简单地在堆栈上保留固定数量的字节,并且在每个分配的恒定时间内发生.堆栈空间非常有限.
动态内存必须从堆中分配,即使在最好的情况下,大多数分配也需要花费时间,每次分配的时间超过线性,比如n log n time或者其他东西.
实际上,动态分配比静态分配慢很多倍.
@update:正如下面的评论中所指出的:堆栈分配在技术上不是静态分配(但它们是OP的问题中使用的语法形式的分配).
在谈到"分配时间"时,我正在考虑管理内存的总时间(分配和免费).
在一些动态分配器中,分配时间比释放时间快.
一些快速分配器也可以通过内存效率来分配速度.在这些情况下,静态仍然"更好",静态和堆栈分配在分配精确大小的块时分别没有时间和常量时间.
动态分配器可以快速折衷显着的内存效率(例如,伙伴分配器向上舍入到两个大小块的下一个功能,如33k alloc将使用64k)
- 堆内存分配算法的复杂性变化很大.除非有一些聪明的索引数据结构,否则常见算法(如first-fit/best-fit)通常是线性的.二进制伙伴可以是用于分配的恒定时间和用于释放的对数 - 以及基于某些预定义大小的空闲列表的简单隔离存储/ slab分配器(如2的幂) (6认同)
- 虽然堆分配_可能很昂贵(通常释放比分配更昂贵),但堆分配的开销通常被高估.当你打开灯光时,它就是你床下的那些怪物之一.在对一个无锁生产商 - 服务器队列进行基准测试时,我一直很失望,当我预计会出现2-3倍的情况时,这个队列每秒只能提供1800万到2000万.直到我的同事问我:"呃,你确实意识到你每秒也要进行2000万次堆分配吗？"_.现在你每秒可以做20M次的事情并不是很令人担忧. (3认同)
真正的静态分配(全局变量和标记为静态的局部变量)被粘合到部分中,并在加载时(execve)使用时加载部分的其余部分mmap.它们基本上是免费的,已经被加载程序的成本所覆盖.
具有静态已知大小的自动数组可以与其他局部变量粘合在一起,并通过调整堆栈指针进行分配.在现代处理器上,这基本上是一个整数减法(堆栈向下增长)或接近1 ns.
可变长度数组不能粘贴到其他变量上,因此它们每个成本约为1 ns.
我尝试malloc在单线程过程中测量不同大小的s,我得到了这个,这意味着对于分配<16MiB的堆栈变量,malloc+free对的成本约为50-100倍.之后,它上升(32MiB和64MiB的成本约为分配<= 16MiB的一百倍):
这些只是获取指针的成本.实际访问可能导致页面错误,从而进一步增加了内存块的成本.堆栈分配时页面错误应该非常少见,但可能首次访问动态分配的内存.
此外,许多小的动态分配将对缓存造成相当大的压力,因为您的内存将被分割.(您可以通过使用内存池来减少此碎片,无论是您自己的还是作为glibc的一部分提供的obstack功能.)
通常在程序(或共享模块/ dll)加载并预先填充其初始值时分配全局内存.这通常有自己的内存部分.
堆栈是内核在创建新线程时分配的块(内存页面系列).在堆栈上分配堆栈内存通常是通过递减堆栈指针来完成的(一个机器指令 - (堆栈通常完全下降 - 较新的分配具有较低的地址).当删除堆栈对象时,堆栈指针递增).因此,堆栈具有严格的先到后语义.堆栈也是固定大小的,所以当你用完时会出现堆栈溢出.
当使用malloc(在C中)或new(C++)时,内存在堆/免费存储上分配.这是任何数字内存块.当需要的内存比已经分配的内存多时,malloc会进入内核以从系统请求更多内存.通常malloc将使用已从系统获得的释放内存.
必须假定对malloc的调用很慢,并且应该避免对任何性能关键或实时例程进行调用.这有两个原因.
- 堆需要以任何顺序分配和释放任何大小的内存.较旧的算法用于遍历已释放块的列表,直到找到合适大小的块.由于内存可能高度分散,因此可能会很慢.如果在多个线程上使用堆,则需要提供某种锁定.已经进行了大量研究以改善这种情况,并且现代堆积的jemalloc和tcmalloc确实改善了事物.但是,不要指望这一点.
- 如果无法从堆分配器已管理的内容中分配所需的内存,则堆分配器将需要向内核请求更多内存.(在UNIX上,这是与完成
mmap或sbrk系统调用).内核需要找到一些未分配的内存页面,并且必须将这些页面映射到进程内存空间中.任何形式的缓存都会消失.所以期望这是超级慢(对于计算机).
因此,如果您需要执行任何性能关键处理,请预先分配所有内存,然后重用已分配的内存.总是假设对malloc和free的调用会很慢.