我最近遇到了奇怪的取消优化(或者说错过了优化机会)。
考虑此功能,可以有效地将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中的方法时会发生什么:
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!
...
如您所见,我们在每次移位(load
)之前从内存中引入了额外的冗余mov rdx,QWORD PTR [rdi]
。似乎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;
}
}
此代码还会产生“良好的”汇编程序,而无需其他存储。所以我的猜测是:不允许编译器提升结构的成员指针的负载,因此,此类“热指针”应始终存储在局部变量中。
正在使用的编译器为g++ 4.8.2-19ubuntu1
,并且具有-O3
优化。我也尝试过clang++ 3.4-1ubuntu3
,结果相似:Clang甚至可以使用本地target
指针对方法进行矢量化。但是,使用this->target
指针会产生相同的结果:在每次存储之前都会额外增加指针的负载。
我检查了一些类似方法的汇编器,结果是相同的:似乎总是必须在存储之前重新加载this
的成员,即使可以简单地将这种负载提升到循环之外。我将不得不重写很多代码来摆脱这些额外的存储,主要是通过将指针自己缓存到在热代码上方声明的局部变量中来进行。 但是我一直认为摆弄诸如在本地变量中缓存指针之类的细节肯定会在当今编译器变得如此聪明的今天有资格进行过早的优化。但似乎我在这里错了。在热循环中缓存成员指针似乎是必要的手动优化技术。
指针别名似乎是个问题,具有讽刺意味的是,在this
和this->target
之间。编译器正在考虑您初始化的相当淫秽的可能性:
this->target = &this
在那种情况下,写入this->target[0]
会更改this
(因此this->target
)的内容。
内存别名问题不限于上述情况。原则上,给定(适当)值this->target[XX]
的任何对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
可能在您修改this->target
内容时被修改。
一旦this->target
被缓存到局部变量中,则该局部变量将不再可能使用别名。
这里的问题是strict aliasing ,它表示我们被允许通过char *进行别名,从而在您遇到的情况下阻止编译器优化。我们不允许通过其他类型的指针来别名,这将是未定义的行为,通常在SO上,我们会看到此问题,即用户尝试alias through incompatible pointer types。
将uint8_t实现为unsigned char似乎是合理的,如果我们查看cstdint on Coliru,它包含如下类型定义为uint8_t的stdint.h:
typedef unsigned char uint8_t;
如果使用其他非字符类型,则编译器应该能够进行优化。
这在C ++标准草案3.10
Lvalues和rvalues]中进行了介绍,其中说:
[如果程序尝试通过除以下任意一个以外的glvalue来访问对象的存储值,以下类型的行为未定义
并包括以下项目符号:
- 一个字符或无符号字符类型。
注意,我在一个问题中张贴了comment on possible work arounds,询问何时uint8_t≠无符号字符?],建议为:
但是,通常的解决方法是使用strict关键字,或者将指针复制到一个永远不会占用其地址的局部变量编译器无需担心uint8_t是否对象可以对其进行别名。
由于C ++不支持restrict
关键字,因此您必须依赖编译器扩展,例如gcc uses __restrict__,因此这不是完全可移植的,但其他建议应该是。