ターボHaskell

ちょうど一週間前（冗談として）、休暇中にBartosz Milewskiを訪ねている間に、私の「ターボHaskellコンパイラ」であるTHCを書き始めました。それ以来、少し成長しました。 THCは現在、GHC 9.14.1のプリムオペレーションのすべてを実装しており、GraalVM上でHaskellを実行する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間のFFIによる変換はゼロコピーです。 アイデアは、データフレームが必要な場合、LLMを実行したい場合、またはD3.jsの可視化を実行したい場合は、単にTextを外部インポート経由で渡すべきだということです。 準引用ベースのinline-<言語名>スタイルのバインディングも実装するのはかなり簡単でしょう。 Haskellライブラリ内のC/C++ビットは、ネイティブモードのSulong（JVM上のLLVM）へのFFIを介して実行されます。 JVM内でLLVMが解釈され、ポインタが管理およびガベージコレクションされるマネージドモードのSulongも利用可能ですが、通常の外部インポートパスでは使用されません。 評価と並行性 内部的には、THCはTruffle評価のために2つの異なるバックエンドをサポートしています。バイトコードベースのJITターゲットと、従来のASTベースのJITターゲットです。 どちらもシングルスレッドまたはマルチスレッドスタイルで実行でき、後者には追加のロックがあります。 また、GHCバイトコード自体もサポートしているため、GHCiによって生成されたBCOコードを実行できます。 THCは、復帰可能なコードを残して非同期例外を発生させるthrowToと、マスキングを完全にサポートしています。 THCは、「通常の」JavaスレッドとProject Loomの両方をサポートしており、それ上で、軽量なGHCスタイルのグリーン・スレッディングを、安価なMVarsなどを可能にするHECスタイルのランタイムエグゼキュータと共に提供します。 SIMD THCは、利用可能なGHCプリムオペレーションの比較的限られた供給を使用してSIMDをサポートしていますが、さらに進んで、ランタイムでSIMD「種」幅の選択を可能にし、インキュベート中のVector API（jdk.incubator.vector）を通じてその情報を使用してループをJITコンパイルします。 これにより、JITは真価を発揮し始めます！ 実際、ランタイムが完全なRuntimeRep-多態コードを実行時に提供することを妨げるものは何もありません。それは、その自由を利用するCoreがないという事実以外にはありません！ 末尾再帰呼び出し ホットな末尾再帰呼び出しはループになります。実行が通常の呼び出しにフォールバックする必要がある場合、THCは定期的に累積されたスタックフレームをアンワインドします。 JVM上で関数型コードを実行する以前の試み（例：Etaプログラミング言語、Runar BjarnasonとのScalazのモナドのトランポリンのための設計）は、トランポリンメカニズムを使用していました。 THCは代わりに、ホットな末尾再帰呼び出しを、サイドエグジットを備えたタイトな基本ブロックスタイルのループ内に維持するためのコード変換トリックを使用します。 トレースモードでの再帰中に、THCは64ビットブルームフィルタを埋めて、可能性のある再帰的な末尾再帰呼び出しを検出します。 可能性のあるヒットを見つけると、継続を起動サイトに接続するために低速パス例外をスローし、カスタムTruffleノードがGraalに現在の末尾再帰呼び出しループを関数本体を横断してタイトなループに変換させます。 偽陽性は追加の低速パス作業を意味します。プログラムの結果は変更しません。 後でコードパスが分岐すると、THCはトレースJITのような追加のサイドループを成長させようとしますが、JVMの関数本体サイズの制限に達します。 その時点で、スタックフレームを「リーク」する形で末尾再帰呼び出しを最終的にスピルします。 そのリークは一時的です。 CHICKEN Schemeのガベージコレクション戦略に似たトリックを使用して累積されたスタックフレームをコンパクト化できます。これは、非同期例外が存在する状況で復帰可能なコードをサポートするために必要だったメカニズムを再利用します。 結果として、ホットなループは非常にホットに実行できます。 特にData.Mapをベンチマークしたところ、数百万回の高速パス呼び出しと比較して、約66回のフォールバックトランポリン呼び出しが必要であることがわかりました。 パフォーマンス ランタイムは、圧縮された通常のオブジェクトポインタ（圧縮Oop）も使用できます。これらは、ヒープ参照を完全な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で議論する。