葛根 - 并发集合和映射数据结构

信息单调增长。

葛根提供了一种在并发跳表中实现的 Map 和 Set。kudzu 中的类型与其它并发数据结构之间的关键区别是，kudzu 的数据结构不支持 删除 操作。这种限制使得这些类型更容易实现，并且希望性能更优，协调开销更小，同时对于许多应用仍然很有用。

用例

这些可以用于任何仅增长（从不丢失成员）的映射或集合的并发算法。例如，这可以与 rayon 结合作为具有重复子问题的分而治之算法（例如斐波那契数列）的缓存表。

并发属性

假设我的实现是正确的，我的推理是合理的（很大的假设），以下这些应该都是正确的

• 不可能发生数据竞争。
• 映射上的所有操作都是 无锁的：不可能有两个并发操作在同一个集合上产生死锁。
• 查找是 无等待的：在集合中查找项永远不会等待另一个线程完成。
• 跳表在任何时候都不会处于与跳表属性不一致的状态（即，每个车道都将始终是下面车道的子集）。

查找访问是通过简单地使用 Relaxed 加载通过跳表进行搜索来执行的，没有锁定或协调。

插入是通过找到插入位置并对节点将要插入的车道中的指针执行 CAS 来执行的。如果最低车道的 CAS 失败，则节点不会插入，并且整个插入算法将重新尝试。然而，在任何比最低车道更高的车道上，一旦插入失败，我们只需停止插入。这使得列表比理想情况下更平坦，但在处理这种竞争时比重试要便宜得多 - 我希望这种权衡是可取的。

（如果发现元素已存在，则插入该元素会返回您尝试插入的元素，而不会更改集合中已存在的值。）

由于这种插入策略和缺乏删除操作，可以通过简单地在每个修改过的指针上使用原子CAS操作来维持并发正确性，而不必跟踪额外的元数据和节点级别的锁。

我非常感谢这篇论文，它描述了一个类似算法并在结论中提出了一些类似于我的算法的建议。

内存布局优化

这个跳表也有高度优化的内存布局来提高性能。每个节点都将其所有通道与元素内联，但大小精确，不包含未使用的通道空间。这意味着每个节点的空间开销平均只有2个指针和1个字节（用于跟踪通道数量以进行分配回收）。

我们还以逆序存储通道，最高通道作为第一个元素。与内联节点相结合，我们应该有更好的内存局部性，因为节点通常是在其最高通道而不是最低通道被访问。