使用此指针会在热循环中导致奇怪的去优化

Question

我最近遇到了一个奇怪的去优化(或者错过了优化机会).

考虑此函数可以有效地将3位整数数组解包为8位整数.它在每次循环迭代中解包16个int:

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!
 ...

如您所见,我们load在每次shift(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;
    }
}

这段代码也产生了"好"的汇编程序而没有额外的存储.所以我的猜测是:编译器不允许提升结构的成员指针的负载,所以这样的"热指针"应该总是存储在局部变量中.

• 那么,为什么编译器无法优化这些负载呢？
• 这是禁止C++内存模型吗？或者它只是我的编译器的缺点？
• 我的猜测是正确的还是无法执行优化的确切原因是什么？

在用编译器是g++ 4.8.2-19ubuntu1与-O3优化.我也尝试clang++ 3.4-1ubuntu3了类似的结果:Clang甚至能够使用本地target指针向量化方法.但是,使用this->target指针会产生相同的结果:在每个存储之前额外加载指针.

我查了一些类似的方法汇编,结果是一样的:似乎成员this总是有一个商店前被重新加载,即使这样的负载可以简单地外循环被吊起.我将不得不重写大量代码来摆脱这些额外的存储,主要是通过将指针自身缓存到一个在热代码之上声明的局部变量.但我一直在想摆弄这些细节,因为在当地变量中缓存指针肯定有资格在编译器变得如此聪明的情况下过早优化.但这似乎我错了.在热循环中缓存成员指针似乎是必要的手动优化技术.

Answer 1

指针别名似乎是问题,具有讽刺意味的是this和之间this->target.编译器考虑到您初始化的相当可怜的可能性:

this->target = &this

在这种情况下,写入this->target[0]将改变this(因此, - > - 目标)的内容.

内存别名问题不限于上述问题.原则上,this->target[XX]给定(in)适当值的任何使用都XX可能指向this.

我更精通C语言,可以通过使用__restrict__关键字声明指针变量来解决这个问题.

Answer 2

严格的别名规则允许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缓存到局部变量中,使用局部变量就不再可以使用别名.

Answer 3

这里的问题是严格的别名,它说我们可以通过char*进行别名,这样就可以防止编译器优化.我们不允许通过不同类型的指针进行别名,这是一种未定义的行为,通常在SO上我们看到这个问题是用户试图通过不兼容的指针类型进行别名.

将uint8_t实现为unsigned char似乎是合理的,如果我们在Coliru上查看cstdint,它包含stdint.h,其中typedefs uint8_t如下:

typedef unsigned char       uint8_t;

如果你使用了另一个非char类型,那么编译器应该能够优化.

这在C++标准部分3.10 Lvalues和rvalues草案中有所说明:

如果程序试图通过以下类型之一以外的glvalue访问对象的存储值,则行为未定义

并包括以下项目:

• char或unsigned char类型.

请注意,我在一个问题中发布了关于可能的解决方法的评论,该问题询问何时是uint8_t≠unsigned char？并且建议是:

然而,简单的解决方法是使用restrict关键字,或者将指针复制到从不采用其地址的局部变量,这样编译器就不必担心uint8_t对象是否可以对其进行别名.

由于C++不支持restrict关键字,你必须依赖编译器扩展,例如gcc使用__restrict__所以这不是完全可移植的,但另一个建议应该是.