失落的C語言結構體封裝藝術
Eric S. Raymond
目錄
1. 誰該閱讀這篇文章
2. 我為什么寫這篇文章
3.對齊要求
4.填充
5.結構體對齊及填充
6.結構體重排序
7.難以處理的標量的情況
8.可讀性和緩存局部性
9.其他封裝的技術
10.工具
11.證明及例外
12.版本履歷
1. 誰該閱讀這篇文章
本文是關于削減C語言程序內存占用空間的一項技術——為了減小內存大小而手工重新封裝C結構體聲明。你需要C語言的基本知識來讀懂本文。
如果你要為內存有限制的嵌入式系統(tǒng)、或者操作系統(tǒng)內核寫代碼，那么你需要懂這項技術。如果你在處理極大的應用程序數據集，以至于你的程序常常達到內存的界限時，這項技術是有幫助的。在任何你真的真的需要關注將高速緩存行未命中降到最低的應用程序里，懂得這項技術是很好的。
最后，理解該技術是一個通往其他深奧的C語言話題的入口。直到你掌握了它，你才成為一個高端的C程序員。直到你可以自己寫出這篇文檔并且可以理智地評論它，你才成為一位C語言大師。
2. 我為什么寫這篇文章
本文之所以存在，是因為在2013年底，我發(fā)現我自己在大量使用一項C語言的優(yōu)化技術，我早在二十多年前就已經學會了該技術，不過在那之后并沒怎么使用過。
我需要減小一個程序的內存占用空間，它用了幾千——有時是幾十萬個——C結構體的實例。這個程序是cvs-fast-export，而問題在于處理巨大的代碼庫時，它曾因內存耗盡的錯誤而瀕臨崩潰。
在這類情況下，有好些辦法能極大地減少內存使用的，比如小心地重新安排結構體成員的順序之類的。這可以獲得巨大的收益——在我的事例中，我能夠減掉大約40%的工作區(qū)大小，使得程序能夠在不崩潰的情況下處理大得多的代碼庫。
當我解決這個問題，并且回想我所做的工作時，我開始發(fā)現，我在用的這個技術現今應被忘了大半了。一個網絡調查確認，C程序員好像已經不再談論該技術了，至少在搜索引擎可以看到的地方不談論了。有幾個維基百科條目觸及了這個話題，但是我發(fā)現沒人能全面涵蓋。
實際上這個現象也是有合理的理由的。計算機科學課程（應當）引導人們避開細節(jié)的優(yōu)化而去尋找更好的算法。機器資源價格的暴跌已經使得壓榨內存用量變 得不那么必要了。而且，想當年，駭客們曾經學習如何使用該技術，使得他們在陌生的硬件架構上撞墻了——現在已經不太常見的經歷。
但是這項技術仍然在重要的場合有價值， 并且只要內存有限，就能永存。本文目的就是讓C程序員免于重新找尋這項技術，而讓他們可以集中精力在更重要的事情上。
3. 對齊要求（Alignment Requirement）
要明白的第一件事是，在現代處理器上，你的C編譯器在內存里對基本的C數據類型的存放方式是受約束的，為的是內存訪問更快。
在x86或者ARM處理器上，基本的C數據類型的儲存一般并不是起始于內存中的任意字節(jié)地址。而是，每種類型，除了字符型以外，都有對齊要求；字符 可以起始于任何字節(jié)地址，但是2字節(jié)的短整型必須起始于一個偶數地址，4字節(jié)整型或者浮點型必須起始于被4整除的地址，以及8字節(jié)長整型或者雙精度浮點型 必須起始于被8整除的地址。帶符號與不帶符號之間沒有差別。
這個的行話叫：在x86和ARM上，基本的C語言類型是自對齊（self-aligned）的。指針，無論是32位（4字節(jié)）亦或是64位（8字節(jié)）也都是自對齊的。
自對齊使得訪問更快，因為它使得一條指令就完成對類型化數據的取和存操作。沒有對齊的約束，反過來，代碼最終可能會不得不跨越機器字的邊界做兩次或更多次訪問。字符是特殊的情況；無論在一個單機器字中的何處，存取的花費都是一樣的。那就是為什么字符型沒有被建議對齊。
我說“在現代的處理器上”是因為，在一些舊的處理器上，強制讓你的C程序違反對齊約束（比方說，將一個奇數的地址轉換成一個整型指針，并試圖使用 它）不僅會使你的代碼慢下來，還會造成非法指令的錯誤。比如在Sun的SPARC芯片上就曾經這么干。實際上，只要夠決心并在處理器上設定正確（e18） 的硬件標志位，你仍然可以在x86上觸發(fā)此錯誤。
此外，自對齊不是唯一的可能的規(guī)則。歷史上，一些處理器（特別是那些缺少移位暫存器的）有更強的限制性規(guī)則。如果你做嵌入式系統(tǒng)，你也許會在跌倒在這些叢林陷阱中。注意，這是有可能的。
有時你可以通過編譯指示，強制讓你的編譯器不使用處理器正常的對齊規(guī)則，通常是#pragma pack。不要隨意使用，因為它會導致產生開銷更大、更慢的代碼。使用我在這里描述的技術，通常你可以節(jié)省同樣或者幾乎同樣多的內存。
#pragma pack的唯一好處是，如果你不得不將你的C語言數據分布精確匹配到某些位級別的硬件或協(xié)議的需求，比如一個內存映射的硬件端口，要求違反正常的對齊才能奏效。如果你遇到那種情況，并且你還未理解我在這里寫的這一切，你會有大麻煩的，我只能祝你好運了。
#p#
4. 填充（Padding）
現在我們來看一個簡單變量在內存里的分布的例子?？紤]在C模塊的最頂上的以下一系列的變量聲明：
- char *p;
- char c;
- int x;
如果你不知道任何關于數據對齊的事情，你可能會假設這3個變量在內存里會占據一個連續(xù)字節(jié)空間。那也就是說，在一個32位機器上，指針的4字節(jié)，之后緊接著1字節(jié)的字符型，且之后緊接著4字節(jié)的整型。在64位機器只在指針是8字節(jié)上會有所不同。
這里是實際發(fā)生的（在x86或ARM或其他任何有自對齊的處理器類型）。p的存儲地址始于一個自對齊的4字節(jié)或者8字節(jié)邊界，取決于機器的字長。這是指針對齊——可能是最嚴格的情況。
緊跟著的是c的存儲地址。但是x的4字節(jié)對齊要求，在內存分布上造成了一個間隙；變成了恰似第四個變量插在其中，像這樣：
- char *p; /* 4 or 8 bytes */
- char c; /* 1 byte */
- char pad[3]; /* 3 bytes */
- int x; /* 4 bytes */
pad[3]字符數組表示了一個事實，結構體中有3字節(jié)的無用的空間。 老派的術語稱之為“slop（水坑）”。
比較如果x是2字節(jié)的短整型會發(fā)生什么：
- char *p;
- char c;
- short x;
在那個情況下，實際的內存分布會變成這樣：
- char *p; /* 4 or 8 bytes */
- char c; /* 1 byte */
- char pad[1]; /* 1 byte */
- short x; /* 2 bytes */
另一方面，如果x是一個在64位機上的長整型
- char *p;
- char c;
- long x;
最終我們會得到：
- char *p; /* 8 bytes */
- char c; /* 1 byte
- char pad[7]; /* 7 bytes */
- long x; /* 8 bytes */
如果你已仔細看到這里，現在你可能會想到越短的變量聲明先聲明的情況：
- char c;
- char *p;
- int x;
如果實際的內存分布寫成這樣：
- char c;
- char pad1[M];
- char *p;
- char pad2[N];
- int x;
我們可以說出M和N的值嗎？
首先，在這個例子中，N是零。x的地址，緊接在p之后，是保證指針對齊的，肯定比整型對齊更嚴格的。
M的值不太能預測。如果編譯器恰巧把c映射到機器字的最后一個字節(jié)，下一個字節(jié)（p的第一部分）會成為下一個機器字的第一個字節(jié)，并且正常地指針對齊。M為零。
c更可能會被映射到機器字的第一個字節(jié)。在那個情況下，M會是以保證p指針對齊而填補的數——在32位機器上是3，64位機器上是7。
如果你想讓那些變量占用更少的空間，你可以通過交換原序列中的x和c來達到效果。
- char *p; /* 8 bytes */
- long x; /* 8 bytes */
- char c; /* 1 byte
通常，對于C程序里少數的簡單變量，你可以通過調整聲明順序來壓縮掉極少幾個字節(jié)數，不會有顯著的節(jié)約。但當用于非標量變量（nonscalar variables），尤其是結構體時，這項技術會變得更有趣。
在我們講到非標量變量之前，讓我們講一下標量數組。在一個有自對齊類型的平臺上，字符、短整型、整型、長整型、指針數組沒有內部填充。每個成員會自動自對齊到上一個之后（譯者注：原文 self-aligned at the end of the next one 似有誤）。
在下一章，我們會看到對于結構體數組，一樣的規(guī)則并不一定正確。
5. 結構體的對齊和填充
總的來說，一個結構體實例會按照它最寬的標量成員對齊。編譯器這樣做，把它作為最簡單的方式來保證所有成員是自對齊，為了快速訪問的目的。
而且，在C語言里，結構體的地址與它第一個成員的地址是相同的——沒有前置填充。注意：在C++里，看上去像結構體的類可能不遵守這個規(guī)則?。ㄗ癫蛔袷匾蕾囉诨惡吞摂M內存函數如何實現，而且因編譯器而不同。）
（當你不能確定此類事情時，ANSI C提供了一個offsetof（）宏，能夠用來表示出結構體成員的偏移量。）
考慮這個結構體：
- struct foo1 {
- char *p;
- char c;
- long x;
- };
#p#
假設一臺64位的機器，任何struct foo1的實例會按8字節(jié)對齊。其中的任何一個的內存分布看上去無疑應該像這樣：
- struct foo1 {
- char *p; /* 8 bytes */
- char c; /* 1 byte
- char pad[7]; /* 7 bytes */
- long x; /* 8 bytes */
- };
的分布就恰好就像這些類型的變量是單獨聲明的。但是如果我們把c放在第一個，這就不是了。
- struct foo2 {
- char c; /* 1 byte */
- char pad[7]; /* 7 bytes */
- char *p; /* 8 bytes */
- long x; /* 8 bytes */
- };
如果成員是單獨的變量，c可以起始于任何字節(jié)邊界，并且pad的大小會不同。但因為struct foo2有按其最寬成員進行的指針對齊，那就不可能了?，F在c必須于指針對齊，之后7個字節(jié)的填充就被鎖定了。
現在讓我們來說說關于在結構體成員的尾隨填充（trailing padding）。要解釋這個，我需要介紹一個基本概念，我稱之為結構體的跨步地址（stride address）。它是跟隨結構體數據后的第一個地址，與結構體擁有同樣對齊方式。
結構體尾隨填充的通常規(guī)則是這樣的：編譯器的行為就如把結構體尾隨填充到它的跨步地址。這條規(guī)則決定了sizeof（）的返回值。
考慮在64位的x86或ARM上的這個例子：
- struct foo3 {
- char *p; /* 8 bytes */
- char c; /* 1 byte */
- };
- struct foo3 singleton;
- struct foo3 quad[4];
你可能會認為，sizeof（struct foo3）應該是9，但實際上是16?？绮降刂肥牵?amp;p）[2]的地址。如此，在quad數組中，每個成員有尾隨填充的7字節(jié)，因為每個跟隨的結構體的第一個成員都要自對齊到8字節(jié)的邊界上。內存分布就如結構體像這樣聲明：
- struct foo3 {
- char *p; /* 8 bytes */
- char c; /* 1 byte */
- char pad[7];
- };
作為對照，考慮下面的例子：
- struct foo4 {
- short s; /* 2 bytes */
- char c; /* 1 byte */
- };
因為s只需對齊到2字節(jié)， 跨步地址就只有c后面的一個字節(jié)，struct foo4作為一個整體，只需要一個字節(jié)的尾隨填充。它會像這樣分布
- struct foo4 {
- short s; /* 2 bytes */
- char c; /* 1 byte */
- char pad[1];
- };
并且sizeof（struct foo4）會返回4。
現在讓我們考慮位域（bitfield）。它們是你能夠聲明比字符寬度還小的結構體域，小到1位，像這樣：
- struct foo5 {
- short s;
- char c;
- int flip:1;
- int nybble:4;
- int septet:7;
- };
關于位域需要知道的事情是，它們以字或字節(jié)級別的掩碼和移位指令來實現。從編譯器的觀點來看，struct foo5的位域看上去像2字節(jié)，16位的字符數組里只有12位被使用。接著是填充，使得這個結構體的字節(jié)長度成為sizeof（short）的倍數即最長成員的大小。
- struct foo5 {
- short s; /* 2 bytes */
- char c; /* 1 byte */
- int flip:1; /* total 1 bit */
- int nybble:4; /* total 5 bits */
- int septet:7; /* total 12 bits */
- int pad1:4; /* total 16 bits = 2 bytes */
- char pad2; /* 1 byte */
- };
這里是最后一個重要的細節(jié)：如果你的結構體含有結構體的成員，里面的結構體也需要按最長的標量對齊。假設如果你寫成這樣：
- struct foo6 {
- char c;
- struct foo5 {
- char *p;
- short x;
- } inner;
- };
這個結構體給了我們一個啟示，重新封裝結構體可能節(jié)省空間。24個字節(jié)中，有13個字節(jié)是用作填充的。超過50%的無用空間！
#p#
6. 結構體重排序（reordering）
現在你知道如何以及為何編譯器要插入填充，在你的結構體之中或者之后，我們要考察你可以做些什么來擠掉這些“水坑”。這就是結構體封裝的藝術。
第一件需要注意的事情是，“水坑”僅發(fā)生于兩個地方。一個是大數據類型（有更嚴格的對齊要求）的存儲區(qū)域緊跟在一個較小的數據類型的存儲區(qū)域之后。另一個是結構體自然結束于它的跨步地址之前，需要填充，以使下一個實例可以正確對齊。
消除“水坑”的最簡單的方法是按對齊的降序來對結構體成員重排序。就是說：所有指針對齊的子域在前面，因為在64位的機器上，它們會有8字節(jié)。接下來是4字節(jié)的整型；然后是2字節(jié)的短整型；然后是字符域。
因此，舉個例子，考慮這個簡單的鏈表結構體：
- struct foo7 {
- char c;
- struct foo7 *p;
- short x;
- };
顯現出隱含的“水坑”，這樣：
- struct foo7 {
- char c; /* 1 byte */
- char pad1[7]; /* 7 bytes */
- struct foo7 *p; /* 8 bytes */
- short x; /* 2 bytes */
- char pad2[6]; /* 6 bytes */
- };
24個字節(jié)。如果我們按大小重新排序，我們得到：
- struct foo8 {
- struct foo8 *p;
- short x;
- char c;
- };
考慮到自對齊，我們看到沒有數據域需要填充。這是因為一個較長的、有較嚴格對齊的域的跨步地址，對于較短的、較不嚴格對齊的域來說，總是合法對齊的起始地址。所有重封裝的結構體實際上需要的只是尾隨填充：
- struct foo8 {
- struct foo8 *p; /* 8 bytes */
- short x; /* 2 bytes */
- char c; /* 1 byte */
- char pad[5]; /* 5 bytes */
- };
我們重封裝的轉變把大小降到了16字節(jié)。這可能看上去沒什么，但是假設你有一個200k的這樣的鏈表呢？節(jié)省的空間累積起來就不小了。
注意重排序并不能保證節(jié)省空間。把這個技巧運用到早先的例子，struct foo6，我們得到：
- struct foo9 {
- struct foo9_inner {
- char *p; /* 8 bytes */
- int x; /* 4 bytes */
- } inner;
- char c; /* 1 byte*/
- };
把填充寫出來，就是這樣
- struct foo9 {
- struct foo9_inner {
- char *p; /* 8 bytes */
- int x; /* 4 bytes */
- char pad[4]; /* 4 bytes */
- } inner;
- char c; /* 1 byte*/
- char pad[7]; /* 7 bytes */
- };
它仍然是24字節(jié)，因為c不能轉換到內部結構體成員的尾隨填充。為了獲得節(jié)省空間的好處，你需要重新設計你的數據結構。
自從發(fā)布了這篇指南的第一版，我就被問到了，如果通過重排序來得到最少的“水坑”是如此簡單，為什么C編譯器不自動完成呢？答案是：C語言最初是被 設計用來寫操作系統(tǒng)和其他接近硬件的語言。自動重排序會妨礙到系統(tǒng)程序員規(guī)劃結構體，精確匹配字節(jié)和內存映射設備控制塊的位級分布的能力。
7. 難以處理的標量的情況
使用枚舉類型而不是#defines是個好主意，因為符號調試器可以用那些符號并且可以顯示它們，而不是未處理的整數。但是，盡管枚舉要保證兼容整型類型，C標準沒有明確規(guī)定哪些潛在的整型類型會被使用。
注意，當重新封裝你的結構體時，雖然枚舉類型變量通常是整型，但它依賴于編譯器；它們可能是短整型、長整型、甚至是默認的字符型。你的編譯器可能有一個編譯指示或者命令行選項來強制規(guī)定大小。
long double類型也是個相似的麻煩點。有的C平臺以80位實現，有的是128， 還有的80位的平臺填充到96或128位。
在這兩種情況下，最好用sizeof（）來檢查存儲大小。
最后，在x86下，Linux的雙精度類型有時是一個自對齊規(guī)則的特例；一個8字節(jié)的雙精度數據在一個結構體內可以只要求4字節(jié)對齊，雖然單獨的雙精度變量要求8字節(jié)的自對齊。這依賴于編譯器及其選項。
#p#
8. 可讀性和緩存局部性
盡管按大小重排序是消除“水坑”的最簡單的方式，但它不是必定正確的。還有兩個問題：可讀性和緩存局部性。
程序不只是與計算機的交流，還是與其他人的交流。代碼可讀性是重要的，即便（或者尤其是?。┙涣鞯牧硪环讲恢皇俏磥淼哪?。
笨拙的、機械的結構體重排序會損害可讀性?？赡艿脑?，最好重排域，使得語義相關的數據段緊緊相連，能形成連貫的組群。理想情況下，你的結構體設計應該傳達到你的程序。
當你的程序經常訪問一個結構體，或者結構體的一部分，如果訪問常命中緩存行（當被告知去讀取任何一個塊里單個地址時，你的處理器讀取的整一塊內存）有助于提高性能。在64位x86機上一條緩存行為64字節(jié)，始于一個自對齊的地址；在其他平臺上經常是32字節(jié)。
你應該做的事情是保持可讀性——把相關的和同時訪問的數據組合到毗鄰的區(qū)域——這也會提高緩存行的局部性。這都是用代碼的數據訪問模式的意識，聰明地重排序的原因。
如果你的代碼有多線程并發(fā)訪問一個結構體，就會有第三個問題：緩存行反彈（cache line bouncing）。為了減少代價高昂的總線通信，你應該組織你的數據，使得在緊湊的循環(huán)中，從一條緩存行中讀取，而在另一條緩存行中寫。
是的，這與之前關于把相關數據組成同樣大小的緩存行塊的指南有些矛盾。多線程是困難的。緩存行反彈以及其它的多線程優(yōu)化問題是十分高級的話題，需要整篇關于它們的教程。這里我能做的最好的就就是讓你意識到這些問題的存在。
9. 其它封裝技術
當重排序與其他技術結合讓你的結構體瘦身時效果最好。如果你在一個結構體里有若干布爾型標志，舉個例子，可以考慮將它們減小到1位的位域，并且將它們封裝到結構體里的一個本會成為“水坑”的地方。
為此，你會碰到些許訪問時間上的不利——但是如果它把工作區(qū)擠壓得足夠小，這些不利會被避免緩存不命中的得益所掩蓋。
更普遍的，尋找縮小數據域大小的方式。比如在cvs-fast-export里，我用的一項壓縮技術里用到了在1982年之前RCS和CVS代碼庫還不存在的知識。我把64位的Unix time_t（1970年作為起始0日期）減少到32位的、從1982-01-01T00:00:00開始的時間偏移量；這會覆蓋2118年前的日期。（注意：如果你要玩這樣的花招，每當你要設定字段，你都要做邊界檢查以防討厭的錯誤?。?/p>
每一個這樣被縮小的域不僅減少了你結構體顯在的大小，還會消除“水坑”，且/或創(chuàng)建額外的機會來得到域重排序的好處。這些效果的良性疊加不難得到。
最有風險的封裝形式是使用聯(lián)合體。如果你知道你結構體中特定的域永遠不會被用于與其他特定域的組合，考慮使用聯(lián)合體使得它們共享存儲空間。但你要額 外小心，并且用回歸測試來驗證你的工作，因為如果你的生命周期分析即使有輕微差錯，你會得到各種程序漏洞，從程序崩潰到（更糟糕的）不易發(fā)覺的數據損壞。
10. 工具
C語言編譯器有個-Wpadded選項，能使它產生關于對齊空洞和填充的消息。
雖然我自己還沒用過，但是一些反饋者稱贊了一個叫pahole的程序。這個工具與編譯器合作，產生關于你的結構體的報告，記述了填充、對齊及緩存行邊界。
11. 證明及例外
你可以下載一個小程序的代碼，此代碼用來展示了上述標量和結構體大小的論斷。就是packtest.c。
如果你瀏覽足夠多的編譯器、選項和不常見的硬件的奇怪組合，你會發(fā)現針對我講述的一些規(guī)則的特例。如果你回到越舊的處理器設計，就會越常見。
比知道這些規(guī)則更進一步，是知道如何以及何時這些規(guī)則會被打破。在我學習它們的那些年（1980年代早期），我們把不懂這些的人稱為“世界都是VAX綜合征”的受害者。記住世界上不只有PC。
12. 版本履歷
1.5 @ 2014-01-03
解釋了為什么不自動做結構體成員的重排序。
1.4 @ 2014-01-06
關于x86 Linux下雙精度的注意。
1.3 @ 2014-01-03
關于難以處理的標量實例、可讀性和緩存局部性及工具的段落。
1.2 @ 2014-01-02
修正了一個錯誤的地址計算。
1.1 @ 2014-01-01
解釋為什么對齊的訪問會更快。提及offsetof。各種小修復，包括packtest.c的下載鏈接。
1.0 @ 2014-01-01
初版
