インテルによる「ポーカーの手の判別の並列化」について


概要:インテル デベロッパー・ゾーンで公開されている「C++ 11 でマルチスレッド・コードを記述する」という記事の,「ポーカーの手の判別は並列化しても速くならない」という主張について調べた結果,私の環境で4.9秒かかる元記事の処理が,0.68秒で終わるようになりました.(コード

計測すべし。計測するまでは速度のための調整をしてはならない。(ロブ・パイク)

オリジナルのpokereval/pokereval.cppを見ながら作業しましょう.

Step 1:実験の意義

タスクの中でスリープするのはやめましょう.そういうことをすればマルチスレッド版がシングルスレッド版より速くなるのは当然ですが,意味がありません.105行目を書き換えます.

//Sleep(1);

Step 2:データセット

2万件(正確には19981件)ではすぐに終わってしまうので,100万件のデータを使いましょう.207行目を書き換えます.

std::ifstream filein("hands1million.txt");

Step 3:シングルスレッド版の実行時間

シングルスレッド版はこれで動くので,この実行時間を基準にチューニングします.

筆者のPC(i7-4930K,Visual Studio Community 2017,Win32 Releaseモード)では,4.9秒でした(シングルスレッド版・オリジナル).

Step 4:バグ修正

マルチスレッドのコードにバグが2個あるので修正します.(補足:この修正はpull requestしました.)

(1) 入力の終わりの判定が間違っていて,hands1million.txtの最後の空行をカウントしています.283, 284行目の,

if (filein.eof()) break;
std::getline(filein, str);

を次で置き換えます.

if (!std::getline(filein, str)) break;

(2) スレッド数の倍数だけ処理したところで出力していますが,最後に余った分を出力し忘れています.299行目の#elseの前に,次を挿入しましょう.

if (count != MaxThreads - 1) {
  for (int i = 0; i < count; ++i) {
    fileout << futures[i].get() << '\n';
  }
}

Step 5:マルチスレッド版の実行時間

269行目の#define Multi 1を有効にして,マルチスレッド版の実行時間を計ります.

筆者のPCでは5.7秒でした(マルチスレッド版・オリジナル).

マルチスレッド版がシングルスレッド版(4.9秒)より遅いと悔しいのは確かです.

Step 6:計測

Visual Studioの,デバッグ→パフォーマンス プロファイラーで,関数ごとのCPU使用率を計測します.

測定結果の上位は次のようなものでした.

プロファイル結果

std::basic_istreamに一番時間がかかっています.もう少しよく見ると,その大部分は,std::endlで費やされているようです.

Step 7:パフォーマンスチューニング

『C++の教科書』の8.2.3項に,endlはバッファをフラッシュさせると書いてあります.100万件のデータの出力する際に,1件ごとにフラッシュするのはまずいでしょう.294行目のstd::endl'\n'に置き換えます.

fileout << e.get() << '\n';

筆者のPCでは2.5秒でした(マルチスレッド版・修正後).

残念ながら,これでシングルスレッド版(4.9秒)を上回ったわけではありません.シングルスレッド版のコードでもstd::endl'\n'に置き換えて(256行目),実行時間を計ります.

筆者のPCでは1.4秒でした(シングルスレッド版・修正後).

依然として,マルチスレッド版よりシングルスレッド版の方が高速です.

とはいえ,元記事の「評価の実行時間が短すぎて、タスクを非同期に呼び出すオーバーヘッドが原因である」という考察は疑問です.ここで解いているのはいわゆる embarrassingly parallel というやつで,並列化の効果が,「あって当然」だからです.

Step 8:OpenMP

OpenMPを使いましょう.『C++の教科書』の12.4節に使い方が載っています.

マクロで場合分けしてもかまいませんが,シングルスレッド版のコード(300から306行目)を書き換えます.データをメモリに読み込んで,OpenMPで並列に判別し,結果を出力します.

std::vector<std::string> hands;
while (std::getline(filein, str)) {
  hands.push_back(str);
}
rowCount = hands.size();

std::vector<std::string> results(rowCount);
#pragma omp parallel for
for (int i = 0; i < rowCount; ++i) {
  PokerHand pokerhand(hands[i]);
  auto result = EvaluateHand(pokerhand);
  results[i] = pokerhand.GetResult(result);
}

for (int i = 0; i < rowCount; ++i) {
  fileout << results[i] << '\n';
}

筆者のPCでは0.68秒でした(OpenMP版).これでシングルスレッド版・修正版(1.4秒)より速くなりました.シングルスレッド版・オリジナル(4.9秒)よりはかなり速いです.ちなみに,OpenMPを有効にしない状態でのこのコードの実行時間は1.7秒でした.

まとめ:ポーカーの手の判別は並列化で速くなります.

「大学への数学」2017年6月号掲載の拙稿「機械まかせの数学 Mathematicaで解く東大入試数学」について


B06XWF34YQ月刊誌「大学への数学」2017年6月号で,「機械まかせの数学」という記事を書きました。内容は副題「Mathematicaで解く東大入試数学」のとおりです。

高校生向けの雑誌ですが,大学生,というか,「コンピュータと数学」ということに興味を持てるすべての人が想定読者です。高校数学の知識を前提にしていますが,大学入試問題を解く数学力は不要です。「Mathematicaでしょ,知ってる」という方も,Ver. 10以降のMathematicaを知らないなら,ちょっと驚くかもしれません。

膨大なネタを4ページに収めました。行間をすべて説明するのは大変なので,ここでは一つだけ。

「プログラミング入門=アプリ制作」や「プログラミング入門=ロボット制御」という風潮がありますが,この記事のように,数学を題材にしてプログラミングを学ぶという話は,もっとあっていいと思います。その際,題材とする数学は,高校レベルがいいでしょう。多くの方が基本的知識を持っていますし,問題の難しさも比較的判断しやすいからです(受験勉強のおかげ?)。大学入試問題を使うと,解けても解けなくてもそれなりの驚きがあります。

というわけで,高校生がメインターゲットの雑誌ですが,この記事は高校生以外にもお勧めです。

高3の一年間,この雑誌の学力コンテストで名前を載せ続けたのですが,著者として名前が載ることになるとは思いませんでした。いわゆる,「当時の自分に読ませたい記事」のつもりです。息子に読ませたいかというとちょっと微妙で,ちょうど1歳になる息子が読めるようになる2020年頃には,状況がまったく変わっているかもしれません。

記事中のコードはWolfram Cloudにまとめてあります。Mathematicaは高価なソフトウェアだと思っている人が多いようですが,基本機能はクラウド上で無料で使えます(こちら)。「別の言語でやってみた」という反応も歓迎です。

電子版はないので,お早めにどうぞ。

見本

Taro Yabukiさん(@taroyabuki)がシェアした投稿 –

大人の塗り絵:塗り分けに五色必要な地図(1975年のエイプリルフール)


4102184619四色あれば,地図上の隣り合う領域の色が同じにならないように塗り分けられるという「四色定理」は,1800年代後半に予想され,1976年にコンピュータを使って「証明」された。

定理が「証明」される前の1975年に,マーチン・ガードナーが塗り分けに五色必要だとして発表した次の絵が話題になったという。(参考:Martin Gardner's April Fool's Map

これはエイプリルフールのネタだったのだが,四色で塗り分けたという手紙が数百通届いたらしい。(ロビン・ウィルソン『四色問題』(新潮社, 2013)p.38)

この大人の塗り絵をやってみたい。

0387753664Mathematica in Action で,塗り分ける方法が紹介されているのだが,http://extras.springer.com/からダウンロードできるコードは,最近のMathematicaでは動かない。(Mathematicaの言語仕様は後方互換性を保持しながら進化しているのだが,外部パッケージが本体に取り込まれた場合は,大抵うまくいかない。)

そこで,簡易版を作る。領域の境界線が垂直または水平の2pxの黒い実線の場合にのみ対応するという意味で「簡易」である。

Importで画像を読み込み,MorphologicalComponentsで領域に分割する(Colorize[matrix]で描画)。

四色で塗り分ける。(参考:ヨーロッパの地図の4色を求める

色を1組の真偽値で表し,色が同じでないという条件を連言標準形で記述することで,高速化している。

細かい注意:上の結果は周りが海に囲まれていても大丈夫なように,条件を追加して求めたもので,このコードの結果とはちょっと違うものになっている。

最後の描画はColorize[matrix, ColorRules -> cTable]でもいいのだが,この関数にはバグがあり,Mathematica 10.4.1では正しく動作しない。(製造元には報告済み。Ver.11で修正された。

MathematicaのRegionPlotのバグ


10.3.1ではできたことが,

10.4でできなくなってしまいました(11.2もダメ)。(報告済み)

Mathematicaのサジェスチョンバーはオフにすべき(10.4)(10.4.1で修正)


10.4.1で直ったようです。

Mathematica 9で導入されたサジェスチョンバーのせいで計算結果がおかしくなることがあるようです。テクニカルサポートにバグを報告したら,その回答として教えてもらいました。

例1:以下のコードを1行ずつ実行するとMathematicaが落ちます。

m = SparseArray[{{0, 1, 0}, {1, 0, 1}, {0, 0, 0}}];

n = Map[With[{s = Total[#]}, If[s == 0, #, #/s]] &, Normal[m]];

n.n

例2:以下のコードを1行ずつ実行するとコンテキストが勝手に変わってしまいます。

Context[]

f = Solve[{2 x + y == p, x - 2 y == q}, {x, y}][[1]];

x + y ≤ 4 /. f

Context[]

せっかくフロントエンドとカーネルを分けているのにどうしてこんなことになるのか不思議ですが,文句を言っても計算結果は変わらないので,以下の資料に従って,サジェスチョンバーはオフにしておきましょう。

入力予測インターフェースの機能をオフにする方法