Dense Arena Interning：编译器性能的关键引擎

背景

编译器在执行过程中需要大量处理名称和结构。源代码中的每个变量、函数和关键字都是字符串，这些字符串需要在编译器的多个阶段中被识别、分类和解析。问题的核心不仅仅是匹配字符串或比较类型签名，而是在整个管道中反复执行这些操作。例如，同一个变量名 counter 可能会被检查数百次：词法分析器检查一次，语法分析器检查一次，类型检查器反复检查，优化阶段也会多次检查。这种重复的字符串比较和结构比较成为编译器性能的重大瓶颈。

传统的做法要么是线性扫描（使用 strcmp），要么是哈希表查找。即使哈希表将每次查找从 O(N*L) 降低到 O(L)，代价依然在每次遇到该字符串时都要重新支付。理想的方案是“把成本前置”：在词法分析或类型构建阶段一次性支付哈希开销，后续所有阶段都依赖 O(1) 的数组索引和单指令指针比较。这正是 Dense Arena Interner（密集竞技场驻留器）所要解决的问题。

核心内容

线性瓶颈：O(N*L)

假设词法分析器扫描代码时遇到字符 f-u-n-c。它需要判断这是关键字（如 func 或 return）还是变量名。朴素的实现是对已知关键字列表进行线性扫描，使用 strcmp 逐一比较：

// 朴素词法分析器逻辑
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 的哈希值后直接跳转到可能的匹配位置。文章使用分离链接法（separate chaining）配合动态数组作为桶，确保即使在冲突情况下性能也保持稳定。哈希查找为 O(L)（平均情况下桶访问为 O(1)）。

// 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)，但每次在语法分析器、类型检查器或优化器中遇到该字符串时仍需支付哈希开销。我们需要一种方式，将这种成本从所有阶段转移至仅词法分析阶段。对于一个在后续阶段被复用 k 次的符号，权衡很简单：不使用驻留（interning），重复检查为 O(k * L)；使用驻留，仅在某一阶段支付 O(L) 的哈希开销，后续阶段变为 O(k)。驻留将成本转移到单一阶段，然后通过规范句柄（canonical handle）实现近乎常数时间的比较。

基础：稳定内存（Arena）

要完全消除字符串比较，需要确保相同的字符串指向完全相同的内存地址。标准的 malloc 或 realloc 可能会移动或分散数据，导致指针比较不可靠。文章使用 Arena Allocator（竞技场分配器），它在大的连续块中管理内存，提供两个关键保证：O(1) 分配和指针稳定性。

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;

在 Arena 中分配仅需“向前 bump”指针。一旦字符串存储在 Arena 块中，其地址永不改变。这种稳定性允许我们直接使用指针本身作为唯一标识。

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;
    /* 对齐 offset，而不仅仅是 size */
    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); /* 对齐后 bump */
    return ptr;
}

但有一个注意点：Arena 的“不可释放”特性。Arena 分配器非常适合批处理编译器，因为通常只需要在编译结束时丢弃整个内存块。但如果该编译器未来被适配为长期运行的 Language Server Protocol (LSP) 守护进程，由于 arena 无法在文件变化时单独释放已驻留的字符串，内存可能会膨胀。

核心抽象：Slice 和 InternResult

在定义驻留器之前，需要两个核心数据结构来传递数据。

Slice：对字符串或对象的轻量引用。它不拥有内存，仅指向起始位置和长度。这允许词法分析器直接指向源文件缓冲区而不需复制。

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

InternResult：驻留器返回的规范句柄。key 指向 arena 分配的 Slice，该 slice 再指向规范的字节序列。词法分析时可能创建许多临时 slice，但只要两个 slice 的字节和长度相同，它们就解析为相同的驻留记录。entry 存储密集 ID（Dense ID）和可选的元数据（如 token 类型）。

typedef struct {
    void *key;         // Arena 分配的 Slice*（指向规范字节）
    Entry *entry;      // 元数据（密集 ID 和元数据）
} InternResult;

密集竞技场驻留器（Dense Arena Interner）：购买 O(1) 查找

驻留（Interning）对数据进行去重——无论是字符串标识符还是复杂的类型结构——使得仅保留一个“规范”副本。实现中的“密集”（Dense）部分指的是如何标识这些对象：不使用仅指针，而是为每个唯一对象分配一个连续的、从零开始的整数（0,