被遗忘的C结构体打包技术

原文见 http://www.catb.org/esr/structure-packing/　。　作者是著名hacker。　虽然讲的是Ｃ语言中一个很基本的概念，但条理清楚，读后仍能获得不少启发。　特别是文中提到的结构体的跨步地址（stride address)，我以前没有注意到！

１. 谁该阅读本文

本文是关于如何减少Ｃ程序的内存占用的：手工重新排列Ｃ结构体的成员声明来减小尺寸。为了读懂它，你需要基本的Ｃ语言知识。　


如果你想为内存受限的嵌入式系统或操作系统内核写代码，你需要了解该技术。　如果你在处理很大量的应用程序数据时经常超出了内存限制，或是你非常想要减小缓存不命中的次数，了解该技术是很有用的。


最后，理解该技术是其它难懂的Ｃ语言概念的入口。　你不是高级的Ｃ程序员除非你掌握了它。你不是Ｃ语言大师除非你自己能写出这样的文件并能聪明地评论它。

2. 我为什么写这篇文章

写这篇文章的起因是，2013年底我发现自己大量地使用一个Ｃ语言优化技术，而这种技术自从我二十多年前学习后就很少使用。


我的程序使用数千甚至数万个Ｃ结构实例，我需要减小内存占用。　该程序是cvs-fast-export , 它在处理巨大的源码库时，会因内存不够而退出。


在这种情况下有方法可以极大地减小内存占用，比如小心地重排结构成员的顺序。　这可以取得明显的效果：以我的情况为例，我能把工作时的内存占用减小40%，使程序能处理更大的源码库而不退出。


在处理问题并回味我的做法时，我意识到这种技术在今天大半被遗忘了。　做一个简单的网页搜索，可以看出至少在搜索引擎能够看到的地方，Ｃ程序员已经不怎么讨论它了。　有几个维基百科词条提到了它，但我觉得没人说得很全面。
　
这种现象也情有可原。　计算机课程（正确地）指引人们避开微观的优化而去寻找更优的算法。　硬件价格的下降也使挤压内存占用变得没有必要。　还有，hacker们以前用这种技术时，常在奇特的硬件架构上碰壁，当然，这种情况现在比较少见了。


但该技术仍在重要的情况下有用武之地，而且只要内存有限制，就会有用。　这篇文章的目的是避免Ｃ程序员重新发现该技术，使他们能专注于更重要的事情。

3. 对齐的要求

首先要理解的是，在现代处理器上，Ｃ编译器在内存里存放基本数据类型时是受限的：以最快存取速度为目标。
在X86或ARM上，基本数据类型并不是存放在任意内存地址上的。　每种类型除了char都有对齐要求(alignment requirement); char类型可以开始于任何地址，但２字节的short类型必须存放在偶数地址上，４字节的整型或浮点型必须放在能被４整除的位置上，而８字节的long或double型必须放在能被８整除的地址上。有符号或无符号没有差别。


用术语来讲就是，基本Ｃ类型在X86和ARM上都是自对齐的（self-aligned）。指针，不管是32位（４字节）还是64位（８字节）也是自对齐的。
自对齐能存取得更快是因为它能用一条指令来存取该类型数据。　另一方面，如果没有对齐限制，代码可能会在跨机器字边界存取的时候使用两条以上的指令。　字符是特殊情况: 不管它在们在机器字的哪个位置，存取代价都是一样的。所以它们没有对齐要求。

我说“在现代处理器上”，是因为在有些更老的处理器上，强迫你的Ｃ代码违反对齐限制（比如，把一个奇数地址转换为int指针并试图使用它）不仅会让你的代码变慢，还会造成非法指令异常。　比如在Sun　SPARC芯片上就是这样。　事实上，只要有足够的决心和正确的硬件标志(e18)，你也可以在X86上触发该异常。

自对齐还不是唯一的规则。　历史上，有些处理器（特别是那些没有barrel shifters的）有更严格的规则。如果你在做嵌入式系统，你可能撞到这些暗礁。要有心理准备。

有时你可以让编译器不遵守处理器的正常对齐规则，一般是使用pragma，比如　#pragma pack。　请不要随意使用，因为它会生成开销更大、更慢的代码。　通过使用我介绍的技术，你可以节省同样、甚至更多的内存。

使用#pragma pack的唯一合理理由是，你需要Ｃ数据分布完全匹配某些硬件或协议，比如一个经过内存映射的物理端口，则不违反对齐规则就无法做下去。　如果你处在那种情况，而不理解本文的内容，你会遇到大麻烦，祝你好运。

4. 填充（padding）

现在我们来看一个简单的例子，变量在内存中的分布。　考虑在Ｃ模块的顶部，有这些变量声明：

[cpp] view plaincopy

1. char *p;  
2. char c;  
3. int x;  

如果你不知道数据对齐，你可能会假定这三个变量在内存里占用连续的字节。　即，在32位机器上4字节的指针后面会紧跟1字节的char，而它后面会紧跟4字节的int。在64位机器上，唯一的差别是指针是８字节的。

这是（在x86或ARM或任何自对齐的机器上）实际的情况：p 存储在４字节或８字节对齐的位置上（由机器的字长决定）。　这是指针对齐－可能的最严格的情况。　

c的存储紧跟着p。但x的４字节对齐要求造成一个缺口，就好像有第四个变量插入其中：

[cpp] view plaincopy

1. char *p;      /* 4 or 8 bytes */  
2. char c;       /* 1 byte */  
3. char pad[3];  /* 3 bytes */  
4. int x;        /* 4 bytes */  

pad[3] 数组表示有３个字节浪费了。　老式的说法是“slop（溢出）”。

比较如果x 是２字节的short会怎样：

[cpp] view plaincopy

1. char *p;  
2. char c;  
3. short x;  

在这种情况下，实际的内存分布是这样的：

[cpp] view plaincopy

1. char *p;      /* 4 or 8 bytes */  
2. char c;       /* 1 byte */  
3. char pad[1];  /* 1 byte */  
4. short x;      /* 2 bytes */  

另一方面，如果是在64位机上，x 是一个long:

[cpp] view plaincopy

1. char *p;  
2. char c;  
3. long x;  

我们会得到：

[cpp] view plaincopy

1. char *p;     /* 8 bytes */  
2. char c;      /* 1 byte 
3. char pad[7]; /* 7 bytes */  
4. long x;      /* 8 bytes */  

如果你是仔细看到这儿的，你可能会想如果更短类型的变量放在前面会怎样：

[cpp] view plaincopy

1. char c;  
2. char *p;  
3. int x;  

如果实际的内存分布写成这样：

[cpp] view plaincopy

1. char c;  
2. char pad1[M];  
3. char *p;  
4. char pad2[N];  
5. int x;  

M 和　N  应该是多少？

首先，N 是０。　x 的地址紧接着p，保证了x 是指针对齐的，而指针对齐肯定比整型对齐更严。

c极有可能被映射到机器字的第一个字节上。　因此M是能让p满足指针对齐的数目－在32位机上是３，在64位上是７。

中间情况也是可能的。　因为char有可能被安排在一个机器字中的任意位置，Ｍ有可能是０到７（在32位机上是０到３）。　

如果你想让这些变量占用较少的空间，你可以交换x和c的位置：

[cpp] view plaincopy

1. char *p;     /* 8 bytes */  
2. long x;      /* 8 bytes */  
3. char c;      /* 1 byte  

通常对于数量较少的Ｃ程序中的标量来说，通过调整声明顺序获得的区区几个字节可能没什么大不了。这种技术如果应用到非标量变量－特别是结构，会变得更加有趣。

在我们继续之前，先说一下标量数组。　在一个自对齐类型的平台上，char/short/int/long/pointer 数组内部没有填充；每个成员都跟在前一个成员后面，自动对齐了。

在下一节我们将看到，在结构体数据里，以上规律并不一定正确。

5. 结构体的对齐和填充

总的来说，结构体实例会和它的最宽成员一样对齐。　编译器这样做因为这是保证所有成员自对齐以获得快速存取的最容易方法。

而且，在Ｃ中，结构的地址等于它的第一个成员的地址－没有前导填充。　注意：在Ｃ++中，形似结构的类可能会破坏这个规则！（跟基类和虚函数如何实现有关，也因编译器而异。）

（当你对此有疑惑时，你可以使用ANSI C 提供的offset()宏来得到结构成员的偏移。）

考虑这个结构：

[cpp] view plaincopy

1. struct foo1 {  
2.     char *p;  
3.     char c;  
4.     long x;  
5. };  

假定是在一台64位机上，那么任何struct foo1的实例都是８字节对齐的。内存分布应是这样的：

[cpp] view plaincopy

1. struct foo1 {  
2.     char *p;     /* 8 bytes */  
3.     char c;      /* 1 byte 
4.     char pad[7]; /* 7 bytes */  
5.     long x;      /* 8 bytes */  
6. };  

就好像这些变量是单独声明的。　但如果我们把c放到第一位，就不是这样了：

[cpp] view plaincopy

1. struct foo2 {  
2.     char c;      /* 1 byte */  
3.     char pad[7]; /* 7 bytes */  
4.     char *p;     /* 8 bytes */  
5.     long x;      /* 8 bytes */  
6. };  

如果单独声明，c可以在任意字节边界上，而pad的尺寸也会不同。　但因为struct foo2有最宽成员的指针对齐，以上情况不可能了。　现在c必须处在指针对齐的位置上，后面跟着锁定的７字节的填充。

现在我们讨论一下结构的拖尾填充(trailing padding)。　为了解释，我需要引入一个我称为跨步地址（stride address）的基本概念。它是跟在结构体后面跟该结构体有相同对齐的数据的第一个地址。拖尾填充的总规则是：　结构体的拖尾填充一直延伸到它的跨步地址。　这条规则决定了sizeof()的返回值。

考虑在64位x86或ARM机器上的这个例子：

[cpp] view plaincopy

1. struct foo3 {  
2.     char *p;     /* 8 bytes */  
3.     char c;      /* 1 byte */  
4. };  
5.   
6. struct foo3 singleton;  
7. struct foo3 quad[4];  

你可能会以为sizeof(struct foo3)会返回９，其实是16。　　跨步地址即quad[0].p的地址，这样，在quad数组里，每个成员都有７字节的拖尾填充，因为下一个结构体的第一个成员需要在８字节边界上对齐。　内存分布就好像这个结构是这样声明的：

[cpp] view plaincopy

1. struct foo3 {  
2.     char *p;     /* 8 bytes */  
3.     char c;      /* 1 byte */  
4.     char pad[7];  
5. };  

作为对比，考虑这个例子：

[cpp] view plaincopy

1. struct foo4 {  
2.     short s;     /* 2 bytes */  
3.     char c;      /* 1 byte */  
4. };  

因为s只需要２字节对齐，跨步地址仅是c后面的一个字节，struct foo4只有一字节的拖尾填充。　就像这样：

[cpp] view plaincopy

1. struct foo4 {  
2.     short s;     /* 2 bytes */  
3.     char c;      /* 1 byte */  
4.     char pad[1];  
5. };  

而sizeof(struct foo4) 返回４。

现在让我们考虑位域(bitfields)。　它们使得你能声明比字节宽度更小的成员，低至１位，比如：

[cpp] view plaincopy

1. struct foo5 {  
2.     short s;  
3.     char c;  
4.     int flip:1;  
5.     int nybble:4;  
6.     int septet:7;  
7. };  

关于位域需要了解的是，它们是由字或字节层面的掩码和移位指令来实现的。　从编译器的角度来看，struct foo5里的位域就像２字节，16位的字符数组，只用到了12位。　为了使结构体的长度是它的最宽成员长度（即sizeof(short)）的整数倍，还有一个字节的填充：

[cpp] view plaincopy

1. struct foo5 {  
2.     short s;       /* 2 bytes */  
3.     char c;        /* 1 byte */  
4.     int flip:1;    /* total 1 bit */  
5.     int nybble:4;  /* total 5 bits */  
6.     int septet:7;  /* total 12 bits */  
7.     int pad1:4;    /* total 16 bits = 2 bytes */  
8.     char pad2;     /* 1 byte */  
9. };  

这是最后一个重要细节：如果你的结构体中含有结构体，里面的结构体也要和最长的标量有相同的对齐。假如你定义了这个：

[cpp] view plaincopy

1. struct foo6 {  
2.     char c;  
3.     struct foo5 {  
4.         char *p;  
5.         short x;  
6.     } inner;  
7. };  

char *p 成员不但使外层结构体也使内层结构体处在指针对齐的位置上。在64位机上实际的内存分布像这样：

[cpp] view plaincopy

1. struct foo6 {  
2.     char c;           /* 1 byte*/  
3.     char pad1[7];     /* 7 bytes */  
4.     struct foo6_inner {  
5.         char *p;      /* 8 bytes */  
6.         short x;      /* 2 bytes */  
7.         char pad2[6]; /* 6 bytes */  
8.     } inner;  
9. };  

该结构提示我们能从重排结构成员中节省多少空间。24字节中，有13个是填充！超过50%的空间浪费了！

6. 结构成员重排

理解了编译器在结构体中间和尾部插入填充的原因和方式后，我们要检查一下如何挤压这些溢出(slop)。　这就是结构体压缩技术。

首先我们注意到溢出只发生在两个地方。　一个是较大的数据类型（从而需要更严格的对齐）跟在较小的数据后面。　另一个是结构体自然结束的位置到跨步地址之间需要填充，以使下一个相同结构能正确地对齐。

最简单的消除溢出的方式是按对齐值的递减来排序成员。　即让指针对齐的成员排在最前面，因为在64位机上它们是8字节；然后是4字节的int；然后是2字节的short，然后是字符。

因此，以简单的链表结构为例：

[cpp] view plaincopy

1. struct foo7 {  
2.     char c;  
3.     struct foo7 *p;  
4.     short x;  
5. };  

把隐含的溢出写明：

[cpp] view plaincopy

1. struct foo7 {  
2.     char c;         /* 1 byte */  
3.     char pad1[7];   /* 7 bytes */  
4.     struct foo7 *p; /* 8 bytes */  
5.     short x;        /* 2 bytes */  
6.     char pad2[6];   /* 6 bytes */  
7. };  

一共是24字节。　如果按长度排序，是：

[cpp] view plaincopy

1. struct foo8 {  
2.     struct foo8 *p;  
3.     short x;  
4.     char c;  
5. };  

考虑到自对齐，我们发现没有一个数据域需要填充。因为有较严对齐要求的成员的跨步地址对不太严对齐要求的数据来说，总是合法的对齐地址。重打包过的结构体只需要拖尾填充：

[cpp] view plaincopy

1. struct foo8 {  
2.     struct foo8 *p; /* 8 bytes */  
3.     short x;        /* 2 bytes */  
4.     char c;         /* 1 byte */  
5.     char pad[5];    /* 5 bytes */  
6. };  

注意重排并不能保证节省空间。　把它应用到先前的例子，　struct foo6，我们得到:

[cpp] view plaincopy

1. struct foo9 {  
2.     struct foo9_inner {  
3.         char *p;      /* 8 bytes */  
4.         int x;        /* 4 bytes */  
5.     } inner;  
6.     char c;           /* 1 byte*/  
7. };  

把填充写明：

[cpp] view plaincopy

1. struct foo9 {  
2.     struct foo9_inner {  
3.         char *p;      /* 8 bytes */  
4.         int x;        /* 4 bytes */  
5.         char pad[4];  /* 4 bytes */  
6.     } inner;  
7.     char c;           /* 1 byte*/  
8.     char pad[7];      /* 7 bytes */  
9. };  

还是24字节，因为c不能放进内层结构的拖尾填充。　为了节省这些空间你要重新设计数据结构。

7. 怪异数据类型

如果符号调试器能显示枚举类型的名称而不原始的数字，使用枚举来代替#define是个好办法。然而，虽然枚举必须与某种整型兼容，Ｃ标准却没有指定到底是何种整型。

请当心重打包结构体的时候，枚举型变量通常是int，这跟编译器相关；但它们也可能是short，long，甚至默认是char。你的编译器可能会有progma或命令行选项指定枚举的尺寸。

long double 是个类似的故障点。　有些C平台以80位实现它，有些是128位，而一些80位平台把它填充到96或128位。

在以上两种情况下最好用sizeof()来检查存储的尺寸。

8. 可读性和cache局部性

按成员尺寸重排是最简单的消除溢出的方式，但不一定是正确的方式。　还有两个问题：可读性和cache局部性。

程序不仅与计算机交流，还与人类交流。　特别当交流的观众是将来的你的时候，代码可读性更重要的。

一个笨拙的、机械的重排可能影响可读性。有可能的话，最好这样重排成员：使得语义相关的数据放在一起，形成连贯的组。　最理想的是，结构体的设计要与程序的设计相互沟通。

当你的程序频繁地存取某个结构或它的一部分，如果存取总是能放进一条cache 行,对提高性能是很有帮助的。cache　行是这样的内存块，当处理器要去取该内存块内的任何单个地址时，会把整个内存块都取出来。　在64位x86上，一条cache 行是64字节，开始于自对齐的地址。在其它平台上通常是32字节。

你为保持可读性而做的事－把相关的和同时要存取的数据放在相邻的位置－也会提高cache行局部性。　它们都是聪明地重排、把数据的存取模式放在心上的原因。

如果你的代码从多个线程上同时存取一个结构体，会有第三个问题：cache line bouncing。　为了减少昂贵的总线通信，你应该这样安排数据，使得在一个更紧的循环里，从一条cache line 里读数据，而往另一条写数据。

是的，这种做法与前面说的把相关的数据放入与cache line长度相同的块矛盾。多线程是困难的。　Cache line bouncing 和其它多线程优化问题是很高级的话题，值得单独为它们写个指导。　这里我能做的只是让你了解有这些问题存在。

　

9. 其它打包技术

在为你的结构瘦身的时候，重排序与其它技术结合在一起工作得最好。如果你在结构里有几个布尔标志，可以考虑把它们压缩成1位的位域，然后把它们打包放在本来可能成为slop(溢出)的地方。

你可能会有一点儿存取时间的损失－但如果它把工作空间压缩得足够小，那点损失可以从避免cache miss 来补偿。

总的原则是，选择能把数据类型缩短的方法。　以cvs-fast-export为例，我使用的一个压缩方法是：利用RCS和CVS在1982年前还不存在这个事实，我弃用了64位的Unix time_t（在1970年开始的时候是零），而用了一个32位的、从1982-01-01T00:00:00开始的偏移量；这样日期会覆盖到2118年。（注意，如果你使用这样的技巧，要用边界条件检查以防讨厌的bug!)

每样缩短法不仅减小了结构的可见尺寸，还可以消除溢出或创造额外的机会来进行重新排序。　这种效果的良性互动是不难被触发的。

最冒险的打包方法是使用union。　如果你知道结构体中的某些域永远不会跟另一些域一起使用，考虑用union使它们共享存储空间。　不过请特别小心，要用回归测试验证你的做法。因为如果你的分析有一丁点儿错误，就会有从程序崩溃到（更糟的）微妙的数据损坏。

10. 工具

有个叫   pahole 的工具，　我自己没有使用过它，不过有一些反馈说它挺好的。该工具与编译器协同工作，输出关于结构体的填充、对齐和cache line 边界的报告。

11. 证明和例外

这个小程序演示了关于标量和结构体的尺寸的断言。　你可以下载它的源码　packtest.c 。

如果你仔细检查各种编译器、选项和罕见硬件的奇怪组合，你会发现我前面提到的规则有例外。　越是旧的处理器设计例外越是常见。

理解这些规则的第二个层次是，何时和如何期望这些规则会被破坏。　在我学习它们的日子里（1980年代早期），我们把不理解这些的人叫做“世上所有的机器都是VAX 综合症”的牺牲品。　记住，并不是世上所有的电脑都是PC。