任意の整数を613413として、素因数分解を実行したいときは以下のようにして実行します。
$./quiz2.sh ;シェルスクリプトを実行 Whats's the number? ;素因数分解すべき数の入力を促してきます。 613413 ;ユーザは、素因数分解したい数を入力してください。 (以下、実行結果参照) |
任意の整数を613413として、素因数分解を実行した時に出力される結果は次のようになります。
(出力ファイル(quiz2_output.txt)へのリンク)
$./quiz2.sh ;シェルスクリプトを実行 Whats's the number? ? 613413 >> 613413: 3 3 3 3 7573 ;左のように613413を素因数分解した結果が表示されます |
作成したシェルスクリプトを実行してみると、613413のように数が大きくなるにつれて素因数分解に必要な時間が長くなっていく様子が見られる。
理由として考えられるのは、
2から割り始めてターゲットの数を素数で割った数で更新しながら、ターゲットの数の平方根を超えるまで割る数を1づつ増やしながらループするという素因数分解のアルゴリズムは、ターゲットの数が大きくなるにつれて計算量が飛躍的に増える。 （ただし、平方根を取らないアルゴリズムよりははるかに早く収束する。コマンドbcを使って平方根を取り収束を早めた点は工夫した点の１つといえる。） 実際これを回避するためのアルゴリズムがいくつか存在する。
シェルスクリプトのsolver1関数のwhileループのなかでexprコマンドを幾度も呼ぶが、この時exprコマンドのプロセスを生成し開始するロスが計算量が増えるにつれ顕著になってくる。
同様に、ループ内に存在する条件分岐にも条件式を判断するのにtestコマンドが実行され、さらなるプロセス実行のオーバヘッドが生じる。
例えば、1〜1000000の素因数分解の結果を知りたいと思ったときに今回作成したシェルスクリプトではとても実用的とは言えない。そこで素因数分解の高速化を次の「さらなる実験」のセクションで行いたいと思う。
ここでは、素因数分解を高速化すために考察１で挙げたの2つ目と3つ目の点に注目したいと思う。
シェルスクリプトの処理系(bash)では算術計算が直接的にはできず、度々exprコマンドを呼ぶ必要がある。同様に条件式の評価にもtestコマンドを実行する必要がある。 このことは、Ruby,JavaScriptといったスクリプト言語、Java,.Net言語（C#, VB.net)、C/C++といったコンパイル型言語では十分に解決される。また、高速化という意味ではスクリプト言語よりもコンパイル型言語の方がアドバンテージが大きいのでコンパイル型言語を使って検証してみたいと思う。今回は、プログラム言語としてC++とJavaを使用したがそれぞれのプログラムの実行形態について以下の特質に注意が必要である。
実験内容は、1〜10(A)、1〜100(B)、1〜1000(C)、1〜10000(D)、1〜100000(E)、1〜1000000(F)、1〜10000000(G)
の数を素因数分解を行うプログラムをC++(イ）、C++最適化オプションあり(ロ）、Java（ハ）、シェルスクリプト（ニ）で作成する。そして、計算結果の出力をファイルにリダイレクトして実行し、それにかかった時間を測定をした。（計算結果を画面に出力する場合、標準出力の内容をコンソール画面に描画する必要がある。この作業時間は数値的な計算にかかる時間よりもはるかに大きい。また、出力を描画するのはおそらくOSのAPI(WindowsであればWin32 API)やその上のレイヤーに存在するGUIフレームワーク(X, Gtk, Qt等）であり、それらのAPIを呼び出すオーバヘッドの時間を計測してしまうことになる。これらの理由から、それらの干渉が小さいリダイレクトを用いることにした。)
なお、時間の計測にはtimeコマンドを利用し、5分以上時間がかかったものを除き3回づつ計測しその平均をとった。
以下が各実験項目(イ）〜(二）、(A)〜(G)の計測時間をあらわす表である。なお、各セル2行目の括弧内の数値は(ハ)Javaの計測時間を1としたときの相対的な計測時間の比である。(シェルスクリプトにおいて(E)、(F)、(G)の項目は時間がかかりすぎ終わる気配がないので途中で実験を打ちきった。）
実験結果のグラフを見ると以下のような特徴を見て取れる
Java, シェルスクリプトに比べて実行ファイルが機械語であるC++で作成したプログラムは、実行時間が(A)〜(G）のどのケースにおいても短い。取り分け(A)〜(B)はtimeコマンドの測定限界に近い値が出ていると思われる。また、(ロ)C++(最適化）は、(イ)の最適化なしなしに比べて計算量が増えるにしたがい1パーセント程高速化しているように見て取れる。ただし、誤差も含まれると思われる。よって、今回行った最適化オプションが最適化なしに比べて期待したほどの効果はなかった。（あるいは、より高速化のため最適化オプションが存在するのかもしれない。）シェルスクリプトの方は、考察1で懸念した通り、(D)より計算量が増える場合には今回の実験内容においてはシェルスクリプトが現実的な選択肢でないと思われる。一方、C++, Javaは(F)の計算量でも実用的な処理時間で仕事をこなしている。シェルスクリプトで記述したソースがbashによりインタープリタされ処理構造を実現する各種コマンドを呼び出したり、算術計算にexprコマンドが呼び出されて実行されるオーバヘッドがないようなプログラミング言語を使用すれば、今回の実験内容ぐらいの仕事はこなせるということになり実験目的を果たせたと言える。
(イ)C++と(ハ)Javaを比較すると、(A)〜(C)についてはJavaの方が100倍ほど遅い。しかしながら、計算量がはるかに増える(E)〜(G)では6〜10倍となり、C++との処理時間の差が小さくなる様子が見て取れる。これは、考察1で取りあげた「プログラム言語としてC++とJavaを使用したがそれぞれのプログラムの実行形態の違い」によって解釈できる。Javaで作成したプログラムは実行時にJVMを立ち上げて、バイトコードをロードする必要がある。これにより、プログラムの起動には若干の時間が必要となる。（起動時にJITコンパイルされる場合はなおさらである。）このことは、実験(A)ではJavaよりもシェルスクリプトの方が短時間で終了しているという結果とも一致する。より処理に時間がかかるような実験(D)以降では、その起動時のオーバヘッドは処理時間にたいして小さくなって行く。また、実行時間が長くなるにつれてVMによるJITコンパイルや最適化が進み実効速度は高速化され、(G)ではC++にたいして約6倍の実効速度までせまっている。裏でVMがメモリをどれぐらい確保しGCがどのように働いているかなどより詳しい調査が必要だが、10年前ほどの「Javaはとても遅い」という印象は現在必ずとも一致せず、上手くプログラムを作ればJavaでも実用的なプログラムがつくれるのではないだろうか。実際、Javaの実効速度はC++などで作成したネイティブコードと比べて変わらないか一部上回るという情報も存在する。(.NetのCLRでも同じようなことが言える。）今回の実験でも、より工夫したり、計算量を増やせば仮想環境を通すプログラミング言語に有利な結果が出るかもしれない。.Net言語やJavaといった言語がコーディングしやすく、セキュアで開発効率が高い上に実行環境を選ばない(同じバイナリで理論上は実行できる）メリットに加え、実効速度もよりともなってくれば大学の科学分野でもっと採用されてもよいと思われる。
シェルスクリプトに不利な考察ばかり挙げたが、本来今回の数値計算的な実験はシェルスクリプトのような実行形態を持つ言語ではデメリットが顕著にでてしまうことに注意が必要である。例えば、ユーザとの対話式のプログラム（問1、問3など）では必ずしも上記のような高速性は必要とされない。この様な場合は、コンパイルが不要なスクリプト言語のメリットが生きてくると思われる。各プログラミング言語の特性を生かしてプログラマが言語を選択することが、計算機を利用して目的を達成するための重要なキーになるといえる。
まずこの様な実験を行いたいと思った動機は、実験機が64bitでありメモリ8GをきちんとOSが認識するという恵まれた環境に遭遇できたからである。今まで、32bitOSでせいぜいメモリが2GぐらいのスペックのPCを使う程度であった。最初、実験室に入った時からぜひこの高いスペックのパソコンでプログラムを走らせてみたいと思っていた。このような形で、夢をかなえることができたのはとても嬉しいと思う。これらの知識を自然科学の数値計算分野で生かせるようによりスキルを高めて行きたい。
TAの方々や先生には無理を言ってご理解いただき、jdkやg++をインストールするためにsudo権限をいただいました。このスタートがなければ、今回の実験意図はかなえることはできませんでした。ありがとうございました。
プログラミング言語、OS、仮想実行環境(JVM, CLR)、パフォーマンスチューニングについての知識は数年かけて集めたものなので全ての参考資料を 書き上げることはとてもできず、記事の作者、著書の作者の方には本当に申し訳ありません。少しながらですが主なサイトを以下に挙げさせていただきました。