跳过列表与二进制搜索树
我最近遇到了称为跳过列表的数据结构。 它似乎与二叉搜索树有非常相似的行为。
为什么你会想要在二叉搜索树上使用跳过列表？
跳过列表更适合于并发访问/修改。 Herb Sutter写了一篇关于并发环境中数据结构的文章。 它有更深的信息。
二叉搜索树最常用的实现是红黑树。 并发问题出现在树被修改时通常需要重新平衡。 重新平衡操作可能会影响树的大部分，这将需要许多树节点上的互斥锁。 将节点插入到跳过列表中是更加本地化的，只有直接链接到受影响节点的节点需要被锁定。
Jon Harrops的评论更新
我读了弗雷泽和哈里斯的最新论文并发编程，没有锁。 真正好的东西，如果你对无锁数据结构感兴趣。 本文重点介绍事务内存和理论操作的多字比较交换MCAS。 这些都是用软件模拟的，因为没有硬件支持它们。 我相当印象深刻的是，他们能够用软件构建MCAS。
我没有发现事务内存的东西特别引人注目，因为它需要一个垃圾回收器。 软件事务性内存也受到性能问题的困扰。 但是，如果硬件事务内存变得普遍，我会非常兴奋。 最后它仍然是研究，并且不会再用于生产代码十年左右。
在第8.2节中，他们比较了几个并发树实现的性能。 我会总结他们的发现。 下载PDF格式是值得的，因为它在第50,53和54页有一些非常丰富的图表。
更新
这里是关于无锁树的论文：使用CAS的无锁红黑树。
我没有深入研究它，但表面上看起来很稳固。
首先，你不能公平地比较随机数据结构和给你最坏情况保证的数据结构。
跳过列表相当于随机平衡二叉搜索树（RBST），其方式在Dean和Jones的“探索跳过列表和二叉搜索树之间的对偶性”中有更详细的解释。
相反，你也可以有确定性的跳过列表来保证最差的表现。 Munro等人
与上述某些声明相反，您可以实现在并发编程中运行良好的二叉搜索树（BST）。 以并发为中心的BSTs存在一个潜在的问题，就是你无法轻易获得相同的结果，就像你从红黑树（RB）树那里获得平衡一样。 （但是“标准”，即随机排序，跳过列表也不能给你这些保证）。在任何时候保持平衡和良好（并且易于编程）并发访问之间有折衷，所以通常使用宽松的RB树当需要良好的并发性时。 放松在于不立即重新平衡树。 对于有点过时的（1998年）调查，请参阅Hanke的“同时红黑树算法的性能”[ps.gz]。
其中一个最近的改进就是所谓的彩色树（基本上你有一些重量，黑色将是1，红色将是零，但是你也允许其中的值）。 一棵彩树如何避免跳过列表？ 让我们来看看布朗等人。 “非阻塞树的通用技术”（2014）必须说：
有128个线程，我们的算法优于Java的非阻塞跳过列表13％至156％，Bronson等人基于锁的AVL树。 增长63％至224％，使用软件事务内存（STM）的RBT提高13至134倍
编辑补充：Pugh的基于锁的跳过列表，在Fraser和Harris（2007）的“无锁并发编程”中进行了基准测试，接近他们自己的无锁版本（这里的顶部答案充分坚持这一点），也调整好并发操作，参见 Pugh的“同时维护跳过列表”，虽然以相当温和的方式。 尽管如此，Herlihy等人提出的2009年的一篇较新的论文“简单的乐观跳过列表算法”提出了一种假设比基于锁的并发跳过列表更简单的实现方式，批评了Pugh没有提供足够令人信服的正确性证明为他们。 撇开这个（也许太迂腐）质量，Herlihy等人。 表明它们更简单的基于锁的跳过列表实现无法扩展以及JDK的无锁实现，但仅适用于高争用（50％插入，50％删除和0％查找）...... Fraser哈里斯根本没有测试; Fraser和Harris仅测试了75％的查找，12.5％的插入和12.5％的删除（在大约500K元素的跳过列表中）。 Herlihy等人的简单实施。 在接受测试（70％查询，20％插入，10％删除）的低争用情况下，它也接近JDK的无锁解决方案; 当他们将跳过列表放大到足够大时（即从200K变为2M元素），他们实际上击败了无锁解决方案，因此任何锁的争用概率变得微不足道。 如果Herlihy等人本来会很好。 已经结束了Pugh的证明并测试了他的实施，但是他们并没有这样做。
编辑2：我发现了一个（2015年出版的）所有基准测试的母模：Gramoli的“超过你想知道的关于同步。同步机制，测量同步对并发算法的影响”：这是一个与这个问题相关的摘录图像。
“Algo.4”是上述Brown等人的前体（2011年版本较早）。 （我不知道2014年版本有多好或多坏）。 “Algo.26”是上面提到的Herlihy的; 正如您所看到的，它会在更新时被丢弃，而在此处使用的Intel CPU与原始纸张上的Sun CPU相比更糟糕。 “Algo.28”是来自JDK的ConcurrentSkipListMap; 与其他基于CAS的跳过列表实现相比，它的表现不如人们所希望的那样好。 高争端的赢家是Crain等人描述的“Algo.2”锁定算法（!!）。 在“争用友好型二进制搜索树”和“Algo.30”中是来自“多核对数数据结构”的“旋转跳过列表”。 “Algo.29”是“无热点无阻塞跳过列表”。 请注意，Gramoli是这三种赢家算法论文的共同作者。 “Algo.27”是Fraser跳过列表的C ++实现。
Gramoli的结论是，搞乱一个基于CAS的并发树实现要比搞砸一个类似的跳过列表容易得多。 根据这些数字，很难不同意。 他对这个事实的解释是：
设计一个无锁树的困难源于自动修改多个引用的困难。 跳过列表由通过后继指针相互连接的塔组成，其中每个节点指向紧靠其下方的节点。 它们通常被认为与树相似，因为每个节点在后继塔和后面都有一个后继者，然而，主要区别在于向下指针通常是不可变的，因此简化了节点的原子修改。 这种区别可能就是为什么跳过列表在大量争用中胜过树木的原因，如图[上图]所示。
布朗等人最近的工作重点关注这一难题。 他们有一个完整的（2013年）论文“关于非阻塞数据结构的实用基元”，它们构建了多记录LL / SC复合“原语”，他们称之为LLX / SCX，它们自己使用（机器级）CAS来实现。 Brown等人 在2014年（但不是2011年）并发树实现中使用了这个LLX / SCX构建块。
我认为这里也许值得总结一下“没有热点”/“争用友好”（CF）跳过列表的基本概念。 它从宽松的RB树（以及类似的混乱数据结构）中添加了一个基本思想：塔插入后不再立即建立，而是延迟到争用较少时为止。 相反，删除高塔可能会引发很多争论; 这可以追溯到Pugh 1990年同时跳过列表的论文，这就是为什么Pugh在删除时引入了指针反转（有关维基百科跳过列表的页面仍然没有提及到今天的消息，叹息）。 CF跳过列表进一步推迟了这一点，并延迟删除高层楼的高层。 CF跳过列表中的这两种延迟操作都是由一个基于（CAS）的独立垃圾收集器样线程执行的，其作者称之为“适配线程”。
Synchrobench代码（包括所有测试的算法）可在以下网址找到：https：//github.com/gramoli/synchrobench。 最新的布朗等人。 实现（未包含在上面）可在http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java获得有没有人可以使用32+核心机器？ J / K我的观点是你可以自己运行这些。
此外，除了给出的答案（易于实施，与平衡树相媲美的性能）。 我发现实现顺序遍历（向前和向后）要简单得多，因为跳过列表在其实现中有效地包含链表。
链接地址: http://www.djcxy.com/p/65679.html