The Fourth Dimension Space

內(nèi)存池技術(shù)(轉(zhuǎn))

6.1 自定義內(nèi)存池性能優(yōu)化的原理

如前所述，讀者已經(jīng)了解到"堆"和"棧"的區(qū)別。而在編程實(shí)踐中，不可避免地要大量用到堆上的內(nèi)存。例如在程序中維護(hù)一個(gè)鏈表的數(shù)據(jù)結(jié)構(gòu)時(shí)，每次新增或者刪除一個(gè)鏈表的節(jié)點(diǎn)，都需要從內(nèi)存堆上分配或者釋放一定的內(nèi)存；在維護(hù)一個(gè)動(dòng)態(tài)數(shù)組時(shí)，如果動(dòng)態(tài)數(shù)組的大小不能滿足程序需要時(shí)，也要在內(nèi)存堆上分配新的內(nèi)存空間。

6.1.1 默認(rèn)內(nèi)存管理函數(shù)的不足

利用默認(rèn)的內(nèi)存管理函數(shù)new/delete或malloc/free在堆上分配和釋放內(nèi)存會(huì)有一些額外的開(kāi)銷(xiāo)。

系統(tǒng)在接收到分配一定大小內(nèi)存的請(qǐng)求時(shí)，首先查找內(nèi)部維護(hù)的內(nèi)存空閑塊表，并且需要根據(jù)一定的算法（例如分配最先找到的不小于申請(qǐng)大小的內(nèi)存塊給請(qǐng)求者，或者分配最適于申請(qǐng)大小的內(nèi)存塊，或者分配最大空閑的內(nèi)存塊等）找到合適大小的空閑內(nèi)存塊。如果該空閑內(nèi)存塊過(guò)大，還需要切割成已分配的部分和較小的空閑塊。然后系統(tǒng)更新內(nèi)存空閑塊表，完成一次內(nèi)存分配。類(lèi)似地，在釋放內(nèi)存時(shí)，系統(tǒng)把釋放的內(nèi)存塊重新加入到空閑內(nèi)存塊表中。如果有可能的話，可以把相鄰的空閑塊合并成較大的空閑塊。

默認(rèn)的內(nèi)存管理函數(shù)還考慮到多線程的應(yīng)用，需要在每次分配和釋放內(nèi)存時(shí)加鎖，同樣增加了開(kāi)銷(xiāo)。

可見(jiàn)，如果應(yīng)用程序頻繁地在堆上分配和釋放內(nèi)存，則會(huì)導(dǎo)致性能的損失。并且會(huì)使系統(tǒng)中出現(xiàn)大量的內(nèi)存碎片，降低內(nèi)存的利用率。

默認(rèn)的分配和釋放內(nèi)存算法自然也考慮了性能，然而這些內(nèi)存管理算法的通用版本為了應(yīng)付更復(fù)雜、更廣泛的情況，需要做更多的額外工作。而對(duì)于某一個(gè)具體的應(yīng)用程序來(lái)說(shuō)，適合自身特定的內(nèi)存分配釋放模式的自定義內(nèi)存池則可以獲得更好的性能。

6.1.2 內(nèi)存池的定義和分類(lèi)

自定義內(nèi)存池的思想通過(guò)這個(gè)"池"字表露無(wú)疑，應(yīng)用程序可以通過(guò)系統(tǒng)的內(nèi)存分配調(diào)用預(yù)先一次性申請(qǐng)適當(dāng)大小的內(nèi)存作為一個(gè)內(nèi)存池，之后應(yīng)用程序自己對(duì)內(nèi)存的分配和釋放則可以通過(guò)這個(gè)內(nèi)存池來(lái)完成。只有當(dāng)內(nèi)存池大小需要?jiǎng)討B(tài)擴(kuò)展時(shí)，才需要再調(diào)用系統(tǒng)的內(nèi)存分配函數(shù)，其他時(shí)間對(duì)內(nèi)存的一切操作都在應(yīng)用程序的掌控之中。

應(yīng)用程序自定義的內(nèi)存池根據(jù)不同的適用場(chǎng)景又有不同的類(lèi)型。

從線程安全的角度來(lái)分，內(nèi)存池可以分為單線程內(nèi)存池和多線程內(nèi)存池。單線程內(nèi)存池整個(gè)生命周期只被一個(gè)線程使用，因而不需要考慮互斥訪問(wèn)的問(wèn)題；多線程內(nèi)存池有可能被多個(gè)線程共享，因此則需要在每次分配和釋放內(nèi)存時(shí)加鎖。相對(duì)而言，單線程內(nèi)存池性能更高，而多線程內(nèi)存池適用范圍更廣。

從內(nèi)存池可分配內(nèi)存單元大小來(lái)分，可以分為固定內(nèi)存池和可變內(nèi)存池。所謂固定內(nèi)存池是指應(yīng)用程序每次從內(nèi)存池中分配出來(lái)的內(nèi)存單元大小事先已經(jīng)確定，是固定不變的；而可變內(nèi)存池則每次分配的內(nèi)存單元大小可以按需變化，應(yīng)用范圍更廣，而性能比固定內(nèi)存池要低。

6.1.3 內(nèi)存池工作原理示例

下面以固定內(nèi)存池為例說(shuō)明內(nèi)存池的工作原理，如圖6-1所示。

固定內(nèi)存池由一系列固定大小的內(nèi)存塊組成，每一個(gè)內(nèi)存塊又包含了固定數(shù)量和大小的內(nèi)存單元。

如圖6-1所示，該內(nèi)存池一共包含4個(gè)內(nèi)存塊。在內(nèi)存池初次生成時(shí)，只向系統(tǒng)申請(qǐng)了一個(gè)內(nèi)存塊，返回的指針作為整個(gè)內(nèi)存池的頭指針。之后隨著應(yīng)用程序?qū)?nèi)存的不斷需求，內(nèi)存池判斷需要?jiǎng)討B(tài)擴(kuò)大時(shí)，才再次向系統(tǒng)申請(qǐng)新的內(nèi)存塊，并把所有這些內(nèi)存塊通過(guò)指針鏈接起來(lái)。對(duì)于操作系統(tǒng)來(lái)說(shuō)，它已經(jīng)為該應(yīng)用程序分配了4個(gè)等大小的內(nèi)存塊。由于是大小固定的，所以分配的速度比較快；而對(duì)于應(yīng)用程序來(lái)說(shuō)，其內(nèi)存池開(kāi)辟了一定大小，內(nèi)存池內(nèi)部卻還有剩余的空間。

例如放大來(lái)看第4個(gè)內(nèi)存塊，其中包含一部分內(nèi)存池塊頭信息和3個(gè)大小相等的內(nèi)存池單元。單元1和單元3是空閑的，單元2已經(jīng)分配。當(dāng)應(yīng)用程序需要通過(guò)該內(nèi)存池分配一個(gè)單元大小的內(nèi)存時(shí)，只需要簡(jiǎn)單遍歷所有的內(nèi)存池塊頭信息，快速定位到還有空閑單元的那個(gè)內(nèi)存池塊。然后根據(jù)該塊的塊頭信息直接定位到第1個(gè)空閑的單元地址，把這個(gè)地址返回，并且標(biāo)記下一個(gè)空閑單元即可；當(dāng)應(yīng)用程序釋放某一個(gè)內(nèi)存池單元時(shí)，直接在對(duì)應(yīng)的內(nèi)存池塊頭信息中標(biāo)記該內(nèi)存單元為空閑單元即可。

可見(jiàn)與系統(tǒng)管理內(nèi)存相比，內(nèi)存池的操作非常迅速，它在性能優(yōu)化方面的優(yōu)點(diǎn)主要如下。

（1）針對(duì)特殊情況，例如需要頻繁分配釋放固定大小的內(nèi)存對(duì)象時(shí)，不需要復(fù)雜的分配算法和多線程保護(hù)。也不需要維護(hù)內(nèi)存空閑表的額外開(kāi)銷(xiāo)，從而獲得較高的性能。

（2）由于開(kāi)辟一定數(shù)量的連續(xù)內(nèi)存空間作為內(nèi)存池塊，因而一定程度上提高了程序局部性，提升了程序性能。

（3）比較容易控制頁(yè)邊界對(duì)齊和內(nèi)存字節(jié)對(duì)齊，沒(méi)有內(nèi)存碎片的問(wèn)題。

回頁(yè)首

6.2 一個(gè)內(nèi)存池的實(shí)現(xiàn)實(shí)例

本節(jié)分析在某個(gè)大型應(yīng)用程序?qū)嶋H應(yīng)用到的一個(gè)內(nèi)存池實(shí)現(xiàn)，并詳細(xì)講解其使用方法與工作原理。這是一個(gè)應(yīng)用于單線程環(huán)境且分配單元大小固定的內(nèi)存池，一般用來(lái)為執(zhí)行時(shí)會(huì)動(dòng)態(tài)頻繁地創(chuàng)建且可能會(huì)被多次創(chuàng)建的類(lèi)對(duì)象或者結(jié)構(gòu)體分配內(nèi)存。

本節(jié)首先講解該內(nèi)存池的數(shù)據(jù)結(jié)構(gòu)聲明及圖示，接著描述其原理及行為特征。然后逐一講解實(shí)現(xiàn)細(xì)節(jié)，最后介紹如何在實(shí)際程序中應(yīng)用此內(nèi)存池，并與使用普通內(nèi)存函數(shù)申請(qǐng)內(nèi)存的程序性能作比較。

6.2.1 內(nèi)部構(gòu)造

內(nèi)存池類(lèi)MemoryPool的聲明如下：

class MemoryPool
            {
            private:
            MemoryBlock*   pBlock;
            USHORT          nUnitSize;
            USHORT          nInitSize;
            USHORT          nGrowSize;
            public:
            MemoryPool( USHORT nUnitSize,
            USHORT nInitSize = 1024,
            USHORT nGrowSize = 256 );
            ~MemoryPool();
            void*           Alloc();
            void            Free( void* p );
            };
            

MemoryBlock為內(nèi)存池中附著在真正用來(lái)為內(nèi)存請(qǐng)求分配內(nèi)存的內(nèi)存塊頭部的結(jié)構(gòu)體，它描述了與之聯(lián)系的內(nèi)存塊的使用信息：

struct MemoryBlock
            {
            USHORT          nSize;
            USHORT          nFree;
            USHORT          nFirst;
            USHORT          nDummyAlign1;
            MemoryBlock*  pNext;
            char            aData[1];
            static void* operator new(size_t, USHORT nTypes, USHORT nUnitSize)
            {
            return ::operator new(sizeof(MemoryBlock) + nTypes * nUnitSize);
            }
            static void  operator delete(void *p, size_t)
            {
            ::operator delete (p);
            }
            MemoryBlock (USHORT nTypes = 1, USHORT nUnitSize = 0);
            ~MemoryBlock() {}
            };
            

此內(nèi)存池的數(shù)據(jù)結(jié)構(gòu)如圖6-2所示。

6.2.2 總體機(jī)制

此內(nèi)存池的總體機(jī)制如下。

（1）在運(yùn)行過(guò)程中，MemoryPool內(nèi)存池可能會(huì)有多個(gè)用來(lái)滿足內(nèi)存申請(qǐng)請(qǐng)求的內(nèi)存塊，這些內(nèi)存塊是從進(jìn)程堆中開(kāi)辟的一個(gè)較大的連續(xù)內(nèi)存區(qū)域，它由一個(gè)MemoryBlock結(jié)構(gòu)體和多個(gè)可供分配的內(nèi)存單元組成，所有內(nèi)存塊組成了一個(gè)內(nèi)存塊鏈表，MemoryPool的pBlock是這個(gè)鏈表的頭。對(duì)每個(gè)內(nèi)存塊，都可以通過(guò)其頭部的MemoryBlock結(jié)構(gòu)體的pNext成員訪問(wèn)緊跟在其后面的那個(gè)內(nèi)存塊。

（2）每個(gè)內(nèi)存塊由兩部分組成，即一個(gè)MemoryBlock結(jié)構(gòu)體和多個(gè)內(nèi)存分配單元。這些內(nèi)存分配單元大小固定（由MemoryPool的nUnitSize表示），MemoryBlock結(jié)構(gòu)體并不維護(hù)那些已經(jīng)分配的單元的信息；相反，它只維護(hù)沒(méi)有分配的自由分配單元的信息。它有兩個(gè)成員比較重要：nFree和nFirst。nFree記錄這個(gè)內(nèi)存塊中還有多少個(gè)自由分配單元，而nFirst則記錄下一個(gè)可供分配的單元的編號(hào)。每一個(gè)自由分配單元的頭兩個(gè)字節(jié)（即一個(gè)USHORT型值）記錄了緊跟它之后的下一個(gè)自由分配單元的編號(hào)，這樣，通過(guò)利用每個(gè)自由分配單元的頭兩個(gè)字節(jié)，一個(gè)MemoryBlock中的所有自由分配單元被鏈接起來(lái)。

（3）當(dāng)有新的內(nèi)存請(qǐng)求到來(lái)時(shí)，MemoryPool會(huì)通過(guò)pBlock遍歷MemoryBlock鏈表，直到找到某個(gè)MemoryBlock所在的內(nèi)存塊，其中還有自由分配單元（通過(guò)檢測(cè)MemoryBlock結(jié)構(gòu)體的nFree成員是否大于0）。如果找到這樣的內(nèi)存塊，取得其MemoryBlock的nFirst值（此為該內(nèi)存塊中第1個(gè)可供分配的自由單元的編號(hào)）。然后根據(jù)這個(gè)編號(hào)定位到該自由分配單元的起始位置（因?yàn)樗蟹峙鋯卧笮」潭?，因此每個(gè)分配單元的起始位置都可以通過(guò)編號(hào)分配單元大小來(lái)偏移定位），這個(gè)位置就是用來(lái)滿足此次內(nèi)存申請(qǐng)請(qǐng)求的內(nèi)存的起始地址。但在返回這個(gè)地址前，需要首先將該位置開(kāi)始的頭兩個(gè)字節(jié)的值（這兩個(gè)字節(jié)值記錄其之后的下一個(gè)自由分配單元的編號(hào)）賦給本內(nèi)存塊的MemoryBlock的nFirst成員。這樣下一次的請(qǐng)求就會(huì)用這個(gè)編號(hào)對(duì)應(yīng)的內(nèi)存單元來(lái)滿足，同時(shí)將此內(nèi)存塊的MemoryBlock的nFree遞減1，然后才將剛才定位到的內(nèi)存單元的起始位置作為此次內(nèi)存請(qǐng)求的返回地址返回給調(diào)用者。

（4）如果從現(xiàn)有的內(nèi)存塊中找不到一個(gè)自由的內(nèi)存分配單元（當(dāng)?shù)?次請(qǐng)求內(nèi)存，以及現(xiàn)有的所有內(nèi)存塊中的所有內(nèi)存分配單元都已經(jīng)被分配時(shí)會(huì)發(fā)生這種情形），MemoryPool就會(huì)從進(jìn)程堆中申請(qǐng)一個(gè)內(nèi)存塊（這個(gè)內(nèi)存塊包括一個(gè)MemoryBlock結(jié)構(gòu)體，及緊鄰其后的多個(gè)內(nèi)存分配單元，假設(shè)內(nèi)存分配單元的個(gè)數(shù)為n，n可以取值MemoryPool中的nInitSize或者nGrowSize），申請(qǐng)完后，并不會(huì)立刻將其中的一個(gè)分配單元分配出去，而是需要首先初始化這個(gè)內(nèi)存塊。初始化的操作包括設(shè)置MemoryBlock的nSize為所有內(nèi)存分配單元的大?。ㄗ⒁?，并不包括MemoryBlock結(jié)構(gòu)體的大?。?、nFree為n-1（注意，這里是n-1而不是n，因?yàn)榇舜涡聝?nèi)存塊就是為了滿足一次新的內(nèi)存請(qǐng)求而申請(qǐng)的，馬上就會(huì)分配一塊自由存儲(chǔ)單元出去，如果設(shè)為n-1，分配一個(gè)自由存儲(chǔ)單元后無(wú)須再將n遞減1），nFirst為1（已經(jīng)知道nFirst為下一個(gè)可以分配的自由存儲(chǔ)單元的編號(hào)。為1的原因與nFree為n-1相同，即立即會(huì)將編號(hào)為0的自由分配單元分配出去。現(xiàn)在設(shè)為1，其后不用修改nFirst的值），MemoryBlock的構(gòu)造需要做更重要的事情，即將編號(hào)為0的分配單元之后的所有自由分配單元鏈接起來(lái)。如前所述，每個(gè)自由分配單元的頭兩個(gè)字節(jié)用來(lái)存儲(chǔ)下一個(gè)自由分配單元的編號(hào)。另外，因?yàn)槊總€(gè)分配單元大小固定，所以可以通過(guò)其編號(hào)和單元大?。∕emoryPool的nUnitSize成員）的乘積作為偏移值進(jìn)行定位?，F(xiàn)在唯一的問(wèn)題是定位從哪個(gè)地址開(kāi)始？答案是MemoryBlock的aData[1]成員開(kāi)始。因?yàn)閍Data[1]實(shí)際上是屬于MemoryBlock結(jié)構(gòu)體的（MemoryBlock結(jié)構(gòu)體的最后一個(gè)字節(jié)），所以實(shí)質(zhì)上，MemoryBlock結(jié)構(gòu)體的最后一個(gè)字節(jié)也用做被分配出去的分配單元的一部分。因?yàn)檎麄€(gè)內(nèi)存塊由MemoryBlock結(jié)構(gòu)體和整數(shù)個(gè)分配單元組成，這意味著內(nèi)存塊的最后一個(gè)字節(jié)會(huì)被浪費(fèi)，這個(gè)字節(jié)在圖6-2中用位于兩個(gè)內(nèi)存的最后部分的濃黑背景的小塊標(biāo)識(shí)。確定了分配單元的起始位置后，將自由分配單元鏈接起來(lái)的工作就很容易了。即從aData位置開(kāi)始，每隔nUnitSize大小取其頭兩個(gè)字節(jié)，記錄其之后的自由分配單元的編號(hào)。因?yàn)閯傞_(kāi)始所有分配單元都是自由的，所以這個(gè)編號(hào)就是自身編號(hào)加1，即位置上緊跟其后的單元的編號(hào)。初始化后，將此內(nèi)存塊的第1個(gè)分配單元的起始地址返回，已經(jīng)知道這個(gè)地址就是aData。

（5）當(dāng)某個(gè)被分配的單元因?yàn)閐elete需要回收時(shí)，該單元并不會(huì)返回給進(jìn)程堆，而是返回給MemoryPool。返回時(shí)，MemoryPool能夠知道該單元的起始地址。這時(shí)，MemoryPool開(kāi)始遍歷其所維護(hù)的內(nèi)存塊鏈表，判斷該單元的起始地址是否落在某個(gè)內(nèi)存塊的地址范圍內(nèi)。如果不在所有內(nèi)存地址范圍內(nèi)，則這個(gè)被回收的單元不屬于這個(gè)MemoryPool；如果在某個(gè)內(nèi)存塊的地址范圍內(nèi)，那么它會(huì)將這個(gè)剛剛回收的分配單元加到這個(gè)內(nèi)存塊的MemoryBlock所維護(hù)的自由分配單元鏈表的頭部，同時(shí)將其nFree值遞增1?；厥蘸?，考慮到資源的有效利用及后續(xù)操作的性能，內(nèi)存池的操作會(huì)繼續(xù)判斷：如果此內(nèi)存塊的所有分配單元都是自由的，那么這個(gè)內(nèi)存塊就會(huì)從MemoryPool中被移出并作為一個(gè)整體返回給進(jìn)程堆；如果該內(nèi)存塊中還有非自由分配單元，這時(shí)不能將此內(nèi)存塊返回給進(jìn)程堆。但是因?yàn)閯倓傆幸粋€(gè)分配單元返回給了這個(gè)內(nèi)存塊，即這個(gè)內(nèi)存塊有自由分配單元可供下次分配，因此它會(huì)被移到MemoryPool維護(hù)的內(nèi)存塊的頭部。這樣下次的內(nèi)存請(qǐng)求到來(lái)，MemoryPool遍歷其內(nèi)存塊鏈表以尋找自由分配單元時(shí)，第1次尋找就會(huì)找到這個(gè)內(nèi)存塊。因?yàn)檫@個(gè)內(nèi)存塊確實(shí)有自由分配單元，這樣可以減少M(fèi)emoryPool的遍歷次數(shù)。

綜上所述，每個(gè)內(nèi)存池（MemoryPool）維護(hù)一個(gè)內(nèi)存塊鏈表（單鏈表），每個(gè)內(nèi)存塊由一個(gè)維護(hù)該內(nèi)存塊信息的塊頭結(jié)構(gòu)（MemoryBlock）和多個(gè)分配單元組成，塊頭結(jié)構(gòu)MemoryBlock則進(jìn)一步維護(hù)一個(gè)該內(nèi)存塊的所有自由分配單元組成的"鏈表"。這個(gè)鏈表不是通過(guò)"指向下一個(gè)自由分配單元的指針"鏈接起來(lái)的，而是通過(guò)"下一個(gè)自由分配單元的編號(hào)"鏈接起來(lái)，這個(gè)編號(hào)值存儲(chǔ)在該自由分配單元的頭兩個(gè)字節(jié)中。另外，第1個(gè)自由分配單元的起始位置并不是MemoryBlock結(jié)構(gòu)體"后面的"第1個(gè)地址位置，而是MemoryBlock結(jié)構(gòu)體"內(nèi)部"的最后一個(gè)字節(jié)aData（也可能不是最后一個(gè)，因?yàn)榭紤]到字節(jié)對(duì)齊的問(wèn)題），即分配單元實(shí)際上往前面錯(cuò)了一位。又因?yàn)镸emoryBlock結(jié)構(gòu)體后面的空間剛好是分配單元的整數(shù)倍，這樣依次錯(cuò)位下去，內(nèi)存塊的最后一個(gè)字節(jié)實(shí)際沒(méi)有被利用。這么做的一個(gè)原因也是考慮到不同平臺(tái)的移植問(wèn)題，因?yàn)椴煌脚_(tái)的對(duì)齊方式可能不盡相同。即當(dāng)申請(qǐng)MemoryBlock大小內(nèi)存時(shí)，可能會(huì)返回比其所有成員大小總和還要大一些的內(nèi)存。最后的幾個(gè)字節(jié)是為了"補(bǔ)齊"，而使得aData成為第1個(gè)分配單元的起始位置，這樣在對(duì)齊方式不同的各種平臺(tái)上都可以工作。

6.2.3 細(xì)節(jié)剖析

有了上述的總體印象后，本節(jié)來(lái)仔細(xì)剖析其實(shí)現(xiàn)細(xì)節(jié)。

（1）MemoryPool的構(gòu)造如下：

MemoryPool::MemoryPool( USHORT _nUnitSize,
            USHORT _nInitSize, USHORT _nGrowSize )
            {
            pBlock      = NULL;	            ①
            nInitSize   = _nInitSize;       ②
            nGrowSize   = _nGrowSize;       ③
            if ( _nUnitSize > 4 )
            nUnitSize = (_nUnitSize + (MEMPOOL_ALIGNMENT-1)) & ~(MEMPOOL_ALIGNMENT-1); ④
            else if ( _nUnitSize <= 2 )
            nUnitSize = 2;              ⑤
            else
            nUnitSize = 4;
            }
            

從①處可以看出，MemoryPool創(chuàng)建時(shí)，并沒(méi)有立刻創(chuàng)建真正用來(lái)滿足內(nèi)存申請(qǐng)的內(nèi)存塊，即內(nèi)存塊鏈表剛開(kāi)始時(shí)為空。

②處和③處分別設(shè)置"第1次創(chuàng)建的內(nèi)存塊所包含的分配單元的個(gè)數(shù)"，及"隨后創(chuàng)建的內(nèi)存塊所包含的分配單元的個(gè)數(shù)"，這兩個(gè)值在MemoryPool創(chuàng)建時(shí)通過(guò)參數(shù)指定，其后在該MemoryPool對(duì)象生命周期中一直不變。

后面的代碼用來(lái)設(shè)置nUnitSize，這個(gè)值參考傳入的_nUnitSize參數(shù)。但是還需要考慮兩個(gè)因素。如前所述，每個(gè)分配單元在自由狀態(tài)時(shí)，其頭兩個(gè)字節(jié)用來(lái)存放"其下一個(gè)自由分配單元的編號(hào)"。即每個(gè)分配單元"最少"有"兩個(gè)字節(jié)"，這就是⑤處賦值的原因。④處是將大于4個(gè)字節(jié)的大小_nUnitSize往上"取整到"大于_nUnitSize的最小的MEMPOOL_ ALIGNMENT的倍數(shù)（前提是MEMPOOL_ALIGNMENT為2的倍數(shù)）。如_nUnitSize為11時(shí)，MEMPOOL_ALIGNMENT為8，nUnitSize為16；MEMPOOL_ALIGNMENT為4，nUnitSize為12；MEMPOOL_ALIGNMENT為2，nUnitSize為12，依次類(lèi)推。

（2）當(dāng)向MemoryPool提出內(nèi)存請(qǐng)求時(shí)：

void* MemoryPool::Alloc()
            {
            if ( !pBlock )           ①
            {
            ……
            }
            MemoryBlock* pMyBlock = pBlock;
            while (pMyBlock && !pMyBlock->nFree )②
            pMyBlock = pMyBlock->pNext;
            if ( pMyBlock )	         ③
            {
            char* pFree = pMyBlock->aData+(pMyBlock->nFirst*nUnitSize);
            pMyBlock->nFirst = *((USHORT*)pFree);
            pMyBlock->nFree--;
            return (void*)pFree;
            }
            else                    ④
            {
            if ( !nGrowSize )
            return NULL;
            pMyBlock = new(nGrowSize, nUnitSize) FixedMemBlock(nGrowSize, nUnitSize);
            if ( !pMyBlock )
            return NULL;
            pMyBlock->pNext = pBlock;
            pBlock = pMyBlock;
            return (void*)(pMyBlock->aData);
            }
            }
            

MemoryPool滿足內(nèi)存請(qǐng)求的步驟主要由四步組成。

①處首先判斷內(nèi)存池當(dāng)前內(nèi)存塊鏈表是否為空，如果為空，則意味著這是第1次內(nèi)存申請(qǐng)請(qǐng)求。這時(shí)，從進(jìn)程堆中申請(qǐng)一個(gè)分配單元個(gè)數(shù)為nInitSize的內(nèi)存塊，并初始化該內(nèi)存塊（主要初始化MemoryBlock結(jié)構(gòu)體成員，以及創(chuàng)建初始的自由分配單元鏈表，下面會(huì)詳細(xì)分析其代碼）。如果該內(nèi)存塊申請(qǐng)成功，并初始化完畢，返回第1個(gè)分配單元給調(diào)用函數(shù)。第1個(gè)分配單元以MemoryBlock結(jié)構(gòu)體內(nèi)的最后一個(gè)字節(jié)為起始地址。

②處的作用是當(dāng)內(nèi)存池中已有內(nèi)存塊（即內(nèi)存塊鏈表不為空）時(shí)遍歷該內(nèi)存塊鏈表，尋找還有"自由分配單元"的內(nèi)存塊。

③處檢查如果找到還有自由分配單元的內(nèi)存塊，則"定位"到該內(nèi)存塊現(xiàn)在可以用的自由分配單元處。"定位"以MemoryBlock結(jié)構(gòu)體內(nèi)的最后一個(gè)字節(jié)位置aData為起始位置，以MemoryPool的nUnitSize為步長(zhǎng)來(lái)進(jìn)行。找到后，需要修改MemoryBlock的nFree信息（剩下來(lái)的自由分配單元比原來(lái)減少了一個(gè)），以及修改此內(nèi)存塊的自由存儲(chǔ)單元鏈表的信息。在找到的內(nèi)存塊中，pMyBlock->nFirst為該內(nèi)存塊中自由存儲(chǔ)單元鏈表的表頭，其下一個(gè)自由存儲(chǔ)單元的編號(hào)存放在pMyBlock->nFirst指示的自由存儲(chǔ)單元（亦即剛才定位到的自由存儲(chǔ)單元）的頭兩個(gè)字節(jié)。通過(guò)剛才定位到的位置，取其頭兩個(gè)字節(jié)的值，賦給pMyBlock->nFirst，這就是此內(nèi)存塊的自由存儲(chǔ)單元鏈表的新的表頭，即下一次分配出去的自由分配單元的編號(hào)（如果nFree大于零的話）。修改維護(hù)信息后，就可以將剛才定位到的自由分配單元的地址返回給此次申請(qǐng)的調(diào)用函數(shù)。注意，因?yàn)檫@個(gè)分配單元已經(jīng)被分配，而內(nèi)存塊無(wú)須維護(hù)已分配的分配單元，因此該分配單元的頭兩個(gè)字節(jié)的信息已經(jīng)沒(méi)有用處。換個(gè)角度看，這個(gè)自由分配單元返回給調(diào)用函數(shù)后，調(diào)用函數(shù)如何處置這塊內(nèi)存，內(nèi)存池?zé)o從知曉，也無(wú)須知曉。此分配單元在返回給調(diào)用函數(shù)時(shí)，其內(nèi)容對(duì)于調(diào)用函數(shù)來(lái)說(shuō)是無(wú)意義的。因此幾乎可以肯定調(diào)用函數(shù)在用這個(gè)單元的內(nèi)存時(shí)會(huì)覆蓋其原來(lái)的內(nèi)容，即頭兩個(gè)字節(jié)的內(nèi)容也會(huì)被抹去。因此每個(gè)存儲(chǔ)單元并沒(méi)有因?yàn)樾枰溄佣攵嘤嗟木S護(hù)信息，而是直接利用單元內(nèi)的頭兩個(gè)字節(jié)，當(dāng)其分配后，頭兩個(gè)字節(jié)也可以被調(diào)用函數(shù)利用。而在自由狀態(tài)時(shí)，則用來(lái)存放維護(hù)信息，即下一個(gè)自由分配單元的編號(hào)，這是一個(gè)有效利用內(nèi)存的好例子。

④處表示在②處遍歷時(shí)，沒(méi)有找到還有自由分配單元的內(nèi)存塊，這時(shí)，需要重新向進(jìn)程堆申請(qǐng)一個(gè)內(nèi)存塊。因?yàn)椴皇堑谝淮紊暾?qǐng)內(nèi)存塊，所以申請(qǐng)的內(nèi)存塊包含的分配單元個(gè)數(shù)為nGrowSize，而不再是nInitSize。與①處相同，先做這個(gè)新申請(qǐng)內(nèi)存塊的初始化工作，然后將此內(nèi)存塊插入MemoryPool的內(nèi)存塊鏈表的頭部，再將此內(nèi)存塊的第1個(gè)分配單元返回給調(diào)用函數(shù)。將此新內(nèi)存塊插入內(nèi)存塊鏈表的頭部的原因是該內(nèi)存塊還有很多可供分配的自由分配單元（除非nGrowSize等于1，這應(yīng)該不太可能。因?yàn)閮?nèi)存池的含義就是一次性地從進(jìn)程堆中申請(qǐng)一大塊內(nèi)存，以供后續(xù)的多次申請(qǐng)），放在頭部可以使得在下次收到內(nèi)存申請(qǐng)時(shí)，減少②處對(duì)內(nèi)存塊的遍歷時(shí)間。

可以用圖6-2的MemoryPool來(lái)展示MemoryPool::Alloc的過(guò)程。圖6-3是某個(gè)時(shí)刻MemoryPool的內(nèi)部狀態(tài)。

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

可以看到，原來(lái)的第1個(gè)可供分配的單元（m編號(hào)處）已經(jīng)顯示為被分配的狀態(tài)。而pBlock的nFirst已經(jīng)指向原來(lái)m單元下一個(gè)自由分配單元的編號(hào)，即k。

（3）MemoryPool回收內(nèi)存時(shí)：

void MemoryPool::Free( void* pFree )
            {
            ……
            MemoryBlock* pMyBlock = pBlock;
            while ( ((ULONG)pMyBlock->aData > (ULONG)pFree) ||
            ((ULONG)pFree >= ((ULONG)pMyBlock->aData + pMyBlock->nSize)) )①
            {
            ……
            }
            pMyBlock->nFree++;                     ②
            *((USHORT*)pFree) = pMyBlock->nFirst;  ③
            pMyBlock->nFirst = (USHORT)(((ULONG)pFree-(ULONG)(pBlock->aData)) / nUnitSize);④
            if (pMyBlock->nFree*nUnitSize == pMyBlock->nSize )⑤
            {
            ……
            }
            else
            {
            ……
            }
            }
            

如前所述，回收分配單元時(shí)，可能會(huì)將整個(gè)內(nèi)存塊返回給進(jìn)程堆，也可能將被回收分配單元所屬的內(nèi)存塊移至內(nèi)存池的內(nèi)存塊鏈表的頭部。這兩個(gè)操作都需要修改鏈表結(jié)構(gòu)。這時(shí)需要知道該內(nèi)存塊在鏈表中前一個(gè)位置的內(nèi)存塊。

①處遍歷內(nèi)存池的內(nèi)存塊鏈表，確定該待回收分配單元（pFree）落在哪一個(gè)內(nèi)存塊的指針?lè)秶鷥?nèi)，通過(guò)比較指針值來(lái)確定。

運(yùn)行到②處，pMyBlock即找到的包含pFree所指向的待回收分配單元的內(nèi)存塊（當(dāng)然，這時(shí)應(yīng)該還需要檢查pMyBlock為NULL時(shí)的情形，即pFree不屬于此內(nèi)存池的范圍，因此不能返回給此內(nèi)存池，讀者可以自行加上）。這時(shí)將pMyBlock的nFree遞增1，表示此內(nèi)存塊的自由分配單元多了一個(gè)。

③處用來(lái)修改該內(nèi)存塊的自由分配單元鏈表的信息，它將這個(gè)待回收分配單元的頭兩個(gè)字節(jié)的值指向該內(nèi)存塊原來(lái)的第一個(gè)可分配的自由分配單元的編號(hào)。

④處將pMyBlock的nFirst值改變?yōu)橹赶蜻@個(gè)待回收分配單元的編號(hào)，其編號(hào)通過(guò)計(jì)算此單元的起始位置相對(duì)pMyBlock的aData位置的差值，然后除以步長(zhǎng)（nUnitSize）得到。

實(shí)質(zhì)上，③和④兩步的作用就是將此待回收分配單元"真正回收"。值得注意的是，這兩步實(shí)際上是使得此回收單元成為此內(nèi)存塊的下一個(gè)可分配的自由分配單元，即將它放在了自由分配單元鏈表的頭部。注意，其內(nèi)存地址并沒(méi)有發(fā)生改變。實(shí)際上，一個(gè)分配單元的內(nèi)存地址無(wú)論是在分配后，還是處于自由狀態(tài)時(shí)，一直都不會(huì)變化。變化的只是其狀態(tài)（已分配/自由），以及當(dāng)其處于自由狀態(tài)時(shí)在自由分配單元鏈表中的位置。

⑤處檢查當(dāng)回收完畢后，包含此回收單元的內(nèi)存塊的所有單元是否都處于自由狀態(tài)，且此內(nèi)存是否處于內(nèi)存塊鏈表的頭部。如果是，將此內(nèi)存塊整個(gè)的返回給進(jìn)程堆，同時(shí)修改內(nèi)存塊鏈表結(jié)構(gòu)。

注意，這里在判斷一個(gè)內(nèi)存塊的所有單元是否都處于自由狀態(tài)時(shí)，并沒(méi)有遍歷其所有單元，而是判斷nFree乘以nUnitSize是否等于nSize。nSize是內(nèi)存塊中所有分配單元的大小，而不包括頭部MemoryBlock結(jié)構(gòu)體的大小。這里可以看到其用意，即用來(lái)快速檢查某個(gè)內(nèi)存塊中所有分配單元是否全部處于自由狀態(tài)。因?yàn)橹恍杞Y(jié)合nFree和nUnitSize來(lái)計(jì)算得出結(jié)論，而無(wú)須遍歷和計(jì)算所有自由狀態(tài)的分配單元的個(gè)數(shù)。

另外還需注意的是，這里并不能比較nFree與nInitSize或nGrowSize的大小來(lái)判斷某個(gè)內(nèi)存塊中所有分配單元都為自由狀態(tài)，這是因?yàn)榈?次分配的內(nèi)存塊（分配單元個(gè)數(shù)為nInitSize）可能被移到鏈表的后面，甚至可能在移到鏈表后面后，因?yàn)槟硞€(gè)時(shí)間其所有單元都處于自由狀態(tài)而被整個(gè)返回給進(jìn)程堆。即在回收分配單元時(shí)，無(wú)法判定某個(gè)內(nèi)存塊中的分配單元個(gè)數(shù)到底是nInitSize還是nGrowSize，也就無(wú)法通過(guò)比較nFree與nInitSize或nGrowSize的大小來(lái)判斷一個(gè)內(nèi)存塊的所有分配單元是否都為自由狀態(tài)。

以上面分配后的內(nèi)存池狀態(tài)作為例子，假設(shè)這時(shí)第2個(gè)內(nèi)存塊中的最后一個(gè)單元需要回收（已被分配，假設(shè)其編號(hào)為m，pFree指針指向它），如圖6-5所示。

不難發(fā)現(xiàn)，這時(shí)nFirst的值由原來(lái)的0變?yōu)閙。即此內(nèi)存塊下一個(gè)被分配的單元是m編號(hào)的單元，而不是0編號(hào)的單元（最先分配的是最新回收的單元，從這一點(diǎn)看，這個(gè)過(guò)程與棧的原理類(lèi)似，即先進(jìn)后出。只不過(guò)這里的"進(jìn)"意味著"回收"，而"出"則意味著"分配"）。相應(yīng)地，m的"下一個(gè)自由單元"標(biāo)記為0，即內(nèi)存塊原來(lái)的"下一個(gè)將被分配出去的單元"，這也表明最近回收的分配單元被插到了內(nèi)存塊的"自由分配單元鏈表"的頭部。當(dāng)然，nFree遞增1。

處理至⑥處之前，其狀態(tài)如圖6-6所示。

這里需要注意的是，雖然pFree被"回收"，但是pFree仍然指向m編號(hào)的單元，這個(gè)單元在回收過(guò)程中，其頭兩個(gè)字節(jié)被覆寫(xiě)，但其他部分的內(nèi)容并沒(méi)有改變。而且從整個(gè)進(jìn)程的內(nèi)存使用角度來(lái)看，這個(gè)m編號(hào)的單元的狀態(tài)仍然是"有效的"。因?yàn)檫@里的"回收"只是回收給了內(nèi)存池，而并沒(méi)有回收給進(jìn)程堆，因此程序仍然可以通過(guò)pFree訪問(wèn)此單元。但是這是一個(gè)很危險(xiǎn)的操作，因?yàn)槭紫仍搯卧诨厥者^(guò)程中頭兩個(gè)字節(jié)已被覆寫(xiě)，并且該單元可能很快就會(huì)被內(nèi)存池重新分配。因此回收后通過(guò)pFree指針對(duì)這個(gè)單元的訪問(wèn)都是錯(cuò)誤的，讀操作會(huì)讀到錯(cuò)誤的數(shù)據(jù)，寫(xiě)操作則可能會(huì)破壞程序中其他地方的數(shù)據(jù)，因此需要格外小心。

接著，需要判斷該內(nèi)存塊的內(nèi)部使用情況，及其在內(nèi)存塊鏈表中的位置。如果該內(nèi)存塊中省略號(hào)"……"所表示的其他部分中還有被分配的單元，即nFree乘以nUnitSize不等于nSize。因?yàn)榇藘?nèi)存塊不在鏈表頭，因此還需要將其移到鏈表頭部，如圖6-7所示。

如果該內(nèi)存塊中省略號(hào)"……"表示的其他部分中全部都是自由分配單元，即nFree乘以nUnitSize等于nSize。因?yàn)榇藘?nèi)存塊不在鏈表頭，所以此時(shí)需要將此內(nèi)存塊整個(gè)回收給進(jìn)程堆，回收后內(nèi)存池的結(jié)構(gòu)如圖6-8所示。

一個(gè)內(nèi)存塊在申請(qǐng)后會(huì)初始化，主要是為了建立最初的自由分配單元鏈表，下面是其詳細(xì)代碼：

MemoryBlock::MemoryBlock (USHORT nTypes, USHORT nUnitSize)
            : nSize  (nTypes * nUnitSize),
            nFree  (nTypes - 1),                     ④
            nFirst (1),                              ⑤
            pNext  (0)
            {
            char * pData = aData;                  ①
            for (USHORT i = 1; i < nTypes; i++) ②
            {
            *reinterpret_cast<USHORT*>(pData) = i; ③
            pData += nUnitSize;
            }
            }
            

這里可以看到，①處pData的初值是aData，即0編號(hào)單元。但是②處的循環(huán)中i卻是從1開(kāi)始，然后在循環(huán)內(nèi)部的③處將pData的頭兩個(gè)字節(jié)值置為i。即0號(hào)單元的頭兩個(gè)字節(jié)值為1，1號(hào)單元的頭兩個(gè)字節(jié)值為2，一直到（nTypes-2）號(hào)單元的頭兩個(gè)字節(jié)值為（nTypes-1）。這意味著內(nèi)存塊初始時(shí)，其自由分配單元鏈表是從0號(hào)開(kāi)始。依次串聯(lián)，一直到倒數(shù)第2個(gè)單元指向最后一個(gè)單元。

還需要注意的是，在其初始化列表中，nFree初始化為nTypes-1（而不是nTypes），nFirst初始化為1（而不是0）。這是因?yàn)榈?個(gè)單元，即0編號(hào)單元構(gòu)造完畢后，立刻會(huì)被分配。另外注意到最后一個(gè)單元初始并沒(méi)有設(shè)置頭兩個(gè)字節(jié)的值，因?yàn)樵搯卧跏荚诒緝?nèi)存塊中并沒(méi)有下一個(gè)自由分配單元。但是從上面例子中可以看到，當(dāng)最后一個(gè)單元被分配并回收后，其頭兩個(gè)字節(jié)會(huì)被設(shè)置。

圖6-9所示為一個(gè)內(nèi)存塊初始化后的狀態(tài)。

當(dāng)內(nèi)存池析構(gòu)時(shí)，需要將內(nèi)存池的所有內(nèi)存塊返回給進(jìn)程堆：

MemoryPool::~MemoryPool()
            {
            MemoryBlock* pMyBlock = pBlock;
            while ( pMyBlock )
            {
            ……
            }
            }
            

6.2.4 使用方法

分析內(nèi)存池的內(nèi)部原理后，本節(jié)說(shuō)明如何使用它。從上面的分析可以看到，該內(nèi)存池主要有兩個(gè)對(duì)外接口函數(shù)，即Alloc和Free。Alloc返回所申請(qǐng)的分配單元（固定大小內(nèi)存），F(xiàn)ree則回收傳入的指針代表的分配單元的內(nèi)存給內(nèi)存池。分配的信息則通過(guò)MemoryPool的構(gòu)造函數(shù)指定，包括分配單元大小、內(nèi)存池第1次申請(qǐng)的內(nèi)存塊中所含分配單元的個(gè)數(shù)，以及內(nèi)存池后續(xù)申請(qǐng)的內(nèi)存塊所含分配單元的個(gè)數(shù)等。

綜上所述，當(dāng)需要提高某些關(guān)鍵類(lèi)對(duì)象的申請(qǐng)／回收效率時(shí)，可以考慮將該類(lèi)所有生成對(duì)象所需的空間都從某個(gè)這樣的內(nèi)存池中開(kāi)辟。在銷(xiāo)毀對(duì)象時(shí)，只需要返回給該內(nèi)存池。"一個(gè)類(lèi)的所有對(duì)象都分配在同一個(gè)內(nèi)存池對(duì)象中"這一需求很自然的設(shè)計(jì)方法就是為這樣的類(lèi)聲明一個(gè)靜態(tài)內(nèi)存池對(duì)象，同時(shí)為了讓其所有對(duì)象都從這個(gè)內(nèi)存池中開(kāi)辟內(nèi)存，而不是缺省的從進(jìn)程堆中獲得，需要為該類(lèi)重載一個(gè)new運(yùn)算符。因?yàn)橄鄳?yīng)地，回收也是面向內(nèi)存池，而不是進(jìn)程的缺省堆，還需要重載一個(gè)delete運(yùn)算符。在new運(yùn)算符中用內(nèi)存池的Alloc函數(shù)滿足所有該類(lèi)對(duì)象的內(nèi)存請(qǐng)求，而銷(xiāo)毀某對(duì)象則可以通過(guò)在delete運(yùn)算符中調(diào)用內(nèi)存池的Free完成。

6.2.5 性能比較

為了測(cè)試?yán)脙?nèi)存池后的效果，通過(guò)一個(gè)很小的測(cè)試程序可以發(fā)現(xiàn)采用內(nèi)存池機(jī)制后耗時(shí)為297 ms。而沒(méi)有采用內(nèi)存池機(jī)制則耗時(shí)625 ms，速度提高了52.48%。速度提高的原因可以歸結(jié)為幾點(diǎn)，其一，除了偶爾的內(nèi)存申請(qǐng)和銷(xiāo)毀會(huì)導(dǎo)致從進(jìn)程堆中分配和銷(xiāo)毀內(nèi)存塊外，絕大多數(shù)的內(nèi)存申請(qǐng)和銷(xiāo)毀都由內(nèi)存池在已經(jīng)申請(qǐng)到的內(nèi)存塊中進(jìn)行，而沒(méi)有直接與進(jìn)程堆打交道，而直接與進(jìn)程堆打交道是很耗時(shí)的操作；其二，這是單線程環(huán)境的內(nèi)存池，可以看到內(nèi)存池的Alloc和Free操作中并沒(méi)有加線程保護(hù)措施。因此如果類(lèi)A用到該內(nèi)存池，則所有類(lèi)A對(duì)象的創(chuàng)建和銷(xiāo)毀都必須發(fā)生在同一個(gè)線程中。但如果類(lèi)A用到內(nèi)存池，類(lèi)B也用到內(nèi)存池，那么類(lèi)A的使用線程可以不必與類(lèi)B的使用線程是同一個(gè)線程。

另外，在第1章中已經(jīng)討論過(guò)，因?yàn)閮?nèi)存池技術(shù)使得同類(lèi)型的對(duì)象分布在相鄰的內(nèi)存區(qū)域，而程序會(huì)經(jīng)常對(duì)同一類(lèi)型的對(duì)象進(jìn)行遍歷操作。因此在程序運(yùn)行過(guò)程中發(fā)生的缺頁(yè)應(yīng)該會(huì)相應(yīng)少一些，但這個(gè)一般只能在真實(shí)的復(fù)雜應(yīng)用環(huán)境中進(jìn)行驗(yàn)證。

6.3 本章小結(jié)

內(nèi)存的申請(qǐng)和釋放對(duì)一個(gè)應(yīng)用程序的整體性能影響極大，甚至在很多時(shí)候成為某個(gè)應(yīng)用程序的瓶頸。消除內(nèi)存申請(qǐng)和釋放引起的瓶頸的方法往往是針對(duì)內(nèi)存使用的實(shí)際情況提供一個(gè)合適的內(nèi)存池。內(nèi)存池之所以能夠提高性能，主要是因?yàn)樗軌蚶脩?yīng)用程序的實(shí)際內(nèi)存使用場(chǎng)景中的某些"特性"。比如某些內(nèi)存申請(qǐng)與釋放肯定發(fā)生在一個(gè)線程中，某種類(lèi)型的對(duì)象生成和銷(xiāo)毀與應(yīng)用程序中的其他類(lèi)型對(duì)象要頻繁得多，等等。針對(duì)這些特性，可以為這些特殊的內(nèi)存使用場(chǎng)景提供量身定做的內(nèi)存池。這樣能夠消除系統(tǒng)提供的缺省內(nèi)存機(jī)制中，對(duì)于該實(shí)際應(yīng)用場(chǎng)景中的不必要的操作，從而提升應(yīng)用程序的整體性能。

posted on 2009-09-22 00:44 abilitytao 閱讀(595) 評(píng)論(0)  編輯 收藏 引用