「サイボウズ・アドベントカレンダー」の4日目です（これまでの記事一覧）。どうやら三日坊主は免れたようです（笑）。
(0) はじめに
こんにちは。サイボウズ・ラボの川合秀実です。私は主にサイボウズ製品の高速化のお手伝いをしています。しかし先日、製品とは関係ないものを高速化したので、今日はそれを発表します。
サイボウズには社内勉強会がいくつかあって、その中にはC++の勉強会もあります。私はサイボウズの勉強会に参加するのが好きなので、このC++の勉強会に参加してみました。この勉強会では、「数独」というパズルを解くプログラムをC++で書いてみよう、というのが最初のテーマでした。参加者各自がプログラムを書き、翌週にお互いにレビューしあうということが行われました。
ここで私はやらかしてしまいました。ええ、そうです、高速化してしまったのです！ 言うまでもないですが、誰もこんなことは望んでいません。そもそもそういう勉強会ではないはずです。・・・しかし、目の前に適当なプログラムがあって、しかも高速化できそうだと思いついてしまって、さらに作業時間も捻出できそうになってしまったら、私の性格上、これはやるしか選択肢がないのです（笑）。・・・この高速化は十分にうまくいって、本社の人たちに私の高速化への執念と実力をアピールできました。
そしてこの顛末をサイボウズ・ラボ社内で報告したところ、それは面白いねということになり、これを元に記事を一つ書いてよいということになりました。・・・となれば、それを理由にさらに業務時間を使って、このプログラムの最適化にいそしんでもよいというわけです。短い時間でしたが、久しぶりに本気でアセンブラしました。最盛期ほどではないかもしれませんが、まだ腕は落ちていないなと思いました。
(1) 今回のお題
数独のルールをご存知でしょうか・・・ご存知ない方は、Wikipediaをご覧ください。→数独
勉強会のお題では、与えられた問題に対して、解が1つしかない場合は解を出力し、それ以外の場合は解なしとせよ、とされていました。このルールでは、超手抜きでプログラムを書いても実用上問題のない速度で（＝一瞬で）答えが出てしまいます。これは実に面白くありません。そこで私は勝手に問題を拡張し、解が複数ある場合には解の個数を求めてもよいとしました。それどころか、解にはシリアルナンバーを振り、i番目の解からj番目の解までを表示するなんてことも可能にしました。そして9x9すべてが空欄の問題を与えたら・・・すごく時間がかかりそうですね。わくわくが止まりません！（註：高速化屋は、強い敵に出会うほどわくわくする）
と思ったら、9x9がすべてが空欄だと、解の個数は6.6e+21を超えるらしく、これは1週間やそこらでは終わる気がしません。そもそもint32の範囲で収まるくらいが自分のスキルを考えると適当だよなと思い直し、以下の問題を解かせることを自分に課しました。
1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
この問題の解の個数は、1300499712で、これは32bitのintでも十分に数えられる範囲です。4行目の2がないと問題としてはもっときれいですが、そうすると long long で数えなければいけなくて、32bitが好きな私としては、ちょっと気乗りしません。
(2) sudoku0.cpp － C++でできるだけ簡潔に
さて最初に紹介するプログラムは、ほとんど工夫のない数独解法プログラムです。工夫しているところは、1,2,3,4,...という数字を内部では直接扱わず、1,2,4,8,...と2のべきに置換し、この数値のOR演算（ビット演算）をすることで、入れられる数字の候補をそこそこ高速に見つけています。それ以外の工夫はできるだけしないようにして、ソースコードの行数が短くて簡潔になることを心がけました。コメントを除けば205行で書けました。→sudoku0.cpp
prompt>sudoku0 q_kawai.txt -1
とすると解の個数を求めるモードになり、私のマシンでは1960.5秒で答えが出ました。32分くらいです。最後の-1の数字を正の数にすれば、解のシリアルナンバーが指定された数字のものを表示してくれます。この場合は大きな数字を指定しない限り一瞬です。数字を省略するか、もしくは0にすれば、最初から5個までの解を表示してくれます。
勉強会では私以外で一番頑張った人でも、シングルスレッドで2万秒はかかると言っていました。まあマシンの違いもあると思うので簡単には比べられませんが、大雑把に言ってこの段階でも普通よりは10倍くらい速いというわけです。きっとこのプログラムがビット演算をうまく使っているからでしょう。・・・ここで私はこの実行環境や使ったコンパイラなどを明らかにするべきなのですが、それは後述します。
高速化するには、マルチスレッド化すればいいとか、問題の対称性を活用すべきなのではないかと思いつきましたが、私としてはこれはそもそも「与えられた問題に対して、解が1つしかない場合は解を出力し、それ以外の場合は解なしとせよ」という課題を勝手に拡張してやっているわけで、自分の拡張のためにしか必要のないアルゴリズムをつけたくはありません。勉強会で説明するのもめんどくさいじゃないですか。ということで、それらについては今回はパスしました。
(3) sudoku1.cpp － 常識的な範囲で最適化
それではどうやって高速化するかですが、関数checkCell()を改造することにしました。これはsudoku0では、こうなっていました（要点を分かりやすくするためにtypedefを展開し整理してあります）。
int SolveSudoku::checkCell(int x0, int y0) const
{
int flags = 0;
for (int i = 0; i < BoardSize; i++)
flags |= board[y0][i] | board[i][x0];
x0 -= x0 % BoardSizeSub;
y0 -= y0 % BoardSizeSub;
for (int y = 0; y < BoardSizeSub; y++) {
for (int x = 0; x < BoardSizeSub; x++)
flags |= board[y0 + y][x0 + x];
}
return flags;
}
これをこうしました。
int SolveSudoku::checkCell(int i) const
{
int flags = 0;
for (int j = 0; j < (BoardSize - 1) * 3 - (BoardSizeSub - 1) * 2; j++)
flags |= board[table[i][j]];
return flags;
}
図を描いて調べるとわかるのですが、9x9の数独では、ある空きマスに注目すると、そのマスと同じ数字になってはいけないマスが20あります。縦で8個、横で8個、ボックスで8個なのですが、ボックスのうちの4マスは縦や横と重なっているので、二度チェックするのは無駄なのです。こうして20という数字が出ます。上のループもBoardSize=9のときは20回まわるようになっています。
プログラムでは簡単化のために、board[]を一次元配列にして添え字を (y * BoardSize + x) で計算しています。そしてtable[i][j]については本計算に入る前にあらかじめ計算しておくのです。→sudoku1.cpp
さてどのくらい速くなったでしょうか。sudoku1では1628.8秒(1.20倍速)になりました。まあちょっと速くなったという感じです。とりあえず高速化の第一歩としては悪くないです。
(4) sudoku2.cpp － ループを展開
次は何をやるのかというと、ループを展開してしまいます。
int SolveSudoku::checkCell(int i) const
{
/* (BoardSize - 1) * 3 - (BoardSizeSub - 1) * 2 == 20 なので全部展開してしまう */
return board[table[i][ 0]] | board[table[i][ 1]] | board[table[i][ 2]] | board[table[i][ 3]] |
board[table[i][ 4]] | board[table[i][ 5]] | board[table[i][ 6]] | board[table[i][ 7]] |
board[table[i][ 8]] | board[table[i][ 9]] | board[table[i][10]] | board[table[i][11]] |
board[table[i][12]] | board[table[i][13]] | board[table[i][14]] | board[table[i][15]] |
board[table[i][16]] | board[table[i][17]] | board[table[i][18]] | board[table[i][19]];
}
うわーという感じですね！（笑）。jに対するループがなくなれば、CPUはjという変数を加算したり20と比較したりする作業から解放されます。この書き方ならflagsという変数も更新しないで済みます。その分速くなります。他にももう一か所別の関数で9回ループする場所があるのですが、そこもループ展開しました。あとおける数字が1つしかない場合というのが頻発する気がしたので、場合分けをして、その場合は処理を単純化しました。これらの結果として行数が増えて気が付けば241行くらいになっています。→sudoku2.cpp
しかし効果は大きくてsoduku2では855.7秒(2.29倍速)で答えが出ます。この程度のソース増加でこれくらいの成果が出るのは、結構いいほうです。やったね！
(5) sudoku3.cpp － C++だけでできる限界？
ここまではまあ常識的な高速化だと思います。ここからが病的です。私の好きな改造が始まります。こんなことをしてみました。
int SolveSudoku::checkCell(int i) const
{
switch (i) {
case 0:
return board[ 0] | board[ 1] | board[ 2] | board[ 3] | board[ 4] |
board[ 5] | board[ 6] | board[ 7] | board[ 8] | board[ 9] |
board[10] | board[11] | board[18] | board[19] | board[20] |
board[27] | board[36] | board[45] | board[54] | board[63];
case 1:
return board[ 0] | board[ 1] | board[ 2] | board[ 3] | board[ 4] |
board[ 5] | board[ 6] | board[ 7] | board[ 8] | board[ 9] |
board[10] | board[11] | board[18] | board[19] | board[20] |
board[28] | board[37] | board[46] | board[55] | board[64];
（中略）
case 80:
return board[ 8] | board[17] | board[26] | board[35] | board[44] |
board[53] | board[60] | board[61] | board[62] | board[69] |
board[70] | board[71] | board[72] | board[73] | board[74] |
board[75] | board[76] | board[77] | board[78] | board[79];
}
return 0; /* dummy */
}
ひどいですね！（笑）。どうせ81通りしかないからswitch-caseで全部書いてしまったというわけです。これでCPUはtable[i][]を参照しないで済みます。きっと速くなります。
もちろんこれは手書きではありません。そんなことをしたら時間もかかりますし、間違えてしまいます。ということで makeCheckCell() という33行の関数を作って、その出力結果をソースに貼り付けて作りました。ソースは682行に膨れました。相変わらず処理内容の本質的には200行程度なのですが。→sudoku3.cpp
さてどれほど速くなったかなと期待して実行してみたら・・・728.3秒(2.69倍速)でした。あれえ、もう少しいい数字が出ると期待していたのに。病的な努力の割には大したことない・・・。
でもC++だけでできる範囲の最適化はこれ以上思いつけません。
(6) sudoku4.cpp － 一部をアセンブラ化
さて最後です。checkCell()とcount()の2つの関数をアセンブラで書くことにしました。その際にはもちろんsudoku3に相当する展開もしました。またcount()内の展開していた部分は、ループに戻しました。でもsudoku1の時のループとはまた少し違ったループです。これはアセンブラでえこひいきをしているのではなくて、同じことはsudoku3の時もC++レベルで試してみたのですが、C++ではこのループにするとかえって遅くなってしまったのです。それでやめました。アセンブラの時は、まあちょっとだけ新ループのほうが速かったので展開の代わりに使うことにしました。
私はアセンブラが一番得意です。とはいえ展開部分で間違えると悲しいので、今回もmakeAsm()という関数を作って、これでプログラムを作っています。C++部分は380行になりました。そしてこのmakeAsm()でアセンブラ部を作らせると、1965行のアセンブラ用のソースコードも出てきます。→sudoku4.cpp
ちなみに、g++がsudoku3で出力していたコードは、こんな感じになっていましたが、
L59:
movl (%ecx), %edx
movl 4(%ecx), %eax
orl %edx, %eax
movl 8(%ecx), %edx
orl %edx, %eax
movl 12(%ecx), %edx
orl %edx, %eax
movl 16(%ecx), %edx
orl %edx, %eax
movl 20(%ecx), %edx
orl %edx, %eax
movl 24(%ecx), %edx
orl %edx, %eax
movl 28(%ecx), %edx
orl %edx, %eax
movl 32(%ecx), %edx
orl %edx, %eax
（中略）
makeAsm()の結果では同じ部分がこうなっています。
case00:
MOV EAX,[ESI+ 0]
MOV ECX,[ESI+ 4]
MOV EDX,[ESI+ 8]
OR EAX,[ESI+ 12]
OR ECX,[ESI+ 16]
OR EDX,[ESI+ 20]
OR EAX,[ESI+ 24]
OR ECX,[ESI+ 28]
OR EDX,[ESI+ 32]
（中略）
gas形式とIntel形式でちょっと分かりにくいかもしれませんが、sudoku4のほうでは、MOV命令は最初の3個だけで、あとはOR命令しか使っていません（中略の部分で、EAXに結果を集約します）。それに対しg++はメモリから値を取ってくる回数の分だけMOVがあり、ORはレジスタ間で行うようになっています。つまり「命令数的には」sudoku4のほうが有利なのです。・・・でもまあ実際は、最近のCPUではこんな最適化はほとんど効果がなくて、sudoku4の書き方は新しくないCPUでもそれなりの速度で動くためのテクニックでしかないですが（苦笑）。まあ気休めということで。
さあ成果は・・・sudoku4は327.2秒(5.99倍速)になりました。おおこれは速い！
(7) コンパイラをうまく選ぶ
ここで一つ種明かしをしなければいけません。というのは私の使っているコンパイラのバージョンがかなり古いのです。gccの3.4.5です。古いコンパイラを使えば、最適化能力があまり高くないので、人間があれこれ工夫した成果は出やすくなります。・・・でもこれは自分の高速化能力を高く見せたいからではなくて、もっとまともな理由があってのことなので、それを説明させてください。
私はgccが好きなのでよく使うのですが、gccはバージョンが変わるとコード生成のクセが大きく変わります。以前問題なく動いたコードが動かなくなることさえたまにあるくらいです。そういうのはOSを趣味で作っている私にとっては大問題で、正直、多少速くなるかどうかなんてことはどうでもよくて、とにかくいつも安定してそれなりに動くバイナリを作ってくれればいいのです。最新コンパイラはおせっかいなのです。
それに私の場合、もし速くしたいプログラムがあれば、それはコンパイラに頼らずに自分で速くするわけです、今回のように。やる気があるときはアセンブラも使ってしまいます。だからコンパイラに速さは求めていないのです。
しかし一方で、私以外の普通の人はアセンブラなんかやらないでしょうし、sudoku3まで自力でやる人も少ししかいないでしょう。そもそも人生は有限で、こんなことに時間をかけている暇があったら、他にやりたいことがたくさんあるのでしょう。私は逆なので、むしろこんなことに時間をかけたいのですけどね（笑）。
ということで、sudoku0～3について、他のコンパイラでやったらどうなるかを計測したので発表します。実はここからが有用な情報です。・・・だって、数独のパズルを解く時間が何秒になったとか、はっきり言ってそんなのどうでもいいじゃないですか。どこのコンパイラがどのくらい優秀なのか、それが多くのプログラマの関心事ですよね！
環境
Windows7 Professional 64bit版
Core i7-2600 @ 3.40GHz
単位は秒 それぞれ sudoku* q_kawai.txt -1 の実行時間を表しています
gcc 3.4.5 gcc 4.7.2 VC++2010
sudoku0 1960.5 1190.5 1247.8 C++でできるだけ簡潔に書いたもの
sudoku1 1628.8 1052.2 1249.7 常識的な範囲で最適化したもの
sudoku2 855.7 710.3 682.5 さらにループ展開したもの
sudoku3 728.3 674.1 536.3 switch-caseの乱用
sudoku4 327.2 count()等をアセンブラ化
最適化オプションは次の通りです
gcc 3.4.5 : -O2 のみ（-O3だとかえって遅くなったので） 32bitコードを生成させています
gcc 4.7.2 : -O3 -mtune=corei7 -march=corei7 これも32bitコードを生成させています（ミスです）
VC++2010 : /Ox /Oi /Ot /Oy /favor:INTEL64 /GA (正確なバージョン: 16.00.40219.01 for x64)
gcc 4.7.2はたぶん私が32bit版を間違って入れてしまい、それで64bitコードを出してくれないのだと思います。今からせっせと私がやりなおせばいいのですが、さすがにくたびれてきたので、興味がある人がやっていただければと思います。32bit版のままでも傾向はわかると思います。
・・・どうですか。コンパイラによってかなりばらつきがあるのが分かりますね。まずすべてのケースで、私が愛用しているgcc 3.4.5の-O2モードはもっとも低速でした。そしてg++はsudoku0とsudoku1に強く、sudoku2やsudoku3ではVC++が最速でした。しかしVC++のsudoku3であっても、sudoku4には及びませんでした。十分な差もついています。つまり（今のところは）結局コンパイラは人間には勝てないということです。まだまだ私も現役ですね。
またsudoku0の段階では、一番速いものと一番遅いものの比は1.65倍ほどありますが、sudoku3になると1.36倍ほどに縮小します。おそらくsudoku4レベルになれば、ほとんど差はなくなるでしょう（試してはいませんが）。
さてこの表をどう見るかですが、まずあなたがどのくらいのレベルまで高速なコードを書けるのか、から考えてください。sudoku4レベルなら、コンパイラはどれでも同じです。気にすることはありません。sudoku2～3レベルならVC++がよさそうです。きっとVC++はプロ向けなのです。人間が容易にできるところはあまりがんばらない代わりに（＝そこまでは人間任せで）、そこまで人間にやっておいてもらえたら、あとはあらん限りの努力をして高速化してくれるのです。・・・一方で、g++はsudoku0～1レベルのソースが得意のようです。素直に書くのが好きで、それ以上がんばるのがめんどくさいのならg++がよきに計らってくれるというわけです。・・・まあなんにせよ、普通に考える限りg++の3.4.5はあり得ないですね。どうもすみません。
ちなみにsudoku4のアセンブラ部は32bitコードしか使っていません。それどころかi386時代の命令セットしか使っていません。それでもここまで速くできるのです。64bitモード用に書けばもう少し速くなりそうですし、32bitを超えて数えられるようになります。その代わり、64bitのCPUとOSを持っている人にしか実行できないバイナリになってしまいますが。
(8) 追加情報
このデータを出したら、サイボウズ・ラボの光成がもっといろいろなコンパイラで試してくれました。-1だと計測に時間がかかりすぎるので、2000万を指定したそうです。測定値の単位は秒です。
gcc 4.6.3(linux), VC2012(win7), icl 12.0(win7)
オプション：
g++ -Ofast -DNDEBUG -fomit-frame-pointer -march=native -msse4
cl /Ox /Oi /Ot /Oy /favor:INTEL64 /GA
icl /fast /EHs /DNDEBUG sudoku2.cpp /Qunroll-aggressive
環境：
sandy-bridge i7-2600 3.4GHz
g++のみWin7上のVMware上のlinuxで実行
VC, iclはnative実行
icc vc gcc
sudoku2 q_kawai.txt 20000000 10.048 10.982 10.710
sudoku3 q_kawai.txt 20000000 9.144 8.69 9.68
→ profile optimization 8.364 8.3 7.580
（↓これはビルドしなおすことなく実行・比較用）
sudoku4 q_kawai.txt 20000000 5.119
sudoku3の結果を見ると、ここでもVC++が健闘しています。しかし驚くべきはg++のプロファイル最適化適用時の結果で、これはまずコンパイル時にプロファイルするようにオプションを付けてプログラムを実行して、そのあとそのプロファイル情報によりもう一度バイナリを生成する、ということをするそうです。私はやったことがないので「そんな時代になったのか！」とむしろ驚くのですが、しかしこれをやった時のg++の性能はすごいですね。アセンブラを全く使っていないのに、アセンブラ版に1.48倍のところまで迫っています。1.62倍までしか行けなかったVC++の結果よりもかなりいいです。・・・となると、g++はsudoku0～3のすべてで、一番うまくやっていると言えるのかもしれません。
でも光成によれば、g++のプロファイル最適化がこれほどの成果を上げるのは珍しいとのことなので、過信しすぎないようにしてください。
追記：
光成によると、VC++でもcheckCell()に__forceinline属性を付けることで、g++のプロファイル最適化と同じくらいの結果が出たとのことです。VC++はさすがです。・・・まあ__forceinlineはVC++でしか使えない記述なので、これをC++の範囲内での改良と言っていいのかどうかについては、少し悩ましいところではありますが・・・。
(9) さいごに
まとめ：
- （少なくともこの例では）素直なプログラムに対して、使用言語やアルゴリズムを変更することなく、ありふれた高速化テクニックを適当に組み合わせたり、使用するコンパイラをうまく選ぶだけでも、実行速度は4倍も向上した。
- → 一部のみアセンブラ化することでさらに1.48倍速になった。
- 世間では高速化したくなると、すぐに並列化だとか、難解なアルゴリズムだとか、ハードウェアの増強とか、記述言語の変更のような「派手な改良」を検討してしまうけど、それより前にできることが実は結構あるという例だと思う。
- → まずはsudoku2程度までやってみてもいいのでは？（地味だけど）
- サイボウズ・ラボの川合は、もはや高速化バカとしか言いようがない（笑）
もしこの記事を読んだ人の中で、
- ○○のコンパイラを使ったらもっと速くなったよ！ （sudoku4と実行速度比較をするといいと思います、比が1.48倍よりも小さくなるでしょうか）
- C++だけでもsudoku3よりももっと速くできるよ（でも(2)の前提条件を忘れずに）
- オレサマのアセンブラはsudoku4よりもうんと速いぜ！（でも(2)の前提条件を忘れずに）
みたいなことがありましたら、ぜひ教えてください。楽しみにしています。ソースや実行ファイルはここにまとめておきました。→https://github.com/h-kawai/20121203_sudoku
しかしそれにしてもコンパイラの最適化技術の進歩はすごいですね。・・・あと10年くらいしたら、sudoku3のままでもsudoku4並みの速さになる日が来るのでしょうか。そして50年くらいしたら、sudoku0のソースからsudoku4のバイナリが自動で出てきたりするのでしょうか。夢のようないい話です。そうなったら私は引退かなあ。
・・・まあ50年後なら引退してもいいかな（笑）。
明日は「社内システムのリプレイス方針とTips」をお送りします。お楽しみに。
