more C vs C++ for Chess

前回に続いて、CとC++でのチェスのプログラムのスピード比較を行った。前回と違い今回はg++でCのコードをコンパイルしただけでなく、コード全体をclassを使って書きなおした。class使ったら遅くなるんじゃないの？という疑問に答えようというわけだ。

まずはCとほぼ同じ処理をするコードをC++らしくclassで書きなおしたものが以下のプログラム。今回の話に関係のない入出力周りとmain周辺は省略してあるが、そこもCと等価なコードになっている。主な違いは

• Move* mやPosition* posが関数の第1引数に必ずのようについていたのが、classとすることでその引数が暗黙のthisとなり不要になった。しかし、これは表面的な差に過ぎず、アセンブル出力をみると this は第1引数の (%rdi) に割り当てられているので実質的には差はない。
• 変数の宣言が最初の使用位置へ。とくにfor loopでscopeが変化している。
• 変数はprivateになり、setter/getterを通してアクセス。ただし、inline化されているので実質は同じと考えられる。

まずはプログラムを見てもらうとして、分析はその後で。

claude.h

claude.cc

前回と同様に random player 同士の対戦を1万回実行の実行時間でベンチマークを行ったところ、C版とほぼ同じ実行時間となった。どちらかというとC++の方がちょっと速いかもしれないが有意とはいえない程度の差。

ただし、どのように書いても同じというわけではなく C と C++ の違いに注意する必要はある。クラス Position のなかで Move next_moves_[200]; としている場所があるが、今度のC++コードでは Move はクラスであるのでコンストラクタが200回呼ばれることになる。このとき Move のコンストラクタとして次のように教科書通りのデフォルトコンストラクタを設定すると実行速度はC版が24秒程度だったのに対して、C++版が35秒程度と大幅に低下した。

実際に new Move[1000000] の実行時間を測ってみると、上記のコンストラクタだと 0.015192 s, 0.014435 s, 0.015185 s と1つあたり0.015 μsかかる。一方、デフォルトコンストラクタ Move::Move() {} だと、0.000804 s, 0.000762 s, 0.000467 s となる。new の数を1桁増やすと上記のコンストラクタの実行時間は1桁増えるが、後者は変わらないので、デフォルトコンストラクタは実際にはなにもせず、この実行時間はメモリ確保のための時間だろう。

そもそも Move next_moves_[200]; という固定配列はよくない。これを STL の vector にする。すると実行時間は27秒前後と3秒程度低下する。このスピード低下を STL を使うからと短絡的に考える前に原因を探ってみよう。DoMoveのなかで、 *dst = *this; としている部分が怪しい。この処理の中でnext_moves_も当然コピーされるが、それは重い。しかし次の盤面では next_moves_.clear() を呼んでいることからも、 next_moves_ のコピーは不要である。is_under_attack_ のコピーも同様に不要。そこでこれらをコピーしないようにプログラムを修正する。

board_ のコピーは memcpyでも出来るがそれほど実行時間に差はでないので、ここでは普通の書き方にしている。実行時間を測定すると 17.166239 s, 16.805014 s, 16.713350 s おお、C++ 速い！ いやいや、同じことが C でもできるよねと、やってみると 18.646168 s, 18.581420 s, 18.566730 s 。

アセンブル出力を見比べてみると、ところどころ微妙な差があるのが分かる。2次元配列にアクセスするコードが違っていて、C では以下の5命令になっている部分が、

C++ では4命令になっている。

is_under_attack の型が int から bool になったので、バイト数が4倍違うせいか。C の方の is_under_attack の型を char にしてみると同じになった。なぜ leaq (%rdi, %rax, 32), %rax とはならないのだろう。32倍はダメなんだっけ？

以上のことから class を使っても、C と C++ では実行時間に差が付かないと結論づけてよさそうである。遠慮無く C++ でコードを書くことにする。 むしろ、C++ の方が速いという計測結果がでているのが不思議。STLを使ってメモリ消費が少なくなった分かな？

あとは virtual 使ったらどうなるのかが残された疑問だけど、今回は使わなかったのでまた次回。