。接下来是4字节的整型;然后是2字节的短整型;然后是字符域。
因此,举个例子,考虑这个简单的链表结构体:
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个字节。如果我们按大小重新排序,我们得到:
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字节。这可能看上去没什么,但是假设你有一个200k的这样的链表呢?节省的空间累积起来就不小了。
注意重排序并不能保证节省空间。把这个技巧运用到早先的例子,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字节,因为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. 证明及例外
你可以下载一个小程序的代码,此代码用来展示了上述标量和结构体大小的论断。就是packtest.c。
如果你浏览足够多的编译器、选项和不常见的硬件的奇怪组合,你会发现针对我讲述的一些规则的特例。如果你回到越旧的处理器设计,就会越常见。
比知道这些规则