堆:欢乐和痛苦

类别:VC语言 点击:0 评论:0 推荐:
堆:欢乐和痛苦

Murali R. Krishnan
Microsoft Corporation

1999 年 2 月

摘要: 讨论常见的堆性能问题以及如何防范它们。(共 9 页)

前言

您是否是动态分配的 C/C++ 对象忠实且幸运的用户?您是否在模块间的往返通信中频繁地使用了“自动化”?您的程 序是否因堆分配而运行起来很慢?不仅仅您遇到这样的问题。几乎所有项目迟早都会遇到 堆问题。大家都想说,“我的代码真正好,只是堆太慢”。那只是部分正确。更深入理解 堆及其用法、以及会发生什么问题,是很有用的。

什么是堆?

(如果您已经知道什么是堆,可以跳到“什么是常见的堆性能问题?”部分)

在程序中,使用堆来动态分配和释放对象。在下列情况下,调用堆操作: 事先不知道程序所需对象的数量和大小。

对象太大而不适合堆栈分配程序。

堆使用了在运行时分配给代码和堆栈的内存之外的部分内存。下图给出了堆分配程序 的不同层。

GlobalAlloc/GlobalFree:Microsoft Win32 堆调用,这些调用直接与每个进 程的默认堆进行对话。

LocalAlloc/LocalFree:Win32 堆调用(为了与 Microsoft Windows NT 兼容),这些调用直接与每个进程的默认堆进行对话。

COM 的 IMalloc 分配程序(或 CoTaskMemAlloc / CoTaskMemFree):函数使用每个进程的默认堆。自动化程序使用“组件对象模型 (COM)”的分配程序,而申请的程序使用每个进程堆。

C/C++ 运行时 (CRT) 分配程序:提供了 malloc()free() 以及 newdelete 操作符。如 Microsoft Visual Basic 和 Java 等语言也提供了新的 操作符并使用垃圾收集来代替堆。CRT 创建自己的私有堆,驻留在 Win32 堆的顶部。

Windows NT 中,Win32 堆是 Windows NT 运行时分配程序周围的薄层。所有 API 转 发它们的请求给 NTDLL。

Windows NT 运行时分配程序提供 Windows NT 内的核心堆分配程序。它由具有 128 个大小从 8 到 1,024 字节的空闲列表的前端分配程序组成。后端分配程序使用虚拟内存来保留和提交页。

在图表的底部是“虚拟内存分配程序”,操作系统使用它来保留和提交页。所有分配 程序使用虚拟内存进行数据的存取。

分配和释放块不就那么简单吗?为何花费这么长时间?

堆实现的注意事项

传统上,操作系统和运行时库是与堆的实现共存的。在一个进程的开始,操作系统创 建一个默认堆,叫做“进程堆”。如果没有其他堆可使用,则块的分配使用“进程堆”。 语言运行时也能在进程内创建单独的堆。(例如,C 运行时创建它自己的堆。)除这些专用的堆外,应用程序或许多已载入的动态链接库 (DLL) 之一可以创建和使用单独的堆。Win32 提供一整套 API 来创建和使用私有堆。有关堆函数( 英文)的详尽指导,请参见 MSDN。

当应用程序或 DLL 创建私有堆时,这些堆存在于进程空间,并且在进程内是可访问的。从给定堆分配的数据 将在同一个堆上释放。(不能从一个堆分配而在另一个堆释放。)

在所有虚拟内存系统中,堆驻留在操作系统的“虚拟内存管理器”的顶部。语言运行 时堆也驻留在虚拟内存顶部。某些情况下,这些堆是操作系统堆中的层,而语言运行时堆 则通过大块的分配来执行自己的内存管理。不使用操作系统堆,而使用虚拟内存函数更利 于堆的分配和块的使用。

典型的堆实现由前、后端分配程序组成。前端分配程序维持固定大小块的空闲列表。 对于一次分配调用,堆尝试从前端列表找到一个自由块。如果失败,堆被迫从后端(保留 和提交虚拟内存)分配一个大块来满足请求。通用的实现有每块分配的开销,这将耗费执 行周期,也减少了可使用的存储空间。

Knowledge Base 文章 Q10758,“用 calloc() 和 malloc() 管理内存” (搜索文章 编号), 包含了有关这些主题的更多背景知识。另外,有关堆实现和设计的详细讨论也可在下列著 作中找到:“Dynamic Storage Allocation: A Survey and Critical Review”,作者 Paul R. Wilson、Mark S. Johnstone、Michael Neely 和 David Boles;“International Workshop on Memory Management”, 作者 Kinross, Scotland, UK, 1995 年 9 月(http://www.cs.utexas.edu/users/oops/papers.html)(英文)。

Windows NT 的实现(Windows NT 版本 4.0 和更新版本) 使用了 127 个大小从 8 到 1,024 字节的 8 字节对齐块空闲列表和一个“大块”列表。“大块”列表(空闲列表[0]) 保存大于 1,024 字节的块。空闲列表容纳了用双向链表链接在一起的对象。默认情况下,“进程堆”执行 收集操作。(收集是将相邻空闲块合并成一个大块的操作。)收集耗费了额外的周期,但 减少了堆块的内部碎片。

单一全局锁保护堆,防止多线程式的使用。(请参见“Server Performance and Scalability Killers”中的第一个注意事项, George Reilly 所著,在 “MSDN Online Web Workshop”上(站点:http://msdn.mi crosoft.com/workshop/server/iis/tencom.asp(英文)。)单一全局锁本质上是用 来保护堆数据结构,防止跨多线程的随机存取。若堆操作太频繁,单一全局锁会对性能有 不利的影响。

什么是常见的堆性能问题?

以下是您使用堆时会遇到的最常见问题: 分配操作造成的速度减慢。光分配就耗费很长时间。最可能导致运行速度 减慢原因是空闲列表没有块,所以运行时分配程序代码会耗费周期寻找较大的空闲块,或 从后端分配程序分配新块。

释放操作造成的速度减慢。释放操作耗费较多周期,主要是启用了收集操 作。收集期间,每个释放操作“查找”它的相邻块,取出它们并构造成较大块,然后再把 此较大块插入空闲列表。在查找期间,内存可能会随机碰到,从而导致高速缓存不能命中 ,性能降低。

堆竞争造成的速度减慢。当两个或多个线程同时访问数据,而且一个线程 继续进行之前必须等待另一个线程完成时就发生竞争。竞争总是导致麻烦;这也是目前多 处理器系统遇到的最大问题。当大量使用内存块的应用程序或 DLL 以多线程方式运行(或运行于多处理器系统上)时将导致速度减慢。单一锁定的使用— 常用的解决方案—意味着使用堆的所有操作是序列化的。当等待锁定时序列化会引起线程 切换上下文。可以想象交叉路口闪烁的红灯处走走停停导致的速度减慢。

竞争通常会导致线程和进程的上下文切换。上下文切换的开销是很大的,但 开销更大的是数据从处理器高速缓存中丢失,以及后来线程复活时的数据重建。

堆破坏造成的速度减慢。造成堆破坏的原因是应用程序对堆块的不正确使 用。通常情形包括释放已释放的堆块或使用已释放的堆块,以及块的越界重写等明显问题 。(破坏不在本文讨论范围之内。有关内存重写和泄漏等其他细节,请参见 Microsoft Visual C++(R) 调试文档 。)

频繁的分配和重分配造成的速度减慢。这是使用脚本语言时非常普遍的现 象。如字符串被反复分配,随重分配增长和释放。不要这样做,如果可能,尽量分配大字 符串和使用缓冲区。另一种方法就是尽量少用连接操作。

竞争是在分配和释放操作中导致速度减慢的问题。理想情况下,希望使用没有竞争和 快速分配/释放的堆。可惜,现在还没有这样的通用堆,也许将来会有。

在所有的服务器系统中(如 IIS、MSProxy、DatabaseStacks、网络服务器、 Exchange 和其他), 堆锁定实在是个大瓶颈。处理器数越多,竞争就越会恶化。

尽量减少堆的使用

现在您明白使用堆时存在的问题了,难道您不想拥有能解决这些问题的超级魔棒吗? 我可希望有。但没有魔法能使堆运行加快—因此不要期望在产品出货之前的最后一星期能 够大为改观。如果提前规划堆策略,情况将会大大好转。调整使用堆的方法,减少对堆的 操作是提高性能的良方。

如何减少使用堆操作?通过利用数据结构内的位置可减少堆操作的次数。请考虑下列 实例:

struct ObjectA { // objectA 的数据 } struct ObjectB { // objectB 的数据 } // 同时使用 objectA 和 objectB // // 使用指针 // struct ObjectB { struct ObjectA * pObjA; // objectB 的数据 } // // 使用嵌入 // struct ObjectB { struct ObjectA pObjA; // objectB 的数据 } // // 集合 – 在另一对象内使用 objectA 和 objectB // struct ObjectX { struct ObjectA objA; struct ObjectB objB; } 避免使用指针关联两个数据结构。如果使用指针关联两个数据结构,前面 实例中的对象 A 和 B 将被分别分配和释放。这会增加额外开销—我们要避免这种做法。

把带指针的子对象嵌入父对象。当对象中有指针时,则意味着对象中有动 态元素(百分之八十)和没有引用的新位置。嵌入增加了位置从而减少了进一步分配/释 放的需求。这将提高应用程序的性能。

合并小对象形成大对象(聚合)。聚合减少分配和释放的块的数量。如果 有几个开发者,各自开发设计的不同部分,则最终会有许多小对象需要合并。集成的挑战 就是要找到正确的聚合边界。

内联缓冲区能够满足百分之八十的需要(aka 80-20 规则)。个别情况下,需要内存缓冲区来保存字符串/二进制数据,但事先不知道 总字节数。估计并内联一个大小能满足百分之八十需要的缓冲区。对剩余的百分之二十, 可以分配一个新的缓冲区和指向这个缓冲区的指针。这样,就减少分配和释放调用并增加 数据的位置空间,从根本上提高代码的性能。

在块中分配对象(块化)。块化是以组的方式一次分配多个对象的方法。 如果对列表的项连续跟踪,例如对一个 {名称,值} 对的列表,有两种选择:选择一是为每一个“名称-值”对分配一个节点;选择二是分 配一个能容纳(如五个)“名称-值”对的结构。例如,一般情况下,如果存储四对,就 可减少节点的数量,如果需要额外的空间数量,则使用附加的链表指针。

块化是友好的处理器高速缓存,特别是对于 L1-高速缓存,因为它提供了 增加的位置 —不用说对于块分配,很多数据块会在同一个虚拟页中。

正确使用 _amblksiz。C 运行时 (CRT) 有它的自定义前端分配程序,该分 配程序从后端(Win32 堆)分配大小为 _amblksiz 的块。将 _amblksiz 设置为较高的值能潜在地减少对后端的调用次数。这 只对广泛使用 CRT 的程序适用。

使用上述技术将获得的好处会因对象类型、大小及工作量而有所不同。但总能在性能 和可升缩性方面有所收获。另一方面,代码会有点特殊,但如果经过深思熟虑,代码还是 很容易管理的。

其他提高性能的技术

下面是一些提高速度的技术: 使用 Windows

本文地址:http://com.8s8s.com/it/it4122.htm