Perlテックブログ

ITエンジニアの成長意欲を刺激する技術考察、モジュール開発の日記。Perlイベントや国内や海外のPerlの記事の紹介。

コンスタントプールの再実装 - SPVM開発日記

SPVMはPerlの実装と、Java VMの仕様を読むことから始まり、両者のアイデアを取り入れながら、付け足したり、削ったりしながら微調整を繰り返しています。

SPVMは、Javaのコンスタントプールの機能を実装していたんだけれど、その後取り外してしまいました。

コンスタントプールよりも、mallocで、個々に確保するほうが、実装が簡単だよね、みたいな感じで。

さて、SPVMの文法と必要な機能が一通り完成してみると、次は、パフォーマンスを最適化するために、メモリ最適化を行うフェーズに入ってきた。

メモリを局所化するとパフォーマンスがよくなるという定石

Javaのコンスタントプールには、クラスごとに、キュキュット小さな領域に、関数の呼び出し情報の参照や、フィールド情報の参照や、文字列定数の参照、整数定数などが含まれている。

タッチするメモリの領域が小さくて、局所化されていれば、アプリケーションは、メモリアクセスの場合に、キャッシュヒット率が高くなると予想できる。

実メモリアクセスは、高価な処理で、できれば、キャッシュメモリ上にあるものを使えたほうがよい。

きっとこういう考え方で、コンスタントプールは、キュキュット小さな領域に収まるようになっているのだなぁという気がしてきた。

そこで、今日からは、SPVMのコンスタントプールの再実装に取り掛かります。

コンスタントプールの仕様

コンスタントプールはint32_t型の配列で、長さはuint16_tのサイズに収まるサイズです。これはちょうどSPVMのオペレーションコードのオペランドのサイズとなります。

コンスタントプールは、パッケージごとに、存在します。

コンスタントプールに含まれるものは以下の情報です。

サブルーチン呼び出しへの参照 int32_t
フィールド呼び出しへの参照 int32_t
パッケージ変数アクセスへの参照 int32_t
longとdoubleの定数 int32_tを二つ使う
文字列定数への参照 int32_tで長さを、バイト列を複数のint32_tに収める

C言語でファイル名だけを取得する方法 - Linux, Windows対応

C言語でファイル名だけを取得する方法について書いておきます。

LinuxのスラッシュとWindowsのバックスラッシュに対応しています。

後ろからスラッシュかバックスラッシュを探して、見つかった場合は、その次の位置のポインタを返します。

見つからなかった場合は、先頭のポインタを返します。

// 三つのファイルに対応
const char* file1 = "/home/foo/bar.txt";
const char* file2 = "\\home\\foo\\bar.txt";
const char* file3 = "bar.txt";

const char* file_base = NULL;
int32_t file1_length = (int32_t)strlen(file1);
int32_t found_sep = 0;
for (int32_t i = file1_length - 1; i >= 0; i--) {
  char ch = file1[i];
  if (ch == '/' || ch == '\\') {
    file_base = &file1[i + 1];
    found_sep = 1;
    break;
  }
}
if (!found_sep) {
  file_base = file1;
}

整数で割り切れれたときはその数を、割り切れなかったときは1大きい数を求めるアルゴリズム

整数で割り切れれたときはその数を、割り切れなかったときは1大きい数を求めるアルゴリズムです。

C言語で必要なメモリブロックの数を計算するのによく利用するのでここにメモしておきます。

計算 結果
7 / 3 3
6 / 3 2
5 / 3 2
4 / 3 2
3 / 3 1
3 / 2 1
3 / 1 1
int32_t byte_size = 6;
int32_t unit = 3;

int32_t block = byte_size / unit;
if (byte_size % unit) {
  block++;
}

リファレンスの機能を実装しつつ、変数領域作成で、mallocしない方法

現在SPVMのメモリ最適化を進めています。

今まさにやろうとしていることは、サブルーチン呼び出しを行ったときの、変数領域のメモリ最適化です。

mallocの回数を減らしたい

mallocをたくさん呼び出すことは、非常に遅いことだといわれています。

mallocを呼び出すと、システムコールが入り、指定されたサイズを元にして空いているメモリ領域を探します。

そして、メモリを確保して、その先頭のアドレスを返します。

これらの処理が重いといわれています。

パフォーマンスを高めるためには、できるだけmallocを減らすことが必要なのです。

リファレンスを実装しているので、メモリ領域が移動できない

SPVMは、リファレンス機能を仕様として含んでいるので、変数として確保した領域を移動させることができないという制約があります。

だから、大きな領域を新しくとって、元のデータを移動させるということが、サブルーチンの変数のメモリ領域に対してはできないということに気が付きました。

アドレス型、byte型~double型までそれぞれの変数領域確保が必要

SPVMは、静的型言語ですが、ランタイムで実行されるときでさえ、変数の型情報を本当に持っています。

  // object variables
  void** object_vars = NULL;
  
  // ref variables
  void** ref_vars = NULL;
  
  // double variables
  SPVM_VALUE_double* double_vars = NULL;
  
  // float variables
  SPVM_VALUE_float* float_vars = NULL;

  // long variables
  SPVM_VALUE_long* long_vars = NULL;

  // int variables
  SPVM_VALUE_int* int_vars = NULL;

  // short variables
  SPVM_VALUE_short* short_vars = NULL;
  
  // byte variables
  SPVM_VALUE_byte* byte_vars = NULL;

これらの変数領域を確保するために、うまくmallocの回数を減らしてあげる必要があります。

変数の長さの最大長は65535個、変数の長さの最大長は、コンパイル時に決定できる

ふと考えていると、すべてのサブルーチンの変数の長さの最大長は、コンパイル時に決定できることがわかりました。

もし長さの最大が、54個だったとしましょう。そして、SPVMのデータ型のサイズは、SPVM_VALUE型よりも小さいことが保証されています。

とすれば、

sizeof(SPVM_VALUE) * 54

というサイズを、領域確保の固定サイズとしておけば、すべての変数領域が納められます。

mallocして、最初は一つ確保、足りなくなったこのサイズで追加します。

# sizeof(SPVM_VALUE) * 54
-------------------

# sizeof(SPVM_VALUE) * 54
-------------------

サブルーチンが一番最初の呼び出し位置に戻ると、この領域を再利用します。

そうすると、リファレンス機能を維持しつつ、プログラム全体で、サブルーチン呼び出しの場合のmallocの回数をほんの数回に抑えることができる。

デメリット

考えられるデメリットの一つ目は、すべてのクラスを静的にコンパイル時に決める必要があることです。実行時に後から、クラスを追加するということはできなくなります。

デメリットの二つ目は、プログラムによって、確保する領域が変わるので、試験が非常に行いにくいということです。実装にミスがあった場合に、自分の試験環境ではうまく動いても、予期せぬ不具合が発見される可能性があります。

PerlはC言語とC++文法を包括しているという発見

SPVMの開発は、C/C++をもっとも簡単にバインディングできるということを一つの目標としています。

C/C++で書かれた、ライブラリを、同じ形で関数として表現したい。

こういった場合に、Perlの二つの文法が役にたつことを発見した。

  • 例外処理
  • リファレンス

「リファレンスはわかりにくい」という評判なんだけど、この間の飲み会では、「Perlにはリファレンスがあるのがいい」という意見が聞けた。

Perlのリファレンスは、C言語のポインタ渡しを表現できる

Perlのリファレンスの文法は、C言語のポインタ渡しを表現できる。こんな風に。

# Perl
my $num = 0;
foo(\$num);

// C言語
int32_t num = 0;
foo(&num);

Perlの例外処理は、C++の例外処理を表現できる

例外処理に関しても、いろいろと批判が加えられているけれど、シングルスレッドに限るのであれば、例外処理はわかりやすいエラー処理だと思う。

# Perl
eval {
   ...
}
if ($@) {

}

// C++
try {
  ...
} catch () {
  ...
}

もしPerlがこれらの文法を包括していなかったとしたら、C/C++を自然な形でラッピングすることは、きっと難しかったに違いない。

多様性や包括性に批判が加えられる時代だけれど、確かな価値を実感している。

メモリの最適化に取り組む - SPVM開発日記

インクリメント、特殊代入の実装が無事終わった。

それとexeの生成の試験がCPANでコケまくっているので、近いうちに修正しなくっちゃ。

メモリの最適化

次は、メモリの最適化に取り組んでいきます。メモリ最適化なんだけど、何をするかというと、mallocの回数を減らすということと、gccがコードを最適化できるようにメモリ配置するということの二点。

mallocの回数を減らす

mallocは、遅いといわれている。遅いといっても、1秒間に100万回くらいは、実行できるようなんだけど、1秒間に1億回と比較すると、遅い感じね。

速くするためには、mallocで先に大きめのメモリを確保して、先頭から利用していくと速いといわれている。

まぁ、その、ベンチはとっていないけど、初期実装は、素直に定石に従おうという感じやね。

Perlの場合は、アリーナという領域があって、少し大きめのメモリを確保して、先頭から利用していって、足りなくなると倍に増やした領域を追加で確保という実装になっていた気がする。

SPVMの場合も、これと合わせようと思う。ちょうど、オブジェクトのヘッダーサイズのブロックを基準にして、その大きさの整数倍のメモリを確保する。そして、足りなくなったら拡張。メモリが解放されたら、フリーリストに追加して、再利用できるようにする。

こんな感じかな。

gccがコードを最適化できるようにメモリ配置する

SPVMは、一切の最適化をgccに任せている。SPVM自体での独自実装の、最適化はしんどい。僕がしんどい。倒れる。バグ混入のリスクが高そう。ひとりでは無理。

というわけで、開発方針として、gccがなるべく最適化しやすいC言語ソースコードを、出力しようということになっている。

具体的には、今は共用体で、すべてのデータを表現しているんだけど、int32_tのところは、すべてint32_t、doubleのところは、すべてdoubleとわかるように、型宣言するということやね。

インクリメントの抽象構文木は意外と難しい - SPVM開発日記

weakenの試験を書き終えて、今日は、インクリメントのバグの修正を行っている。

インクリメントは単純そうに見えて意外と構文木を構成するのは難しい。インクリメントには前置と後置の二種類がある。

  • 前置のインクリメント
  • 後置のインクリメント

前置のインクリメントは、1足した後に、その値を返す。

後置のインクリメントは、値を返してから、値を1足す。

さて、これを、どうやって抽象構文木に落とし込もうか。

特に後置のインクリメントは難しそうだね。

ヒントは「代入演算子」と「加算演算子」と「カンマ演算子」で表現できるということだ。

カンマ演算子は(値1, 値2, 値3)と書いて、値3を返す演算子のことね。























答え

答え、というか、今考えていること。

前置インクリメントの抽象構文木
var = var + 1

これは意外と簡単だね。代入演算子が代入した値を返却するから。

後置のインクリメントの抽象構文木

一時変数が必要。

(tmp = var, var = var + 1, tmp)

カンマ演算子が、最後の値を返すことを利用して、上記のように書ける。

代入前の値を、一時変数に保存しておいて、1足して、一時変数を返す。

SPVMは、C言語Perlの表現に親和させることがひとつの目標なので、少し難しいが頑張って実装する。