algorithm - 跳过列表与二叉搜索树

Question

我最近遇到了一种称为跳过列表的数据结构。它似乎与二叉搜索树具有非常相似的行为。

为什么要在二叉搜索树上使用跳过列表？

Answer 1

跳过列表更适合并发访问/修改。Herb Sutter 写了一篇关于并发环境中的数据结构的文章。它有更深入的信息。

二叉搜索树最常用的实现是红黑树。修改树时会出现并发问题，它通常需要重新平衡。重新平衡操作会影响树的大部分，这将需要在许多树节点上使用互斥锁。将节点插入跳过列表更加本地化，​​只有直接链接到受影响节点的节点需要被锁定。

Jon Harrops 评论的更新

我阅读了 Fraser 和 Harris 的最新论文Concurrent programming without locks。如果您对无锁数据结构感兴趣，这真是个好东西。这篇论文的重点是事务性内存和一个理论操作多字比较和交换 MCAS。这两者都是在软件中模拟的，因为还没有硬件支持它们。我对他们能够在软件中构建 MCAS 印象深刻。

我没有发现事务内存的东西特别引人注目，因为它需要垃圾收集器。软件事务内存也受到性能问题的困扰。但是，如果硬件事务内存变得普遍，我会非常兴奋。最后，它仍在研究中，在未来十年左右不会用于生产代码。

在 8.2 节中，他们比较了几种并发树实现的性能。我将总结他们的发现。下载 pdf 是值得的，因为它在第 50、53 和 54 页上有一些非常有用的图表。

• 锁定跳过列表非常快。它们随着并发访问的数量而扩展得非常好。这就是使跳过列表特别的原因，其他基于锁的数据结构往往在压力下发声。
• 无锁跳过列表始终比锁定跳过列表快，但只是勉强。
• 事务跳过列表始终比锁定和非锁定版本慢 2-3 倍。
• 锁定红黑树在并发访问下呱呱叫。它们的性能随着每个新的并发用户而线性下降。在两种已知的锁定红黑树实现中，一种在树重新平衡期间本质上具有全局锁。另一个使用花哨（和复杂）的锁升级，但仍然没有明显优于全局锁版本。
• 不存在无锁红黑树（不再正确，请参阅更新）。
• 事务性红黑树与事务性跳过列表相当。这是非常令人惊讶和非常有希望的。事务性内存，虽然更容易编写，但速度较慢。它可以像在非并发版本上快速搜索和替换一样简单。

---

更新
这里是关于无锁树的论文：Lock-Free Red-Black Trees Using CAS。
我没有深入研究它，但从表面上看，它似乎很牢固。

Answer 2

首先，您无法公平地将随机数据结构与提供最坏情况保证的数据结构进行比较。

跳过列表等效于随机平衡二叉搜索树 (RBST)，在 Dean 和 Jones 的“探索跳过列表和二叉搜索树之间的对偶性”中进行了更详细的解释。

反过来，你也可以有确定性的跳过列表来保证最坏情况下的性能，参见。门罗等人。

与上面的某些说法相反，您可以实现在并发编程中运行良好的二叉搜索树 (BST)。以并发为中心的 BST 的一个潜在问题是，您无法像从红黑 (RB) 树中那样轻松获得相同的平衡保证。（但是“标准”，即随机的，跳过列表也不能给你这些保证。）在始终保持平衡和良好（且易于编程）的并发访问之间进行权衡，因此通常使用宽松的 RB 树当需要良好的并发性时。放松包括不立即重新平衡树。对于有点过时的（1998 年）调查，请参阅 Hanke 的“并发红黑树算法的性能” [ps.gz]。

对这些最近的改进之一是所谓的彩色树（基本上你有一些权重，黑色为 1，红色为 0，但你也允许介于两者之间的值）。彩色树在跳过列表中的表现如何？让我们看看布朗等人是什么。“A General Technique for Non-blocking Trees”（2014）不得不说：

我们的算法有 128 个线程，比 Java 的非阻塞跳过列表（Bronson 等人的基于锁的 AVL 树）高出 13% 到 156%。63% 到 224%，以及使用软件事务内存 (STM) 13 到 134 次的 RBT

编辑添加：Pugh 的基于锁的跳过列表，在 Fraser 和 Harris (2007) “无锁并发编程”中进行了基准测试，接近他们自己的无锁版本（这里的最佳答案中充分强调了这一点），还针对良好的并发操作进行了调整，参见。Pugh 的“跳过列表的并发维护”，虽然方式相当温和。尽管如此，一篇较新的/2009 年论文“A Simple Optimistic skip-list Algorithm”Herlihy 等人提出了一种据称更简单（比 Pugh 的）基于锁的并发跳过列表实现，批评 Pugh 没有为他们提供足够令人信服的正确性证明。撇开这个（也许太迂腐的）疑虑不谈，Herlihy 等人。表明他们更简单的基于锁的跳过列表实现实际上无法像 JDK 的无锁实现一样扩展，但仅适用于高争用（50% 插入、50% 删除和 0% 查找）......弗雷泽哈里斯根本没有测试；Fraser 和 Harris 仅测试了 75% 的查找、12.5% 的插入和 12.5% 的删除（在具有约 500K 元素的跳过列表上）。Herlihy 等人的更简单的实现。在他们测试的低争用情况下（70% 查找、20% 插入、10% 删除），也接近 JDK 的无锁解决方案；当他们使他们的跳过列表足够大时，他们实际上击败了这种情况下的无锁解决方案，即从 200K 到 2M 元素，因此任何锁的争用概率变得可以忽略不计。如果 Herlihy 等人会很好。他们已经克服了对 Pugh 证明的困扰，并测试了他的实现，但可惜他们没有这样做。

EDIT2：我发现了所有基准的（2015 年出版）母线：Gramoli 的“比你想知道的更多关于同步。同步台，测量同步对并发算法的影响”：这是与这个问题相关的摘录图像。

“Algo.4”是上述 Brown 等人的前身（旧版本，2011 年版本）。（我不知道 2014 版本好坏了多少）。“Algo.26”是上面提到的 Herlihy；正如您所看到的，它在更新时被丢弃了，而且这里使用的 Intel CPU 比原始论文中的 Sun CPU 更糟糕。“Algo.28”是来自 JDK 的 ConcurrentSkipListMap；与其他基于 CAS 的跳过列表实现相比，它的表现不如人们希望的那么好。竞争激烈的获胜者是“Algo.2”，一种由 Crain 等人描述的基于锁的算法 (!!)。在"A Contention-Friendly Binary Search Tree"和 "Algo.30" 中是 "rotating skiplist" 来自"Logarithmic data structures for multicores"。". 请注意，Gramoli 是所有这三篇获胜者算法论文的合著者。“Algo.27”是弗雷泽跳过列表的 C++ 实现。

Gramoli 的结论是，搞砸基于 CAS 的并发树实现比搞砸类似的跳过列表要容易得多。根据这些数字，很难不同意。他对这个事实的解释是：

设计无锁树的困难源于原子地修改多个引用的困难。跳过列表由通过后继指针相互链接的塔组成，其中每个节点都指向紧接在其下方的节点。它们通常被认为类似于树，因为每个节点在后继塔及其下方都有一个后继者，但是，主要区别是向下指针通常是不可变的，因此简化了节点的原子修改。这种区别可能是跳过列表在激烈争用下优于树的原因，如图 [上图] 所示。

克服这一困难是 Brown 等人最近工作的一个关键问题。他们有一篇完全独立的（2013 年）论文“Pragmatic Primitives for Non-blocking Data Structures” ，关于构建多记录 LL/SC 复合“原语”，他们称之为 LLX/SCX，他们自己使用（机器级）CAS 实现。布朗等人。在他们的 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 我的意思是你可以自己运行这些。

Answer 3

此外，除了给出的答案（易于实施以及与平衡树相当的性能）。我发现实现按顺序遍历（向前和向后）要简单得多，因为跳过列表在其实现中实际上有一个链表。

Answer 4

在实践中，我发现我的项目中的 B-tree 性能比跳过列表更好。跳过列表似乎更容易理解，但实现 B 树并不难。

我知道的一个优点是一些聪明的人已经研究出如何实现一个只使用原子操作的无锁并发跳过列表。例如，Java 6 包含 ConcurrentSkipListMap 类，如果你疯了，你可以阅读它的源代码。

但是编写并发 B-tree 变体也不是太难——我见过其他人做过——如果你在沿着树走的时候“以防万一”抢先拆分和合并节点，那么你就不必担心死锁，并且一次只需要在树的两个级别上持有一个锁。同步开销会更高一些，但 B-tree 可能更快。

Answer 5

从您引用的维基百科文章中：

Θ(n) 操作，它迫使我们以升序访问每个节点（例如打印整个列表），提供了以最佳方式对跳过列表的级别结构执行幕后去随机化的机会，将跳过列表带到 O(log n) 搜索时间。[...] 一个跳过列表，我们最近没有对其执行[任何这样的] Θ(n) 操作，它不能提供与更传统的平衡树数据结构相同的绝对最坏情况性能保证，因为它总是可能的（尽管概率非常低）用于构建跳过列表的硬币翻转将产生一个不平衡的结构

编辑：所以这是一个权衡：跳过列表使用更少的内存，但它们可能会退化为不平衡的树。

Answer 6

跳过列表是使用列表实现的。

单链表和双链表都存在无锁解决方案——但没有任何 O(logn) 数据结构直接使用 CAS 的无锁解决方案。

但是，您可以使用基于 CAS 的列表来创建跳过列表。

（请注意，使用 CAS 创建的 MCAS 允许任意数据结构，并且使用 MCAS 创建了概念证明红黑树）。

因此，尽管它们很奇怪，但事实证明它们非常有用:-)

Answer 7

跳过列表确实具有锁剥离的优势。但是，runt time 取决于如何决定新节点的级别。通常这是使用 Random() 完成的。在 56000 个单词的字典中，skip list 比 splay tree 花费更多时间，而 tree 比 hash table 花费更多时间。前两个无法匹配哈希表的运行时。此外，哈希表的数组也可以以并发的方式进行锁剥离。

当需要参考位置时，使用跳过列表和类似的有序列表。例如：查找应用程序中某个日期的下一个和之前的航班。

内存二叉搜索展开树非常好，也更常用。

字典查找操作上的跳过列表与展开树与哈希表运行时