技術系備忘録​/C++​/最適化小手先テクニック​/シフト演算の乗除算に注意すべし :: シンクリッジ

通説ですが、"２のべき乗での乗除算は、シフト演算（ビットシフト）で処理したほうが早い"というのがあります。
CPUが高速化されたといっても、乗除算命令はそれなりに遅い処理で、比較するまでもなくシフト演算のほうが高速です。(List1)

• List1

  int Test(int n)
  {
  //  return n * 8;		// 掛け算ではなく
  	return n << 3;		// ビットシフトを使う
  }

８倍する掛け算なのですが、２進数の仕組みを利用し、ビットシフトすることで８倍という処理を実現しています。
これは確かに有効な手段であり、古くからあるテクニックで、まったく問題ないと思います。

しかし、昨今のコンパイラは、わざわざシフト演算で記述をしなくても、シフト演算を使うコードを吐き出します。(VisualC++6で確認)
こうなると、シフト演算で記述しようと、掛け算で記述しようと、最適化の観点からはどっちでも良いということになります。

　・
　・
　・

というわけで、以上でこのネタは終わりでもよいのですが、ちょっとツッコンだ個人的見解を述べたいと思います。

自分は、昨今の最適化コンパイラを使う場合、素直に掛け算で記述するほうが良いと思っています。
理由は、コードの見易さと間違いの避け易さからです。

２のべき乗という単純な場合であれば、どちらの書き方であってもコードの見易さは変わらないと思いますが、それ以外の数で処理する場合、コードの見易さと間違いやすさは劇的に変わります。

１５倍する例を見てみます。(List2)

• List2

  int Test(int n)
  {
  //  return n * 15;
  	return ( n << 4 ) - n;
  }

これは、掛け算をビット演算に分解することで、掛け算命令を使わずに処理速度を稼ぐという、昔からある小手先テクニックです。１６倍から１倍を引くことで１５倍を実現しています。

この場合、最適化の面から言えば問題ないかもしれませんが、コードの見易さは大きく犠牲になってますし、１５倍をビット演算に分解する過程でミスを犯すかもしれません。

さらに、最適化の面からも、実は正解ではなさそうです。
List2 をコンパイルした結果（アセンブラ）が List3 です。

• List3

  int Test(int n)
  	mov  eax, DWORD PTR n
  	lea  eax, DWORD PTR [eax+eax*2]		// 3倍して
  	lea  eax, DWORD PTR [eax+eax*4]		// 5倍する
  }

期待した結果とは明らかに違いますが、これがコンパイラの最適化の結果です。

つまり、見辛い上に最適ではないコードを記述してしまったことになります。
（というか、どっちの記述でも出力されるアセンブラは List3 になります。ビット演算で記述してもコンパイラ(VisualC++6)は最適化してくれました。全然違う書き方でも同じように解釈するとは優秀です。）

以上の結果からわかるように、定数の乗除算程度は、素直にコンパイラ任せにするほうが、コードの見易さも犠牲にせず、しかも最適な結果になる訳です。

もちろん、コンパイラが優秀であればという条件が必要になるので、不安であれば念のため調べたほうが良いと思います。

/*
VisualC++の最適化性能がどんなもんか色々試しましたが、定数の乗除算についてはかなり詰められているようです。
とはいえ、CPU特性などを考慮すると、どういうアセンブラが最速なのかということは、一見しただけじゃ分かりません。
今回の例でも、コンパイラの出力が最速なのかどうかは確認も検証もしてません。しかし必要もないかなと思います。
*/

なお、一つ注意点があります。List4をご覧下さい。

• List4

  int Test(int n)
  {
  	return n / 8;
  }

一見何も問題なさそうです。コンパイラはシフト演算するアセンブラを出力してくれそうに思えます。
しかし、この場合は期待通りにはなりません。
それは型が int (符号付) だからです。単純にビットシフトすることは出来ないため、けっこう面倒なアセンブラが出力されます。

どうすればよいかというと、符号付として処理する場合はどうしようもありません。
しかし、"マイナス値の引数はあり得ない"という前提があるのであれば、List5 のように書くと、ビット演算のアセンブラを出力させることが出来ます。

• List5

  int Test(int n)
  {
  	return (unsigned int)n / 8;
  }

unsigned int にキャストすることで、符号無しで処理しなさいとコンパイラに教えています。
もちろん、このキャストによるオーバーヘッドというのはありません。変数 n を符号無しとして扱えとコンパイラに教えているだけです。

まとめとして。
昨今の最適化コンパイラのおかげで、定数の乗除算はどのように書いても最適化されたアセンブラが吐き出されるようですので、それを期待して素直な乗除算コードを書いたほうが良いと思います。
もちろん、最適化されないコンパイラや環境を使う場合、ビット演算でのコーディングは有効な手段だと思います。
List2 のような往年のテクニックも十分活かせると思いますので、知っておくことは損ではないと思います。

なお、言うまでもないかもですが、本ネタは整数演算を前提に書いています。浮動小数点演算についてはまったく当てはまりませんのでご注意下さい。