定数倍最適化の話

この記事はMCC Advent Calendar 2016 8日目の記事です．某実験の定数倍最適化について少し語ります．
UTC+9では9日になってしまいました．
MCC Advent Calendar 2016 - Adventar

背景

大学の学部の実験で乱数に関連する実験がありました．
その発展課題にモンテカルロ法を用いたシミュレーションの高速化があります．
これが結構面白く，1週間くらいは定数倍最適化を頑張っていました．
その時に試したいろいろなノウハウをまとめて見たいと思います．

この記事を実験の参考文献として扱うのはあまりオススメしない．

まず，この実験には重要な制約があります．1つ目は使用言語がCまたはC++に限る．
2つ目は，マルチスレッド禁止です．つまり，OpenMPなどを利用した高速化はできないということです．
3つ目は，MTのコードを勝手に書き換えてはいけないという点です.．(確か)
あと，当時のコンパイラのバージョンがg++ 4.3.4であったということです．

コード編

• 2の累乗の掛け算や割り算をbit演算で書き換える．

before

b=32*a;
d=c/16;

after

b=a<<5;
d=c>>4;

こうすることで，演算にかかるコストを減らして高速化できる．

• 非復元抽出

以下の記事を読むのがオススメ
非復元抽出の高速かつ実装が簡単な方法を考える - 睡眠不足？！
あとは，配列から$k$個の要素を繰り返し選ぶときに配列の初期化をせずに使うと良いです．

before

for(int loop=0;loop<T;++loop){
    //配列の初期化
    // 配列から要素を選択
}

after

//配列の初期化
for(int loop=0;loop<T;++loop){
    // 配列から要素を選択
}

• 条件判定をbit演算で表す．

例えば，cが3から10までの値を取りうるとして，を満たしていればOKとしてresを1足すことを考えます．
このときcから3を引くと，となり，下位2ビット目(0-indexed)が1になっていればOKという判定ができます．不等式条件が複数ある場合は，条件を全列挙してみると良いビットの条件が出てくるかもしれません．

コンパイルオプション編

対応するバージョンのリファレンスをよく読むと良いです．
https://gcc.gnu.org/onlinedocs/gcc.pdf

試しに，以下のようなソースコードを3.1 GHz Intel Core i7で走らせてみる．

#include <cstdio>
using namespace std;

/*
ここにMTのコードを貼る
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/mt19937ar.html
*/

const int T=1000000000;

int main(void){
	int res=0;
	init_genrand(0UL);

	for(int loop=0;loop<T;loop++){
		res+=genrand_int32()&1;		
	}

	printf("%.8f\n",1.0*res/T);
	return 0;
}

ひとまず， g++ a.cpp -o a.out でコンパイルしてtimeコマンドで測定すると10.232sとなります．

• 最適化オプションの有無

最適化オプションはいろいろあります．最近で，一番早いものだと-Ofastになります．
そこまでしなくても，-O2で十分です．
上記のコードは適当に最適化オプションをつけると，複雑なことはやってないのでどれも4.0sくらいになります．

• インライン化する関数のサイズ制限

-finline-limit=n をつけるとインライン化する関数のサイズの上限を変更できます．
g++ 5b.cpp -o 5b.out -Ofast -finline-limit=1000
とかやってみると，上記のコードが3.0sくらいになります．
なお，実行ファイルを解析して，MTの部分がインライン化されているかどうかは確かめていないです．

まとめ

なんか，ありきたりなものから変なものまでいろいろ書き連ねました．
もう少し，記憶を思い出して加筆修正できればと思います．
まだ，実際に使っている実験課題なのであまりヒントを出しすぎないようにという配慮です．