失传的 C 结构体打包技艺（转）

转自： https://fishc.com.cn/forum.php?mod=viewthread&tid=83418&extra=page%3D2%26filter%3Dtypeid%26typeid%3D571

作者：Eric S. Raymond 原文链接：http://www.catb.org/esr/structure-packing

谁应阅读本文

如果你在内存容量受限的嵌入式系统中写程序，或者编写操作系统内核代码，就有必要了解这项技术。如果数据集巨大，应用时常逼近内存极限，这项技术会有所帮助。倘若你非常非常关心如何最大限度地减少处理器缓存段（cache-line）未命中情况的发生，这项技术也有所裨益。

2013 年底，我大量应用了一项 C 语言优化技术，这项技术是我早在二十余年前就已掌握的，但彼时之后，鲜有使用。

通过精心调整结构成体员的顺序，可以在这种情况下大幅减少内存占用。其效果显著——在上述案例中，可以减少 40% 的内存空间。程序应用于更大的软件仓库，也不会因内存耗尽而崩溃。

事出有因。计算机科学课程（正确地）引导人们远离微观优化，转而寻求更理想的算法。计算成本一路走低，令压榨内存的必要性变得越来越低。旧日里，黑客们通过在陌生的硬件架构中跌跌撞撞学习 —— 如今已不多见。

首先需要了解的是，对于现代处理器，C 编译器在内存中放置基本 C 数据类型的方式受到约束，以令内存的访问速度更快。

用行话来说，x86 和 ARM 上的基本 C 类型是“自对齐（self-aligned）”的。关于指针，无论 32 位（4 字节）还是 64 位（8 字节）也都是自对齐的。

我提到“现代处理器”，是因为有些老平台强迫 C 程序违反对齐规则（例如，为 int 指针分配一个奇怪的地址并试图使用它），不仅令速度减慢，还会导致非法指令错误。例如 Sun SPARC 芯片就有这种问题。事实上，如果你下定决心，并恰当地在处理器中设置标志位（e18），在 x86 平台上，也能引发这种错误。

你还可以通过 pragma 指令（通常为 ）强迫编译器不采用处理器惯用的对齐规则。但请别随意运用这种方式，因为它强制生成开销更大、速度更慢的代码。通常，采用我在下文介绍的方式，可以节省相同或相近的内存。 #pragma pack

我们来看一个关于变量在内存中分布的简单案例。思考形式如下的一系列变量声明，它们处在一个 C 模块的顶层。

然而实际情况（在 x86、ARM 或其他采用自对齐类型的平台上）如下。存储 p 需要自对齐的 4 或 8 字节空间，这取决于机器字的大小。这是指针对齐 —— 极其严格。

1
2
3
4
5
6

   
   
   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] 意味着在这个结构体中，有 3 个字节的空间被浪费掉了。老派术语将其称之为“废液（slop）”。

1
2
3

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

在这个例子中，实际分布将会是：

1
2
3

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

我们将得到：

1
2
3

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

假如实际内存分布可以写成下面这样：

首先，在此例中，N 将为 0，x 的地址紧随 p 之后，能确保是与指针对齐的，因为指针的对齐要求总比 int 严格。

不过更有可能的情况是，c 将被映射为机器字的首字节。于是乎 M 将会用于填充，以使 p 指针对齐——32 位系统中为 3 字节，64 位系统中为 7 字节。

倘若你希望这些变量占用的空间更少，那么可以交换 x 与 c 的次序。

在讲述这部分内容前，我们先对标量数组做个说明。在具有自对齐类型的平台上，char、short、int、long 和指针数组都没有内部填充，每个成员都与下一个成员自动对齐。

通常情况下，结构体实例以其最宽的标量成员为基准进行对齐。编译器之所以如此，是因为此乃确保所有成员自对齐，实现快速访问最简便的方法。

假如你对此有疑惑，ANSI C 提供了一个 宏，可用于读取结构体成员位移。

1
2
3
4
5

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

假定处在 64 位系统中，任何 struct fool 的实例都采用8字节对齐。不出所料，其内存分布将会像下面这样：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  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 需要指针对齐，接下来填充的7个字节被锁定了。

结构体尾填充的通用法则是：编译器将会对结构体进行尾填充，直至它的跨步地址。这条法则决定了 sizeof() 的返回值。

1
2
3
4
5
6
7

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

复制代码

你以为 的值是 9，但实际是 16。它的跨步地址是 。于是，在 quad 数组中，每个成员都有 7 字节的尾填充，因为下个结构体的首个成员需要在 ８ 字节边界上对齐。内存分布就好像这个结构是这样声明的：

1. 1 2 3 4

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

因为 s 只需要 2 字节对齐，跨步地址仅在 c 的 1 字节之后，整个 struct foo4 也只需要 1 字节的尾填充。形式如下：

的返回值将为 4。

1. 1 2 3 4 5 6 7

   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 位。为了使结构体的长度是其最宽成员长度 的整数倍，接下来进行了填充。

1. 1 2 3 4 5 6 7 8 9

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

内层结构体成员 char *p 强迫外层结构体与内层结构体指针对齐一致。在 64 位系统中，实际的内存分布将类似这样：

理解了编译器在结构体中间和尾部插入填充的原因与方式后，我们来看看如何榨出这些废液。此即结构体打包的技艺。

消除废液最简单的方式，是按对齐值递减重新对结构体成员排序。即让所有指针对齐成员排在最前面，因为在 64 位系统中它们占用 8 字节；然后是 4 字节的 int；再然后是 2 字节的 short，最后是字符。

1
2
3
4
5

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

将隐含的废液写明，形式如下：

1
2
3
4
5
6
7

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

考虑到自对齐，我们看到所有数据域之间都不需填充。因为有较严对齐要求（更长）成员的跨步地址对不太严对齐要求的（更短）成员来说，总是合法的对齐地址。重打包过的结构体只需要尾填充：

注意，重新打包不能确保在所有情况下都能节省空间。将这项技术应用于更靠前 struct foo6 的那个例子，我们得到：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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 无法作为内层结构体的尾填充。要想节省空间，你需要得新设计数据结构。 棘手的标量案例

#define 请当心，重打包结构体时，枚举型变量通常是 int，这与编译器相关；但也可能是 short、long、甚至默认为 char。编译器可能会有 预处理指令或命令行选项指定枚举的尺寸。

以上两种情况，最好用 来检查存储尺寸。

尽管按尺寸重排是最简单的消除废液的方式，却不一定是正确的方式。还有两个问题需要考量：可读性与缓存局部性。

笨拙地、机械地重排结构体可能有损可读性。倘若有可能，最好这样重排成员：将语义相关的数据放在一起，形成连贯的组。最理想的情况是，结构体的设计应与程序的设计相通。

为保持可读性所做的工作（将相关和同时访问的数据放在临近位置）也会提高缓存段的局部性。这些都是需要明智地重排，并对数据的存取模式了然于心的原因。

是的，某些时候，这种做法与前文将相关数据放入与缓存段长度相同块的做法矛盾。多线程的确是个难题。缓存段弹跳和其他多线程优化问题是很高级的话题，值得单独为它们写份指导。这里我所能做的，只是让你了解有这些问题存在。 其他打包技术

你可能会有一点儿存取时间的损失，但只要将工作集合压缩得足够小，那点损失可以靠避免缓存未命中补偿。

这不仅减小了结构体的可见尺寸，还可以消除废液和/或创造额外的机会来进行重新排序。这种良性串连的效果不难被触发。

clang 编译器有个 Wpadded 选项，可以生成有关对齐和填充的信息。

读者可以下载一段程序源代码 ，验证上文有关标量和结构体尺寸的结论。

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