為了速度和正確性,請(qǐng)對(duì)齊你的數(shù)據(jù).

    概述:對(duì)于所有直接操作內(nèi)存的程序員來(lái)說(shuō),數(shù)據(jù)對(duì)齊都是很重要的問(wèn)題.數(shù)據(jù)對(duì)齊對(duì)你的程序的表現(xiàn)甚至能否正常運(yùn)行都會(huì)產(chǎn)生影響.就像本文章闡述的一樣,理解了對(duì)齊的本質(zhì)還能夠解釋一些處理器的"奇怪的"行為.

 

內(nèi)存存取粒度

   程序員通常傾向于認(rèn)為內(nèi)存就像一個(gè)字節(jié)數(shù)組.在C及其衍生語(yǔ)言中,char * 用來(lái)指代"一塊內(nèi)存",甚至在JAVA中也有byte[]類(lèi)型來(lái)指代物理內(nèi)存.

 

Figure 1. 程序員是如何看內(nèi)存的

 

   然而,你的處理器并不是按字節(jié)塊來(lái)存取內(nèi)存的.它一般會(huì)以雙字節(jié),四字節(jié),8字節(jié),16字節(jié)甚至32字節(jié)為單位來(lái)存取內(nèi)存.我們將上述這些存取單位稱(chēng)為內(nèi)存存取粒度.

 

Figure 2. 處理器是如何看內(nèi)存的

 

   高層(語(yǔ)言)程序員認(rèn)為的內(nèi)存形態(tài)和處理器對(duì)內(nèi)存的實(shí)際處理方式之間的差異產(chǎn)生了許多有趣的問(wèn)題,本文旨在闡述這些問(wèn)題.

   如果你不理解內(nèi)存對(duì)齊,你編寫(xiě)的程序?qū)⒂锌赡墚a(chǎn)生下面的問(wèn)題,按嚴(yán)重程度遞增:

程序運(yùn)行速度變慢

應(yīng)用程序產(chǎn)生死鎖

操作系統(tǒng)崩潰

你的程序會(huì)毫無(wú)征兆的出錯(cuò),產(chǎn)生錯(cuò)誤的結(jié)果(silently fail如何翻譯?)

 

內(nèi)存對(duì)齊基礎(chǔ)

   為了說(shuō)明內(nèi)存對(duì)齊背后的原理,我們考察一個(gè)任務(wù),并觀察內(nèi)存存取粒度是如何對(duì)該任務(wù)產(chǎn)生影響的.這個(gè)任務(wù)很簡(jiǎn)單:先從地址0讀取4個(gè)字節(jié)到寄存器,然后從地址1讀取4個(gè)字節(jié)到寄存器.

   首先考察內(nèi)存存取粒度為1byte的情況:

 

Figure 3. 單字節(jié)存取

 

   這迎合了那些天真的程序員的觀點(diǎn):從地址0和地址1讀取4字節(jié)數(shù)據(jù)都需要相同的4次操作.現(xiàn)在再看看存取粒度為雙字節(jié)的處理器(像最初的68000處理器)的情況:

 

Figure 4. 雙字節(jié)存取

 

   從地址0讀取數(shù)據(jù),雙字節(jié)存取粒度的處理器讀內(nèi)存的次數(shù)是單字節(jié)存取粒度處理器的一半.因?yàn)槊看蝺?nèi)存存取都會(huì)產(chǎn)生一個(gè)固定的開(kāi)銷(xiāo),最小化內(nèi)存存取次數(shù)將提升程序的性能.

   但從地址1讀取數(shù)據(jù)時(shí)由于地址1沒(méi)有和處理器的內(nèi)存存取邊界對(duì)齊,處理器就會(huì)做一些額外的工作.地址1這樣的地址被稱(chēng)作非對(duì)齊地址.由于地址1是非對(duì)齊的,雙字節(jié)存取粒度的處理器必須再讀一次內(nèi)存才能獲取想要的4個(gè)字節(jié),這減緩了操作的速度.

   最后我們?cè)倏匆幌麓嫒×６葹?/SPAN>4字節(jié)的處理器(像68030,PowerPC® 601)的情況:

Figure 5. 四字節(jié)存取

 

   在對(duì)齊的內(nèi)存地址上,四字節(jié)存取粒度處理器可以一次性的將4個(gè)字節(jié)全部讀出;而在非對(duì)齊的內(nèi)存地址上,讀取次數(shù)將加倍.

   既然你理解了內(nèi)存對(duì)齊背后的原理,那么你就可以探索該領(lǐng)域相關(guān)的一些問(wèn)題了.

懶惰的處理器

   處理器對(duì)非對(duì)齊內(nèi)存的存取有一些技巧.考慮上面的四字節(jié)存取粒度處理器從地址1讀取4字節(jié)的情況,你肯定想到了下面的解決方法:

Figure 6. 處理器如何處理非對(duì)齊內(nèi)存地址

 

   處理器先從非對(duì)齊地址讀取第一個(gè)4字節(jié)塊,剔除不想要的字節(jié),然后讀取下一個(gè)4字節(jié)塊,同樣剔除不要的數(shù)據(jù),最后留下的兩塊數(shù)據(jù)合并放入寄存器.這需要做很多工作.

   有些處理器并不情愿為你做這些工作.

   最初的68000處理器的存取粒度是雙字節(jié),沒(méi)有應(yīng)對(duì)非對(duì)齊內(nèi)存地址的電路系統(tǒng).當(dāng)遇到非對(duì)齊內(nèi)存地址的存取時(shí),它將拋出一個(gè)異常.最初的Mac OS并沒(méi)有妥善處理這個(gè)異常,它會(huì)直接要求用戶(hù)重啟機(jī)器.悲劇.

   隨后的680x0系列,像68020,放寬了這個(gè)的限制,支持了非對(duì)齊內(nèi)存地址存取的相關(guān)操作.這解釋了為什么一些在68020上正常運(yùn)行的舊軟件會(huì)在68000上崩潰.這也解釋了為什么當(dāng)時(shí)一些老Mac編程人員會(huì)將指針初始化成奇數(shù)地址.在最初的Mac機(jī)器上如果指針在使用前沒(méi)有被重新賦值成有效地址,Mac會(huì)立即跳到調(diào)試器.通常他們通過(guò)檢查調(diào)用堆棧會(huì)找到問(wèn)題所在.

   所有的處理器都使用有限的晶體管來(lái)完成工作.支持非對(duì)齊內(nèi)存地址的存取操作會(huì)消減"晶體管預(yù)算",這些晶體管原本可以用來(lái)提升其他模塊的速度或者增加新的功能.

   以速度的名義犧牲非對(duì)齊內(nèi)存存取功能的一個(gè)例子就是MIPS.為了提升速度,MIPS幾乎廢除了所有的瑣碎功能.

    PowerPC各取所長(zhǎng).目前所有的PowPC都硬件支持非對(duì)齊的32位整型的存取.雖然犧牲掉了一部分性能,但這些損失在逐漸減少.

   另一方面,現(xiàn)今的PowPC處理器缺少對(duì)非對(duì)齊的64-bit浮點(diǎn)型數(shù)據(jù)的存取的硬件支持.當(dāng)被要求從非對(duì)齊內(nèi)存讀取浮點(diǎn)數(shù)時(shí),PowerPC會(huì)拋出異常并讓操作系統(tǒng)來(lái)處理內(nèi)存對(duì)齊這樣的雜事.軟件解決內(nèi)存對(duì)齊要比硬件慢得多.

psting 1. 每次處理一個(gè)字節(jié)

   運(yùn)行這個(gè)函數(shù)需要67364微秒,現(xiàn)在修改成每次處理2個(gè)字節(jié),這將使存取次數(shù)減半:

psting 2.每次處理2個(gè)字節(jié)

   如果處理的內(nèi)存地址是對(duì)齊的話,上述函數(shù)處理同一個(gè)緩沖區(qū)需要48765微秒--比Munge8快38%.如果緩沖區(qū)不是對(duì)齊的,處理時(shí)間會(huì)增加到66385微秒--比對(duì)齊情況下慢了27%.下圖展示了對(duì)齊內(nèi)存和非對(duì)齊內(nèi)存之間的性能對(duì)比.

速度

   下面編寫(xiě)一些測(cè)試來(lái)說(shuō)明非對(duì)齊內(nèi)存對(duì)性能造成的損失.過(guò)程很簡(jiǎn)單:從一個(gè)10MB的緩沖區(qū)中讀取,取反,并寫(xiě)回?cái)?shù)據(jù).這些測(cè)試有兩個(gè)變量:

處理緩沖區(qū)的處理粒度,單位bytes. 一開(kāi)始每次處理1個(gè)字節(jié),然后2個(gè)字節(jié),4個(gè)字節(jié)和8個(gè)字節(jié).

緩沖區(qū)的對(duì)準(zhǔn). 用每次增加緩沖區(qū)的指針來(lái)交錯(cuò)調(diào)整內(nèi)存地址,然后重新做每個(gè)測(cè)試.

   這些測(cè)試運(yùn)行在800MHz的PowerBook G4上.為了最小化中斷引起的波動(dòng),這里取十次結(jié)果的平均值.第一個(gè)是處理粒度為單字節(jié)的情況:

psting 1. 每次處理一個(gè)字節(jié)

   運(yùn)行這個(gè)函數(shù)需要67364微秒,現(xiàn)在修改成每次處理2個(gè)字節(jié),這將使存取次數(shù)減半:

psting 2.每次處理2個(gè)字節(jié)

   如果處理的內(nèi)存地址是對(duì)齊的話,上述函數(shù)處理同一個(gè)緩沖區(qū)需要48765微秒--比Munge8快38%.如果緩沖區(qū)不是對(duì)齊的,處理時(shí)間會(huì)增加到66385微秒--比對(duì)齊情況下慢了27%.下圖展示了對(duì)齊內(nèi)存和非對(duì)齊內(nèi)存之間的性能對(duì)比.

Figure7. 單字節(jié)存取 vs.雙字節(jié)存取

 

   第一個(gè)讓人注意到的現(xiàn)象是單字節(jié)存取結(jié)果很均勻,且都很慢.第二個(gè)是雙字節(jié)存取時(shí),每當(dāng)?shù)刂肥菃螖?shù)時(shí),變慢的27%就會(huì)出現(xiàn).

   下面加大賭注,每次處理4個(gè)字節(jié):

psting 3. 每次處理4個(gè)字節(jié)

   對(duì)于對(duì)齊的緩沖區(qū),函數(shù)需要43043微秒;對(duì)于非對(duì)齊的緩沖區(qū),函數(shù)需要55775微秒.因此,在所測(cè)試的機(jī)器上,非對(duì)齊地址的四字節(jié)存取速度比對(duì)齊地址的雙字節(jié)存取速度要慢.

 

Figure8. 單字節(jié)vs.雙字節(jié)vs.四字節(jié)存取

 

現(xiàn)在來(lái)最恐怖的:每次處理8個(gè)字節(jié):

psting 4.每次處理8個(gè)字節(jié)

    Munge64處理對(duì)齊的緩沖區(qū)需要39085微秒--大約比對(duì)齊的Munge32快10%.但是,在非對(duì)齊緩沖區(qū)上的處理時(shí)間是讓人驚訝的1841155微秒--比對(duì)齊的慢了兩個(gè)數(shù)量級(jí),慢了足足4610%.

   怎么回事?因?yàn)槲覀儸F(xiàn)今所使用的PowerPC缺少對(duì)存取非對(duì)齊內(nèi)存的浮點(diǎn)數(shù)的硬件支持.對(duì)每次非對(duì)齊內(nèi)存的存取,處理器都拋出一個(gè)異常.操作系統(tǒng)獲取該異常并軟件實(shí)現(xiàn)內(nèi)存對(duì)齊.下圖顯示了非對(duì)齊內(nèi)存存取帶來(lái)的不利后果.

 

Figure 9. 多字節(jié)存取對(duì)比

 

   單字節(jié),雙字節(jié)和四字節(jié)的細(xì)節(jié)都被掩蓋了.或許去除頂部以后的圖形,如下圖,更清晰:

 

Figure 10. 多字節(jié)存取對(duì)比 #2

 

   在這些數(shù)據(jù)背后還隱藏著一個(gè)微妙的現(xiàn)象.比較8字節(jié)粒度時(shí)邊界是4的倍數(shù)的內(nèi)存的存取速度:

 

Figure10. 多字節(jié)存取對(duì)比 #3

 

   你會(huì)發(fā)現(xiàn)8字節(jié)粒度時(shí)邊界為4和12字節(jié)的內(nèi)存存取速度要比相同情況下的4和2字節(jié)粒度的慢.即使PowerPC硬件支持4字節(jié)對(duì)齊的8字節(jié)雙浮點(diǎn)型數(shù)據(jù)的存取,你還是要承擔(dān)額外的開(kāi)銷(xiāo)造成的損失.誠(chéng)然,這種損失絕不會(huì)像4610%那么大,但還是不能忽略的.這個(gè)實(shí)驗(yàn)告訴我們:存取非對(duì)齊內(nèi)存時(shí)，大粒度的存取可能會(huì)比小粒度存取還要慢