1. 谁该阅读这篇文章
2. 我为什么写这篇文章
3.对齐要求
4.填充
5.结构体对齐及填充
6.结构体重排序
7.难以处理的标量的情况
8.可读性和缓存局部性
9.其他封装的技术
10.工具
11.证明及例外
12.版本履历
1. 谁该阅读这篇文章
本文是关于削减C语言程序内存占用空间的一项技术——为了减小内存大小而手工重新封装C结构体声明。你需要C语言的基本知识来读懂本文。
如果你要为内存有限制的嵌入式系统、或者操作系统内核写代码，那么你需要懂这项技术。如果你在处理极大的应用程序数据集，以至于你的程序常常达到内存的界限时，这项技术是有帮助的。在任何你真的真的需要关注将高速缓存行未命中降到最低的应用程序里，懂得这项技术是很好的。
最后，理解该技术是一个通往其他深奥的C语言话题的入口。直到你掌握了它，你才成为一个高端的C程序员。直到你可以自己写出这篇文档并且可以理智地评论它，你才成为一位C语言大师。
2. 我为什么写这篇文章
本文之所以存在，是因为在2013年底，我发现我自己在大量使用一项C语言的优化技术，我早在二十多年前就已经学会了该技术，不过在那之后并没怎么使用过。
我需要减小一个程序的内存占用空间，它用了几千——有时是几十万个——C结构体的实例。这个程序是，而问题在于处理巨大的代码库时，它曾因内存耗尽的错误而濒临崩溃。
在这类情况下，有好些办法能极大地减少内存使用的，比如小心地重新安排结构体成员的顺序之类的。这可以获得巨大的收益——在我的事例中，我能够减掉大约40%的工作区大小，使得程序能够在不崩溃的情况下处理大得多的代码库。
当我解决这个问题，并且回想我所做的工作时，我开始发现，我在用的这个技术现今应被忘了大半了。一个网络调查确认，C程序员好像已经不再谈论该技术了，至少在搜索引擎可以看到的地方不谈论了。有几个维基百科条目触及了这个话题，但是我发现没人能全面涵盖。
实际上这个现象也是有合理的理由的。计算机科学课程（应当）引导人们避开细节的优化而去寻找更好的算法。机器资源价格的暴跌已经使得压榨内存用量变得不那么必要了。而且，想当年，骇客们曾经学习如何使用该技术，使得他们在陌生的硬件架构上撞墙了——现在已经不太常见的经历。
但是这项技术仍然在重要的场合有价值， 并且只要内存有限，就能永存。本文目的就是让C程序员免于重新找寻这项技术，而让他们可以集中精力在更重要的事情上。
3. 对齐要求（Alignment Requirement）
要明白的第一件事是，在现代处理器上，你的C编译器在内存里对基本的C数据类型的存放方式是受约束的，为的是内存访问更快。
在x86或者ARM处理器上，基本的C数据类型的储存一般并不是起始于内存中的任意字节地址。而是，每种类型，除了字符型以外，都有对齐要求；字符可以起始于任何字节地址，但是2字节的短整型必须起始于一个偶数地址，4字节整型或者浮点型必须起始于被4整除的地址，以及8字节长整型或者双精度浮点型必须起始于被8整除的地址。带符号与不带符号之间没有差别。
这个的行话叫：在x86和ARM上，基本的C语言类型是自对齐（self-aligned）的。指针，无论是32位（4字节）亦或是64位（8字节）也都是自对齐的。
自对齐使得访问更快，因为它使得一条指令就完成对类型化数据的取和存操作。没有对齐的约束，反过来，代码最终可能会不得不跨越机器字的边界做两次或更多次访问。字符是特殊的情况；无论在一个单机器字中的何处，存取的花费都是一样的。那就是为什么字符型没有被建议对齐。
我说“在现代的处理器上”是因为，在一些旧的处理器上，强制让你的C程序违反对齐约束（比方说，将一个奇数的地址转换成一个整型指针，并试图使用它）不仅会使你的代码慢下来，还会造成非法指令的错误。比如在Sun的SPARC芯片上就曾经这么干。实际上，只要够决心并在处理器上设定正确（e18）的硬件标志位，你仍然可以在x86上触发此错误。
此外，自对齐不是唯一的可能的规则。历史上，一些处理器（特别是那些缺少的）有更强的限制性规则。如果你做嵌入式系统，你也许会在跌倒在这些丛林陷阱中。注意，这是有可能的。
有时你可以通过编译指示，强制让你的编译器不使用处理器正常的对齐规则，通常是#pragma pack。不要随意使用，因为它会导致产生开销更大、更慢的代码。使用我在这里描述的技术，通常你可以节省同样或者几乎同样多的内存。
#pragma pack的唯一好处是，如果你不得不将你的C语言数据分布精确匹配到某些位级别的硬件或协议的需求，比如一个内存映射的硬件端口，要求违反正常的对齐才能奏效。如果你遇到那种情况，并且你还未理解我在这里写的这一切，你会有大麻烦的，我只能祝你好运了。
4. 填充（Padding）
现在我们来看一个简单变量在内存里的分布的例子。考虑在C模块的最顶上的以下一系列的变量声明：
|
1
2
3
|
char *p;
char c;
int x;
|
如果你不知道任何关于数据对齐的事情，你可能会假设这3个变量在内存里会占据一个连续字节空间。那也就是说，在一个32位机器上，指针的4字节，之后紧接着1字节的字符型，且之后紧接着4字节的整型。在64位机器只在指针是8字节上会有所不同。
这里是实际发生的（在x86或ARM或其他任何有自对齐的处理器类型）。p的存储地址始于一个自对齐的4字节或者8字节边界，取决于机器的字长。这是指针对齐——可能是最严格的情况。
紧跟着的是c的存储地址。但是x的4字节对齐要求，在内存分布上造成了一个间隙；变成了恰似第四个变量插在其中，像这样：
|
1
2
3
4
|
char *p; /* 4 or 8 bytes */
char c; /* 1 byte */
char pad[3]; /* 3 bytes */
int x; /* 4 bytes */
|
pad[3]字符数组表示了一个事实，结构体中有3字节的无用的空间。 老派的术语称之为“slop（水坑）”。
比较如果x是2字节的短整型会发生什么：
|
1
2
3
|
char *p;
char c;
short x;
|
在那个情况下，实际的内存分布会变成这样：
|
1
2
3
4
|
char *p; /* 4 or 8 bytes */
char c; /* 1 byte */
char pad[1]; /* 1 byte */
short x; /* 2 bytes */
|
另一方面，如果x是一个在64位机上的长整型
|
1
2
3
|
char *p;
char c;
long x;
|
最终我们会得到：
|
1
2
3
4
|
char *p; /* 8 bytes */
char c; /* 1 byte
char pad[7]; /* 7 bytes */
long x; /* 8 bytes */
|
如果你已仔细看到这里，现在你可能会想到越短的变量声明先声明的情况：
|
1
2
3
|
char c;
char *p;
int x;
|
如果实际的内存分布写成这样：
|
1
2
3
4
5
|
char c;
char pad1[M];
char *p;
char pad2[N];
int x;
|
我们可以说出M和N的值吗？
首先，在这个例子中，N是零。x的地址，紧接在p之后，是保证指针对齐的，肯定比整型对齐更严格的。
M的值不太能预测。如果编译器恰巧把c映射到机器字的最后一个字节，下一个字节（p的第一部分）会成为下一个机器字的第一个字节，并且正常地指针对齐。M为零。
c更可能会被映射到机器字的第一个字节。在那个情况下，M会是以保证p指针对齐而填补的数——在32位机器上是3，64位机器上是7。
如果你想让那些变量占用更少的空间，你可以通过交换原序列中的x和c来达到效果。
|
1
2
3
|
char *p; /* 8 bytes */
long x; /* 8 bytes */
char c; /* 1 byte
|
通常，对于C程序里少数的简单变量，你可以通过调整声明顺序来压缩掉极少几个字节数，不会有显著的节约。但当用于非标量变量（nonscalar variables），尤其是结构体时，这项技术会变得更有趣。
在我们讲到非标量变量之前，让我们讲一下标量数组。在一个有自对齐类型的平台上，字符、短整型、整型、长整型、指针数组没有内部填充。每个成员会自动自对齐到上一个之后（译者注：原文 self-aligned at the end of the next one 似有误）。
在下一章，我们会看到对于结构体数组，一样的规则并不一定正确。
5. 结构体的对齐和填充
总的来说，一个结构体实例会按照它最宽的标量成员对齐。编译器这样做，把它作为最简单的方式来保证所有成员是自对齐，为了快速访问的目的。
而且，在C语言里，结构体的地址与它第一个成员的地址是相同的——没有前置填充。注意：在C++里，看上去像结构体的类可能不遵守这个规则！（遵不遵守依赖于基类和虚拟内存函数如何实现，而且因编译器而不同。）
（当你不能确定此类事情时，ANSI C提供了一个offsetof（）宏，能够用来表示出结构体成员的偏移量。）
考虑这个结构体：
|
1
2
3
4
5
|
struct foo1 {
char *p;
char c;
long x;
};
|
假设一台64位的机器，任何struct foo1的实例会按8字节对齐。其中的任何一个的内存分布看上去无疑应该像这样：
|
1
2
3
4
5
6
|
struct foo1 {
char *p; /* 8 bytes */
char c; /* 1 byte
char pad[7]; /* 7 bytes */
long x; /* 8 bytes */
};
|
它的分布就恰好就像这些类型的变量是单独声明的。但是如果我们把c放在第一个，这就不是了。
|
1
2
3
4
5
6
|
struct foo2 {
char c; /* 1 byte */
char pad[7]; /* 7 bytes */
char *p; /* 8 bytes */
long x; /* 8 bytes */
};
|
如果成员是单独的变量，c可以起始于任何字节边界，并且pad的大小会不同。但因为struct foo2有按其最宽成员进行的指针对齐，那就不可能了。现在c必须于指针对齐，之后7个字节的填充就被锁定了。
现在让我们来说说关于在结构体成员的尾随填充（trailing padding）。要解释这个，我需要介绍一个基本概念，我称之为结构体的跨步地址（stride address）。它是跟随结构体数据后的第一个地址，与结构体拥有同样对齐方式。
结构体尾随填充的通常规则是这样的：编译器的行为就如把结构体尾随填充到它的跨步地址。这条规则决定了sizeof（）的返回值。
考虑在64位的x86或ARM上的这个例子：
|
1
2
3
4
5
6
7
|
struct foo3 {
char *p; /* 8 bytes */
char c; /* 1 byte */
};
struct foo3 singleton;
struct foo3 quad[4];
|
你可能会认为，sizeof（struct foo3）应该是9，但实际上是16。跨步地址是（&p）[2]的地址。如此，在quad数组中，每个成员有尾随填充的7字节，因为每个跟随的结构体的第一个成员都要自对齐到8字节的边界上。内存分布就如结构体像这样声明：
|
1
2
3
4
5
|
struct foo3 {
char *p; /* 8 bytes */
char c; /* 1 byte */
char pad[7];
};
|
作为对照，考虑下面的例子：
|
1
2
3
4
|
struct foo4 {
short s; /* 2 bytes */
char c; /* 1 byte */
};
|
因为s只需对齐到2字节， 跨步地址就只有c后面的一个字节，struct foo4作为一个整体，只需要一个字节的尾随填充。它会像这样分布
|
1
2
3
4
5
|
struct foo4 {
short s; /* 2 bytes */
char c; /* 1 byte */
char pad[1];
};
|
并且sizeof（struct foo4）会返回4。
现在让我们考虑位域（bitfield）。它们是你能够声明比字符宽度还小的结构体域，小到1位，像这样：
|
1
2
3
4
5
6
7
|
struct foo5 {
short s;
char c;
int flip:1;
int nybble:4;
int septet:7;
};
|
关于位域需要知道的事情是，它们以字或字节级别的掩码和移位指令来实现。从编译器的观点来看，struct foo5的位域看上去像2字节，16位的字符数组里只有12位被使用。接着是填充，使得这个结构体的字节长度成为sizeof（short）的倍数即最长成员的大小。
|
1
2
3
4
5
6
7
8
9
|
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 */
};
|
这里是最后一个重要的细节：如果你的结构体含有结构体的成员，里面的结构体也需要按最长的标量对齐。假设如果你写成这样：
|
1
2
3
4
5
6
7
|
struct foo6 {
char c;
struct foo5 {
char *p;
short x;
} inner;
};
|
内部结构体的char *p成员使得外部的结构体与内部的一样成为指针对齐。在64位机器上，实际的分布是像这样的：
|
1
2
3
4
5
6
7
8
9
|
struct foo6 {
char c; /* 1 byte*/
char pad1[7]; /* 7 bytes */
struct foo6_inner {
char *p; /* 8 bytes */
short x; /* 2 bytes */
char pad2[6]; /* 6 bytes */
} inner;
};
|
这个结构体给了我们一个启示，重新封装结构体可能节省空间。24个字节中，有13个字节是用作填充的。超过50%的无用空间！
6. 结构体重排序（reordering）
现在你知道如何以及为何编译器要插入填充，在你的结构体之中或者之后，我们要考察你可以做些什么来挤掉这些“水坑”。这就是结构体封装的艺术。
第一件需要注意的事情是，“水坑”仅发生于两个地方。一个是大数据类型（有更严格的对齐要求）的存储区域紧跟在一个较小的数据类型的存储区域之后。另一个是结构体自然结束于它的跨步地址之前，需要填充，以使下一个实例可以正确对齐。
消除“水坑”的最简单的方法是按对齐的降序来对结构体成员重排序。就是说：所有指针对齐的子域在前面，因为在64位的机器上，它们会有8字节。接下来是4字节的整型；然后是2字节的短整型；然后是字符域。
因此，举个例子，考虑这个简单的链表结构体：
|
1
2
3
4
5
|
struct foo7 {
char c;
struct foo7 *p;
short x;
};
|
显现出隐含的“水坑”，这样：
|
1
2
3
4
5
6
7
|
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个字节。如果我们按大小重新排序，我们得到：
|
1
2
3
4
5
|
struct foo8 {
struct foo8 *p;
short x;
char c;
};
|
考虑到自对齐，我们看到没有数据域需要填充。这是因为一个较长的、有较严格对齐的域的跨步地址，对于较短的、较不严格对齐的域来说，总是合法对齐的起始地址。所有重封装的结构体实际上需要的只是尾随填充：
|
1
2
3
4
5
6
|
struct foo8 {
struct foo8 *p; /* 8 bytes */
short x; /* 2 bytes */
char c; /* 1 byte */
char pad[5]; /* 5 bytes */
};
|
我们重封装的转变把大小降到了16字节。这可能看上去没什么，但是假设你有一个200k的这样的链表呢？节省的空间累积起来就不小了。
注意重排序并不能保证节省空间。把这个技巧运用到早先的例子，struct foo6，我们得到：
|
1
2
3
4
5
6
7
|
struct foo9 {
struct foo9_inner {
char *p; /* 8 bytes */
int x; /* 4 bytes */
} inner;
char c; /* 1 byte*/
};
|
把填充写出来，就是这样
|
1
2
3
4
5
6
7
8
9
|
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字节，因为c不能转换到内部结构体成员的尾随填充。为了获得节省空间的好处，你需要重新设计你的数据结构。
自从发布了这篇指南的第一版，我就被问到了，如果通过重排序来得到最少的“水坑”是如此简单，为什么C编译器不自动完成呢？答案是：C语言最初是被设计用来写操作系统和其他接近硬件的语言。自动重排序会妨碍到系统程序员规划结构体，精确匹配字节和内存映射设备控制块的位级分布的能力。
7. 难以处理的标量的情况
使用枚举类型而不是#defines是个好主意，因为符号调试器可以用那些符号并且可以显示它们，而不是未处理的整数。但是，尽管枚举要保证兼容整型类型，C标准没有明确规定哪些潜在的整型类型会被使用。
注意，当重新封装你的结构体时，虽然枚举类型变量通常是整型，但它依赖于编译器；它们可能是短整型、长整型、甚至是默认的字符型。你的编译器可能有一个编译指示或者命令行选项来强制规定大小。
long double类型也是个相似的麻烦点。有的C平台以80位实现，有的是128， 还有的80位的平台填充到96或128位。
在这两种情况下，最好用sizeof（）来检查存储大小。
最后，在x86下，Linux的双精度类型有时是一个自对齐规则的特例；一个8字节的双精度数据在一个结构体内可以只要求4字节对齐，虽然单独的双精度变量要求8字节的自对齐。这依赖于编译器及其选项。
8. 可读性和缓存局部性
尽管按大小重排序是消除“水坑”的最简单的方式，但它不是必定正确的。还有两个问题：可读性和缓存局部性。
程序不只是与计算机的交流，还是与其他人的交流。代码可读性是重要的，即便（或者尤其是！）交流的另一方不只是未来的你。
笨拙的、机械的结构体重排序会损害可读性。可能的话，最好重排域，使得语义相关的数据段紧紧相连，能形成连贯的组群。理想情况下，你的结构体设计应该传达到你的程序。
当你的程序经常访问一个结构体，或者结构体的一部分，如果访问常命中缓存行（当被告知去读取任何一个块里单个地址时，你的处理器读取的整一块内存）有助于提高性能。在64位x86机上一条缓存行为64字节，始于一个自对齐的地址；在其他平台上经常是32字节。
你应该做的事情是保持可读性——把相关的和同时访问的数据组合到毗邻的区域——这也会提高缓存行的局部性。这都是用代码的数据访问模式的意识，聪明地重排序的原因。
如果你的代码有多线程并发访问一个结构体，就会有第三个问题：缓存行反弹（cache line bouncing）。为了减少代价高昂的总线通信，你应该组织你的数据，使得在紧凑的循环中，从一条缓存行中读取，而在另一条缓存行中写。
是的，这与之前关于把相关数据组成同样大小的缓存行块的指南有些矛盾。多线程是困难的。缓存行反弹以及其它的多线程优化问题是十分高级的话题，需要整篇关于它们的教程。这里我能做的最好的就就是让你意识到这些问题的存在。
9. 其它封装技术
当重排序与其他技术结合让你的结构体瘦身时效果最好。如果你在一个结构体里有若干布尔型标志，举个例子，可以考虑将它们减小到1位的位域，并且将它们封装到结构体里的一个本会成为“水坑”的地方。
为此，你会碰到些许访问时间上的不利——但是如果它把工作区挤压得足够小，这些不利会被避免缓存不命中的得益所掩盖。
更普遍的，寻找缩小数据域大小的方式。比如在cvs-fast-export里，我用的一项压缩技术里用到了在1982年之前RCS和CVS代码库还不存在的知识。我把64位的Unix time_t（1970年作为起始0日期）减少到32位的、从1982-01-01T00:00:00开始的时间偏移量；这会覆盖2118年前的日期。（注意：如果你要玩这样的花招，每当你要设定字段，你都要做边界检查以防讨厌的错误！）
每一个这样被缩小的域不仅减少了你结构体显在的大小，还会消除“水坑”，且/或创建额外的机会来得到域重排序的好处。这些效果的良性叠加不难得到。
最有风险的封装形式是使用联合体。如果你知道你结构体中特定的域永远不会被用于与其他特定域的组合，考虑使用联合体使得它们共享存储空间。但你要额外小心，并且用回归测试来验证你的工作，因为如果你的生命周期分析即使有轻微差错，你会得到各种程序漏洞，从程序崩溃到（更糟糕的）不易发觉的数据损坏。
10. 工具
C语言编译器有个-Wpadded选项，能使它产生关于对齐空洞和填充的消息。
虽然我自己还没用过，但是一些反馈者称赞了一个叫pahole的程序。这个工具与编译器合作，产生关于你的结构体的报告，记述了填充、对齐及缓存行边界。
11. 证明及例外
你可以下载一个小程序的代码，此代码用来展示了上述标量和结构体大小的论断。就是。
如果你浏览足够多的编译器、选项和不常见的硬件的奇怪组合，你会发现针对我讲述的一些规则的特例。如果你回到越旧的处理器设计，就会越常见。
比知道这些规则更进一步，是知道如何以及何时这些规则会被打破。在我学习它们的那些年（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
初版