最大公約数をもっと高速に求める(その2)【cmova命令は遅い】

先週の記事の続きです。

最大公約数をもっと高速に求める(その1) - よーる

前回示したコードは、以下のようなものでした。

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修正))。

https://software.intel.com/sites/default/files/managed/9e/bc/64-ia-32-architectures-optimization-manual.pdf

bool q = m > tの場合、cmovbe命令とcmovnbe命令が使われ、レイテンシが二サイクルとなります。一方、bool q = t < mの場合、cmovb命令とcmovnb命令が使われ、レイテンシは一サイクルとなります。 これにより高速化したということのようでした。

なお、Haswell以前の場合、前者は2μOP、後者は3μOPに分解され、それらが直列に実行されるようなので、その差は小さくなるとはいえ、やはり性能に差が出ます。

まとめ

cmov命令は、使う条件によっては遅いことがあります。(はじめて知りました!) そのため、不等号の方向を変えるだけという一見等価な変換で高速化したり、遅くなったりすることがありえるようです。

今回の記事はもっとアルゴリズム的なところを掘り下げようと思っていたのですが、Intel社製CPUに最適化するだけの回になってしまいました。(でも25%高速化!)

まだまだ続きます。

*1:似たような命令なのに動作原理が違うあたり、x86はやはりCISCだなぁという感じです