堆用于動態(tài)分配和釋放程序所使用的對象。在以下情況中調(diào)用堆操作：

1. 事先不知道程序所需對象的數(shù)量和大小。
2. 對象太大，不適合使用堆棧分配器。

堆使用運行期間分配給代碼和堆棧以外的部分內(nèi)存。下圖顯示堆分配器的不同層。

GlobalAlloc/GlobalFree：直接與每個進程的默認堆通訊的 Microsoft Win32 堆調(diào)用。

LocalAlloc/LocalFree：直接與每個進程的默認堆通訊的 Win32 堆調(diào)用（用于與 Microsoft Windows NT 的兼容性）。

COM 的 IMalloc 分配器（或 CoTaskMemAlloc / CoTaskMemFree）：函數(shù)使用默認的每個進程堆。自動化使用組件對象模型 (COM) 的分配器，而請求使用每進程堆。

C/C++ 運行時 (CRT) 分配器：提供 malloc() 和 free() 以及 new 和 delete 運算符。編程語言如 Microsoft Visual Basic 和 Java 還提供新運算符，它們使用的是垃圾回收而不是堆。CRT 創(chuàng)建自己的駐留在 Win32 堆之上的專用堆。

在 Windows NT 中，Win32 堆是圍繞 Windows NT 運行時分配器的一個薄層。所有的 API 都將它們的請求轉(zhuǎn)發(fā)到 NTDLL。

在 Windows NT 中，Windows NT 運行時分配器提供了該核心堆分配器。它包含一個前端分配器，該分配器具有 128 個大小從 8 到 1,024 字節(jié)不等的自由列表。后端分配器使用虛擬內(nèi)存保留和提交頁面。

圖表的底部是虛擬內(nèi)存分配器，它保留和提交操作系統(tǒng)使用的頁面。所有的分配器都使用虛擬內(nèi)存設(shè)備訪問數(shù)據(jù)。

分配和釋放塊不是很簡單嗎？為什么這要花費很長的時間？

傳統(tǒng)上，操作系統(tǒng)和運行時庫隨附了堆實現(xiàn)。當(dāng)進程開始時，操作系統(tǒng)創(chuàng)建稱為進程堆的默認堆。如果沒有使用其他堆，則使用進程堆分配塊。語言運行時庫也可在一個進程內(nèi)創(chuàng)建單獨的堆。（例如，C 運行時庫創(chuàng)建自己的堆。）除這些專用堆外，應(yīng)用程序或許多加載的動態(tài)鏈接庫 (DLL) 之一也可以創(chuàng)建并使用單獨的堆。Win32 提供了一組豐富的 API 用于創(chuàng)建和使用專用堆。有關(guān)堆函數(shù)的優(yōu)秀教程，請參閱 MSDN 平臺 SDK 節(jié)點。

當(dāng)應(yīng)用程序或 DLL 創(chuàng)建專用堆時，這些堆駐留于進程空間中并且在進程范圍內(nèi)是可訪問的。某一給定堆分配的任何數(shù)據(jù)應(yīng)為同一堆所釋放。（從一個堆分配并釋放給另一個堆沒有意義。）

在所有虛擬內(nèi)存系統(tǒng)中，堆位于操作系統(tǒng)的虛擬內(nèi)存管理器之上。語言運行時堆也駐留在虛擬內(nèi)存之上。某些情況下，這些堆在操作系統(tǒng)堆的上層，但語言運行時堆通過分配大的塊來執(zhí)行自己的內(nèi)存管理。繞開操作系統(tǒng)堆來使用虛擬內(nèi)存函數(shù)可使堆更好地分配和使用塊。

典型的堆實現(xiàn)由前端分配器和后端分配器組成。前端分配器維護固定大小塊的自由列表。當(dāng)堆收到分配調(diào)用后，它嘗試從前端列表中查找自由塊。如果此操作失敗，則堆將被迫從后端（保留和提交虛擬內(nèi)存）分配一個大塊來滿足請求。通常的實現(xiàn)具有每個塊分配的開銷，這花費了執(zhí)行周期，也減少了可用存儲區(qū)。

知識庫文章 Q10758"Managing Memory with calloc() and malloc()"（按文章 ID 號搜索）包含有關(guān)這些主題的更多背景知識。另外，有關(guān)堆實現(xiàn)和設(shè)計的詳細討論，請參閱 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 的實現(xiàn)（Windows NT 4.0 版及更高版本）使用 127 個從 8 到 1,024 字節(jié)不等的 8 字節(jié)對齊塊的自由列表和 1 個混合列表。混合列表（自由列表[0]）包含大小超過 1,024 字節(jié)的塊。自由列表包含在雙向鏈接表中鏈接在一起的對象。默認情況下，進程堆執(zhí)行合并操作。（合并操作是組合相鄰的自由塊以生成更大的塊的操作。）合并操作花費了額外的周期，但減少了堆塊的內(nèi)部碎片。

以下是在使用堆時會遇到的最常見問題：

既然您知道了關(guān)于堆的一些問題，難道不想要一根解決這些問題的魔棒嗎？我希望有一根魔棒。但是沒有魔法使堆運行得更快，因此不要期望在發(fā)行產(chǎn)品的前一個星期內(nèi)使速度加快。請盡早計劃您的堆策略，這樣會好得多。改變使用堆的方式并減少堆操作數(shù)是提高性能的可靠策略。

如何減少堆操作的使用呢？可以通過在數(shù)據(jù)結(jié)構(gòu)內(nèi)使用位置來減少堆操作數(shù)。考慮下面的示例：

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

1. 避免使用指針來關(guān)聯(lián)兩個數(shù)據(jù)結(jié)構(gòu)。如果使用指針關(guān)聯(lián)兩個數(shù)據(jù)結(jié)構(gòu)，則前面示例中的對象 A 和 B 將分別被分配和釋放。這是一個額外的開銷，并且是我們希望避免的事情。
2. 將指向的子對象嵌入父對象中。每當(dāng)對象中有指針時，就意味著有一個動態(tài)元素 (80%) 和一個要取消引用的新位置。嵌入操作增加了位置并減少了進一步分配/釋放的需要。這將提高應(yīng)用程序的性能。
3. 合并較小的對象以形成較大的對象（聚合）。聚合可減少分配和釋放的塊數(shù)。如果有多個開發(fā)人員同時對負責(zé)設(shè)計的不同部分進行開發(fā)，最后可能得到許多可以合并的小對象。此合并的難點是要找到正確的聚合邊界。
4. 內(nèi)聯(lián)一個可滿足 80% 需要的緩沖區(qū)（也稱為 80-20 規(guī)則）。在一些情況下，需要用內(nèi)存緩沖區(qū)來存儲字符串/二進制數(shù)據(jù)，而總字節(jié)數(shù)事先是未知的。進行測量并內(nèi)聯(lián)一個大小可滿足 80% 需要的緩沖區(qū)。對于余下的 20%，可以分配一個新緩沖區(qū)并用指針指向該緩沖區(qū)。這樣可以減少分配和釋放調(diào)用并增加數(shù)據(jù)的空間位置，這將最終提高代碼的性能。
5. 將對象分配為塊區(qū)（分塊）。分塊是指一次將多個對象分配在一組中的方法。如果必須跟蹤項列表，例如 {名稱, 值} 對列表，則有兩種方法：方法 1 是為每一名稱-值對分配一個節(jié)點。方法 2 是分配一個可容納例如五個名稱-值對的結(jié)構(gòu)。例如，如果存儲四對數(shù)據(jù)是常見方案，可以減少節(jié)點數(shù)和附加鏈接表指針所需的額外空間量。

   分塊是處理器緩存友好的，尤其是對于 L1 緩存，因為它提供了增加的位置，更不用說其中一些數(shù)據(jù)塊位于用于塊分配的同一虛擬頁了。

6. 適當(dāng)?shù)厥褂?_amblksiz。C 運行時庫 (CRT) 具有自定義的前端分配器，該分配器用于從后端（Win32 堆）分配 _amblksiz 大小的塊。將 _amblksiz 設(shè)置為一個較大的值可以潛在地減少對后端的調(diào)用數(shù)量。這只適用于大量使用 CRT 的程序。

通過使用上述技巧獲得的節(jié)省因?qū)ο箢愋�、大小和工作負荷而異。但總是能獲得性能和可縮放性方面的好處。退一步說，代碼會有點專用，但是如果認真思考，代碼還是可以易于管理的。

更多性能提升

以下是一些提升速度的更多技巧：

1. 使用 Windows NT5 堆

   由于幾個人的努力和辛勤工作，在 1998 年初，Microsoft Windows 2000 進行了一些顯著改進：

   • 堆代碼內(nèi)部的鎖定改進。堆代碼在每個堆上使用一個鎖。此全局鎖用于保護堆數(shù)據(jù)結(jié)構(gòu)不由多個線程使用。不幸的是，在高通訊量的情況中，堆仍然可能陷入此全局鎖中，從而導(dǎo)致高爭用和低性能。Windows 2000 減少了鎖內(nèi)代碼的關(guān)鍵區(qū)域以使爭用的可能性減到最小，從而提高了縮放性。
   • 使用后備列表。堆數(shù)據(jù)結(jié)構(gòu)對塊大小介于 8 和 1,024 字節(jié)之間（以 8 字節(jié)遞增）的所有自由項使用快速緩存。最初是在全局鎖中保護快速緩存�，F(xiàn)在使用后備列表訪問快速緩存自由列表。這些列表不需要鎖，并使用 64 位互鎖操作，因此提高了性能。
   • 內(nèi)部數(shù)據(jù)結(jié)構(gòu)算法也得到改進。

   這些改進消除了分配緩存的需求，但并不排除其他優(yōu)化。針對 Windows NT5 堆評估您的代碼；它對于小于 1,024 字節(jié) (1 KB) 的塊（來自前端分配器的塊）應(yīng)該是最理想的。GlobalAlloc() 和 LocalAlloc() 建立在同一個堆上，并且是訪問每進程堆的常見機制。使用 Heap* API 可以訪問每進程堆，或者在需要高度專用性能時可以創(chuàng)建您自己用于分配操作的堆。也可以在大塊操作需要時直接使用 VirtualAlloc() / VirtualFree() 操作。

   以上描述的改進在 Windows 2000 beta 2 和 Windows NT 4.0 SP4 中得到體現(xiàn)。經(jīng)過這些改進后，堆鎖的爭用率顯著降低。這有利于 Win32 堆的所有直接用戶。CRT 堆建立在 Win32 堆之上，卻使用自己的小塊堆，因此并不受益于 Windows NT 的這些改進。（Visual C++ 6.0 版也具有一個改進的堆分配器。）

2. 使用分配緩存

   分配緩存使您得以緩存已分配的塊以便將來重用。這可以減少對進程堆（或全局堆）的分配/釋放調(diào)用的數(shù)量，也使得塊一旦分配就得以最大程度地重用。另外，分配緩存允許您收集統(tǒng)計信息以便更好地理解高層上的對象使用。

   通常情況下，自定義堆分配器在進程堆之上實現(xiàn)。自定義堆分配器的行為與系統(tǒng)堆非常類似。主要差異是自定義堆分配器在進程堆之上為已分配的對象提供緩存。緩存設(shè)計用于一組固定的大�。ɡ�如，32 字節(jié)、64 字節(jié)、128 字節(jié)，等等）。這是一個好的策略，但是這種類型的自定義堆分配器不具有與已分配和已釋放的對象相關(guān)的語義信息。

   與自定義堆分配器相比，"分配緩存"作為每類分配緩存實現(xiàn)。它們除了提供自定義堆分配器的所有優(yōu)點外，還可以保留許多語義信息。每個分配緩存處理程序都與目標二進制文件中的一個對象關(guān)聯(lián)。它可以由一組指示并發(fā)級別、對象大小、保留在自由列表中的元素數(shù)等的參數(shù)初始化。分配緩存處理程序?qū)ο缶S護自己的已釋放實體的專用池（不超過指定的閾值），并使用專用鎖進行保護。分配緩存和專用鎖一起減少了到主系統(tǒng)堆的通訊量，從而提供了增強的并發(fā)性、最大的重用性和更高的可伸縮性。

   需要清理程序定期檢查所有分配緩存處理程序的活動并回收未使用的資源。如果（當(dāng)）沒有發(fā)現(xiàn)任何活動，則可釋放已分配對象池，從而提高性能。

   可以審核每一個分配/釋放活動。第一級別的信息包括對象、分配和已進行的自由調(diào)用的總數(shù)�？梢酝ㄟ^查看不同對象的統(tǒng)計信息，得出它們之間的語義關(guān)系。該關(guān)系可用于通過使用剛才所說的多個技巧之一減少內(nèi)存分配。

   分配緩存也可作為調(diào)試輔助手段，幫助您跟蹤未完全清理的對象數(shù)。除了尚未清理的對象外，甚至還可以通過查看動態(tài)堆棧反向跟蹤和簽名，查找確切的錯誤調(diào)用方。

3. MP 堆

   MP 堆是用于多處理器友好的分布式分配的包，并可用于 Win32 SDK（Windows NT 4.0 及更高版本）。此堆最初由 JVert 實現(xiàn)，此處的堆抽象化建立在 Win32 堆包之上。MP 堆創(chuàng)建多個 Win32 堆并嘗試將分配調(diào)用分布到其他堆以減少任何單個鎖上的爭用。

   該包是一個好的步驟，它算得上是一種改進的 MP 友好的自定義堆分配器。然而，它沒有提供語義信息并缺少統(tǒng)計信息。使用 MP 堆的常用方式是將它用作 SDK 庫。如果使用此 SDK 創(chuàng)建可重用組件，您將獲益匪淺。而如果將此 SDK 庫內(nèi)置到每個 DLL 中，則將增加工作集。

4. 重新考慮算法和數(shù)據(jù)結(jié)構(gòu)

   若要在多處理器計算機上伸縮，算法、實現(xiàn)、數(shù)據(jù)結(jié)構(gòu)和硬件必須動態(tài)伸縮。請查看最常分配和釋放的數(shù)據(jù)結(jié)構(gòu)。問問自己："我可以使用不同的數(shù)據(jù)結(jié)構(gòu)來完成這項工作嗎？"例如，如果有一個只讀項列表在應(yīng)用程序初始化時加載，則此列表不必是線性鏈接表。它完全可以是一個動態(tài)分配數(shù)組。動態(tài)分配數(shù)組可減少內(nèi)存中的堆塊并減少碎片，從而提供性能提升。

   減少所需的小對象數(shù)可減少堆分配器上的負載。例如，我們在服務(wù)器的關(guān)鍵處理路徑上使用了五個不同的對象，每個對象單獨分配和釋放。將對象一起緩存使堆調(diào)用從五個減少到一個，并顯著減少了堆上的負載，尤其當(dāng)每秒處理的請求多于 1,000 個時。

   如果廣泛使用自動化結(jié)構(gòu)，可考慮從主線代碼中分離出自動化 BSTR，或者至少避免 BSTR上的重復(fù)操作。（BSTR 串聯(lián)會導(dǎo)致過多的重新分配和分配/釋放操作。）

摘要

堆實現(xiàn)趨于對所有平臺保持通用，因此具有巨大的系統(tǒng)開銷。每個人的代碼都有特定的要求，但是設(shè)計可以適應(yīng)本文所討論的原則以減少堆交互。

1. 評估代碼中堆的使用。
2. 提高代碼的效率以使用較少的堆調(diào)用：分析關(guān)鍵路徑并修復(fù)數(shù)據(jù)結(jié)構(gòu)。
3. 在實現(xiàn)自定義包裝前進行度量以量化堆調(diào)用的成本。
4. 如果對性能不滿意，請詢問操作系統(tǒng)組以改進堆。此類請求越多，意味著將投入越多的精力改進堆。
5. 詢問 C 運行時組以在操作系統(tǒng)提供的堆上使分配器成為瘦包裝。結(jié)果，C 運行時堆調(diào)用的成本隨著操作系統(tǒng)堆的改進而減少。
6. 操作系統(tǒng)（Windows NT 家族）不斷進行著堆的改進。保持步調(diào)一致并利用這些改進。

Murali Krishnan 是 Internet Information Server (IIS) 團隊的首席軟件設(shè)計工程師。他從 1.0 版就開始研究 IIS，并成功地將 IIS 從 1.0 版一直升級到 4.0。Murali 組織和領(lǐng)導(dǎo)了 IIS 性能小組三年 (1995-1998)，并從第一天起就開始改變 IIS 的性能。他在印第安納州的 Anna 大學(xué)獲得計算機科學(xué)學(xué)士學(xué)位，并在 Wisconsin-Madison 大學(xué)獲得計算機科學(xué)碩士學(xué)位。工作之余，他喜歡讀書、打排球和在家烹飪。