内存管理算法优化及在游戏引擎中的实现
An Optimized Memory Manager and Application to Game Engine
( 1.上海大学通信与信息工程学院2.西安电子科技大学电子工程学院) 周政春1 吴楷2 万旺根1
Zhou,Zhengchun Wu,Kai Wan,Wanggen
摘要: 本文对C++动态内存管理算法进行了描述, 对其中可能存在的问题进行了探讨并提出了解决方法。通过对原来内存管
理链表的结构改进, 提出了新的双向链式哈希结构并应用于插入式调试内存管理器来跟踪所有动态分配的内存。此内存管
理器的特点在于搜索速度快, 内存管理全面, 接口是无缝的。该内存管理器算法在我们一个最新研发的一款游戏引擎中进
行了应用并通过了测试, 获得了良好的效果。
关键词: 内存管理; 双向哈希链表; 游戏引擎
中图分类号: TP 311.52 文献标识码: A
Abstr act:This paper presents the theory and technology of dynamic memory management. And the potential problems are studied and
solved. Secondly, by means of modifying original structure of memory manage linked list, a new double- linked hash table structure is
proposed and applied to our new drop- in debug memory manager to track memory allocation. It features in fast sought, comprehensive
memory management and seamless interfaces. This manager algorithm is applied and tested in our newly- designed game engine
with good quality and system performance.
Key words: memory manage; double- linked hash table; game engine
文章编号:1008- 0570(2006)05- 3- 0212- 03
随着游戏编程变得越来越复杂, 游戏的最低内存
需求变得越来越高。为支持图形、音乐、视频、动画等,
需要大量的资源, 而当前的游戏必须高效的处理这些
资源。现在软件技术要使用大量的内存, 所以编程人
员要用可靠的技术, 来管理内存空间, 并指导程序优
化的使用内存。随着项目不断增大, 发生内存泄漏、超
越内存边界以及分配过多内存的可能性也将越来越
大, 良好的内存管理算法显得非常重要。
1 内存管理概述
在C++中, 我们用malloc/free 和new 和delete 来
申请动态内存和释放内存。前者是C/C++语言的标准
库函数, 后者是C++的运算符。
内存管理器的核心思想就是, 对于标准运算符new/
delete 进行重载, 并使用#define 来创建一些宏, 这些宏
可以插入到我们自己的工程中去。内存管理器目的是通
过报告内存泄漏、跟踪分配的内存被使用的比例, 提醒
程序员不要边界违例, 来确保内存被合理的使用。
2 传统内存管理算法分析
传统的内存管理主要使用链表来存储于内存分
配情况相关的信息。
分配内存块时, 顺序记录内存分配的相关信息到
链表中去, 然后更新链表。删除内存块时, 同样也必须
搜索整个链表删去相关节点。顺序搜索在最坏情况下
要搜索整个链表, 而一般情况下的搜索节点数接近链
表总节点数的一半。定义: t1 为搜索一个节点平均的时
间耗费, l 为已分配内存链表的长度。为了使分析结果
更具有可比性和一般性, 采用遍历的节点数来表示时
间, 而不是真实的时间。
结果如下:
t1=l/2 ( 1)
从( 1) 式可以看出, 平均耗费依赖于链表的长度,
也就是l。这种方法在普通的程序中也许可以使用。但
是, 在游戏编程这种需要大量耗费内存, 不停地申请
和释放内存的应用程序中, 这种方法显然是部合理
的。由此可以看出, 传统的算法中, 分配和释放与链表
的长度成正比。由于释放和分配的引用一般成对使
用, 因此降低释放内存的耗费是关键。
3 内存管理器的实现与算法改进
3.1 设计原理
通过设立一个双向的Hash 表( struct HashNode)
来保存所有被分配的动态内存块的信息。链表中的每
个节点对应一个动态内存块, 节点中的信息包括内存
块的实际大小、申请分配的大小、实际地址、申请分配
地址、内存分配代码所在的文件、行号、豁余量、分配
类型等等。我将每一个分配的内存块插入到Hash 表
中, 释放时, 在从表中删除。链表节点结构定义如下:
Struct HashNode
{size_t actualsize; /* 实际大小*/
周政春: 硕士研究生
基金资助: 上海市科委重大攻关项目( 045115014) ; 上
海市重点学科建设项目( T0102)
-212-
邮局订阅号: 82-946 360 元/ 年
技
术
创
新
软件时空
《PLC 技术应用200 例》
您的论文得到两院院士关注
size_t requiredsize; /* 申请分配的大小*/
void *actualaddress; /* 实际地址*/
void *requiredaddress; /* 申请分配地址*/
⋯⋯}
通过内存管理器分配的内存结构可知, 返回给用户
的指针ptr 指向的是用户申请内存区域的起始位置。链
表节点, 前后检测区域均为内部使用, 用户是不可见的。
3.2 算法的改进
基于游戏引擎的特殊性, 如申请和释放内存十分
频繁。若采用传统的算法则肯定会降低系统的效率。
加之游戏是很讲究实时性的东西对于时间的要求自
然要比普通的程序来得高。为了解决上面所提到的链
表式的内存管理所带来的问题。我采用一种新的双向
链式哈希表数据结构, 并使用一个巧妙的方法来获取
哈希函数。
由于内存分配的地址是随机的, 经实验发现一个
32 位的地址的低40 位是随机变化概率最高的, 产生冲
突的概率也随之减小。于是我开辟了一个地址空间大
小为1024 的哈希表。把内存分配的地址与( 1024- 1) 相
与, 来获得哈希地址, 易知其值肯定在0～1024 之间。这
个哈希函数的特点在于, 构造简单方便, 利用了计算机
原有的特性从而简单了解决了地址冲突的问题。
函数原型如下:
int getHashIndex( void *address )
{return((unsignedint)address>>4)&(HASH_SIZE-1);}
当然, 我们知道一个游戏的内存分配可能远远超
过1024 个, 于是地址冲突又成了一个不可避免的问
题。为了解决这个问题, 采用双向链式哈希表, 其结构
如图1 所示。
图1 双向链式哈希表结构
Fig.1 configuration of double listed hash table
由于用链地址解决冲突构造的哈希表是个动态
结构, 故更适合在造表之前无法确定记录个数的情
况。对其进行性能分析可知, 链地址法的平均查找长
度在等概率的情况下为:
ASL=1- α
2
(2)
由上可知, 哈希表的平均查找长度不是记录数l
的函数, 而是装填系数α的函数。因此在设计哈希表
时, 可以选择α以控制其平均查找长度。α越小, 空间
冗余度越大, 产生冲突的机会就少; 但是α过小, 空间
浪费会过多。经过试验, 装填系数选择0.7, 比较符合
实际应用。
4 C++的具体实现
首先, 需要创建重载的new和delete 运算符。正如
前面指出的, 我们将记录请求内存分配的代码的文件
和行号。重载这些运算符的方式如下( 数组重载方式
类似) :
inline void*operator new(size_t,const char *file,int line);
inline void operator delete(void* address);
需要注意的是, 为确保正确运行, 必须对运算符
new和delete 的标准版本和数组版本都进行重载。虽然
这些声名不复杂, 但是我们现在需要解决的问题是: 让
所有将使用内存管理器的程序都无缝的将额外的参数
传递给new运算符。为此, 可以使用编译指令#define。
#define new new(__FILE__ , __LINE__)
#define delete predele (__FILE__ , __LINE__) ,
false ? predele( “”, 0) : delete
#define new 语句将把所有的new 调用替换为新
的new, 后者接收的参数并非仅仅是需要分配的内存
量, 还包括了文件和行号, 以便跟踪内存的分配情况。
宏#define delete 与#define new 基本相同。在不引起
语法问题的情况下, 无法将额外的参数传递给delete
运算符, 因此我们巧用“? : ”运算符来使得在调用
delete 之前先调用predele 函数来记录文件名和行号。
另外, 很重要的一点是, 应有条件的创建这些宏, 以避
免多行宏中常见的问题。最后, 出于完整性的考虑我
们还必须使用自己的方法来替换malloc ()、calloc()、
realloc()、free()等。
至此, 我们还需要一个类用来管理我们的内存管
理器, 即以后所有对内存的操作必须通过这个类的对
象进行调用。其中包括内存的分配和释放, 哈希表的插
入和删除等。下面的代码中仅列出了与此相关的成员:
class memorycontrol
{ // Hash 表操作部分
void insertMemoryNode ( MemoryNode *node );
// 向hash 表中插入一内存节点.
MemoryNode *removeMemoryNode(void *address );
// 内存的分配与删除
void deallocateMemory( MemoryNode *node );}
接下来就是该如何去分配内存了, 考虑到版面限
制, 这里仅给出allocatememory()的伪代码。
void *allocatememory ( const char *file, int line,
size_t size, ALLOC_TYPE type, void *address )
{//检查memorycontrol 是否已经被初试化;
//检查是否为0 分配, 若是0 分配的话当作1 分
配来看;
//判断分配类型, 若是realloc 分配, 则从hash 表
中删除这个节点并重新用realloc 命令来分配;
//若为其他类型的分配, 则建立一个内存节点;
//记录一些必要的信息报告, 分配内存并初始化;
//把节点插入hash 表, 返回内存分配地址; }
最后, 我们要解决的问题是: 确保内存管理器是
- 213 -
技
术
创
新
中文核心期刊《微计算机信息》( 管控一体化)2006 年第22 卷第5-3 期
360元/ 年邮局订阅号: 82-946 《现场总线技术应用200 例》
软件时空
第一个被创建的对象, 同时也是最后一个被释放的对
象。为解决这个问题, 需要做一下改进: 首先, 通过在
内存管理器的头文件中创建InitMemoryControl 对象,
确保它在任何静态对象声名之前被创建。Microsoft 指
出, 静态对象被创建的顺序与出现的顺序相同, 而被
释放的顺序则与此相反。其次, 为确保内存管理器始
终可用, 我们将在allocatememory()和deallocatememory
()中调用Initializememory(), 从而保证内存管理器出于
活动状态。最后, 为确保内存管理器是最后一个被释
放的对象, 我们将使用atexit()方法。因此, 必须对内存
管理器作出的唯一限制是, 它必须是第一个调用::exit
函数的方法。
5 实际应用
Shugine 游戏引擎是我们自主研发的一个游戏引
擎, 由于游戏开发资源量庞大。在游戏中需要不停的
分配内存空间, 这样对于内存的合理分配和回收就成
了我们必须考虑的一个重要问题。内存泄漏所引发的
一切意料之外的事件都会给玩家带来意想不到的后
果, 甚至将失去玩家。在这个庞大的工程中, 加入这个
内存管理器, 来跟踪我们分配出去的每一块内存, 在
游戏最后退出时, 打印出内存的分配情况以及未释放
的内存。整个内存管理器在引擎的编写中起到了重要
的作用, 并且收到了良好的效果。图2 是内存管理器
应用于游戏引擎的打印报告的统计部分, 其中详细列
出了内存的分配情况。
图2 部分内存管理报告
Fig.2 part of the memory management report
同样内存管理器也有缺点, 管理器分配、释放以
及查询内存以获得统计信息需要占用额外的时间。虽
然, 我们已经在算法上做了改进, 但是, 在最后创建游
戏时, 我们将不会启用该选项。为了消除这一缺陷, 我
们只在调试时或符号MEMORY_CONTROL_ON 被定
义时, 才启用内存管理器。
6 结语
这个内存管理器提供了一下功能及特点:
1 无缝的接口, 即代码可以嵌入任何的工程中。
2 跟踪所有的内存分配及释放。
3 统计并报告内存分配情况与内存泄漏和越界操
作。
4 用户自定义选项, 以便定制自己的内存管理器。
由于其改进了释放和搜索算法, 使得内存管理器
在游戏引擎编写中的效率得到了大幅的提高, 并且其
无缝的接口以及个性化的定制选项, 为代码的重用创
造了良好的条件。我们在游戏引擎的开发过程中, 由于
使用了内存管理, 也使得整个工程在推进的过程中避
免了不少内存泄漏的问题。并且这个内存管理器可用
于任何软件工程中, 可作为是程序员的必备工具之一。
参考文献：
[1]Microsoft Developer Network Library, http://msdn.microsoft.com/
library/devprods/vs6/visualc/vccore/
core_memory_management_with_mfc.3a_.overview.htm
[2]沈被娜,刘祖照.计算机软件基础（第三版）[M].北京.清华大学
出版社.2000.89- 90
[3]杨雷,吴珏,陈汶滨.实时系统中动静结合的内存管理实现[J].微
计算机信息,2005,10- 2:15- 16
[4]McConnell,Steve,Code Complete [M],Microsoft Press.1993.
[5]MicrosoftDeveloperNetworkLibrary,http://msdn.microsoft.com/library/
devprods/vs6/visualc/vclang/_pluslang_initializing_static_objects.htm
[6]CHANG J M,GEHRINGGER E.A high - performance memory
allocator for obiected - oriented system [J].IEEE Transactions on
Computers,1996,45(3):357- 366.
作者简介: 周政春( 1983.2～) , 男, 浙江余姚人, 硕士研究
生。专业: 通信与信息系统。主要研究方向: 互动数字媒
体, 多媒体信号处理,E- mail: zhouzhengchun@163.
com。万旺根( 1961.6～) , 男, 江西南昌人, 教授、博士生
导师, 博士学位。专业: 信号与信息处理。主要研究领
域: 互动数字媒体, 多媒体信号处理。
Author br ief introduction:Zhou,Zhengchun,was born in
Shanghai,China,on Feb 8,1983.He received the B.S.from
Shanghai University,China,in 2004.His research interests include
interactive digital media,multi- media signal processing.
通讯地址:
( 200072 上海市闸北区延长路149 号上海大学行健
楼1202 室) 周政春
(投稿日期:2005.9.23) (修稿日期:2005.10.28)
更正说明
本文发表在2005 年10 月第3 期" 基于IP 技术的
端对端通信网络安全模型分析设计"的作者林永和，将
文章正确信息更正如下：
1、第一页第三行"（湖南国防科技大学）林永和"应
该为"（广东警官学院）林永和"；
2、第一页倒数第二行"林永和：副教授"应改为"林
永和：讲师"；
3、第二页第二栏第十八行" 作者简介：林永和
（1966- ），男，副教授" 应改为" 作者简介：林永和
（1966- ），男，讲师"；
4、第二页第二栏第二十六行"（410073 湖南国防
科技大学五院博士生队）林永和"应改为"（510232 广州
广州市滨江东路500 号广东警官学院教务处）林永和" .
-214-