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

コンパイラは、名前や構造体の処理に膨大な時間を費やします。ソースコード中のすべての変数、関数、キーワードは文字列であり、コンパイラの複数のフェーズにわたって識別、分類、解決される必要があります。問題は単に文字列を照合したり、型シグネチャを比較したりすることだけではありません。パイプライン全体でそれを何度も繰り返すことです。同じ変数名 "counter" が、最初はレクサーで、次にパーサーで、型チェッカーで繰り返し、最適化パス全体で何度もチェックされる可能性があります。私は、文字列や構造体を生成された瞬間に密な整数に変換する Dense Arena Interner を実装して、この問題を解決しました。ハッシュのコストは、レキシングまたは型構築中に事前に支払われます。その見返りとして、コンパイラの各後続フェーズは、O(1) の配列インデックス参照と単一命令のポインタ比較に完全に依存できるようになります。ここでは、繰り返し行われる高コストな構造チェックから、ハードウェアレベルの整数比較への技術的な道のりを見ていきます。 C3 compiler-v3 明示的なメモリ制御と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) よりもはるかに優れていますが、パーサー、型チェッカー、オプティマイザーでその文字列に遭遇するたびにハッシュのコストを支払っています。このコストをすべてのステージからレクサーだけにシフトする方法が必要です。後続パス全体で 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; } ただし、注意点があります。アリーナの「解放不能」な性質です。アリーナアロケータはバッチコンパイラに最適です。通常、コンパイル終了時にメモリブロック全体を破棄するだけだからです。しかし、このコンパイラが長期間実行される言語サーバープロトコル (LSP) デーモンとして適応される場合、アリーナは個々のインターン化された文字列をファイル変更時に解放できないため、メモリが膨張する可能性があります。 コア抽象化: スライスとインターン結果 インターナー自体を見る前に、データをやり取りするために使用される 2 つのコアデータ構造を定義する必要があります。 スライス: 文字列またはオブジェクトへの軽量な参照です。メモリを所有せず、開始位置と長さを指すだけです。これにより、レクサーはコピーせずにソースファイルバッファを直接指すことができます。 typedef struct { const char *ptr; size_t len; } Slice; インターン結果: これはインターナーから返される正規のハンドルです。key はアリーナに割り当てられたスライスを指し、そのスライスは正規のバイトシーケンスを指します。レキシング中に多くのテンポラリスライスを作成する可能性がありますが、2 つのスライスが同じバイトと長さを持つ場合、それらは同じインターン化されたレコードに解決されます。Entry は Dense 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 を返します。存在しない場合は、アリーナに 1 回だけコピーし、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( int