1. 从一次编译期崩溃说起为什么要啃LLVM的ADT和内存管理前阵子帮一个做静态分析工具的朋友排查问题他的工具基于LLVM做了一套自定义的IR遍历逻辑跑小文件没问题一上大工程就随机崩溃堆栈指向的却总是标准库容器相关的位置。折腾了两天最后定位到的问题很典型他在遍历过程中用SmallVector存了一堆指向Value的指针但没搞清楚SmallVector的inline容量和堆分配切换的时机加上对BumpPtrAllocator的生命周期理解有偏差导致对象被提前回收。这个坑其实不算深但它暴露了一个共性问题——很多人用LLVM写pass、写工具语法层面能跑通可一旦涉及ADTAbstract Data Types抽象数据类型和内存管理就开始凭感觉写出问题只能靠猜。这篇随笔想聊的就是这块。LLVM的ADT和内存管理机制是它区别于普通C项目最核心的工程决策之一。LLVM没有直接用std::vector、std::map、std::string这些标准库设施作为主力而是自己造了一套容器和分配器原因不复杂编译器前端和中端要在极短的时间内处理海量的临时对象标准库的分配策略和容器设计在这个场景下不够用。理解这套机制不只是为了读懂LLVM源码更是为了在写pass、做IR分析、甚至做大模型推理框架的算子调度时能做出正确的数据结构选型和内存生命周期设计。关键词里提到了“大模型推理梳理”这看起来和LLVM八竿子打不着但实际做推理框架的人越来越关注LLVM这套东西。原因在于大模型推理的图编译、算子融合、内存池管理和编译器后端做的指令选择、寄存器分配、栈帧布局在工程思路上高度同构。很多推理框架的内存池设计本质上就是在模仿BumpPtrAllocator的思路很多图IR的节点存储用的就是SmallVector和ilist的变体。所以这篇内容我会把两条线并着讲一条是LLVM ADT和内存管理的具体机制另一条是这些机制在大模型推理场景下的映射和启发。适合谁看如果你正在写LLVM pass、做Clang插件、搞静态分析工具或者在做推理框架的图优化和内存管理这篇内容应该能帮你少踩几个坑。如果你只是刚接触LLVM想搞清楚SmallVector和std::vector到底该用哪个也能从里面找到答案。我会尽量把每个设计决策背后的“为什么”讲清楚而不是只列API。2. LLVM ADT的设计哲学不是重复造轮子而是场景倒逼2.1 标准库容器在编译器场景下的三个硬伤很多人第一次看LLVM源码会有一个疑问C标准库已经有vector、map、string了为什么LLVM还要自己写一套SmallVector、DenseMap、StringRef这不是重复造轮子吗我一开始也这么想直到自己写了一个基于std::unordered_map的符号表在几十万行代码的工程上跑了一遍才发现问题所在。第一个硬伤是小对象场景下的堆分配开销。编译器里大量的容器实际只存几个元素比如一个基本块的前驱列表、一条指令的操作数列表通常就2到8个元素。std::vector在这种情况下仍然会走一次堆分配而堆分配的开销在编译器这种需要遍历成千上万个基本块的场景下会被放大到不可接受。SmallVector的设计就是针对这个它在栈上预留一段inline空间元素数量不超过这个容量时完全不碰堆超过了才切换到堆分配。这个设计看起来简单但省下来的分配次数是数量级的。第二个硬伤是迭代器失效和引用稳定性。标准库容器在扩容时会重新分配内存导致所有迭代器、指针、引用失效。编译器里经常出现“我拿着一个指向某条指令的指针结果往某个容器里插了个元素指针就悬空了”的情况。LLVM的ilistintrusive linked list通过把链表节点嵌入对象本身保证了对象地址的稳定性——只要对象不被销毁指向它的指针就一直有效。这个特性在IR遍历和修改场景下极其重要。第三个硬伤是内存布局和缓存友好性。std::map是红黑树每个节点单独分配遍历时缓存命中率很差。LLVM的DenseMap用开放寻址法实现哈希表所有元素存在一块连续内存里遍历和查找的缓存表现好得多。编译器里符号表、常量表的查找极其频繁这个差异在大型工程上能带来可观的性能提升。2.2 SmallVector的inline容量一个需要认真对待的参数SmallVector是LLVM里用得最多的容器之一它的模板签名是SmallVectorT, N其中N是inline容量。这个N的选择不是随便填的它直接决定了容器的内存行为和性能特征。我见过不少人写SmallVectorValue *, 1或者SmallVectorInstruction *, 64前者太小导致频繁堆分配后者太大导致栈帧膨胀。正确的做法是根据实际场景的元素数量分布来选。比如一个函数参数的列表通常不超过8个那N8是合理的一条PHI节点的入边数量可能很多但绝大多数情况下不超过4个那N4加上堆扩容兜底是合适的。这里有一个容易被忽略的细节SmallVector的inline容量是按元素个数算的不是按字节数。如果你存的是大对象比如一个包含多个字段的结构体N8可能意味着栈上要预留几百字节。在递归深度较大的遍历算法里这会迅速耗尽栈空间。我踩过一次坑在一个递归下降的分析里每层栈帧都有一个SmallVectorSomeStruct, 16结果在深层嵌套的IR上直接爆栈。后来改成SmallVectorSomeStruct *, 16存指针问题才解决。提示SmallVector的inline容量选择建议先用一个保守的小值如4或8在profile确认分配次数确实成为瓶颈后再调大。不要一上来就填一个大数字。2.3 DenseMap与std::unordered_map的取舍逻辑DenseMap是LLVM的哈希表实现和std::unordered_map相比它的核心差异在于开放寻址、连续存储、对空键和墓碑键的特殊处理。这些差异带来的实际影响我用一个真实场景来说明。之前做一个跨过程的常量传播分析需要维护一个从Value *到常量值的映射。一开始用的是std::unordered_mapValue *, Constant *在中等规模的模块上跑时间还能接受。后来换到DenseMapValue *, Constant *同样的分析逻辑耗时下降了大约三成。原因不复杂DenseMap的连续存储让查找时的缓存命中率大幅提升而std::unordered_map的链式哈希在每个桶上都要跳一次指针。但DenseMap不是没有代价的。它要求键类型有“空键”和“墓碑键”的概念对于指针类型这很自然nullptr是空键但对于自定义类型就需要特化DenseMapInfo。另外DenseMap的迭代顺序是不确定的而且随着删除操作会产生墓碑影响性能。如果你的场景需要频繁删除且对迭代顺序有要求std::map或者MapVector可能更合适。容器底层结构适用场景不适用场景SmallVectorinline数组堆数组元素少、生命周期短、频繁遍历元素数量大且不可预测DenseMap开放寻址哈希表查找密集、键为指针或整数频繁删除、需要稳定迭代顺序StringMap哈希表字符串池字符串键的查找需要按字典序遍历ilist侵入式双向链表对象地址需稳定、频繁插入删除需要随机访问MapVectorvectormap组合需要稳定迭代顺序且查找频繁元素数量极大3. BumpPtrAllocator与内存生命周期LLVM为什么敢“不释放”3.1 区域分配的核心思想批量申请统一释放LLVM的内存管理里BumpPtrAllocator是一个绕不开的东西。它的思路用一句话概括从系统申请大块内存然后在这块内存上像指针碰撞一样往前分配单个对象不单独释放最后整块一起还回去。这种分配方式叫区域分配arena allocation在编译器、游戏引擎、推理框架里都很常见。为什么LLVM敢这么做因为编译器处理的绝大多数对象生命周期是“阶段性的”。比如解析一个翻译单元时创建的所有AST节点在整个翻译单元处理完后就可以全部释放一个函数被优化时创建的临时IR节点在函数优化完成后就可以全部回收。这种“同生共死”的生命周期模式天然适合区域分配。BumpPtrAllocator的核心接口就几个Allocate(size, align)分配内存Reset()重置分配器不释放底层内存只是把指针拨回去析构时释放所有底层内存。它内部维护一个slab列表每个slab是一块较大的内存默认4KB起按需增长分配时在当前slab上移动指针当前slab不够了就开新slab。这个设计的性能优势很明显分配就是指针加法释放就是整块回收没有逐对象的malloc/free开销也没有内存碎片问题。代价是你不能单独释放某个对象也不能在分配器销毁前让对象“提前死亡”——除非你手动调用析构函数。3.2 对象生命周期与析构BumpPtrAllocator不负责调用析构函数这是最容易踩的坑。BumpPtrAllocator只管理内存不管理对象生命周期。你用Allocate拿到的是一块原始内存如果要在上面构造对象需要自己调用placement new对象用完需要析构时也要自己调用析构函数。分配器析构时不会帮你调用任何析构函数。我见过一个典型的错误有人用BumpPtrAllocator分配了一堆包含std::string成员的对象然后直接Reset()结果std::string内部的堆内存全部泄漏。正确的做法是要么在Reset()前手动遍历调用析构函数要么用SpecificBumpPtrAllocator——它会在析构时对每个分配的对象调用析构函数。SpecificBumpPtrAllocatorT是BumpPtrAllocator的一个包装它知道对象类型所以能在析构时正确调用T的析构函数。但注意它仍然不支持单独释放某个对象也不支持在Reset()时调用析构Reset()只是把内存拨回去不调用析构。如果你需要“分配-释放-再分配”的模式SpecificBumpPtrAllocator并不适合。注意如果你的对象持有堆资源如std::vector、std::string、文件句柄使用BumpPtrAllocator时必须确保在分配器销毁前手动调用析构函数否则资源泄漏。SpecificBumpPtrAllocator只在析构时调用Reset()不调用。3.3 大模型推理中的内存池BumpPtrAllocator思路的现代翻版现在把视角切到大模型推理。推理框架里有一个核心组件叫内存池memory pool它的设计目标和BumpPtrAllocator高度一致推理过程中会频繁申请和释放张量内存如果每次都走系统分配器开销和碎片都不可接受。所以主流推理框架都会预分配一大块显存或内存然后在上面做子分配。以常见的推理场景为例一个batch的请求进来需要为每个请求的KV Cache、中间激活值、算子临时缓冲区分配内存。这些内存的生命周期是“请求级”的——请求处理完就可以全部回收。这正好对应BumpPtrAllocator的“区域分配”模式为每个请求或每个batch开一个arena请求结束就整块回收。但推理场景比编译器多了一个约束显存是有限的不能像CPU内存那样“先申请了再说”。所以推理框架的内存池通常会在BumpPtrAllocator的基础上加一层空闲块管理支持不同大小的块复用。这其实是在区域分配和自由链表分配之间做折中。理解BumpPtrAllocator的取舍能帮你在设计推理内存池时想清楚哪些内存适合arena哪些需要独立管理。另一个映射点是图IR的节点存储。推理框架的图IR里节点和边的关系经常用侵入式链表或SmallVector来存这和LLVM的ilist、SmallVector思路一致。图优化过程中会创建大量临时节点这些节点的生命周期通常也是阶段性的用arena分配比逐个new/delete高效得多。4. 从LLVM ADT到推理框架数据结构选型的迁移经验4.1 StringRef与字符串视图避免拷贝的通用模式StringRef是LLVM里一个很巧妙的设计它只是一个指针加长度不拥有字符串内存所有操作都是视图级别的。这个设计在编译器里用来表示标识符、文件名、IR中的字符串常量避免了大量不必要的字符串拷贝。这个模式在大模型推理里也有直接对应。推理框架处理token序列、prompt模板、算子名称时如果每个字符串都拷贝一份内存和CPU开销都会上去。用类似StringRef的视图类型配合一个字符串池所有字符串存在池里视图只引用池中的片段能显著降低开销。LLVM的StringMap和StringSaver就是这套组合StringSaver负责把字符串存进分配器StringMap负责查找StringRef负责传递。我自己的经验是在推理框架的图优化阶段算子名称、属性键、设备名称这些字符串用字符串池加视图的方式管理比直接用std::string省下不少内存和拷贝时间。尤其是图优化会反复遍历节点、比较名称视图比较比字符串比较快得多。4.2 ilist的侵入式设计对象地址稳定的价值ilist是LLVM的侵入式链表它的节点指针直接嵌在对象里所以对象一旦分配地址就固定不变。这个特性在IR修改场景下极其重要你拿着一个指向某条指令的指针往链表里插入或删除其他节点这个指针始终有效。推理框架的图IR也有类似需求。图优化过程中你会持有指向某个节点的指针同时修改图的结构增删节点、改边。如果节点存在std::vector里vector扩容会让所有指针失效你就得用索引或者智能指针来间接引用代码会变得很啰嗦。用侵入式链表或者稳定地址的节点池能避免这个问题。但侵入式链表也有代价每个对象要多存两个指针前驱和后继内存开销增加对象不能被随意拷贝拷贝会破坏链表结构删除节点时要手动从链表上摘下来。这些代价在编译器场景下可以接受因为节点数量相对可控而且地址稳定的收益远大于内存开销。4.3 DenseMap在算子调度中的应用与边界推理框架的算子调度器需要维护“算子到设备”的映射、“张量到内存块”的映射这些查找非常频繁。用DenseMap的思路开放寻址、连续存储来实现这些映射比用std::unordered_map更合适。但要注意DenseMap的边界条件。它的性能在负载因子较低时很好负载因子高了之后冲突增多性能下降明显。LLVM的DenseMap默认在负载因子达到3/4时扩容这个阈值在大多数场景下是合理的。如果你的场景删除操作很多墓碑会累积需要定期shrink_and_clear或者重建。另一个坑是DenseMap的键类型要求。指针和整数作为键很自然但如果你用自定义结构体作为键需要提供DenseMapInfo特化定义空键、墓碑键和哈希函数。这个工作不难但容易出错尤其是哈希函数的质量直接影响性能。我一般建议如果键是复合类型先用std::pair或std::tuple包装LLVM已经为这些类型提供了DenseMapInfo。5. 实操中的坑与排查链路几个真实案例的复盘5.1 SmallVector扩容导致的指针失效前面提到的那个静态分析工具崩溃根因就是SmallVector扩容。具体场景是这样的工具在遍历一个基本块时用SmallVectorInstruction *, 4收集需要后续处理的指令。遍历过程中每收集一条指令就往另一个SmallVector里插入一条新指令而这两个SmallVector之间存在指针引用关系。当第二个SmallVector扩容时它内部的元素地址变了但第一个SmallVector里存的指针还指向旧地址于是访问时崩溃。排查过程是这样的先看崩溃堆栈发现是在访问某个Instruction的字段时出错地址看起来是合法的但内容不对。然后用AddressSanitizer跑了一遍报的是use-after-free但对象其实没被释放只是被移动了。最后定位到SmallVector扩容才明白是扩容导致的地址变化。修复方案有两种一是把存指针改成存索引扩容后索引仍然有效二是把SmallVector换成std::deque或ilist保证元素地址稳定。我选了第一种因为改动最小而且索引访问的性能也不差。这个坑的教训是任何时候你持有指向容器元素的指针都要问自己这个容器会不会扩容扩容后指针会不会失效。SmallVector、std::vector都有这个问题std::deque和ilist没有。5.2 BumpPtrAllocator的Reset与对象析构顺序另一个案例来自一个IR重写工具。工具用BumpPtrAllocator管理所有新建的IR节点处理完一个函数后调用Reset()回收内存。但节点里有一些std::string成员Reset()不调用析构函数导致这些字符串的堆内存泄漏。工具跑小函数没问题跑大函数时内存持续增长最后OOM。排查时先用valgrind跑报了一堆“still reachable”的块指向std::string的内部缓冲区。然后看代码发现BumpPtrAllocator的Reset()确实不调用析构。修复方案是把BumpPtrAllocator换成SpecificBumpPtrAllocatorIRNode它在析构时会调用每个节点的析构函数。但注意SpecificBumpPtrAllocator的Reset()仍然不调用析构所以如果需要在处理完一个函数后回收得改成每个函数用一个独立的分配器函数处理完直接销毁分配器。这个坑的教训是BumpPtrAllocator只管理内存不管理生命周期。对象里有堆资源时必须确保析构函数被调用。要么用SpecificBumpPtrAllocator并在销毁时回收要么手动遍历调用析构。5.3 DenseMap的墓碑累积导致性能退化第三个案例是一个符号表实现。用DenseMap存符号名到符号信息的映射支持符号的插入和删除。工具长时间运行后发现查找越来越慢。用perf分析发现大量时间花在DenseMap的探测上。原因是DenseMap删除元素时不会真正移除而是标记为墓碑。墓碑会占用探测序列导致查找时的探测长度增加。当删除操作很多时墓碑比例上升性能退化。LLVM的DenseMap在墓碑比例达到一定程度时会触发rehash但如果你的删除模式是“删一批插一批”rehash的时机可能不够及时。修复方案是定期调用shrink_and_clear()或者重建DenseMap。更根本的方案是换用MapVector或者std::map如果删除操作确实很频繁。我最后换成了MapVector因为符号表还需要稳定的迭代顺序MapVector正好满足。问题现象根因排查手段修复方案随机崩溃地址合法但内容不对SmallVector扩容导致指针失效ASan 代码审查改存索引或换稳定地址容器内存持续增长OOMBumpPtrAllocator不调用析构valgrind 代码审查换SpecificBumpPtrAllocator或手动析构查找越来越慢DenseMap墓碑累积perf 容器状态检查定期shrink或换MapVector6. 大模型推理场景下的内存管理再思考6.1 KV Cache的分配策略与arena思路KV Cache是大模型推理里内存占用的大头。每个请求的KV Cache大小取决于序列长度、层数、头数、头维度通常是几十MB到几百MB。推理框架需要为每个请求分配KV Cache请求结束后回收。这个场景和BumpPtrAllocator的思路很契合为每个请求或每个batch开一个arena请求处理过程中所有KV Cache、中间激活、临时缓冲区都从这个arena分配请求结束整块回收。这样避免了频繁的malloc/free也避免了碎片。但KV Cache有一个特殊之处它的生命周期可能跨越多个推理步骤自回归生成时每生成一个token就要追加KV。所以arena不能在整个请求结束后才回收而是要在请求的整个生命周期内保持。这要求arena的管理粒度是“请求级”而不是“步骤级”。推理框架通常会用分页或分块的方式管理KV Cache本质上是在arena的基础上加了一层块管理。6.2 图编译阶段的内存复用与生命周期分析推理框架的图编译阶段会对计算图做算子融合、内存规划、生命周期分析。其中内存规划的核心是分析每个张量的生命周期把生命周期不重叠的张量分配到同一块内存上减少峰值内存占用。这个思路和编译器后端的栈帧布局、寄存器分配高度同构。LLVM的SlotIndexes、LiveIntervals分析就是在做类似的事情分析每个值的活跃区间然后分配寄存器或栈槽。推理框架的内存规划器也在做活跃区间分析只是对象从寄存器变成了张量。理解LLVM的这套分析框架对设计推理框架的内存规划器很有帮助。比如LLVM的活跃区间分析用LiveInterval表示一个值的活跃范围用LiveIntervals管理所有区间用RegisterCoalescer做合并。推理框架的内存规划器可以用类似的数据结构用区间表示张量的生命周期用区间树或扫描线算法做内存复用。6.3 推理框架中ADT选型的经验法则结合前面的讨论我总结几条推理框架里ADT选型的经验法则小列表用SmallVector思路算子的输入输出列表、图的边列表元素通常不多用inline容量小的容器避免堆分配。查找密集的映射用DenseMap思路算子名到算子的映射、张量ID到张量的映射用开放寻址哈希表注意墓碑管理。需要稳定地址的对象用侵入式链表或对象池图节点、IR节点用侵入式链表或稳定地址的对象池避免指针失效。字符串用视图加池算子名、属性键、设备名用字符串池加视图避免拷贝。阶段性对象用arena请求级的KV Cache、中间激活用arena分配整块回收。这些法则不是绝对的具体选型还要看场景的访问模式、生命周期特征、内存约束。但有了这套框架至少不会在选型时凭感觉走。7. 几个容易被忽略的细节与个人体会7.1 ADT的迭代器失效规则要记牢LLVM的ADT迭代器失效规则和标准库不完全一样需要单独记。SmallVector的迭代器在扩容时失效这点和std::vector一样。DenseMap的迭代器在插入时可能失效因为可能触发rehash删除时只有被删除元素的迭代器失效。ilist的迭代器在插入删除时只有被操作元素的迭代器失效其他元素的迭代器保持有效。这些规则在写遍历加修改的代码时很关键。我一般建议如果遍历过程中要修改容器先把要修改的元素收集起来遍历完再统一修改或者用make_early_inc_range这类工具它在遍历时先递增迭代器再返回元素避免删除当前元素导致的失效。7.2 分配器的对齐要求不能忽略BumpPtrAllocator的Allocate接口接受对齐参数默认是按alignof(std::max_align_t)对齐。如果你分配的对象有更高的对齐要求比如SIMD类型要求16或32字节对齐必须显式传入对齐参数。否则在某些平台上会触发对齐异常或者性能下降。这个坑在推理框架里更容易踩因为张量数据经常要求特定的对齐比如GPU内存要求256字节对齐。用arena分配张量内存时一定要把对齐要求传进去否则可能出现“数据能读但性能不对”的隐蔽问题。7.3 内存池的碎片问题与应对arena分配虽然避免了外部碎片但内部碎片仍然存在。如果arena里分配的对象大小差异很大小对象占用的slab空间可能浪费很多。推理框架里KV Cache是大块中间激活是小块如果混在同一个arena里碎片问题会比较明显。应对方式是按大小分池大块走大块池小块走小块池各自用独立的arena。这样每种池内的对象大小相对均匀内部碎片可控。LLVM的BumpPtrAllocator本身不区分大小但你可以用多个分配器实例来达到分池的效果。7.4 个人体会理解机制比记住API重要最后说点个人体会。LLVM的ADT和内存管理API其实不多但背后的设计决策和取舍很丰富。我见过很多人能背出SmallVector的接口但说不清楚为什么N要选某个值能用BumpPtrAllocator分配内存但不知道析构函数什么时候被调用。这种“会用但不懂”的状态在遇到边界问题时就会暴露。我的建议是每用一个LLVM的ADT或分配器都问自己三个问题它的内存布局是什么样的它的生命周期规则是什么它在什么场景下会失效或退化把这三个问题想清楚比记住API有用得多。这套思维方式在迁移到推理框架的内存管理时同样适用——毕竟编译器和大模型推理在内存管理这件事上面对的是同一类问题。