N-Queen問題をWeb Workersで解いてみた(Javascript関係)

Javascritpベンチを作ってみたくN-Queen問題をJavascriptで解いてみました。N-Queen問題回答のサンプルがありますが、ブラウザでは再帰しすぎると止まるため、再帰する回数はある程度抑えるようにしています。

ソースは、ソース置き場のnqueen.zipです。ただし、ChromeはpostMessageをローカルファイルではやり取りできないようなので、N-Queenにありますので、試したい方はアクセスしてください。

Threadにはスレッド数を、N-Queenにはマスの数を入れてください。Threadに0を入れると、Web Workersを使いません。

N-Queen:12、Thread:4、Chrom 5.0.375.99、Phenom II X4 940BE(3.0GHz)の条件で1秒前後かかります。Web Workersを使っているためブラウザは止まりませんが、あまり大きな数字は入れないほうが良いでしょう。

Operaが10.60からWeb Workersをサポートしたので、Chrome、Safari、Firefox、Operaの正式版で、スレッドを1～12までどのように測定時間が変わるか調べてみました。測定したハードは、Phenom II X4 940BE(4コア)です。

まず、Firefoxの挙動はわかりません。同じファイルを使っているにも関わらず、どうしてこのようになるかさっぱりわかりません。

OperaはWeb Workersをサポートしたといっても、APIをサポートしただけでマルチスレッドになっていないようです。4スレッド時のタスクマネージャーは以下の様になっています。

次のバージョンでマルチスレッドに対応してもらいたいものです。Chrome、Safariは、4スレッド以上でCPU使用率が100%に行きました。

また、今回のサンプルは均等にスレッド分散ができていません。マスの数をスレッド数で割り切れると都合が良いですが、そうでないと若干スレッド数比で性能向上はしません。

【Javasript関係】
・素数を Web Workersを作って計算してみた(Javascriptサンプル)
・File APIを使ってブラウザバージョンシェアの加工してみた(Javascriptサンプル)
・Web Wrokersを使ってマルチコアを使い尽くしてみた(Javascriptサンプル)