HN 日本語サマリー

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

JITコンパイルを5μsで実行する

JIT Compiling Code in 5μs (malisper.me)

142 pointsby zX41ZdbW91 コメント

要約

この記事では、AIの助けを借りて、わずか5マイクロ秒でコードをコンパイルできる高速JITコンパイラを構築する方法を解説しています。従来のJITコンパイラ開発の難しさや、LLVMやC++コード生成の限界に触れつつ、pgrustプロジェクトでの経験を基に、ARM64アセンブリを直接ターゲットとする「コピー&パッチ」方式のJITコンパイル手法を、簡単な正規表現エンジンの例を用いて具体的に説明しています。これにより、SQLクエリ全体をJITコンパイルすることが可能になり、パフォーマンスが大幅に向上します。

全文翻訳

JITコンパイルを5μsで実現

かつて、高速なJITコンパイラは秘伝の技でした。高速なJITコンパイラを書くには、アセンブリ言語の知識が必要でした。例えば、現在プロダクションレベルで稼働しているデータベースで、独自のJITコンパイラを持つものは存在しません。それらはすべてLLVMを使用するか、C/C++コードを生成しています。これらの選択肢はどちらもコンパイル時間が長いため、適用範囲が限定されます。しかし、AIの利用により、直接アセンブリをターゲットとして高速なコンパイル時間を持つJITコンパイラを書くことが、かつてないほど容易になりました。これは、新しいデータベースが古いデータベースを改善する機会でもあります。pgrustを構築する際、当初はJITコンパイラの実装は非常に難しいだろうと考えていました。しかし、AIの支援のおかげで、予想よりもはるかに簡単であることがわかり、pgrustが非常に高速である理由の一部となっています。pgrustのJITコンパイラは、約5μsでコードをコンパイルするため、サブセットだけでなく、すべてのSQLクエリをJITコンパイルできます。この記事では、独自の高速JITコンパイラを構築する方法を解説します。例として、JITコンパイルを使用する簡単な正規表現エンジンを構築します。

なぜJITコンパイルなのか

JITコンパイルとは、実行時にコンパイル済みコードを生成する「Just In Time」という手法です。適切に行われれば、パフォーマンスが劇的に向上し、多くの場合2〜5倍、時にはそれ以上になります。JITコンパイルの主なユースケースは、実行時に得られる情報がプログラムの動作を劇的に変更する場合です。これは特にプログラミング言語インタプリタで一般的です。インタプリタは実行時に実行するコードを受け取ります。JITコンパイラは、プログラミング言語以外のドメイン、例えばデータ解析などでも役立ちます。実行時に解析するデータのスキーマがわからない場合があり、JITが役立ちます。


まず、おもちゃの正規表現エンジンを実装しましょう。シンプルにするために、リテラル文字列と繰り返し(つまり、正規表現の *)のみをサポートします。パーサーはスキップし、正規表現を既に解析されたRustの構造体として表現します。これは、次のような文字列をサポートできることを意味します。

  • apples
  • b(an)

しかし、代替(alternation)や後読み(lookbehind)などはサポートしません。

コードではこれは非常にシンプルです。3種類のNodeがあります:リテラル文字列ノード、繰り返しノード、そして2つのノードの組み合わせである連結ノードです。これは次のような形になります。

enum Node {
    Literal(&'static str),
    Concatenation(Box<Node>, Box<Node>),
    Repetition(Box<Node>),
}

fn literal(text: &'static str) -> Node {
    Node::Literal(text)
}

fn concatenation(left: Node, right: Node) -> Node {
    Node::Concatenation(Box::new(left), Box::new(right))
}

fn repetition(body: Node) -> Node {
    Node::Repetition(Box::new(body))
}

正規表現エンジンのインタプリタを書くのも簡単です。

fn match_node(node: &Node, input: &[u8], pos: usize, next: &dyn Fn(usize) -> bool) -> bool {
    match node {
        Node::Literal(text) => {
            let literal = text.as_bytes();
            input[pos..].starts_with(literal) && next(pos + literal.len())
        }

        Node::Concatenation(left, right) => {
            match_node(left, input, pos, &|left_end| {
                match_node(right, input, left_end, next)
            })
        }

        Node::Repetition(body) -> {
            match_node(body, input, pos, &|body_end| {
                match_node(node, input, body_end, next)
            }) || next(pos)
        }
    }
}

fn interp_match(regex: &Node, input: &str) -> bool {
    let bytes = input.as_bytes();
    match_node(regex, bytes, 0, &|pos| pos == bytes.len())
}

この正規表現エンジンは非常にシンプルです。コードは20行未満ですが、パフォーマンスはどうでしょうか。比較のために、正規表現専用に手書きされたコードと比較します。例として、正規表現 b(an)* を使用します。手書きコードは次のようになります。

fn handwritten_b_an_star(input: &str) -> bool {
    let bytes = input.as_bytes();
    let mut pos = 0;

    if pos == bytes.len() || bytes[pos] != b'b' {
        return false;
    }
    pos += 1;

    while pos < bytes.len() {
        if bytes[pos] != b'a' {
            return false;
        }
        pos += 1;
        if pos == bytes.len() || bytes[pos] != b'n' {
            return false;
        }
        pos += 1;
    }
    true
}

(このコードを最適化してさらに高速化する方法はありますが、ここでは比較対象として十分です)

これらの2つをいくつかの例でベンチマークすると、手書きバージョンはインタプリタよりも10〜20倍高速であることがわかりました。明らかに改善の余地があります。

次に、JITコンパイルを使用して、手書きバージョンと同等のパフォーマンスを持つ汎用正規表現エンジンをどのように使用できるかを見てみましょう。

JITコンパイルの方法

JITコンパイルには2つのステップがあります。まず、実行したいコードのアセンブリを生成します。コードができたら、そのアセンブリコードをプログラム内の他のコードと同じように呼び出せる関数にパッケージ化します。

アセンブリを生成するために、コピー&パッチと呼ばれるアプローチのバリアントを使用します。このアイデアは、JITコンパイルしたいさまざまな操作のためのアセンブリテンプレートのシリーズを持っているということです。これらのテンプレートは「ステンシル」と呼ばれます。操作をJITコンパイルしたい場合は、関連するステンシルを取得し、操作の具体性に基づいて小さな調整を加えます。実際のステンシルに記入するのと非常によく似ています。これらの記入済みのステンシルをいくつか連結することで、手書きバージョンと同等のパフォーマンスを持つプログラムを実行時に構築できます。

ここでは、b(an)* のために生成したいARM64コードを見ていきます。次に、繰り返し命令シーケンスを再利用可能なステンシルに変換し、正規表現ASTからそれらのステンシルを埋め込むエミッタを書き、最後に生成された命令を実行可能メモリにコピーしてRustが通常の関数のように呼び出せるようにします。

これをどのように行うかを説明するために、生成されたコードから始めてJITコンパイラ自体に向かって逆方向に作業するのが最も簡単です。ここでも、正規表現 b(an)* を扱います。設計上の決定をいくつか示します。

  • バックトラッキングにはスタックを使用します。スタックは、行き詰まった場合に遷移すべき状態を追跡します。
  • マッチングする文字列はヌルバイトで終わります。これは、文字列の終わりに達すると、すべての文字比較が自動的に失敗することを意味します。これにより、長さを比較する必要がなくなります。

プログラムの状態には、次のレジスタを使用します。

  • x0 – 文字列内の現在の位置と戻り値
  • x1 – バックトラッキングに使用するスタックのトップ
  • x2 – バックトラッキングに使用するスタックのボトム(スタックが空かどうかを判断するために必要です)
  • x9 – 一時変数として使用

プログラムの入力として、次のものが渡されます。

  • x0 – 文字列の開始ポインタ
  • x1 – スタックに使用する場所のポインタ
生成されたARM64

これで準備ができたので、生成されたアセンブリを部分ごとに見ていきましょう。これは特にmacOSのARM64です。まず、プログラムを初期化するプロローグです。これが行うことはすべて、スタックトップとスタックボトムを渡された値に設定してスタックを初期化することです。

0:  aa0103e2   mov   x2, x1

次に、文字 b をチェックするコードです。 b 以外の文字が見つかった場合は、フォールバックロジックを処理するコードブロックにジャンプします。そうでない場合は、文字列内の位置を進めます。

; CHAR 'b'
  4:  39400009   ldrb  w9, [x0]                  ; 現在の入力バイトをロード
  8:  7101893f   cmp   w9, #0x62                 ; 'b' か?
  c:  54000281   b.ne  0x5c                      ; いいえ -> フォールバックブロック
 10:  91000400   add   x0, x0, #1                ; はい -> 入力を進める

次に、繰り返し(an)*です。繰り返しにはバックトラッキングが必要です。ここでバックトラックする場合、ループの終了に直接ジャンプすることを意味します。これは、ループの後の命令のアドレスと文字列内の位置の両方をスタックに保存する必要があることを意味します。

 14:  d2800989   movz  x9, #0x004c               ; 再開アドレスを構築
 18:  f2a00009   movk  x9, #0x0000, lsl #16      ;   = 0x1_0000_004c
 1c:  f2c00029   movk  x9, #0x0001, lsl #32      ;   (ループ終了)
 20:  f2e00009   movk  x9, #0x0000, lsl #48      ; 
 24:  a8810029   stp   x9, x0, [x1], #16         ; (終了、位置) をスタックにプッシュ

これが配置されたら、繰り返しの本体を実行できます。これは、文字 'a' と 'n' をチェックし、それらが見つかった場合は、新しい文字列位置で繰り返しの先頭に戻ります。

; CHAR 'a'
 28:  39400009   ldrb  w9, [x0]
 2c:  7101853f   cmp   w9, #0x61                 ; 'a'?
 30:  54000161   b.ne  0x5c                      ; いいえ -> フォールバックブロック
 34:  91000400   add   x0, x0, #1

; CHAR 'n'
 38:  39400009   ldrb  w9, [x0]
 3c:  7101b93f   cmp   w9, #0x6e                 ; 'n'?
 40:  540000e1   b.ne  0x5c                      ; いいえ -> フォールバックブロック
 44:  91000400   add   x0, x0, #1

; JMP
 48:  17fffff3   b     0x14                      ; ループの先頭に戻る

これでループを過ぎました。ここがバックトラックがジャンプする場所です。繰り返しを終了すると、正規表現の末尾に到達します。あとは、文字列の末尾にいるかどうかを確認するだけです。文字列の末尾にいれば、成功として1を返します。そうでない場合は、正規表現のマッチに失敗したことを意味し、フォールバックを実行するための失敗ロジックを実行する必要があります。

 4c:  39400009   ldrb  w9, [x0]
 50:  35000069   cbnz  w9, 0x5c                  ; NUL でない -> フォールバックブロック
 54:  d2800020   mov   x0, #1                    ; 成功
 58:  d65f03c0   ret

そして最後に、フォールバックロジックです。これはスタックが空かどうかをチェックします。空の場合は0を返します。空でない場合は、フォールバックアドレスとフォールバック文字列位置の両方をスタックからポップし、フォールバックアドレスにジャンプします。

 5c:  eb02003f   cmp   x1, x2                    ; 残りのフレームは?
 60:  54000060   b.eq  0x6c                      ; いいえ -> ギブアップ
 64:  a9ff0029   ldp   x9, x0, [x1, #-16]!       ; (再開、位置) をポップ
 68:  d61f0120   br    x9                        ; そこへジャンプ
 6c:  d2800000   mov   x0, #0                    ; マッチせず
 70:  d65f03c0   ret
ステンシルの構築

コンパイル済みコードを見る機会を得たので、コピー&パッチコンパイラがどのように機能するかについての感覚を得られるはずです。命令の共通セットがあり、それらの間にはわずかな違いしかありません。これらの各関数ブロックに対して、対応するコードを生成する関数を記述できます。各関数は、コードを変更するために使用する値を受け取ります。たとえば、stencil_char の引数の1つは、比較する文字になります。その文字をマシンコードに直接挿入します。

プロローグは、単なるコードブロックなので簡単です。

const PROLOGUE_WORDS: usize = 1;

fn stencil_prologue() -> [u32; PROLOGUE_WORDS] {
    [0xAA0103E2] // mov x2, x1
}

文字比較の場合、比較する文字とフォールバックロジックへのジャンプ先を挿入する必要があります。

const CHAR_WORDS: usize = 4;

fn stencil_char(byte: u8, stencil_pos: usize, fail_pos: usize) -> [u32; CHAR_WORDS] {
    [
        0x39400009,                                                 // ldrb w9, [x0]
        0x7100013F | ((byte as u32) << 10),                         // cmp  w9, #byte
        0x54000001 | cond_branch_offset(stencil_pos + 2, fail_pos), // b.ne fail
        0x91000400,                                                 // add  x0, x0, #1
    ]
}

繰り返しの場合、スタックにプッシュするループの開始と、終了へのジャンプがあります。

const SPLIT_WORDS: usize = 5;

fn stencil_split(resume_addr: u64) -> [u32; SPLIT_WORDS] {
    [
        0xD2800009 | addr_bits(resume_addr, 0), // movz x9, #addr[0..16]
        0xF2A00009 | addr_bits(resume_addr, 1), // movk x9, #addr[16..32], lsl 16
        0xF2C00009 | addr_bits(resume_addr, 2), // movk x9, #addr[32..48], lsl 32
        0xF2E00009 | addr_bits(resume_addr, 3), // movk x9, #addr[48..64], lsl 48
        0xA8810029,                             // stp  x9, x0, [x1], #16
    ]
}

const JMP_WORDS: usize = 1;

fn stencil_jmp(stencil_pos: usize, target_pos: usize) -> [u32; JMP_WORDS] {
    [0x14000000 | branch_offset(stencil_pos, target_pos)] // b target
}

そして、マッチブロックと失敗ブロックがあります。これらは非常にクリーンです。

const MATCH_WORDS: usize = 4;

fn stencil_match(stencil_pos: usize, fail_pos: usize) -> [u32; MATCH_WORDS] {
    [
        0x39400009,                                                 // ldrb w9, [x0]
        0x35000009 | cond_branch_offset(stencil_pos + 1, fail_pos), // cbnz w9, fail
        0xD2800020,                                                 // mov  x0, #1
        0xD65F03C0,                                                 // ret
    ]
}

const FAIL_WORDS: usize = 6;

fn stencil_fail() -> [u32; FAIL_WORDS] {
    [
        0xEB02003F, // cmp  x1, x2
        0x54000060, // b.eq +3 (to the mov below)
        0xA9FF0029, // ldp  x9, x0, [x1, #-16]!
        0xD61F0120, // br   x9
        0xD2800000, // mov  x0, #0
        0xD65F03C0, // ret
    ]
}

補足として、特定のデータを命令に挿入するのに役立つヘルパー関数を以下に示します。

// 条件付き分岐 (b.ne / cbnz) の分岐オフセットフィールドを計算します。
// 分岐からターゲットまでの命令数で、ビット5〜24に格納されます。
fn cond_branch_offset(branch_pos: usize, target_pos: usize) -> u32 {
    let instr_count = target_pos as i64 - branch_pos as i64; // マイナスになることもあります
    (((instr_count as u64) & 0x7FFFF) << 5) as u32
}

// 無条件分岐 (b) の分岐オフセットフィールドを計算します。
// 同じ考え方ですが、ビット0〜26に格納されます。
fn branch_offset(branch_pos: usize, target_pos: usize) -> u32 {
    let instr_count = target_pos as i64 - branch_pos as i64; // マイナスになることもあります
    ((instr_count as u64) & 0x3FF_FFFF) as u32
}

// movz/movk の即値に配置される絶対アドレスの16ビットを抽出します。
fn addr_bits(addr: u64, part: usize) -> u32 {
    (((addr >> (16 * part)) & 0xFFFF) as u32) << 5
}
コードのエミット

これで、それを駆動するコードです。

// ノードがコンパイルされる命令数を計算します。
fn node_words(node: &Node) -> usize {
    match node {
        Node::Literal(text) => text.len() * CHAR_WORDS,
        Node::Concatenation(left, right) => node_words(left) + node_words(right),
        Node::Repetition(body) => SPLIT_WORDS + node_words(body) + JMP_WORDS,
    }
}

struct Emitter {
    code: Vec<u32>,
    fail: usize, // 共有失敗ブロックのワードオフセット
    base: u64,   // コード[0]の実行時アドレス、絶対アドレスの穴埋め用
}

impl Emitter {
    // 次の命令が配置されるオフセットを返します。
    fn pos(&self) -> usize {
        self.code.len()
    }

    // 記入済みのステンシルをコードバッファに追加します。
    fn emit(&mut self, stencil: &[u32]) {
        self.code.extend_from_slice(stencil);
    }

    // 1つのノードのコードをエミットし、子ノードに再帰します。
    fn emit_node(&mut self, node: &Node) {
        match node {
            Node::Literal(text) => {
                for &byte in text.as_bytes() {
                    self.emit(&stencil_char(byte, self.pos(), self.fail));
                }
            }
            Node::Concatenation(left, right) => {
                self.emit_node(left);
                self.emit_node(right);
            }
            Node::Repetition(body) => {
                let split_at = self.pos();
                let exit = split_at + SPLIT_WORDS + node_words(body) + JMP_WORDS;
                self.emit(&stencil_split(self.base + exit as u64 * 4));
                self.emit_node(body);
                self.emit(&stencil_jmp(self.pos(), split_at));
            }
        }
    }
}

// 完全なプログラムを生成します:プロローグ、コンパイル済みAST、MATCH、失敗ブロック。
fn generate_code(regex: &Node, base: u64) -> Vec<u32> {
    let nwords = PROLOGUE_WORDS + node_words(regex) + MATCH_WORDS + FAIL_WORDS;
    let mut emitter = Emitter {
        code: Vec::with_capacity(nwords),
        fail: nwords - FAIL_WORDS,
        base,
    };
    emitter.emit(&stencil_prologue());
    emitter.emit_node(regex);
    let match_at = emitter.pos();
    emitter.emit(&stencil_match(match_at, emitter.fail));
    emitter.emit(&stencil_fail());
    assert_eq!(emitter.pos(), nwords);
    emitter.code
}

そして、これが難しい部分です!個人的には、アセンブリを書くのがAIが最も役立つ分野だと感じています。アセンブリに関する私の主な経験は、microcorruption CTFを完了することです。自分でアセンブリを書いたことはありません。必要な正確な命令と、目的の出力を得るためにそれらをどのように変更するかを理解するのに非常に苦労するでしょう。AIを使えば、JITコンパイラがどのように機能してほしいかという一般的な形状をコーディングエージェントに与えることができ、それがあまりにも多くの詳細を処理してくれます。

機械コードのロード

コンパイラを完成させるには、実際にコードをロードする必要があります。これを行うために、読み取り可能、書き込み可能、および実行可能なメモリブロックを割り当てるために mmap を使用します。次に、コードをそのメモリにコピーし、そのメモリブロックを関数に変換して呼び出します。

const BSTACK_MAX: usize = 4096;

// これらの関数は mac システムライブラリに含まれています
unsafe extern "C" {
    fn pthread_jit_write_protect_np(enabled: libc::c_int);
    fn sys_icache_invalidate(start: *mut libc::c_void, len: libc::size_t);
}

type MatchFn = unsafe extern "C" fn(input: *const u8, bstack: *mut u64) -> u64;

struct Jit {
    buf: *mut u32,
    nbytes: usize,
    bstack: Vec<u64>,
}

impl Jit {
    fn compile(regex: &Node) -> Jit {
        let nwords = PROLOGUE_WORDS + node_words(regex) + MATCH_WORDS + FAIL_WORDS;
        let nbytes = nwords * 4;

        unsafe {
            let buf = libc::mmap(
                std::ptr::null_mut(),
                nbytes,
                libc::PROT_READ | libc::PROT_WRITE | libc::PROT_EXEC,
                libc::MAP_PRIVATE | libc::MAP_ANON | libc::MAP_JIT,
                -1,
                0,
            ) as *mut u32;
            assert!(buf as *mut libc::c_void != libc::MAP_FAILED, "mmap failed");

            let code = generate_code(regex, buf as u64);

            pthread_jit_write_protect_np(0); // リージョンを書き込み可能にする (Apple W^X)
            std::slice::from_raw_parts_mut(buf, code.len()).copy_from_slice(&code);
            pthread_jit_write_protect_np(1); // 実行可能に戻す
            sys_icache_invalidate(buf as *mut libc::c_void, nbytes);

            Jit { buf, nbytes, bstack: vec![0; BSTACK_MAX * 2] }
        }
    }

    // 生成されたコードを実行します。入力は NUL バイトで終わる必要があります。
    fn is_match(&mut self, nul_terminated: &[u8]) -> bool {
        debug_assert_eq!(nul_terminated.last(), Some(&0));
        unsafe {
            let matcher: MatchFn = std::mem::transmute(self.buf);
            matcher(nul_terminated.as_ptr(), self.bstack.as_mut_ptr()) != 0
        }
    }
}

impl Drop for Jit {
    fn drop(&mut self) {
        unsafe {
            libc::munmap(self.buf as *mut libc::c_void, self.nbytes);
        }
    }
}

結果

これらすべてが完了したので、構築したさまざまな実装のパフォーマンスを比較してみましょう。

入力長インタプリタJIT手書きJIT スピードアップ手書きスピードアップ
945 ns3.8 ns3.8 ns11.7x11.9x
33103 ns7.9 ns10.5 ns13.0x9.8x
129597 ns30 ns32 ns19.7x18.6x
5131,955 ns126 ns120 ns15.5x16.2x
2,0498,301 ns470 ns393 ns17.7x21.1x

JITと手書きの実装はほぼ互角です。JITバージョンの方が速い場合もあれば、手書きバージョンの方が速い場合もあります。


「コードは決して難しい部分ではなかった」というミームが広まっています。これはいくつかのドメインでは真実ですが、他のドメインでは、コードを書くことが間違いなく難しい部分でした。JITコンパイラはその良い例です。多くのソフトウェアでは、JITコンパイラがコードの高速化に大いに役立つでしょう。JITコンパイラの希少性は、JITコンパイラの実装が歴史的に価値があるには難しすぎたことを示唆しています。LLMは参入障壁を下げ、JITコンパイラを書くことをはるかに容易にしました。これがpgrustの根底にある考え方です。データベースは歴史的に構築が最も難しいソフトウェアであり、そのために制限されていました。今では、AIを使って、構築するソフトウェアの種類についてより野心的になることができます。

読んでいただきありがとうございます。プロジェクトをサポートしたい場合は、pgrustをサポートする最良の方法は、GitHubでスターを付けることです。フォローしたい場合は、次のとおりです。

JITコンパイルのフォローアップを含む、pgrustの週次アップデート。

X: MalisJasonpgrust