如何组织结构体中的成员以在对齐时浪费最少的空间？

Question

如何组织结构体中的成员以在对齐时浪费最少的空间？

c++optimizationmemory-alignmentmemory-layoutstruct-member-alignment

61

[这不是结构体内部填充和打包的重复问题。那个问题是关于填充何时发生的。这个问题是关于如何处理它的。]

我刚意识到在C ++中由于对齐而浪费了多少内存。考虑以下简单的例子：

struct X
{
    int a;
    double b;
    int c;
};

int main()
{
    cout << "sizeof(int) = "                      << sizeof(int)                      << '\n';
    cout << "sizeof(double) = "                   << sizeof(double)                   << '\n';
    cout << "2 * sizeof(int) + sizeof(double) = " << 2 * sizeof(int) + sizeof(double) << '\n';
    cout << "but sizeof(X) = "                    << sizeof(X)                        << '\n';
}

使用g++编译程序会输出以下内容：

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 24

这将增加50%的内存开销！在一个由134217728个 X 组成的3GB数组中，有1GB纯粹是填充空间。

幸运的是，解决这个问题非常简单 - 我们只需要交换 double b 和 int c 的位置：

struct X
{
    int a;
    int c;
    double b;
};

现在的结果要令人满意得多：

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 16

然而有一个问题：这不是跨平台兼容的。是的，在g++下，int是4个字节，double是8个字节，但这不一定总是正确的（它们的对齐方式也不必相同），因此在不同的环境下，这种“修复”不仅可能是无用的，而且可能会通过增加所需填充的数量来恶化情况。

是否有可靠的跨平台方法来解决这个问题（最小化需要的填充量而不会因对齐不当而导致性能下降）？为什么编译器不执行这样的优化（交换结构/类成员以减少填充）？

澄清：由于误解和混淆，我想强调我不想“压缩”我的结构。也就是说，我不希望其成员不对齐，从而访问速度变慢。相反，我仍然希望所有成员都是自对齐的，但以使用最少的填充内存的方式进行。这可以通过手动重新排列来解决，如Eric Raymond在The Lost Art of Packing中所述。我正在寻找一种自动化的、尽可能跨平台的方法来完成此操作，类似于正在开发的C++20标准中提到的P1112提案。

- user11313931

2

如果你需要数亿个元素的“数组”，那么也许数组并不是正确的数据结构？至少不是内存中的数组（考虑内存映射文件，或者甚至某种类型的数据库）？ - Some programmer dude

2

使用固定宽度整数可能会带来一些可移植性的好处，因为它们不会改变大小。 - user4581301

1

关于“为什么编译器不执行这样的优化（交换结构/类成员以减少填充）？”如何在编译器无法确定结构用途时进行操作？也许它将原始存储在二进制文件中，或通过串行通信协议发送（在这种情况下，解包结构（手动或通过编译器指示）真的是一个坏主意，但它仍然会发生）。 - Some programmer dude

6

首先考虑对齐要求最高的元素。如果没有这样的元素，则考虑最大的成员变量。关于您真正的问题，是的，有一种跨平台兼容的方法：它被称为字符串（string）。除此之外，使用指定位宽度的类型可以在很大程度上帮助，但如果您确实非常注重跨平台性，仍需要处理字节序。简而言之，协议是专门用来解决这些问题并弥合平台之间的巨大差异的。正因为存在诸如此类的原因，它们是存在的。注意：我非常可能误解了本问题中的"this"。 - WhozCraig

4

由于上述原因，没有一种方法可以保证结构体大小的最小存储空间。但是@WhozCraig提供了一条简单规则的精确解释：“先放最大的，后放最小的”，以所需的存储空间递减的顺序排列。这是一种合理的方法，可以在编译器和硬件之间最小化存储空间，但不能保证任何两个结构体在编译器之间分配相同数量的存储空间（除了像struct foo { int a, b; };这样的简单例子）。 - David C. Rankin

显示剩余10条评论

7个回答

32

gcc有一个-Wpadded警告，用于在结构体中添加填充时发出警告:

https://godbolt.org/z/iwO5Q3:

<source>:4:12: warning: padding struct to align 'X::b' [-Wpadded]
    4 |     double b;
      |            ^

<source>:1:8: warning: padding struct size to alignment boundary [-Wpadded]
    1 | struct X
      |        ^

你可以手动重新排列成员，以减少/消除填充。但这不是一种跨平台的解决方案，因为不同的类型在不同系统上可能具有不同的大小/对齐方式（最明显的是指针在不同架构上为4或8字节）。通常的经验法则是在声明成员时按从大到小的对齐方式进行排序，如果你仍然担心，可以使用-Wpadded编译代码一次（但我通常不会保持它开启，因为有时填充是必要的）。

至于编译器不能自动执行此操作的原因，是因为标准规定（[class.mem]/19），因为这是一个只有公共成员的简单结构体，所以&x.a < &x.c（对于某些X x;），因此它们无法被重新排列。

- Artyer

9

老实说，我并没有想到这个问题会有什么有用的结果。我不知道那个gcc选项（现在我希望clang也有它），感谢你教会了我一些东西。打勾。 - WhozCraig

1

@WhozCraig 是的，clang也有这个选项（甚至名称相同）。当处理“重新排列问题”时，它非常有帮助（至少对我来说是这样）。遗憾的是，（至少目前）我还没有找到自动化解决方案。 - user11313931

有没有任何现代平台，在其中按顺序放置类型 double、[无符号] long long、[i] int64_t、int64_t、指针、long、float、int32_t、int、int16_t、short、char，不会产生最佳对齐？ - supercat

您链接到 eel.is 的链接会随着标准草案的演变而失效。将链接指向最终文档会更有用。请参见此处。例如：[class.mem]/19。 - Dr. Gut

14

在通用情况下，真的没有一种便携式解决方案。除了标准规定的最小要求外，类型可以是实现希望使它们成为的任何大小。

除此之外，编译器不允许重新排序类成员以使其更有效率。标准要求对象必须按其声明顺序（按访问修饰符）布局，因此这也不可行。

您可以使用固定宽度的类型，例如

struct foo
{
    int64_t a;
    int16_t b;
    int8_t c;
    int8_t d;
};

只要提供这些类型，所有平台上的结果都将是相同的，但它仅适用于整数类型。没有固定宽度的浮点类型，并且许多标准对象/容器在不同平台上的大小可能不同。

- NathanOliver

更加令人沮丧的是，浮点类型经常对总线对齐位置非常敏感，从而增强了“没有银弹”口号。尽管如此，在使用结构体加载除浮点数和潜在指针之外的任何内容时，这非常有用。我经常使用它。 - WhozCraig

为什么不允许成员重新排列？您能澄清一下吗？ - user11313931

3

如果你将跨平台可移植性发挥到极致，需要注意这些“精确宽度”类型是可选的。每个平台必须拥有int_least16_t和int_fast16_t，但是（例如如果CHAR_BIT！=8），在某个平台上不一定存在int16_t。 - DevSolar

2

@DevSolar 虽然它们是可选的，但如果它们不存在，代码将无法编译，因此至少您不会得到二进制文件，导致程序崩溃。 - NathanOliver

你可以将浮点数存储在4字节的整型中，但读写操作会比较麻烦。 - Oblivion

1

@YanB。因为标准是这样规定的。另外请参考https://dev59.com/K3VD5IYBdhLWcg3wBWvd。至于原理，如果编译器可以自由地这样做，很多东西都会出问题（其中之一是，想象一下一个使用`fwrite`直接将`struct`写入文件并使用`fread`读取它们的程序；编译器的更改可能会突然破坏已编译程序的文件格式兼容性）。 - jamesdlin

5

伙计，如果你有3GB的数据，你可能应该采用其他方式来解决问题，而不是交换数据成员。

可以使用“数组结构”而不是“结构数组”。就像这样

struct X
{
    int a;
    double b;
    int c;
};

constexpr size_t ArraySize = 1'000'000;
X my_data[ArraySize];

将要成为

constexpr size_t ArraySize = 1'000'000;
struct X
{
    int    a[ArraySize];
    double b[ArraySize];
    int    c[ArraySize];
};

X my_data;

每个元素仍然易于访问mydata.a[i] = 5; mydata.b[i] = 1.5f;...。
除了数组之间的几个字节外，没有填充。内存布局对缓存很友好。预取器处理从几个单独的内存区域读取顺序内存块的操作。

乍一看，这并不是那么不寻常。该方法广泛用于SIMD和GPU编程。

结构体数组（AoS），数组结构

- user3124812

2

当 SIMD 可能时，这会好得多。但是当需要对结构体进行分散/随机访问（并且需要同一结构体的多个成员，但不需要附近结构体的任何内容）时，SoA 会使你的缓存失效率提高 3 倍。它还会增加更多指针/寄存器的使用，特别是对于非 CISC 和/或非静态分配。但是如果在您的循环中 SIMD 是一个选项，那么使用 SoA 通常会好得多。 - Peter Cordes

4

这是一个经典的内存与速度问题。填充(padding)是为了以换取速度来节省内存。你不能说:

“我不想'打包(pack)'我的结构体。”

因为pragma pack就是为了用另一种方式实现这种权衡：牺牲内存以换取速度。

“是否有可靠的跨平台方法呢？”

答案是否定的，因为对齐(alignment)是严格依赖于平台的问题。不同类型(sizeof)的大小也是平台相关的问题。通过重新组织来避免填充(padding)也是平台相关的问题的平方。

速度、内存和跨平台——你只能选择其中两个。

“为什么编译器不执行这样的优化(交换结构/类成员以减少填充)?”

因为C++规范明确保证编译器不会破坏你精心组织的结构体。想象一下，如果你有四个浮点数在一起，有时你使用它们的名称，有时你将它们传递给一个需要float[3]参数的方法。

你建议编译器应该洗牌它们，可能会破坏自1970年以来的所有代码。而这么做的原因是什么？你能保证每个程序员都想要节省你每个结构体的8个字节吗？如果我有一个3GB的数组，我肯定会遇到比多或少1GB更大的问题。

- Agent_L

2

@JeremyFriesner：请注意，“未定义行为”旨在允许实现在实际情况下提供更有用的语义，但在语言破坏者接管并开始将其用作借口时，即使在不需要任何代价的情况下也不提供有用的语义。 - supercat

1

@JeremyFriesner：确保在使用这种低级编程技术时，所使用的实现“被设计或配置为适合此类目的”，否则会遇到麻烦。但是，如果使用不适合任何特定工作的实现，则会引发麻烦。 - supercat

1

@supercat，实际上并不是“语言破坏者接管了”，而是编译器编写者通过严格遵守“未定义行为”来挤出更多的优化机会。本质上，您希望编译器执行一些明智的操作，而编译器编写者则更喜欢执行一些快速的操作（因为这可以提高基准测试结果，从而提高销售/知名度，并且实际上即使对于相当正常的程序，也可以提高运行时速度）。 - toolforger

2

@toolforger：你读过已发布的Rationale吗？根据委员会的说法，C语言精神最基本的方面是“信任程序员”和“不阻止程序员做必须要做的事情”。他们还明确承认C语言的一个优点是能够使用非可移植程序来完成可移植程序无法完成的任务（因为标准没有提供）。如果某个任务需要执行某些操作，则适用于该任务的所有实现都将支持该操作，无论标准是否要求。 - supercat

1

顺便说一句，这正在变成关于背景细节的延伸讨论，而这不是评论的目的。 - toolforger

显示剩余10条评论

2

虽然标准允许实现在结构成员之间插入任意数量的空格，但这是因为作者不想尝试猜测所有可能需要填充的情况，而且“没有理由浪费空间”的原则被认为是不言自明的。

实际上，几乎每个常见的硬件实现都会使用大小为2的幂次方的原始对象，并且所需的对齐方式也是2的幂次方，且不大于大小。此外，几乎每个这样的实现都会将结构的每个成员放置在其对齐的第一个可用倍数上，该倍数完全跟随前一个成员。

一些学究会抱怨利用这种行为的代码是“非可移植的”。对他们我会回答：

C代码可以是非可移植的。虽然它力图给程序员编写真正可移植的程序的机会，但C89委员会不想强迫程序员编写可移植的程序，以避免使用C作为“高级汇编器”：编写机器特定的代码是C的优点之一。

作为该原则的轻微扩展，只需要在90％的计算机上运行的代码即使不完全是“机器特定的”，也可以利用该90％计算机中常见的功能，这是C的优点之一。 C程序员不应该期望他们要迎合几十年来只在博物馆中使用的体系结构的限制，这一点应该是不言自明的，但显然并非如此。

- supercat

1

你可以使用#pragma pack(1)，但这样做的原因是编译器进行了优化。通过完整寄存器访问变量比访问最不重要的位更快。

特定的打包仅用于序列化和编译器间的兼容性等方面。

正如NathanOliver所正确添加的那样，这甚至可能在某些平台上失败。

- Michael Chourdakis

7

请注意，这可能会导致性能问题或使代码无法在某些平台上运行：https://dev59.com/z2sz5IYBdhLWcg3wlY69 - NathanOliver

1

据我所知，使用#pragma pack会导致潜在的性能问题，因此不是理想的解决方案。 - user11313931

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

不要盲目应用这些规则。请参考ESR关于一起使用的成员的缓存局部性的观点。在多线程程序中，要注意不同线程写入的成员之间的虚假共享。通常情况下，出于这个原因，你不希望在单个结构体中有每个线程的数据，除非你正在使用alignas(128)来控制分离。这适用于原子和非原子变量；重要的是线程写入缓存行，而不管它们如何执行。

经验法则：从大到小排列alignof()。现在最常见的情况是针对普通32位或64位CPU的合理“正常”C++实现。所有基本类型都有2的幂次大小。

大多数类型的alignof(T) = sizeof(T)，或者alignof(T)被限制在实现的寄存器宽度上。因此，较大的类型通常比较小的类型具有更高的对齐方式。

大多数ABIs中的结构体打包规则使结构体成员相对于结构体开头具有其绝对alignof(T)对齐方式，并且结构体本身继承其任何成员中最大的alignof()。

首先放置始终为64位的成员（如double、long long和int64_t）。当然，ISO C++并没有将这些类型固定在64位/8字节，但实际上，在您关心的所有CPU上，它们都是64位的。将代码移植到异域CPU的人可以调整结构布局以进行优化。
然后是指针和指针宽度的整数：size_t、intptr_t和ptrdiff_t（可能是32位或64位）。在具有平面内存模型的正常现代C++实现中，它们的宽度都相同。

如果你关心x86和Intel CPU，考虑首先放置链表和树的左/右指针。当结构体起始地址与你要访问的成员不在同一个4k页面时，通过节点进行指针跟踪会有惩罚。将它们放在前面可以保证这种情况不会发生。
然后是long（即使指针是64位的，在像Windows x64这样的LLP64 ABI中有时也是32位的）。但至少保证与int一样宽。
然后是32位的int32_t、int、float、enum。（如果你关心可能将这些类型填充到32位的8/16位系统，或者自然对齐效果更好的系统，则可以选择在int之前单独分离int32_t和float。大多数这样的系统没有更宽的负载（FPU或SIMD），因此更宽的类型必须始终作为多个单独的块处理。）

ISO C++允许int最窄为16位，或任意宽度，但实际上即使在64位CPU上也是32位类型。ABI设计人员发现，如果int更宽，那么为了适应32位的int程序会浪费内存（和缓存占用）。不要做会导致正确性问题的假设，但对于“可移植性能”，您只需要在正常情况下做正确的事情。

为异域平台调整代码的人可以进行调整。如果某种结构布局对性能至关重要，也许可以在头文件中注释您的假设和推理。
然后是short/int16_t
然后是char/int8_t/bool
（对于多个bool标志，特别是如果它们大多数情况下只读或者它们都在一起修改，请考虑使用1位位域来打包它们。）

（对于无符号整数类型，请在我的列表中找到相应的有符号类型。）

如果你想要一个更窄的类型的8字节倍数的数组出现在前面，那么可以这样做。但是，如果你不知道类型的确切大小，你不能保证 int i + char buf[4] 会填充两个 double 之间的8字节对齐插槽。但这并不是一个坏的假设，所以如果有一些原因（比如一起访问的成员的空间局部性）将它们放在一起而不是放在最后，我仍然会这样做。

异类类型：x86-64 System V 的 alignof(long double) = 16，但 i386 System V 只有 alignof(long double) = 4，sizeof(long double) = 12。这是 x87 80位类型，实际上是10字节，但填充到12或16字节，使其成为其 alignof 的倍数，从而使数组可以在不违反对齐保证的情况下使用。

总的来说，当结构体成员本身是聚合体（结构体或联合体），且 sizeof(x) != alignof(x) 时，情况会变得更加棘手。

在某些ABIs中（例如32位Windows，如果我记得正确的话），结构成员会相对于结构的起始位置按其大小（最多8字节）对齐，即使对于double和int64_t，alignof(T)仍然只有4。这是为了优化单个结构的8字节对齐内存的常见情况，而不提供对齐保证。i386 System V对于大多数原始类型也具有相同的alignof(T)=4（但malloc仍然会给您8字节对齐的内存，因为alignof(maxalign_t)=8）。但是，无论如何，i386 System V都没有那个结构打包规则，因此（如果您没有按照从大到小的顺序排列结构），您可能会发现8字节成员与结构的起始位置不对齐。

大多数CPU都有寻址模式，可以通过寄存器中的指针访问任何字节偏移量。最大偏移通常非常大，但是在x86上，如果字节偏移适合于有符号字节（[-128..+127]），则可以节省代码大小。因此，如果您有任何类型的大型数组，请优先将其放置在结构体中较后面的位置，而不是经常使用的成员之前。即使这样会稍微增加填充。

您的编译器几乎总会生成具有结构体地址的代码，而不是一些地址位于结构体中间以利用短负位移。

Eric S. Raymond写过一篇文章The Lost Art of Structure Packing，其中Structure reordering部分基本上回答了这个问题。

他还提出了另一个重要观点：

9. 可读性和高速缓存局部性

尽管按大小重新排序是消除浪费的最简单方法，但不一定是正确的方法。还有两个问题：可读性和高速缓存局部性。

在可以轻松跨越高速缓存线边界的大型结构中，如果它们总是一起使用，则将2个元素放在附近是有意义的。甚至可以连续地进行加载/存储合并，例如使用一个（不对齐的）整数或SIMD加载/存储来复制8或16字节，而不是分别加载更小的成员。

现代CPU上的高速缓存行通常为32或64字节。（在现代x86上，始终为64字节。Sandybridge系列在L2缓存中具有相邻行空间预取器，试图完成128字节的行对，与主L2流处理程序HW预取模式检测器和L1d预取不同）。

有趣的事实：Rust允许编译器重新排列结构体以获得更好的打包效果或其他原因。虽然我不知道是否有任何编译器实际上这样做了。如果您希望选择基于结构体的实际使用情况，则可能仅在链接时进行整个程序优化才能实现。否则，程序的单独编译部分无法就布局达成一致。

(@alexis发布了一个只包含链接的答案，链接到ESR的文章，所以感谢这个起点。)

({{@alexis}}发布了一篇只有链接的回答，链接指向ESR的文章，因此感谢这个起点。)