Perlが30倍速くなるかもしれないSPVMの開発版をリリースしました。

Perlが30倍速くなるかもしれないSPVMの開発版をリリースしました。

SPVM(CPAN)

かもしれないと書いたのはベンチマークをまだとってないからで、理論的にはJava VMの速度まで、近づけることができるんじゃないかなと思うから。

開発版なので、まだ機能が足りないのだけれど、CPANにリリースして、CentOS, FreeBSD, Windowsで動かすところまでやったので、ここで公開します。Macを持っていないので、Macの方は、CPANからインストールできるか確認していただけるとありがたいです。

  • SPVMはPerlに似た新しいプログラミング言語で、バーチャルマシン上で動き、関数をPerlから簡単に呼び出すことができる。
  • 完全な静的型を持ち、Javaと同じデータ型、byte, short, int, long, float, doubleを持つ
  • モジュールを書いてすぐに実行できる。XSのように事前のコンパイルはいらない。
  • 64ビット整数をサポートしている環境のみサポート(longの値が渡せない受け取れないため)
use FindBin;
use lib "$FindBin::Bin/lib";
 
use SPVM 'MyModule2';
 
my $total = SPVM::MyModule2::foo(3, 5);
print $total . "\n";

(参考)FindBin

以下はSPVMのモジュールファイルで、拡張子は「spvm」です。

# lib/SPVM/MyModule1.spvm
package MyModule1 {
  has x : int;
  has y : int;
   
  sub sum ($a : int, $b : int) : int {
     
    my $total = $a + $b;
     
    return $total;
  }
}
 
# lib/SPVM/MyModule2.spvm
use MyModule1;
package MyModule2 {
   
  sub foo ($a : int, $b : int) : int {
     
    my $total = ($a * $b) + MyModule1::sum(2, 4);
     
    return $total;
  }
}

用語や文法は、できる限りPerlと同じにしています。Perlを書きなれた人が、すぐに書くことができるように。XSのように事前のコンパイルの必要はありません。

開発中に考えていたこと

CPANリリースまで、来たので、ここまで開発中に考えていたことを書いておく。

動機

動機は、統計・解析と機械学習のために、Perlの集合演算を速くしたいというものだ。Perlの弱点は数値演算と集合演算で、Perlは、高速化を行うための、データ構造を持っていない。

たとえば、intの配列というものはなく、すべてのデータはSV構造体に入れられ、それが、メモリ上に飛び飛びに配置される。また関数は、スタック上に、整数型や浮動小数点型を積むことはできない。

Perlは文字列に関しては、優秀なパフォーマンスを出しますが、数値計算と集合演算に関しては、ものすごく悪いパフォーマンスだ。

これを解決するためには、XSというC言語拡張を書くしかない。でも、XSは、ものすごく難しいし、メモリ管理に失敗するとセグメンテーションフォールトが起こるし、事前にコンパイルする必要がある。

もちろん、速度はC言語なので、ピカイチなのだけれど、PerlとXSの中間地点で、もう少し簡単で、安全で、書ける方法はないかと考えていた。

僕はRstatsというR言語APIPerlに持ってくるためのプロジェクトをC++で書いていたのだけれど、行き詰ってしまった。

それは、集合演算を書くためには、つねに、XSを書かないといけないという部分だ。XSの最大の弱点は、モジュール化ができないということだ。XSで書いたコードを、Perlから呼び出すことは簡単だけれど、XSどうしで運用するのは、不可能に近い。

  • 適切なデータ構造
  • 高速な処理
  • モジュール化
  • Perlから簡単に利用できる

試行錯誤

これをPerlでやろうと思ったときに、方法を考えていたのだけれど、いろいろと参考にした。

静的型

pythonにはRPythonというものがある。これは、pythonのサブセットで、pythonに静的型をつけようというものだ。

最近ではこれを真似してRPerlというのもある。

動的言語のサブセットとして、静的型をもたせるというアイデアは、グッっときた。

そうだ「静的型にして、集合演算に適切なデータ構造が必要だなぁ」という感じ。

静的型はパフォーマンスのためには必須だ。データがあらかじめ決定していれば、型の判定のための条件分岐をいれる必要がない。

最近のCPUは、分岐予測というものを行うから、最初は、数値、次は、浮動小数点、次は、オブジェクトのように、データ判定に条件分岐を使うと、そこで、速度が遅くなる。

静的型だとコンパイル時に、データが決定されるから、条件分岐を行うことがそもそもない。

型推論か自動型変換か

実装していた感じたのは、型推論と自動型変換の両方を実装するのは、ちょっと無理があるということだった。

最初はgoのような型推論と、Javaのような自動型変換を両方実装していたのだけれど、両方実装するのは、きつい(というか無理?)という感じになってきたので、型推論の方を採用した。

# 型推論
my $num = 5;
バーチャルマシン

次は、バーチャルマシン。最初は、コンパイル型がよいのか、バーチャルマシンが良いのかということを考えた。でも、コンパイルしてマシン語にするのはないなというのを考えて、バーチャルマシンでも、最終的にJITで最適化すれば、かなり速くなるんじゃないかなということを思った。

Java HotSpotは、かなり速くってC言語にかなり近い速度がでるようだし、バーチャルマシンにしておけば、後で、性能は何とかなるかなと考えた。

GC

開発中は、Javaのように世代別GCにしようかなぁとも考えていたのだけれど、Perlとの相互運用を考えるとどうもうまくいかない。

Perlは、メモリをがばがばと使えるだけ使う。Perlのメモリ管理は、いわばフリーリストのようなもので、リファレンスカウント式のGCだ。

Javaのメモリ管理は、ヒープが拡大していって、あるところで止める。ヒープの中で、世代別GCをする。

Perlとの相互運用をやるために、結論としては、リファレンスカウント方式のGCにした。循環参照の解決は、オブジェクトどうしの相互参照をできないようにした。単独のプログラミング言語であれば、、だめなんだけど、Perlから運用するから、とりあえず、これでいってみようという形。

オブジェクトの配列は作れる、配列の配列も作れる、オブジェクトは、数値型と数値の配列型を所有できる。オブジェクトは、オブジェクトと、オブジェクトの配列を所有できない。これで、循環参照を回避。うまくいかなかったときはまた考えればいいさ。

技術

技術的な話題を。SPVMは、C言語で書いています。理由は、PerlC言語で書かれているので、C言語で書いておけば、もっとも安全で、問題が起こりにくいから。

字句解析

字句解析は自前で書いてます。spvm_toke.c

構文解析

構文解析はbison(yaccのラッパ)を使ってます。spvm_yacc.y。

構文木の作成

抽象構文木の作成はspvm_op.c。

部分的に解析するのではなくって、すべてのソースコードを読み込んでから、解析するような実装です。すべてのパッケージ、フィールド、サブルーチンを読み込んでから、型チェック、構文チェックを行う。

定数プールの生成

環境として定数プールを持っています。constant_pool.c

バイトコードの生成

バイトコードは90%がJava VMを参考にしています。spvm_bytecode_builder.c。

ランタイム - サブルーチンの実行

サブルーチンの実行は、ランタイムで。spvm_runtime.c。ここで、バイトコードが解析されて実行されます。ダイレクトスレッディドコードになっています。

グローバル変数、マクロ関数と定数のマクロ定義なし

C言語で、使わないほうがよいとされている、グローバル変数、マクロ関数、定数のマクロ定義を0個にしました。使ったら負けだという意思を貫くと、複雑なソースコードでも、なしで行けるという確信が持てた。

唯一使っているのは、インクルードガードだけ。

辛かったこと・発見したこと

字句解析はまぁまぁ簡単。yaccは、reduce/reduceとの闘い。どうやったら、reduce/reduceしないか試行錯誤。構文木の構築は、辛い。ツリー構造というのは、きつい。それが、やたら多い。再帰処理は、精神的にきつい。

If else文を作るのが意外と難しい。どこでどうジャンプするバイトコードに置き換えるか。for文のほうが難しそうだけど、If elseのほうが実装がちょっと難しい。

ランタイムは、バイトコードと定数プールだけの情報で、実行できるようにしなくちゃいけなかったこと。解析機とランタイムは、完全に分離させて、解析機のメモリを解放したとしても、ランタイムを動かさないといけない。

C言語はメモリ管理との戦い。すべてのメモリ管理を自前で実装しないといけない。動的配列、連想配列、メモリプールというデータ構造も、自前で実装。コードを書けば書くほど、作らないといけない部品が、あらたにあることがわかってくる。

今後

今後は、バグをなくすのと、Perlからの型変換を実装するのと、SPVMのデータ仕様を書くのと、やります。

Macを持っていないので、Macで、インストールできるか、確認していただけるとありがたいです。