LLVM 项目中的常见数据结构

type

status

date

slug

summary

category

icon

password

造轮子可以说是C++程序员的传统艺能了，作为最知名、影响最深的C++开源项目之一，LLVM也为其自身需求实现了许多数据结构。

为什么不直接使用 C++ 标准库呢：

标准数据结构性能的平台依赖性：C++ 标准库（STL）的实现由各编译器厂商（如 GCC、Clang、MSVC）自行完成，导致相同数据结构的性能特征可能因平台而异。

案例对比：

操作	`std::vector`（GCC）	`std::vector`（MSVC）
`push_back` 扩容策略	2 倍容量增长	1.5 倍容量增长
内存对齐	默认 16 字节	默认 8 字节

性能影响：MSVC 的扩容策略更节省内存但可能增加重新分配次数，GCC 的对齐方式对 SIMD 运算更友好。

功能缺失：开发项目时，当时的C++标准库可能还缺少相应的数据结构

例如 unordered_map 是 C++11 引入的

优化空间：可以进行针对性的优化，比标准库效率更高

本文尝试列举一些在学习LLVM项目的过程中经常会遇到的数据结构。

目前以下大部分内容摘自互联网和 DeepSeek生成的内容，对于前者会在最后列出参考资料，但原谅我懒得每句都标注引用了。

SmallVector

LLVM 的 SmallVector 是一个高度优化的动态数组容器，专为编译器场景设计，结合了栈上静态分配和堆上动态分配的优势，旨在提升小数据集场景下的性能。

代码示例

核心设计理念

SmallVector 的核心思想是 「小对象优化」（Small Object Optimization, SOO）：

栈上预分配：在栈内存中预先分配固定大小的空间（模板参数指定），避免小数据集时的堆内存分配。

动态扩展：当元素数量超过预分配容量时，自动切换到堆内存（类似 std::vector），保持动态扩容能力。

测试数据

DenseMap

LLVM 的 DenseMap 是一个高性能的哈希表实现。与标准库的 std::map（基于红黑树）或 std::unordered_map（基于链式哈希表）不同，DenseMap 是一个基于二次探查（Quadratic probing）的哈希表。

特点

DenseMap使用单一分配方式一次性分配所有bucket的内存(用来存储key-value pair), 因此具有较好的局部性。在插入元素时在已分配的地址上构造元素。

由于其预分配内存的原因, 扩增哈希表会导致重新分配内存与拷贝(否则无法维护连续内存的特性),因此增删元素会导致迭代器失效(这点与std::map不同)。另外预分配也导致额外内存开销(实际插入元素个数少于分配个数)。

键类型

DenseMap 支持所有的指针和整形作为键。

其他的类型可以通过定义对应的 DenseMapInfo<> 类，以作为新的键类型。

使用自定义数据类型做Key时需要注意是否实现了对应的DenseMapInfo<>类, 如果不想关心这些琐事, 保险的做法是指针用对象指针做Key.

测试数据

实现

键值对本身是std::pair<KeyT, ValueT>。

DenseMap<>有四个数据成员：

Buckets: 散列桶的首地址

NumEntries: 存储的数据个数

NumTombstones: Tombstone（二次探查法删除数据时需要设置deleted标识）

NumBuckets: 桶的个数

SmallDenseMap

DenseMap最小要求分配 64 个元素, 如果map中存储元素较少造成很大的浪费, 所以LLVM又定义了一个针对少量元素的SmallDenseMap。

SmallDenseMap与DenseMap的唯一区别是前者假定元素个数通常小于一个给定值, 因此默认初始化时会静态初始化一个bucket数组. 在分配元素超过了限制后会退化为DenseMap。

在元素个数可估算时通常使用SmallDenseMap更为高效.

SmallDenseMap与DenseMap基本类似, 区别在于:

SmallDenseMap定义一个union(AlignedCharArrayUnion), 保存了InlineBuckets个BucketT元素的数组, 或是一个LargeRep结构. 前者是静态构造的bucket数组, 后者等同于DenseMap中动态分配的bucket数组。