跳过列表与二进制树
我最近遇到了称为跳过列表的数据结构。 他们似乎有非常相似的行为二叉search树…我的问题是 – 为什么你会想在二叉search树上使用跳过列表？
跳过列表更适合于并发访问/修改。 Herb Sutter在并发环境中写了一篇关于数据结构的文章 。 它有更深的信息。
二叉search树最常用的实现是红黑树 。 并发问题出现在树被修改时往往需要重新平衡。 重新平衡操作可能会影响树的大部分，这需要在许多树节点上进行互斥锁。 将节点插入到跳过列表中是更加本地化的，只有直接链接到受影响节点的节点需要被locking。
Jon Harrops的更新评论
我读了弗雷泽和哈里斯的最新论文并发编程没有锁 。 真正好的东西，如果你对无锁数据结构感兴趣。 本文重点介绍事务内存和理论操作的多字比较交换MCAS。 这两个都是软件模拟的，因为没有硬件支持它们。 我相当印象深刻的是，他们能够用软件来构buildMCAS。
我没有发现事务内存的东西特别引人注目，因为它需要一个垃圾回收器。 另外软件事务性内存受到性能问题的困扰。 但是，如果硬件事务内存变得普遍，我会非常兴奋。 最后，它仍然是研究，将不会用于生产代码十年左右。
在第8.2节中，他们比较了几个并发树实现的性能。 我将总结他们的发现。 下载PDF格式是值得的，因为它在第50,53和54页有一些非常丰富的图表。
- locking跳过列表非常快速。 它们的并发访问数量非常好。 这就是跳过列表的特殊之处，其他基于锁的数据结构往往会在压力下发作。
- 无locking跳过列表始终比locking跳过列表快，但几乎没有。
- 事务性跳过列表一直比locking和非locking版本慢2-3倍。
- 在并发访问下locking红黑树木 。 它们的性能随着每个新的并发用户线性降低。 在两个已知的locking红黑树实现中，在树重新平衡期间基本上具有全局锁。 另一个使用花哨（和复杂）的锁升级，但仍然没有显着执行全局锁版本。
- 无locking的红黑树不存在（不再是真实的，请参阅更新）。
- 事务性红黑树与事务性跳过列表相当。 这是非常令人惊讶和非常有前途的。 事务性内存虽然比较容易写，但速度较慢。 它可以像在非并发版本上快速search和replace一样简单。
更新
这里是关于无锁树的论文： 使用CAS的无锁红黑树 。
我没有深入研究，但表面上看起来很稳固。
首先，你不能公平地比较一个随机数据结构和一个给你最坏情况保证的数据结构。
跳过列表相当于一个随机平衡二叉search树（RBST），在Dean和Jones的“探索跳过列表和二叉search树之间的对偶性”中有更详细的解释。
反过来，你也可以有确定性的跳过列表，保证最差的performance，比较。 Munro等人
与上面的某些声明相反，您可以实现在并发编程中运行良好的二叉search树（BST）。 以并发为中心的BST的一个潜在的问题是，你不能轻易得到同样的保证，就像你从红黑树（RB）中得到的一样。 （但是“标准”，即随机sorting，跳过列表也不能给你这些保证）。在任何时候保持平衡和良好（并且容易编程）并发访问之间有折衷，所以通常使用宽松的 RB树当需要良好的并发性时。 放松在于不立即重新平衡树。 对于一个有点过时的（1998年）调查，请参阅Hanke的“同时红黑树algorithm的性能” [ps.gz] 。
其中一个最近的改进就是所谓的彩色树 （基本上你有一些重量，黑色将是1，红色将是零，但你也允许在两者之间的值）。 一棵彩树如何避免跳过列表？ 让我们来看看布朗等人。 “无障碍树的通用技术” （2014）必须说：
有128个线程，我们的algorithm优于Java的非阻塞跳过列表13％至156％，Bronson等人的基于锁的AVL树。 由63％提高到224％，而使用软件事务存储器（STM）的RBT提高了13到134倍
编辑添加：Pugh的基于锁的跳过列表，在Fraser和Harris（2007年） “无锁并发编程”中进行了基准testing，接近他们自己的无锁版本（这里最重要的答案是充分坚持的观点），也调整好并发操作，参见。 Pugh的“同时维护跳过列表” ，虽然在一个相当温和的方式。 尽pipe如此，Herlihy等人提出的2009年的一篇较新的论文“简单的乐观跳过列表algorithm”提出了一个比Pugh更为简单的并发跳过列表的基于锁的实现方式，批评了Pugh没有提供足够令人信服的certificate为他们。 撇开这个（也许太迂腐）质量，Herlihy等人。 表明它们更简单的基于锁的跳过列表的实现实际上不能像JDK的无锁实现那样扩展，但是仅仅针对高争用（50％插入，50％删除和0％查找）…… Fraser哈里斯根本没有testing; Fraser和Harris只testing了75％的查找，12.5％的插入和12.5％的删除（在大约500K元素的跳过列表中）。 Herlihy等人的简单实现 在接受testing（70％查询，20％插入，10％删除）的低争用情况下，它也接近JDK的无锁解决scheme。 实际上，当他们将跳过列表放大到足够大时，他们实际上击败了无锁解决scheme，即从200K到2M个元素，从而使任何锁的争用概率变得微不足道。 如果Herlihy等人会这么好。 已经结束了Pugh的certificate，并testing了他的实施，但是他们没有这样做。
编辑2：我发现了一个（2015年出版的）所有基准testing的妈妈：Gramoli的“比你想知道的同步更多。同步机制，测量并发algorithm同步的影响” ：这是一个与这个问题相关的摘录图像。
“Algo.4”是上述Brown等人的前身（2011年版本）。 （我不知道2014年版本有多好或多less）。 “Algo.26”是上面提到的Herlihy; 正如您所看到的，它会在更新时被丢弃，而在此处使用的Intel CPU比在原始纸张上的Sun CPU要糟糕得多。 “Algo.28”是来自JDK的ConcurrentSkipListMap; 与其他基于CAS的跳过列表实现相比，它的效果不如人们所希望的。 高竞争的获奖者是Crain等人描述的基于锁的algorithm（!!）“Algo.2”。 在“竞争友好的二叉search树”和“Algo.30”是来自“多对数数据结构 ”的“旋转跳过列表” 。 “Algo.29”是“无热点无阻塞跳过列表” 。 请注意，Gramoli是这三个赢家algorithm论文的共同作者。 “Algo.27”是Fraser跳过列表的C ++实现。
Gramoli的结论是，更容易搞砸一个基于CAS的并发树实现，而不是搞砸一个类似的跳过列表。 而根据这些数字，很难不同意。 他对这个事实的解释是：
devise无锁树的困难源于自动修改多个引用的困难。 跳过列表包括通过后继指针相互连接的塔，每个节点指向其下面的节点。 它们通常被认为与树相似，因为每个节点在后继塔和后面都有一个后继者，然而，主要的区别是向下的指针通常是不可变的，从而简化了节点的primefaces修改。 这种区别可能就是为什么跳过列表的性能优于竞争对手，如图[上图]所示。
布朗等人最近的工作重点关注了这个难题。 他们有一个完整的（2013年）论文“构build非阻塞数据结构的实用原语” ，构build多loggingLL / SC复合“原语”，它们被称为LLX / SCX，它们自己使用（机器级）CAS来实现。 Brown等人 在2014年（但不是在2011年）并发树实现中使用了这个LLX / SCX构build块。
我认为在这里也可以总结一下“不热点”/“争用友好型”跳过列表的基本概念。 它从宽松的RB树（以及类似的混乱的数据结构）中增加了一个基本的想法：塔插入后不再立即build立，而是延迟到争用较less时为止。 相反，删除一座高塔会引起很多争论， 早在Pugh的1990年同时跳过列表文件中就已经观察到了这一点，这就是为什么Pugh在删除时引入了指针反转的原因（维基百科跳过列表的页面仍然没有提到今天的消息）。 CF跳过清单进一步推迟了删除高层塔楼的时间。 CF跳过列表中的这两种延迟操作都是由一个基于（CAS的）独立垃圾回收器的线程来执行的，它的作者称之为“适配线程”。
同步代码（包括所有testing的algorithm）可在https://github.com/gramoli/synchrobench上find 。 最新的布朗等人。 实现（不包括在上面）可在http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java有没有人有一个32 +核心机器可用？ J / K我的观点是你可以自己来运行。
此外，除了给出的答案（易于实施结合平衡树相当的performance）。 我发现执行顺序遍历（向前和向后）要简单得多，因为跳过列表在其实现中有效地具有链接列表。
在实践中，我发现我的项目中的B-tree性能比跳过列表要好。 跳过列表似乎更容易理解，但实现B树并不难。
我知道的一个好处是，一些聪明的人已经研究出如何实现一个只使用primefaces操作的无锁并发跳过列表。 例如，Java 6包含ConcurrentSkipListMap类，如果你疯了，你可以阅读它的源代码。
但是，编写一个并发的B-树变体也不难 – 如果你先行分裂和合并节点“以防万一”，那么你就不需要担心死锁，并且一次只需要locking树的两个级别。 同步开销会稍微高一些，但是B-tree可能会更快。
从你引用的维基百科文章：
Θ（n）操作迫使我们以升序访问每个节点（例如打印整个列表），以最佳方式为跳过列表的级别结构执行幕后去随机化提供了机会，将跳过列表带到O（log n）search时间。 […]我们最近没有进行[任何这样的]Θ（n）操作的跳过列表不提供与更传统的平衡树数据结构相同的绝对最差情况性能保证 ，因为它总是可能的（尽pipe概率很低）用于构build跳过列表的投币将产生非常均衡的结构
编辑：所以这是一个权衡：跳过列表使用较less的内存风险，他们可能退化成一个不平衡的树。
跳过列表是使用列表实现的。
无锁解决scheme存在单和双链表 – 但是没有无锁解决scheme，直接使用CAS仅用于任何O（logn）数据结构。
但是，您可以使用基于CAS的列表创build跳过列表。
（请注意，使用CAS创build的MCAS允许使用MCAS创build任意数据结构和概念validation红黑树）。
所以，他们是奇怪的，他们变得非常有用:-)
跳过列表具有locking剥离的优点。 但是，短时间取决于新节点的层次是如何决定的。 通常这是使用Random（）完成的。 在56000字的字典中，跳过列表花费的时间比显示树多，并且树比哈希表占用更多时间。 前两个不能匹配散列表的运行时间。 而且，哈希表的数组也可以同时被locking去除。
跳过列表和类似的有序列表用于需要参考的地点。 例如：在应用程序中的下一个date之前查找航class。
内存二进制searchsplay树是伟大的，更频繁使用。
跳过列表VS显示树与散列表运行时字典查找操作
