RRB 向量:一种实用的通用不可变序列

主要观点:现有的最先进的不可变集合在不同操作上性能差异大,导致程序员需为每项任务选择不同集合实现,程序更改会使集合选择无效,增加代码演化成本,希望有能在多种操作上表现良好的集合。
关键信息:介绍 RRB-Vector 这一不可变序列集合,其在大量顺序和并行操作上性能良好,底层创新包括松弛基数平衡(RRB)树结构可高效重组结构,以及利用时空局部性抵消遍历树的成本。
重要细节:在基准测试中,RRB-Vector 在 4 个 8 核 CPU 上并行操作的加速比下限为 7 倍,在离散操作如两端添加、更新和删除元素等方面性能始终良好,与现有重要不可变序列集合相比有优势,其内存占用与数组相当,比竞争集合低一个数量级。

阅读 30
0 条评论