邊界對齊

開始之前先簡單講講邊界對齊。之前的專欄介紹了C語言中malloc()分配的內(nèi)存對齊問題,一般情況下為半字對齊,即在64位機中調(diào)用malloc()分配內(nèi)存時如果沒有達(dá)到半字字長(32位),那么就會自動填充到32位,這樣一來就造成了很大的開銷。不過這樣設(shè)計可以減少訪問內(nèi)存的次數(shù),一次訪存就能取出數(shù)據(jù),如下圖:

從王道計組第47頁的內(nèi)容來看,存儲器提供了按字節(jié),半字和字尋址的多種尋址方式,假設(shè)存儲字長為32位的話，按字節(jié)尋址一次只能讀出8位,按半字尋址一次能讀出16位,按字尋址一次能讀出32位。如果按字節(jié)尋址,讀出一個字需要讀4次,這不得累死。那么肯定是一次存取能讀得越多越好啊,假設(shè)按字尋址,一次可以讀出32位數(shù)據(jù),但如果數(shù)據(jù)是short類型(16位),就會產(chǎn)生16位的開銷,浪費了16位空間。再比如數(shù)據(jù)是char類型(8位),就浪費了24位空間。

假設(shè)存儲字長是64位,且按照字邊界對齊方式存儲,那么char類型的開銷就達(dá)到了56位?？梢娺吔鐚R并不是越大越好的,空間開銷會成倍增長。這是一種空間換時間的思想,空間代價太大換來的時間就不劃算了,那么就取一個平均值,半字對齊。

這樣一來,取1字節(jié)的小數(shù)據(jù)開銷不會太大,取8字節(jié)的大數(shù)據(jù),大數(shù)據(jù)又不常用,用兩個周期取存取也沒多大影響。

如果不按照邊界對齊存儲會怎么樣呢？

像圖2.11?因為沒有對齊,所以導(dǎo)致字1被分成了兩行,這時你要想取字1(字1-1和字1-2)時就需要訪存兩次。

由于存儲器存儲字長為32位,訪存采用字尋址方式,所以每次只能4個字節(jié)4個字節(jié)的去讀取,要讀字1時只能先讀高32位,再讀低32位,然后再把這兩組數(shù)據(jù)拼接起來,十分的陰間啊。

值得一提的是,王道在此節(jié)最后還介紹了精簡指令集架構(gòu)的處理器例如ARM采用邊界對齊方式,而復(fù)雜指令集架構(gòu)的處理器如x86對齊和不對齊都支持。而在對齊方式下取指令的時間相同,可以適應(yīng)指令流水。

C語言中的內(nèi)存對齊

在C語言malloc()的對齊中,不再按照半字,字節(jié)等單位進行邊界對齊了,轉(zhuǎn)而使用指針長度為單位(64位機下指針長度為8字節(jié))。原理簡單說明下,調(diào)用malloc()會分配空間并返回一個指針,而在C語言中訪存指針,也就是先做64位地址尋址后,再把內(nèi)存空間中的值拿出來。

看過我上篇博客的都知道,win10 64位的內(nèi)存對齊系數(shù)是16字節(jié),最小分配空間是32字節(jié),那么以分配34字節(jié)為例子,malloc(34),理論上大小應(yīng)該是頭部+數(shù)據(jù)=8+34=42字節(jié),超過了32字節(jié),系統(tǒng)會進行內(nèi)存對齊,對齊到48字節(jié)。但如果不對齊呢,就按照42字節(jié)去訪問會怎么樣?假設(shè)按字尋址,每次讀8字節(jié),最好的情況下需要訪問6次內(nèi)存,最壞的情況下需要訪問7次內(nèi)存。但是對齊之后48字節(jié),只需要訪問6次,這樣一來雖然增加了開銷,但是減少了訪存次數(shù)。

改進

既然C語言malloc()會額外產(chǎn)生這么大的內(nèi)存開銷(包括頭部開銷和對齊開銷)有沒有一種辦法能既不影響內(nèi)存對齊又不產(chǎn)生過多的開銷呢？答案是肯定的,通過內(nèi)存池。

首先先用malloc()分配一塊504字節(jié)的空間作為內(nèi)存池的初始大小,后續(xù)內(nèi)存池的擴容也以504字節(jié)為單位。malloc(504)不會產(chǎn)生任何開銷,加上頭部8字節(jié)剛好是512,是16的整數(shù)倍。

再額外分配64字節(jié)(512bit 1bit可表示0和1)的空間來記錄內(nèi)存池存儲單元的占用情況,為1表示被使用,為0表示可用。

這樣算下來,總共分配了512+64=576字節(jié),只多了13%的開銷。

而直接使用malloc()進行分配,由于存在最小分配空間的限制,最小也要分配32字節(jié),會產(chǎn)生極大的開銷。再加上每次分配都會產(chǎn)生的的16字節(jié)內(nèi)存對齊開銷,stm32看了簡直要落淚啊。

內(nèi)存池初始化完畢后,怎么進行分配和管理呢？

先看內(nèi)存池存儲單元的結(jié)構(gòu)設(shè)計:

存儲單元分為兩部分:

1. DATA 數(shù)據(jù)區(qū): 長度最小為1字節(jié)

2. NEXT下地址: 占用1字節(jié)(0-256),表示與此存儲單元相連接的下一塊內(nèi)存單元地址。可用于連接256對碎片空間(共512個空間)

結(jié)構(gòu)非常簡單,創(chuàng)建數(shù)據(jù)僅額外占用1字節(jié)開銷用于連接碎片空間,最小長度為2字節(jié)。

例如需要創(chuàng)建48字節(jié)空間,那么就需要內(nèi)存池中有49字節(jié)的連續(xù)空間。

若有足夠連續(xù)空間,則直接分配并返回頭指針(額外開銷1字節(jié))

若有足夠非連續(xù)的空間,則按碎片塊的大小依次分配并連接,每次連接碎片塊將產(chǎn)生1字節(jié)下地址開銷。

最壞情況下(內(nèi)存池中全是2字節(jié)大小的碎片空間),那就需要連接48對內(nèi)存碎片(共96個碎片空間),額外開銷達(dá)到2N=96字節(jié)。在這種情況下,使用內(nèi)存池碎片分配產(chǎn)生的開銷遠(yuǎn)遠(yuǎn)大于直接malloc(48)分配的開銷(64字節(jié)),那么就不從內(nèi)存池碎片分配,而對內(nèi)存池進行擴容,分配一塊新的512字節(jié)連續(xù)內(nèi)存空間,再在這塊空間中分配內(nèi)存給用戶。

非最壞情況下(開銷小于直接malloc()的開銷),那么就按碎片塊的大小依次分配并連接,每次連接碎片塊將產(chǎn)生1字節(jié)下地址。

若無足夠空間,則對內(nèi)存池進行擴容,分配一塊新的512字節(jié)連續(xù)內(nèi)存空間后再從這塊空間中分配內(nèi)存給用戶。

經(jīng)過這樣的設(shè)計,不會過多開銷,唯一的問題就是碎片內(nèi)存的使用。要知道像傳統(tǒng)的malloc()法分配內(nèi)存空間都是返回一個指向連續(xù)內(nèi)存空間的指針,而碎片空間雖然在邏輯上連續(xù),但是實際上采用指針是訪問不了下地址的。例如:

若用指針操作:

char* A= memPoolAlloc();? //從內(nèi)存池分配空間

for(int i=0;i<5;i++) printf("%c?",*A);

這樣是無法把完整的字符數(shù)組A打印出來的

所以我轉(zhuǎn)變思路,直接采用對象來代替指針,用對象封裝底層的邏輯內(nèi)存和實際內(nèi)存的轉(zhuǎn)換,熟知的讀取,僅將數(shù)據(jù)讀取接口提供給用戶,通過調(diào)用此接口即可代替用戶使用指針來完成數(shù)據(jù)的讀取,下面我將演示一個大體的構(gòu)想:

//Bytes是一個結(jié)構(gòu)體(基本類型),注意不是結(jié)構(gòu)體指針!

Bytes bytes=new(Bytes,27);? ? //從內(nèi)存池中分配27個字節(jié)空間,類型為字節(jié)集合

char data1=bytes.getByte(5);? ?//獲取字節(jié)集合索引值為5的字節(jié)類型數(shù)據(jù)

char* data2=bytes.getString(24); //獲取字節(jié)集合索引值為24的字符串?dāng)?shù)據(jù)

int data3=bytes.getInteger(10);//獲取字節(jié)集合索引值為10的整型數(shù)據(jù)

這樣一來,部署了此內(nèi)存池之后,由于內(nèi)存碎片整理的問題,用戶不能用指針去正確訪問內(nèi)存池的數(shù)據(jù),但是通過引入面向?qū)ο蟮臋C制,來規(guī)避對底層指針的依賴。

此專欄僅僅是對近期學(xué)習(xí)的總結(jié)和對曾經(jīng)內(nèi)存池設(shè)計的設(shè)想方案,有生之年我將會將此方案實現(xiàn)并分享。