C++應(yīng)用程序性能優(yōu)化之內(nèi)存池

1、引言本書主要針對的是C+程序的性能優(yōu)化，深入介紹C+程序性能優(yōu)化的方法和實例。全書由4個篇組成，第1篇介紹C+語言的對彖模型，該篇是優(yōu)化C+程序的慕礎(chǔ)；第2篇主要針對如何優(yōu)化C+程序的內(nèi)存使用；第3篇介紹如何優(yōu)化程序的啟動性能；第4篇介紹了三類性能優(yōu)化工具，即內(nèi)存分析工具、性能分析工具和I/O檢測工具，它們是測暈程序性能的利器。本章首先簡單介紹門定義內(nèi)存池性能優(yōu)化的原理，然后列舉軟件開發(fā)中常用的內(nèi)存池的不同類型，并給出具體實現(xiàn)的實例。6.1自定義內(nèi)存池性能優(yōu)化的原理如前所述，讀者C經(jīng)了解到堆和棧的區(qū)別。而在編程實踐中，不可避免地要人最用到堆上的內(nèi)存。例如在程序中維護(hù)一個鏈表的數(shù)據(jù)結(jié)構(gòu)時，每次新

2、增或者刪除一個鏈表的節(jié)點(diǎn)，都需要從內(nèi)存堆上分配或者釋放一定的內(nèi)存；在維護(hù)一個動態(tài)數(shù)組時，如果動態(tài)數(shù)組的人小不能滿足程序需要時，也要在內(nèi)存堆上分配新的內(nèi)存空間。6.1.1默認(rèn)內(nèi)存管理函數(shù)的不足利用默認(rèn)的內(nèi)存管理函數(shù)new/delete或malloc/free在堆上分配和釋放內(nèi)存會有一些額外的開銷。系統(tǒng)在接收到分配一定人小內(nèi)存的請求時，首先查找內(nèi)部維護(hù)的內(nèi)存空閑塊表，并且需要根據(jù)一定的算法（例如分配最先找到的不小于中請人小的內(nèi)存塊給請求者，或者分配最適于中請人小的內(nèi)存塊，或者分配最人空閑的內(nèi)存塊等）找到合適人小的空閑內(nèi)存塊。如果該空閑內(nèi)存塊過人，還需要切割成C分配的部分和較小的空閑塊。然后系統(tǒng)更新

3、內(nèi)存空閑塊表，完成一次內(nèi)存分配。類似地，在釋放內(nèi)存時，系統(tǒng)把釋放的內(nèi)存塊重新加入到空閑內(nèi)存塊表中。如果有可能的話，可以把和鄰的空閑塊合并成較人的空閑塊。默認(rèn)的內(nèi)存管理函數(shù)還考慮到多線程的應(yīng)用，需要在每次分配和釋放內(nèi)存時加鎖，同樣增加了開銷?？梢姡绻麘?yīng)用程序頻繁地在堆上分配和釋放內(nèi)存，則會導(dǎo)致性能的損失。并且會使系統(tǒng)中出現(xiàn)人量的內(nèi)存碎片，降低內(nèi)存的利用率。默認(rèn)的分配和釋放內(nèi)存算法門然也考慮了性能，然而這些內(nèi)存管理算法的通用版本為了應(yīng)付更復(fù)雜、更廣泛的情況，需要做更多的額外工作。而對于某一個具體的應(yīng)用程序來說，適合門身特定的內(nèi)存分配釋放模式的門定義內(nèi)存池則可以獲得更好的性能。6.1.2內(nèi)存池的定

4、義和分類門定義內(nèi)存池的思想通過這個池字表露無疑，應(yīng)用程序可以通過系統(tǒng)的內(nèi)存分配調(diào)用預(yù)先一次性中請適當(dāng)人小的內(nèi)存作為一個內(nèi)存池，Z后應(yīng)用程序門己對內(nèi)存的分配和釋放則可以通過這個內(nèi)存池來完成。只有當(dāng)內(nèi)存池人小需要動態(tài)擴(kuò)展時，才需要再調(diào)用系統(tǒng)的內(nèi)存分配函數(shù)，其他時間對內(nèi)存的一切操作都在應(yīng)用程序的學(xué)控Z中。應(yīng)用程序門定義的內(nèi)存池根據(jù)不同的適用場景又有不同的類型。從線程安全的角度來分，內(nèi)存池可以分為單線程內(nèi)存池和多線程內(nèi)存池。單線程內(nèi)存池整個生命周期只被一個線程使用，因而不需要考慮互斥訪問的問題；多線程內(nèi)存池有可能被多個線程共亨，因此則需要在每次分配和釋放內(nèi)存時加鎖。和對而言,單線程內(nèi)存池性能更高，而多

5、線程內(nèi)存池適用范圍更廣。從內(nèi)存池可分配內(nèi)存單元人小來分，可以分為固定內(nèi)存池和可變內(nèi)存池。所謂固定內(nèi)存池是指應(yīng)用程序每次從內(nèi)存池中分配出來的內(nèi)存單元人小事先C經(jīng)確定，是固定不變的；而可變內(nèi)存池則每次分配的內(nèi)存單元人小可以按需變化，應(yīng)用范圍更廣,而性能比固定內(nèi)存池要低。6.1.3內(nèi)存池工作原理示例下面以固定內(nèi)存池為例說明內(nèi)存池的工作原理，如圖6-1所示。圖6-1固定內(nèi)存池固定內(nèi)存池由一系列固定人小的內(nèi)存塊組成，每一個內(nèi)存塊又包含了固定數(shù)最和人小的內(nèi)存單元。如圖6-1所示，該內(nèi)存池一共包含4個內(nèi)存塊。在內(nèi)存池初次生成時，只向系統(tǒng)中請了一個內(nèi)存塊，返回的指針作為整個內(nèi)存池的頭指針。Z后隨著應(yīng)用程序?qū)?nèi)

6、存的不斷需求，內(nèi)存池判斷需要動態(tài)擴(kuò)人時，才再次向系統(tǒng)中請新的內(nèi)存塊，并把所有這些內(nèi)存塊通過指針鏈接起來。對于操作系統(tǒng)來說，它C經(jīng)為該應(yīng)用程序分配了4個等人小的內(nèi)存塊。由于是人小固定的，所以分配的速度比較快；而對于應(yīng)用程序來說，其內(nèi)存池開辟了一定大小，內(nèi)存池內(nèi)部卻還有剩余的空間。例如放人來看第4個內(nèi)存塊，其中包含一部分內(nèi)存池塊頭信息和3個大小札I等的內(nèi)存池單元。單元1和單元3是空閑的，單元2C經(jīng)分配。當(dāng)應(yīng)用程序需要通過該內(nèi)存池分配一個單元人小的內(nèi)存時，只需要簡單遍歷所有的內(nèi)存池塊頭信息，快速定位到還有空閑單元的那個內(nèi)存池塊。然后根據(jù)該塊的塊頭信息直接定位到第1個空閑的單元地址，把這個地址返回，并

7、且標(biāo)記下一個空閑單元即可；當(dāng)應(yīng)用程序釋放某一個內(nèi)存池單元時，直接在對應(yīng)的內(nèi)存池塊頭信息中標(biāo)記該內(nèi)存單元為空閑單元即可?？梢娕c系統(tǒng)管理內(nèi)存相比，內(nèi)存池的操作非常迅速，它在性能優(yōu)化方面的優(yōu)點(diǎn)主要如下。（1）針對特殊情況，例如需要頻繁分配釋放固定人小的內(nèi)存對彖時，不需要復(fù)雜的分配算法和多線程保護(hù)。也不需要維護(hù)內(nèi)存空閑表的額外開銷，從而獲得較高的性能。（2）由于開辟一定數(shù)暈的連續(xù)內(nèi)存空間作為內(nèi)存池塊，因而一定程度上提高了程序局部性，提升了程序性能。（3）比較容易控制頁邊界對齊和內(nèi)存字節(jié)對齊，沒有內(nèi)存碎片的問題?；仨撌?2個內(nèi)存池的實現(xiàn)實例本節(jié)分析在某個人型應(yīng)用程序?qū)嶋H應(yīng)用到的一個內(nèi)存池實現(xiàn)，并詳細(xì)講解

8、其使用方法與工作原理。這是一個應(yīng)用于單線程環(huán)境且分配單元大小固定的內(nèi)存池，一般用來為執(zhí)行時會動態(tài)頻繁地創(chuàng)建且可能會被多次創(chuàng)建的類對象或者結(jié)構(gòu)體分配內(nèi)存。本節(jié)首先講解該內(nèi)存池的數(shù)據(jù)結(jié)構(gòu)聲明及圖示，接著描述其原理及行為特征。然后逐一講解實現(xiàn)細(xì)節(jié)，最后介紹如何在實際程序中應(yīng)用此內(nèi)存池，并與使用普通內(nèi)存函數(shù)中請內(nèi)存的程序性能作比較。6.2.1內(nèi)部構(gòu)造內(nèi)存池類MemoryPoo1的聲明如卜：classMemoryPoolprivate:MemoryBlock*USHORTUSHORTUSHORTpBlock;nUnitSize;nlnitSize;nGrowSize;public:MemoryPool(

9、USHORTnUnitSize,USHORTnlnitSize=1024,USHORTnGrowSize=256);MemoryPool();void*voidAlloc();Free(void*p);MemoryBlock為內(nèi)存池中附著在真正用來為內(nèi)存請求分配內(nèi)存的內(nèi)存塊頭部的結(jié)構(gòu)體，它描述了與Z聯(lián)系的內(nèi)存塊的使用信息：structMemoryBlockUSHORTUSHORTUSHORTUSHORTMemoryBlock*charnSize;nFree;nFirst;nDummyAlignl;pNext;aDataEl;staticvoid*operatornew(size_t,USHOR

10、TnTypes,USHORTnUnitSize)return:operatornew(sizeof(MemoryBlock)+nTypes*nUnitSize);staticvoidoperatordelete(void*p,size_t):：operatordelete(p);USHORTnUnitSize二USHORTnUnitSize二0);；此內(nèi)存池的數(shù)據(jù)結(jié)構(gòu)如圖6-2所示。MemoiyBlock圖6-2內(nèi)存池的數(shù)據(jù)結(jié)構(gòu)MemoiyBlock圖6-2內(nèi)存池的數(shù)據(jù)結(jié)構(gòu)MemoiyPoolMemoiyBlock6.2.2總體機(jī)制此內(nèi)存池的總體機(jī)制如下。（1）在運(yùn)行過程中，MemoryPoo

11、l內(nèi)存池可能會有多個用來滿足內(nèi)存中請請求的內(nèi)存塊，這些內(nèi)存塊是從進(jìn)程堆中開辟的一個較人的連續(xù)內(nèi)存區(qū)域，它由一個MemoryBlock結(jié)構(gòu)體和多個可供分配的內(nèi)存單元組成，所有內(nèi)存塊組成了一個內(nèi)存塊鏈表，MemoryPool的pBlock是這個鏈表的頭。對每個內(nèi)存塊，都可以通過其頭部的MemoryBlock結(jié)構(gòu)體的pNext成員訪問緊跟在其后面的那個內(nèi)存塊。（2）每個內(nèi)存塊由兩部分組成，即一個MemoryBlock結(jié)構(gòu)體和多個內(nèi)存分配單元。這些內(nèi)存分配單元人小固定（由MemoryPool的nUnitSize表示），MemoryBlock結(jié)構(gòu)體并不維護(hù)那些C經(jīng)分配的單元的信息：相反，它只維護(hù)沒有分配

12、的門由分配單元的信息。它有兩個成員比較重要：nFree和nFirst。nFree記錄這個內(nèi)存塊中還有多少個門由分配單元，而nFirst則記錄下一個可供分配的單元的編號。每一個門由分配單元的頭兩個字節(jié)（即一個USHORT型值）記錄了緊跟它Z后的下一個門由分配單元的編號，這樣，通過利用每個門由分配單元的頭兩個字節(jié)，一個MemoryBlock中的所有自由分配單元被鏈接起來。（3）當(dāng)有新的內(nèi)存請求到來時,MemoryPool會通過pBlock遍歷MemoryBlock鏈表,直到找到某個MemoryBlock所在的內(nèi)存塊，其中還有門由分配單元（通過檢測MemoryBlock結(jié)構(gòu)體的nFree成員是否人于

13、0）。如果找到這樣的內(nèi)存塊，取得其MemoryBlock的nFirst值（此為該內(nèi)存塊中第1個可供分配的門由單元的編號）。然后根據(jù)這個編號定位到該門由分配單元的起始位置（因為所有分配單元人小固定,因此每個分配單元的起始位置都可以通過編號分配單元人小來偏移定位），這個位置就是用來滿足此次內(nèi)存中請請求的內(nèi)存的起始地址。但在返回這個地址前，需要首先將該位置開始的頭兩個字節(jié)的值（這兩個字節(jié)值記錄其之后的下一個門由分配單元的編號）賦給本內(nèi)存塊的MemoryBlock的nFirst成員。這樣下一次的請求就會用這個編號對應(yīng)的內(nèi)存單元來滿足，同時將此內(nèi)存塊的MemoryBlock的nFree遞減1,然后才將剛

14、才定位到的內(nèi)存單元的起始位置作為此次內(nèi)存請求的返回地址返回給調(diào)用者。（4）如果從現(xiàn)有的內(nèi)存塊中找不到一個門由的內(nèi)存分配單元（當(dāng)?shù)?次請求內(nèi)存,以及現(xiàn)有的所有內(nèi)存塊中的所有內(nèi)存分配單元都匕經(jīng)被分配時會發(fā)生這種情形），MemoryPool就會從進(jìn)程堆中中請一個內(nèi)存塊（這個內(nèi)存塊包括一個MemoryBlock結(jié)構(gòu)體，及緊鄰其后的多個內(nèi)存分配單元，假設(shè)內(nèi)存分配單元的個數(shù)為n,n可以取值MemoryPool中的nInitSize或者nGrowSize）,中請完后，并不會立刻將其中的一1個分配單元分配岀去，而是需要首先初始化這個內(nèi)存塊。初始化的操作包括設(shè)置MemoryBlock的nSize為所有內(nèi)存分配單

15、元的人?。ㄗ⒁?，并不包括MemoryBlock結(jié)構(gòu)體的人?。?、nFree為n-l（注意，這里是n-l而不是n,因為此次新內(nèi)存塊就是為了滿足一次新的內(nèi)存請求而中請的，馬上就會分配一塊門由存儲單元出去，如果設(shè)為n-1,分配一個門由存儲單元后無須再將n遞減1）,nFirst為1（C經(jīng)知道nFirst為下一個可以分配的門由存儲單元的編號。為1的原因與nFree為nl相同，即立即會將編號為0的門由分配單元分配出去?，F(xiàn)在設(shè)為1,其后不用修改nFirst的值），MemoryBlock的構(gòu)造需要做更重要的事情，即將編號為0的分配單元Z后的所有門由分配單元鏈接起來。如前所述，每個門由分配單元的頭兩個字節(jié)用來存儲

16、下一個門由分配單元的編號。另外，因為每個分配單元人小固定，所以可以通過其編號和單元人?。∕emoryPool的nUnitSize成員）的乘積作為偏移值進(jìn)彳亍定位?，F(xiàn)在唯一的問題是定位從哪個地址開始？答案是MemoryBlock的aDataEl成員開始。因為aDatall實際上是屬于MemoryBlock結(jié)構(gòu)體的（MemoryBlock結(jié)構(gòu)體的最后一個字節(jié)），所以實質(zhì)上，MemoryBlock結(jié)構(gòu)體的最后一個字節(jié)也用做被分配岀去的分配單元的一部分。因為整個內(nèi)存塊由MemoryBlock結(jié)構(gòu)體和整數(shù)個分配單元組成，這意味著內(nèi)存塊的最后一個字節(jié)會被浪費(fèi)，這個字節(jié)在圖6-2中用位于兩個內(nèi)存的最后部分的

17、濃黑背景的小塊標(biāo)識。確定了分配單元的起始位置后，將門由分配單元鏈接起來的工作就很容易了。即從aData位置開始，每隔nUnitSize人小取其頭兩個字節(jié)，記錄其Z后的門由分配單元的編號。因為剛開始所有分配單元都是門由的，所以這個編號就是門身編號加1,即位置上緊跟其后的單元的編號。初始化后，將此內(nèi)存塊的第1個分配單元的起始地址返回，C經(jīng)知道這個地址就是aDatao（5）當(dāng)某個被分配的單元因為delete需要回收時，該單元并不會返回給進(jìn)程堆，而是返回給MemoryPoolo返回時，MemoryPool能夠知道該單元的起始地址。這時,MemoryPool開始遍歷其所維護(hù)的內(nèi)存塊鏈表，判斷該單元的起始

18、地址是否落在某個內(nèi)存塊的地址范圍內(nèi)。如果不在所有內(nèi)存地址范圍內(nèi)，則這個被回收的單元不屬于這個MemoryPool：如果在菜個內(nèi)存塊的地址范圍內(nèi)，那么它會將這個剛剛回收的分配單元加到這個內(nèi)存塊的MemoryBlock所維護(hù)的門由分配單元鏈表的頭部，同時將其nFree值遞增1?；厥蘸?，考慮到資源的有效利用及后續(xù)操作的性能，內(nèi)存池的操作會繼續(xù)判斷：如果此內(nèi)存塊的所有分配單元都是門由的，那么這個內(nèi)存塊就會從MemoryPool中被移出并作為一個整體返回給進(jìn)程堆;如果該內(nèi)存塊4還有非門由分配單元，這時不能將此內(nèi)存塊返回給進(jìn)程堆。但是因為剛剛有一個分配單元返回給了這個內(nèi)存塊，即這個內(nèi)存塊有門由分配單元可供

19、下次分配，因此它會被移到MemoryPool維護(hù)的內(nèi)存塊的頭部。這樣下次的內(nèi)存請求到來，MemoryPool遍歷其內(nèi)存塊鏈表以尋找門由分配單元時，第1次尋找就會找到這個內(nèi)存塊。因為這個內(nèi)存塊確實有自由分配單元，這樣可以減少M(fèi)emoryPool的遍歷次數(shù)。綜上所述，每個內(nèi)存池（MemoryPool）維護(hù)一個內(nèi)存塊鏈表（單鏈表），每個內(nèi)存塊由一個維護(hù)該內(nèi)存塊信息的塊頭結(jié)構(gòu)（MemoryBlock）和多個分配單元組成，塊頭結(jié)構(gòu)MemoryBlock則進(jìn)一步維護(hù)一個該內(nèi)存塊的所有門由分配單元組成的鏈表這個鏈表不是通過指向下一個門由分配單元的指針鏈接起來的，而是通過下一個H由分配單元的編號鏈接起來，這個

20、編號值存儲在該H由分配單元的頭兩個字節(jié)中。另外，第1個門由分配單元的起始位置并不是MemoryBlock結(jié)構(gòu)體后面的第1個地址位置，而是MemoryBlock結(jié)構(gòu)體內(nèi)部的最后一個字節(jié)aData（也可能不是最后一個，因為考慮到字節(jié)對齊的問題），即分配單元實際上往前面錯了一位。又因為MemoryBlock結(jié)構(gòu)體后面的空間剛好是分配單元的整數(shù)倍,這樣依次錯位下去,內(nèi)存塊的最后一個字節(jié)實際沒有被利用。這么做的一個原因也是考慮到不同平臺的移植問題，因為不同平臺的對齊方式可能不盡相同。即當(dāng)中請MemoryBlock人小內(nèi)存時，可能會返回比其所有成員人小總和還要大一些的內(nèi)存。最后的幾個字節(jié)是為了補(bǔ)齊，而使得

21、aData成為第1個分配單元的起始位置，這樣在對齊方式不同的各種平臺上都可以工作。6.2.3細(xì)節(jié)剖析有了上述的總體印象后，本節(jié)來仔細(xì)剖析其實現(xiàn)細(xì)節(jié)。MemoryPool的構(gòu)造如下:MemoryPool:MemoryPool(USHORT_nUnitSize,USHORTnlnitSize,USHORTnGrowSize)pBlock二NULL;nlnitSize=_nInitSize;nGrowSize=_nGrowSize;(MEMP00L.ALIGNMENT-1)&if(_nUnitSize4)nUnitSize二(_nUnitSize(MEIPOOL_ALIGNMENT-1):(MEMP

22、00L.ALIGNMENT-1)&elseif(_nUnitSizenFree、pMyBlock=pMyBlock-pNext;if(pMyBlock)char*pFree=pMyBlock-aData+(pMyBlock-nFirst*nUnitSize);pMyB1ock-nFirst二*(USHORT*)pFree);pIyBlocknFree-一；return(void*)pFree;elseftif(!nGrowSize)returnNULL;pMyBlock二new(nGrowSize,nUnitSize)FixedMemBlock(nGrowSize,nUnitSize);if(

23、!pMyBlock)returnNULL;pMyB1ock-pNext=pBlock;pBlock=pMyBlock;return(void*)(pMyBlock-aData);MemoryPool滿足內(nèi)存請求的步驟主要由四步組成。處首先判斷內(nèi)存池當(dāng)前內(nèi)存塊鏈表是否為空，如果為空，則意味著這是第1次內(nèi)存中請請求。這時，從進(jìn)程堆中中請一個分配單元個數(shù)為nInitSize的內(nèi)存塊，并初始化該內(nèi)存塊（主要初始化MemoryBlock結(jié)構(gòu)體成員，以及創(chuàng)建初始的廣I由分配單元鏈表，下面會詳細(xì)分析其代碼）。如果該內(nèi)存塊中請成功，并初始化完畢，返回第1個分配單元給調(diào)用函數(shù)。第1個分配單元以MemoryBlo

24、ck結(jié)構(gòu)體內(nèi)的最后一個字節(jié)為起始地址。處的作用是當(dāng)內(nèi)存池中匕有內(nèi)存塊（即內(nèi)存塊鏈表不為空）時遍歷該內(nèi)存塊鏈表,尋找還有門由分配單元的內(nèi)存塊。處檢查如果找到還有廣|由分配單元的內(nèi)存塊，則定位到該內(nèi)存塊現(xiàn)在可以用的門由分配單元處。定位以MemoryBlock結(jié)構(gòu)體內(nèi)的最后一個字節(jié)位置aData為起始位賢，以MemoryPool的nUnitSize為步長來進(jìn)行。找到后，需要修改MemoryBlock的nFree信息（剩下來的門由分配單元比原來減少了一個），以及修改此內(nèi)存塊的門由存儲單元鏈表的信息。在找到的內(nèi)存塊中，pMyBlock-nFirst為該內(nèi)存塊中門由存儲單元鏈表的表頭，其下一個門由存儲單元

25、的編號存放在PMyBlock-nFirst指示的門由存儲單元（亦即剛才定位到的門由存儲單元）的頭兩個字節(jié)。通過剛才定位到的位置，取其頭兩個字節(jié)的值，賦給PMyBlock-nFirst,這就是此內(nèi)存塊的門由存儲單元鏈表的新的表頭，即下一次分配出去的門由分配單元的編號（如果nFree人于零的話）。修改維護(hù)信息后，就可以將剛才定位到的門由分配單元的地址返回給此次中請的調(diào)用函數(shù)。注意，因為這個分配單元C經(jīng)被分配，而內(nèi)存塊無須維護(hù)C分配的分配單元，因此該分配單元的頭兩個字節(jié)的信息C經(jīng)沒有用處。換個角度看，這個門由分配單元返回給調(diào)用函數(shù)后，調(diào)用函數(shù)如何處置這塊內(nèi)存，內(nèi)存池?zé)o從知曉，也無須知曉。此分配單元在

26、返回給調(diào)用函數(shù)時，其內(nèi)容對于調(diào)用函數(shù)來說是無意義的。因此兒乎可以肯定調(diào)用函數(shù)在用這個單元的內(nèi)存時會覆蓋其原來的內(nèi)容，即頭兩個字節(jié)的內(nèi)容也會被抹去。因此每個存儲單元并沒有因為需要鏈接而引入多余的維護(hù)信息，而是直接利用單元內(nèi)的頭兩個字節(jié)，當(dāng)其分配后，頭兩個字節(jié)也可以被調(diào)用函數(shù)利用。而在門由狀態(tài)時，則用來存放維護(hù)信息，即下一個門由分配單元的編號，這是一個有效利用內(nèi)存的好例子。處表示在處遍歷時，沒有找到還有門由分配單元的內(nèi)存塊，這時，需要重新向進(jìn)程堆中請一個內(nèi)存塊。因為不是第一次中請內(nèi)存塊，所以中請的內(nèi)存塊包含的分配單元個數(shù)為nGrowSize,而不再是nlnitSize。與處和同，先做這個新中請內(nèi)存

27、塊的初始化工作，然后將此內(nèi)存塊插入MemoryPool的內(nèi)存塊鏈表的頭部，再將此內(nèi)存塊的第1個分配單元返回給調(diào)用函數(shù)。將此新內(nèi)存塊插入內(nèi)存塊鏈表的頭部的原因是該內(nèi)存塊還有很多可供分配的門由分配單元（除非nGrowSize等于1,這應(yīng)該不太可能。因為內(nèi)存池的含義就是一次性地從進(jìn)程堆中中請一人塊內(nèi)存，以供后續(xù)的多次中請），放在頭部可以使得在下次收到內(nèi)存中請時，減少處對內(nèi)存塊的遍歷時間?？梢杂脠D62的MemoryPool來展示MemoryPool:Alloc的過程。圖6-3是某個時刻MemoryPool的內(nèi)部狀態(tài)。圖6-3某個時刻MemoryPool的內(nèi)部狀態(tài)MernoiyPoolMemolyBlo

28、ckMeraoiyBlock因為MemoryPool的內(nèi)存塊鏈表不為空，因此會遍歷其內(nèi)存塊鏈表。又因為第1個內(nèi)存塊里有門由的分配單元，所以會從第1個內(nèi)存塊中分配。檢査nFirst,其值為m,這時pBlock-aData+（pBlock-nFirst*nUnitSize）定位到編號為皿的門由分配單元的起始位置（用pFree表示）。在返回pFreeZ前，需要修改此內(nèi)存塊的維護(hù)信息。首先將nFree遞減1,然后取得pFree處開始的頭兩個字節(jié)的值（需要說明的是，這里aData處值為k。其實不是這一個字節(jié)。而是以aData和緊跟其后的另外一個字節(jié)合在一起構(gòu)成的一個USHORT的值，不可誤會）。發(fā)現(xiàn)為心

29、這時修改pBlock的nFirst為k。然后，返回pFreeo此時MemoryPool的結(jié)構(gòu)如圖6-4所示。圖6-4MemoryPool的結(jié)構(gòu)MeraolyPoolMernoiyBlockpBLockriSizeriSizenUriitSizenUriitSizeiiFreeiiFreerdnitSizerdnitSizenFiist:knGrowSizenGrowSizenFiist:kpNext張唸N滋瑟滋必沁么，:MernoiyBLock00圖6-4MemoryPool的結(jié)構(gòu)MeraolyPoolMernoiyBlockpBLockriSizeriSizenUriitSizenUriit

30、SizeiiFreeiiFreerdnitSizerdnitSizenFiist:knGrowSizenGrowSizenFiist:kpNext張唸N滋瑟滋必沁么，:MernoiyBLock00可以看到，原來的第1個可供分配的單元(m編號處)C經(jīng)顯示為被分配的狀態(tài)。而pBlock的nFirstC經(jīng)指向原來m單元下一個門由分配單元的編號，即koMemoryPool回收內(nèi)存時：voidMemoryPool:Free(void*pFree)MemoryBlock*pMyBlock=pBlock;while(ULONG)pMyBlock-aData(ULONG)pFree)|(L10NG)pFree

31、=(ULONG)pMyBlock-aData+pMyBlock-nSize)(DpMyBlock-nFree+;*(USHORT*)pFree)=pMyBlock-nFirst;pMyBlock-nFirst=(USHORT)(ULONG)pFree-(ULONG)(pBlock-aData)/nUnitSize);if(pMyBlock-nFree*nUnitSize=pMyB1ock-nSize)else如前所述，回收分配單元時，可能會將整個內(nèi)存塊返回給進(jìn)程堆，也可能將被回收分配單元所屬的內(nèi)存塊移至內(nèi)存池的內(nèi)存塊鏈表的頭部。這兩個操作都需要修改鏈表結(jié)構(gòu)。這時需要知道該內(nèi)存塊在鏈表中前一個位

32、置的內(nèi)存塊。處遍歷內(nèi)存池的內(nèi)存塊鏈表，確定該待回收分配單元(pFree)落在哪一個內(nèi)存塊的指針范圍內(nèi)，通過比較指針值來確定。運(yùn)行到處，pMyBlock即找到的包含pFree所指向的待回收分配單元的內(nèi)存塊(當(dāng)然，這時應(yīng)該還需要檢査pMyBlock為NULL時的情形，即pFree不屬于此內(nèi)存池的范圍，因此不能返回給此內(nèi)存池，讀者可以門行加上)。這時將pMyBlock的nFree遞增1,表示此內(nèi)存塊的自由分配單元多了一個。處用來修改該內(nèi)存塊的門由分配單元鏈表的信息，它將這個待回收分配單元的頭兩個字節(jié)的值指向該內(nèi)存塊原來的第一個可分配的門由分配單元的編號。處將pMyBlock的nFirst值改變?yōu)橹赶?/p>

33、這個待回收分配單元的編號，其編號通過計算此單元的起始位置相對pMyBlock的aData位置的差值，然后除以步長(nUnitSize)得到。實質(zhì)上，和兩步的作用就是將此待回收分配單元真正回收。值得注意的是，這兩步實際上是使得此回收單元成為此內(nèi)存塊的下一個可分配的h由分配單元，即將它放在了門由分配單元鏈表的頭部。注意，其內(nèi)存地址并沒有發(fā)生改變。實際上,一個分配單元的內(nèi)存地址無論是在分配后，還是處于門由狀態(tài)時，一宜都不會變化。變化的只是其狀態(tài)(C分配/門由)，以及當(dāng)其處于門由狀態(tài)時在門由分配單元鏈表中的位置。處檢查當(dāng)回收完畢后，包含此回收單元的內(nèi)存塊的所有單元是否都處于門由狀態(tài),且此內(nèi)存是否處于內(nèi)

34、存塊鏈表的頭部。如果是，將此內(nèi)存塊整個的返回給進(jìn)程堆，同時修改內(nèi)存塊鏈表結(jié)構(gòu)。注意，這里在判斷一個內(nèi)存塊的所有單元是否都處于門由狀態(tài)時，并沒有遍歷其所有單元，而是判斷nFree乘以nUnitSize是否等丁nSize。nSize是內(nèi)存塊中所有分配單元的人小，而不包括頭部MemoryBlock結(jié)構(gòu)體的人小。這里可以看到其用意，即用來快速檢査某個內(nèi)存塊中所有分配單元是否全部處于門由狀態(tài)。因為只需結(jié)合nFree和nUnitSize來計算得出結(jié)論，而無須遍歷和計算所有門由狀態(tài)的分配單元的個數(shù)。另外還需注意的是，這里并不能比較nFree與nlnitSize或nGrowSize的人小來判斷某個內(nèi)存塊中所有

35、分配單元都為門由狀態(tài)，這是因為第1次分配的內(nèi)存塊（分配單元個數(shù)為nlnitSize）可能被移到鏈表的后面，其至可能在移到鏈表后面后，因為某個時間其所有單元都處于n由狀態(tài)而被整個返回給進(jìn)程堆。即在回收分配單元時，無法判定某個內(nèi)存塊中的分配單元個數(shù)到底是nInitSize還是nGrowSize,也就無法通過比較nFree與nlnitSize或nGrowSize的人小來判斷一個內(nèi)存塊的所有分配單元是否都為門由狀態(tài)。以上面分配后的內(nèi)存池狀態(tài)作為例子，假設(shè)這時第2個內(nèi)存塊中的最后一個單元需要回收（已被分配，假設(shè)其編號為m,pFree指針指向它），如圖6-5所示。不難發(fā)現(xiàn)，這時nFirst的值由原來的0變

36、為m。即此內(nèi)存塊下一個被分配的單元是m編號的單元，而不是0編號的單元（最先分配的是最新回收的單元，從這一點(diǎn)看,這個過程與棧的原理類似，即先進(jìn)后出。只不過這里的進(jìn)意味著回收，而出則意味著分配“）。相應(yīng)地，m的下一個自由單元標(biāo)記為0,即內(nèi)存塊原來的下一個將被分配岀去的單元，這也表明最近回收的分配單元被插到了內(nèi)存塊的門由分配單元鏈表的頭部。當(dāng)然，nFree遞增1。MeinoiyBtocknSizenFieeriSizeiiFreerdiiitSizenGioizeriFirst:OnFiiet:kpNextpNext三或歟說；;MeinoiyBtocknSizenFieeriSizeiiFreerd

37、iiitSizenGioizeriFirst:OnFiiet:kpNextpNext三或歟說；;pFree、K，,丁:：處理至處Z前，其狀態(tài)如圖6-6所示。圖6-6處理至處之前的內(nèi)存池狀態(tài)MemoiyPoolMerttoiyBlockMemoiyBlockaSizeiiFreeriFirsi:mpNext.邊dt&nTT：aData!k-：pFiee圖6-5分配后的內(nèi)存池狀態(tài)MemoiyPoolMernoiyBlockpBLocknUnitSizeMernoiyBlockMerrioiyBlockMernoiyBlockMerrioiyBlock這里需要注意的是，雖然pFree被回收，但是pF

38、ree仍然指向m編號的單元，這個單元在回收過程中，其頭兩個字節(jié)被覆寫，但其他部分的內(nèi)容并沒有改變。而且從整個進(jìn)程的內(nèi)存使用和度來看，這個m編號的單元的狀態(tài)仍然是有效的。因為這里的回收只是回收給了內(nèi)存池，而并沒有回收給進(jìn)程堆，因此程序仍然可以通JIpFree訪問此單元。但是這是一個很危險的操作，因為首先該單元在回收過程中頭兩個字節(jié)C被覆寫，并且該單元可能很快就會被內(nèi)存池重新分配。因此回收后通PFree指針對這個單元的訪問都是錯誤的，讀操作會讀到錯誤的數(shù)據(jù)，寫操作則可能會破壞程序中其他地方的數(shù)據(jù)，因此需要格外小心。接著，需要判斷該內(nèi)存塊的內(nèi)部使用情況，及其在內(nèi)存塊鏈表中的位置。如果該內(nèi)存塊中省略號

39、所表示的其他部分中還有被分配的單元，即nFree乘以nUnitSize不等于nSize。因為此內(nèi)存塊不在鏈表頭，因此還需要將其移到鏈表頭部,如圖6-7所示。圖6-7因回收引起的MemoryBlock移動MeirioryPoolpBlocknUriitSizerJriitSizeitGrowSize如果該內(nèi)存塊中省略號表示的其他部分中全部都是fl由分配單元，即nFree乘以nUnitSize等于nSize。因為此內(nèi)存塊不在鏈表頭，所以此時需要將此內(nèi)存塊整個回收給進(jìn)程堆，回收后內(nèi)存池的結(jié)構(gòu)如圖6-8所示。圖6-8回收后內(nèi)存池的結(jié)構(gòu)MemoiyPoolMemolyBook一個內(nèi)存塊在中請后會初始化，

40、主要是為了建立最初的門由分配單元鏈表，下面是其詳細(xì)代碼：TOC o 1-5 h zMemoryBlock:MemoryBlock(USHORTnTypes,USHORTnUnitSize):nSize(nTypesreinterpret_cast(pData)二i;pDatareinterpret_cast(pData)二i;pData+二nUnitSize;nFirst(1),pNext(0)char*pData=aData;for(USHORTi=1;inTypes;i+)這里可以看到，處pData的初值是aData,即0編號單元。但是處的循環(huán)中i卻是從1開始，然后在循環(huán)內(nèi)部的處將pDat

41、a的頭兩個字節(jié)值置為i。即0號單元的頭兩個字節(jié)值為1,1號單元的頭兩個字節(jié)值為2,真到（nTypes-2）號單元的頭兩個字節(jié)值為（nTypes-1）。這意味著內(nèi)存塊初始時，其門由分配單元鏈表是從0號開始。依次串聯(lián)，一直到倒數(shù)第2個單元指向最后一個單元。還需要注意的是，在其初始化列表中，nFree初始化為nTypes-1（而不是nTypes）,nFirst初始化為1（而不是0）。這是因為第1個單元，即0編號單元構(gòu)造完畢后,立刻會被分配。另外注意到最后一個單元初始并沒有設(shè)置頭兩個字節(jié)的值，因為該單元初始在本內(nèi)存塊中并沒有下一個門由分配單元。但是從上而例子中可以看到，當(dāng)最后一個單元被分配并回收后，其頭兩個字節(jié)會被設(shè)置。圖6-9所示為一個內(nèi)存塊初始化后的狀態(tài)。圖6-9一個