浏览量:1,821

内存分配器浅谈

ogre渲染引擎中采用的是nedmalloc内存分配器,查了些资料,看了些论文,这里对ogre中使用的nedmalloc内存分配器进行简单的介绍。第1小节,介绍的是好的内存处理器的目标,第2小节,介绍dlmalloc分配器的基本思想,第3小节,介绍nedmalloc的性能。

一. 简介

参考【2】,作者总结了1995年以前的内存分配器,对内存分配器的目的、需要解决的问题、采用的策略等都进行了总结。其中要解决的一个很重要的问题就是碎片化(fragmentation),因为应用程序可以在任意时间,分配任意大小的对象,并在将来的某个时间释放这些内存,就可能导致一个结果就是:在两个使用的内存块之间存在非常小的空闲块,无法满足所要求的内存申请要求,也已经证实碎片化问题是无法避免。对碎片问题的研究在【2】都有详细的表述。

一个内存分配器主要的目的可以总结为如下几点:

(1)最大化兼容性

与其它程序兼容,特别是它应该遵守ANSI/POSIX规范

(2)最大化可移植性

尽可能少的依赖系统相关的特征(比如系统调用),同时在某些系统上也要提供一些有用特征的可选操作。遵守系统对字节对齐规则和取址规则的约束。

(3)最小化时间

malloc()、free()和realloc()消耗的时间尽可能的少

(4)最大化可调性

一些可选的方法可以由用户来控制。有静态的(编译时)方法,使用(#define定义一些宏);有动态的(运行时)方法,使用命令来控制。

(5)最大化局部性

尽可能的分配物理内存相互接近的内存块,在程序执行时有利于最小化页面和cache的丢失。

(6)最大化错误检测

通用目的分配器也作为通用目的的内存错误检测工具,显得不太可能,但是分配器应该提供一些由于重写内存、多次释放等原因造成的内存崩溃。

(7)最小化异常

一个使用默认配置的分配器在不同的应用背景下,应该尽可能少的出现异常,比如在窗口工具包里、GUI应用中、编译器中、网络浏览器中等等。

一个内存分配器应当能记录使用的和空闲的内存,在合适的时间范围内最小化存储空间的浪费,即要做到时间开销和空间浪费之间的一个平衡。

二. dlmalloc算法基本思想

这里以dlmalloc内存分配器为例,参考【1】【3】,这里介绍它的算法基本思想。

2.1 边界标签

2013-12-29 14-24-10

图1. 边界标签

在内存块的前面和后面都有大小信息,这能带来两个好处:

(1)       两个相邻的空闲块能够合并成一个大的内存块

(2)       所有的内存块既能向前遍历,也能向后遍历。

2.2 装箱方法

2013-12-29 14-24-23

图2. 装箱方法

内存块均以箱子的形式来维护,以箱子的大小来分组,有128个固定大小的箱子类型,小于512个字节的箱子之间的间隔大小是8个字节。对块的搜索采用最小优先、最佳优先的准则,以便减小碎片化的效果。在1995年以前的版本中,箱子中的块都没有进行排序,所以最佳优先的策略仅仅是一种估计。最近的实现版本中,箱子里的块不采用按大小排序,而是采用了最老优先的准则。

所以把这类算法的归类为“带合并的最佳优先算法”,相邻的空闲块合并为一个更大的空闲块,通过大小排序,把它保存在对应的箱子中。

通过边界标签完成合并和通过装箱方法完成最佳优先匹配,就是内存分配算法的主要思想。在此基础上完成一些启发式的改进,这些改进也是在实现中必需考虑到的一些因素,包括局部性的维护(Locality Preservation)、拓展块的维护(Wilderness Preservation)、内存映射(Memory Mapping)和高速缓存(Cache)。

【1】对上面提到的启发式的改进进行了更加详细的介绍;【3】实现了算法,提供了dlmalloc实现的细节。

三.  nedmalloc内存分配器

nedmalloc基于dlmalloc,支持win32平台和POSIX平台上,是一个高性能的、支持多线程的、少碎片化的动态内存分配器,它遵守Boost软件协议,允许商业应用。在旧版本的操作系统下(比如Windows XP,Linux 2.4系列,FreeBSD 6系列,Mac OS X 10.4系列或者更早期的系统),nedmalloc可能很显著的提高应用程序的性能,但是在新版本的操作系统(比如windows 7,Linux 3.x,FreeBSD 8,Mac OS X 10.6等,由于使用了较先进的内存分配器,在真实的测试结果中,第三方内存分配器很可能不会显著提高性能)。

nedmalloc在一些配置较高的硬件(CPU多于8核,RAM超过8Gb)上进行了测试,都取得了较好的性能。nedmalloc可以打到现有的二进制程序中,替换系统的内存分配器,例如当把nedmalloc的dll注入到Windows XP上的Microsoft Word软件后,对于大文档的word编辑会显著提高。

它比Windows XP的内存分配器快了125倍,比标准的FreeBSD 6内存分配器快了4-10倍,比ptmalloc2(标准的Linux内存分配器)快了一倍。在一台3400(2.20Ghz)AMD Athlon64机器上,最少能完成7.3m到8.2m个malloc和free对的操作。

【4】,通过基准测试(Packetised benchmark和Memory Mapped benchmark)得到的结果来验证nedmalloc的性能,还将nedmalloc与tcmalloc、Hoard、ptmalloc3、jemalloc进行了对比。

【5】【6】,是Niall Douglas写的,关于用户态内存管理的一些见解。

【1】【3】,介绍的是Doug Lea实现的一个内存分配器;【7】~【12】,介绍了其它更加复杂的内存分配器的实现方法。

【13】~【15】,是查找到的与内存分配器相关的一些资料。

这块内容很多,时间精力有限,不作深入研究了。

四. 参考

【1】       http://g.oswego.edu/dl/html/malloc.html

【2】       Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, “Dynamic Storage Allocation: A Survey and Critical Review” in International Workshop on Memory Management, September 1995

【3】       ftp://g.oswego.edu/pub/misc/malloc.c

【4】       http://www.nedprod.com/programs/portable/nedmalloc/index.html

【5】       Douglas, N, (2011-May), ‘User Mode Memory Page Management: An old idea applied anew to the memory wall problem‘,ArXiv e-prints, vol: 1105.1815.

【6】       Douglas, N, (2011-May), ‘User Mode Memory Page Allocation: A Silver Bullet For Memory Allocation?‘, ArXiv e-prints, vol: 1105.1811.

【7】       Berger, Emery D., et al. “Hoard: A scalable memory allocator for multithreaded applications.” ACM SIGPLAN Notices 35.11 (2000): 117-128.

【8】       Michael, Maged M. “Scalable lock-free dynamic memory allocation.” ACM SIGPLAN Notices. Vol. 39. No. 6. ACM, 2004.

【9】       Hudson, Richard L., et al. “McRT-Malloc: a scalable transactional memory allocator.” Proceedings of the 5th international symposium on Memory management. ACM, 2006.

【10】   Berger, Emery D., Benjamin G. Zorn, and Kathryn S. McKinley. “Composing high-performance memory allocators.” ACM SIGPLAN Notices. Vol. 36. No. 5. ACM, 2001.

【11】   Udayakumaran, Sumesh, and Rajeev Barua. “Compiler-decided dynamic memory allocation for scratch-pad based embedded systems.” Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems. ACM, 2003.

【12】   The Boost C++ ”Pool” library which can be found at http://www.boost.org/doc/libs/release/libs/pool/doc/.

【13】   http://gperftools.googlecode.com/svn/trunk/doc/tcmalloc.html

【14】   http://locklessinc.com/benchmarks_allocator.shtml

【15】   http://lwn.net/Articles/396657/

spacer

Leave a reply