コグノスケ

インタプリタon Java VM（PythonとRubyでNクイーン問題）

目次: ベンチマーク

コメント欄にて他のインタプリタ実装もあるよ、と教えていただいたので、早速試してみました。

今回試したのはJythonとJRubyです。開発環境が認識するかどうか不安だったのですが、PyCharmもRubyMineもいとも簡単に認識してくれました。これは便利。JetBrainさんに感謝だ。

Visual Studioも持っていたので、ついでにC++ 版も作りました。Windows/POSIXスレッド、時刻取得辺りは、超てきとー実装なので、参考にしないでください。

再び測定

つまるところ、今回追加したのは下記の3つです。

• C++ 実装
• Python VMのJava実装Jython
• Ruby VMのJava実装JRuby

結果はこんな感じです。上から速い順に並んでいます。Javaって速いね。

C++: Visual C++ 2012 Relaseビルド

非並列1049[ms]、並列425[ms]

Java: IntelliJ IDEA付属のJava 7 JRE（1.7.0_10）

非並列1101[ms]、並列533[ms]

JavaScript: Internet Explorer 10（10.0.9200.16599）

非並列10415[ms]、並列（不可）

Python: Jython 2.5.3

非並列31664[ms]、並列15416[ms]

Ruby: JRuby 1.7.4

非並列30653[ms]、並列21166[ms]

Ruby: Ruby 1.9.2-p0 Windows x64版

非並列121059[ms]、並列121294[ms]

Python: Python 3.3.2 Windows x64版

非並列161900[ms]、並列158069[ms]

併せて7月2日の方も結果一覧を更新しています。

コード

測定に使用したソースコードとプロジェクト設定ファイルは下記に置いています。Webインタフェースからアーカイブが取れます。ページ右上のzipとかbz2というリンクからどうぞ。

もしGitが使える環境ならgit clone https://〜 でもコピー可能です（2019年3月12日、GitHubに移しました）。コミットのpushはできないので、お気づきの点はコメントかなんかで教えてください。

いずれもApache License, version 2.0です。といっても、流用することはないでしょうけど…。
NクイーンC++ 版
NクイーンJava版
NクイーンPython版
NクイーンRuby版

 NクイーンJavaScript版（リポジトリは作っていないです）

開発環境やインタプリタはググればすぐ見つかりますので、各自拾ってくださいませ。

スクリプト言語始めました（PythonとRubyでNクイーン問題）

目次: ベンチマーク

目次: Python

スクリプト言語の手始めに、まずは有名どころ（PythonとRuby）から目を付けました。どちらも甲乙つけ難かったため、両方使ってみることにしました。

開発環境はPythonがJetBrainのPyCharm、Rubyが同じくJetBrainのRubyMineです。これらは有償ですが、30日間の無料評価期間がありますので、触ってみたいだけなら十分に楽しめるはずです。

Nクイーンを移植

スクラッチから書く用事が今のところないので、先日JavaScriptで書いたNクイーン問題のソルバ（2013年5月13日の日記参照）の移植にトライしようと思います。手始めに無駄な処理を削って、5倍くらい速くしたJavaScript版を準備しました。

このJavaScript版NクイーンをPythonとRubyと、ついでにJavaへの移植、それに加えて並列処理ができるように改造する、というところまで実践しました。アルゴリズム自体はJavaScript版と同等とします。

目指せ一本道Python

実際に書いてみると、Pythonは初心者に優しい作りになっているように思います。特に公式のチュートリアルが非常に丁寧かつ、まとまっていてありがたいです。教育用の名は伊達じゃありません。

さらにPythonはおかしな書き方をしないように、様々な考慮がなされています。その一つが、言語策定者自らによるコーディングルール（PEP 8 - Style Guide for Python Code※）です。チェックツールまでも用意されていて、PEP 8に違反している個所を注意してくれます。

（※）ありがたいことに 和訳を公開されている方がいらっしゃいます。

僕らは自由Ruby

Rubyは好きな書き方ができてしまいますが、変な書き方を発見するとRubyMineさんが警告してくれるので、それに従っています。ただ、RubyMineさんはやたらとif文を後置（Modifier？）したがるのが困りものです。

慣れの問題だとは思いますが、処理→条件の順で書かれると、条件判定→処理という実際の手続きと逆になってしまって、理解が遠のく感じがします。英語だと文章の順に近くなるから嬉しいのかなあ。

あと、Rubyとはあまり関係ないけれど、躓いてしばらく悩んだ点を書いておきます。

自作のクラスなどを書いた .rbファイルをrequireするときは、2点注意が必要です。1個目はrequire './hoge.rb' のように ./ を付けること、2個目はRubyMineの実行設定でWorking directoryを設定しておくことです。

パスに ./ を付ける理由はRuby 1.9からrequireの探索対象パスが変わって、カレントディレクトリが対象外になったから、だそうです。RubyMineの設定を変える理由は、Working directoryのデフォルト値が「空」になっていてrequireの探索が迷子になってしまうからです。

速度はいかに？

せっかく作ったので、各言語のソルバにNクイーン（N = 15）を解かせて、速度を測ってみました。オマケで測った割に、予想以上の差が出てちょっとびっくりです。

環境について付記しておきます。CPUはIntel Core i5 2450M/2.50GHz、OSはWindows 8 Pro 64ビット版です。

C++: Visual C++ 2012 Relaseビルド

非並列1049[ms]、並列425[ms]

Java: IntelliJ IDEA付属のJava 7 JRE（1.7.0_10）

非並列1101[ms]、並列533[ms]

JavaScript: Internet Explorer 10（10.0.9200.16599）

非並列10415[ms]、並列（不可）

Python: Jython 2.5.3

非並列31664[ms]、並列15416[ms]

Ruby: JRuby 1.7.4

非並列30653[ms]、並列21166[ms]

Ruby: Ruby 1.9.2-p0 Windows x64版

非並列121059[ms]、並列121294[ms]

Python: Python 3.3.2 Windows x64版

非並列161900[ms]、並列158069[ms]

こういう単純な計算の場合、Javaはケタ違いに速いです。並列化の効果も出ます（※）。当初からC言語と比較しては遅い遅いと文句言う人達と、ガチンコ勝負してきた成果でしょうか。

JavaScriptはブラウザによって2〜3倍の差が出ましたが、一番速かったIE 10の結果を載せました。スクリプト言語では速い方？

PythonもRubyも桁違いにゆっくりです。スレッドは備えているものの、スレッドを使って並列化しても実際には1スレッド分の速度しか出ません。どうもCPythonやCRubyはネイティブスレッドを使わないようです。

（※）Core i5は2コア4スレッドなので、性能が4倍か3倍くらいになることが期待値だったのですが、なぜか性能は2倍にしかなりません。謎ですね…。

余談

次に挑戦するなら、JavaVM上で動作するスクリプト言語が良いだろうと思っています。開発環境（IntelliJ IDEA）から使える言語から選ぶなら、GroovyかScalaかKotlinかな…？どれも良さげです。

今まではJava開発にはEclipseを使っていたのですが、最近はIntelliJ IDEAを試しています。ここにPyCharmとRubyMineが加わったおかげで、開発環境がJetBrain一色に染まってしまいました。

ただIntelliJもPyCharmもRubyMineも、今のところ開発環境の能力を活用できている気が微塵もしないのが残念なところです。もうしばらく使ってみないとねー。

世の中にありそうでない言語2

せっかく年休を取ったのに、雨、というか台風来てるし…。

前回（2013年6月13日の日記参照）こんなこといいな、できたらいいな、とウダウダ書きましたが、結局何がしたいのか？を考えてみました。

条件2（ガベージコレクション）と3（標準ライブラリ、GUIライブラリ）についてはalloc/freeは面倒くさい、車輪の再発明は面倒くさい、という普遍的な悩みですから特筆することはないでしょう。引っかかるのは条件1（unsigned型の存在）です。

条件1がなくて困るのは「バイト列のMSB側からNビット取ってきて、数値として返す」処理（※）が返すべき数値が、signedだったり、unsignedだったりして扱いが面倒くさいことです。

例を挙げると、あるバイト列から3ビット取ってきて3'b101というビット列が得られたとします。得られたビット列を5と解釈すべき場合と、符号拡張して -3と解釈すべき場合があるということです。

（※）MPEGの仕様書なんかでgetbits() という関数が出てきますが、まさにアレです。

符号拡張が悩み？

単にNビット整数値の符号拡張をしたいだけであれば、下記のようにすればunsigned型なんて要りません。

/**
 * Sign extension.
 * 
 * @param v Value
 * @param n Bits of v
 * @param s 0: don't sign extension, 
 *          otherwise: do sign extension
 */
long long signext(long long v, int n, int s) {
    long long sb, mb;

    if (n == 0) {
        return 0;
    }

    sb = 1LL << (n - 1);
    mb = (-1LL << (n - 1)) << 1;
    v &= ~mb;
    if (s && (v & sb)) {
        v = mb + v;
    }
    
    return v;
}

さらに言えばRubyのように無限長整数を扱える言語の方がオーバーフローを考えなくて良いという点で有利である、とすら言えるでしょう。

あれだけ長々書いたくせに自己解決しちゃったよ、非常に迷惑だね！
でも、なんだろうこのコレジャナイ感は…？