在 C++ 編程的世界里，頻繁地進(jìn)行內(nèi)存分配與釋放操作，就像是一場無休無止的 “資源爭奪戰(zhàn)”。每次使用 new 和 delete，不僅消耗大量的 CPU 時間在系統(tǒng)調(diào)用上，還極易引發(fā)內(nèi)存碎片化，讓程序性能大打折扣。想象一下，一個大型游戲在關(guān)鍵時刻，因?yàn)閮?nèi)存管理的低效卡頓，玩家體驗(yàn)瞬間崩塌；或是一個高頻交易系統(tǒng)，因內(nèi)存分配延遲錯失良機(jī)。而今天，我們即將開啟一段神奇之旅 —— 用 C++ 代碼打造一個高性能內(nèi)存池，將這些困擾一掃而空，讓程序如虎添翼，掌控內(nèi)存的高效利用。

一、引言（Introduction）

1.1 內(nèi)存管理困境，你中招了嗎？

在 C++ 編程的世界里，內(nèi)存管理猶如一場精細(xì)的舞蹈，一步踏錯，就可能引發(fā)性能的 “滑鐵盧”。當(dāng)我們使用默認(rèn)的內(nèi)存管理函數(shù)，如 new/delete 或 malloc/free 在堆上分配和釋放內(nèi)存時，一些隱藏的問題正悄然滋生。

想象一下，你正在開發(fā)一款實(shí)時圖形渲染引擎，每一幀都需要快速地創(chuàng)建和銷毀大量的圖形對象。使用 new 來分配這些對象的內(nèi)存，系統(tǒng)首先得在內(nèi)部維護(hù)的內(nèi)存空閑塊表中，依據(jù)特定算法查找合適的空閑內(nèi)存塊。要是找到的塊比需求大，還得切割，之后更新表格，這一系列操作帶來了不小的額外開銷。就好比快遞員在一個雜亂無章的倉庫里找包裹，每次都得花費(fèi)大量時間翻找、整理，效率自然高不起來。

頻繁地分配與釋放不同大小的內(nèi)存塊，還會導(dǎo)致內(nèi)存碎片問題。這些碎片如同城市中零散分布、無法利用的小塊空地，夾雜在已分配的內(nèi)存之間，使得后續(xù)較大內(nèi)存需求難以得到滿足。即使系統(tǒng)試圖合并相鄰空閑塊，但面對復(fù)雜的內(nèi)存使用情況，也常常有心無力。最終，內(nèi)存利用率大打折扣，程序運(yùn)行起來越來越慢，就像道路被雜物堵塞，交通逐漸癱瘓。

更令人頭疼的是內(nèi)存泄漏。倘若在代碼的某個角落，new 出來的內(nèi)存忘記用 delete 釋放，這就好比打開水龍頭后沒關(guān)緊，水（內(nèi)存）一直在流，卻沒有回收的機(jī)制。隨著程序運(yùn)行，可用內(nèi)存越來越少，直到系統(tǒng)不堪重負(fù)，甚至崩潰，辛苦構(gòu)建的程序大廈可能因這一小小的 “疏忽” 轟然倒塌。

1.2 內(nèi)存池登場，救星來了！

就在傳統(tǒng)內(nèi)存管理陷入困境之時，內(nèi)存池宛如一位身披鎧甲的騎士閃亮登場。內(nèi)存池，簡單來說，是在程序啟動之初，就預(yù)先申請一塊較大的連續(xù)內(nèi)存區(qū)域，就好比提前圈出一大片專屬的 “內(nèi)存領(lǐng)地”。這片領(lǐng)地被精心劃分成一個個大小相等（通常情況下）的小內(nèi)存塊，猶如整齊排列的儲物格。

當(dāng)程序運(yùn)行過程中需要分配內(nèi)存時，直接從這片內(nèi)存池中 “提貨”，也就是取出合適的內(nèi)存塊交付使用，而無需頻繁向操作系統(tǒng) “求情” 索要內(nèi)存。就像超市有自己的倉庫提前備好貨物，顧客來買東西時直接從倉庫取，比每次缺貨都臨時向供應(yīng)商進(jìn)貨快多了。如此一來，省去了系統(tǒng)在內(nèi)部空閑塊表中反復(fù)查找、切割、更新的繁瑣流程，內(nèi)存分配速度大幅提升。

由于內(nèi)存池分配的是預(yù)先劃分好的固定大小塊，避免了像傳統(tǒng)方式那樣隨意切割內(nèi)存造成的碎片，內(nèi)存空間得以規(guī)整排列，利用率大大提高。而且，內(nèi)存池通常設(shè)有回收機(jī)制，當(dāng)某個內(nèi)存塊使用完畢，會被精準(zhǔn)地歸還到池中，等待下次復(fù)用，就像圖書館的書被借走看完后又還回書架，而不是被隨意丟棄。這一機(jī)制有效杜絕了因忘記釋放內(nèi)存而導(dǎo)致的泄漏問題，讓程序的內(nèi)存管理更加穩(wěn)健、可靠，為長時間穩(wěn)定運(yùn)行保駕護(hù)航。

二、內(nèi)存池技術(shù)詳解

2.1 什么是內(nèi)存池

內(nèi)存池（Memory Pool），也被稱為對象池（Object Pool），是一種內(nèi)存管理策略。在這種策略中，內(nèi)存被劃分為固定大小的塊，這些塊被組織在一起并被稱為“池”。當(dāng)程序需要分配內(nèi)存時，它會從內(nèi)存池中獲取一個塊，而不是直接從操作系統(tǒng)請求內(nèi)存。

內(nèi)存池的主要優(yōu)點(diǎn)是它可以減少內(nèi)存分配和釋放的開銷。因?yàn)閮?nèi)存池中的塊是預(yù)先分配的，所以分配內(nèi)存只需要從池中取出一個塊，而不需要進(jìn)行系統(tǒng)調(diào)用。同樣，釋放內(nèi)存只需要將塊放回池中，而不需要通知操作系統(tǒng)。這種方式可以大大提高內(nèi)存分配和釋放的速度。

此外，內(nèi)存池還可以減少內(nèi)存碎片化。因?yàn)樗械膲K都是相同大小的，所以它們可以緊密地排列在一起，而不會留下無法使用的空隙。這種方式可以提高內(nèi)存的利用率，特別是對于那些需要大量小塊內(nèi)存的程序。然而，內(nèi)存池并不是萬能的。它也有一些缺點(diǎn)，比如它不能很好地處理大塊內(nèi)存的分配，因?yàn)榇髩K內(nèi)存的分配可能會導(dǎo)致內(nèi)存池中的空間被浪費(fèi)。此外，內(nèi)存池的管理也會帶來一些開銷，特別是當(dāng)內(nèi)存池需要擴(kuò)展或收縮時。

總的來說，內(nèi)存池是一種強(qiáng)大的工具，它可以幫助我們更有效地管理內(nèi)存。但是，像所有工具一樣，我們需要理解它的優(yōu)點(diǎn)和缺點(diǎn)，以便在適當(dāng)?shù)那闆r下使用它。

圖片

2.2 為什么需要內(nèi)存池

⑴內(nèi)存碎片問題

造成堆利用率很低的一個主要原因就是內(nèi)存碎片化。如果有未使用的存儲器，但是這塊存儲器不能用來滿足分配的請求，這時候就會產(chǎn)生內(nèi)存碎片化問題。內(nèi)存碎片化分為內(nèi)部碎片和外部碎片。

內(nèi)部碎片：內(nèi)部碎片是指一個已分配的塊比有效載荷大時發(fā)生的。(假設(shè)以前分配了10個大小的字節(jié)，現(xiàn)在只用了5個字節(jié)，則剩下的5個字節(jié)就會內(nèi)碎片)。內(nèi)部碎片的大小就是已經(jīng)分配的塊的大小和他們的有效載荷之差的和。因此內(nèi)部碎片取決于以前請求內(nèi)存的模式和分配器實(shí)現(xiàn)(對齊的規(guī)則)的模式。

外部碎片：假設(shè)系統(tǒng)依次分配了16byte、8byte、16byte、4byte，還剩余8byte未分配。這時要分配一個24byte的空間，操作系統(tǒng)回收了一個上面的兩個16byte，總的剩余空間有40byte，但是卻不能分配出一個連續(xù)24byte的空間，這就是外碎片問題。

圖片

⑵申請效率問題

例如：我們上學(xué)家里給生活費(fèi)一樣，假設(shè)一學(xué)期的生活費(fèi)是6000塊。

• 方式1：開學(xué)時6000塊直接給你，自己保管，自己分配如何花。
• 方式2：每次要花錢時，聯(lián)系父母，父母轉(zhuǎn)錢。

同樣是6000塊錢，第一種方式的效率肯定更高，因?yàn)榈诙N方式跟父母的溝通交互成本太高了。

同樣的道理，程序就像是上學(xué)的我們，操作系統(tǒng)就像父母，頻繁申請內(nèi)存的場景下，每次需要內(nèi)存，都像系統(tǒng)申請效率必然有影響。

三、C++內(nèi)存管理機(jī)制

3.1 C++內(nèi)存分配與釋放

在C++中，內(nèi)存的分配和釋放是一個非常重要的環(huán)節(jié)。理解這個過程，對于我們深入理解內(nèi)存池的設(shè)計與實(shí)現(xiàn)，有著至關(guān)重要的作用。

首先，我們來看一下C++中的內(nèi)存分配。在C++中，我們通常使用new操作符來分配內(nèi)存。當(dāng)我們寫下如下代碼：

int* p = new int;

這行代碼做了什么呢？首先，new操作符會向操作系統(tǒng)請求一塊內(nèi)存，大小為一個int的大小。如果請求成功，操作系統(tǒng)會返回這塊內(nèi)存的地址，然后new操作符會將這個地址賦值給指針p。這樣，我們就成功地在堆（Heap）上分配了一塊內(nèi)存。

那么，這個過程中有什么需要我們注意的地方呢？首先，我們需要注意的是，new操作符的執(zhí)行效率。因?yàn)閚ew操作符需要向操作系統(tǒng)請求內(nèi)存，這個過程涉及到了系統(tǒng)調(diào)用，是一個相對耗時的操作。因此，如果我們在程序中頻繁地使用new操作符，可能會導(dǎo)致程序的執(zhí)行效率降低。

其次，我們需要注意的是，new操作符可能會失敗。當(dāng)操作系統(tǒng)的可用內(nèi)存不足時，new操作符會返回一個空指針。因此，我們在使用new操作符時，需要檢查其返回值，以防止內(nèi)存分配失敗。

那么，我們?nèi)绾吾尫艃?nèi)存呢？在C++中，我們使用delete操作符來釋放內(nèi)存。當(dāng)我們寫下如下代碼：

delete p;

這行代碼做了什么呢？delete操作符會將p指向的內(nèi)存塊返回給操作系統(tǒng)，這樣，這塊內(nèi)存就可以被其他程序使用了。同時，為了防止產(chǎn)生野指針，delete操作符會將p的值設(shè)置為nullptr。

在使用delete操作符時，我們需要注意的是，必須確保要刪除的指針是由new操作符分配的。如果我們試圖刪除一個非法的指針，或者是一個已經(jīng)被刪除的指針，都會導(dǎo)致未定義的行為。此外，我們還需要注意，如果我們使用new[]操作符分配了一個數(shù)組，那么在刪除這個數(shù)組時，必須使用delete[]操作符，而不能使用delete操作符。

總的來說，C++中的內(nèi)存分配和釋放是一個相對復(fù)雜的過程，需要我們仔細(xì)處理。在接下來的章節(jié)中，我們將看到，內(nèi)存池可以幫助我們簡化這個過程，提高程序的執(zhí)行效率，同時也可以幫助我們更好地管理內(nèi)存，防止內(nèi)存泄漏和野指針的產(chǎn)生。

3.2 C++內(nèi)存管理的問題

雖然C++提供了new和delete操作符來幫助我們管理內(nèi)存，但在實(shí)際使用中，我們?nèi)匀粫龅揭恍﹩栴}。這些問題主要包括：

• 內(nèi)存碎片（Memory Fragmentation）：在C++中，頻繁地進(jìn)行內(nèi)存的分配和釋放，會導(dǎo)致內(nèi)存碎片的產(chǎn)生。內(nèi)存碎片是指一些小的、無法被有效利用的內(nèi)存塊。這些內(nèi)存塊雖然無法被有效利用，但仍然會占用系統(tǒng)資源，降低系統(tǒng)的性能。
• 內(nèi)存泄漏（Memory Leak）：在C++中，如果我們分配了內(nèi)存，但忘記釋放，就會導(dǎo)致內(nèi)存泄漏。內(nèi)存泄漏會導(dǎo)致系統(tǒng)的可用內(nèi)存不斷減少，嚴(yán)重時甚至可能導(dǎo)致系統(tǒng)崩潰。
• 野指針（Dangling Pointer）：在C++中，如果我們釋放了一塊內(nèi)存，但仍然有指針指向這塊內(nèi)存，這個指針就成為了野指針。野指針是非常危險的，因?yàn)槲覀儫o法預(yù)測對野指針的操作會有什么后果。
• 分配和釋放內(nèi)存的效率問題：在C++中，分配和釋放內(nèi)存需要調(diào)用操作系統(tǒng)的函數(shù)，這是一個相對耗時的操作。如果我們在程序中頻繁地分配和釋放內(nèi)存，可能會導(dǎo)致程序的執(zhí)行效率降低。

以上就是在C++中進(jìn)行內(nèi)存管理時可能會遇到的一些問題。在接下來的章節(jié)中，我們將看到，內(nèi)存池可以幫助我們解決這些問題，提高程序的執(zhí)行效率，同時也可以幫助我們更好地管理內(nèi)存，防止內(nèi)存泄漏和野指針的產(chǎn)生。

3.3 內(nèi)存池解決的問題

內(nèi)存池（Memory Pool）是一種內(nèi)存管理策略。通過預(yù)先在內(nèi)存中分配一大塊連續(xù)的內(nèi)存空間，然后將這塊內(nèi)存空間劃分為大小相等的小塊，當(dāng)程序需要分配內(nèi)存時，直接從內(nèi)存池中分配一塊小內(nèi)存，而不是直接向操作系統(tǒng)申請。這種方式可以有效地解決C++內(nèi)存管理中的一些問題。

• 解決內(nèi)存碎片問題：因?yàn)閮?nèi)存池中的內(nèi)存塊大小是固定的，所以不會出現(xiàn)因?yàn)轭l繁分配和釋放不同大小的內(nèi)存導(dǎo)致的內(nèi)存碎片問題。
• 提高內(nèi)存分配效率：內(nèi)存池在程序啟動時就已經(jīng)預(yù)先分配了一大塊內(nèi)存，所以在程序運(yùn)行過程中分配和釋放內(nèi)存的速度會比直接使用new和delete操作符快很多。
• 防止內(nèi)存泄漏和野指針：內(nèi)存池通常會提供一些機(jī)制來跟蹤內(nèi)存的使用情況，比如引用計數(shù)等，這可以幫助我們更好地管理內(nèi)存，防止內(nèi)存泄漏和野指針的產(chǎn)生。

四、內(nèi)存池的設(shè)計

在C/C++中我們通常使用malloc,free或new,delete來動態(tài)分配內(nèi)存。一方面，因?yàn)檫@些函數(shù)涉及到了系統(tǒng)調(diào)用，所以頻繁的調(diào)用必然會導(dǎo)致程序性能的損耗；另一方面，頻繁的分配和釋放小塊內(nèi)存會導(dǎo)致大量的內(nèi)存碎片的產(chǎn)生，當(dāng)碎片積累到一定的量之后，將無法分配到連續(xù)的內(nèi)存空間，系統(tǒng)不得不進(jìn)行碎片整理來滿足分配到連續(xù)的空間，這樣不僅會導(dǎo)致系統(tǒng)性能損耗，而且會導(dǎo)致程序?qū)?nèi)存的利用率低下。

當(dāng)然，如果我們的程序不需要頻繁的分配和釋放小塊內(nèi)存，那就沒有使用內(nèi)存池的必要，直接使用malloc,free或new,delete函數(shù)即可。

• malloc優(yōu)點(diǎn):使用自由鏈表的數(shù)組，提高分配釋放效率；減少內(nèi)存碎片，可以合并空閑的內(nèi)存
• malloc缺點(diǎn)：為了維護(hù)隱式/顯示鏈表需要維護(hù)一些信息，空間利用率不高；在多線程的情況下，會出現(xiàn)線程安全的問題，如果以加鎖的方式解決，會大大降低效率。

4.1 為什么要使用內(nèi)存池

• 解決內(nèi)碎片問題
• 由于向內(nèi)存申請的內(nèi)存塊都是比較大的，所以能夠降低外碎片問題
• 一次性向內(nèi)存申請一塊大的內(nèi)存慢慢使用，避免了頻繁的向內(nèi)存請求內(nèi)存操作，提高內(nèi)存分配的效率
• 但是內(nèi)碎片問題無法避免，只能盡可能的降低

4.2 內(nèi)存池的演變

⑴最簡單的內(nèi)存分配器：做一個鏈表指向空閑內(nèi)存，分配就是取出一塊來，改寫鏈表，返回，釋放就是放回到鏈表里面，并做好歸并。注意做好標(biāo)記和保護(hù)，避免二次釋放，還可以花點(diǎn)力氣在如何查找最適合大小的內(nèi)存快的搜索上，減少內(nèi)存碎片，有空你了還可以把鏈表換成伙伴算法。

• 優(yōu)點(diǎn)： 實(shí)現(xiàn)簡單
• 缺點(diǎn)： 分配時搜索合適的內(nèi)存塊效率低，釋放回歸內(nèi)存后歸并消耗大，實(shí)際中不實(shí)用。

⑵定長內(nèi)存分配器：即實(shí)現(xiàn)一個 FreeList，每個 FreeList 用于分配固定大小的內(nèi)存塊，比如用于分配 32字節(jié)對象的固定內(nèi)存分配器，之類的。每個固定內(nèi)存分配器里面有兩個鏈表，OpenList 用于存儲未分配的空閑對象，CloseList用于存儲已分配的內(nèi)存對象，那么所謂的分配就是從 OpenList 中取出一個對象放到 CloseList 里并且返回給用戶，釋放又是從 CloseList 移回到 OpenList。分配時如果不夠，那么就需要增長 OpenList：申請一個大一點(diǎn)的內(nèi)存塊，切割成比如 64 個相同大小的對象添加到 OpenList中。這個固定內(nèi)存分配器回收的時候，統(tǒng)一把先前向系統(tǒng)申請的內(nèi)存塊全部還給系統(tǒng)。

• 優(yōu)點(diǎn)： 簡單粗暴，分配和釋放的效率高，解決實(shí)際中特定場景下的問題有效。
• 缺點(diǎn)： 功能單一，只能解決定長的內(nèi)存需求，另外占著內(nèi)存沒有釋放。

⑶哈希映射的FreeList 池：在定長分配器的基礎(chǔ)上，按照不同對象大小(8，16，32，64，128，256，512，1k…64K),構(gòu)造十多個固定內(nèi)存分配器，分配內(nèi)存時根據(jù)要申請內(nèi)存大小進(jìn)行對齊然后查H表，決定到底由哪個分配器負(fù)責(zé)，分配后要在內(nèi)存頭部的 header 處寫上 cookie，表示由該塊內(nèi)存哪一個分配器分配的，這樣釋放時候你才能正確歸還。如果大于64K，則直接用系統(tǒng)的 malloc作為分配，如此以浪費(fèi)內(nèi)存為代價你得到了一個分配時間近似O(1)的內(nèi)存分配器。這種內(nèi)存池的缺點(diǎn)是假設(shè)某個 FreeList 如果高峰期占用了大量內(nèi)存即使后面不用，也無法支援到其他內(nèi)存不夠的 FreeList，達(dá)不到分配均衡的效果。

• 優(yōu)點(diǎn)：這個本質(zhì)是定長內(nèi)存池的改進(jìn)，分配和釋放的效率高?？梢越鉀Q一定長度內(nèi)的問題。
• 缺點(diǎn)：存在內(nèi)碎片的問題，且將一塊大內(nèi)存切小以后，申請大內(nèi)存無法使用。多線程并發(fā)場景下，鎖競爭激烈，效率降低。

范例：sgi stl 六大組件中的空間配置器就是這種設(shè)計實(shí)現(xiàn)的。

4.3 內(nèi)存池的設(shè)計原則

內(nèi)存池（Memory Pool）的設(shè)計是一個復(fù)雜且需要深入理解計算機(jī)內(nèi)存管理的過程。設(shè)計一個高效的內(nèi)存池，我們需要遵循以下幾個原則：

• 最小化內(nèi)存分配次數(shù)：內(nèi)存分配是一個開銷較大的操作，頻繁的內(nèi)存分配和釋放會導(dǎo)致系統(tǒng)性能下降。因此，內(nèi)存池的設(shè)計應(yīng)盡可能減少內(nèi)存分配次數(shù)，一種常見的做法是預(yù)先分配一大塊內(nèi)存，然后在需要時從中劃分出小塊內(nèi)存。
• 減少內(nèi)存碎片：頻繁的內(nèi)存分配和釋放會導(dǎo)致內(nèi)存碎片，這會降低內(nèi)存的利用率。內(nèi)存池通過管理預(yù)先分配的內(nèi)存，可以有效地減少內(nèi)存碎片。
• 快速響應(yīng)內(nèi)存請求：內(nèi)存池應(yīng)能快速地響應(yīng)內(nèi)存請求，這需要內(nèi)存池有一個高效的數(shù)據(jù)結(jié)構(gòu)來管理可用的內(nèi)存塊。常見的做法是使用鏈表或者樹形結(jié)構(gòu)來管理內(nèi)存塊。
• 靈活的內(nèi)存管理：內(nèi)存池應(yīng)能靈活地管理內(nèi)存，包括內(nèi)存的分配、釋放和整理。這需要內(nèi)存池有一套完整的內(nèi)存管理策略。

以上就是設(shè)計內(nèi)存池需要遵循的原則，接下來我們將詳細(xì)介紹如何根據(jù)這些原則來設(shè)計和實(shí)現(xiàn)一個內(nèi)存池。

五、內(nèi)存池的實(shí)現(xiàn)方案

內(nèi)存池的實(shí)現(xiàn)原理大致如下：提前申請一塊大內(nèi)存由內(nèi)存池自己管理，并分成小片供給程序使用。程序使用完之后將內(nèi)存歸還到內(nèi)存池中（并沒有真正的從系統(tǒng)釋放），當(dāng)程序再次從內(nèi)存池中請求內(nèi)存時，內(nèi)存池將池子中的可用內(nèi)存片返回給程序使用。

我們在設(shè)計內(nèi)存池的實(shí)現(xiàn)方案時，需要考慮到以下問題：

①內(nèi)存池是否可以自動增長？

如果內(nèi)存池的最大空間是固定的（也就是非自動增長），那么當(dāng)內(nèi)存池中的內(nèi)存被請求完之后，程序就無法再次從內(nèi)存池請求到內(nèi)存。所以需要根據(jù)程序?qū)?nèi)存的實(shí)際使用情況來確定是否需要自動增長。

②內(nèi)存池的總內(nèi)存占用是否只增不減？

如果內(nèi)存池是自動增長的，就涉及到了“內(nèi)存池的總內(nèi)存占用是否是只增不減”這個問題了。試想，程序從一個自動增長的內(nèi)存池中請求了1000個大小為100KB的內(nèi)存片，并在使用完之后全部歸還給了內(nèi)存池，而且假設(shè)程序之后的邏輯最多之后請求10個100KB的內(nèi)存片，那么該內(nèi)存池中的900個100KB的內(nèi)存片就一直處于閑置狀態(tài)，程序的內(nèi)存占用就一直不會降下來。對內(nèi)存占用大小有要求的程序需要考慮到這一點(diǎn)。

③內(nèi)存池中內(nèi)存片的大小是否固定？

如果每次從內(nèi)存池中的請求的內(nèi)存片的大小如果不固定，那么內(nèi)存池中的每個可用內(nèi)存片的大小就不一致，程序再次請求內(nèi)存片的時候，內(nèi)存池就需要在“匹配最佳大小的內(nèi)存片”和“匹配操作時間”上作出衡量?！白罴汛笮〉膬?nèi)存片”雖然可以減少內(nèi)存的浪費(fèi)，但可能會導(dǎo)致“匹配時間”變長。

④內(nèi)存池是否是線程安全的？

是否允許在多個線程中同時從同一個內(nèi)存池中請求和歸還內(nèi)存片？這個線程安全可以由內(nèi)存池來實(shí)現(xiàn)，也可以由使用者來保證。

⑤內(nèi)存片分配出去之前和歸還到內(nèi)存池之后，其中的內(nèi)容是否需要被清除？

程序可能出現(xiàn)將內(nèi)存片歸還給內(nèi)存池之后，仍然使用內(nèi)存片的地址指針進(jìn)行內(nèi)存讀寫操作，這樣就會導(dǎo)致不可預(yù)期的結(jié)果。將內(nèi)容清零只能盡量的（也不一定能）將問題拋出來，但并不能解決任何問題，而且將內(nèi)容清零會消耗一定的CPU時間。所以，最終最好還是需要由內(nèi)存池的使用者來保證這種安全性。

⑥是否兼容std::allocator？

STL標(biāo)準(zhǔn)庫中的大多類都支持用戶提供一個自定義的內(nèi)存分配器，默認(rèn)使用的是std::allocator，如std::string：

typedef basic_string<char, char_traits<char>, allocator<char> > string;

如果我們的內(nèi)存池兼容std::allocator，那么我們就可以使用我們自己的內(nèi)存池來替換默認(rèn)的std::allocator分配器，如：

typedef basic_string<char, char_traits<char>, MemoryPoll<char> > mystring;

5.1 內(nèi)存池的基本結(jié)構(gòu)

內(nèi)存池的基本結(jié)構(gòu)主要包括兩個部分：內(nèi)存塊（Memory Block）和內(nèi)存塊鏈表（Memory Block List）。下面我們將詳細(xì)介紹這兩個部分。

• 內(nèi)存塊（Memory Block）：內(nèi)存塊是內(nèi)存池中最基本的單位，每個內(nèi)存塊都有一個固定的大小。內(nèi)存塊的大小可以根據(jù)實(shí)際需求進(jìn)行設(shè)置，但通常情況下，我們會設(shè)置多種大小的內(nèi)存塊，以滿足不同的內(nèi)存需求。
• 內(nèi)存塊鏈表（Memory Block List）：內(nèi)存塊鏈表是用來管理內(nèi)存塊的數(shù)據(jù)結(jié)構(gòu)。每個鏈表節(jié)點(diǎn)代表一個內(nèi)存塊，節(jié)點(diǎn)中包含了內(nèi)存塊的地址和狀態(tài)信息。通過內(nèi)存塊鏈表，我們可以快速地找到一個可用的內(nèi)存塊，也可以在內(nèi)存塊被釋放時，快速地將其加入到鏈表中。

在實(shí)際的設(shè)計中，我們還需要考慮到內(nèi)存池的擴(kuò)展性和靈活性。例如，我們可以設(shè)計一個動態(tài)的內(nèi)存池，當(dāng)內(nèi)存池中的內(nèi)存塊不足時，可以動態(tài)地增加內(nèi)存塊。另外，我們也可以設(shè)計多級內(nèi)存池，通過多級內(nèi)存池，我們可以更好地管理不同大小的內(nèi)存塊，提高內(nèi)存的利用率。

以上就是內(nèi)存池的基本結(jié)構(gòu)，接下來我們將詳細(xì)介紹如何根據(jù)這個結(jié)構(gòu)來實(shí)現(xiàn)一個內(nèi)存池。

5.2 內(nèi)存池的工作原理

⑴預(yù)分配策略

內(nèi)存池的高效首先得益于其預(yù)分配策略。在程序啟動之際，內(nèi)存池依據(jù)對程序運(yùn)行過程中內(nèi)存需求的預(yù)估，向操作系統(tǒng)一次性申請一塊容量較大的連續(xù)內(nèi)存空間，這就好比提前為一場盛宴準(zhǔn)備了充足的食材，集中采購顯然比賓客陸續(xù)點(diǎn)餐時廚師一次次臨時外出采購高效得多。

這塊內(nèi)存被劃分為多個大小固定的內(nèi)存塊，以適配常見的內(nèi)存分配需求。比如，對于一個頻繁創(chuàng)建小型數(shù)據(jù)結(jié)構(gòu)（如鏈表節(jié)點(diǎn)）的程序，內(nèi)存池會劃分出一批剛好能容納單個鏈表節(jié)點(diǎn)的小內(nèi)存塊。當(dāng)程序需要創(chuàng)建新節(jié)點(diǎn)時，直接從內(nèi)存池中取出一個預(yù)先備好的小內(nèi)存塊，無需像使用 new 時那樣，讓操作系統(tǒng)在碎片化的空閑內(nèi)存中艱難尋覓合適空間，再進(jìn)行切割、分配等繁瑣流程，大大節(jié)省了時間開銷。

⑵內(nèi)存塊管理

內(nèi)存池內(nèi)部精心維護(hù)著一個空閑內(nèi)存塊鏈表，這是它實(shí)現(xiàn)高效分配與回收的關(guān)鍵 “賬本”。鏈表中的每個節(jié)點(diǎn)對應(yīng)一個空閑內(nèi)存塊，它們通過指針相互串聯(lián)，猶如一條無形的鏈條串起了內(nèi)存池中的空閑資源。

當(dāng)程序請求分配內(nèi)存時，內(nèi)存池沿著鏈表快速遍歷，找到首個可用的空閑內(nèi)存塊，將其從鏈表中摘下交付給程序使用。這個過程如同從掛滿鑰匙的鑰匙環(huán)上迅速取下一把所需的鑰匙，速度極快。而當(dāng)內(nèi)存使用完畢，需要回收時，回收的內(nèi)存塊會被精準(zhǔn)插回空閑鏈表，通常是插在表頭位置，以便下次分配時能優(yōu)先被選用，就像歸還的鑰匙總是放在最順手可取的地方，方便下次快速找到。

由于內(nèi)存塊大小固定，不會出現(xiàn)因隨意切割導(dǎo)致的零碎空間，避免了內(nèi)存碎片的產(chǎn)生。而且，回收再利用機(jī)制使得內(nèi)存利用率大幅提升，曾經(jīng)被用過的內(nèi)存塊能迅速滿血復(fù)活，重新投入戰(zhàn)斗，為程序持續(xù)穩(wěn)定運(yùn)行提供堅實(shí)保障。

⑶多線程適配

在當(dāng)今多核處理器盛行，多線程編程廣泛應(yīng)用的時代，內(nèi)存池也具備出色的多線程適配能力。當(dāng)多個線程同時對內(nèi)存池發(fā)起內(nèi)存分配或回收請求時，沖突風(fēng)險驟升，就像多個人同時爭搶有限的資源容易亂套。

為應(yīng)對這一挑戰(zhàn)，內(nèi)存池引入了互斥鎖等同步機(jī)制。當(dāng)一個線程進(jìn)入內(nèi)存池執(zhí)行分配或回收操作時，會先獲取互斥鎖，將內(nèi)存池 “鎖住”，其他線程此時只能等待，如同排隊上公共廁所，門被占用時其他人只能在外等候。線程完成操作后，釋放互斥鎖，讓其他線程有機(jī)會進(jìn)入。

有些高性能內(nèi)存池還采用更精細(xì)的無鎖編程技術(shù)，利用原子操作等手段減少線程等待時間，進(jìn)一步提升并發(fā)性能，確保在多線程的復(fù)雜環(huán)境下，內(nèi)存池依然能有條不紊地運(yùn)行，為各個線程快速、穩(wěn)定地提供內(nèi)存服務(wù)。

5.3 C++實(shí)現(xiàn)內(nèi)存池的步驟

實(shí)現(xiàn)一個內(nèi)存池需要經(jīng)過以下幾個步驟：

• 預(yù)分配內(nèi)存：首先，我們需要預(yù)先分配一大塊內(nèi)存，這個內(nèi)存的大小可以根據(jù)實(shí)際需求進(jìn)行設(shè)置。預(yù)分配的內(nèi)存將被劃分為多個內(nèi)存塊，每個內(nèi)存塊的大小也可以根據(jù)需求進(jìn)行設(shè)置。
• 初始化內(nèi)存塊鏈表：然后，我們需要初始化內(nèi)存塊鏈表。鏈表中的每個節(jié)點(diǎn)代表一個內(nèi)存塊，節(jié)點(diǎn)中包含了內(nèi)存塊的地址和狀態(tài)信息。初始化內(nèi)存塊鏈表的過程就是將預(yù)分配的內(nèi)存劃分為多個內(nèi)存塊，并將這些內(nèi)存塊加入到鏈表中。
• 實(shí)現(xiàn)內(nèi)存分配函數(shù)：內(nèi)存分配函數(shù)是用來分配內(nèi)存的，當(dāng)有內(nèi)存請求時，內(nèi)存分配函數(shù)會從內(nèi)存塊鏈表中找到一個可用的內(nèi)存塊，并返回其地址。在這個過程中，我們需要考慮內(nèi)存塊的狀態(tài)，只有狀態(tài)為可用的內(nèi)存塊才能被分配。
• 實(shí)現(xiàn)內(nèi)存釋放函數(shù)：內(nèi)存釋放函數(shù)是用來釋放內(nèi)存的，當(dāng)有內(nèi)存被釋放時，內(nèi)存釋放函數(shù)會將對應(yīng)的內(nèi)存塊加入到內(nèi)存塊鏈表中，并將其狀態(tài)設(shè)置為可用。在這個過程中，我們需要考慮內(nèi)存塊的狀態(tài)，只有狀態(tài)為已分配的內(nèi)存塊才能被釋放。
• 實(shí)現(xiàn)內(nèi)存整理函數(shù)：內(nèi)存整理函數(shù)是用來整理內(nèi)存的，它可以將連續(xù)的可用內(nèi)存塊合并為一個大的內(nèi)存塊，也可以將大的內(nèi)存塊劃分為多個小的內(nèi)存塊。通過內(nèi)存整理，我們可以提高內(nèi)存的利用率，減少內(nèi)存碎片。

以上就是實(shí)現(xiàn)內(nèi)存池需要經(jīng)過的步驟，每個步驟都需要深入理解內(nèi)存管理的原理，才能設(shè)計出一個高效的內(nèi)存池。

5.4 內(nèi)存池的具體實(shí)現(xiàn)

計劃實(shí)現(xiàn)一個內(nèi)存池管理的類MemoryPool，它具有如下特性：

• 內(nèi)存池的總大小自動增長。
• 內(nèi)存池中內(nèi)存片的大小固定。
• 支持線程安全。
• 在內(nèi)存片被歸還之后，清除其中的內(nèi)容。
• 兼容std::allocator。

因?yàn)閮?nèi)存池的內(nèi)存片的大小是固定的，不涉及到需要匹配最合適大小的內(nèi)存片，由于會頻繁的進(jìn)行插入、移除的操作，但查找比較少，故選用鏈表數(shù)據(jù)結(jié)構(gòu)來管理內(nèi)存池中的內(nèi)存片。

MemoryPool中有2個鏈表，它們都是雙向鏈表（設(shè)計成雙向鏈表主要是為了在移除指定元素時，能夠快速定位該元素的前后元素，從而在該元素被移除后，將其前后元素連接起來，保證鏈表的完整性）：

• data_element_ 記錄以及分配出去的內(nèi)存片。
• free_element_ 記錄未被分配出去的內(nèi)存片。

MemoryPool實(shí)現(xiàn)代碼

代碼中使用了std::mutex等C++11才支持的特性，所以需要編譯器最低支持C++11：

#ifndef PPX_BASE_MEMORY_POOL_H_
#define PPX_BASE_MEMORY_POOL_H_

#include <climits>
#include <cstddef>
#include <mutex>

namespace ppx {
    namespace base {
        template <typename T, size_t BlockSize = 4096, bool ZeroOnDeallocate = true>
        class MemoryPool {
        public:
            /* Member types */
            typedef T               value_type;
            typedef T*              pointer;
            typedef T&              reference;
            typedef const T*        const_pointer;
            typedef const T&        const_reference;
            typedef size_t          size_type;
            typedef ptrdiff_t       difference_type;
            typedef std::false_type propagate_on_container_copy_assignment;
            typedef std::true_type  propagate_on_container_move_assignment;
            typedef std::true_type  propagate_on_container_swap;

            template <typename U> struct rebind {
                typedef MemoryPool<U> other;
            };

            /* Member functions */
            MemoryPool() noexcept;
            MemoryPool(const MemoryPool& memoryPool) noexcept;
            MemoryPool(MemoryPool&& memoryPool) noexcept;
            template <class U> MemoryPool(const MemoryPool<U>& memoryPool) noexcept;

            ~MemoryPool() noexcept;

            MemoryPool& operator=(const MemoryPool& memoryPool) = delete;
            MemoryPool& operator=(MemoryPool&& memoryPool) noexcept;

            pointer address(reference x) const noexcept;
            const_pointer address(const_reference x) const noexcept;

            // Can only allocate one object at a time. n and hint are ignored
            pointer allocate(size_type n = 1, const_pointer hint = 0);
            void deallocate(pointer p, size_type n = 1);

            size_type max_size() const noexcept;

            template <class U, class... Args> void construct(U* p, Args&&... args);
            template <class U> void destroy(U* p);

            template <class... Args> pointer newElement(Args&&... args);
            void deleteElement(pointer p);

        private:
            struct Element_ {
                Element_* pre;
                Element_* next;
            };

            typedef char* data_pointer;
            typedef Element_ element_type;
            typedef Element_* element_pointer;

            element_pointer data_element_;
            element_pointer free_element_;

            std::recursive_mutex m_;

            size_type padPointer(data_pointer p, size_type align) const noexcept;
            void allocateBlock();

            static_assert(BlockSize >= 2 * sizeof(element_type), "BlockSize too small.");
        };


        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::size_type
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::padPointer(data_pointer p, size_type align)
            const noexcept {
            uintptr_t result = reinterpret_cast<uintptr_t>(p);
            return ((align - result) % align);
        }



        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool()
            noexcept {
            data_element_ = nullptr;
            free_element_ = nullptr;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool(const MemoryPool& memoryPool)
            noexcept :
            MemoryPool() {
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool(MemoryPool&& memoryPool)
            noexcept {
            std::lock_guard<std::recursive_mutex> lock(m_);

            data_element_ = memoryPool.data_element_;
            memoryPool.data_element_ = nullptr;
            free_element_ = memoryPool.free_element_;
            memoryPool.free_element_ = nullptr;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        template<class U>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::MemoryPool(const MemoryPool<U>& memoryPool)
            noexcept :
            MemoryPool() {
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>&
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::operator=(MemoryPool&& memoryPool)
            noexcept {
            std::lock_guard<std::recursive_mutex> lock(m_);

            if (this != &memoryPool) {
                std::swap(data_element_, memoryPool.data_element_);
                std::swap(free_element_, memoryPool.free_element_);
            }
            return *this;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        MemoryPool<T, BlockSize, ZeroOnDeallocate>::~MemoryPool()
            noexcept {
            std::lock_guard<std::recursive_mutex> lock(m_);

            element_pointer curr = data_element_;
            while (curr != nullptr) {
                element_pointer prev = curr->next;
                operator delete(reinterpret_cast<void*>(curr));
                curr = prev;
            }

            curr = free_element_;
            while (curr != nullptr) {
                element_pointer prev = curr->next;
                operator delete(reinterpret_cast<void*>(curr));
                curr = prev;
            }
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::address(reference x)
            const noexcept {
            return &x;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::const_pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::address(const_reference x)
            const noexcept {
            return &x;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::allocateBlock() {
            // Allocate space for the new block and store a pointer to the previous one
            data_pointer new_block = reinterpret_cast<data_pointer> (operator new(BlockSize));
            element_pointer new_ele_pointer = reinterpret_cast<element_pointer>(new_block);
            new_ele_pointer->pre = nullptr;
            new_ele_pointer->next = nullptr;

            if (data_element_) {
                data_element_->pre = new_ele_pointer;
            }

            new_ele_pointer->next = data_element_;
            data_element_ = new_ele_pointer;
        }

        template <typename T, size_t BlockSize,  bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::allocate(size_type n, const_pointer hint) {
            std::lock_guard<std::recursive_mutex> lock(m_);

            if (free_element_ != nullptr) {
                data_pointer body =
                    reinterpret_cast<data_pointer>(reinterpret_cast<data_pointer>(free_element_) + sizeof(element_type));

                size_type bodyPadding = padPointer(body, alignof(element_type));

                pointer result = reinterpret_cast<pointer>(reinterpret_cast<data_pointer>(body + bodyPadding));

                element_pointer tmp = free_element_;

                free_element_ = free_element_->next;

                if (free_element_)
                    free_element_->pre = nullptr;

                tmp->next = data_element_;
                if (data_element_)
                    data_element_->pre = tmp;
                tmp->pre = nullptr;
                data_element_ = tmp;

                return result;
            }
            else {
                allocateBlock();

                data_pointer body =
                    reinterpret_cast<data_pointer>(reinterpret_cast<data_pointer>(data_element_) + sizeof(element_type));

                size_type bodyPadding = padPointer(body, alignof(element_type));

                pointer result = reinterpret_cast<pointer>(reinterpret_cast<data_pointer>(body + bodyPadding));

                return result;
            }
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::deallocate(pointer p, size_type n) {
            std::lock_guard<std::recursive_mutex> lock(m_);

            if (p != nullptr) {
                element_pointer ele_p =
                    reinterpret_cast<element_pointer>(reinterpret_cast<data_pointer>(p) - sizeof(element_type));

                if (ZeroOnDeallocate) {
                    memset(reinterpret_cast<data_pointer>(p), 0, BlockSize - sizeof(element_type));
                }

                if (ele_p->pre) {
                    ele_p->pre->next = ele_p->next;
                }

                if (ele_p->next) {
                    ele_p->next->pre = ele_p->pre;
                }

                if (ele_p->pre == nullptr) {
                    data_element_ = ele_p->next;
                }

                ele_p->pre = nullptr;
                if (free_element_) {
                    ele_p->next = free_element_;
                    free_element_->pre = ele_p;
                }
                else {
                    ele_p->next = nullptr;
                }
                free_element_ = ele_p;
            }
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::size_type
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::max_size()
            const noexcept {
            size_type maxBlocks = -1 / BlockSize;
            return (BlockSize - sizeof(data_pointer)) / sizeof(element_type) * maxBlocks;
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        template <class U, class... Args>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::construct(U* p, Args&&... args) {
            new (p) U(std::forward<Args>(args)...);
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        template <class U>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::destroy(U* p) {
            p->~U();
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        template <class... Args>
        inline typename MemoryPool<T, BlockSize, ZeroOnDeallocate>::pointer
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::newElement(Args&&... args) {
            std::lock_guard<std::recursive_mutex> lock(m_);
            pointer result = allocate();
            construct<value_type>(result, std::forward<Args>(args)...);
            return result;
        }

        template <typename T, size_t BlockSize, bool ZeroOnDeallocate>
        inline void
            MemoryPool<T, BlockSize, ZeroOnDeallocate>::deleteElement(pointer p) {
            std::lock_guard<std::recursive_mutex> lock(m_);
            if (p != nullptr) {
                p->~value_type();
                deallocate(p);
            }
        }
    }
}

#endif // PPX_BASE_MEMORY_POOL_H_


使用示例：
#include <iostream>
#include <thread>
using namespace std;
class Apple {
public:
    Apple() {
        id_ = 0;
        cout << "Apple()" << endl;
    }

    Apple(int id) {
        id_ = id;
        cout << "Apple(" << id_ << ")" << endl;
    }

    ~Apple() {
        cout << "~Apple()" << endl;
    }

    void SetId(int id) {
        id_ = id;
    }

    int GetId() {
        return id_;
    }
private:
    int id_;
};



void ThreadProc(ppx::base::MemoryPool<char> *mp) {
    int i = 0;
    while (i++ < 100000) {
        char* p0 = (char*)mp->allocate();

        char* p1 = (char*)mp->allocate();

        mp->deallocate(p0);

        char* p2 = (char*)mp->allocate();

        mp->deallocate(p1);
        
        mp->deallocate(p2);

    }
}

int main()
{
    ppx::base::MemoryPool<char> mp;
    int i = 0;
    while (i++ < 100000) {
        char* p0 = (char*)mp.allocate();

        char* p1 = (char*)mp.allocate();

        mp.deallocate(p0);

        char* p2 = (char*)mp.allocate();

        mp.deallocate(p1);

        mp.deallocate(p2);

    }

    std::thread th0(ThreadProc, &mp);
    std::thread th1(ThreadProc, &mp);
    std::thread th2(ThreadProc, &mp);

    th0.join();
    th1.join();
    th2.join();

    Apple *apple = nullptr;
    {
        ppx::base::MemoryPool<Apple> mp2;
        apple = mp2.newElement(10);
        int a = apple->GetId();
        apple->SetId(10);
        a = apple->GetId();

        mp2.deleteElement(apple);
    }

    apple->SetId(12);
    int b = -4 % 4;

    int *a = nullptr;
    {
        ppx::base::MemoryPool<int, 18> mp3;
        a =  mp3.allocate();
        *a = 100;
        //mp3.deallocate(a);

        int *b =  mp3.allocate();
        *b = 200;
        //mp3.deallocate(b);

        mp3.deallocate(a);
        mp3.deallocate(b);

        int *c = mp3.allocate();
        *c = 300;
    }

    getchar();
    return 0;
}

5.5避開這些坑，讓內(nèi)存池更完美

在探索內(nèi)存池的征途中，也有一些暗藏的 “礁石” 需要留意，稍有不慎，就可能讓內(nèi)存池這葉 “扁舟” 偏離高效運(yùn)行的航道。

內(nèi)存泄漏隱患是首當(dāng)其沖的問題。雖然內(nèi)存池本身旨在避免傳統(tǒng)內(nèi)存管理中的泄漏風(fēng)險，但倘若在內(nèi)存池的實(shí)現(xiàn)代碼里，對空閑鏈表的操作有誤，比如在回收內(nèi)存塊插入鏈表時指針賦值出錯，導(dǎo)致內(nèi)存塊 “迷失” 在內(nèi)存荒野，無法被再次分配，日積月累，就如同堤壩出現(xiàn)微小裂縫，最終也可能引發(fā)潰堤之災(zāi)，程序可用內(nèi)存被悄然蠶食。

線程同步問題宛如一團(tuán)亂麻，困擾著多線程環(huán)境下的內(nèi)存池應(yīng)用。當(dāng)多個線程高頻訪問內(nèi)存池，若互斥鎖使用不當(dāng)，就可能引發(fā)死鎖。例如線程 A 持有鎖 1 并等待鎖 2，而線程 B 持有鎖 2 又在等待鎖 1，二者僵持不下，內(nèi)存分配與回收流程陷入停滯，整個程序如同被施了定身咒，動彈不得，嚴(yán)重影響運(yùn)行效率與穩(wěn)定性。

過度的內(nèi)存預(yù)分配也是個容易踏入的誤區(qū)。開發(fā)者滿心想著為程序運(yùn)行備足 “彈藥”，卻未精準(zhǔn)預(yù)估內(nèi)存需求，申請了一塊大得離譜的內(nèi)存池。這不僅造成程序啟動初期內(nèi)存占用飆升，還可能導(dǎo)致大量內(nèi)存閑置浪費(fèi)，其他急需內(nèi)存的程序或系統(tǒng)組件只能望 “內(nèi)存” 興嘆，系統(tǒng)整體性能因此失衡，得不償失。

為躲開這些陷阱，嚴(yán)謹(jǐn)?shù)拇a審查與測試是關(guān)鍵護(hù)盾。在代碼編寫階段，對涉及內(nèi)存池操作的每一行代碼都要反復(fù)推敲，確保鏈表操作、指針賦值等準(zhǔn)確無誤；借助專業(yè)的內(nèi)存檢測工具，如 Valgrind 等，像偵探一樣揪出潛在的內(nèi)存泄漏點(diǎn)。對于多線程同步，運(yùn)用成熟的線程分析工具排查死鎖風(fēng)險，合理設(shè)計鎖的獲取與釋放邏輯，必要時采用更高級的無鎖編程技巧化解難題。在規(guī)劃內(nèi)存池大小時，結(jié)合性能分析數(shù)據(jù)與實(shí)際業(yè)務(wù)場景，精打細(xì)算，用最小的內(nèi)存開銷支撐程序的順暢運(yùn)行，讓內(nèi)存池在正確的軌道上全速前進(jìn)，助力程序性能騰飛。

六、并發(fā)內(nèi)存池項(xiàng)目實(shí)戰(zhàn)

6.1 項(xiàng)目介紹

我寫這個項(xiàng)目呢，主要是為了學(xué)習(xí)，參考的是tc_malloc，項(xiàng)目設(shè)計分為三層結(jié)構(gòu)：

圖片

• 第一層是Thread Cache，線程緩存是每個線程獨(dú)有的，在這里設(shè)計的是用于小于64k的內(nèi)存分配，線程在這里申請不需要加鎖，每一個線程都有自己獨(dú)立的cache，這也就是這個項(xiàng)目并發(fā)高效的地方。
• 第二層是Central Cache，在這里是所有線程共享的，它起著承上啟下的作用，Thread Cache是按需要從Central Cache中獲取對象，它就要起著平衡多個線程按需調(diào)度的作用，既可以將內(nèi)存對象分配給Thread Cache來的每個線程，又可以將線程歸還回來的內(nèi)存進(jìn)行管理。Central Cache是存在競爭的，所以在這里取內(nèi)存對象的時候是需要加鎖的，但是鎖的力度可以控制得很小。
• 第三層是Page Cache，存儲的是以頁為單位存儲及分配的，Central Cache沒有內(nèi)存對象(Span)時，從Page cache分配出一定數(shù)量的Page，并切割成定長大小的小塊內(nèi)存，分配給Central Cache。Page Cache會回收Central Cache滿足條件的Span(使用計數(shù)為0)對象，并且合并相鄰的頁，組成更大的頁，緩解內(nèi)存碎片的問題。

注：怎么實(shí)現(xiàn)每個線程都擁有自己唯一的線程緩存呢？

為了避免加鎖帶來的效率，在Thread Cache中使用（tls）thread local storage保存每個線程本地的Thread Cache的指針，這樣Thread Cache在申請釋放內(nèi)存是不需要鎖的。因?yàn)槊恳粋€線程都擁有了自己唯一的一個全局變量。

TLS分為靜態(tài)的和動態(tài)的：

• 靜態(tài)的TLS是：直接定義
• 動態(tài)的TLS是：調(diào)用系統(tǒng)的API去創(chuàng)建的，我們這個項(xiàng)目里面用到的就是靜態(tài)的TLS

6.2 設(shè)計Thread Cache

圖片

ThreadCache.h:

#pragma once

#include "Common.h"

class ThreadCache
{
private:
	Freelist _freelist[NLISTS];//自由鏈表

public:
	//申請和釋放內(nèi)存對象
	void* Allocate(size_t size);
	void Deallocate(void* ptr, size_t size);

	//從中心緩存獲取對象
	void* FetchFromCentralCache(size_t index, size_t size);

	//釋放對象時，鏈表過長時，回收內(nèi)存回到中心堆
	void ListTooLong(Freelist* list, size_t size);
};

//靜態(tài)的，不是所有可見
//每個線程有個自己的指針, 用(_declspec (thread))，我們在使用時，每次來都是自己的，就不用加鎖了
//每個線程都有自己的tlslist
_declspec (thread) static ThreadCache* tlslist = nullptr;

申請內(nèi)存:

• 當(dāng)內(nèi)存申請size<=64k時在Thread Cache中申請內(nèi)存，計算size在自由鏈表中的位置，如果自由鏈表中有內(nèi)存對象時，直接從FistList[i]中Pop一下對象，時間復(fù)雜度是O(1)，且沒有鎖競爭。
• 當(dāng)FreeList[i]中沒有對象時，則批量從Central Cache中獲取一定數(shù)量的對象，插入到自由鏈表并返回一個對象。

釋放內(nèi)存：

• 當(dāng)釋放內(nèi)存小于64k時將內(nèi)存釋放回Thread Cache，計算size在自由鏈表中的位置，將對象Push到FreeList[i].
• 當(dāng)鏈表的長度過長，也就是超過一次向中心緩存分配的內(nèi)存塊數(shù)目時則回收一部分內(nèi)存對象到Central Cache。

6.3 對齊大小的設(shè)計（對齊規(guī)則）

//專門用來計算大小位置的類
class SizeClass
{
public:
	//獲取Freelist的位置
	inline static size_t _Index(size_t size, size_t align)
	{
		size_t alignnum = 1 << align;  //庫里實(shí)現(xiàn)的方法
		return ((size + alignnum - 1) >> align) - 1;
	}

	inline static size_t _Roundup(size_t size, size_t align)
	{
		size_t alignnum = 1 << align;
		return (size + alignnum - 1)&~(alignnum - 1);
	}

public:
	// 控制在12%左右的內(nèi)碎片浪費(fèi)
	// [1,128]				8byte對齊 freelist[0,16)
	// [129,1024]			16byte對齊 freelist[16,72)
	// [1025,8*1024]		128byte對齊 freelist[72,128)
	// [8*1024+1,64*1024]	1024byte對齊 freelist[128,184)

	inline static size_t Index(size_t size)
	{
		assert(size <= MAX_BYTES);

		// 每個區(qū)間有多少個鏈
		static int group_array[4] = { 16, 56, 56, 56 };
		if (size <= 128)
		{
			return _Index(size, 3);
		}
		else if (size <= 1024)
		{
			return _Index(size - 128, 4) + group_array[0];
		}
		else if (size <= 8192)
		{
			return _Index(size - 1024, 7) + group_array[0] + group_array[1];
		}
		else//if (size <= 65536)
		{
			return _Index(size - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		}
	}

	// 對齊大小計算，向上取整
	static inline size_t Roundup(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		if (bytes <= 128){
			return _Roundup(bytes, 3);
		}
		else if (bytes <= 1024){
			return _Roundup(bytes, 4);
		}
		else if (bytes <= 8192){
			return _Roundup(bytes, 7);
		}
		else {//if (bytes <= 65536){
			return _Roundup(bytes, 10);
		}
	}

	//動態(tài)計算從中心緩存分配多少個內(nèi)存對象到ThreadCache中
	static size_t NumMoveSize(size_t size)
	{
		if (size == 0)
			return 0;

		int num = (int)(MAX_BYTES / size);
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	// 根據(jù)size計算中心緩存要從頁緩存獲取多大的span對象
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num*size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}
};

6.4 設(shè)計Thread Cache

• Central Cache本質(zhì)是由一個哈希映射的Span對象自由雙向鏈表構(gòu)成
• 為了保證全局只有唯一的Central Cache，這個類被可以設(shè)計成了單例模式
• 單例模式采用餓漢模式，避免高并發(fā)下資源的競爭

圖片

CentralCache.h:

#pragma once

#include "Common.h"

//上面的ThreadCache里面沒有的話，要從中心獲取

/*
進(jìn)行資源的均衡，對于ThreadCache的某個資源過剩的時候，可以回收ThreadCache內(nèi)部的的內(nèi)存
從而可以分配給其他的ThreadCache
只有一個中心緩存，對于所有的線程來獲取內(nèi)存的時候都應(yīng)該是一個中心緩存
所以對于中心緩存可以使用單例模式來進(jìn)行創(chuàng)建中心緩存的類
對于中心緩存來說要加鎖
*/

//設(shè)計成單例模式
class CentralCache
{
public:
	static CentralCache* Getinstence()
	{
		return &_inst;
	}

	//從page cache獲取一個span
	Span* GetOneSpan(SpanList& spanlist, size_t byte_size);

	//從中心緩存獲取一定數(shù)量的對象給threa cache
	size_t FetchRangeObj(void*& start, void*& end, size_t n, size_t byte_size);

	//將一定數(shù)量的對象釋放給span跨度
	void ReleaseListToSpans(void* start, size_t size);

private:
	SpanList _spanlist[NLISTS];

private:
	CentralCache(){}//聲明不實(shí)現(xiàn)，防止默認(rèn)構(gòu)造，自己創(chuàng)建

	CentralCache(CentralCache&) = delete;
	static CentralCache _inst;
};

申請內(nèi)存：

• 當(dāng)Thread Cache中沒有內(nèi)存時，就會批量向Central Cache申請一些內(nèi)存對象，Central Cache也有一個哈希映射的freelist，freelist中掛著span，從span中取出對象給Thread Cache，這個過程是需要加鎖的。
• Central Cache中沒有非空的span時，則將空的span鏈在一起，向Page Cache申請一個span對象，span對象中是一些以頁為單位的內(nèi)存，切成需要的內(nèi)存大小，并鏈接起來，掛到span中。
• Central Cache的span中有一個_usecount，分配一個對象給Thread Cache，就++_usecount。

釋放內(nèi)存：

• 當(dāng)Thread Cache過長或者線程銷毀，則會將內(nèi)存釋放回Central Cache中的，釋放回來時- -_usecount。
• 當(dāng)_usecount減到0時則表示所有對象都回到了span，則將Span釋放回Page Cache，Page Cache中會對前后相鄰的空閑頁進(jìn)行合并。

特別關(guān)心：什么是span?一個span是由多個頁組成的一個span對象。一頁大小是4k。

//Span是一個跨度，既可以分配內(nèi)存出去，也是負(fù)責(zé)將內(nèi)存回收回來到PageCache合并
//是一鏈?zhǔn)浇Y(jié)構(gòu)，定義為結(jié)構(gòu)體就行，避免需要很多的友元
struct Span
{
	PageID _pageid = 0;//頁號
	size_t _npage = 0;//頁數(shù)

	Span* _prev = nullptr;
	Span* _next = nullptr;

	void* _list = nullptr;//鏈接對象的自由鏈表，后面有對象就不為空，沒有對象就是空
	size_t _objsize = 0;//對象的大小

	size_t _usecount = 0;//對象使用計數(shù),
};

特別關(guān)心：關(guān)于spanlist，設(shè)計為一個雙向鏈表，插入刪除效率較高。

//和上面的Freelist一樣，各個接口自己實(shí)現(xiàn)，雙向帶頭循環(huán)的Span鏈表
class SpanList
{
public:
	Span* _head;
	std::mutex _mutex;

public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	~SpanList()//釋放鏈表的每個節(jié)點(diǎn)
	{
		Span * cur = _head->_next;
		while (cur != _head)
		{
			Span* next = cur->_next;
			delete cur;
			cur = next;
		}
		delete _head;
		_head = nullptr;
	}

	//防止拷貝構(gòu)造和賦值構(gòu)造，將其封死，沒有拷貝的必要，不然就自己會實(shí)現(xiàn)淺拷貝
	SpanList(const SpanList&) = delete;
	SpanList& operator=(const SpanList&) = delete;

	//左閉右開
	Span* Begin()//返回的一個數(shù)據(jù)的指針
	{
		return _head->_next;
	}

	Span* End()//最后一個的下一個指針
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	//在pos位置的前面插入一個newspan
	void Insert(Span* cur, Span* newspan)
	{
		Span* prev = cur->_prev;

		//prev newspan cur
		prev->_next = newspan;
		newspan->_next = cur;

		newspan->_prev = prev;
		cur->_prev = newspan;
	}

	//刪除pos位置的節(jié)點(diǎn)
	void Erase(Span* cur)//此處只是單純的把pos拿出來，并沒有釋放掉，后面還有用處
	{
		Span* prev = cur->_prev;
		Span* next = cur->_next;

		prev->_next = next;
		next->_prev = prev;
	}

	//尾插
	void PushBack(Span* newspan)
	{
		Insert(End(), newspan);
	}

	//頭插
	void PushFront(Span* newspan)
	{
		Insert(Begin(), newspan);
	}

	//尾刪
	Span* PopBack()//實(shí)際是將尾部位置的節(jié)點(diǎn)拿出來
	{
		Span* span = _head->_prev;
		Erase(span);

		return span;
	}

	//頭刪
	Span* PopFront()//實(shí)際是將頭部位置節(jié)點(diǎn)拿出來
	{
		Span* span = _head->_next;
		Erase(span);

		return span;
	}

	void Lock()
	{
		_mutex.lock();
	}

	void Unlock()
	{
		_mutex.unlock();
	}
};

特別關(guān)心：怎么才能將Thread Cache中的內(nèi)存對象還給它原來的span呢？

答：可以在Page Cache中維護(hù)一個頁號到span的映射，當(dāng)Span Cache給Central Cache分配一個span時，將這個映射更新到unordered_map中去，在Thread Cache還給Central Cache時，可以查這個unordered_map找到對應(yīng)的span。

6.5 設(shè)計Page Cache

• Page cache是一個以頁為單位的span自由鏈表。
• 為了保證全局只有唯一的Page cache，這個類可以被設(shè)計成了單例模式。
• 本單例模式采用餓漢模式。

圖片

PageCache.h

#pragma once

#include "Common.h"

//對于Page Cache也要設(shè)置為單例，對于Central Cache獲取span的時候
//每次都是從同一個page數(shù)組中獲取span
//單例模式
class PageCache
{
public:
	static PageCache* GetInstence()
	{
		return &_inst;
	}

	Span* AllocBigPageObj(size_t size);
	void FreeBigPageObj(void* ptr, Span* span);

	Span* _NewSpan(size_t n);
	Span* NewSpan(size_t n);//獲取的是以頁為單位

	//獲取從對象到span的映射
	Span* MapObjectToSpan(void* obj);

	//釋放空間span回到PageCache，并合并相鄰的span
	void ReleaseSpanToPageCache(Span* span);

private:
	SpanList _spanlist[NPAGES];
	//std::map<PageID, Span*> _idspanmap;
	std::unordered_map<PageID, Span*> _idspanmap;

	std::mutex _mutex;
private:
	PageCache(){}

	PageCache(const PageCache&) = delete;
	static PageCache _inst;
};

申請內(nèi)存：

• 當(dāng)Central Cache向page cache申請內(nèi)存時，Page Cache先檢查對應(yīng)位置有沒有span，如果沒有則向更大頁尋找一個span，如果找到則分裂成兩個。比如：申請的是4page，4page后面沒有掛span，則向后面尋找更大的span，假設(shè)在10page位置找到一個span，則將10page span分裂為一個4page span和一個6page span。
• 如果找到128 page都沒有合適的span，則向系統(tǒng)使用mmap、brk或者是VirtualAlloc等方式申請128page span掛在自由鏈表中，再重復(fù)1中的過程。

釋放內(nèi)存：如果Central Cache釋放回一個span，則依次尋找span的前后_pageid的span，看是否可以合并，如果合并繼續(xù)向前尋找。這樣就可以將切小的內(nèi)存合并收縮成大的span，減少內(nèi)存碎片。

6.6 項(xiàng)目不足

項(xiàng)目的獨(dú)立性不足：

• 不足：當(dāng)前實(shí)現(xiàn)的項(xiàng)目中我們并沒有完全脫離malloc，比如在內(nèi)存池自身數(shù)據(jù)結(jié)構(gòu)的管理中，如SpanList中的span等結(jié)構(gòu)，我們還是使用的new Span這樣的操作，new的底層使用的是malloc，所以還不足以替換malloc，因?yàn)閭儽旧頉]有完全脫離它。
• 解決方案：項(xiàng)目中增加一個定長的ObjectPool的對象池，對象池的內(nèi)存直接使用brk、VirarulAlloc等向系統(tǒng)申請，new Span替換成對象池申請內(nèi)存。這樣就完全脫離的malloc，就可以替換掉malloc。

平臺及兼容性：

• linux等系統(tǒng)下面，需要將VirtualAlloc替換為brk等。
• x64系統(tǒng)下面，當(dāng)前的實(shí)現(xiàn)支持不足。比如：id查找Span得到的映射，我們當(dāng)前使用的是map<id,
  Span*>。在64位系統(tǒng)下面，這個數(shù)據(jù)結(jié)構(gòu)在性能和內(nèi)存等方面都是撐不住。需要改進(jìn)后基數(shù)樹。
• 具體參考：Linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)：基數(shù)樹Radix Tree