《0bug-C/C++商用工程之道》節選01--記憶體棧-1

<a></a>

記憶體塊如果要提升可重用性，必須對記憶體塊尺寸進行取模，否則的話，很容易因為幾個Bytes的偏差，導緻記憶體塊無法重用，被迫向系統頻繁申請新的記憶體空間，那意義就不大了。

取模的主要目的，是減少記憶體塊的種類，以有限幾個尺寸的記憶體塊，應對絕大多數記憶體使用要求。

筆者看過STL的記憶體管理子產品源代碼，對其記憶體塊的取模機制深表欽佩，是以，在筆者自己的記憶體池中，也是按照這種方式取模。

提示：32位系統，有個位元組對齊問題，即一個程式變量單元，如一個結構體，一個記憶體塊，如果其尺寸不是4Bytes的整倍數，作業系統會按照比它大的整倍數配置設定記憶體，這其實也是作業系統在取模。比如我們的一個結構體為7Bytes，作業系統配置設定時會配置設定8Bytes，一個14Bytes的記憶體塊，作業系統會配置設定16Bytes，這主要是簡化記憶體位址運算，以一定的記憶體消耗，來提升程式的運作速度。

我們對記憶體的取模也是這個原理，當然，我們不可能像作業系統那樣，機械地以4Bytes為模數，那樣，記憶體塊種類還是太多，管理起來壓力很大，記憶體池的效率也不高。

筆者仿造STL的取模方式，在記憶體池中按照如下邏輯取模，簡單說來，就是從16Bytes開始，以兩倍方式遞增模數。直到4G記憶體為止。當然，實際使用時，超過1M的記憶體塊，一般應用很少，即使有，基本上也屬于應用程式永久緩沖區，很少會中途頻繁釋放，是以，筆者的記憶體池管理，一般模數為16Bytes~1M即可。

序号

記憶體塊大小模數（Bytes）

應對申請需求（Bytes）

1

16

1~16

2

32

17~32

3

64

33~64

4

128

65~128

5

256

129~256

6

512

257~512

7

1k

513~1k

8

2k

1k+1~2k

9

4k

2k+1~4k

10

8k

4k+1~8k

11

16k

8k+1~16k

12

32k

16k+1~32k

13

64k

32k+1~64k

14

128k

64k+1~128k

15

256k

128k+1~256k

512k

256k+1~512k

17

1M

512k+1~1M

圖7.1：記憶體模數表

如表7.1所示，記憶體池實際上是一個樹型資料結構在管理，每一種類型的記憶體塊，構成一個連結清單，形成樹的“右枝”，而所有右枝的鍊頭，又是以一個連結清單在管理，形成樹的“左枝”。請注意，這并不是二叉樹，還是一顆普通的樹結構。如下圖所示：

<a href="http://blog.51cto.com/attachment/201106/100047795.jpg" target="_blank"></a>

圖7.2：記憶體管理樹模型

我們舉個例子，當應用程式申請一塊57Bytes的記憶體塊，程式邏輯會沿着樹的左枝，從頭到尾比對，首先是16Bytes的的管理鍊，由于57&gt;16，是以，無法在這根右枝進行管理，是以繼續往下，32Bytes也不行，64Bytes，比57要大，可以使用，是以，就在64Bytes這根右枝實作記憶體塊管理。

管理原則：配置設定時，首先在合适的右枝尋找可用的記憶體塊，如果有，則直接配置設定給應用程式重用該塊，如果沒有，則向系統申請一塊64Bytes的記憶體塊，配置設定給應用程式使用。而當應用程式釋放時，記憶體塊本身是64Bytes的，是以，可以直接挂回到64Bytes這根右枝，等待下次重用。

提示：這裡面有一個隐含的推論，如果一個應用程式，需要一塊57Bytes的記憶體塊，那麼，我們配置設定一塊比它大的記憶體塊，比如64Bytes的記憶體塊，是完全可以的，應用程式不關心自己實際獲得的記憶體塊大小，同時，這種稍稍超大的配置設定機制，也不回引發任何的記憶體溢出bug，反而更安全，是以，這種記憶體取模配置設定的思路，是完全可行的。

雖然上文我們讨論的是以連結清單方式管理，不過，在實做中，筆者發現一個問題，即連結清單效率不高，原因很簡單，筆者的連結清單是以隊列方式管理，每次從右枝取出記憶體塊，是從連結清單頭取出，但釋放時，将記憶體塊推回右枝，需要循環周遊到連結清單尾部進行挂鍊操作。這在高速的記憶體申請和釋放時，會嚴重影響連結清單的效率。

筆者經過思考，發現一個問題，當一個記憶體塊被推回一個右枝，其實已經是無屬性的，比如，64Bytes這個右枝上，挂的都是64Bytes大小的記憶體塊，應用程式申請時，使用任何一塊都是可以的，無需考慮這塊是在鍊頭還是鍊尾，同時，申請的記憶體塊，都是需要初始化的，應用程式也不關心這塊記憶體塊是否剛剛被使用完，還是已經空閑很久了。筆者了解這個記憶體樹的右枝，其實已經是前文所說的“被動池”邏輯了。

我們知道，在“推”入和“提取”這個邏輯上，“棧”的效率遠高于“隊列”，通常我們不使用棧的唯一原因，主要是棧是“後進先出”邏輯，而隊列是“先進先出”邏輯，而我們常見的應用模型，一般都有資料順序要求，是以，隊列的使用場合，遠多于棧結構。

但此處既然我們已經明确論證了，記憶體塊無順序需求，那麼，我們完全可以使用棧模型來管理記憶體樹的右枝，以提高效率。

這在實做時非常簡單，當應用程式釋放一塊記憶體，我們需要推回右枝時，直接将其挂接到鍊頭即可，取消了無意義的循環周遊鍊尾的操作，雖然，下次申請時，最後釋放的一塊記憶體會被最先配置設定使用，但這又有什麼關系呢？

這個優化看似很小，但實做時威力驚人，經筆者測試，記憶體塊的申請和釋放吞吐量，在“隊列”管理方式下，每秒僅5萬次左右，一旦使用“棧”方式管理，迅速提升到40~50萬次，提升了整整一個數量級。

正因為如此，筆者才将記憶體池最核心的記憶體管理子產品，定名為記憶體棧（Memory Stack）。

提示：在進行程式開發時，很多時候，需要針對業務需求進行分析，實作針對性優化，很多時候，很小的一點優化，都可以大幅度提升程式的性能。反過來說，通用的優化其實不存在，隻有深刻了解了業務需求之後，才有可能實施有效的優化方案。

提示：原則上，程式開發應該遵循“先實作，後優化”的原則，筆者常說的“先解決有無問題，再解決好壞問題”，也是這個意思，本章在此先讨論優化，是因為筆者這個記憶體池在實踐中已經經過了多次優化，有條件讨論此事，并不意味着可以再程式實作前實施優化，請各位讀者關注這個細節。事實上，本書展示的記憶體池，已經是筆者第19個版本，中間經過了十幾次優化的結果。

讨論完上面的問題，我們再來讨論一下基本資料結構管理的問題。我們知道，雖然我們的記憶體池是樹結構管理，但具體到每個右枝上，還是連結清單，而連結清單元素是動态申請的，依賴内部指向下一進制素的指針，實作連結關系。

具體到我們記憶體塊管理上，我們發現一個基本的連結清單元素，至少需要定義成如下形式：

typedef struct _CHAIN_TOKEN_

{

    struct _CHAIN_TOKEN_* m_pNext;  //指向下一連結清單元素的指針

    char* m_pBuffer;                //指向真實記憶體塊的指針

}SChainToken;

這就帶來一個問題，連結清單的元素，應該分為兩部分，一部分是實作連結清單管理的邏輯資料，如：m_pNext，另一部分，是業務相關的資料，如m_pBuffer，這樣的資料結構，造成程式開發非常麻煩。

比如一個簡單的記憶體申請和釋放動作，以上述資料結構管理，其基本邏輯如下：

記憶體申請：

1、檢查連結清單有無空閑記憶體單元

2、如果有，提取其中的m_pBuffer，準備傳回給應用程式使用

3、從連結清單中解除安裝已經為空的連結清單管理元素，直接釋放給系統（注意，無管控的記憶體塊釋放，記憶體碎片的隐患）

記憶體釋放：

1、尋找合适的鍊，準備做挂鍊操作

2、申請一個連結清單管理單元，将記憶體塊的指針放入其中的m_pBuffer

3、執行挂鍊操作，填充m_pBext指針

大家注意到沒有，我們本意是記憶體管理，減小記憶體碎片，但是，為了實作連結清單的管理，反而中間引入了一個多餘的連結清單單元申請和釋放邏輯，反而增加了記憶體碎片的産生可能，這種方法當然不可取。

另外，這裡還有一個隐患，我們配置設定給應用程式的記憶體塊，其中所有的記憶體單元，都是對應用程式透明的，應用程式可以任意使用，這說明，這塊記憶體塊中，沒有存儲任何關于記憶體塊尺寸的資訊，當應用程式釋放指針時，我們面臨一個問題，就是怎麼确定這根指針指向的記憶體塊，究竟有多大，應該挂在哪個右枝上，等待下次使用。

這個問題不解決，上述的記憶體釋放邏輯的第一步，尋找合适的鍊，根本無法完成。

是以，為了記錄記憶體塊的尺寸資訊，我們必須内部再建立一個映射表，将我們管理的每根記憶體塊指針，在申請時的具體尺寸，都記錄下來，等釋放時，需要根據指針，逆查其對應的長度資料，才能完成功能。

筆者做開發有個原則：“<b>簡單的程式才是好程式</b>”，上述邏輯雖然最終也能完成功能，但無論怎麼看，都太複雜了，不是好的解決方案。

為此，筆者經過了較長時間的思考，發現所有問題的核心焦點，無非隻有兩條：

1、如何使連結清單的管理資料，不要發生新的動态記憶體配置設定。

2、如何使配置設定出去的指針，能夠攜帶相關的緩沖區尺寸資訊，避免額外的存儲和查詢壓力。

經過分析，筆者突發奇想，既然我們記憶體池管理的就是記憶體塊，就有存儲能力，為什麼我們不能利用記憶體塊做一點自己的管理資料存儲呢？大不了這個記憶體塊實際可用記憶體，比我們從作業系統申請的，要小一點，但這又有什麼關系呢？應用程式需要的隻是自己需要的記憶體塊，這個記憶體塊原來有多大？能給應用程式使用的又有多大？應用程式并不關心。

經過考慮，筆者做了如下一個結構體：

typedef struct _TONY_MEM_BLOCK_HEAD_

    ULONG m_ulBlockSize;                        //記憶體塊的尺寸

    struct _TONY_MEM_BLOCK_HEAD_* m_pNext;      //指向下一連結清單元素的指針

}STonyMemoryBlockHead;

//本結構體的長度，經過計算，恒定為8Bytes

const ULONG STonyMemoryBlockHeadSize=sizeof(STonyMemoryBlockHead);

上述結構體，包含了記憶體塊尺寸資訊，來滿足釋放時查找的需求，同時，包含了指向下一進制素的指針，這個指針，在配置設定給應用程式使用時，是無效的，隻有當這個記憶體塊挂接在連結清單中時，才有意義。

筆者這麼思考，當我們向系統申請一個記憶體塊，比如說64Bytes，我們記憶體池占用其中最開始的8Bytes來存儲上述資訊，也就是說，實際能給應用程式使用的，隻有56Bytes。如圖7.3：

<a href="http://blog.51cto.com/attachment/201106/100227729.jpg" target="_blank"></a>

圖7.3：記憶體塊組織結構

我們假定這個記憶體塊的真實尺寸為N Bytes，我們從系統申請的首指針為p0，那麼，我們占用8Bytes作為管理使用，當應用程式申請時，我們真實配置設定給應用程式的指針為p1=(p0+8)。這樣，當應用程式釋放時，我們隻需要執行p0=（p1-8），即可求出原始首位址，并以此獲得所有的管理資訊。當最後向系統釋放記憶體時，我們隻要記得釋放p0即可。

提示：此處可能出于業務考慮，有點違背C和C++無錯化程式設計方法中，關于指針不得參與四則運算的原則，不過，沒辦法，需求如此，隻有這條路走了。是以，違背就違背一點了。

唯一需要我們注意的細節，是我們在分析應用程式的記憶體申請需求時，不能以申請的記憶體塊的真實尺寸進行比對，而應該比對減去8Bytes之後的資料。即64Bytes這個右枝上提供的記憶體，隻有56Bytes大小，如果超過這個值，請找下一鍊，即到128 Bytes這個右枝處理，當然，此時的128 Byte的右枝，也僅能提供120 Bytes的記憶體塊，以此類推。

有鑒于此，筆者做了如下的宏定義，來界定所有的計算行為：

//根據一個應用程式資料塊的長度，計算一個記憶體塊的真實大小，即n+8

#define TONY_MEM_BLOCK_SIZE(nDataLength) \

     (nDataLength+STonyMemoryBlockHeadSize)

//根據向系統申請的記憶體塊，計算其應用程式資料記憶體的真實大小，即n-8

#define TONY_MEM_BLOCK_DATA_SIZE(nBlockSize) \

     (nBlockSize-STonyMemoryBlockHeadSize)

//根據應用程式釋放的指針，逆求真實的記憶體塊指針，即p0=p1-8

#define TONY_MEM_BLOCK_HEAD(pData) \

     ((STonyMemoryBlockHead*)(((char*)pData)-STonyMemoryBlockHeadSize))

//根據一個記憶體塊的真實指針，求資料記憶體塊的指針，即p1=p0+8

#define TONY_MEM_BLOCK_DATA(pHead) \

     (((char*)pHead)+STonyMemoryBlockHeadSize)

//最小記憶體塊長度，16 Bytes，由于我們管理占用8 Bytes，這個最小長度不能再小了，

//否則無意義，即使這樣，我們最小的記憶體塊，能配置設定給應用程式使用的，僅有8 Bytes。

#define TONY_XIAO_MEMORY_STACK_BLOCK_MIN 16

//這是管理的最大記憶體塊長度，1M，如前文表中所示，超過此限制，記憶體池停止服務

//改為直接向系統申請和釋放。

#define TONY_XIAO_MEMORY_STACK_MAX_SAVE_BLOCK_SIZE (1*1024*1024)