Dense Arena Interner：编译器性能的引擎

# 密集区域驻留：编译器性能的引擎 | 系统笔记 来源：https://aikoschurmann.com/blog/string-interning-compilers 编译器花费大量时间处理名称和结构。源代码中的每个变量、函数和关键字都是一个需要跨多个编译阶段进行识别、分类和解析的字符串。问题不仅在于匹配字符串或比较类型签名，而在于在整个流水线中**反复**进行这些操作。同一个变量名`counter`可能会被检查数百次：最初在词法分析器中，再次在解析器中，在类型检查器中重复，以及在整个优化遍中。 我实现了一个**密集区域驻留器（Dense Arena Interner）**，通过在创建字符串和结构的同时将其转换为密集整数来解决这一问题。我们在词法分析或类型构建期间预先支付哈希成本。作为交换，编译器的每个后续阶段都可以完全依赖于**O(1)**的数组索引和单指令指针比较。下文是技术历程，从重复、昂贵的结构检查到硬件级别的整数比较。 本文为一个具有显式内存控制的静态类型过程语言编译器，后端基于LLVM。 ## 线性瓶颈：O(N*L) 想象词法分析器扫描你的代码。它找到字符`f-u-n-c`。需要知道：“这是像`func`或`return`这样的关键字，还是变量名？”朴素的做法是使用`strcmp`对已知关键字列表进行线性扫描： ```c // 朴素的词法分析器逻辑 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)** 是 **O(L)**，其中L是字符串长度。它必须检查每个字符直到发现不匹配。 - **线性扫描**是 **O(N)**，其中N是关键字的数量。 - **总成本：** 每个token **O(N * L)**。如果你的语言有50个关键字，平均标识符长度为8个字符，那么仅识别一个单词就需要大约400次字符比较。在大型项目中，这种开销会成为性能的巨大负担。 ## 哈希改进：O(L) 为了改进，我们转向哈希映射（Hash Map）。我们不检查每个关键字，而是计算token的哈希值并直接跳转到潜在匹配位置。我使用带有动态数组的分离链接法来处理桶。这确保了即使在冲突发生时，性能也保持稳定。哈希查找消耗 **O(L)**（平均情况**O(1)**桶访问）。 ```c // hash_map.c - 简化版插入 bool hashmap_put(HashMap* map, void* key, void* value) { // 1. 自动扩容（负载因子 > 0.75） if (map->size >= (map->bucket_count * 3) / 4) { hashmap_rehash(map, map->bucket_count * 2); } // 2. O(L) 哈希：必须访问每个字节来计算哈希值。 size_t index = hash_func(key) % map->bucket_count; DynArray *bucket = &map->buckets[index]; // 3. 桶链中的 O(1) 平均查找 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; // 更新已有项 return true; } } // 4. 推入新条目 return dynarray_push(bucket, (KeyValue){key, value}); } ``` 虽然O(L)比O(N*L)好得多，但我们**每次**在解析器、类型检查器或优化器中遇到那个字符串时，仍然需要支付哈希成本。我们需要将这种成本从所有阶段转移到仅词法分析器阶段。对于一个在后续阶段中被重用次的符号，权衡很简单：没有驻留时，重复检查的成本是**O(k * L)**；有了驻留，你在一个阶段内只支付**O(L)**，后续阶段变为**O(k)**。驻留将成本转移到一个阶段，然后重用规范的句柄进行近乎常数时间的比较。 ## 基础：稳定内存（区域） 为了完全消除字符串比较，我们需要确保相同的字符串指向**完全相同的内存地址**。标准的`malloc`或`realloc`可能会移动数据或将其分散，使得指针比较变得不可靠。我使用**区域分配器（Arena Allocator）**，它在大的连续块中管理内存，提供两个关键保证：**O(1)分配**和**指针稳定性**。 ```c typedef struct ArenaBlock { struct ArenaBlock *next; // 指向链表中的下一个块 size_t capacity; // 此块数据的整体大小 size_t used; // 当前已分配的字节数 uint8_t data[]; // 实际内存 } ArenaBlock; typedef struct { ArenaBlock *blocks; // 块列表的头部 size_t block_size; // 新块的默认大小 } Arena; ``` 区域中的分配只是“前移”指针。一旦字符串存储在区域块中，它的地址**永远不会改变**。这种稳定性允许我们将指针本身用作唯一ID。 ```c void *arena_alloc(Arena *arena, size_t size) { if (!arena) return NULL; if (size == 0) return NULL; /* 语义选择 */ const size_t align = alignof(max_align_t); ArenaBlock *block = arena->blocks; if (!block) return NULL; /* 对齐偏移量，而非仅仅对齐大小 */ size_t offset = align_up(block->used, align); /* 如果当前块空间不足，分配新块 */ 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); /* 对齐后前移 */ return ptr; } ``` 然而，有一个陷阱：**区域的“不可释放”性质**。区域分配器非常适合批处理编译器，因为通常在编译结束时直接丢弃整个内存块。但如果这个编译器被改编成长运行的**语言服务器协议（LSP）**守护进程，内存可能会膨胀，因为区域无法在文件更改时单独释放驻留的字符串。 ## 核心抽象：Slice 和 InternResult 在查看驻留器本身之前，我们需要定义两个用于传递数据的核心数据结构。 **Slice:** 对字符串或对象的轻量引用。它不拥有自己的内存，只指向起始位置和长度。这允许词法分析器直接指向源文件缓冲区，而不需要复制。 ```c typedef struct { const char *ptr; size_t len; } Slice; ``` **InternResult:** 这是驻留器返回的规范句柄。`key`指向区域分配的`Slice`，而该slice指向规范的字节序列。你可能会在词法分析过程中创建许多临时slice，但如果两个slice具有相同的字节和长度，它们解析到相同的驻留记录。`Entry`存储密集ID和可选元数据（例如，token类型）。 ```c typedef struct { void *key; // 区域分配的 Slice*（指向规范字节） Entry *entry; // 元数据（密集ID和元数据） } InternResult; ``` ## 密集区域驻留器：购买 O(1) 查找 驻留对数据进行去重——无论是字符串标识符还是复杂的类型结构——使得只有一份“规范”副本存在。这个实现的**密集**部分指的是我们如何识别这些对象。除了使用指针，我们还为每个唯一项分配一个连续的、从零开始的整数（0, 1, 2...）。 `DenseArenaInterner`使用哈希映射来查找已有条目，并使用区域来存储新条目。 ```c typedef struct { Arena *arena; // 规范数据所在区域 HashMap *hashmap; // 将原始数据映射到 InternResult* int dense_index_count; // 密集ID的计数器（0, 1, 2...） } DenseArenaInterner; ``` 当驻留一个项时，我们检查哈希映射。如果已存在，则返回已有的`InternResult`。如果不存在，我们将其正好复制到区域一次，并增加`dense_index_count`。这确保如果我们看到了500个唯一对象，它们映射为整数0到499。 ```c // dense_arena_interner.c - 简化的驻留循环 InternResult* intern(DenseArenaInterner *interner, Slice *slice, void *meta) { // 1. O(L) 哈希 + O(1) 映射查找 InternResult *found = hashmap_get( interner->hashmap, slice, interner->hash_func, interner->cmp_func ); if (found) return found; // 2. 创建稳定的、区域拥有的键和规范字节 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. 分配下一个密集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. 更新映射，以便未来 O(1) 查找 hashmap_put( interner->hashmap, key_slice, res, interner->hash_func, interner->cmp_func ); interner->dense_index_count++; return res; } ``` ## 词法分析器集成：内存带来的好处 词法分析器维护两个独立的驻留器：一个用于**关键字**，一个用于**标识符**。 **启动：引导关键字。** 当编译器启动时，我们预先填充关键字表。这确保每个关键字在扫描一行代码之前就已经是“规范”的，并且位于哈希映射中。 ```c // lexer.c - 初始化逻辑 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) }; // 将TokenType作为元数据直接存储在Entry中 intern(lexer->keywords, &s, (void*)(uintptr_t)KEYWORDS[i].type); } ``` **运行时：O(L) 检查。** 现在，当词法分析器扫描一个单词时，它使用`intern_peek`——一个检查关键字映射而不分配新内存的函数。 ```c // lexer.c - 标识符扫描 static void *lexer_lex_identifier(Lexer *lexer, ...) { Slice slice = lexer_make_slice_from_ptrs(start, end); // 1. 关键字检查（O(L) 哈希 + O(1) 指针查找） InternResult *kw = intern_peek(lexer->keywords, &slice); if (kw) { // 是关键字！从元数据中提取TokenType。 *out_type = (TokenType)(uintptr_t)kw->entry->meta; return kw; } // 2. 不是关键字？将其驻留在通用标识符表中。 *out_type = TOK_IDENTIFIER; return intern(lexer->identifiers, &slice, NULL); } ``` **我们在词法分析器中获得了什么？** 关键地，**我们并没有获得速度提升**。对于词法分析器，标准哈希映射和驻留器都是**O(L)**操作。这里的收获有两个： 1. **内存去重：** 如果`return`出现500次，我们只存储一次，而不是500次。 2. **密集索引生成：** 通过为每个标识符分配一个连续的**密集ID**，我们使后续的编译器阶段——特别是**作用域**和**类型检查**系统——能够使用这些ID进行**O(1)**的扁平数组查找。词法分析器支付**O(L)**的“通行费”来生成这些ID，但编译器其余部分从中获得性能收益。 ## 超越哈希：密集ID的威力 **1. 扁平数组符号表。** 这是最显著的好处。在传统编译器中，符号表常常是另一个复杂的哈希映射。有了密集ID，符号表变成了一个**扁平数组**。由于每个变量名都保证有一个介于0到N之间的ID，我们可以将该ID用作数组的直接索引。这使符号解析变成一个单一的内存偏移计算——访问数据的最快可能方式，即**O(1)**。 **处理变量遮蔽。** 一个复杂性来自词法作用域。如果变量`index`在全局作用域中声明，然后在嵌套函数中被`index`参数遮蔽，两个字符串解析为相同的密集ID。我们通过维护一个作用域层次结构来解决这个问题，每个作用域都有自己的稀疏数组。 ```c // 每个作用域都有自己的symbols数组，由全局密集ID索引 Symbol *scope_lookup_symbol(Scope *scope, InternResult *rec) { Scope *current = scope; while (current) { // 每层作用域的 O(1) 索引检查 if (rec->entry->dense_index < current->capacity) { Symbol *symbol = current->symbols[rec->entry->dense_index]; if (symbol) return symbol; // 找到最局部的版本 } current = current->parent; } return NULL; } ``` 虽然这个层次结构工作得很好，但其他高性能编译器有时会使用**栈数组**（每个密集ID映射到一个符号栈）或**撤销日志**（压入全局数组并在离开作用域时回滚）。我还没有实现这些，但它们提供了一种树遍历的替代方案，通过将最局部的符号保持在全局结构的顶部。作用域遍历本身与嵌套深度成比例：**O(h)**。 **2. 内存效率和缓存局部性。** 由于ID是连续的，我们可以将元数据存储在紧凑、缓存友好的结构中。当编译器迭代所有符号时，它是在连续内存块上进行线性扫描。这最大化CPU缓存命中，并将与哈希映射等稀疏数据结构相关的内存开销降到最低。 **3. 及时的类型和符号比较。** 驻留不仅仅用于字符串；它也是一种**结构化规范化**的策略。当我们驻留复杂类型（如“指向i32的指针”或“返回bool的函数”）时，我们确保整个程序中每个相同的类型都指向完全相同的内存地址。这创建了一个**递归快捷方式**。即使驻留新的复杂类型也是快速的，因为它的组成部分（返回类型、参数、基类型）已经驻留。不需要进行深度的递归结构检查，我们只需要对组件指针进行“浅层”比较。 ```c // 驻留一个复杂函数类型只是一个浅层指针检查 // 因为'ret'和'params'已经是规范指针。 bool type_compare(Type *a, Type *b) { if (a->kind != b->kind) return false; if (a->ret != b->ret) return false; // 简单的指针比较 if (a->param_count != b->param_count) return false; // 检查参数指针数组是否匹配 return memcmp(a->params, b->params, a->param_count * sizeof(Type*)) == 0; } ``` 通过确保每个“子”类型已经是规范的，驻留器可以确定“父”类型是否存在，而无需遍历超过一层深度。一旦类型被驻留，编译器的其余部分可以将复杂签名当作简单整数进行比较。规范化之后，相等性检查表现为常数时间操作：**O(1)**。 ```c // 终极胜利：其他地方 O(1) 相等性 if (type_a == type_b) { // 在单个CPU指令中验证相同的签名 } ``` ## 结果：自由解析 通过在词法分析和类型构建期间预先支付哈希成本，每个标识符和复杂结构都被转换为唯一的指针和密集ID。从那时起，解析器、类型检查器和优化器再也不使用`strcmp`或深度递归结构检查。密集区域驻留将编译器从缓慢的文本和树处理器转变为一个精简的、处理整数的机器。这一优化确保整个前端流水线几乎感觉是瞬时的。