非本人作也!因非常經典,是以收歸旗下,與衆人閱之!原作者不祥!
堆和棧的差別
一、預備知識—程式的記憶體配置設定
一個由c/C++編譯的程式占用的記憶體分為以下幾個部分
1、棧區（stack）— 由編譯器自動配置設定釋放 ，存放函數的參數值，局部變量的值等。其操作方式類似于資料結構中的棧。
2、堆區（heap） — 一般由程式員配置設定釋放， 若程式員不釋放，程式結束時可能由OS回收 。注意它與資料結構中的堆是兩回事，配置設定方式倒是類似于連結清單，呵呵。
3、全局區（靜态區）（static）—，全局變量和靜态變量的存儲是放在一塊的，初始化的全局變量和靜态變量在一塊區域， 未初始化的全局變量和未初始化的靜态變量在相鄰的另一塊區域。 - 程式結束後有系統釋放
4、文字常量區—常量字元串就是放在這裡的。 程式結束後由系統釋放
5、程式代碼區—存放函數體的二進制代碼。
二、例子程式
這是一個前輩寫的，非常詳細
//main.cpp
int a = 0; 全局初始化區
char *p1; 全局未初始化區
main()
{
int b; 棧
char s[] = "abc"; 棧
char *p2; 棧
char *p3 = "123456"; 123456\0在常量區，p3在棧上。
static int c =0； 全局（靜态）初始化區
p1 = (char *)malloc(10);
p2 = (char *)malloc(20);
配置設定得來得10和20位元組的區域就在堆區。
strcpy(p1, "123456"); 123456\0放在常量區，編譯器可能會将它與p3所指向的"123456"優化成一個地方。
}
二、堆和棧的理論知識
2.1申請方式
stack:
由系統自動配置設定。 例如，聲明在函數中一個局部變量 int b; 系統自動在棧中為b開辟空間
heap:
需要程式員自己申請，并指明大小，在c中malloc函數
如p1 = (char *)malloc(10);
在C++中用new運算符
如p2 = (char *)malloc(10);
但是注意p1、p2本身是在棧中的。
2.2
申請後系統的響應
棧：隻要棧的剩餘空間大于所申請空間，系統将為程式提供記憶體，否則将報異常提示棧溢出。
堆：首先應該知道作業系統有一個記錄空閑記憶體位址的連結清單，當系統收到程式的申請時，
會周遊該連結清單，尋找第一個空間大于所申請空間的堆結點，然後将該結點從空閑結點連結清單中删除，并将該結點的空間配置設定給程式，另外，對于大多數系統，會在這塊記憶體空間中的首位址處記錄本次配置設定的大小，這樣，代碼中的delete語句才能正确的釋放本記憶體空間。另外，由于找到的堆結點的大小不一定正好等于申請的大小，系統會自動的将多餘的那部分重新放入空閑連結清單中。
2.3申請大小的限制
棧：在Windows下,棧是向低位址擴充的資料結構，是一塊連續的記憶體的區域。這句話的意思是棧頂的位址和棧的最大容量是系統預先規定好的，在WINDOWS下，棧的大小是2M（也有的說是1M，總之是一個編譯時就确定的常數），如果申請的空間超過棧的剩餘空間時，将提示overflow。是以，能從棧獲得的空間較小。
堆：堆是向高位址擴充的資料結構，是不連續的記憶體區域。這是由于系統是用連結清單來存儲的空閑記憶體位址的，自然是不連續的，而連結清單的周遊方向是由低位址向高位址。堆的大小受限于計算機系統中有效的虛拟記憶體。由此可見，堆獲得的空間比較靈活，也比較大。
2.4申請效率的比較：
棧由系統自動配置設定，速度較快。但程式員是無法控制的。
堆是由new配置設定的記憶體，一般速度比較慢，而且容易産生記憶體碎片,不過用起來最友善.
另外，在WINDOWS下，最好的方式是用VirtualAlloc配置設定記憶體，他不是在堆，也不是在棧是直接在程序的位址空間中保留一快記憶體，雖然用起來最不友善。但是速度快，也最靈活。
2.5堆和棧中的存儲内容
棧： 在函數調用時，第一個進棧的是主函數中後的下一條指令（函數調用語句的下一條可執行語句）的位址，然後是函數的各個參數，在大多數的C編譯器中，參數是由右往左入棧的，然後是函數中的局部變量。注意靜态變量是不入棧的。
當本次函數調用結束後，局部變量先出棧，然後是參數，最後棧頂指針指向最開始存的位址，也就是主函數中的下一條指令，程式由該點繼續運作。
堆：一般是在堆的頭部用一個位元組存放堆的大小。堆中的具體内容有程式員安排。
2.6存取效率的比較
char s1[] = "aaaaaaaaaaaaaaa";
char *s2 = "bbbbbbbbbbbbbbbbb";
aaaaaaaaaaa是在運作時刻指派的；
而bbbbbbbbbbb是在編譯時就确定的；
但是，在以後的存取中，在棧上的數組比指針所指向的字元串(例如堆)快。
比如：
#include
void main()
{
char a = 1;
char c[] = "1234567890";
char *p ="1234567890";
a = c[1];
a = p[1];
return;
}
對應的彙編代碼
10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
0040106A 88 4D FC mov byte ptr [ebp-4],cl
11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
00401070 8A 42 01 mov al,byte ptr [edx+1]
00401073 88 45 FC mov byte ptr [ebp-4],al
第一種在讀取時直接就把字元串中的元素讀到寄存器cl中，而第二種則要先把指針值讀到edx中，在根據edx讀取字元，顯然慢了。
2.7小結：
堆和棧的差別可以用如下的比喻來看出：
使用棧就象我們去飯館裡吃飯，隻管點菜（發出申請）、付錢、和吃（使用），吃飽了就走，不必理會切菜、洗菜等準備工作和洗碗、刷鍋等掃尾工作，他的好處是快捷，但是自由度小。
使用堆就象是自己動手做喜歡吃的菜肴，比較麻煩，但是比較符合自己的口味，而且自由度大。
windows程序中的記憶體結構
在閱讀本文之前，如果你連堆棧是什麼多不知道的話，請先閱讀文章後面的基礎知識。
接觸過程式設計的人都知道，進階語言都能通過變量名來通路記憶體中的資料。那麼這些變量在記憶體中是如何存放的呢？程式又是如何使用這些變量的呢？下面就會對此進行深入的讨論。下文中的C語言代碼如沒有特别聲明，預設都使用VC編譯的release版。
首先，來了解一下 C 語言的變量是如何在記憶體分部的。C 語言有全局變量(Global)、本地變量(Local)，靜态變量(Static)、寄存器變量(Regeister)。每種變量都有不同的配置設定方式。先來看下面這段代碼：
#include <stdio.h>
int g1=0, g2=0, g3=0;
int main()
{
static int s1=0, s2=0, s3=0;
int v1=0, v2=0, v3=0;
//列印出各個變量的記憶體位址
printf("0x%08x\n",&v1); //列印各本地變量的記憶體位址
printf("0x%08x\n",&v2);
printf("0x%08x\n\n",&v3);
printf("0x%08x\n",&g1); //列印各全局變量的記憶體位址
printf("0x%08x\n",&g2);
printf("0x%08x\n\n",&g3);
printf("0x%08x\n",&s1); //列印各靜态變量的記憶體位址
printf("0x%08x\n",&s2);
printf("0x%08x\n\n",&s3);
return 0;
}
編譯後的執行結果是：
0x0012ff78
0x0012ff7c
0x0012ff80
0x004068d0
0x004068d4
0x004068d8
0x004068dc
0x004068e0
0x004068e4
輸出的結果就是變量的記憶體位址。其中v1,v2,v3是本地變量，g1,g2,g3是全局變量，s1,s2,s3是靜态變量。你可以看到這些變量在記憶體是連續分布的，但是本地變量和全局變量配置設定的記憶體位址差了十萬八千裡，而全局變量和靜态變量配置設定的記憶體是連續的。這是因為本地變量和全局/靜态變量是配置設定在不同類型的記憶體區域中的結果。對于一個程序的記憶體空間而言，可以在邏輯上分成3個部份：代碼區，靜态資料區和動态資料區。動态資料區一般就是“堆棧”。“棧(stack)”和“堆(heap)”是兩種不同的動态資料區，棧是一種線性結構，堆是一種鍊式結構。程序的每個線程都有私有的“棧”，是以每個線程雖然代碼一樣，但本地變量的資料都是互不幹擾。一個堆棧可以通過“基位址”和“棧頂”位址來描述。全局變量和靜态變量配置設定在靜态資料區，本地變量配置設定在動态資料區，即堆棧中。程式通過堆棧的基位址和偏移量來通路本地變量。
├———————┤低端記憶體區域
│ …… │
├———————┤
│ 動态資料區 │
├———————┤
│ …… │
├———————┤
│ 代碼區 │
├———————┤
│ 靜态資料區 │
├———————┤
│ …… │
├———————┤高端記憶體區域
堆棧是一個先進後出的資料結構，棧頂位址總是小于等于棧的基位址。我們可以先了解一下函數調用的過程，以便對堆棧在程式中的作用有更深入的了解。不同的語言有不同的函數調用規定，這些因素有參數的壓入規則和堆棧的平衡。windows API的調用規則和ANSI C的函數調用規則是不一樣的，前者由被調函數調整堆棧，後者由調用者調整堆棧。兩者通過“__stdcall”和“__cdecl”字首區分。先看下面這段代碼：
#include <stdio.h>
void __stdcall func(int param1,int param2,int param3)
{
int var1=param1;
int var2=param2;
int var3=param3;
printf("0x%08x\n",¶m1); //列印出各個變量的記憶體位址
printf("0x%08x\n",¶m2);
printf("0x%08x\n\n",¶m3);
printf("0x%08x\n",&var1);
printf("0x%08x\n",&var2);
printf("0x%08x\n\n",&var3);
return;
}
int main()
{
func(1,2,3);
return 0;
}
編譯後的執行結果是：
0x0012ff78
0x0012ff7c
0x0012ff80
0x0012ff68
0x0012ff6c
0x0012ff70
├———————┤<—函數執行時的棧頂（ESP）、低端記憶體區域
│ …… │
├———————┤
│ var 1 │
├———————┤
│ var 2 │
├———————┤
│ var 3 │
├———————┤
│ RET │
├———————┤<—“__cdecl”函數傳回後的棧頂（ESP）
│ parameter 1 │
├———————┤
│ parameter 2 │
├———————┤
│ parameter 3 │
├———————┤<—“__stdcall”函數傳回後的棧頂（ESP）
│ …… │
├———————┤<—棧底（基位址 EBP）、高端記憶體區域
上圖就是函數調用過程中堆棧的樣子了。首先，三個參數以從又到左的次序壓入堆棧，先壓“param3”，再壓“param2”，最後壓入“param1”；然後壓入函數的傳回位址(RET)，接着跳轉到函數位址接着執行（這裡要補充一點，介紹UNIX下的緩沖溢出原理的文章中都提到在壓入RET後，繼續壓入目前EBP，然後用目前ESP代替EBP。然而，有一篇介紹windows下函數調用的文章中說，在windows下的函數調用也有這一步驟，但根據我的實際調試，并未發現這一步，這還可以從param3和var1之間隻有4位元組的間隙這點看出來）；第三步，将棧頂(ESP)減去一個數，為本地變量配置設定記憶體空間，上例中是減去12位元組(ESP=ESP-3*4，每個int變量占用4個位元組)；接着就初始化本地變量的記憶體空間。由于“__stdcall”調用由被調函數調整堆棧，是以在函數傳回前要恢複堆棧，先回收本地變量占用的記憶體(ESP=ESP+3*4)，然後取出傳回位址，填入EIP寄存器，回收先前壓入參數占用的記憶體(ESP=ESP+3*4)，繼續執行調用者的代碼。參見下列彙編代碼：
;--------------func 函數的彙編代碼-------------------
:00401000 83EC0C sub esp, 0000000C //建立本地變量的記憶體空間
:00401003 8B442410 mov eax, dword ptr [esp+10]
:00401007 8B4C2414 mov ecx, dword ptr [esp+14]
:0040100B 8B542418 mov edx, dword ptr [esp+18]
:0040100F 89442400 mov dword ptr [esp], eax
:00401013 8D442410 lea eax, dword ptr [esp+10]
:00401017 894C2404 mov dword ptr [esp+04], ecx
……………………（省略若幹代碼）
:00401075 83C43C add esp, 0000003C ;恢複堆棧，回收本地變量的記憶體空間
:00401078 C3 ret 000C ;函數傳回，恢複參數占用的記憶體空間
;如果是“__cdecl”的話，這裡是“ret”，堆棧将由調用者恢複
;-------------------函數結束-------------------------
;--------------主程式調用func函數的代碼--------------
:00401080 6A03 push 00000003 //壓入參數param3
:00401082 6A02 push 00000002 //壓入參數param2
:00401084 6A01 push 00000001 //壓入參數param1
:00401086 E875FFFFFF call 00401000 //調用func函數
;如果是“__cdecl”的話，将在這裡恢複堆棧，“add esp, 0000000C”
聰明的讀者看到這裡，差不多就明白緩沖溢出的原理了。先來看下面的代碼：
#include <stdio.h>
#include <string.h>
void __stdcall func()
{
char lpBuff[8]="\0";
strcat(lpBuff,"AAAAAAAAAAA");
return;
}
int main()
{
func();
return 0;
}
編譯後執行一下回怎麼樣？哈，“"0x00414141"指令引用的"0x00000000"記憶體。該記憶體不能為"read"。”，“非法操作”喽！"41"就是"A"的16進制的ASCII碼了，那明顯就是strcat這句出的問題了。"lpBuff"的大小隻有8位元組，算進結尾的\0，那strcat最多隻能寫入7個"A"，但程式實際寫入了11個"A"外加1個\0。再來看看上面那幅圖，多出來的4個位元組正好覆寫了RET的所在的記憶體空間，導緻函數傳回到一個錯誤的記憶體位址，執行了錯誤的指令。如果能精心構造這個字元串，使它分成三部分，前一部份僅僅是填充的無意義資料以達到溢出的目的，接着是一個覆寫RET的資料，緊接着是一段shellcode，那隻要着個RET位址能指向這段shellcode的第一個指令，那函數傳回時就能執行shellcode了。但是軟體的不同版本和不同的運作環境都可能影響這段shellcode在記憶體中的位置，那麼要構造這個RET是十分困難的。一般都在RET和shellcode之間填充大量的NOP指令，使得exploit有更強的通用性。
├———————┤<—低端記憶體區域
│ …… │
├———————┤<—由exploit填入資料的開始
│ │
│ buffer │<—填入無用的資料
│ │
├———————┤
│ RET │<—指向shellcode，或NOP指令的範圍
├———————┤
│ NOP │
│ …… │<—填入的NOP指令，是RET可指向的範圍
│ NOP │
├———————┤
│ │
│ shellcode │
│ │
├———————┤<—由exploit填入資料的結束
│ …… │
├———————┤<—高端記憶體區域
windows下的動态資料除了可存放在棧中，還可以存放在堆中。了解C++的朋友都知道，C++可以使用new關鍵字來動态配置設定記憶體。來看下面的C++代碼：
#include <stdio.h>
#include <iostream.h>
#include <windows.h>
void func()
{
char *buffer=new char[128];
char bufflocal[128];
static char buffstatic[128];
printf("0x%08x\n",buffer); //列印堆中變量的記憶體位址
printf("0x%08x\n",bufflocal); //列印本地變量的記憶體位址
printf("0x%08x\n",buffstatic); //列印靜态變量的記憶體位址
}
void main()
{
func();
return;
}
程式執行結果為：
0x004107d0
0x0012ff04
0x004068c0
可以發現用new關鍵字配置設定的記憶體即不在棧中，也不在靜态資料區。VC編譯器是通過windows下的“堆(heap)”來實作new關鍵字的記憶體動态配置設定。在講“堆”之前，先來了解一下和“堆”有關的幾個API函數：
HeapAlloc 在堆中申請記憶體空間
HeapCreate 建立一個新的堆對象
HeapDestroy 銷毀一個堆對象
HeapFree 釋放申請的記憶體
HeapWalk 枚舉堆對象的所有記憶體塊
GetProcessHeap 取得程序的預設堆對象
GetProcessHeaps 取得程序所有的堆對象
LocalAlloc
GlobalAlloc
當程序初始化時，系統會自動為程序建立一個預設堆，這個堆預設所占記憶體的大小為1M。堆對象由系統進行管理，它在記憶體中以鍊式結構存在。通過下面的代碼可以通過堆動态申請記憶體空間：
HANDLE hHeap=GetProcessHeap();
char *buff=HeapAlloc(hHeap,0,8);
其中hHeap是堆對象的句柄，buff是指向申請的記憶體空間的位址。那這個hHeap究竟是什麼呢？它的值有什麼意義嗎？看看下面這段代碼吧：
#pragma comment(linker,"/entry:main") //定義程式的入口
#include <windows.h>
_CRTIMP int (__cdecl *printf)(const char *, ...); //定義STL函數printf
void main()
{
HANDLE hHeap=GetProcessHeap();
char *buff=HeapAlloc(hHeap,0,0x10);
char *buff2=HeapAlloc(hHeap,0,0x10);
HMODULE hMsvcrt=LoadLibrary("msvcrt.dll");
printf=(void *)GetProcAddress(hMsvcrt,"printf");
printf("0x%08x\n",hHeap);
printf("0x%08x\n",buff);
printf("0x%08x\n\n",buff2);
}
執行結果為：
0x00130000
0x00133100
0x00133118
hHeap的值怎麼和那個buff的值那麼接近呢？其實hHeap這個句柄就是指向HEAP首部的位址。在程序的使用者區存着一個叫PEB(程序環境塊)的結構，這個結構中存放着一些有關程序的重要資訊，其中在PEB首位址偏移0x18處存放的ProcessHeap就是程序預設堆的位址，而偏移0x90處存放了指向程序所有堆的位址清單的指針。windows有很多API都使用程序的預設堆來存放動态資料，如windows 2000下的所有ANSI版本的函數都是在預設堆中申請記憶體來轉換ANSI字元串到Unicode字元串的。對一個堆的通路是順序進行的，同一時刻隻能有一個線程通路堆中的資料，當多個線程同時有通路要求時，隻能排隊等待，這樣便造成程式執行效率下降。
最後來說說記憶體中的資料對齊。所位資料對齊，是指資料所在的記憶體位址必須是該資料長度的整數倍，DWORD資料的記憶體起始位址能被4除盡，WORD資料的記憶體起始位址能被2除盡，x86 CPU能直接通路對齊的資料，當他試圖通路一個未對齊的資料時，會在内部進行一系列的調整，這些調整對于程式來說是透明的，但是會降低運作速度，是以編譯器在編譯程式時會盡量保證資料對齊。同樣一段代碼，我們來看看用VC、Dev-C++和lcc三個不同編譯器編譯出來的程式的執行結果：
#include <stdio.h>
int main()
{
int a;
char b;
int c;
printf("0x%08x\n",&a);
printf("0x%08x\n",&b);
printf("0x%08x\n",&c);
return 0;
}
這是用VC編譯後的執行結果：
0x0012ff7c
0x0012ff7b
0x0012ff80
變量在記憶體中的順序：b(1位元組)-a(4位元組)-c(4位元組)。
這是用Dev-C++編譯後的執行結果：
0x0022ff7c
0x0022ff7b
0x0022ff74
變量在記憶體中的順序：c(4位元組)-中間相隔3位元組-b(占1位元組)-a(4位元組)。
這是用lcc編譯後的執行結果：
0x0012ff6c
0x0012ff6b
0x0012ff64
變量在記憶體中的順序：同上。
三個編譯器都做到了資料對齊，但是後兩個編譯器顯然沒VC“聰明”，讓一個char占了4位元組，浪費記憶體哦。
基礎知識：
堆棧是一種簡單的資料結構，是一種隻允許在其一端進行插入或删除的線性表。允許插入或删除操作的一端稱為棧頂，另一端稱為棧底，對堆棧的插入和删除操作被稱為入棧和出棧。有一組CPU指令可以實作對程序的記憶體實作堆棧通路。其中，POP指令實作出棧操作，PUSH指令實作入棧操作。CPU的ESP寄存器存放目前線程的棧頂指針，EBP寄存器中儲存目前線程的棧底指針。CPU的EIP寄存器存放下一個CPU指令存放的記憶體位址，當CPU執行完目前的指令後，從EIP寄存器中讀取下一條指令的記憶體位址，然後繼續執行。
參考：《Windows下的HEAP溢出及其利用》by: isno
《windows核心程式設計》by: Jeffrey Richter
摘要： 讨論常見的堆性能問題以及如何防範它們。（共 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 也有改進的堆配置設定程式。）
使用配置設定高速緩存
配置設定高速緩存允許高速緩存配置設定的塊，以便将來重用。這能夠減少對程序堆（或全局堆）的配置設定/釋放調用的次數，也允許最大限度的重用曾經配置設定的塊。另外，配置設定高速緩存允許收集統計資訊,以便較好地了解對象在較高層次上的使用。
典型地，自定義堆配置設定程式在程序堆的頂部實作。自定義堆配置設定程式與系統堆的行為很相似。主要的差别是它在程序堆的頂部為配置設定的對象提供高速緩存。高速緩存設計成一套固定大小（如 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.。工作之外，他喜歡閱讀、打排球和家庭烹饪。
http://community.csdn.net/Expert/FAQ/FAQ_Index.asp?id=172835
我在學習對象的生存方式的時候見到一種是在堆棧(stack)之中，如下
CObject object;
還有一種是在堆(heap)中 如下
CObject* pobject=new CObject();
請問
（1）這兩種方式有什麼差別？
（2）堆棧與堆有什麼差別？？
---------------------------------------------------------------
1) about stack, system will allocate memory to the instance of object automatically, and to the
heap, you must allocate memory to the instance of object with new or malloc manually.
2) when function ends, system will automatically free the memory area of stack, but to the
heap, you must free the memory area manually with free or delete, else it will result in memory
leak.
3)棧記憶體配置設定運算内置于處理器的指令集中，效率很高，但是配置設定的記憶體容量有限。
4）堆上配置設定的記憶體可以有我們自己決定，使用非常靈活。
---------------------------------------------------------------
![POJ 1284 Primitive Roots (歐拉函數&原根定理)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)