在C++中优化成员变量顺序

53
我正在阅读一篇由Introversion的游戏编码者撰写的博客文章,他正忙于尝试从代码中挤出每一个CPU时钟。他顺便提到的一个技巧是:

"将类的成员变量按最常用和不常用排序。"

我不熟悉C++,也不了解它是如何编译的,但我想知道:
  1. 这个说法准确吗?
  2. 怎么/为什么?
  3. 它适用于其他(编译/脚本)语言吗?
我知道这个技巧节省的(CPU)时间很少,这并不是决定性因素。但另一方面,在大多数函数中,很容易确定哪些变量将是最常用的,并且默认情况下开始编码就可以了。

好的,现在来吧 - 你们都是嵌入式系统的人,对吧? - chickeninabiscuit
我在嵌入式系统方面完全没有经验,甚至不确定它的确切含义。我会去查一下,但现在还不清楚。 - DevinB
10个回答

66

这里有两个问题:

  • 是否以及何时将某些字段放在一起是一种优化。
  • 如何实际执行它。

之所以可能有帮助,是因为内存加载到 CPU 缓存中的块称为“缓存行”。这需要时间,一般来说,加载到您对象的缓存行越多,耗费的时间就越长。同时,更多其他内容会被清除以腾出空间,这会以不可预测的方式减慢其他代码的速度。

缓存行的大小取决于处理器。如果与对象大小相比较大,则很少有对象跨越缓存行边界,因此整个优化基本上无关紧要。否则,你可以有时只在缓存中保留对象的一部分,其余部分在主内存(或L2缓存,也许)中。如果最常见的操作(访问经常使用的字段的操作)尽可能少地使用对象的缓存,那么将这些字段分组在一起会使你更有机会实现这一点。

总的原则称为“局部性”。程序访问的不同存储器地址越接近,则获取良好的缓存行为的机会越大。通常很难事先预测性能:相同架构的不同处理器型号可以表现不同,多线程意味着你经常不知道会有什么在缓存中,等等。但通常可以谈论发生的可能性大多数时间。如果您想要了解任何事情,通常必须测量它。

请注意,这里有一些陷阱。如果您使用基于 CPU 的原子操作(C++0x中的原子类型通常会),则可能会发现 CPU 锁定整个缓存行以锁定字段。然后,如果您有几个相邻的原子字段,不同的线程在不同的核心上运行,并且同时在不同的字段上操作,则会发现所有这些原子操作被串行化,因为它们都锁定相同的内存位置,即使它们在不同的字段上操作。如果它们在不同的缓存行上操作,那么它们将并行工作并更快地执行。实际上,正如 Glen(通过 Herb Sutter)在他的回答中指出的那样,在一致性高速缓存体系结构上,即使没有原子操作,这也会发生,并可能完全破坏您的一天。因此,在涉及多个核心的情况下,局部性引用不一定是一个好东西,即使它们共享缓存。你可以期望它是,因为缓存未命中通常是速度损失的来源,但在你特定的情况下可能会非常错误。

现在,除了区分常用和不常用的字段之外,对象越小,它占用的内存(因此缓存)就越少。这基本上是好消息,至少在没有大量争用的情况下是这样。对象的大小取决于其中的字段以及必须插入字段之间的任何填充以确保它们对于体系结构正确对齐。C ++(有时)根据它们声明的顺序放置字段的约束条件在一个对象中。这是为了使低级编程更容易。所以,如果您的对象包含:

  • int(4字节,4对齐)
  • 后跟char(1字节,任何对齐方式)
  • 后跟int(4字节,4对齐)
  • 后跟char(1字节,任何对齐方式)

那么很有可能它将占用16字节的内存。顺便说一下,int的大小和对齐方式在每个平台上都不同,但4非常常见,这只是一个例子。

在这种情况下,编译器将在第二个int之前插入3个字节的填充,以正确对齐它,并在末尾插入3个字节的填充。对象的大小必须是其对齐方式的倍数,以便可以将相同类型的对象相邻地放置在内存中。这就是C / C ++中的数组,相邻的内存对象。如果结构体是int,int,char,char,则相同的对象可能只有12个字节,因为char没有对齐要求。

我说过int是否4对齐取决于平台:在ARM上,它绝对必须是,因为未对齐访问会引发硬件异常。在x86上,您可以访问不对齐的整数,但通常速度较慢,并且我IRC非原子。因此,编译器通常(总是?)在x86上将int 4对齐。

编写代码时的经验法则是,如果您关心打包,请查看结构的每个成员的对齐要求。然后按最大对齐类型的字段首先排序,然后按下一个最小的字段排序,以此类推,直到没有对齐要求的成员。例如,如果我正在尝试编写可移植代码,则可能会得出以下结果:

struct some_stuff {
    double d;   // I expect double is 64bit IEEE, it might not be
    uint64_t l; // 8 bytes, could be 8-aligned or 4-aligned, I don't know
    uint32_t i; // 4 bytes, usually 4-aligned
    int32_t j;  // same
    short s;    // usually 2 bytes, could be 2-aligned or unaligned, I don't know
    char c[4];  // array 4 chars, 4 bytes big but "never" needs 4-alignment
    char d;     // 1 byte, any alignment
};

如果你不知道一个字段的对齐方式,或者你正在编写可移植代码但是希望尽可能地避免大量的技巧,那么你可以假设结构中任何基本类型的对齐要求都是最大的要求,并且基本类型的对齐要求就是它们的大小。因此,如果你的结构包含uint64_t或long long,则最好的猜测是它是8字节对齐的。有时你会猜错,但很多时候你会猜对。
请注意,像博主这样的游戏程序员通常了解他们的处理器和硬件的一切,因此他们不需要猜测。他们知道缓存行大小,他们知道每种类型的大小和对齐方式,以及他们的编译器用于POD和非POD类型的结构布局规则。如果他们支持多个平台,那么他们可以特殊处理每个平台(如果必要的话)。他们还花费大量时间思考哪些对象在他们的游戏中将受益于性能提升,并使用分析工具找出真正的瓶颈所在。但即使如此,拥有一些经验法则也不是一个坏主意,只要它不会使代码变得不清晰,“将常用字段放在对象的开头”和“按对齐要求排序”是两个好规则。

不要忘记 #pragma pack 及其对成员对齐的影响。 - Remus Rusanu
1
好的观点。可以说,一些/许多编译器允许您以非默认方式布置结构体,如果您知道在特定情况下需要什么而默认设置不是它。在结构体表示某些I/O字节序列的情况下,打包指示语是至关重要的,例如当您正在读取或写入网络数据包时。您不能承受意外的、平台特定的填充。 - Steve Jessop
5
“Far too long” you claim. 我认为这是一个令人难以置信的回复。如果我能给它点赞(+10),我会这么做。 - DevinB
1
如果所有的ARM CPU在访问不对齐时都能引发硬件异常,那么世界将会更美好。然而,许多ARM7TDMI设计并没有这样做,它们只是旋转/扩散数据,这对于调试来说并不是一件有趣的事情。 - bk1e
@bk1e:呸。我曾经工作的一个地方,调试模式下的x86编译器在每次内存访问之前插入了对齐检查,这样那种问题通常可以在设备上出现之前被捕获。这很有帮助。 - Steve Jessop
显示剩余2条评论

12

根据你运行的程序类型,这些建议可能会增加性能,也可能会极大地减缓速度。

在多线程程序中这样做意味着增加“虚假共享”的机会。

请查阅Herb Sutter在这个主题上的文章此处

我之前已经说过,我将继续说。唯一真正获得性能提升的方式是测量您的代码,并使用工具识别真正的瓶颈,而不是随意更改代码库中的东西。


非常同意。Sutter关于伪共享的文章写得很好。此外,性能分析绝对应该是优化的第一步。 - luke
+1 这是一个好观点... 但我没有在问题中看到任何关于代码是否多线程的提及。 - oz10

6

这是优化工作集大小的一种方式。约翰·罗宾斯有一篇很好的文章,介绍了如何通过优化工作集大小来加速应用程序性能。当然,这需要仔细选择最常用的用例,即最终用户可能使用的应用程序。


那篇文章很棒,但似乎只适用于C++。你知道这些概念是否也适用于C#吗? - DevinB
我不懂C#的ABC,但如果有dll的概念,它应该会有所帮助。有没有C#大师有什么评论? - Canopus

3
我们在这里为成员制定了稍微不同的指南(ARM架构目标,主要是由于各种原因使用THUMB 16位代码生成):
  • 按对齐要求分组(或者对于新手,“按大小分组”通常就可以解决问题)
  • 从最小开始
“按对齐分组”有些显而易见,并且超出了本问题的范围;它避免填充,使用更少的内存等。
然而,第二个要点源自于THUMB LDRB(加载寄存器字节),LDRH(加载寄存器半字)和LDR(加载寄存器)指令上的小型5位“立即数”字段大小。
5位意味着可以编码0-31的偏移量。有效地,假设“this”在一个寄存器中(通常是这样的):
  • 如果8位字节存在于this+0到this+31,则可以在一条指令中加载它们。
  • 如果16位半字存在于this+0到this+62,则可以在一条指令中加载它们;
  • 如果32位机器字存在于this+0到this+124,则可以在一条指令中加载它们。
如果它们超出了这个范围,就必须生成多个指令:要么是一系列带有立即数的ADD,以累加寄存器中的适当地址,要么是更糟糕的,即从函数末尾的文字池中加载。
如果我们确实命中了文字池,那就会很痛苦:文字池通过d-cache而不是i-cache,这意味着至少需要从主存储器加载一个缓存行的数据来进行第一次文字池访问,然后在d-cache和i-cache之间可能会出现大量的驱逐和失效问题,如果文字池不是从自己的缓存行开始(例如,如果实际代码不是在缓存行的末尾结束)。
(如果我对我们正在使用的编译器有一些愿望,那么强制文字池从缓存行边界开始的方法将是其中之一。)
(不相关的是,我们为了避免使用文字池而做的一件事情是将所有的“全局变量”保存在一个单独的表中。这意味着对于“GlobalTable”,只需要一个文字池查找,而不是每个全局变量都需要多次查找。如果你真的聪明,你可能能够将你的GlobalTable保存在某种可以在不加载文字池条目的情况下访问的内存中--是.sbss吗?)

3
虽然缓存行为的局部性通常是一个相关考虑,以提高数据访问的缓存效果,但在需要优化时控制布局还有其他一些原因——尤其是在嵌入式系统中,即使许多嵌入式系统使用的CPU甚至没有缓存。

- 结构体中字段的内存对齐

许多程序员都很清楚地了解到内存对齐的注意事项,所以我不会在这里详细介绍。

在大多数CPU架构中,结构体中的字段必须以本地对齐方式进行访问以提高效率。这意味着如果您混合使用各种大小的字段,则编译器必须在字段之间添加填充以保持对齐要求正确。因此,为了优化结构使用的内存,重要的是要牢记这一点,并布置字段,使最大的字段后跟较小的字段,以将所需的填充量最小化。如果一个结构体要被“打包”以防止填充,则访问未对齐的字段的运行时成本很高,因为编译器必须使用一系列访问来访问未对齐的字段,以及移位和掩码来组装寄存器中的字段值。

- 结构体中经常使用的字段的偏移量

在许多嵌入式系统上,另一个需要考虑的问题是将经常访问的字段放在结构的开头。

一些架构在指令中有限数量的位可用于编码对指针访问的偏移量,因此如果您访问的字段的偏移量超过该位数,则编译器将不得不使用多个指令来形成对该字段的指针。例如,ARM的Thumb架构有5位可用于编码偏移量,因此只有在距离起始位置124字节以内的情况下,才能在单个指令中访问一个字大小的字段。因此,如果您有一个大的结构体,嵌入式工程师可能要考虑的一种优化是将经常使用的字段放在结构布局的开头。


2

首个成员不需要添加偏移量到指针上来进行访问。


偏移量是固定的,所以我认为机器码指令将包含该加法操作,而且无论如何都会有一个CPU周期。 - Macke
@Pax:为什么呢?首先,如果没有虚函数表,第一个成员的偏移量将为零,并且不会存储在代码中,这将使代码更小。然后,较小的代码可以提高指令缓存的使用效率。 - sharptooth
加载地址+小的固定偏移指令非常常见,它们已经被高效地表示了。 - Macke
1
在x86上,如果偏移量不为零,你仍然必须存储32位的偏移量。无论它是否适合一个字节。 - sharptooth

2
在C#中,成员的顺序由编译器决定,除非您使用属性[LayoutKind.Sequential/Explicit],这将强制编译器按照您指定的方式布局结构/类。
据我所知,编译器似乎会最小化填充,同时按照数据类型的自然顺序对其进行对齐(即4字节int从4字节地址开始)。

没有人问到C#。 C ++编译器通常不会重新排序成员变量,因为它们不会尝试替你进行思考。 - oz10
作为有关于内存布局对性能影响的一般讨论,该评论确实增加了价值。CLR是一个非常常见的环境。 - Remus Rusanu
1
@ceretullis 我在问题中问到“它如何适用于其他语言”,我是一名C#程序员。因此,我对这个答案非常感兴趣。 - DevinB

1

我专注于性能和执行速度,而不是内存使用。 编译器在没有任何优化开关的情况下,将按照代码中声明的顺序映射变量存储区域。 想象一下

 unsigned char a;
 unsigned char b;
 long c;

出现了大问题?没有对齐开关,低内存操作等等,我们将会在您的DDR3 DIMM上使用一个64位字来使用无符号字符,另一个64位字用于另一个变量,而长整型则是不可避免的。

因此,每个变量都需要一次提取。

然而,打包或重新排序将导致一次提取和一次AND掩码以便使用无符号字符。

因此,在当前64位字内存机器上,对齐、重新排序等都是不可行的。我做微控制器的东西,在那里,打包/非打包的差异真的非常明显(谈论小于10MIPS处理器,8位字内存)

此外,众所周知,为了性能而调整代码所需的工程努力,除了好的算法指导您要做什么和编译器能够优化的内容之外,通常会导致毫无实际效果的烧胶。还有一些语法上存在问题的只写代码。

我看到的最后一步优化(在微处理器上,不认为PC应用程序可以做到)是将您的程序编译为单个模块,让编译器进行优化(更通用的速度/指针分辨率/内存打包等),并让链接器删除未被调用的库函数、方法等。

1
最后一步现在对所有人来说都非常容易实现,但是应该通过告诉编译器使用LTO(或您供应商的首选委婉语)来正确执行,而不是通过将整个源代码树重写或脚本化为单个巨大的翻译单元来实现。 - underscore_d

0

理论上,如果你有大对象,它可以减少缓存未命中。但通常最好将相同大小的成员分组在一起,这样可以更紧密地打包内存。


-1

我非常怀疑这与CPU的改进有任何关系 - 或许只是可读性。如果在同一组页面中执行在给定帧内执行的常用基本块,则可以优化可执行代码。 这是相同的想法,但不知道如何在代码中创建基本块。我猜编译器按其看到它们的顺序放置函数,没有进行任何优化,因此您可以尝试将常见功能放在一起。

尝试运行分析器/优化器。首先,您需要使用某些分析选项进行编译,然后运行程序。一旦分析了exe文件,它就会转储一些分析信息。使用此转储作为输入运行优化器。

我已经离开这个领域多年了,但工作方式并没有太大改变。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接