[解決済み] このポインタを使用するとホットループでおかしな最適化が起こる

質問

最近、奇妙な非最適化（というか最適化の機会を逸すること）に遭遇しました。

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

ご覧のように、さらに冗長な 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;
    }
}

このコードでも、追加のストアなしで "good" アセンブラが生成されます。つまり、私の推測では コンパイラは構造体のメンバ ポインタの負荷を上げることはできないので、そのようなホット ポインタは常にローカル変数に格納されるはずです。

• では、なぜコンパイラはこれらのロードを最適化できないのでしょうか。
• これを禁止しているのは C++ のメモリモデルでしょうか？それとも単に私のコンパイラの欠点なのでしょうか？
• 私の推測は正しいですか、または最適化が実行できない正確な理由は何ですか？

使用されているコンパイラは 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__ キーワードでポインタ変数を宣言することで解決できます。