Murali R. Krishnan
Microsoft Corporation

1999 年 2 月

摘要： 討論常見的堆性能問題以及如何防范它們。（共 9 頁）

前言

您是否是動態分配的 C/C++ 對象忠實且幸運的用戶？您是否在模塊間的往返通信中頻繁地使用了“自動化”？您的程序是否因堆分配而運行起來很慢？不僅僅您遇到這樣的問題。幾乎所有項目遲早都會遇到堆問題。大家都想說，“我的代碼真正好，只是堆太慢”。那只是部分正確。更深入理解堆及其用法、以及會發生什么問題，是很有用的。

什么是堆？

（如果您已經知道什么是堆，可以跳到“什么是常見的堆性能問題？”部分）

在程序中，使用堆來動態分配和釋放對象。在下列情況下，調用堆操作：

1. 事先不知道程序所需對象的數量和大小。
   
   
2. 對象太大而不適合堆棧分配程序。

堆使用了在運行時分配給代碼和堆棧的內存之外的部分內存。下圖給出了堆分配程序的不同層。

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;
}

1. 避免使用指針關聯兩個數據結構。如果使用指針關聯兩個數據結構，前面實例中的對象 A 和 B 將被分別分配和釋放。這會增加額外開銷—我們要避免這種做法。
   
   
2. 把帶指針的子對象嵌入父對象。當對象中有指針時，則意味著對象中有動態元素（百分之八十）和沒有引用的新位置。嵌入增加了位置從而減少了進一步分配/釋放的需求。這將提高應用程序的性能。
   
   
3. 合并小對象形成大對象（聚合）。聚合減少分配和釋放的塊的數量。如果有幾個開發者，各自開發設計的不同部分，則最終會有許多小對象需要合并。集成的挑戰就是要找到正確的聚合邊界。
   
   
4. 內聯緩沖區能夠滿足百分之八十的需要（aka 80-20 規則）。個別情況下，需要內存緩沖區來保存字符串/二進制數據，但事先不知道總字節數。估計并內聯一個大小能滿足百分之八十需要的緩沖區。對剩余的百分之二十，可以分配一個新的緩沖區和指向這個緩沖區的指針。這樣，就減少分配和釋放調用并增加數據的位置空間，從根本上提高代碼的性能。
   
   
5. 在塊中分配對象（塊化）。塊化是以組的方式一次分配多個對象的方法。如果對列表的項連續跟蹤，例如對一個 {名稱，值} 對的列表，有兩種選擇：選擇一是為每一個“名稱-值”對分配一個節點；選擇二是分配一個能容納（如五個）“名稱-值”對的結構。例如，一般情況下，如果存儲四對，就可減少節點的數量，如果需要額外的空間數量，則使用附加的鏈表指針。

   塊化是友好的處理器高速緩存，特別是對于 L1-高速緩存，因為它提供了增加的位置 —不用說對于塊分配，很多數據塊會在同一個虛擬頁中。

6. 正確使用 _amblksiz。C 運行時 (CRT) 有它的自定義前端分配程序，該分配程序從后端（Win32 堆）分配大小為 _amblksiz 的塊。將 _amblksiz 設置為較高的值能潛在地減少對后端的調用次數。這只對廣泛使用 CRT 的程序適用。

使用上述技術將獲得的好處會因對象類型、大小及工作量而有所不同。但總能在性能和可升縮性方面有所收獲。另一方面，代碼會有點特殊，但如果經過深思熟慮，代碼還是很容易管理的。

其他提高性能的技術

下面是一些提高速度的技術：

1. 使用 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 也有改進的堆分配程序。）

2. 使用分配高速緩存

   分配高速緩存允許高速緩存分配的塊，以便將來重用。這能夠減少對進程堆（或全局堆）的分配/釋放調用的次數，也允許最大限度的重用曾經分配的塊。另外，分配高速緩存允許收集統計信息,以便較好地理解對象在較高層次上的使用。

   典型地，自定義堆分配程序在進程堆的頂部實現。自定義堆分配程序與系統堆的行為很相似。主要的差別是它在進程堆的頂部為分配的對象提供高速緩存。高速緩存設計成一套固定大小（如 32 字節、64 字節、128 字節等）。這一個很好的策略，但這種自定義堆分配程序丟失與分配和釋放的對象相關的“語義信息”。

   與自定義堆分配程序相反，“分配高速緩存”作為每類分配高速緩存來實現。除能夠提供自定義堆分配程序的所有好處之外，它們還能夠保留大量語義信息。每個分配高速緩存處理程序與一個目標二進制對象關聯。它能夠使用一套參數進行初始化，這些參數表示并發級別、對象大小和保持在空閑列表中的元素的數量等。分配高速緩存處理程序對象維持自己的私有空閑實體池（不超過指定的閥值）并使用私有保護鎖。合在一起，分配高速緩存和私有鎖減少了與主系統堆的通信量，因而提供了增加的并發、最大限度的重用和較高的可伸縮性。

   需要使用清理程序來定期檢查所有分配高速緩存處理程序的活動情況并回收未用的資源。如果發現沒有活動，將釋放分配對象的池，從而提高性能。

   可以審核每個分配/釋放活動。第一級信息包括對象、分配和釋放調用的總數。通過查看它們的統計信息可以得出各個對象之間的語義關系。利用以上介紹的許多技術之一，這種關系可以用來減少內存分配。

   分配高速緩存也起到了調試助手的作用，幫助您跟蹤沒有完全清除的對象數量。通過查看動態堆棧返回蹤跡和除沒有清除的對象之外的簽名，甚至能夠找到確切的失敗的調用者。

3. MP 堆

   MP 堆是對多處理器友好的分布式分配的程序包，在 Win32 SDK（Windows NT 4.0 和更新版本）中可以得到。最初由 JVert 實現，此處堆抽象建立在 Win32 堆程序包的頂部。MP 堆創建多個 Win32 堆，并試圖將分配調用分布到不同堆，以減少在所有單一鎖上的競爭。

   本程序包是好的步驟 —一種改進的 MP-友好的自定義堆分配程序。但是，它不提供語義信息和缺乏統計功能。通常將 MP 堆作為 SDK 庫來使用。如果使用這個 SDK 創建可重用組件，您將大大受益。但是，如果在每個 DLL 中建立這個 SDK 庫，將增加工作設置。

4. 重新思考算法和數據結構

   要在多處理器機器上伸縮，則算法、實現、數據結構和硬件必須動態伸縮。請看最經常分配和釋放的數據結構。試問，“我能用不同的數據結構完成此工作嗎？”例如，如果在應用程序初始化時加載了只讀項的列表，這個列表不必是線性鏈接的列表。如果是動態分配的數組就非常好。動態分配的數組將減少內存中的堆塊和碎片，從而增強性能。

   減少需要的小對象的數量減少堆分配程序的負載。例如，我們在服務器的關鍵處理路徑上使用五個不同的對象，每個對象單獨分配和釋放。一起高速緩存這些對象，把堆調用從五個減少到一個，顯著減少了堆的負載，特別當每秒鐘處理 1,000 個以上的請求時。

   如果大量使用“Automation”結構，請考慮從主線代碼中刪除“Automation BSTR”，或至少避免重復的 BSTR 操作。（BSTR 連接導致過多的重分配和分配/釋放操作。）

摘要

對所有平臺往往都存在堆實現，因此有巨大的開銷。每個單獨代碼都有特定的要求，但設計能采用本文討論的基本理論來減少堆之間的相互作用。

1. 評價您的代碼中堆的使用。
   
   
2. 改進您的代碼，以使用較少的堆調用：分析關鍵路徑和固定數據結構。
   
   
3. 在實現自定義的包裝程序之前使用量化堆調用成本的方法。
   
   
4. 如果對性能不滿意，請要求 OS 組改進堆。更多這類請求意味著對改進堆的更多關注。
   
   
5. 要求 C 運行時組針對 OS 所提供的堆制作小巧的分配包裝程序。隨著 OS 堆的改進，C 運行時堆調用的成本將減小。
   
   
6. 操作系統（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.。工作之外，他喜歡閱讀、打排球和家庭烹飪。