読者です 読者をやめる 読者になる 読者になる

euphonictechnologies’s diary

Haskell超初心者の日記です。OCamlが好きです。

follow us in feedly

Haskellで将棋 - 指し手生成のスピードテストとHaskellのマイクロベンチマークライブラリ:criterion

コンピュータ将棋 Haskell

前回は指し手生成部分に手を加えてみた。ここにあるよくベンチマークに使われている局面からの指し手生成スピードを測定して、先の変更がどれ位悪影響をもたらしているかを確認しておく必要がある。

当然のことながら一発で計算できるものを分割してリストをconsするコストを掛けるわけなので、当然スピードは低下する。一体どのぐらい低下しているのかをお手軽に本格的な方法で計算をしてみる。

プロファイリングは難しい

基本的にこの手のマイクロベンチマークはほとんど意味を成さないことがほとんどだ。当然ガーベッジコレクタやその時のマシンのCPUの稼働状況などに大きく左右されてしまう。実行するプラットフォームのカーネルバージョンなんかにも影響を受けてしまう。さらにベンチマーク用の小さなコードと実際に稼働する大きなコードでは最適化の程度も大きく異なってくる。当然コードのコンプレクシティが上がれば上がるほどどんどん最適化は雑になっていく。さらにHaskellは遅延評価なので直感ではとても実行効率など見積もれない。

自分の経験から言うと、大抵の人は実行のボトルネックを正しく認識できていない。もっというと色眼鏡をかけてみている。たとえ実際のパフォーマンス改善をプロファイリングに基づいて行うとしても、正しいボトルネックの認識を持ち続けるのは難しい。

なので、私自身は可能な限りツールに依存しようと思っている。バイアスや思い込みの入り込む余地を最小限にしたい。お手軽にそれができれば最高。

なのでcriterion

criterionに頼ってしまおう。上に挙げたような制限を肝に銘じておけばそれほど目が曇ることもあるまい。

criterionはHaskellのコード編のマイクロベンチマークを取るのを助けてくれるライブラリ。基本的なところをひと通り綺麗にしてコードの実行時間を測定してくれる。 たとえば

  • warm up
  • クロック精度のキャリブレーション
  • 何度も測定して分散とかを計算してくれる

辺りをやってくれる。 今回はこのコードを測定して比較してみる。

MoveGenerator.mvGenFull (Usi.bdFromSfen [
                    "l6nl/5+P1gk/2nl1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL",
                    "w",
                    "GR5pnsg"
                    ])

MoveGenerator.mvGenFullN (Usi.bdFromSfen [
                    "l6nl/5+P1gk/2nl1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL",
                    "w",
                    "GR5pnsg"
                    ])

この2つは前回作ったN付きのバージョンとその前のバージョン。どちらも同じ指し手を生成する。

コードを書いてみる

まずはcriterion.cabalファイルに追加する。

次に、こんな感じで2つのコードをcriterionから実行してみる。

module Main where

-- friends
import qualified Usi
import qualified MoveGenerator
-- GHC

-- libraries
import Criterion.Main

-- std

main :: IO ()
main = do
    print "Running test ..."
    defaultMain [
        bgroup "bench group" [
            bench "moveGeneration - old version" $ whnf
                MoveGenerator.mvGenFull (Usi.bdFromSfen [
                    "l6nl/5+P1gk/2nl1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL",
                    "w",
                    "GR5pnsg"
                    ]),
            bench "moveGeneration - new version" $ whnf
                MoveGenerator.mvGenFullN (Usi.bdFromSfen [
                    "l6nl/5+P1gk/2nl1S3/p1p4Pp/3P2Sp1/1PPb2P1P/P5GS1/R8/LN4bKL",
                    "w",
                    "GR5pnsg"
                    ])
            ]
        ]

これが完成品のコード。凄くシンプルなのがわかると思う。

defaultMainの中でcriterionを実行する。defaultMainBenchmark型のベンチマークを引数に取る。bgroupは複数のBenchmarkを取り、それを一つのBenchmarkにまとめる。Stringでベンチマークグループに名前をつけることができる。

bgroup :: String -> [Benchmark] -> Benchmark

である。

benchは実行可能なモノを受け取ってBenchmarkをつくる。つまり

bench :: String -> Benchmarkable -> Benchmark

だ。

さて、肝心なのはBenchmarkableだけど、とりあえず、普通の関数であればBenchmarkableになる。ただし、遅延評価されるので、普通に関数呼び出しをしても評価されない、のでベンチマークが一瞬で終わってしまう。そこで、何らか評価する仕組みが必要だ。

簡単に使う場合はwhnf関数を使うのが早い。whnfはその名の通り引数の関数とその関数への引数一つをとって弱頭部正規形に簡約する。弱頭部正規形を簡単に言うと

  • プリミティブ型は完全に評価された形
  • データ型は一番外側の構築子が明白な形式になっている形
  • 関数は一番外側の部分が明白な形式になっている形

といったところだけど、難しいのでここでは深入りしない。

兎にも角にも一つの引数を取る関数であればwhnfに変換すれば大丈夫なはず。指し手生成は局面を受け取って指し手のリストを返すので、ひとつの引数だけなのでwhnfで大丈夫。まとめると上のコードになる。

実行してみると

$ cabal run movegenbench
Preprocessing executable 'movegenbench' for hamilcar-1.0...
[10 of 10] Compiling Main             ( src/bench/Main.hs, dist/build/movegenbench/movegenbench-tmp/Main.o )
Linking dist/build/movegenbench/movegenbench ...
"Running test ..."
benchmarking bench group/moveGeneration - old version
time                 1.139 μs   (1.096 μs .. 1.185 μs)
                     0.988 R²   (0.979 R² .. 0.996 R²)
mean                 1.126 μs   (1.097 μs .. 1.158 μs)
std dev              102.1 ns   (68.09 ns .. 149.5 ns)
variance introduced by outliers: 87% (severely inflated)

benchmarking bench group/moveGeneration - new version
time                 2.945 μs   (2.914 μs .. 2.978 μs)
                     0.998 R²   (0.996 R² .. 0.999 R²)
mean                 3.013 μs   (2.964 μs .. 3.123 μs)
std dev              227.4 ns   (143.8 ns .. 379.8 ns)
variance introduced by outliers: 81% (severely inflated)

というようにベンチマークごとに結果を表示してくれる。マイクロセカンドレベルで測定できていることがわかる。 ブレもそれほどなくstd devが227.4ナノ秒となっている。有効数字はきちんと考慮されているものと信じたい(ここを深入りしてもいいけれど、泥沼そうなのでいまは入らない)。

これを見ると最初の予想通り昔の一発で指して生成するバージョンの方が早い。さらに新しいバージョンは2倍以上遅いことになる。 1秒辺りの指し手生成数に直すと

1 / 3.013 μs * 106 = 331,895.12

なので1秒間で30万局面ほど生成できている。ちなみに-O2でLLVMは使っていない。そこそこのスピードのようだ。

参考文献

かずの心の贅肉 指し手生成祭2

一人指し手生成祭り - 将棋プログラム「技巧」開発日記

指し手生成祭り開催 - Bonanzaソース完全解析ブログ

Criterion.Main

Success is a Journey, not a Destination: Criterionを使ったHaskellコードのパフォーマンス計測

第5章 プロファイルを取る

Javaの理論と実践: 欠陥マイクロベンチマークを分析する

基本的なこと