Key Take Away

1. 从长到短排列结构体成员变量可获得最紧凑的结构体, 减少内存浪费.
2. 程序给计算机跑也给人看, 考虑到易读性和缓存命中, 不要盲目按位宽降序排列成员变量, 考虑将经常一起访问的放在一起.
3. 使用union和bitfields等激进的优化手段可以获得比1更紧凑的结构体内存布局, 虽然访问本身会变慢, 但基本会在缓存命中这里弥补回来.

闲话

有预感自己最近又要开始写C了, 准备复习一些老掉牙的知识, 也借此机会重新拜读各位大神们的作品. 这篇博客的内容几乎全部来自esr的这篇文章. 这不是一篇翻译, 也不会根据原文修改持续更新, 有英文基础的读者可以直接看原作.

原文针对c语言编写, 但知识可作用于Golang,Rust(repr(C)),Java等c风格的结构体, 因为这主要受限于ISA而非语言. esr在开发cvs-fast-export时面对大型repo时遇到了OOM. 通过重新排列结构体成员, 可以做到节省40%的内存开销. 哦吼, 让我们看看怎么个事儿.

对齐要求

现代处理器规定了在内存中放置基本数据类型的方式,以便加快内存访问速度. 在Intel, ARM, RISC-V等"原始"ISA中, 基本数据类型通常不会从任意内存地址开始放置. 对齐要求如下:

• char可以从任意地址开始
• short必须从偶数地址开始
• int或float必须从能被4整除的地址开始
• long或double必须从能被8整除的地址开始

行话称之为自对齐(self-aligned). 自对齐使得访存速度加快, 因为这有助于生成单指令的load和store. 否则你可能会需要跨越machine word的边界进行多次访存.

结构体外的填充

有如下一段C顶层的变量声明:

char *p;
char c;
int x;

指针类型p的长度是4或8, 和是32位机还是64位机有关. p从某个已经对齐的地方开始, 后面紧跟着c占1byte, 但之后的x为了满足对齐规则使内存出现间隙, 看上去就像:

char *p;      /* 4 or 8 bytes */
char c;       /* 1 byte */
char pad[3];  /* 3 bytes */
int x;        /* 4 bytes */

char pad[3]表示有3 byte的浪费, 称作slop. 填充位的值未定义, 更不保证清零. 事实上, 静态变量的分配顺序是其在源码中定义的顺序这一假设并不一定奏效. C不强制要求这样, 但这个假设通常正确.

类似的下面的定义:

char *p;
char c;
short x;

实际内存布局上看上去是:

char *p;      /* 4 or 8 bytes */
char c;       /* 1 byte */
char pad[1];  /* 1 byte */
short x;      /* 2 bytes */

又或者x是64位机上的long型:

char *p;
char c;
long x;

则看上去是这样:

char *p;     /* 8 bytes */
char c;      /* 1 byte */
char pad[7]; /* 7 bytes */
long x;      /* 8 bytes */

那细心的你一定会想, 如果短变量先定义呢:

char c;
char *p;
int x;

如果把内存布局看作是:

char c;
char pad1[M];
char *p;
char pad2[N];
int x;

那M和N是多少呢?

首先N一定是0. x出现在p之后, p保证了指针类型对齐, 即至少是4 byte.

M的情况则更多变. 如果编译器刚好把c放在了machine word的最后一个byte, 此时M为零.

但机器更有可能将c放在machine word的第一个byte. 此时为了对齐指针类型, 32位下会有3 byte的padding; 64位下会有7 byte的padding.

当然M可能是0-7(32位则是0-3)中的任意数字因为c可能被放在任意位置.

如果你想让这些变量占用更少的空间, 你可以交换x和c的顺序.

char *p;     /* 8 bytes */
long x;      /* 8 bytes */
char c;      /* 1 byte  */

结构体对齐与填充

你可能觉得像上面那样搞也省不了多少内存. 那我们看看结构体数组.

有结构体:

struct foo1 {
    char *p;
    char c;
    long x;
};

64位机, 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可能从任意地址开始, pad的长度不固定. 但结构体中, c必须和最宽的成员变量对齐, 此时pad的长度固定为7.

现在来讨论结构体的尾部填充, 为了说明它我们在这里引入一个概念: 结构体的步幅地址(stride address of a structure), 步幅地址是紧跟在结构体数据之后的第一个与结构体对齐要求相同的地址.

关于结构体尾部填充的一般规则是这样的：编译器会将结构体的尾部填充视为延伸到它的步幅地址。这个规则决定了sizeof()函数的返回值。

也就是说, 为了能保证结构体数组能够自动正确对齐, 会对结构体进行必要的尾填充. 比如:

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

虽然foo4的成员变量之间没有pad, 但为了结构体之间也能对齐, 会进行尾填充, 实际上长这样:

struct foo4 {
    short s;     /* 2 bytes */
    char c;      /* 1 byte */
    char pad[1];
};

这个尾填充在即使只声明单个结构体是也会存在, 所以sizeof(struct foo4)会返回4.

又例如, 某x86_64或ARM64机上有:

struct foo3 {
    char *p;     /* 8 bytes */
    char c;      /* 1 byte */
};

struct foo3 singleton;
struct foo3 quad[4];

实际上长这样:

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

sizeof(struct foo3)的值是16而非9, 因为步幅地址是(&p)[2]. 也因此quad中每个成员都引入了7 byte的 padding.

重点是: 如果你的结构体中有内嵌结构体, 内嵌结构体也和最长的成员变量对齐. 例如:

#include <stdio.h>

struct foo5 {
    char c;              /* 1 byte*/
    // char pad1[7];     /* 7 bytes */
    struct foo5_inner {
        char *p;         /* 8 bytes */
        short x;         /* 2 bytes */
        // char pad2[6]; /* 6 bytes */
    } inner;
};

struct foo6 {
    struct foo6_inner {
        char *p;         /* 8 bytes */
        short x;         /* 2 bytes */
        // char pad1[6]; /* 6 bytes */
    } inner;
    char c;              /* 1 byte*/
    // char pad2[7];     /* 7 bytes */
};

int main(){
    struct foo5 fo5;
    struct foo6 fo6;
    printf("foo5:%d\n",sizeof(fo5)); // 24
    printf("foo6:%d\n",sizeof(fo6)); // 24
    return 0;
}

可以看到, 在foo6中我们把char c移到了结构体的末尾, 虽然在不考虑结构体内嵌的情况下已经是对齐的, 但sizof仍然返回24. 于是乎, 24 byte结构体13 byte的padding, 超过50%的浪费!

Bitfields

C语言的 bitfield 功能允许你声明比byte更短的字段. 它通过word掩码和byte掩码加上rotate指令来实现. 你会在访问上有一些时间损失, 但如果你可以打包的足够紧凑, 缓存命中率提高带来的收益会抵消这部分损失.

C99标准严格保证在每个字段不cross word的情况下最紧凑的排列. C11和C14放缓了cross word的硬性要求, 具体取决于ABI的实现.

// 有如下struct
struct foo6 {
    short s;
    char c;
    int flip:1;
    int nybble:4;
    int septet:7;
};

// 32位机下根据C99标准的实现会长这样:
struct foo6 {
    short s;       /* 2 bytes */
    char c;        /* 1 byte */
    int flip:1;    /* total 1 bit */
    int nybble:4;  /* total 5 bits */
    int pad1:3;    /* pad to an 8-bit boundary */
    int septet:7;  /* 7 bits */
    int pad2:25;   /* pad to 32 bits */
};

// 但C标准也没规定bits必须从低到高分配所以也可能长这样:
struct foo6 {
    short s;       /* 2 bytes */
    char c;        /* 1 byte */
    int pad1:3;    /* pad to an 8-bit boundary */
    int flip:1;    /* total 1 bit */
    int nybble:4;  /* total 5 bits */
    int pad2:25;   /* pad to 32 bits */
    int septet:7;  /* 7 bits */
};

就是说字段可能在padding的前或后. 而且, 和正常padding一样, 位的padding值也不保证为0.

不能cross word的规定会要求你用它的时候多想想. 比如下面这种情况:

struct foo7 {
    int bigfield:31;      /* 32-bit word 1 begins */
    int littlefield:1;
};

struct foo8 {
    int bigfield1:31;     /* 32-bit word 1 begins */
    int littlefield1:1;
    int bigfield2:31;     /* 32-bit word 2 begins */
    int littlefield2:1;
};

struct foo9 {
    int bigfield1:31;     /* 32-bit word 1 begins */
    // int pad:1;
    int bigfield2:31;     /* 32-bit word 2 begins */
    int littlefield1:1;
    int littlefield2:1;   /* 32-bit word 3 begins */
};

结构体成员变量重排序

简单地将字段宽度从高到低排列即可获得最紧凑的结构体. 有趣的是, 从低到高也是可以的.

那既然如此简单, 编译器为什么不自动完成这个工作呢? 这是因为C最初设计为编写操作系统等贴近硬件层面的代码语言, 自动排序会干扰程序员对内存布局的掌控能力. Go遵循C哲学不做重排序; Rust相反默认会重排.

其他结构体打包技巧

1. 基于对要处理的数据的知识进行压缩. 比如说如果我知道我要处理的数据的时间戳不会早于1982-01-01T00:00:00, 那我可以只使用32位的time_t, 将时间从unix元年做一个位移, 并将其视作unsigned, 那我可以处理到2118年的数据. 当然, 这么做的时候一定要加上边界检查的逻辑来避免奇怪的bug.

2. union是最危险的打包技巧, 如果你知道你的某些数据永远不会和另一些数据同时使用, 考虑用union将它们打包到一起. 但务必写好测试用例, 通过回归测试来保证程序的正确性. 稍有不慎就会遇到各种错误, 崩溃都算好的, 细微的数据损坏更头疼.

标量的特殊情况

用#define做枚举类型不是个好主意, 编译器保证它是整数但不保证它的底层类型, 虽然通常是int.

long double也是个麻烦, 有些平台的实现是80位, 有的是128位, 有些80位的实现会padding到96又或是128位.

在x86 Linux下, double还有可能只需要4byte的对齐.

其他

重新排序体简单却不一定是正确. 还有两个考虑点: 可读性和缓存局部性.

程序不仅仅是给计算机运行的, 也是与其他人交流的. 即使交流的受众只是未来的你.

无脑地对结构体重新排序可能会损害可读性. 最好重新排序字段, 使它们保持在连贯的组中, 并将语义相关的数据片段保持紧密联系. 理想情况下, 结构的设计应该传达程序的设计.

当您的程序频繁访问某个结构或某个结构的一部分时，如果访问往往适合缓存行（处理器在被告知获取块内的任何单个地址时提取的内存块），则对性能很有帮助。在 64 位 x86 上，缓存行是 64 个字节，从自对齐地址开始；在其他平台上，缓存行通常是 32 个字节。

为了保持可读性，您应该做的事情 - 将相关和共同访问的数据分组到相邻字段中 - 也可以改善缓存行局部性。这些都是智能地重新排序的原因，同时了解代码的数据访问模式。

如果您的代码确实从多个线程并发访问某个结构，则会出现第三个问题：缓存行反弹。为了最大限度地减少昂贵的总线流量，您应该在更紧密的循环中安排数据，以便读取来自一个缓存行，写入转到另一个缓存行。

是的，这有时与之前关于将相关数据分组到同一个缓存行大小的块中的指导相矛盾。多线程很难。缓存行反弹和其他多线程优化问题是非常高级的主题，值得专门写一个完整的教程。我在这里能做的最好的就是让你意识到这些问题的存在。