HN 日本語サマリー

← 一覧へ戻る
プログラミング

ターボHaskell

Turbo Haskell (comonad.com)

202 pointsby pjmlp59 コメント

要約

Haskellコンパイラ「THC」は、GHCのプリムオペレーションの大部分を実装し、GraalVM上でHaskellコードを実行するJITコンパイラを提供します。これにより、Template HaskellやLinear Haskellなどの高度な機能もサポートされ、PandocやGHC自身を含む様々なプログラムのJIT/AOTコンパイルが可能になります。また、Python、Ruby、R、JavaScriptなどの他言語との相互運用性も強化されています。

全文翻訳

Turbo Haskell

ちょうど1週間前(冗談として)、休暇中にBartosz Milewski氏を訪ねている間に、私の「ターボHaskellコンパイラ」であるTHCの執筆を開始しました。

それ以来、わずかに成長しました。

THCは現在、GHC 9.14.1のすべてのprim-opsを実装しており、HaskellをJVM上で実行するためのGHC CoreのJITを提供しています。これは、私が数年前にCadenza(トーク)で開発した、TruffleとGraalVMを使用した型付き関数型言語実行アプローチを採用しています。

GHCは引き続き、パース、型チェック、デシュガーリング、Core最適化を担当します。THCはそこから引き継ぎ、独自のランタイム上でTruffle/GraalVMを介してCoreをコンパイル・実行します。Template HaskellやLinear Haskellのような高度な言語機能は完全にサポートされています。

GHCグレードのHaskellのJITとして使用できるだけでなく、Native ImageによるAhead-of-Time (AOT) コンパイルもサポートしており、実行可能ファイルを生成できます。

THCは、pandoc、happy、alex、そして本日からはGHC自身さえも、多数のHaskellプログラムをJITまたはAOTコンパイルできます。

THCはCabalを使用してパッケージを解決し、Backpackを含む複数のライブラリを持つパッケージも完全にサポートしています。

ライブラリの借用

THCは、Python、Ruby、R、JavaScriptへのポリグロットFFIを提供しており、Haskellは他の言語のライブラリを借用し、その出力を直接JITコンパイルされたHaskellプログラムに取り込むことができます。他のポリグロット言語内のUTF-8エンコードされた文字列に対するData.TextとTruffle文字列間のFFIを介した変換は、ゼロコピーで行われます。

アイデアとしては、データフレームが必要な場合、LLMを実行したい場合、またはD3.jsの可視化を行いたい場合は、単にTextを外部インポート経由で渡せばよいということです。inline-<language name>スタイルのクォートベースのバインディングも、実装はかなり容易になるはずです。

Haskellライブラリ内のC/C++コードは、ネイティブモードのSulong(JVM上のLLVM)へのFFIを介して実行されます。マネージドモードのSulong、つまりLLVMがJVM内で解釈され、ポインタが管理・ガベージコレクションされるモードも利用可能ですが、通常のforeign importパスでは使用されません。

評価と並行処理

内部的に、THCはTruffle評価のために2つの異なるバックエンドをサポートしています:バイトコードベースのJITターゲットと、従来のASTベースのJITターゲットです。どちらもシングルスレッドまたはマルチスレッドスタイルで実行でき、後者には追加のロックがあります。また、GHCバイトコード自体もサポートしているため、GHCiによって生成されたBCOコードを実行できます。

THCは、非同期例外をリジューム可能なコードを残して処理するthrowToとマスキングを完全にサポートしています。

THCは、「通常の」JavaスレッドとProject Loomの両方をサポートしており、後者上で、軽量なGHCスタイルのグリーン・スレッディングと、安価なMVarなどを可能にするHECスタイルのランタイムエグゼキュータを提供します。

SIMD

THCは、利用可能なGHC prim-opsの比較的限られた供給を利用してSIMDをサポートしていますが、さらに進んで、ランタイムでSIMDの「種」の幅を選択し、その情報を使用してインキュベーション中のVector API (jdk.incubator.vector) を介してループをJITコンパイルすることもできます。これにより、JITがその価値を発揮し始めます!

実際、ランタイムが実行時に完全なRuntimeRep-多相コードを提供することを妨げるものは何もありません。それは、その自由を利用するCoreがないという事実を除いては!

テールコール

ホットなテールコールはループになります。実行が通常のコールにフォールバックする必要がある場合、THCは蓄積されたスタックフレームを定期的にアンワインドします。

以前、JVM上で関数型コードを実行しようとした試み、例えばEtaプログラミング言語や、ScalazのモナドのトランポリンのためにRunar Bjarnasonと使用した設計では、トランポリンメカニズムが使用されていました。THCは代わりに、ホットなテールコールを、サイドエグジットを持つタイトな基本ブロック風のループ内に保持するためのコード変換トリックを使用します。

トレースモードでの再帰中に、THCは64ビットのBloomフィルターを埋め込み、再帰的なテールコールを検出します。可能性のあるヒットが見つかると、スローパス例外を発生させて継続を起動サイトに接続し、カスタムTruffleノードが現在のテールコールループを関数本体を横断してタイトなループに変換するようにGraalに指示します。偽陽性は追加のスローパス処理を意味しますが、プログラムの結果は変更しません。

後続のコードパスが分岐すると、THCはトレースJITのような追加のサイドループを成長させようとしますが、JVMの関数本体サイズの上限に達するまで続きます。その時点で、スタックフレームを「リーク」する形でテールコールを最終的にスピルします。

そのリークは一時的です。非同期例外が存在する場合のリジューム可能なコードをサポートするために必要だったメカニズムを再利用して、CHICKEN Schemeのガベージコレクション戦略にいくぶん似たトリックを使用して、蓄積されたスタックフレームをコンパクト化できます。その結果、ホットなループは非常にホットに実行できます。

特にData.Mapのベンチマークを行ったところ、数百万回の高速パスコールと比較して、約66回のフォールバックトランポリンコールが必要であることがわかりました。

パフォーマンス

ランタイムは、圧縮普通オブジェクトポインタ(compressed oops)を使用することもできます。これらは、ヒープ参照を完全な64ビットポインタの代わりに32ビットオフセットとして表現し、参照のメモリ使用量を削減し、より多くのデータがキャッシュに収まるようにします。JVMの通常の8バイトオブジェクトアラインメントでは、このモードで実行する場合、ヒープは約32GBに制限されます。

パフォーマンスは、開発の最初の数日間の重要な考慮事項でした。Data.Mapなどのテストでは、ウォームアップ後、一般的に3倍高速から3倍低速の範囲で実行させることができ、ほとんどはGHCより10〜20%低速でした。とはいえ、ここ数日はより広範なカバレッジを目指して競っていたためベンチマークを行っておらず、その間に簡単なベンチマークで10倍程度のパフォーマンス低下に見舞われました。開発努力は、これを制御下に置くために引き続き取り組んでいます。

非テールコールパスでのスタック成長がGHCのスタック使用量に対して制限されたままであるかどうかは、まだテストしていません。その制限を保証することは、将来の作業の可能性があります。

開発

コードはgithub.com/ekmett/thcで利用可能で、ドキュメントにはTHCのビルド、実行、使用方法が記載されています。

開発はirc.libera.chatの##thcチャンネルで進められています。

ぜひご参加ください。

— Edward Kmett

Redditで議論する