数据结构对齐

数据结构对齐

对于大多数 x86-64 指令来说，保持数据对齐能够提高效率，但是它不会影响程序的行为．另一方面，如果数据没有对齐，某些型号的 Intel 和 AMD 处理器对于有些实现多媒体操作的 SSE 指令，就无法正确执行．这些指令对 16 字节数据块进行操作，在 SSE 单元和内存之间传递数据的指令要求内存地址必须是 16 的倍数．任何试图以不满足对齐要求的地址来访问内存都会导致异常，默认的行为是程序终止．[1]

结构体的大小不总是等于各数据成员的大小之和

struct test
{
    char a;
    long b;
    int c;
    char d;
};

结构体的大小不总是等于各数据成员的大小之和，但事实上结构体的成员间 常常 存在「空隙」．
例如上面的结构体，在笔者的设备上的大小为: 24 byte，但「各成员的大小的和」仅为 14 byte．
经过简单的计算就知道该结构体中有 41.6% 的没有被利用，这不一定是一件坏事，但是在可用内存较小的设备上创建过多的该类结构体可能不是一个好的做法．

对齐的方式

基本数据类型的「对齐要求」

上文说到结构体的数据成员间存在「间隙」，但这个间隙到底是如何分布的？

为此，需要了解先每个基本的数据类型的「对齐要求」．

info
INFO

C11 中为定义了 _Alignof 运算符来输出数据的「对齐要求」， _Alignof 的使用方式与 sizeof 类似．

_Alignof 运算符给出一个类型的对齐要求，在关键字 _Alignof 后面的圆括号中写上类型名即可：

size_t d_align = _Alignof(float);

假设 d_align 的值是 4，意思是 float 类型 对象的对齐要求是 4．也就是说，4 是储存该类型值相邻地址的字节数．一般而言，对齐值都应该是 2 的非负整数次幂．[2]

_Alignof(type) 的意义为：「若定义 TYPE a;，则 (unsigned long)&a%_Alignof(type)==0」．

较大的对齐值被称为 stricter 或 stronger，较小的对齐值被称为 weaker．[2]

#include <stdio.h>
int main(void)
{
    printf("char %zu\n", _Alignof(char));
    printf("short %zu\n", _Alignof(short));
    printf("int %zu\n", _Alignof(int));
    printf("void* %zu\n", _Alignof(void *));
    printf("long %zu\n", _Alignof(long));
    printf("long long %zu\n", _Alignof(long));
    printf("float %zu\n", _Alignof(float));
    printf("double %zu\n", _Alignof(double));
    printf("long double %zu\n", _Alignof(long double));

    printf("char %zu\n", _Alignof(const char));
    printf("short %zu\n", _Alignof(const short));
    printf("int %zu\n", _Alignof(const int));
    printf("void* %zu\n", _Alignof(const void *));
    printf("long %zu\n", _Alignof(const long));
    printf("long long %zu\n", _Alignof(const long));
    printf("float %zu\n", _Alignof(const float));
    printf("double %zu\n", _Alignof(const double));
    printf("long double %zu\n", _Alignof(const long double));

    printf("char %zu\n", _Alignof(unsigned char));
    printf("short %zu\n", _Alignof(unsigned short));
    printf("int %zu\n", _Alignof(unsigned int));
    printf("long %zu\n", _Alignof(unsigned long));
    printf("long long %zu\n", _Alignof(unsigned long));
}

可以看到的是：「对齐要求」仅与数据类型本身有关，与 const、signed、unsigned 无关．

结构体的「对齐要求」

一个定义完成的结构体是一个 复合数据类型 ，那么结构体也该有它自己的「对齐要求」．
结构体的对齐要求为其 成员 的「对齐要求」中的最大值．
因此，下面的结构体的对齐要求为：「1、8、4、1」中的最大值，也就是 8，当然也可以用 _Alignof(struct test) 验证刚才的结论．
由此，得到数据结构对齐的要求之1：「结构体地址 满足 结构体的『对齐要求』」．

struct test
{
    char a;
    long b;
    int c;
    char d;
};

特别需要注意的是：「对于任意数据类型，数据类型的大小应当为其『对齐要求』的整数倍．」
该要求在基本数据类型中没有意义，因为单个元素总是其「对齐要求」的整数倍．在结构体中，结构体的最后一个成员后 可能 需要添加「空隙」使结构体的大小为其「对齐要求」的整数倍．
由此，得到数据结构对齐的要求之2：「结构体大小 为结构体的『对齐要求』的倍数」．

结构体的「空隙」

讨论完了数据类型的「对齐要求」，现在来看看结构体中的「空隙」究竟是如何分布的．

#include <stddef.h>//提供 offsetof
#include <stdio.h>
struct test
{
    char a;
    long b;
    int c;
    char d;
};
int main(void)
{
    printf("offsetof(struct test, a)\t%lu\n", offsetof(struct test, a));
    printf("offsetof(struct test, b)\t%lu\n", offsetof(struct test, b));
    printf("offsetof(struct test, c)\t%lu\n", offsetof(struct test, c));
    printf("offsetof(struct test, d)\t%lu\n", offsetof(struct test, d));
}

info
INFO

如果你必须确定结构某个成员的实际位置，应该考虑边界对齐因素，可以使用 offsetof 宏（定义于 stddef.h）．

offsetof( type, member )

type 就是结构的类型，member 就是你需要的那个成员名．表达式的结果是一个 size_t 值，表示这个指定成员开始存储的位置距离结构开始存储的位置偏移几个字节．[3]

根据每个成员的大小和相对结构体开始处的偏移量，能得到下面的表格．

offset	内容	offset	内容
0	char a	12	long b
1	—	13	long b
2	—	14	long b
3	—	15	long b
4	—	16	int c
5	—	17	int c
6	—	18	int c
7	—	19	int c
8	long b	20	char d
9	long b	21	—
10	long b	22	—
11	long b	23	—

根据上文，一个结构体的「对齐要求」为其成员的「对齐要求」的最大值，又因为「对齐要求」通常为 2的幂，那么结构体的「对齐要求」必然是其成员对齐要求的 最小公倍数．即「结构体的首地址」满足「结构体的任一成员」的「对齐要求」．那么，只需要让结构体中的成员的偏移量为成员的「对齐要求」的倍数，那么成员的地址必将满足其「对齐要求」．
由此，得到数据结构对齐的要求之3：「成员的偏移量为成员『对齐要求』的倍数」．

联合的「对齐要求」

联合与结构体相比在「对齐要求」只有些许不同：「联合的『对齐要求』为其最大的成员的『对齐要求』」．
对下面的联合而言，其「对齐要求」为long y;或者说double z;的「对齐要求」，即 8．

union test
{
    char x;
    long y;
    double z;
};

复合数据结构的嵌套

在考虑数据结构对齐的问题时，如果遇到了「复合数据结构」嵌套的情况，只需要把内层的「复合数据结构」当作一个新的数据类型进行思考即可，在思考时不必关注其成员是 基本数据类型 还是 结构体 亦或是 联合体，只需逐层分析，逐层分析其「对齐要求」．

举个例子吧：

struct TEST
{
    union U1
    {
        char a;
        int b;
        short c;
    } d;
    long e;
    struct S1
    {
        int f;
        union U1 g;
        unsigned long h;
    } i;
    union U2
    {
        struct S1 j;
        union U1 k;
    } l;
    char m;
};

danger
WARNING

上面这段代码仅为了说明「复合数据结构的嵌套」，代码本身无应用价值且难以理解和维护．实际开发中，除非有十分充足的理由，否则不应当写出类似的代码．

现在笔者尝试分析 struct TEST：

1. 首先得出 U1 中最大的成员为 int b;，则 U1 的「对齐要求」为 int b; 的「对齐要求」，即 U1 的「对齐要求」为 4．
2. 又因为 long e; 的「对齐要求」为 8，则 d 与 e 间有 4 bytes 的「间隙」．
3. 现在分析 S1．
   1. 从 1 中知 U1 的「对齐要求」为 4．又因为 int f; 的大小为 4，所以 f 与 g 间无「间隙」．
   2. unsigned long h; 的「对齐要求」为 8，又因为在 S1 中， h 前面的成员 f 和 g 正好占用了 S1 的前 8 bytes．可知，h 与 g 间无间隙．
   3. 此时共占用 S1 的前 16 bytes ，而 S1 的「对齐要求」为 unsigned long h; 的「对齐要求」，即为 8．可知 h 后无「空隙」．
   4. 又因为 S1 的「对齐要求」为 8，而 d 与 e 共占用 struct TEST 的前 16 bytes，则 i 与 e 间无 「间隙」．
4. 现在分析 union U2;
   1. 由上：「 struct S1 j; 的『对齐要求』为 8；union U1 k; 的『对齐要求』为 4 」，则 union U2; 的「对齐要求」为：「4、8」中的最大值，即为 8．
   2. k 的「对齐要求」为 4，j 占据了 U2 的前 16 bytes ，则 k 与 j 间无「间隙」．且 k 后无「间隙」．
   3. i 与 l 的「对齐要求」均为 8 ，则i 与 l 间无「间隙」．
5. char m; 的「对齐要求」为 1，而 l 的「对齐要求」为8，故此 l 与 m 间无「间隙」．
6. 由上，struct TEST 的「对齐要求」为：「4、8、8、8、1」中的最大值，即为 8．
7. 最终得到，m 后有 7 bytes 的「空隙」．

调整结构体的成员的顺序

有了上面一大堆的铺垫，笔者相信读者们 数据结构对齐 有了自己的理解．但是还有一个遗留的问题值得在此共同探讨：怎么排列成员才能提高结构体的空间利用率．
答案很简单：「将成员按照其『对齐要求』降序排列」．
重新回到最开始的示例：

struct test
{
    char a;
    long b;
    int c;
    char d;
};

将其成员按照「对齐要求」降序排列便得到了：

struct test
{
    long b;
    int c;
    char a;
    char d;
};

经过简单的重新排序，struct test 现在只需要占用 16 bytes，节省了 8 bytes．

但是这种做法并不一定是最好的，有时结构体的成员的排列具有逻辑顺序，具有便于开发者理解的作用，重排可能会打破原有的逻辑顺序．

tip
TIP

有时，我们有充分的理由，决定不对结构的成员进行重排以减少因对齐带来的空间损失．例如，我们可能想把相关的结构成员存储在一起，提高程序的可维护性和可读性．但是，如果不存在这样的理由，结构的成员应该根据它们的边界需要进行重排，减少因边界对齐而造成的内存损失．
当程序将创建几百个甚至几千个结构时，减少内存浪费的要求就比程序的可读性更为急迫．在这种情况下，在声明中增加注释可能避免可读性方面的损失．[3]

参考资料

¹. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社 ↩

². Stephen Prata.C Primer Plus[M].第六版.姜佑,译.北京:人民邮电出版社 ↩

³. Kenneth.A.Reek.C和指针[M].徐波,译.北京:人民邮电出版社 ↩