先週の記事の続きです。
前回示したコードは、以下のようなものでした。
uint64_t gcd_impl( uint64_t n, uint64_t m ) { for( int i = 0; i < 10; ++i ) { uint64_t t = n - m; bool q = m > t; n = q ? m : t; m = q ? t : m; if( m == 0 ) { return n; } } return gcd_impl( m, n % m ); } uint64_t gcd( uint64_t n, uint64_t m ) { return n > m ? gcd_impl( n, m ) : gcd_impl( m, n ); }
コンパイラの気まぐれにつきあう
先ほど示したコードの
bool q = m > t;
を
bool q = t < m;
に変えてみましょう。私の環境では、25%ほど高速化しました。わけがわかりません。こんな高速化は誰も思いつけません。
アセンブリを確認しても、レジスタの割り付けは一切変わっておらず、単にcmp
命令のオペランドが逆転し、後続のcmov
命令の条件が変わるだけです。
他の環境でも試してみましたが、25%などという劇的な高速化ではないものの、10%程度は性能が向上するようです。
Intel社製CPUとつきあう
Intel Architecture Code Analyzerを使って調べてみたところ、Broadwell以降の場合、
cmovb
命令やcmovnb
命令は1つのμOPに変換される。実行は一サイクルで完了する。cmovbe
命令やcmovnbe
命令は2つのμOPに変換される。実行には合計で二サイクルかかる。cmova
命令はcmovnbe
命令の別名称。cmovna
命令はcmovbe
命令の別名称。
というようになっているようです*1。
Code Analyzerなんて持ち出さなくても、インテルの最適化リファレンスマニュアルに書いてあったようです(最後の方、C-17ページ。pdfとしては759ページ目796ページ目(2019/09/15修正))。
bool q = m > t
の場合、cmovbe
命令とcmovnbe
命令が使われ、レイテンシが二サイクルとなります。一方、bool q = t < m
の場合、cmovb
命令とcmovnb
命令が使われ、レイテンシは一サイクルとなります。
これにより高速化したということのようでした。
なお、Haswell以前の場合、前者は2μOP、後者は3μOPに分解され、それらが直列に実行されるようなので、その差は小さくなるとはいえ、やはり性能に差が出ます。
まとめ
cmov
命令は、使う条件によっては遅いことがあります。(はじめて知りました!)
そのため、不等号の方向を変えるだけという一見等価な変換で高速化したり、遅くなったりすることがありえるようです。
今回の記事はもっとアルゴリズム的なところを掘り下げようと思っていたのですが、Intel社製CPUに最適化するだけの回になってしまいました。(でも25%高速化!)
まだまだ続きます。