Porting a Segmented List from C to Rust
7 months ago
- #systems-programming
- #memory-management
- #performance
- 将分段列表从C语言移植到Rust，以比较语义、实现方式、性能及代码美学
- 分段列表具备零重分配、零拷贝、按需增长的惰性分配特性，底层采用碰撞分配器实现
- 向量（动态数组）因重分配和拷贝在扩容时表现不佳，而分段列表以非连续存储为代价，在大规模AST节点场景中性能更优
- 设计采用几何级数增长策略（如1.5倍或2倍），减少系统调用并保持指针稳定性
- 分段列表的索引需通过对数运算计算段位置和偏移量
- C语言实现包含基于mmap的碰撞分配器，并通过宏实现泛型列表操作
- Rust实现利用x86 Linux系统调用ABI处理mmap/munmap，定制兼容GlobalAlloc的分配器，并预计算块边界提升效率
- 基准测试显示：对于超大元素（≥1MiB），Rust分段列表性能优于std::vec::Vec，但Vec在小规模常规场景仍保持优化优势
- Rust的痛点包括分配器需满足Sync/Send约束、并发测试的不稳定性，以及段错误更难调试
- 相比C语言，Rust在泛型、trait实现（如Drop）、枚举类型、内置测试/基准测试及编译期优化等方面更具优势