マイ・Guarded Horn Clauses コンパイラのメモリ消費改善

# 概要

これまで、未具体化変数は必ずヒープ上に置くことにしていました。
レジスタウィンドウ上にも未具体化変数を置けるようにすることで、ヒープ消費を削減したいと思いました。

# 問題意識

例えば

```prolog
tarai(X, Y, _, R) :- X =< Y | R = Y.
otherwise.
tarai(X, Y, Z, R) :- true |
    X_1 := X - 1, tarai(X_1, Y, Z, R_X),
    Y_1 := Y - 1, tarai(Y_1, Z, X, R_Y),
    Z_1 := Z - 1, tarai(Z_1, X, Y, R_Z),
    tarai(R_X, R_Y, R_Z, R).
```

を例に考えます。

`X_1 := X - 1` は見た目通り単純に X-1 を計算してその結果を X_1 に格納する、至極単純な処理なのですが、他のサブゴール呼び出しと同様に処理するならば

1. ヒープ上に `X_1` の場所を確保（自己参照ループ）
2. ヒープ上に項 `X - 1` （言い換えると `'-'(X, 1)` ）を作る
2. 引数レジスタ 1 に `X_1` の場所を格納
3. 引数レジスタ 2 に項 `X - 1` の場所を格納
4. サブゴール ':='/2 呼び出し

のようになります。

流石にこれだと重いのでコンパイル時に -1 の計算であることを検出して

1. ヒープ上に `X_1` の場所を確保（自己参照ループ）
2. 引数レジスタ 1 に `X_1` の場所を格納
3. 引数レジスタ 2 に `X` の値を格納
4. サブゴール '__dec__'/2 呼び出し

のようにしています。

これにより、項 `X - 1` のヒープ消費を削減できました。しかし、整数一つを受け取るだけのためにヒープ上に場所 `X_1` を確保しているのが今ひとつです。直接レジスタに整数を書き込んでもらうことができればヒープを使う必要はないはずです。

たらい回しのように繰り返し多数回呼び出される処理の場合、このヒープ消費は膨大なものになり、ばかにはできません。

一方で、`X_1 := X - 1` を実行するタイミングで `X` が具体化されていない場合のことも考慮する必要があります。この場合、変数 `X` に対して `X_1 := X - 1` を具体化待ち状態ゴールとしてフックする必要があり、`X_1` はいつ消えるかわからないレジスタ上の位置ではなく永続的なヒープ上にあるべきです。

# 前提条件

マイ・Guarded Horn Clauses コンパイラは、データ格納場所として、以下を用いています。

## レジスタ

基本的に、レジスタは用途によって以下に大別しています。

1. ゴール呼び出しの引数を格納する領域 (in)
2. タグ付きポインタ、アトム、整数などの一時変数の領域 (x)
3. サブゴール呼び出しの引数を格納する領域 (out)

in / x / out は使い方で決まるだけなので、例えば不要になった引数 (in) は一時変数 (x) で上書きして再利用しても構いませんし、サブゴール呼び出し引数 (out) の位置もそのときのレジスタ使用状況に応じて決定できます。

レジスタはサブゴール呼び出しの際に積み上げる形で(out を in に読み替える形で）切り替え、ゴール処理完了時にもとの位置に戻す、というレジスタウィンドウ形式です。

具体的には、サブゴール呼び出しは

1. out レジスタ領域を決定し、
2. 呼び出し先ゴールの引数として渡す内容を out レジスタに設定した上で、
3. レジスタウィンドウのベースオフセットを切り替えることで out レジスタが in レジスタとして見えるようにし、
4. 呼び出し先ゴールの処理を開始する

のような形で実現しています（細かいことを言うと、末尾呼び出しは異なる動きをする）。

in レジスタより前の領域は呼び出し元ゴールが使っているレジスタなので破壊禁止です。

## ヒープ

ヒープは永続的なメモリ領域です。

ヒープ上の値は

1. 未具体化変数あるいは具体的な値として初期化し、
2. 未具体化変数には単一化によって値を具体化できる、
3. 具体化後の値の書き換えは禁止

というルールにしています。

レジスタは任意のタイミングで任意の値への書き換えが可能な代わりに、ゴール処理が続いている間だけしか利用できません。ゴール処理を跨いで永続的にアクセスの継続が必要なデータはヒープ上に置く必要があります。

# 改善方法

## 新規タグ (LREF) の追加

これまで、サブゴール呼び出しの際に新たな未具体化変数が必要になった際、必ずヒープ上に当該変数の領域を確保していました。

これは以下の理由によります。

- サブゴール処理が具体化待ちによって遅延された場合には、引数で渡した変数はいつ具体化されるかわからない。いつ書き換えられるか（具体化されるか）わからないのでレジスタ上の一時的な位置を渡すわけにはいかない。
- 渡した変数に対して具体化待ちのフックが登録される可能性もある。フック登録はヒープ上にある変数に対してしか行えない。
- そもそもレジスタ上にある位置をどうサブゴールに渡すか。タグ付きポインタとしてエンコードする必要があり、単一化処理など全ての処理に対応を追加する必要がある。

これに対して以下を考慮しつつ、サブゴール呼び出し引数にレジスタ上のアドレスを渡せるようにしました。

1. レジスタ上のアドレスを示す新たなタグを追加を追加する。未具体化変数が自己参照ループなのは通常のヒープ上の変数と同じ。
2. この新たなタグでのアドレスは、通常のヒープ上の変数と同様に別のレジスタアドレスを指して連鎖を構成してもよい。→デリファレンス処理に新しいタグのサポートの追加が必要。
3. 新しいタグで指すアドレスは必ずより低位アドレスのレジスタ上アドレスでなければならない（より長い寿命を持つ親ゴールの変数を差さなければならない）。→単一化処理での考慮が必要
4. レジスタファイルは std::vector で構成しており、サイズが不足した場合には領域の再確保、つまりアドレスの変更が発生する。→レジスタファイルサイズ拡張時にアドレス変換が必要
5. 新しいタグで指すアドレスはヒープ上のアドレスであってはならない。→単一化処理での考慮が必要
6. ヒープ上の変数（具体化待ちフック上の遅延レコード含む）がレジスタ上アドレスを指してはならない→単一化処理での考慮が必要
7. レジスタ上にある変数にフックを登録したい場合、一旦新たな変数をヒープ上に確保したうえでフックを登録しなければならない。そのうえでもともとのレジスタ上の変数をヒープ上の新しい変数を指す形に書き換える→fail時の具体化待ち処理の修正が必要

## 新規レジスタ種別 (y) の追加

上述の in / x / out の場合、コンパイラはゴール処理期間の一部、使い始めてから使い終わるまでの期間だけ存在を保証していれば問題ありませんでした。

新しいタグ (LREF) の場合、最初に出現してから全てのサブゴール呼び出しが終わるまで、当該変数のレジスタ上位置を保全する必要があります。

単純に、x レジスタとして分類したうえで特定の変数だけ特別扱いする、ということも可能ではあります。しかしわかりやすさのため新たな種別、y レジスタを設けることにしました。

y レジスタはほとんど x レジスタと同じですが、ゴール処理終了まで当該アドレスの再利用（別の値での上書き）を許さない、という点でのみ異なります。

これにより、少なくとも一連のサブゴールの木を全て呼び出し終わるまでレジスタ上の変数の存在を保証します。

サブゴールが具体化待ち状態になるとき、あるいは別スレッドで処理する場合には、ゴール終了以降にも当該変数の保全が必要になります。この場合には必要なレジスタ上の変数をヒープ上の新しい変数に書き換えます。この書き換えの後も、後続の処理はデリファレンスによりヒープ上の新しい変数を参照することで処理を継続できます。

## コンパイル例

```prolog
tarai(X, Y, _, R) :- X =< Y | R = Y.
otherwise.
tarai(X, Y, Z, R) :- true |
    X_1 := X - 1, tarai(X_1, Y, Z, R_X),
    Y_1 := Y - 1, tarai(Y_1, Z, X, R_Y),
    Z_1 := Z - 1, tarai(Z_1, X, Y, R_Z),
    tarai(R_X, R_Y, R_Z, R).
```

は、以下に示すような抽象機械コードにコンパイルされます（コメント部分は手で追加したもの）。
それぞれの抽象機械コード命令の引数部分の `reg(in, N)`,  `reg(y, N)`, `reg(out, N)` が in レジスタ、y レジスタ、out レジスタの利用をそれぞれ表しています。x レジスタはこの例では使用していません。

```prolog
label(tarai/4).
  goal(tarai/4).
  requires(15).
  try_guard_else(label(tarai/4-2)).     % tarai(X, Y, _, R) :- 
  seq(2,6).                             %
    out_value(reg(in,1),reg(out,1)).    % X
    out_value(reg(in,2),reg(out,2)).    %  =< Y
    call((=<)/2).
  activate.                             % |
    get_value(reg(in,2),reg(in,4)).     % R = Y.
  proceed.
label(tarai/4-2).
  otherwise.                            % otherwise.
  activate.                             % tarai(X, Y, Z, R) :- true |
  par(2,6).
    out_value(reg(in,1),reg(out,1)).    % X_1
    out_variable(reg(y,5),reg(out,2)).  %     := X - 1,
    call('__dec__'/2).
  par(4,7).                             % tarai(
    out_value(reg(y,5),reg(out,1)).     %       X_1,
    out_value(reg(in,2),reg(out,2)).    %           Y,
    out_value(reg(in,3),reg(out,3)).    %             Z,
    out_variable(reg(y,6),reg(out,4)).  %               R_X
    spawn(tarai/4).                     %                  ),
  par(2,8).
    out_value(reg(in,2),reg(out,1)).    % Y_1
    out_variable(reg(y,7),reg(out,2)).  %    := Y - 1,
    call('__dec__'/2).
  par(4,9).                             % tarai(
    out_value(reg(y,7),reg(out,1)).     %       Y_1,
    out_value(reg(in,3),reg(out,2)).    %           Z,
    out_value(reg(in,1),reg(out,3)).    %             X,
    out_variable(reg(y,8),reg(out,4)).  %               R_Y
    spawn(tarai/4).                     %                  ),
  par(2,10).
    out_value(reg(in,3),reg(out,1)).    % Z_1
    out_variable(reg(y,9),reg(out,2)).  %    := Z - 1,
    call('__dec__'/2).
  par(4,11).                            % tarai(
    out_value(reg(y,9),reg(out,1)).     %       Z_1,
    out_value(reg(in,1),reg(out,2)).    %           X,
    out_value(reg(in,2),reg(out,3)).    %             Y,
    out_variable(reg(y,10),reg(out,4)). %               R_Z
    spawn(tarai/4).                     %                  ),
  tail(4,11).                           % tarai(
    out_value(reg(y,6),reg(out,1)).     %       R_X,
    out_value(reg(y,8),reg(out,2)).     %           R_Y,
    out_value(reg(y,10),reg(out,3)).    %               R_Z,
    out_value(reg(in,4),reg(out,4)).    %                   R
    execute(tarai/4).                   %                    ).
```

複合項（リスト、構造体）の一部である変数はそもそも複合項自体がヒープ上にあるためにその部分である変数もやはりヒープ上に存在します。このため、レジスタ内変数として割り当てるべきパターンは以下の一つしかありません：

- サブゴール呼び出し時点で初出の変数、かつ複合項の一部としてでなくサブゴールの引数に直接現れる変数

out_variable はこのような変数を割り付けるための命令です。

コンパイル結果を見ても、out_variable 命令において y レジスタに変数を割り付け、この変数を必要に応じて後続の命令が使う、という形になっているのが見て取れます。

# 結果

[色々な言語でたらい回し関数の速度を比較してみた](https://qiita.com/Freezer/items/7d00cfbe70493f026e16) を参考に、`tarai(15,5,0,X)` 実行時のメモリ使用量を修正前後で比較しました。

修正前

```
$ \time -o /dev/stdout -f 'real:%e[sec]_user:%U[sec]_sys:%S[sec]_Memory:%M[KB]' sample/tarai 15 5 0
% 12441815848 inferences(1 times resumed), 242.219 CPU seconds (51366025.172499 Lips)
15
real:246.24[sec]_user:230.81[sec]_sys:14.64[sec]_Memory:28929680[KB]
```

修正後

```
$ \time -o /dev/stdout -f 'real:%e[sec]_user:%U[sec]_sys:%S[sec]_Memory:%M[KB]' sample/tarai 15 5 0
% 12441815848 inferences(1 times resumed), 282.006 CPU seconds (44118930.909221 Lips)
15
real:282.27[sec]_user:281.97[sec]_sys:0.03[sec]_Memory:5880[KB]
```

28,929,680[KB] つまり 30GB 近いメモリ消費が 5,880[KB] つまり 5MB 程度にまで削減できました。

# まとめと感想

目論見通り、ヒープ使用量を削減することができました。

ヒープ使用量は削減できましたが、処理性能は若干落ちています。

経験的に、デリファレンス処理のループ内に分岐を追加すると処理性能が落ちることがわかっています。
今回も、新たなタグを追加したことによるデリファレンス性能劣化が性能低下につながったのではないかと推測しています。

とはいえ、ヒープ使用量削減の効果は大きいのでこの程度の処理性能の低下は止む得ないものとして受け入れることにしたいと思います。