月刊LunarML進捗報告です。前回は

• LunarML進捗・2022年6月
• LunarMLが自身をコンパイルできるようになった

あたりです。

JavaScriptバックエンドの高速化

第2世代コンパイラーでJS-CPSバックエンドを使って第3世代コンパイラーを生成するのに3時間以上かかるのはいくら何でも遅いので、高速化しました。

LunarMLでLuaやJavaScriptのコードを生成する際に、一旦文字列のリスト（string list）を生成して最後に String.concat しています。この際に @ 演算子でリストの連結をやっていると遅いので、差分リスト (difference list) というテクニックを使って高速化しました。差分リストはHaskellの ShowS とかでお馴染みのやつです。

差分リスト以外にも似たような改善をちょこちょこやった結果、JS-CPSバックエンドがLuaバックエンド並みに速くなりました。それでもまだ数分かかりますが……。

Luaバックエンドは差分リスト化していないので、まだ高速化の余地があるのかもしれません。

LuaJITバックエンド

普通のLuaが遅いならLuaJITで動かそう、ということでLuaJITバックエンドを実装することにしました。

これまで実装していたのはLua 5.3をターゲットとするコード生成器です。LuaJITはLua 5.1互換です。Luaは小数点以下が違ったら互換性のない別言語なので、これまでのLuaバックエンドで生成したコードはそのままではLuaJITでは動きません。

Lua 5.3とLuaJITの最も（LunarMLにとって）重大な違いは、数値型周りです。Lua 5.3は整数と浮動小数点数の区別がありますが、LuaJITは基本的に浮動小数点数のみです。ただ、素のLua 5.1とは違って拡張で64ビット整数も扱えます。

この辺の話は

• Luaの数値型

という記事にまとめました。

LunarMLのテストを動かしていると、LuaJITのバグを2件見つけました。両方浮動小数点数の0の符号に関するものです。報告しましたが、1件は修正され、もう1件はwon’t fixとなりました。

• Negative zero in dual number mode · Issue #858 · LuaJIT/LuaJIT
  • won’t fix
  • AArch64などで発現し、x86系では発現しません
  • LunarML側で対策を打つことにしました
• math.ceil fails to return `-0` for `-1 < x < -0.5` · Issue #859 · LuaJIT/LuaJIT
  • 修正済み
  • x86系では発現し、AArch64では発現しません
  • x86系では修正されたけど、他のアーキは大丈夫なんだろうか？

LuaJITのリリースタイミングは謎なので（最後のリリースが5年前のベータ版）、修正を取り込んだバージョンがリリースされるのがいつになるのかは謎です。

Luaでは関数の外のスコープで定義されたレキシカルな変数（local変数）を上位値 (upvalue) と呼びます。例えば、次のコードにおいて f にとっての x は上位値であり、 y は上位値ではないグローバル変数です。

local x = 42
function f()
   return x + y
end

Lua 5.1の頃は一つの関数が持てる上位値の個数は60個まででしたが、Lua 5.2以降では制限が255個に緩和されました。ですが、LuaJITはLua 5.1の60個という制限を受け継いでいます。

LunarML自身を素直にコンパイルして生成されたLuaコードは60個以上の上位値を利用していたので、LuaJITで動かすには対策が必要となりました。どうするかというと、適当にテーブルを用意して溢れた上位値をキャプチャーします。キャプチャーする変数は「その後変更されない」変数である必要があります。

LuaJIT特有の問題として、ある程度大きい関数をコンパイルすると “function too long for return fixup near ‘end'” というエラーが出ました。これは簡単な説明が難しいのですが、以下のような関数をLuaJITでバイトコードにコンパイルした際に

function f()
  local a = 1
  if ... then
    return 0 -- 最初の関数リテラルに遭遇する前のreturn
  end
  ...
  g = function() return a end -- 関数リテラル
  ...
end

内部に関数リテラルを持つ関数からreturnする部分は「関数内のローカル変数をcloseする命令」の後にジャンプを行うようにコンパイルされます。ですが、最初の関数リテラルに遭遇するまでに出現したreturnには「closeする命令」が伴っていません。この場合、LuaJITはそういうreturn命令を関数末尾へのジャンプ命令に書き換え、そこでcloseとジャンプを行うようにします。

関数が大きいと、この際の「関数末尾へのジャンプ命令」がバイトコードで表現できる範囲外となって前述のエラーが出るのです。

対策としては、内部に関数リテラルを含むある程度大きな関数をコンパイルする際は、関数の最初にダミーの関数リテラルを設置するようにします。例えば、さっきの例は次のように変換します：

function f()
  if true then else -- if false then よりも if true then else の方が生成されるバイトコードが短そう
    local DUMMY = function() end -- ダミーの関数(この部分は実行されないのでコストはかからない)
  end
  local a = 1
  if ... then
    return 0 -- 最初の関数リテラルに遭遇する前のreturn改め、最初の関数リテラルに遭遇した後のreturn
  end
  ...
  g = function() return a end -- 関数リテラル
  ...
end

こうすることで、関数内のすべてのreturnがclose命令付きのジャンプとしてコンパイルされ、fixupが発生しなくなります。

このほか、LuaJITはスタックサイズが厳しいのか、 List.tabulate や List.@ も末尾再帰にする必要がありました。List.tabulate は構築するリストの長さが短い時は末尾再帰にしないようにしてみました。

色々やってLunarMLがLuaJITで動くようになりましたが、結局のところLuaJITでLunarMLを動かしてもLua 5.3と比べて大きな高速化にはなりませんでした。高速化にはやはり適切な中間コードと最適化が必要なのでしょう。

IntInfの高速化：短除算

LunarMLのLuaバックエンドではSMLで書かれたIntInf（多倍長整数）を使用しており、標準ライブラリーのテストでも多倍長整数の演算をガンガン使っています。それがLuaJITだとLua 5.3と比べて大幅に遅く、耐え難いレベルとなっていました。

遅いのはフィボナッチ数列を十進出力するテストです。多倍長整数の足し算はそんなに遅くないと思うのですが、文字列化の際の基数変換に使う除算が遅いために時間を食ってしまうのです。

基数変換に使う除算は多倍長整数を1ワードで割るやつなので、その場合を高速化すれば良いです。多項式除算の場合は組立除法みたいな効率の良い除算アルゴリズムがありますが、多倍長整数の場合も似たような効率の良いアルゴリズム（短除算）があるので、それを実装しました。詳しくはThe Art of Computer Programming Vol 2を見てください。

それでLuaJITでフィボナッチ数列を計算するやつも高速化されました。もちろん、Lua 5.3のやつも同じアルゴリズムで高速化されているので、LuaJITは相対的には遅いままです。

多倍長整数に関してはいずれKaratsuba乗算や分割統治による基数変換（一部ではKaratsuba基数変換と呼ばれている）も実装したいところですが、それはまた今度にします。

Lua 5.3とLuaJITの両方で動くコード？

これまでのLuaバックエンドの出力するコードはLua 5.3/5.4を前提としています。また、今回追加したLuaJITバックエンドはLuaJIT 2.1を前提としています。

Luaはバージョンを跨ぐと互換性が保証されないとは言え、うまく書けばLua 5.3とLuaJITの両方で動作するコードを書けるはずです。LunarMLでLua 5.3とLuaJITの両方で動くようなコードを出力するオプションがあってもいいかもしれません。

具体的には、Luaのバージョンを見て整数周りを切り替えてやればLua 5.3とLuaJITの両方で動作するコードが出力できるはずです。

しかし、実際のところ「Lua 5.3とLuaJITの両方で動くコード」にそれほどの需要があるのでしょうか？Luaを組み込む環境というのは大抵は5.3以降に移行したかLua 5.1/LuaJITを使い続けるかのどちらかが多いと考えられます（要調査）。

とはいえ、LunarML自体をコンパイルしてできたLuaコードはLua 5.3/LuaJITの両方で動くと嬉しいかもしれません。

標準ライブラリーの充実

ぼちぼちと進めています。

SMLUnitの標準ライブラリーに対するテストが動かせれば良いのですが、足りない機能がまだ多いです。

作りたいアプリケーション

そろそろコンパイラー以外も書きたいです。

前に「WebGLで何かしたい」という旨を書きました。JavaScriptバックエンドがある程度機能するようになった今、それは不可能ではないはずです。

しかし、CGに使う行列やベクトルの型はStandard MLでどう表したら良いのでしょうか。サイズごとに別々の型を定義するべきか、 (three, four) matrix のようにサイズでパラメーター化するべきか。演算については乗算 * を使えると便利ですが、アドホックに拡張してしまうとSMLらしさが失われます。まあやってみたら何とかなるのかもしれませんが。

Webアプリケーションも書きたいです。筆者はVPSは持ってなくてレンタルサーバーだけなので、CGIとかPHPとかで動かせるのが望ましいです。

というわけでPHPバックエンドをそろそろ真面目に考えたいです。

PHPは整数と浮動小数点数が分かれています。その点ではJavaScriptよりはLua 5.3っぽいです。ですが、整数演算がオーバーフローした場合はwrap aroundせずに浮動小数点数になります。なので、Intの演算のオーバーフロー検査は容易にできますが、Wordの演算（wrap aroundする）をどうやって提供するかという問題があります。

LuaやJavaScriptバックエンドの場合は筆者がターゲット言語に習熟した状態で始めましたが、筆者はPHPに習熟していないので、PHPを勉強するところからスタートする必要があります。

その他

GitHub Actionsでpush時にテストを実行するようにしました。aptでMLtonとかを入れます。ただ、aptで入るLuaJITは多分math.ceilがバグってるのでLuaJITのテストは実行していません。ソースから入れればいいのかもしれないけど。

---

LunarMLは以下のGitHubリポジトリーで開発しています。面白そうだと思っていただけましたらスターをお願いします。

• minoki/LunarML: A Standard ML compiler that produces Lua/JavaScript