迷失的结构包装艺术

本页介绍了一种减少C类结构编译语言中程序的内存占用的技术--手动重新打包这些声明以减小大小。要阅读它，您需要具备C编程语言的基本知识。

如果您打算为内存受限的嵌入式系统或操作系统内核编写代码，则需要了解此技术。如果您使用的应用程序数据集太大，以至于您的程序经常达到内存限制，这一点很有用。在任何应用程序中，您都非常非常关心如何优化内存带宽的使用，并最大限度地减少高速缓存线未命中，这是一件很好的事情。

最后，了解这项技术是通向其他深奥话题的大门。只有掌握了这些规则，你才算得上是一名高级C程序员。除非你能自己写这篇文档，并能明智地批评它，否则你不是C语言大师。

本文档起源于标题中的C#34；C#34；，但其中几乎所有内容都适用于C++。这里讨论的许多技术也适用于Go语言，并且应该推广到任何具有类似C的结构的编译语言。在结尾处有一个讨论C++、Go、Rust、Java、Swiftm和C#的笔记。

这个网页之所以存在，是因为在2013年末，我发现自己在大量使用一种优化技术，这是我在20多年前学到的，此后就不太用了。

我需要减少一个使用数千个(有时是数十万个)C结构实例的程序的内存占用。该程序是CVS快速输出的，问题是它在大型存储库中因内存不足错误而死亡。

在这种情况下，有一些方法可以通过仔细地重新排列结构成员的顺序来显著减少内存使用量。这可以带来显著的收益--在我的例子中，我能够将工作集大小减少约40%，使程序能够处理更大的存储库而不会死。

但是，当我工作，思考我在做什么的时候，我开始意识到，我所使用的技术在后来的日子里已经被遗忘了一半以上。一些网络研究证实，程序员似乎不再谈论它了，至少在搜索引擎可以看到他们的地方不再谈论它。有几个维基百科谈到了这个话题，但我发现没有人能全面地报道这个问题。

事实上，这样做的原因并不愚蠢。计算机科学课程(理所当然)引导人们从微观优化转向寻找更好的算法。机器资源价格的暴跌降低了挤压内存使用的必要性。在过去，黑客学习如何做到这一点的方法是用鼻子撞上奇怪的硬件架构--这在现在不那么常见了。

但这项技术在重要情况下仍然有价值，只要记忆力有限就行。本文档旨在让程序员不必重新发现这项技术，这样他们就可以将精力集中在更重要的事情上。

首先要了解的是，在现代处理器上，为了提高内存访问速度，编译器在内存中布局基本数据类型的方式是有限制的。我们的例子是用C语言编写的，但是任何编译语言都会在相同的约束下生成代码。

X86或ARM处理器上基本C数据类型的存储通常不会从内存中的任意字节地址开始。相反，除char之外的每种类型都有对齐要求；chars可以从任何字节地址开始，但2字节短码必须从偶数地址开始，4字节整型或浮点型必须从可被4整除的地址开始，8字节长或双精度必须从可被8整除的地址开始。有符号或无符号没有区别。

这方面的行话是，x86和ARM上的基本C类型是自对齐的。指针，无论是32位(4字节)还是64位(8字节)也是自对齐的。

自对齐使访问速度更快，因为它便于生成类型数据的单指令读取和放置。另一方面，如果没有对齐约束，代码最终可能不得不跨机器字边界进行两次或更多访问。字符是一个特例；它们在单个机器字内的任何位置都同样昂贵。这就是为什么他们没有参考的序列。

我之所以说是在现代处理器上，是因为在一些较老的处理器上，强迫你的C程序违反对齐规则(比如，把一个奇数地址投射到一个整型指针中并试图使用它)不仅会减慢你的代码速度，还会导致一个非法的指令错误。例如，这就是Sun SPARC芯片上的行为。事实上，在处理器上设置了足够的确定和正确的(E18)硬件标志后，您仍然可以在x86上触发此操作。

此外，自我调整也不是唯一可能的规则。从历史上看，一些加工者(特别是那些缺少桶装移位器的加工者)有更多的限制。如果你使用嵌入式系统，你可能会被潜伏在灌木丛中的其中一个绊倒。请注意，这是可能的。

摩托罗拉68020及其后继者是一个奇怪而又具有说服力的例外。它们是面向字的32位机器--也就是说，快速访问的底层粒度是16位。即使第一个成员是32位标量，编译器也可以在不影响速度的情况下在16位边界上启动structs。因此，只有字节长度为奇数的字符字段才会导致填充。

从2014年初第一次编写到2016年底，这一节以关于奇怪架构的告诫结束。在此期间，我从使用NTP参考实现的源代码中学到了一些不那么令人放心的东西。它通过将数据包从线路上直接读入内存来执行数据包分析，其余代码将其视为结构，这依赖于最小自对齐填充的假设-或者在像690x0这样的奇怪情况下的零填充。

有趣的消息是，几十年来，NTP显然一直在广泛的硬件、操作系统和编译器(不仅包括Unix，也包括Windows变体)中解决这一问题。这表明，除了自对齐之外，具有填充规则的平台要么是不存在的，要么是局限于特定的利基市场，它们既不是NTP服务器，也不是客户端。

现在我们来看一个简单的内存中变量布局的例子。考虑C模块顶层中的以下一系列变量声明：

如果您对数据对齐一无所知，您可能会认为这三个变量会在内存中占用连续的字节范围。也就是说，在32位机器上，4字节的指针紧跟1字节的char，紧随其后的是4字节的int。而64位机器的不同之处只在于指针是8个字节。

事实上，隐藏的假设，即静态变量的分配顺序就是它们的源顺序，并不一定是有效的；C标准并没有强制要求这样做。我将忽略这个细节，因为(A)隐藏的假设通常是正确的，以及(B)讨论结构外部的填充和包装的实际目的是为了让你为结构内部发生的事情做好准备。

以下是实际发生的情况(在x86或ARM或任何其他自对齐类型的设备上)。P的存储开始于自对齐的4字节或8字节边界，具体取决于机器字的大小。这是指针对齐，这是最严格的。

C的存储紧随其后。但是，x的4字节对齐要求会在布局中产生间隙；假设有第四个中间变量，如下所示：

Char*p；/*4或8字节*/char c；/*1字节*/char pad[3]；/*3字节*/int x；/*4字节*/。

Pad[3]字符数组表示结构中有三个字节的浪费空间。这是一个老式的术语，叫slop&34；slop；。填充比特的值是未定义的；具体而言，不能保证它们将被置零。

Char*p；/*4或8字节*/char c；/*1字节*/char pad[1]；/*1字节*/短x；/*2字节*/。

Char*p；/*8字节*/char c；/*1 bytehar pad[7]；/*7字节*/long x；/*8字节*/。

如果您一直在仔细研究，您现在可能会想知道较短的变量声明首先出现的情况是什么：

首先，在这种情况下，N将为零。紧跟在p之后的x的地址被保证是指针对齐的，其严格程度永远不亚于整型对齐。

M的值更难预测。如果编译器碰巧将c映射到机器字的最后一个字节，则下一个字节(p的第一个)将是下一个字节的第一个字节，并且指针正确对齐。M将为零。

更有可能的是，c将被映射到机器字的第一个字节。在这种情况下，M将是确保p在32位机器上具有指针对齐所需的任何填充，在64位机器上为7。

中间案件是可能的。M可以是0到7之间的任何值(32位上的0到3)，因为字符可以从机器字中的任何字节边界开始。

如果你想让这些变量占用更少的空间，你可以通过在原始序列中用x和c互换来达到这个效果。

Char*p；/*8字节*/long x；/*8字节*/char c；/*1字节。

通常，对于C程序中数量较少的标量变量，通过更改声明顺序来节省几个字节并不足以使您的工作变得重要。当应用于非标量变量时，这项技术变得更加有趣--尤其是结构。

在我们讨论这些之前，让我们先来处理一下标量数组。在具有自对齐类型的平台上，字符/短/整型/长/指针数组没有内部填充；每个成员在下一个成员的末尾自动自对齐。

所有这些规则和示例都映射到go结构，并映射到只有语法变化的带有repr(C)属性的Ruststructs。

在下一节中，我们将看到结构数组不一定是这样的。

通常，结构实例将具有其最宽标量成员的对齐方式。为了确保所有成员都是自对齐的，以便快速访问，编译器这样做是最简单的方法。

此外，在C中(以及GO和Rust)，结构的地址与其第一个成员的地址相同-没有前导填充。INC++这可能不是真的；请参见第14节“其他语言”。

(当您对这类事情有疑问时，ANSI C提供了一个offsetof()宏，可用于读取结构成员偏移量。)。

假设是一台64位机器，struct foo1的任何实例都将具有8字节对齐。其中一个的内存布局看起来令人惊讶，如下所示：

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可以从任何字节边界开始，填充的大小可能会有所不同。因为struct foo2具有其最宽成员的指针对齐，所以这不再可能。现在c必须与指针对齐，并且随后7个字节的填充被锁定。

现在让我们来讨论一下结构上的尾部填充。为了解释这一点，我需要介绍一个基本概念，我将其称为结构的横幅地址。它是结构数据之后的第一个地址，与结构具有相同的对齐方式。

尾随结构填充的一般规则是：编译器的行为就像结构有尾随填充到它的跨步地址一样。此规则控制sizeof()将返回的大小。

Struct foo3{char*p；/*8 bytes*/char c；/*1 byte*/}；struct foo3 singleton；struct foo3 quad[4]；

您可能认为sizeof(Struct Foo3)应该是9，但实际上是16。跨度地址是(&；p)[2]。因此，在四元组中，每个成员都有7个字节的尾部填充，因为每个后续结构的第一个成员希望在8字节边界上自对齐。内存布局看起来就像是这样描述的结构：

Struct foo3{char*p；/*8 bytes*/char c；/*1 byte*/char pad[7]；}；

Struct foo4{Short s；/*2 bytes*/char c；/*1 byte*/}；

因为s只需要两个字节对齐，所以跨距地址只在c之后一个字节，而struct foo4整体上只需要一个字节的尾部填充。它的布局是这样的：

Struct foo4{Short s；/*2 bytes*/char c；/*1 byte*/char pad[1]；}；

最后一个重要细节是：如果您的结构有结构成员，内部结构也希望具有最长标量的对齐方式。假设你这样写：

内部结构中的char*p成员强制外部结构与内部结构指针对齐。在64位计算机上的实际布局如下所示：

Struct foo5{char c；/*1 byte*/char pad1[7]；/*7字节*/struct foo5_ner{char*p；/*8字节*/Short x；/*2字节*/char pad2[6]；/*6字节*/}内部；}；

这种结构给我们提供了一个线索，那就是重新打包结构可能带来的节省。在24个字节中，有13个字节是填充的，这是超过50%的浪费空间！

现在让我们考虑C位域。它们允许您声明小于字符宽度(最小为1位)的结构字段，如下所示：

关于位域，需要知道的是，它们是通过字级和字节级掩码和旋转指令在机器字上操作实现的，不能跨越字边界。C99保证位域将被尽可能紧密地打包，前提是它们不会跨越存储单元边界(6.7.2.1#10)。

在C11(6.7.2.1p11)和C++14([class.bit]p1)中放宽了这一限制；这些修订实际上并不要求struct foo9是64位而不是32位；一个位域可以跨越多个分配单元，而不是开始一个新的分配单元。这是由实现决定的；GCC把它留给了ABI，对于x64，ABI确实阻止它们共享一个分配单元。

假设我们在一台32位机器上，C99规则暗示布局可能如下所示：

Struct foo6{短s；/*2字节*/char c；/*1字节*/int翻转：1；/*共1位*/int翻转：4；/*共5位*/int PAD1：3；/*填充到8位边界*/int间隔：7；/*7位*/int pad2：25；/*填充到32位*/}；

但这并不是唯一的可能性，因为C标准并没有指定从低到高分配比特。因此，布局可能如下所示：

Struct foo6{短s；/*2字节*/char c；/*1字节*/int PAD1：3；/*填充到8位边界*/int flip：1；/*总计1位*/int nyeble：4；/*总共5位*/int pad2：25；/*填充到32位*/int间隔：7；/*7位*/}；

还要注意的是，与正常结构填充一样，填充位不能保证为零；C99提到了这一点。

注意，位字段的基本类型被解释为符号，但不一定是大小。是否支持"；Short Flip：1"；或"；Long Flip：1"；以及这些基本类型是否会更改字段所在存储单元的大小取决于实现者。

谨慎行事，如果您有-Wppad(例如，在clang下)，请检查它。外来硬件上的编译器可能会以令人惊讶的方式解释C99规则；较老的编译器可能不会完全遵循这些规则。

位域不能跨越机器字边界的限制意味着，正如您所预期的那样，下面的前两个结构打包成一个32位字和两个32位字，而第三个结构(Struct Foo9)在C99中占据了三个32位字，其中最后一个只使用了一个位。

Struct foo7{int bigfield：31；/*32位字1开始*/int littlefield：1；}；struct foo8{int bigfield1：31；/*32位字1开始/*int littlefield1：1；int bigfield2：31；/*32位字2开始*/int littlefield2：1；}；struct foo9{int bigfield1：31；/*32-。

同样，C11和C++14可能会将foo9包装得更紧，但指望这一点可能是不明智的。

另一方面，如果机器有的话，struct foo8可以放入一个64位的单词中。

既然您已经了解了编译器如何以及为什么在您的结构中和之后插入填充，我们将研究您可以做些什么来挤出斜率。这就是结构打包的艺术。

首先要注意的是，Slop只发生在两个地方。一个是绑定到较大数据类型(具有更严格的对齐要求)的存储跟随绑定到较小数据类型的存储。另一个是结构在跨步地址之前自然结束的位置，需要填充，这样下一个结构才能正确对齐。

消除倾斜的最简单方法是通过减少对齐来重新排序结构成员。也就是说：让所有指针对齐的子字段排在第一位，因为在64位机器上，它们将是8字节。然后是4字节整型，然后是2字节短型，然后是字符字段。

Struct foo10{char c；/*1个字节*/char pad1[7]；/*7个字节*/struct foo10*p；/*8个字节*/Short x；/*2个字节*/char pad2[6]；/*6个字节*/}；

考虑到自对齐，我们看到没有一个数据字段需要填充。这是因为具有较严格对准的(较长)场的步长地址始终是具有较低要求的(较短)场的有效对准的起始地址。所有重新打包的结构实际上需要的是尾部填充：

Struct foo11{struct foo11*p；/*8字节*/Short x；/*2字节*/char c；/*1字节*/char pad[5]；/*5字节*/}；

我们的重新打包转换将大小从24字节减少到16字节。这可能看起来不是很多，但是假设你有一个包含200K个这样的链接列表？节省的速度很快--特别是在内存受限的嵌入式系统上，或者是在必须驻留的操作系统内核的核心部分。

请注意，重新排序并不能保证节省成本。将此技术应用于前面的示例struct foo5，我们得到以下结果：

Struct foo12{struct foo5{char*p；/*8字节*/Short x；/*2字节*/}内部；char c；/*1字节*/}；

Struct foo12{struct foo5{char*p；/*8字节*/Short x；/*2字节*/char pad[6]；/*6字节*/}内部；char c；/*1字节*/char pad[7]；/*7字节*/}；

它仍然是24个字节，因为c不能回到内部结构的拖尾填充中。要获得这一收益，您需要重新设计您的数据结构。

奇怪的是，通过增加大小来严格排序结构字段也可以最大限度地减少填充。您可以按以下任何顺序最小化填充：(A)任何一种大小的所有字段都在一个连续的跨度内(完全消除了它们之间的填充)，以及(B)这些跨度之间的间距是这样的：两边的大小彼此相差尽可能少的倍增步长。通常情况下，这意味着一侧没有任何填充物。

Struct foo13{int32_t i；int32_t i2；char octet[8]；int32_t i3；int32_t i4；int64_t l；int32_t i5；int32_t i6；}；

此结构在自对齐规则下具有零填充。找出原因是一种有益的锻炼，可以加深你的理解。

自从发布了本指南的第一个版本以来，我一直被问到，如果重新排序以获得最小的斜率是如此简单，为什么C编译器不自动执行这一操作。答案是：C语言最初是为编写操作系统和其他接近硬件的代码而设计的。自动重新排序会干扰系统程序员布局与内存映射设备控制块的字节和位级布局完全匹配的结构的能力。

Go遵循C哲学，不会对字段进行重新排序。Ruust做出了相反的选择；默认情况下，它的编译器可能会对结构字段进行重新排序。

使用枚举类型而不是#定义是一个好主意，如果只是因为符号调试器有这些符号可用，并且可以显示它们而不是原始整数。但是，虽然枚举被保证与整型兼容，但C标准并没有指定哪种类型的枚举与整型兼容。

.