数据结构对齐

总览

数据结构对齐是指在计算机内存中排列和访问数据的方式。它包含三个独立但相关的问题：数据对齐（data alignment），数据结构填充（ data structure padding）和打包（packing）。

当数据自然对齐时，现代计算机硬件中的CPU最有效地执行对内存的读写操作，这通常意味着数据的内存地址是数据大小的倍数。

读/写总是从word_size的倍数的地址开始的。
**读/写的长度总是word_size的倍数。**例如，在32位体系结构中，如果数据存储在4个连续字节中并且第一个字节位于4字节边界上，则可以对齐数据。

数据对齐是根据元素的自然对齐来进行的。为了确保自然对齐，可能需要在结构元素之间或结构的最后一个元素之后插入一些填充。例如，在32位机器上，一个包含16位值和32位值的数据结构可以在16位值和32位值之间有16位的填充，以使32位值在32位边界对齐。或者，我们可以将结构打包（packing），省略填充，这可能会导致较慢的访问速度，但只使用了四分之三的内存。

尽管数据结构对齐是所有现代计算机的一个基本问题，但许多计算机语言和计算机语言实现都会自动处理数据对齐。Fortran、Ada、 PL/I、Pascal、某些C和C++实现、D、Rust、C#和汇编语言，允许至少在部分范围内控制数据结构填充，这在某些特殊情况下可能是有用的。

数据对齐（alignment）

当一个内存地址a是n的倍数（其中 n = 2 k n=2^k n=2k）时，可以说是n字节对齐的。在这种情况下，一个字节是最小的内存访问单位，即每个内存地址指定一个不同的字节。一个n字节对齐地址，再用二进制表示时将至少有 l o g 2 ( n ) log_2(n) log2(n)个最低有效零。

而b位对齐，实际上就是另一种说法，指 b / 8 b/8 b/8字节对齐的地址（例如，64位对齐的是8字节对齐的）。

当被访问的数据长度为n个字节，并且基准地址是n个字节对齐的时候，就可以说一个内存访问是对齐的。当一个内存访问没有被对齐时，它被称为错位（misaligned）。请注意，根据定义，字节内存访问总是被对齐的。

如果一个内存指针指的是n字节长的原始数据，并且只允许它包含n字节对齐的地址，那么这个指针就被称为对齐的。否则，它就被称作不对齐的（unaligned）。当（且仅当）集合中的每个原始数据是对齐的，指向数据集合（数据结构或数组）的内存指针才是对齐的。

请注意，上面的定义假定每个原始数据的长度是 2 k 2^k 2k。如果不是这种情况（如x86的80位浮点），上下文会影响数据是否被认为是对齐的条件。

数据结构可以存储在堆栈中，在栈中的静态尺寸被称为有界（bounded），在堆中的动态尺寸被称为无界（unbounded）。

存在的问题

CPU一次访问内存一个内存字。只要内存字大小至少与计算机支持的最大基本数据类型一样大，对齐访问将始终访问一个内存字。然而，对于未对齐的数据访问可能就不是这样了。

如果一个数据的高位和低位字节不在同一个内存字中，计算机必须将该数据的访问分成多个内存访问。这需要复杂的电路来生成内存访问并协调它们。为了处理内存字位于不同的内存页的情况，处理器必须在执行指令之前验证两个内存页是否都存在，或者在任何内存访问过程中能够处理TLB缺失或页面故障。

一些处理器设计有意避免引入这种复杂性，在不对齐的内存访问时会产生替代行为。例如，在ARMv6 ISA之前的一些ARM架构实现需要所有多字节的加载和存储指令强制对齐内存访问。根据执行哪个具体的指令，尝试未对齐访问的结果可能是将违规地址的最低有效位舍入为对齐访问（有时附加其他警告），或者抛出MMU异常（如果有MMU硬件），或者无声地产生其他潜在不可预测的结果。ARMv6和更新的架构在许多情况下支持不对齐访问，但并非全部情况。

当单个内存字被访问时，操作是原子性的，即整个内存字被一次性读或写，其他设备必须等到读或写操作完成后才能访问它。这对于对多个内存字的非对齐访问来说可能不是正确的，例如，第一个字由一个设备读取，然后另一设备写入两个字，然后再由第一设备读取第二个字。这种情况读取的值既不是原始值也不是更新的值。虽然这种故障很少，但却很难识别。

数据结构填充（padding）

尽管编译器（或解释器）通常将单个数据项分配到对齐的边界上，但数据结构通常具有不同对齐要求的成员。为了保持适当的对齐，翻译器通常插入额外的未命名数据成员，以便每个成员都得到适当的对齐。此外，整个数据结构可能会用最后一个未命名成员填充。这使得结构数组的每个成员都可以得到适当的对齐。

仅当结构成员后面紧跟具有较大对齐要求的成员或位于结构末尾时，才插入填充。通过改变结构中成员的顺序，可以改变维护对齐所需的填充量。例如，如果成员按降序排列要求进行排序，则需要最少的填充。所需的最少填充量始终小于结构中最大的对齐要求。计算所需最大填充量更为复杂，但始终小于所有成员对齐要求之和减去最不对齐的一半结构成员对齐要求之和的两倍。

尽管 C 和 C++ 不允许编译器重新排序结构成员以节省空间，但其他语言可能允许。大多数 C 和 C++ 编译器也可以指定将结构体成员“打包”到特定的对齐级别，例如**“pack(2)”表示将大于一个字节的数据成员对齐到两个字节边界**，使得任何填充成员最多为一个字节长。同样，在 PL/I 中，可以声明结构体为 UNALIGNED 以除去除位串外的所有填充。

这种 "打包 "结构的**一个用途是节约内存**。例如，一个包含一个字节（如char）和一个四字节整数（如uint32_t）的结构将需要三个额外的字节填充。一个由此类结构组成的大数组如果被打包，将减少37.5%的内存，尽管访问每个结构可能需要更长时间。这种妥协可以被认为是一种空间-时间权衡的形式。

尽管使用 "打包 "结构最常被用来节省内存空间，但它也可以被用来**格式化数据结构**，以便使用标准协议进行传输。然而，在这种用法中，还必须注意确保结构成员的值是以协议要求的字节数（通常是网络字节数）来存储的，这可能与主机本身使用的字节数不同。

计算填充

下面的公式提供了对准数据结构的开始所需的填充字节数（其中mod是modulo运算符）：
padding = ( align − ( offset m o d align ) ) m o d a l i g n aligned = offset + padding = offset + ( ( align − ( offset m o d align ) ) m o d a l i g n ) \begin{aligned} \text { padding } & =(\text { align }-(\text { offset } \ mod \ \text{ align })) \ mod \text \ { align } \\ \text { aligned } & =\text { offset }+ \text { padding } \\ & =\text { offset }+((\text { align }-(\text { offset } \ mod \ \text{ align })) \ mod \text \ { align }) \end{aligned} padding aligned =( align −( offset mod align )) mod align= offset + padding = offset +(( align −( offset mod align )) mod align)
例如，对于一个地址偏移是0x59d的4字节对齐结构体，该结构体将从0x5a0开始存储并添加3字节的填充，因为0x5a0是4的倍数。计算过程如下：
p a d d i n g = ( 4 − ( 0x59d m o d 4 ) ) m o d 4 = ( 4 − 1 ) m o d 4 = 3 a l i g n e d = 0x59d + 3 = 0x5a0 \begin{aligned} padding &= (4 - (\text{0x59d} \ mod \ 4)) \ mod \ 4 = (4 - 1) \ mod \ 4 = 3 \\ aligned &= \text{0x59d} + 3 = \text{0x5a0} \end{aligned} paddingaligned=(4−(0x59d mod 4)) mod 4=(4−1) mod 4=3=0x59d+3=0x5a0
反之，当地址偏移量offset已经和对齐字节数align相等时，第二个*(align - (offset mod align)) mod align*中的模除将返回0，因此原始值将保持不变。

因为对齐操作根据定义是按照2的幂次方，所以模除运算可以简化为布尔和位运算。

下面的公式可以产生正确的值（其中&是位与，~是位非）—— 但前提是地址偏移量是无符号的，或者系统使用二进制补码运算：

padding = ( align − ( offset & ( align − 1 ) ) ) & ( align ⁡ − 1 ) = − offset & ( align − 1 ) aligned = ( offset + ( align − 1 ) ) & ∼ ( align − 1 ) = ( offset + ( align − 1 ) ) & − a l i g n \begin{aligned} \text { padding } & =(\text { align }-(\text { offset \& }(\text { align }-1))) \&(\operatorname{align}-1) \\ & =- \text { offset \& }(\text { align }-1) \\ \text { aligned } & =(\text { offset }+(\text { align }-1)) \& \sim(\text { align }-1) \\ & =(\text { offset }+(\text { align }-1)) \&-a l i g n \end{aligned} padding aligned =( align −( offset & ( align −1)))&(align−1)=− offset & ( align −1)=( offset +( align −1))&∼( align −1)=( offset +( align −1))&−align

C语言结构体在x86上的典型对齐方式

数据结构成员在内存中是按顺序存储的，因此，在下面的结构中，成员Data1总是在Data2之前；而Data2总是在Data3之前：

struct MyData
{
    short Data1;
    short Data2;
    short Data3;
};

如果 "short "类型存储在2字节的内存中，那么上面描述的数据结构的每个成员都将是2字节对齐的。数据1在偏移0，数据2在偏移2，数据3在偏移4。这个结构体的大小将是6个字节。

结构中每个成员的类型通常有一个默认的对齐方式，也就是说，除非程序员另有要求，否则它将在一个预先确定的边界上对齐。以下典型的对齐方式对微软（Visual C++）、Borland/CodeGear（C++Builder）、Digital Mars（DMC）和GNU（GCC）的编译器在为32位x86编译时有效：

有些数据类型取决于实现方式。

64 位数据模型

在 32 位程序中，指针和整数等数据类型通常具有相同的长度。但在 64 位机器上不一定如此。因此，在C及其后代（如C++和Objective-C）等编程语言中混合数据类型可能适用于 32 位实现，但不适用于 64 位实现。

在 64 位机器上的许多 C 和 C 派生语言的编程环境中，int变量仍然是 32 位宽，但long int和pointer是 64 位宽。这些被描述为具有，它是==“Long, Pointer, 64”ILP64数据模型==，其中所有三种数据类型都是64位宽，甚至还有，其中short也是64位宽。然而，在大多数情况下，所需的修改相对较小且直接，许多编写良好的程序可以简单地针对新环境重新编译而无需更改。另一种选择是，它通过将int和long保留为 32 位来保持与 32 位代码的兼容性。LL指的是类型，在所有平台上至少是64位，包括32位环境。

也有使用的 64 位处理器的系统，添加了 64 位 long long 整数；这也用于许多具有 32 位处理器的平台。该模型以更小的地址空间为代价减少了代码大小和包含指针的数据结构的大小，对于某些嵌入式系统来说是一个不错的选择。对于 x86 和 ARM 等指令集，其中 64 位版本的指令集比 32 位版本的指令集具有更多的寄存器，它提供了对额外寄存器的访问而没有空间损失。它在 64 位 RISC 机器中很常见，在 x86 中作为x32 ABI 进行了探索，并且最近被用于Apple Watch Series 4和 5。

今天许多64位平台使用LP64模型（包括Solaris、AIX、HP-UX、Linux、macOS、BSD和IBM z/OS）。微软Windows使用LLP64模型。LP64模型的缺点是，将long存储到int中会被截断。另一方面，在LP64中，将一个指针转换为一个长字符串会 “有效”。在LLP64模型中，情况恰恰相反。这些问题并不影响完全符合标准的代码，但代码的编写往往隐含着对数据类型宽度的假设。C代码在将指针转换为整数对象时，应该选择(u)intptr_t而不是long。

参考文献

1：Data structure alignment - Wikipedia

2：数据结构对齐 - 维基百科，自由的百科全书

3：64-bit computing - Wikipedia

4：Data structure alignment （数据结构对齐 / 内存对齐）_Jeff_的博客-CSDN博客

Mr.Idleman