《0bug-C/C++商用工程之道》节选01--内存栈-1
?
7.2? 內(nèi)存池的核心邏輯—內(nèi)存棧
在內(nèi)存池中,首先要有一個內(nèi)存塊管理的核心模塊,來負責所有內(nèi)存塊的申請、分發(fā)、回收和釋放工作,經(jīng)過設(shè)計,筆者是使用“棧”來完成的這個模塊,因此,筆者將其定名為“內(nèi)存棧”(Memory Stack)。下面我們將詳細討論其設(shè)計細節(jié)。
7.2.1? 內(nèi)存管理的數(shù)學模型
內(nèi)存塊如果要提升可重用性,必須對內(nèi)存塊尺寸進行取模,否則的話,很容易因為幾個Bytes的偏差,導致內(nèi)存塊無法重用,被迫向系統(tǒng)頻繁申請新的內(nèi)存空間,那意義就不大了。
取模的主要目的,是減少內(nèi)存塊的種類,以有限幾個尺寸的內(nèi)存塊,應對絕大多數(shù)內(nèi)存使用要求。
筆者看過STL的內(nèi)存管理模塊源代碼,對其內(nèi)存塊的取模機制深表欽佩,因此,在筆者自己的內(nèi)存池中,也是按照這種方式取模。
提示:32位系統(tǒng),有個字節(jié)對齊問題,即一個程序變量單元,如一個結(jié)構(gòu)體,一個內(nèi)存塊,如果其尺寸不是4Bytes的整倍數(shù),操作系統(tǒng)會按照比它大的整倍數(shù)分配內(nèi)存,這其實也是操作系統(tǒng)在取模。比如我們的一個結(jié)構(gòu)體為7Bytes,操作系統(tǒng)分配時會分配8Bytes,一個14Bytes的內(nèi)存塊,操作系統(tǒng)會分配16Bytes,這主要是簡化內(nèi)存地址運算,以一定的內(nèi)存消耗,來提升程序的運行速度。
我們對內(nèi)存的取模也是這個原理,當然,我們不可能像操作系統(tǒng)那樣,機械地以4Bytes為模數(shù),那樣,內(nèi)存塊種類還是太多,管理起來壓力很大,內(nèi)存池的效率也不高。
筆者仿造STL的取模方式,在內(nèi)存池中按照如下邏輯取模,簡單說來,就是從16Bytes開始,以兩倍方式遞增模數(shù)。直到4G內(nèi)存為止。當然,實際使用時,超過1M的內(nèi)存塊,一般應用很少,即使有,基本上也屬于應用程序永久緩沖區(qū),很少會中途頻繁釋放,因此,筆者的內(nèi)存池管理,一般模數(shù)為16Bytes~1M即可。
| 序號 | 內(nèi)存塊大小模數(shù)(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 |
| 16 | 512k | 256k+1~512k |
| 17 | 1M | 512k+1~1M |
| 圖7.1:內(nèi)存模數(shù)表 |
?
如表7.1所示,內(nèi)存池實際上是一個樹型數(shù)據(jù)結(jié)構(gòu)在管理,每一種類型的內(nèi)存塊,構(gòu)成一個鏈表,形成樹的“右枝”,而所有右枝的鏈頭,又是以一個鏈表在管理,形成樹的“左枝”。請注意,這并不是二叉樹,還是一顆普通的樹結(jié)構(gòu)。如下圖所示:
| ? 圖7.2:內(nèi)存管理樹模型 |
?
?
| 我們舉個例子,當應用程序申請一塊57Bytes的內(nèi)存塊,程序邏輯會沿著樹的左枝,從頭到尾比對,首先是16Bytes的的管理鏈,由于57>16,因此,無法在這根右枝進行管理,因此繼續(xù)往下,32Bytes也不行,64Bytes,比57要大,可以使用,因此,就在64Bytes這根右枝實現(xiàn)內(nèi)存塊管理。 |
管理原則:分配時,首先在合適的右枝尋找可用的內(nèi)存塊,如果有,則直接分配給應用程序重用該塊,如果沒有,則向系統(tǒng)申請一塊64Bytes的內(nèi)存塊,分配給應用程序使用。而當應用程序釋放時,內(nèi)存塊本身是64Bytes的,因此,可以直接掛回到64Bytes這根右枝,等待下次重用。
提示:這里面有一個隱含的推論,如果一個應用程序,需要一塊57Bytes的內(nèi)存塊,那么,我們分配一塊比它大的內(nèi)存塊,比如64Bytes的內(nèi)存塊,是完全可以的,應用程序不關(guān)心自己實際獲得的內(nèi)存塊大小,同時,這種稍稍超大的分配機制,也不回引發(fā)任何的內(nèi)存溢出bug,反而更安全,因此,這種內(nèi)存取模分配的思路,是完全可行的。
7.2.2? 管理模型的優(yōu)化
雖然上文我們討論的是以鏈表方式管理,不過,在實做中,筆者發(fā)現(xiàn)一個問題,即鏈表效率不高,原因很簡單,筆者的鏈表是以隊列方式管理,每次從右枝取出內(nèi)存塊,是從鏈表頭取出,但釋放時,將內(nèi)存塊推回右枝,需要循環(huán)遍歷到鏈表尾部進行掛鏈操作。這在高速的內(nèi)存申請和釋放時,會嚴重影響鏈表的效率。
筆者經(jīng)過思考,發(fā)現(xiàn)一個問題,當一個內(nèi)存塊被推回一個右枝,其實已經(jīng)是無屬性的,比如,64Bytes這個右枝上,掛的都是64Bytes大小的內(nèi)存塊,應用程序申請時,使用任何一塊都是可以的,無需考慮這塊是在鏈頭還是鏈尾,同時,申請的內(nèi)存塊,都是需要初始化的,應用程序也不關(guān)心這塊內(nèi)存塊是否剛剛被使用完,還是已經(jīng)空閑很久了。筆者理解這個內(nèi)存樹的右枝,其實已經(jīng)是前文所說的“被動池”邏輯了。
我們知道,在“推”入和“提取”這個邏輯上,“棧”的效率遠高于“隊列”,通常我們不使用棧的唯一原因,主要是棧是“后進先出”邏輯,而隊列是“先進先出”邏輯,而我們常見的應用模型,一般都有數(shù)據(jù)順序要求,因此,隊列的使用場合,遠多于棧結(jié)構(gòu)。
但此處既然我們已經(jīng)明確論證了,內(nèi)存塊無順序需求,那么,我們完全可以使用棧模型來管理內(nèi)存樹的右枝,以提高效率。
這在實做時非常簡單,當應用程序釋放一塊內(nèi)存,我們需要推回右枝時,直接將其掛接到鏈頭即可,取消了無意義的循環(huán)遍歷鏈尾的操作,雖然,下次申請時,最后釋放的一塊內(nèi)存會被最先分配使用,但這又有什么關(guān)系呢?
這個優(yōu)化看似很小,但實做時威力驚人,經(jīng)筆者測試,內(nèi)存塊的申請和釋放吞吐量,在“隊列”管理方式下,每秒僅5萬次左右,一旦使用“棧”方式管理,迅速提升到40~50萬次,提升了整整一個數(shù)量級。
正因為如此,筆者才將內(nèi)存池最核心的內(nèi)存管理模塊,定名為內(nèi)存棧(Memory Stack)。
提示:在進行程序開發(fā)時,很多時候,需要針對業(yè)務(wù)需求進行分析,實現(xiàn)針對性優(yōu)化,很多時候,很小的一點優(yōu)化,都可以大幅度提升程序的性能。反過來說,通用的優(yōu)化其實不存在,只有深刻理解了業(yè)務(wù)需求之后,才有可能實施有效的優(yōu)化方案。
提示:原則上,程序開發(fā)應該遵循“先實現(xiàn),后優(yōu)化”的原則,筆者常說的“先解決有無問題,再解決好壞問題”,也是這個意思,本章在此先討論優(yōu)化,是因為筆者這個內(nèi)存池在實踐中已經(jīng)經(jīng)過了多次優(yōu)化,有條件討論此事,并不意味著可以再程序?qū)崿F(xiàn)前實施優(yōu)化,請各位讀者關(guān)注這個細節(jié)。事實上,本書展示的內(nèi)存池,已經(jīng)是筆者第19個版本,中間經(jīng)過了十幾次優(yōu)化的結(jié)果。
7.2.3? 關(guān)于鏈表管理的思考
討論完上面的問題,我們再來討論一下基本數(shù)據(jù)結(jié)構(gòu)管理的問題。我們知道,雖然我們的內(nèi)存池是樹結(jié)構(gòu)管理,但具體到每個右枝上,還是鏈表,而鏈表元素是動態(tài)申請的,依賴內(nèi)部指向下一元素的指針,實現(xiàn)鏈接關(guān)系。
具體到我們內(nèi)存塊管理上,我們發(fā)現(xiàn)一個基本的鏈表元素,至少需要定義成如下形式:
| typedef struct _CHAIN_TOKEN_ { ??? struct _CHAIN_TOKEN_* m_pNext;? //指向下一鏈表元素的指針 ??? char* m_pBuffer;??????????????? //指向真實內(nèi)存塊的指針 }SChainToken; |
這就帶來一個問題,鏈表的元素,應該分為兩部分,一部分是實現(xiàn)鏈表管理的邏輯數(shù)據(jù),如:m_pNext,另一部分,是業(yè)務(wù)相關(guān)的數(shù)據(jù),如m_pBuffer,這樣的數(shù)據(jù)結(jié)構(gòu),造成程序開發(fā)非常麻煩。
比如一個簡單的內(nèi)存申請和釋放動作,以上述數(shù)據(jù)結(jié)構(gòu)管理,其基本邏輯如下:
| 內(nèi)存申請: 1、檢查鏈表有無空閑內(nèi)存單元 2、如果有,提取其中的m_pBuffer,準備返回給應用程序使用 3、從鏈表中卸載已經(jīng)為空的鏈表管理元素,直接釋放給系統(tǒng)(注意,無管控的內(nèi)存塊釋放,內(nèi)存碎片的隱患) 內(nèi)存釋放: 1、尋找合適的鏈,準備做掛鏈操作 2、申請一個鏈表管理單元,將內(nèi)存塊的指針放入其中的m_pBuffer 3、執(zhí)行掛鏈操作,填充m_pBext指針 |
大家注意到?jīng)]有,我們本意是內(nèi)存管理,減小內(nèi)存碎片,但是,為了實現(xiàn)鏈表的管理,反而中間引入了一個多余的鏈表單元申請和釋放邏輯,反而增加了內(nèi)存碎片的產(chǎn)生可能,這種方法當然不可取。
另外,這里還有一個隱患,我們分配給應用程序的內(nèi)存塊,其中所有的內(nèi)存單元,都是對應用程序透明的,應用程序可以任意使用,這說明,這塊內(nèi)存塊中,沒有存儲任何關(guān)于內(nèi)存塊尺寸的信息,當應用程序釋放指針時,我們面臨一個問題,就是怎么確定這根指針指向的內(nèi)存塊,究竟有多大,應該掛在哪個右枝上,等待下次使用。
這個問題不解決,上述的內(nèi)存釋放邏輯的第一步,尋找合適的鏈,根本無法完成。
因此,為了記錄內(nèi)存塊的尺寸信息,我們必須內(nèi)部再建立一個映射表,將我們管理的每根內(nèi)存塊指針,在申請時的具體尺寸,都記錄下來,等釋放時,需要根據(jù)指針,逆查其對應的長度數(shù)據(jù),才能完成功能。
筆者做開發(fā)有個原則:“簡單的程序才是好程序”,上述邏輯雖然最終也能完成功能,但無論怎么看,都太復雜了,不是好的解決方案。
為此,筆者經(jīng)過了較長時間的思考,發(fā)現(xiàn)所有問題的核心焦點,無非只有兩條:
| 1、如何使鏈表的管理數(shù)據(jù),不要發(fā)生新的動態(tài)內(nèi)存分配。 2、如何使分配出去的指針,能夠攜帶相關(guān)的緩沖區(qū)尺寸信息,避免額外的存儲和查詢壓力。 |
經(jīng)過分析,筆者突發(fā)奇想,既然我們內(nèi)存池管理的就是內(nèi)存塊,就有存儲能力,為什么我們不能利用內(nèi)存塊做一點自己的管理數(shù)據(jù)存儲呢?大不了這個內(nèi)存塊實際可用內(nèi)存,比我們從操作系統(tǒng)申請的,要小一點,但這又有什么關(guān)系呢?應用程序需要的只是自己需要的內(nèi)存塊,這個內(nèi)存塊原來有多大?能給應用程序使用的又有多大?應用程序并不關(guān)心。
經(jīng)過考慮,筆者做了如下一個結(jié)構(gòu)體:
| typedef struct _TONY_MEM_BLOCK_HEAD_ { ??? ULONG m_ulBlockSize;??????????????????????? //內(nèi)存塊的尺寸 ??? struct _TONY_MEM_BLOCK_HEAD_* m_pNext;????? //指向下一鏈表元素的指針 }STonyMemoryBlockHead; //本結(jié)構(gòu)體的長度,經(jīng)過計算,恒定為8Bytes const ULONG STonyMemoryBlockHeadSize=sizeof(STonyMemoryBlockHead); |
上述結(jié)構(gòu)體,包含了內(nèi)存塊尺寸信息,來滿足釋放時查找的需求,同時,包含了指向下一元素的指針,這個指針,在分配給應用程序使用時,是無效的,只有當這個內(nèi)存塊掛接在鏈表中時,才有意義。
筆者這么思考,當我們向系統(tǒng)申請一個內(nèi)存塊,比如說64Bytes,我們內(nèi)存池占用其中最開始的8Bytes來存儲上述信息,也就是說,實際能給應用程序使用的,只有56Bytes。如圖7.3:
| 圖7.3:內(nèi)存塊組織結(jié)構(gòu) |
?
我們假定這個內(nèi)存塊的真實尺寸為N Bytes,我們從系統(tǒng)申請的首指針為p0,那么,我們占用8Bytes作為管理使用,當應用程序申請時,我們真實分配給應用程序的指針為p1=(p0+8)。這樣,當應用程序釋放時,我們只需要執(zhí)行p0=(p1-8),即可求出原始首地址,并以此獲得所有的管理信息。當最后向系統(tǒng)釋放內(nèi)存時,我們只要記得釋放p0即可。
提示:此處可能出于業(yè)務(wù)考慮,有點違背C和C++無錯化程序設(shè)計方法中,關(guān)于指針不得參與四則運算的原則,不過,沒辦法,需求如此,只有這條路走了。因此,違背就違背一點了。
唯一需要我們注意的細節(jié),是我們在分析應用程序的內(nèi)存申請需求時,不能以申請的內(nèi)存塊的真實尺寸進行比對,而應該比對減去8Bytes之后的數(shù)據(jù)。即64Bytes這個右枝上提供的內(nèi)存,只有56Bytes大小,如果超過這個值,請找下一鏈,即到128 Bytes這個右枝處理,當然,此時的128 Byte的右枝,也僅能提供120 Bytes的內(nèi)存塊,以此類推。
有鑒于此,筆者做了如下的宏定義,來界定所有的計算行為:
| //根據(jù)一個應用程序數(shù)據(jù)塊的長度,計算一個內(nèi)存塊的真實大小,即n+8 #define TONY_MEM_BLOCK_SIZE(nDataLength) \ ??? ?(nDataLength+STonyMemoryBlockHeadSize) //根據(jù)向系統(tǒng)申請的內(nèi)存塊,計算其應用程序數(shù)據(jù)內(nèi)存的真實大小,即n-8 #define TONY_MEM_BLOCK_DATA_SIZE(nBlockSize) \ ??? ?(nBlockSize-STonyMemoryBlockHeadSize) //根據(jù)應用程序釋放的指針,逆求真實的內(nèi)存塊指針,即p0=p1-8 #define TONY_MEM_BLOCK_HEAD(pData) \ ??? ?((STonyMemoryBlockHead*)(((char*)pData)-STonyMemoryBlockHeadSize)) //根據(jù)一個內(nèi)存塊的真實指針,求數(shù)據(jù)內(nèi)存塊的指針,即p1=p0+8 #define TONY_MEM_BLOCK_DATA(pHead) \ ??? ?(((char*)pHead)+STonyMemoryBlockHeadSize) //最小內(nèi)存塊長度,16 Bytes,由于我們管理占用8 Bytes,這個最小長度不能再小了, //否則無意義,即使這樣,我們最小的內(nèi)存塊,能分配給應用程序使用的,僅有8 Bytes。 #define TONY_XIAO_MEMORY_STACK_BLOCK_MIN 16 //這是管理的最大內(nèi)存塊長度,1M,如前文表中所示,超過此限制,內(nèi)存池停止服務(wù) //改為直接向系統(tǒng)申請和釋放。 #define TONY_XIAO_MEMORY_STACK_MAX_SAVE_BLOCK_SIZE (1*1024*1024) |
?
?
總結(jié)
以上是生活随笔為你收集整理的《0bug-C/C++商用工程之道》节选01--内存栈-1的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 程序语言中基本数值类型的分类
- 下一篇: 备份的误区