最近、奇妙な最適化解除(というか、最適化の機会を逃した)に遭遇しました。
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
ご覧のとおり、各シフトの前にメモリからの冗長な追加( 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
そのようなロードがループの外側に簡単に持ち上げられるとしても、ストアの前に常に再ロードする必要があるようです。主に、ホット コードの上に宣言されているローカル変数にポインターをキャッシュすることによって、これらの追加のストアを取り除くために多くのコードを書き直す必要があります。しかし、私はいつも、ポインタをローカル変数にキャッシュするなどの詳細をいじることは、コンパイラが非常に賢くなった今日では、間違いなく時期尚早の最適化に該当すると考えていました。しかし、どうやら私はここで間違っているようです。ホット ループ内でメンバー ポインターをキャッシュすることは、必要な手動の最適化手法であると思われます。
ベストアンサー1
this
皮肉なことに、との間にあるポインタ エイリアシングが問題のようですthis->target
。コンパイラは、次のように初期化したというかなり不愉快な可能性を考慮しています。
this->target = &this
その場合、 に書き込むとthis->target[0]
の内容が変更されますthis
(したがってthis->target
)。
メモリエイリアシングの問題は上記に限定されません。原則として、this->target[XX]
の不適切な値または不適切な値が与えられた場合の の使用は、XX
を指す可能性がありますthis
。
私は C に精通しており、キーワードを使用してポインタ変数を宣言することでこの問題を解決できます__restrict__
。