Gauche:グローバル変数参照の最適化

0.8.4に向けてコンパイラをチューニングしている過程で、グローバル変数参照のオーバヘッドが無視できないファクタとして浮上してきた。色々入り組んでいるので、後々のためにメモしておく。

前提となる仕組み

Gaucheでは、グローバル変数束縛はmoduleによって管理される。

グローバル変数参照は、Scm_FindBinding (module.c) によって解決される。これは指定モジュールおよびそこから可視のモジュール中から、指定された名前に束縛されているGLOC (global location) オブジェクトを探して返すもの。

この操作は軽いものではないので、実行時のグローバル変数参照のたびに行うわけにはいかない。ソース上の各グローバル変数の出現につき、 Scm_FindBindingがたかだか2回しか呼ばれないようになっている。

コンパイル時に1回、その変数がオペレータ位置にある場合はマクロや構文束縛がないか、またそれ以外の位置にある場合でも定数ではないかを確認するためにScm_FindBindingが呼ばれる。
グローバル変数参照であると確定した場合 (マクロや定数としてコンパイル時に展開されなかった場合)、VMコードのGREFインストラクションのオペランドとして、該当変数がidentifier (モジュールスコープと名前をカプセル化したもの)として埋め込まれる。実行時にVMがGREFインストラクションを実行する際に、そのオペランドがidentifierであればScm_FindBindingを呼んで、得られたGLOCオブジェクトでオペランドを置き換える。以降の変数アクセスは直接GLOCオブジェクトを介して行われ、テーブルルックアップは省かれる。

このような仕組みにしてはいるが、巨大なソースを読み込む場合などは Scm_FindBindingの呼び出しが上がって来る。

最適化の軌跡

ロックについて

以前のGaucheではモジュール毎にロックを持って置いて、束縛テーブルのアクセス時にそのモジュールのロックを獲得するようにしていた。Scm_FindBindingはたいてい複数のモジュールを見にゆくので、何度もmutex_lockを呼ぶことになる。プロファイリングしたところ、プログラムロード時 (コンパイル時間が多くを占める) に mutex操作がかなりの部分を占めていることが判明。

プログラムのロードが多くの場合はスタートアップ時に集中しており、従って束縛テーブルのアクセスもそこに集中することから、モジュール毎という粒度でのロックは却ってオーバヘッドが大きいと判断。モジュールアクセス全てに共通するロックをひとつ作って、Scm_FindBindingはそれひとつだけをロックするようにした。これで20〜30%のロード時間の改善が見られた。

この時点で、Scm_FindBindingに費される時間は大きなソースを読み込む場合、ロード時間の4%くらい。

どこを、どのくらい探しているのか

Scm_FindBindingは、次の順に束縛を探す。

指定モジュール(base)
importしているモジュールとその親モジュール
親モジュール

(2で重複するモジュールがあり得るが、Scm_FindBinding中で一度探したモジュールを覚えてるので重複して探しに行くことはない)。

それぞれの段階でどのくらいの時間を費しているかを測ってみた。大きなソースファイルの場合、こんな感じ。

	探索に費す時間配分	束縛を見つけた割合
base	1	14%
import	2	2%
parent	1	84%

また、一回のScm_FindBindingで見に行くモジュール数の平均は17個くらい。うち、重複を避けて実際に探しに行くのは7個くらい。

見て取れること：

多くの場合、求めるシンボルは親モジュールのどれか (組み込み関数なら、gauche とかschemeモジュールが多いだろう) にある。
でもそこにたどりつくまでに、importしてるモジュール (とその親) をとりあえず全部見なくちゃならない。 importしてるモジュールの場合、ハッシュテーブルでヒットするかだけでなく、それがexportされているかを調べる必要があるので結構重い。 (もっとも、exportの検査はハッシュテーブルでヒットした場合のみなんで、実はそれほど大きくないかもしれん)。

ふむ。importしてるモジュールの探索に工夫が必要そうだ。

うーむ。一度探したモジュールの結果のキャッシュ方法を変えてみたり、クラスに倣って module precedence listのキャッシュ版module precedence arrayを入れてみたりしたけど、あまり速くならない。exportの検査は工夫の余地があるかもしれないけど、Scm_FindBinding本体の時間を削るのはしばらく置いておいて、Scm_FindBindingの呼び出し自体を削る方法を考えようか。

一回で済ませられないか

コンパイル時にScm_FindBindingでGLOCが得られた場合、直接それをコードに埋め込むことで実行時のScm_FindBinding呼び出しを省けないだろうか。

コンパイル時にGLOCが見つからない場合というのは、コンパイル時にまだ未定義のグローバル変数を参照している場合だが、その時は今まで通り実行時まで解決を遅らせればいい。

考えられる問題

GLOCは実行時の情報なので、バッチコンパイルを行って結果を Cに落としておく場合に使えない。バッチコンパイルとそれ以外の場合とで動作を変える必要がある。
コンパイル後、実行前のタイミングで、コンパイル時に見付けた束縛をシャドウするような束縛が導入された場合の動作が今までと異なることになる。

コンパイルユニット単位でキャッシュできない?

コンパイルユニット (requireとかloadするファイル単位) を考えると、そのコンパイル中に現在コンパイルしているモジュールから見える束縛が変化することは考えにくい。確かにマルチスレッドでloadが走っている間に別スレッドで見えているモジュールに束縛を追加したりすれば変化は起きるが、そもそもそういう事態が予測困難なことであり、それによってふるまいが変わるようなコーディングはまずいと言える。

それならば、コンパイルユニット単位で一度Scm_FindBindingかけた結果をハッシュテーブルかなんかに取っといたらどうか。同じシンボルが何度も何度もルックアップされてるはずなので、結構いけるかもしれない。

現在はコンパイルユニットを表現する機構がコンパイラから見える範囲に無いので、それを作る必要はある。

それと、load中にwith-moduleで別モジュールに行ってdefineするとか、 select-moduleでモジュールを切替えまくるとか、そういう場合の扱いをどうするかだな。