-
上帝是个女孩儿（God is a girl)
2006-09-13
-
内存碎片处理技术
2006-09-13
为了能有耐心看完这篇比较枯燥的文章，听个音乐先放松一下。。。
内存碎片是一个很棘手的问题。如何分配内存决定着内存碎片是否会、何时会、如何会成为一个问题。
即使在系统中事实上仍然有许多空闲内存时，内存碎片还会最终导致出现内存用完的情况。一个不断产生内存碎片的系统，不管产生的内存碎片多么小，只要时间足够长，就会将内存用完。这种情况在许多嵌入式系统中，特别是在高可用性系统中是不可接受的。有些软件环境，如OSE 实时操作系统已经备有避免内存碎片的良好工具，但个别程序员做出的选择仍然会对最终结果形成影响。“碎片的内存”描述一个系统中所有不可用的空闲内存。这些资源之所以仍然未被使用，是因为负责分配内存的分配器使这些内存无法使用。这一问题通常都会发生，原因在于空闲内存以小而不连续方式出现在不同的位置。由于分配方法决定内存碎片是否是一个问题，因此内存分配器在保证空闲资源可用性方面扮演着重要的角色。编译时间与运行时间在许多情况下都会出现内存分配问题。程序员可以通过编译程序和链接程序，为结构、并集、数组和标量（用作局部变量、静态变量或全局变量）方面的数据分配内存，程序员还可以在运行时间使用诸如 malloc()调用命令动态地分配内存。当用编译程序和链接程序完成内存分配功能时，就不会出现内存碎片，因为编译程序了解数据寿命。掌握可供使用的数据寿命，好处在于可以使数据以后进先出的方式叠加起来。这样就可以使内存分配程序工作效率更高，而不会出现内存碎片。一般来说，运行时间内的内存分配是不可叠加的。内存分配在时间上是独立的，从而使得碎片问题难以解决。
图 1，内存碎片的几种形式。内存分配程序浪费内存的基本方式有三种：即额外开销、内部碎片以及外部碎片（图 1）。内存分配程序需要存储一些描述其分配状态的数据。这些存储的信息包括任何一个空闲内存块的位置、大小和所有权，以及其它内部状态详情。一般来说，一个运行时间分配程序存放这些额外信息最好的地方是它管理的内存。内存分配程序需要遵循一些基本的内存分配规则。例如，所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址。内存分配程序把仅仅预定大小的内存块分配给客户，可能还有其它原因。当某个客户请求一个 43 字节的内存块时，它可能会获得 44字节、48字节 甚至更多的字节。由所需大小四舍五入而产生的多余空间就叫内部碎片。外部碎片的产生是当已分配内存块之间出现未被使用的差额时，就会产生外部碎片。例如，一个应用程序分配三个连续的内存块，然后使中间的一个内存块空闲。内存分配程序可以重新使用中间内存块供将来进行分配，但不太可能分配的块正好与全部空闲内存一样大。倘若在运行期间，内存分配程序不改变其实现法与四舍五入策略，则额外开销和内部碎片在整个系统寿命期间保持不变。虽然额外开销和内部碎片会浪费内存，因此是不可取的，但外部碎片才是嵌入系统开发人员真正的敌人，造成系统失效的正是分配问题。定义内存碎片的方法有几种，其中最常用的是：
这一方法适用于外部碎片，但可以修改这一公式使之包括内部碎片，办法是把内部碎片加入到分母中。内存碎片是一个介于 0 和 1 之间的分数。一个碎片为 1(100%)的系统就是把内存全用完了。如果所有空闲内存都在一个内存块（最大内存块）中，碎片为 0%。当所有空闲内存的四分之一在最大内存块中时，碎片为 75%。例子如下：一个系统有 5M 字节的空闲内存，当它可用来分配的最大内存块为 50 k 字节时，其内存碎片为99%。这个 99%内存碎片实例来自开发嵌入式软实时系统期间出现的一种真实情况。当这种碎片程度发生一秒后，系统就崩溃了。该系统在碎片率达到 99% 之前，已经进行了约两周的连续现场测试。这种情况是如何发生的？为什么会发现得如此晚？当然，系统都经过测试，但测试很少超过两个小时。交付前的最后压力测试持续了一个周末。在这样短的测试周期内未必会产生内存碎片的后果，所以就发生了内存碎片需要多长时间才会达到临界值，这一问题很难回答。对某些应用来说，在某些情况下，系统会在用完内存前达到一种稳定状态。而对于另一些应用来说，系统则不会及时达到稳定状态（图 2）。只要消除不确定性因素和风险因素，不产生碎片的内存分配程序（图 3）就能快速达到一种稳定状态，从而有助于开发人员夜晚安稳睡觉。在开发数月甚至数年不再重新启动的长期运行系统时，快速收敛到稳定状态是一个重要因素。在比系统连续运行周期短的时间内，对系统进行适当的测试，这是必不可少的。
图 2，这一案例研究把最先适合内存分配程序用于一个嵌入系统项目。系统在现场测试中连续运行了两周，然后碎片率达到 99%。
图 3，一个不产生碎片的内存分配程序一旦试验应用程序的全部，它就能达到稳定状态。
很难确定哪种内存分配算法更胜一筹，因为每种算法在不同的应用中各有所长（表 1）。最先适合内存分配算法是最常用的一种。它使用了四个指针：MSTART 指向被管理内存的始端；MEND 指向被管理内存的末尾；MBREAK 指向 MSTART 和 MEND 之间已用内存的末端； PFREE 则指向第一个空闲内存块（如果有的话）。
在系统开始运行时，PFREE 为 NULL，MBREAK 指向 MSTART。当一个分配请求来到时，分配程序首先检查 PFREE有无空闲内存块。由于 PFREE 为 NULL，一个具有所请求存储量加上管理标题的内存块就脱离 MBREAK ，然后MBREAK就更新。这一过程反复进行，直至系统使一个内存块空闲，管理标题包含有该存储块的存储量为止。此时，PFREE 通过头上的链接表插入项被更新为指向该内存块，而块本身则用一个指向旧 PFREE 内容的指针进行更新，以建立一个链接表。下一次出现分配请求时，系统就会搜索空闲内存块链接表，寻找适合请求存储量的第一个空闲内存块。一旦找到合适的内存块，它将此内存块分成两部分，一部分返还给系统，另一部分则送回给自由表。最先适合内存分配算法实现起来简单，而且开始时很好用。但是，经过一段时间后，会出现如下的情况：当系统将内存交给自由表时，它会从自由表的开头部分去掉大内存块，插入剩余的小内存块。最先适合算法实际上成了一个排序算法，即把所有小内存碎片放在自由表的开头部分。因此，自由表会变得很长，有几百甚至几千个元素。因此，内存分配变得时间很长又无法预测，大内存块分配所花时间要比小内存块分配来得长。另外，内存块的无限制拆分使内存碎片程度很高。有些实现方法在使内存空闲时会将邻近的空闲内存块连接起来。这种方法多少有些作用，而最先适合算法与时间共处算法(time co-location)和空间共处算法(spatial co-location)不同，它在使内存块空闲时，无法提高相邻内存块同时空闲的概率。
最佳适合与最差适合分配程序最佳适合算法在功能上与最先适合算法类似，不同之处是，系统在分配一个内存块时，要搜索整个自由表，寻找最接近请求存储量的内存块。这种搜索所花的时间要比最先适合算法长得多，但不存在分配大小内存块所需时间的差异。最佳适合算法产生的内存碎片要比最先适合算法多，因为将小而不能使用的碎片放在自由表开头部分的排序趋势更为强烈。由于这一消极因素，最佳适合算法几乎从来没有人采用过。
最差适合算法也很少采用。最差适合算法的功能与最佳适合算法相同，不同之处是，当分配一个内存块时，系统在整个自由表中搜索与请求存储量不匹配的内存快。这种方法比最佳适合算法速度快，因为它产生微小而又不能使用的内存碎片的倾向较弱。始终选择最大空闲内存块，再将其分为小内存块，这样就能提高剩余部分大得足以供系统使用的概率。伙伴(buddy)分配程序与本文描述的其它分配程序不同，它不能根据需要从被管理内存的开头部分创建新内存。它有明确的共性，就是各个内存块可分可合，但不是任意的分与合。每个块都有个朋友，或叫“伙伴”，既可与之分开，又可与之结合。伙伴分配程序把内存块存放在比链接表更先进的数据结构中。这些结构常常是桶型、树型和堆型的组合或变种。一般来说，伙伴分配程序的工作方式是难以描述的，因为这种技术随所选数据结构的不同而各异。由于有各种各样的具有已知特性的数据结构可供使用，所以伙伴分配程序得到广泛应用。有些伙伴分配程序甚至用在源码中。伙伴分配程序编写起来常常很复杂，其性能可能各不相同。伙伴分配程序通常在某种程度上限制内存碎片。
固定存储量分配程序有点像最先空闲算法。通常有一个以上的自由表，而且更重要的是，同一自由表中的所有内存块的存储量都相同。至少有四个指针：MSTART 指向被管理内存的起点，MEND 指向被管理内存的末端，MBREAK 指向 MSTART 与 MEND 之间已用内存的末端，而 PFREE[n] 则是指向任何空闲内存块的一排指针。在开始时，PFREE[*] 为 NULL，MBREAK 指针为 MSTART。当一个分配请求到来时，系统将请求的存储量增加到可用存储量之一。然后，系统检查 PFREE[ 增大后的存储量 ] 空闲内存块。因为 PFREE[ 增大后的存储量 ] 为 NULL，一个具有该存储量加上一个管理标题的内存块就脱离 MBREAK，MBREAK 被更新。
这些步骤反复进行，直至系统使一个内存块空闲为止，此时管理标题包含有该内存块的存储量。当有一内存块空闲时，PFREE[ 相应存储量 ] 通过标题的链接表插入项更新为指向该内存块，而该内存块本身则用一个指向 PFREE[ 相应存储量 ] 以前内容的指针来更新，以建立一个链接表。下一次分配请求到来时，系统将 PFREE[ 增大的请求存储量 ] 链接表的第一个内存块送给系统。没有理由搜索链接表，因为所有链接的内存块的存储量都是相同的。固定存储量分配程序很容易实现，而且便于计算内存碎片，至少在块存储量的数量较少时是这样。但这种分配程序的局限性在于要有一个它可以分配的最大存储量。固定存储量分配程序速度快，并可在任何状况下保持速度。这些分配程序可能会产生大量的内部内存碎片，但对某些系统而言，它们的优点会超过缺点。
减少内存碎片内存碎片是因为在分配一个内存块后，使之空闲，但不将空闲内存归还给最大内存块而产生的。最后这一步很关键。如果内存分配程序是有效的，就不能阻止系统分配内存块并使之空闲。即使一个内存分配程序不能保证返回的内存能与最大内存块相连接（这种方法可以彻底避免内存碎片问题），但你可以设法控制并限制内存碎片。所有这些作法涉及到内存块的分割。每当系统减少被分割内存块的数量，确保被分割内存块尽可能大时，你就会有所改进。这样做的目的是尽可能多次反复使用内存块，而不要每次都对内存块进行分割，以正好符合请求的存储量。分割内存块会产生大量的小内存碎片，犹如一堆散沙。以后很难把这些散沙与其余内存结合起来。比较好的办法是让每个内存块中都留有一些未用的字节。留有多少字节应看系统要在多大程度上避免内存碎片。对小型系统来说，增加几个字节的内部碎片是朝正确方向迈出的一步。当系统请求1字节内存时，你分配的存储量取决于系统的工作状态。如果系统分配的内存存储量的主要部分是 1 ～ 16 字节，则为小内存也分配 16 字节是明智的。只要限制可以分配的最大内存块，你就能够获得较大的节约效果。但是，这种方法的缺点是，系统会不断地尝试分配大于极限的内存块，这使系统可能会停止工作。减少最大和最小内存块存储量之间内存存储量的数量也是有用的。采用按对数增大的内存块存储量可以避免大量的碎片。例如，每个存储量可能都比前一个存储量大 20%。在嵌入式系统中采用“一种存储量符合所有需要”对于嵌入式系统中的内存分配程序来说可能是不切实际的。这种方法从内部碎片来看是代价极高的，但系统可以彻底避免外部碎片，达到支持的最大存储量。将相邻空闲内存块连接起来是一种可以显著减少内存碎片的技术。如果没有这一方法，某些分配算法（如最先适合算法）将根本无法工作。然而，效果是有限的，将邻近内存块连接起来只能缓解由于分配算法引起的问题，而无法解决根本问题。而且，当内存块存储量有限时，相邻内存块连接可能很难实现。
有些内存分配器很先进，可以在运行时收集有关某个系统的分配习惯的统计数据，然后，按存储量将所有的内存分配进行分类，例如分为小、中和大三类。系统将每次分配指向被管理内存的一个区域，因为该区域包括这样的内存块存储量。较小存储量是根据较大存储量分配的。这种方案是最先适合算法和一组有限的固定存储量算法的一种有趣的混合，但不是实时的。
有效地利用暂时的局限性通常是很困难的，但值得一提的是，在内存中暂时扩展共处一地的分配程序更容易产生内存碎片。尽管其它技术可以减轻这一问题，但限制不同存储量内存块的数目仍是减少内存碎片的主要方法。
现代软件环境业已实现各种避免内存碎片的工具。例如，专为分布式高可用性容错系统开发的 OSE 实时操作系统可提供三种运行时内存分配程序：内核 alloc()，它根据系统或内存块池来分配；堆 malloc()，根据程序堆来分配； OSE 内存管理程序 alloc_region，它根据内存管理程序内存来分配。从许多方面来看，Alloc就是终极内存分配程序。它产生的内存碎片很少，速度很快，并有判定功能。你可以调整甚至去掉内存碎片。只是在分配一个存储量后，使之空闲，但不再分配时，才会产生外部碎片。内部碎片会不断产生，但对某个给定的系统和八种存储量来说是恒定不变的。Alloc 是一种有八个自由表的固定存储量内存分配程序的实现方法。系统程序员可以对每一种存储量进行配置，并可决定采用更少的存储量来进一步减少碎片。除开始时以外，分配内存块和使内存块空闲都是恒定时间操作。首先，系统必须对请求的存储量四舍五入到下一个可用存储量。就八种存储量而言，这一目标可用三个 如果 语句来实现。其次，系统总是在八个自由表的表头插入或删除内存块。开始时，分配未使用的内存要多花几个周期的时间，但速度仍然极快，而且所花时间恒定不变。
堆 malloc() 的内存开销（8 ～ 16 字节/分配）比 alloc小，所以你可以停用内存的专用权。malloc() 分配程序平均来讲是相当快的。它的内部碎片比alloc()少，但外部碎片则比alloc()多。它有一个最大分配存储量，但对大多数系统来说，这一极限值足够大。可选的共享所有权与低开销使 malloc() 适用于有许多小型对象和共享对象的 C++ 应用程序。堆是一种具有内部堆数据结构的伙伴系统的实现方法。在 OSE 中，有 28 个不同的存储量可供使用，每种存储量都是前两种存储量之和，于是形成一个斐波那契（Fibonacci）序列。实际内存块存储量为序列数乘以 16 字节，其中包括分配程序开销或者 8 字节/分配（在文件和行信息启用的情况下为 16 字节）。
当你很少需要大块内存时，则OSE内存管理程序最适用。典型的系统要把存储空间分配给整个系统、堆或库。在有 MMU 的系统中，有些实现方法使用 MMU 的转换功能来显著降低甚至消除内存碎片。在其他情况下，OSE 内存管理程序会产生非常多的碎片。它没有最大分配存储量，而且是一种最先适合内存分配程序的实现方法。内存分配被四舍五入到页面的偶数——典型值是 4 k 字节。
-
什么是“堆”
2006-09-13
Q：解释一个术语——“堆”。
A. “堆“的英文为heap, 与代码段，数据段，堆栈类似，堆也是进程地址空间的一块线性空间，它被用来存放（和管理）进程动态分配的全局内存对象，例如：进程通过malloc(),calloc()分配的内存。
在进程的数据对象中，局部变量通常在栈里存放（少量直接放在寄存器中）;预先分配的全局变量在数据段中存放；而动态分配的全局变量在"堆“内存放。
----------------曾经听闻说“堆是堆，栈是栈，合在一起称为堆栈”，这种说法超级幽默。堆栈和栈本来就是一个意思，只是中文对stack这个英文词汇的两种翻译方式。呵呵，这种解释也算是一桩经典了。
-
堆：欢乐和痛苦
2006-09-13
堆：欢乐和痛苦
Murali R. Krishnan
Microsoft Corporation1999 年 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。
当应用程序或 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.microsoft.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 NT5 堆
由于几个同事的努力和辛勤工作，1998 年初 Microsoft Windows(R) 2000 中有了几个重大改进：
- 改进了堆代码内的锁定。堆代码对每堆一个锁。全局锁保护堆数据结构，防止多线程式的使用。但不幸的是，在高通信量的情况下，堆仍受困于全局锁，导致高竞争和低性能。Windows 2000 中，锁内代码的临界区将竞争的可能性减到最小,从而提高了可伸缩性。
- 使用 “Lookaside”列表。堆数据结构对块的所有空闲项使用了大小在 8 到 1,024 字节（以 8-字节递增）的快速高速缓存。快速高速缓存最初保护在全局锁内。现在，使用 lookaside 列表来访问这些快速高速缓存空闲列表。这些列表不要求锁定，而是使用 64 位的互锁操作，因此提高了性能。
- 内部数据结构算法也得到改进。
这些改进避免了对分配高速缓存的需求，但不排除其他的优化。使用 Windows NT5 堆评估您的代码；它对小于 1,024 字节 (1 KB) 的块（来自前端分配程序的块）是最佳的。GlobalAlloc() 和 LocalAlloc() 建立在同一堆上，是存取每个进程堆的通用机制。如果希望获得高的局部性能，则使用 Heap(R) API 来存取每个进程堆，或为分配操作创建自己的堆。如果需要对大块操作，也可以直接使用 VirtualAlloc() / VirtualFree() 操作。
上述改进已在 Windows 2000 beta 2 和 Windows NT 4.0 SP4 中使用。改进后，堆锁的竞争率显著降低。这使所有 Win32 堆的直接用户受益。CRT 堆建立于 Win32 堆的顶部，但它使用自己的小块堆，因而不能从 Windows NT 改进中受益。（Visual C++ 版本 6.0 也有改进的堆分配程序。）
- 改进了堆代码内的锁定。堆代码对每堆一个锁。全局锁保护堆数据结构，防止多线程式的使用。但不幸的是，在高通信量的情况下，堆仍受困于全局锁，导致高竞争和低性能。Windows 2000 中，锁内代码的临界区将竞争的可能性减到最小,从而提高了可伸缩性。
- 使用分配高速缓存
分配高速缓存允许高速缓存分配的块，以便将来重用。这能够减少对进程堆（或全局堆）的分配/释放调用的次数，也允许最大限度的重用曾经分配的块。另外，分配高速缓存允许收集统计信息,以便较好地理解对象在较高层次上的使用。
典型地，自定义堆分配程序在进程堆的顶部实现。自定义堆分配程序与系统堆的行为很相似。主要的差别是它在进程堆的顶部为分配的对象提供高速缓存。高速缓存设计成一套固定大小（如 32 字节、64 字节、128 字节等）。这一个很好的策略，但这种自定义堆分配程序丢失与分配和释放的对象相关的“语义信息”。
与自定义堆分配程序相反，“分配高速缓存”作为每类分配高速缓存来实现。除能够提供自定义堆分配程序的所有好处之外，它们还能够保留大量语义信息。每个分配高速缓存处理程序与一个目标二进制对象关联。它能够使用一套参数进行初始化，这些参数表示并发级别、对象大小和保持在空闲列表中的元素的数量等。分配高速缓存处理程序对象维持自己的私有空闲实体池（不超过指定的阀值）并使用私有保护锁。合在一起，分配高速缓存和私有锁减少了与主系统堆的通信量，因而提供了增加的并发、最大限度的重用和较高的可伸缩性。
需要使用清理程序来定期检查所有分配高速缓存处理程序的活动情况并回收未用的资源。如果发现没有活动，将释放分配对象的池，从而提高性能。
可以审核每个分配/释放活动。第一级信息包括对象、分配和释放调用的总数。通过查看它们的统计信息可以得出各个对象之间的语义关系。利用以上介绍的许多技术之一，这种关系可以用来减少内存分配。
分配高速缓存也起到了调试助手的作用，帮助您跟踪没有完全清除的对象数量。通过查看动态堆栈返回踪迹和除没有清除的对象之外的签名，甚至能够找到确切的失败的调用者。
- MP 堆
MP 堆是对多处理器友好的分布式分配的程序包，在 Win32 SDK（Windows NT 4.0 和更新版本）中可以得到。最初由 JVert 实现，此处堆抽象建立在 Win32 堆程序包的顶部。MP 堆创建多个 Win32 堆，并试图将分配调用分布到不同堆，以减少在所有单一锁上的竞争。
本程序包是好的步骤 —一种改进的 MP-友好的自定义堆分配程序。但是，它不提供语义信息和缺乏统计功能。通常将 MP 堆作为 SDK 库来使用。如果使用这个 SDK 创建可重用组件，您将大大受益。但是，如果在每个 DLL 中建立这个 SDK 库，将增加工作设置。
- 重新思考算法和数据结构
要在多处理器机器上伸缩，则算法、实现、数据结构和硬件必须动态伸缩。请看最经常分配和释放的数据结构。试问，“我能用不同的数据结构完成此工作吗？”例如，如果在应用程序初始化时加载了只读项的列表，这个列表不必是线性链接的列表。如果是动态分配的数组就非常好。动态分配的数组将减少内存中的堆块和碎片，从而增强性能。
减少需要的小对象的数量减少堆分配程序的负载。例如，我们在服务器的关键处理路径上使用五个不同的对象，每个对象单独分配和释放。一起高速缓存这些对象，把堆调用从五个减少到一个，显著减少了堆的负载，特别当每秒钟处理 1,000 个以上的请求时。
如果大量使用“Automation”结构，请考虑从主线代码中删除“Automation BSTR”，或至少避免重复的 BSTR 操作。（BSTR 连接导致过多的重分配和分配/释放操作。）
摘要
对所有平台往往都存在堆实现，因此有巨大的开销。每个单独代码都有特定的要求，但设计能采用本文讨论的基本理论来减少堆之间的相互作用。
- 评价您的代码中堆的使用。
- 改进您的代码，以使用较少的堆调用：分析关键路径和固定数据结构。
- 在实现自定义的包装程序之前使用量化堆调用成本的方法。
- 如果对性能不满意，请要求 OS 组改进堆。更多这类请求意味着对改进堆的更多关注。
- 要求 C 运行时组针对 OS 所提供的堆制作小巧的分配包装程序。随着 OS 堆的改进，C 运行时堆调用的成本将减小。
- 操作系统（Windows NT 家族）正在不断改进堆。请随时关注和利用这些改进。
Murali Krishnan 是 Internet Information Server (IIS) 组的首席软件设计工程师。从 1.0 版本开始他就设计 IIS，并成功发行了 1.0 版本到 4.0 版本。Murali 组织并领导 IIS 性能组三年 (1995-1998), 从一开始就影响 IIS 性能。他拥有威斯康星州 Madison 大学的 M.S.和印度 Anna 大学的 B.S.。工作之外，他喜欢阅读、打排球和家庭烹饪。
- 事先不知道程序所需对象的数量和大小。
共1页 1
