HN 日本語サマリー

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

Dense Arena Interning: コンパイラパフォーマンスの原動力

Dense Arena Interning: The Engine of Compiler Performance (aikoschurmann.com)

8 pointsby g0xA52A2A2 コメント

要約

コンパイラは、ソースコード中の変数名やキーワードなどの文字列処理に多くの時間を費やします。この問題を解決するため、Dense Arena Interningという手法が提案されています。この手法では、文字列をコンパイルの初期段階で一意な整数に変換し、以降の処理ではO(1)の配列インデックス参照やポインタ比較で済ませることで、コンパイラのパフォーマンスを劇的に向上させます。

全文翻訳

Dense Arena Interning: コンパイラパフォーマンスの原動力

コンパイラは、名前や構造体の処理に膨大な時間を費やします。ソースコード中のすべての変数、関数、キーワードは文字列であり、コンパイラの複数のフェーズで識別、分類、解決される必要があります。

問題は、単に文字列を照合したり、型シグネチャを比較したりすることだけではありません。それは、パイプライン全体で繰り返し繰り返し行われることです。同じ変数名 counter は、レクサー、パーサー、型チェッカー、最適化パスなど、数百回チェックされる可能性があります。

私は、文字列や構造体を生成された瞬間に密な整数に変換することで、この問題を解決するためにDense Arena Internerを実装しました。ハッシュ計算のコストは、レキシングまたは型構築中に前もって支払われます。その見返りとして、コンパイラの後続の各フェーズは、O(1) の配列インデックス参照と単一命令のポインタ比較に完全に依存できるようになります。

ここでは、繰り返しの多い高コストな構造チェックから、ハードウェアレベルの整数比較への技術的な道のりをたどります。

明示的なメモリ制御とLLVMバックエンドを備えた、静的型付けのプロシージャル言語のコンパイラ。

CLLVMCOMPILERS

線形ボトルの首: O(N*L)

レクサーがコードをスキャンしていると想像してください。文字 f-u-n-c を見つけました。レクサーは、「これは func や return のようなキーワードか、それとも変数名か?」を知る必要があります。

ナイーブなアプローチは、既知のキーワードのリストに対して strcmp を使用した線形スキャンです。

// Naive Lexer logic
const char* keywords[] = { "fn", "if", "else", "while", "return", ... };

for (int i = 0; i < num_keywords; i++) {
    if (strcmp(token_string, keywords[i]) == 0) {
        return keyword_tokens[i];
    }
}
  • strcmp(s1, s2) は、文字列長を L とすると O(L) です。不一致が見つかるまで、すべての文字をチェックする必要があります。
  • 線形スキャンは、キーワード数を N とすると O(N) です。
  • 総コスト: トークンあたり O(N * L)。

言語に50個のキーワードがあり、平均識別子が8文字の場合、単一の単語を識別するためだけに約400文字の比較を行っていることになります。大規模なプロジェクトでは、このオーバーヘッドはパフォーマンスの巨大な足かせとなります。

ハッシュによる改善: O(L)

これを改善するために、ハッシュマップに移行します。すべてのキーワードをチェックする代わりに、トークンのハッシュを計算し、直接候補の照合先にジャンプします。バケットには、動的配列を使用したチェイン法を使用します。これにより、衝突が発生した場合でもパフォーマンスは安定します。ハッシュ計算は、ルックアップあたり O(L) です(平均ケースでは O(1) のバケットアクセス)。

// hash_map.c - Simplified insertion
bool hashmap_put(HashMap* map, void* key, void* value) {
    // 1. Automatic Resizing (Load Factor > 0.75)
    if (map->size >= (map->bucket_count * 3) / 4) {
        hashmap_rehash(map, map->bucket_count * 2);
    }

    // 2. O(L) Hashing: We must visit every byte to compute the hash.
    size_t index = hash_func(key) % map->bucket_count;
    DynArray *bucket = &map->buckets[index];

    // 3. O(1) average lookup in bucket chain
    for (size_t i = 0; i < bucket->count; i++) {
        KeyValue *kv = dynarray_get(bucket, i);
        if (cmp_func(kv->key, key) == 0) {
            kv->value = value; // Update existing
            return true;
        }
    }
    
    // 4. Push new entry
    return dynarray_push(bucket, (KeyValue){key, value});
}

O(L) は O(N * L) よりはるかに優れていますが、パーサー、型チェッカー、オプティマイザーでその文字列に遭遇するたびにハッシュ計算のコストを支払っています。このコストをすべてのステージからレクサーの1つのステージにシフトする方法が必要です。

後続のパス全体でシンボルが k 回再利用される場合、トレードオフは単純です。インターニングなしでは、繰り返しのチェックは O(k * L) です。インターニングを使用すると、O(k * L) のコストは1つのフェーズでのみ発生し、後続のパスは O(k) になります。

インターニングはコストを1つのフェーズにシフトし、その後、ほぼ定数時間比較のために正規のハンドルを再利用します。

基盤: 安定したメモリ (アリーナ)

文字列比較を完全に排除するには、同一の文字列がまったく同じメモリ位置を指すようにする必要があります。標準の malloc や realloc は、メモリを移動させたり散乱させたりする可能性があり、ポインタ比較を危険にします。

私はアリーナアロケーターを使用しています。これは、大きな連続ブロックでメモリを管理し、O(1) 割り当てとポインタの安定性という2つの重要な保証を提供します。

typedef struct ArenaBlock {
    struct ArenaBlock *next; // Pointer to the next block in the chain
    size_t capacity;         // Total size of this block's data
    size_t used;             // Number of bytes currently allocated
    uint8_t data[];          // The actual memory
} ArenaBlock;

typedef struct {
    ArenaBlock *blocks;      // Head of the block list
    size_t block_size;       // Default size for new blocks
} Arena;

アリーナでの割り当ては、単にポインタを前方に「バンプ」させるだけです。文字列がアリーナブロックに格納されると、そのアドレスは決して変更されません。この安定性により、ポインタ自体をユニークなIDとして使用できます。

void *arena_alloc(Arena *arena, size_t size) {
    if (!arena) return NULL;
    if (size == 0) return NULL; /* semantic choice */

    const size_t align = alignof(max_align_t);

    ArenaBlock *block = arena->blocks;
    if (!block) return NULL;

    /* align the *offset*, not just the size */
    size_t offset = align_up(block->used, align);

    /* If not enough room in current block, allocate a new one */
    if (offset + size > block->capacity) {
        size_t new_capacity = arena->block_size;
        while (new_capacity < size) new_capacity *= 2;

        ArenaBlock *new_block = malloc(sizeof(ArenaBlock) + new_capacity);
        if (!new_block) return NULL;

        new_block->next = arena->blocks;
        new_block->capacity = new_capacity;
        new_block->used = 0;
        arena->blocks = new_block;

        block = new_block;
        offset = 0;
    }

    void *ptr = (void*)(block->data + offset);
    block->used = offset + align_up(size, align); /* bump after alignment */
    return ptr;
}

ただし、注意点があります。それはアリーナの「解放不能」な性質です。アリーナアロケーターはバッチコンパイラに最適です。なぜなら、通常はコンパイル終了時にメモリブロック全体を破棄するだけだからです。しかし、このコンパイラが長期間実行されるLanguage Server Protocol (LSP) デーモンとして適応される場合、アリーナはファイル変更時に個々のインターンされた文字列を解放できないため、メモリが膨張する可能性があります。

コア抽象化: Slice と InternResult

インターナー自体を見る前に、データをやり取りするために使用される2つのコアデータ構造を定義する必要があります。

Slice: 文字列またはオブジェクトへの軽量な参照です。メモリを所有せず、開始位置と長さを指すだけです。これにより、レクサーはコピーなしでソースファイルバッファを直接指すことができます。

typedef struct {
    const char *ptr;
    size_t len;
} Slice;

InternResult: これはインターナーから返される正規のハンドルです。key はアリーナで割り当てられた Slice* を指し、そのスライスは正規のバイトシーケンスを指します。レキシング中に多くのテンポラリスライスを作成する可能性がありますが、2つのスライスが同じバイトと長さを共有する場合、それらは同じインターンされたレコードに解決されます。Entry は密なIDとオプションのメタデータ(例: トークンタイプ)を格納します。

typedef struct {
    void *key;      // Arena-allocated Slice* (points to canonical bytes)
    Entry *entry;   // Metadata (Dense ID and metadata)
} InternResult;

Dense Arena Interner: O(1) ルックアップの購入

インターニングは、文字列識別子であれ、複雑な型構造体であれ、データを重複排除し、単一の「正規」コピーのみが存在するようにします。この実装のDenseという部分は、オブジェクトを識別する方法を指します。単にポインタを使用するのではなく、一意の各アイテムに連続したゼロから始まる整数(0、1、2…)を割り当てます。

DenseArenaInterner は、ハッシュマップを使用して既存のエントリを見つけ、アリーナを使用して新しいエントリを格納します。

typedef struct {
    Arena *arena;           // Where canonical data lives
    HashMap *hashmap;       // Maps raw data -> InternResult*
    int dense_index_count;  // Counter for the Dense ID (0, 1, 2...)
} DenseArenaInterner;

アイテムをインターンする際、ハッシュマップをチェックします。すでに存在する場合は、既存の InternResult を返します。存在しない場合は、アリーナに一度だけコピーし、dense_index_count をインクリメントします。これにより、500個のユニークなオブジェクトを見た場合、それらは0から499までの整数にマッピングされることが保証されます。

// dense_arena_interner.c - Simplified interning loop
InternResult* intern(DenseArenaInterner *interner, Slice *slice, void *meta) {
    // 1. O(L) Hash + O(1) Map Lookup
    InternResult *found = hashmap_get(
        interner->hashmap,
        slice,
        interner->hash_func,
        interner->cmp_func
    );
    if (found) return found;

    // 2. Create stable, arena-owned key and canonical bytes
    Slice *key_slice = arena_alloc(interner->arena, sizeof(Slice));
    void *canonical_data = interner->copy_func(interner->arena, slice->ptr, slice->len);
    key_slice->ptr = canonical_data;
    key_slice->len = slice->len;

    // 3. Assign the next Dense ID
    InternResult *res = arena_alloc(interner->arena, sizeof(InternResult));
    Entry *ent = arena_alloc(interner->arena, sizeof(Entry));
    ent->meta = meta;
    ent->dense_index = interner->dense_index_count;
    res->key = key_slice;
    res->entry = ent;

    // 4. Update the map for future O(1) lookups
    hashmap_put(
        interner->hashmap,
        key_slice,
        res,
        interner->hash_func,
        interner->cmp_func
    );

    interner->dense_index_count++;
    return res;
}

レキサー統合: メモリの勝利

レクサーは、キーワード用と識別子用の2つの別々インターナーを維持します。

起動: キーワードのブートストラップ。 コンパイラが起動すると、キーワードテーブルを事前に入力します。これにより、コードを1行もスキャンする前に、すべてのキーワードがすでに「正規」化され、ハッシュマップ内に存在することが保証されます。

// lexer.c - Initialization logic
static const struct { const char *word; TokenType type; } KEYWORDS[] = {
    {"fn", TOK_FN}, {"if", TOK_IF}, {"return", TOK_RETURN}, ...
};

for (size_t i = 0; KEYWORDS[i].word; i++) {
    Slice s = { .ptr = KEYWORDS[i].word, .len = strlen(KEYWORDS[i].word) };
    // Store the TokenType as metadata directly in the Entry
    intern(lexer->keywords, &s, (void*)(uintptr_t)KEYWORDS[i].type);
}

実行時: O(L) チェック。 レクサーが単語をスキャンすると、intern_peek を使用します。これは、新しいメモリを割り当てることなくキーワードマップをチェックする関数です。

// lexer.c - Identifier scanning
static void *lexer_lex_identifier(Lexer *lexer, ...) {
    Slice slice = lexer_make_slice_from_ptrs(start, end);

    // 1. Keyword check (O(L) hashing + O(1) pointer lookup)
    InternResult *kw = intern_peek(lexer->keywords, &slice);
    if (kw) {
        // It's a keyword! Pull the TokenType from the metadata.
        *out_type = (TokenType)(uintptr_t)kw->entry->meta;
        return kw; 
    }

    // 2. Not a keyword? Intern it into the general identifier table.
    *out_type = TOK_IDENTIFIER;
    return intern(lexer->identifiers, &slice, NULL);
}

レクサーで何が得られたか? 決定的に、速度は向上しませんでした。標準のハッシュマップとインターナーの両方で、レクサーにとって O(L) の操作です。ここでの勝利は二重です。

  1. メモリの重複排除: return が500回出現する場合、500回ではなく1回だけ格納します。
  2. 密なインデックス生成: 各識別子に連続した密なIDを割り当てることにより、コンパイラの後のフェーズ、特にスコープと型チェックシステムが、これらのIDを使用して O(1) のフラット配列ルックアップを行えるようになります。

レクサーはこれらのIDを生成するために O(L) の「通行料」を支払いますが、パフォーマンスの恩恵を受けるのはコンパイラの残りの部分です。

ハッシュを超えて: 密なIDの力

1. フラット配列シンボルテーブル。 これが最も重要な利点です。従来のコンパイラでは、シンボルテーブルはしばしば複雑なハッシュマップです。密なIDを使用すると、シンボルテーブルはフラット配列になります。

すべての変数名が0から N までのIDを持つことが保証されているため、そのIDを配列への直接インデックスとして使用できます。これにより、シンボル解決は単一のメモリオフセット計算、つまりデータをアクセスする最も高速な方法、すなわち O(1) になります。

変数シャドーイングの処理。 複雑な点の1つは、レキシカルスコープです。グローバルスコープで宣言された変数 index が、ネストされた関数の index パラメータによってシャドーイングされる場合、両方の文字列はまったく同じ密なIDに解決されます。これを解決するために、それぞれが独自のスパース配列を持つスコープの階層を維持します。

// Each scope has its own symbols array, indexed by the global Dense ID
Symbol *scope_lookup_symbol(Scope *scope, InternResult *rec) {
    Scope *current = scope;
    while (current) {
        // Direct O(1) index check per scope level
        if (rec->entry->dense_index < current->capacity) {
            Symbol *symbol = current->symbols[rec->entry->dense_index];
            if (symbol) return symbol; // Found the most local version
        }
        current = current->parent;
    }
    return NULL;
}

この階層構造は完全に機能しますが、他の高性能コンパイラでは、スタックの配列(各密なIDがシンボルのスタックにマッピングされる)やアンドゥログ(グローバル配列にプッシュし、スコープ終了時にロールバックする)を使用することがあります。これらはまだ実装していませんが、スコープウォークをグローバル構造のトップにある最もローカルなシンボルを保持するという点で、ツリーウォークの興味深い代替手段を提供します。スコープウォーク自体は、ネストの深さに比例します: O(h)。

2. メモリ効率とキャッシュローカリティ。 IDは連続しているため、メタデータをコンパクトでキャッシュフレンドリーな構造に格納できます。コンパイラがすべてのシンボルを反復処理する場合、連続したメモリブロックに対する線形スキャンを実行します。これにより、CPUキャッシュヒットが最大化され、ハッシュマップのようなスパースデータ構造に関連するメモリオーバーヘッドが最小限に抑えられます。

3. 即時の型およびシンボル比較。 インターニングは文字列だけを対象とするものではありません。これは構造の正規化戦略です。(「i32へのポインタ」や「boolを返す関数」のような)複雑な型をインターンすると、プログラム全体で同一の型がすべて同じメモリ位置を指すことが保証されます。

これにより、再帰的なショートカットが作成されます。新しい複雑な型をインターンするプロセスさえも高速です。なぜなら、その構成要素(戻り値の型、パラメータ、基底型)はすでにインターンされているからです。深い再帰的な構造チェックの代わりに、「浅い」比較でコンポーネントポインタを比較するだけで済みます。

// Interning a complex function type is just a shallow pointer check
// because 'ret' and 'params' are already canonical pointers.
bool type_compare(Type *a, Type *b) {
    if (a->kind != b->kind) return false;
    if (a->ret != b->ret) return false; // Simple pointer comparison
    if (a->param_count != b->param_count) return false;
    
    // Check if the parameter pointer arrays match
    return memcmp(a->params, b->params, a->param_count * sizeof(Type*)) == 0;
}

各「子」型がすでに正規化されていることを保証することにより、インターナーは1レベルより深く歩くことなく、「親」型が存在するかどうかを判断できます。型がインターンされると、コンパイラの残りの部分は複雑なシグネチャを単純な整数であるかのように比較できます。正規化後、等価性チェックは定数時間操作のように動作します: O(1)。

// The ultimate win: O(1) equality everywhere else
if (type_a == type_b) {
    // Verified identical signatures in a single CPU instruction
}

結果: 無料の解決

レキシングと型構築中にハッシュ計算のコストを前もって支払うことにより、すべての識別子と複雑な構造がユニークなポインタと密なIDに変換されます。

それ以降、パーサー、型チェッカー、オプティマイザーは strcmp や深い再帰的な構造チェックを二度と使用しません。Dense arena interning は、コンパイラを遅いテキストおよびツリープロセッサから、軽量な整数処理マシンへと変革します。この最適化により、フロントエンドパイプライン全体が事実上瞬時に感じられるようになります。