我最近遇到了一个奇怪的去优化(或者说错过了优化机会)。
考虑使用此函数将 3 位整数数组高效解包为 8 位整数。它在每次循环迭代中解压缩 16 个整数:
void unpack3bit(uint8_t* target, char* source, int size) {
while(size > 0){
uint64_t t = *reinterpret_cast<uint64_t*>(source);
target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;
target[3] = (t >> 9) & 0x7;
target[4] = (t >> 12) & 0x7;
target[5] = (t >> 15) & 0x7;
target[6] = (t >> 18) & 0x7;
target[7] = (t >> 21) & 0x7;
target[8] = (t >> 24) & 0x7;
target[9] = (t >> 27) & 0x7;
target[10] = (t >> 30) & 0x7;
target[11] = (t >> 33) & 0x7;
target[12] = (t >> 36) & 0x7;
target[13] = (t >> 39) & 0x7;
target[14] = (t >> 42) & 0x7;
target[15] = (t >> 45) & 0x7;
source+=6;
size-=6;
target+=16;
}
}
这是为部分代码生成的程序集:
...
367: 48 89 c1 mov rcx,rax
36a: 48 c1 e9 09 shr rcx,0x9
36e: 83 e1 07 and ecx,0x7
371: 48 89 4f 18 mov QWORD PTR [rdi+0x18],rcx
375: 48 89 c1 mov rcx,rax
378: 48 c1 e9 0c shr rcx,0xc
37c: 83 e1 07 and ecx,0x7
37f: 48 89 4f 20 mov QWORD PTR [rdi+0x20],rcx
383: 48 89 c1 mov rcx,rax
386: 48 c1 e9 0f shr rcx,0xf
38a: 83 e1 07 and ecx,0x7
38d: 48 89 4f 28 mov QWORD PTR [rdi+0x28],rcx
391: 48 89 c1 mov rcx,rax
394: 48 c1 e9 12 shr rcx,0x12
398: 83 e1 07 and ecx,0x7
39b: 48 89 4f 30 mov QWORD PTR [rdi+0x30],rcx
...
它看起来相当有效。只需一个 shift right
后跟一个 and
,然后是一个 store
到 target
缓冲区。但是现在,看看当我将函数更改为结构中的方法时会发生什么:
struct T{
uint8_t* target;
char* source;
void unpack3bit( int size);
};
void T::unpack3bit(int size) {
while(size > 0){
uint64_t t = *reinterpret_cast<uint64_t*>(source);
target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;
target[3] = (t >> 9) & 0x7;
target[4] = (t >> 12) & 0x7;
target[5] = (t >> 15) & 0x7;
target[6] = (t >> 18) & 0x7;
target[7] = (t >> 21) & 0x7;
target[8] = (t >> 24) & 0x7;
target[9] = (t >> 27) & 0x7;
target[10] = (t >> 30) & 0x7;
target[11] = (t >> 33) & 0x7;
target[12] = (t >> 36) & 0x7;
target[13] = (t >> 39) & 0x7;
target[14] = (t >> 42) & 0x7;
target[15] = (t >> 45) & 0x7;
source+=6;
size-=6;
target+=16;
}
}
我认为生成的程序集应该完全相同,但事实并非如此。这是其中的一部分:
...
2b3: 48 c1 e9 15 shr rcx,0x15
2b7: 83 e1 07 and ecx,0x7
2ba: 88 4a 07 mov BYTE PTR [rdx+0x7],cl
2bd: 48 89 c1 mov rcx,rax
2c0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
2c3: 48 c1 e9 18 shr rcx,0x18
2c7: 83 e1 07 and ecx,0x7
2ca: 88 4a 08 mov BYTE PTR [rdx+0x8],cl
2cd: 48 89 c1 mov rcx,rax
2d0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
2d3: 48 c1 e9 1b shr rcx,0x1b
2d7: 83 e1 07 and ecx,0x7
2da: 88 4a 09 mov BYTE PTR [rdx+0x9],cl
2dd: 48 89 c1 mov rcx,rax
2e0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
2e3: 48 c1 e9 1e shr rcx,0x1e
2e7: 83 e1 07 and ecx,0x7
2ea: 88 4a 0a mov BYTE PTR [rdx+0xa],cl
2ed: 48 89 c1 mov rcx,rax
2f0: 48 8b 17 mov rdx,QWORD PTR [rdi] // Load, BAD!
...
如您所见,我们在每个班次 (mov rdx,QWORD PTR [rdi]
) 之前从内存中引入了一个额外的冗余 load
。似乎 target
指针(现在是成员而不是局部变量)在存储到它之前必须始终重新加载。 这大大减慢了代码速度(在我的测量中约为 15%)。
首先,我认为 C++ 内存模型可能强制成员指针不能存储在寄存器中,但必须重新加载,但这似乎是一个尴尬的选择,因为它会使许多可行的优化变得不可能。所以我很惊讶编译器没有将 target
存储在此处的寄存器中。
我尝试自己将成员指针缓存到局部变量中:
void T::unpack3bit(int size) {
while(size > 0){
uint64_t t = *reinterpret_cast<uint64_t*>(source);
uint8_t* target = this->target; // << ptr cached in local variable
target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;
target[3] = (t >> 9) & 0x7;
target[4] = (t >> 12) & 0x7;
target[5] = (t >> 15) & 0x7;
target[6] = (t >> 18) & 0x7;
target[7] = (t >> 21) & 0x7;
target[8] = (t >> 24) & 0x7;
target[9] = (t >> 27) & 0x7;
target[10] = (t >> 30) & 0x7;
target[11] = (t >> 33) & 0x7;
target[12] = (t >> 36) & 0x7;
target[13] = (t >> 39) & 0x7;
target[14] = (t >> 42) & 0x7;
target[15] = (t >> 45) & 0x7;
source+=6;
size-=6;
this->target+=16;
}
}
这段代码也产生了“好”的汇编程序,而无需额外的存储。所以我的猜测是:编译器不允许提升结构的成员指针的负载,所以这样的“热指针”应该始终存储在局部变量中。
那么,为什么编译器无法优化这些负载呢?
是 C++ 内存模型禁止这样做吗?或者它只是我的编译器的一个缺点?
我的猜测是否正确或者无法执行优化的确切原因是什么?
使用的编译器是具有 -O3
优化的 g++ 4.8.2-19ubuntu1
。我还尝试了 clang++ 3.4-1ubuntu3
并得到了类似的结果:Clang 甚至能够使用本地 target
指针对方法进行矢量化。但是,使用 this->target
指针会产生相同的结果:在每次存储之前额外加载指针。
我检查了一些类似方法的汇编程序,结果是相同的:似乎 this
的成员总是必须在存储之前重新加载,即使这样的加载可以简单地提升到循环之外。我将不得不重写大量代码来摆脱这些额外的存储,主要是通过自己将指针缓存到在热代码上方声明的局部变量中。 但我一直认为,在编译器变得如此聪明的今天,摆弄诸如在局部变量中缓存指针之类的细节肯定有资格进行过早优化。但这里似乎我错了。在热循环中缓存成员指针似乎是一种必要的手动优化技术。
this->
只是语法糖。问题与变量(本地与成员)的性质以及编译器从这一事实中推断出的事物有关。
指针别名似乎是问题所在,讽刺的是在 this
和 this->target
之间。编译器正在考虑您初始化的相当淫秽的可能性:
this->target = &this
在这种情况下,写入 this->target[0]
将改变 this
的内容(因此,this->target
)。
内存混叠问题不仅限于上述情况。原则上,给定(不)适当的 XX
值的 this->target[XX]
的任何使用都可能指向 this
。
我更精通 C,这可以通过使用 __restrict__
关键字声明指针变量来解决。
严格的别名规则允许 char*
对任何其他指针进行别名。所以 this->target
可以与 this
别名,并且在您的代码方法中,代码的第一部分,
target[0] = t & 0x7;
target[1] = (t >> 3) & 0x7;
target[2] = (t >> 6) & 0x7;
实际上是
this->target[0] = t & 0x7;
this->target[1] = (t >> 3) & 0x7;
this->target[2] = (t >> 6) & 0x7;
因为当您修改 this->target
内容时,可能会修改 this
。
一旦 this->target
被缓存到局部变量中,别名就不再可能与局部变量一起使用。
char*
或 void*
时,一定要在写入之前将其缓存在局部变量中?
char*
时,不需要作为成员。
这里的问题是 strict aliasing ,它表示我们可以通过 char* 进行别名,因此在您的情况下会阻止编译器优化。我们不允许通过不同类型的指针来别名,这将是未定义的行为,通常在 SO 我们看到这个问题是用户试图 alias through incompatible pointer types。
将 uint8_t 实现为 unsigned char 似乎是合理的,如果我们查看 cstdint on Coliru,它包括 stdint.h,其 typedef 如下所示 uint8_t :
typedef unsigned char uint8_t;
如果您使用了另一种非字符类型,那么编译器应该能够进行优化。
这在草案 C++ 标准部分 3.10
Lvalues and rvalues 中有介绍,其中说:
如果程序尝试通过以下类型之一以外的 glvalue 访问对象的存储值,则行为未定义
并包括以下项目符号:
char 或 unsigned char 类型。
请注意,我在询问uint8_t ≠ unsigned char?的问题中发布了一个comment on possible work arounds,建议是:
然而,简单的解决方法是使用restrict 关键字,或者将指针复制到一个从不获取地址的局部变量,这样编译器就不必担心uint8_t 对象是否可以给它起别名。
由于 C++ 不支持 restrict 关键字,因此您必须依赖编译器扩展,例如 gcc uses __restrict__ 所以这不是完全可移植的,但其他建议应该是。
不定期副业成功案例分享
target
从uint8_t
更改为uint16_t
(以便启动严格的别名规则)改变了它。使用uint16_t
,负载总是被优化掉。this
的内容不是你的意思(它不是变量);你的意思是改变*this
的内容。