KOTET'S PERSONAL BLOG

#dlang 新・CTFEエンジンについて【翻訳】

Created: , Last modified:
#dlang #tech #translation #d_blog

これは1年以上前の記事です

ここに書かれている情報、見解は現在のものとは異なっている場合があります。

この記事は

The New CTFE Engine – The D Blog

の翻訳である。 ぼーっと読んでたら途中でわけがわからなくなってきたので、しっかり翻訳しようと思って書いた。 その後翻訳の公開の許可を取り、 無事承諾していただけた のでここに公開する。 翻訳できていないところや訳の怪しいところがあるので、気になったら今すぐ Pull request だ!

Stefan KochはDのネイティヴなsqliteリーダー、sqlite-d のメンテナーであり、SDC(the Stupid D Compiler)や vibe.dのようなプロジェクトに貢献していました。 彼はDの現在のCTFE実装の10%のパフォーマンス改善のかつての責任者でもあり、現在はこの投稿の対象である新CTFEエンジンを書いています。

9ヶ月前、私はNewCTFEと呼ばれる、Dコンパイラフロントエンドのコンパイル時関数実行(CTFE) 機能の再実装のプロジェクトで作業をしていました。 CTFEはDの革新的機能とされています。

その名前が示すように、CTFEは関数が実装されているソースコードのコンパイル時にコンパイラが関数を実行できるようにします。 関数のすべての引数がコンパイル時に利用可能で、関数が純粋(副作用を持たない)な限り、関数はCTFEの資格を持ちます。 コンパイラは関数呼び出しをその結果で置き換えます。

これは言語の切り離せない部分のため、コンパイル時定数の行くところどこでも純粋関数を実行できます。 シンプルな例を標準ライブラリモジュール、 std.uriに見ることができ、ここでCTFEはルックアップテーブルを計算するために使われています。 このようなものです:

private immutable ubyte[128] uri_flags = // indexed by character
({

    ubyte[128] uflags;

    // Compile time initialize
    uflags['#'] |= URI_Hash;

    foreach (c; 'A' .. 'Z' + 1)
    {
        uflags[c] |= URI_Alpha;
        uflags[c + 0x20] |= URI_Alpha; // lowercase letters

    }

    foreach (c; '0' .. '9' + 1) uflags[c] |= URI_Digit;

    foreach (c; ";/?:@&=+$,") uflags[c] |= URI_Reserved;

    foreach (c; "-_.!~*'()") uflags[c] |= URI_Mark;

    return uflags;

})();

テーブルにマジックバリューを入れる代わりに、シンプルで意味のある関数リテラル が使われています。 これは不透明な静的配列より理解とデバッグが簡単です。 ({で関数リテラルが始まり、})で閉じられます。 最後の()はuri_flagsがリテラルの結果になるようコンパイラにリテラルを即座に呼びださせます。

関数は必要な時のみコンパイル時に実行されます。 上のスニペットのuri_flagsはモジュールスコープで宣言されています。 このマナーの中でモジュールスコープ変数が初期化される時、初期化子はコンパイル時に利用可能でなければなりません。 このケースで、初期化子は関数リテラルのため、CTFEの実行が試みられます。 この独特なリテラルは引数を持たず純粋のため、試みは成功します。

CTFEのより詳細な議論については、D wikiのH. S. Teohの このアーティクルを見てください。

もちろん、より複雑な問題にも同じテクニックが適用できます。 たとえば、std.regexは正規表現にスペシャライズされたオートマトンをCTFEを使いコンパイル時にビルドできます。 しかし、std.regexが非自明なパターンのCTFEで使われるとすぐに、コンパイル時間が非常に長くなることがあります(Dではコンパイルに1秒以上かかるすべてがブロートウェアです:))。 結局、パターンがより複雑になれば、コンパイラはメモリ不足になりすべてのシステムをダウンさせるかもしれません。

これに対する責任は現在のCTFEインタプリタのアーキテクチャのものにできます。 それはASTインタプリタ、ASTをトラバースする間それを解釈するものです。 解釈された式の結果を表現するために、DMDのASTノードクラスを使います。 これは遭遇するすべての式が1つ以上のASTノードをアロケートすることを意味します。 最奥ループ内で、インタプリタはたやすく100_000_000以上のノードを生成し、RAMの数ギガバイトを食いつぶします。 それはメモリを非常に速く消耗させます。

Issue 12844はstd.regexがRAMを16ギガバイト以上消費することについてのものです。 ひとつのパターンで、です。 単純な0から10_000_000までのwhileループをCTFEで実行するとメモリ不足に陥るIssue 6498もあります。

単純にノードを解放することは問題を解決しません。 どのノードがフリーかはわからず、ガベージコレクタを有効にするとコンパイラ全体が非常に遅くなります。 幸いにも式に遭遇するたびに毎回アロケートしないという別のアプローチがあります。 それは関数をバーチャルISA(命令セットアーキテクチャ)にコンパイルすることを含みます。 バイトコードとしても知られるこのISAは、そのISAに向けて専門化されたインタプリタに渡されます (このケースで、バーチャルISAの中でホストのISAと同じことがおこり、それをJIT(Just in Time)インタプリタと呼びます)。

NewCTFEプロジェクトはそのようなバイトコードインタプリタを扱うものです。 実際にインタプリタ(バーチャルCPU/ISA用CPUエミュレータ)を書くことは割とシンプルです。 しかし、コードをバーチャルISAにコンパイルすることはリアルISAにコンパイルすることと同じ仕事量です (が、バーチャルISAは個別のニーズのために拡張できるという追加のベネフィットがあります。しかしそれにより後でJITをするのに困難が伴います)。 それが最初のシンプルなサンプルが新CTFEエンジン上で走るだけで1ヶ月を要した理由で、ちょっと複雑なものは開発9ヶ月後まで動かなかった理由です。 ポストの最後で、今までの仕事のおおよそのタイムラインを見ることができます。

私はDConf 2017でプレゼンテーションを行い、 エンジンの実装の経験について話し、技術的詳細、特に私が作ったトレードオフとデザインチョイスに関することを説明します。 現在の見積もりでは1.0のゴールはその時には間に合いませんが、完了するまでコーディングを続けます。

私の進捗を追うことに興味がある人はDフォーラム で私のステータスアップデートをフォローできます。 将来のある時点で、私は実装の技術的詳細について別のアーティクルを書きます。 その間、下のリストがNewCTFEの実装にどれだけの作業をしているか明らかにしてくれるでしょう🙂