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() 以及 new 和 delete 运算符。编程语言如 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 平台 SDK 节点。
当应用程序或 DLL 创建专用堆时，这些堆驻留于进程空间中并且在进程范围内是可访问的。某一给定堆分配的任何数据应为同一堆所释放。（从一个堆分配并释放给另一个堆没有意义。）
在所有虚拟内存系统中，堆位于操作系统的虚拟内存管理器之上。语言运行时堆也驻留在虚拟内存之上。某些情况下，这些堆在操作系统堆的上层，但语言运行时堆通过分配大的块来执行自己的内存管理。绕开操作系统堆来使用虚拟内存函数可使堆更好地分配和使用块。
典型的堆实现由前端分配器和后端分配器组成。前端分配器维护固定大小块的自由列表。当堆收到分配调用后，它尝试从前端列表中查找自由块。如果此操作失败，则堆将被迫从后端（保留和提交虚拟内存）分配一个大块来满足请求。通常的实现具有每个块分配的开销，这花费了执行周期，也减少了可用存储区。
知识库文章 Q10758"Managing Memory with calloc() and malloc()"（按文章 ID 号搜索）包含有关这些主题的更多背景知识。另外，有关堆实现和设计的详细讨论，请参阅 Paul R. Wilson、Mark S. Johnstone、Michael Neely 和 David Boles 所著的"Dynamic Storage Allocation: A Survey and Critical Review"。"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 字节对齐块的自由列表和 1 个混合列表。混合列表（自由列表[0]）包含大小超过 1,024 字节的块。自由列表包含在双向链接表中链接在一起的对象。默认情况下，进程堆执行合并操作。（合并操作是组合相邻的自由块以生成更大的块的操作。）合并操作花费了额外的周期，但减少了堆块的内部碎片。
单个全局锁可防止多线程同时使用堆。（请参阅 George Reilly 写的服务器性能和可伸缩性杀手锏的第一条戒律。）此锁主要用于保护堆数据结构不受多线程的任意访问。当堆操作过于频繁时，此锁会对性能造成负面影响。
以下是在使用堆时会遇到的最常见问题：
在分配及释放操作中，争用是使速度降低的原因。理想情况下，我们希望有一个没有争用且快速分配/释放的堆。哎，这样的通用用途堆尚不存在，尽管在将来某个时候也许会出现。
在所有的服务器系统（如 IIS、MSProxy、DatabaseStacks、网络服务器、Exchange 等等）中，堆锁都是一个"大"瓶颈。处理器的数目越多，争用越厉害。
既然您知道了关于堆的一些问题，难道不想要一根解决这些问题的魔棒吗？我希望有一根魔棒。但是没有魔法使堆运行得更快，因此不要期望在发行产品的前一个星期内使速度加快。请尽早计划您的堆策略，这样会好得多。改变使用堆的方式并减少堆操作数是提高性能的可靠策略。
如何减少堆操作的使用呢？可以通过在数据结构内使用位置来减少堆操作数。考虑下面的示例：
struct ObjectA {
// data for objectA
}
struct ObjectB {
// data for objectB
}
// Use of ObjectA and ObjectB together.
//
// Use pointers
//
struct ObjectB {
struct ObjectA * pObjA;
// data for objectB
}
//
// Use embedding
//
struct ObjectB {
struct ObjectA pObjA;
// data for objectB
}
//
// Aggregation - use ObjectA and ObjectB inside another object
//
struct ObjectX {
struct ObjectA objA;
struct ObjectB objB;
}
- 避免使用指针来关联两个数据结构。如果使用指针关联两个数据结构，则前面示例中的对象 A 和 B 将分别被分配和释放。这是一个额外的开销，并且是我们希望避免的事情。
- 将指向的子对象嵌入父对象中。每当对象中有指针时，就意味着有一个动态元素 (80%) 和一个要取消引用的新位置。嵌入操作增加了位置并减少了进一步分配/释放的需要。这将提高应用程序的性能。
- 合并较小的对象以形成较大的对象（聚合）。聚合可减少分配和释放的块数。如果有多个开发人员同时对负责设计的不同部分进行开发，最后可能得到许多可以合并的小对象。此合并的难点是要找到正确的聚合边界。
- 内联一个可满足 80% 需要的缓冲区（也称为 80-20 规则）。在一些情况下，需要用内存缓冲区来存储字符串/二进制数据，而总字节数事先是未知的。进行测量并内联一个大小可满足 80% 需要的缓冲区。对于余下的 20%，可以分配一个新缓冲区并用指针指向该缓冲区。这样可以减少分配和释放调用并增加数据的空间位置，这将最终提高代码的性能。
- 将对象分配为块区（分块）。分块是指一次将多个对象分配在一组中的方法。如果必须跟踪项列表，例如 {名称, 值} 对列表，则有两种方法：方法 1 是为每一名称-值对分配一个节点。方法 2 是分配一个可容纳例如五个名称-值对的结构。例如，如果存储四对数据是常见方案，可以减少节点数和附加链接表指针所需的额外空间量。
分块是处理器缓存友好的，尤其是对于 L1 缓存，因为它提供了增加的位置，更不用说其中一些数据块位于用于块分配的同一虚拟页了。
- 适当地使用 _amblksiz。C 运行时库 (CRT) 具有自定义的前端分配器，该分配器用于从后端（Win32 堆）分配 _amblksiz 大小的块。将 _amblksiz 设置为一个较大的值可以潜在地减少对后端的调用数量。这只适用于大量使用 CRT 的程序。
通过使用上述技巧获得的节省因对象类型、大小和工作负荷而异。但总是能获得性能和可缩放性方面的好处。退一步说，代码会有点专用，但是如果认真思考，代码还是可以易于管理的。
更多性能提升
以下是一些提升速度的更多技巧：
- 使用 Windows NT5 堆
由于几个人的努力和辛勤工作，在 1998 年初，Microsoft Windows 2000 进行了一些显著改进：
- 堆代码内部的锁定改进。堆代码在每个堆上使用一个锁。此全局锁用于保护堆数据结构不由多个线程使用。不幸的是，在高通讯量的情况中，堆仍然可能陷入此全局锁中，从而导致高争用和低性能。Windows 2000 减少了锁内代码的关键区域以使争用的可能性减到最小，从而提高了缩放性。
- 使用后备列表。堆数据结构对块大小介于 8 和 1,024 字节之间（以 8 字节递增）的所有自由项使用快速缓存。最初是在全局锁中保护快速缓存。现在使用后备列表访问快速缓存自由列表。这些列表不需要锁，并使用 64 位互锁操作，因此提高了性能。
- 内部数据结构算法也得到改进。
这些改进消除了分配缓存的需求，但并不排除其他优化。针对 Windows NT5 堆评估您的代码；它对于小于 1,024 字节 (1 KB) 的块（来自前端分配器的块）应该是最理想的。GlobalAlloc() 和 LocalAlloc() 建立在同一个堆上，并且是访问每进程堆的常见机制。使用 Heap* API 可以访问每进程堆，或者在需要高度专用性能时可以创建您自己用于分配操作的堆。也可以在大块操作需要时直接使用 VirtualAlloc() / VirtualFree() 操作。
以上描述的改进在 Windows 2000 beta 2 和 Windows NT 4.0 SP4 中得到体现。经过这些改进后，堆锁的争用率显著降低。这有利于 Win32 堆的所有直接用户。CRT 堆建立在 Win32 堆之上，却使用自己的小块堆，因此并不受益于 Windows NT 的这些改进。（Visual C++ 6.0 版也具有一个改进的堆分配器。）
- 使用分配缓存
分配缓存使您得以缓存已分配的块以便将来重用。这可以减少对进程堆（或全局堆）的分配/释放调用的数量，也使得块一旦分配就得以最大程度地重用。另外，分配缓存允许您收集统计信息以便更好地理解高层上的对象使用。
通常情况下，自定义堆分配器在进程堆之上实现。自定义堆分配器的行为与系统堆非常类似。主要差异是自定义堆分配器在进程堆之上为已分配的对象提供缓存。缓存设计用于一组固定的大小（例如，32 字节、64 字节、128 字节，等等）。这是一个好的策略，但是这种类型的自定义堆分配器不具有与已分配和已释放的对象相关的语义信息。
与自定义堆分配器相比，"分配缓存"作为每类分配缓存实现。它们除了提供自定义堆分配器的所有优点外，还可以保留许多语义信息。每个分配缓存处理程序都与目标二进制文件中的一个对象关联。它可以由一组指示并发级别、对象大小、保留在自由列表中的元素数等的参数初始化。分配缓存处理程序对象维护自己的已释放实体的专用池（不超过指定的阈值），并使用专用锁进行保护。分配缓存和专用锁一起减少了到主系统堆的通讯量，从而提供了增强的并发性、最大的重用性和更高的可伸缩性。
需要清理程序定期检查所有分配缓存处理程序的活动并回收未使用的资源。如果（当）没有发现任何活动，则可释放已分配对象池，从而提高性能。
可以审核每一个分配/释放活动。第一级别的信息包括对象、分配和已进行的自由调用的总数。可以通过查看不同对象的统计信息，得出它们之间的语义关系。该关系可用于通过使用刚才所说的多个技巧之一减少内存分配。
分配缓存也可作为调试辅助手段，帮助您跟踪未完全清理的对象数。除了尚未清理的对象外，甚至还可以通过查看动态堆栈反向跟踪和签名，查找确切的错误调用方。
- MP 堆
MP 堆是用于多处理器友好的分布式分配的包，并可用于 Win32 SDK（Windows NT 4.0 及更高版本）。此堆最初由 JVert 实现，此处的堆抽象化建立在 Win32 堆包之上。MP 堆创建多个 Win32 堆并尝试将分配调用分布到其他堆以减少任何单个锁上的争用。
该包是一个好的步骤，它算得上是一种改进的 MP 友好的自定义堆分配器。然而，它没有提供语义信息并缺少统计信息。使用 MP 堆的常用方式是将它用作 SDK 库。如果使用此 SDK 创建可重用组件，您将获益匪浅。而如果将此 SDK 库内置到每个 DLL 中，则将增加工作集。
- 重新考虑算法和数据结构
若要在多处理器计算机上伸缩，算法、实现、数据结构和硬件必须动态伸缩。请查看最常分配和释放的数据结构。问问自己："我可以使用不同的数据结构来完成这项工作吗？"例如，如果有一个只读项列表在应用程序初始化时加载，则此列表不必是线性链接表。它完全可以是一个动态分配数组。动态分配数组可减少内存中的堆块并减少碎片，从而提供性能提升。
减少所需的小对象数可减少堆分配器上的负载。例如，我们在服务器的关键处理路径上使用了五个不同的对象，每个对象单独分配和释放。将对象一起缓存使堆调用从五个减少到一个，并显著减少了堆上的负载，尤其当每秒处理的请求多于 1,000 个时。
如果广泛使用自动化结构，可考虑从主线代码中分离出自动化 BSTR，或者至少避免 BSTR上的重复操作。（BSTR 串联会导致过多的重新分配和分配/释放操作。）
摘要
堆实现趋于对所有平台保持通用，因此具有巨大的系统开销。每个人的代码都有特定的要求，但是设计可以适应本文所讨论的原则以减少堆交互。
- 评估代码中堆的使用。
- 提高代码的效率以使用较少的堆调用：分析关键路径并修复数据结构。
- 在实现自定义包装前进行度量以量化堆调用的成本。
- 如果对性能不满意，请询问操作系统组以改进堆。此类请求越多，意味着将投入越多的精力改进堆。
- 询问 C 运行时组以在操作系统提供的堆上使分配器成为瘦包装。结果，C 运行时堆调用的成本随着操作系统堆的改进而减少。
- 操作系统（Windows NT 家族）不断进行着堆的改进。保持步调一致并利用这些改进。
Murali Krishnan 是 Internet Information Server (IIS) 团队的首席软件设计工程师。他从 1.0 版就开始研究 IIS，并成功地将 IIS 从 1.0 版一直升级到 4.0。Murali 组织和领导了 IIS 性能小组三年 (1995-1998)，并从第一天起就开始改变 IIS 的性能。他在印第安纳州的 Anna 大学获得计算机科学学士学位，并在 Wisconsin-Madison 大学获得计算机科学硕士学位。工作之余，他喜欢读书、打排球和在家烹饪。
<!--Footer Start-->
加好友 
发短信
Post By：2009/11/24 17:29:10
