跳过列表与二进制搜索树

Question

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

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

Answer 1

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

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

Jon Harrops的评论更新

我阅读了弗雷泽和哈里斯的最新论文" 没有锁的并发编程".如果您对无锁数据结构感兴趣,那真是好东西.本文重点介绍了事务记忆和理论操作多字比较和交换MCAS.这两个都是在软件中模拟的,因为还没有硬件支持它们.我对他们能够在软件中构建MCAS印象深刻.

我没有发现事务性内存的东西特别引人注目,因为它需要垃圾收集器.此外软件事务内存存在着严重的性能问题.但是,如果硬件事务内存变得普遍,我会非常兴奋.最后,它仍在研究中,并且在未来十年左右的时间里不会用于生产代码.

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

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

更新
这里有关于无锁树的文章:使用CAS的无锁红黑树.
我没有深入研究过,但从表面上看它似乎很坚固.

Answer 2

首先,您无法公平地比较随机数据结构与提供最坏情况保证的数据结构.

跳过列表相当于随机平衡的二叉搜索树(RBST),在Dean和Jones的"探索跳过列表和二进制搜索树之间的对偶性"中有更详细的解释.

反过来说,你也可以使用确定性的跳过列表来保证最坏情况下的性能,参见 Munro等.

与上面的一些说法相反,您可以实现二进制搜索树(BST),这些树在并发编程中运行良好.以并发为重点的BST的一个潜在问题是,你不能轻易得到与红黑(RB)树一样的平衡保证.(但是"标准",即随机,跳过列表也没有给你这些保证.)在任何时候保持平衡和良好(并且易于编程)的并发访问之间存在权衡,因此通常使用宽松的 RB树当需要良好的并发性时.放松包括不立即重新平衡树.对于有点过时(1998)的调查,请参阅Hanke的''并行红黑树算法的表现'' [ps.gz].

最近对这些进行改进的一个就是所谓的彩色树(基本上你有一些重量,黑色为1,红色为零,但你也允许它们之间的值).一个彩色树如何对抗跳过列表？让我们看看布朗等人."无阻树的一般技术"(2014)必须说:

使用128个线程,我们的算法优于Java的非阻塞跳过列表13%到156%,Bronson等人的基于锁的AVL树.63%到224%,RBT使用软件事务存储器(STM)13到134次

编辑添加:Pugh的基于锁定的跳过列表,在Fraser和Harris(2007)"无锁定的并发编程"中进行了基准测试,接近他们自己的无锁版本(这里的答案非常坚持),也被调整为良好的并发操作,参见 Pugh的"同时维护跳过列表",虽然方式相当温和.然而,一篇更新的2009年论文"简单乐观的跳过列表算法"通过Herlihy等人提出了一个假定的(比Pugh的)基于锁定的并发跳过列表的实现,批评Pugh没有提供足够令人信服的正确性证明.撇开这个(可能太迂腐)的质疑,Herlihy等人.表明他们更简单的基于锁定的跳过列表实现实际上无法扩展以及JDK的无锁实现,但仅限于高争用(50%插入,50%删除和0%查找)...哪个Fraser哈里斯根本没有考试; Fraser和Harris仅测试了75%的查找,12.5%的插入和12.5%的删除(在跳过列表中有~500K元素).Herlihy等人的简单实现.在他们测试的低争用情况下,也接近JDK的无锁解决方案(70%查找,20%插入,10%删除); 当他们使跳过列表足够大时,他们实际上击败了这种情况下的无锁解决方案,即从200K到2M元素,这样任何锁争用的可能性都可以忽略不计.如果Herlihy等人的话会很好.他已经克服了Pugh的证据,并测试了他的实施,但唉他们没有这样做.

EDIT2:我发现了(2015年发布)所有基准测试的母亲:Gramoli的"比你想知道的更多同步.Synchrobench,测量同步对并发算法的影响":这是一个与这个问题相关的摘录图像.

"Algo.4"是上面提到的Brown等人的前身(旧版,2011版).(我不知道2014版本有多好或多差)."Algo.26"是上面提到的Herlihy; 正如你所看到的那样,它会在更新时被破坏,而在这里使用的英特尔CPU比原始论文中的太阳CPU更糟糕."Algo.28"是来自JDK的ConcurrentSkipListMap; 与其他基于CAS的跳过列表实现相比,它没有像人们希望的那样好.高争用的赢家是"Algo.2",一种基于锁的算法(!!),由Crain等人描述.在"A Contention-Friendly Binary Search Tree"中,"Algo.30"是"Multicores的对数数据结构 "中的"旋转跳转列表".".请注意,Gramoli是所有这三个获胜者算法论文的共同作者."Algo.27"是Fraser跳过列表的C++实现.

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

设计无锁树的困难源于难以原子地修改多个引用.跳过列表由通过后继指针相互链接的塔组成,其中每个节点指向紧邻其下方的节点.它们通常被认为类似于树,因为每个节点在后继塔中具有后继,并且在其下方,但是,主要区别在于向下指针通常是不可变的,因此简化了节点的原子修改.这种区别可能就是为什么跳过列表在严重争用下表现优于树[如上图所示].

克服这一困难是布朗等人近期工作中的一个关键问题.他们有一个完全独立的(2013)论文"非阻塞数据结构的实用原语", 用于构建多记录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树性能已经比跳过列表更好.跳过列表似乎更容易理解,但实现B树并不是那么难.

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

但是编写一个并发的B树变种并不难 - 我已经看到它由其他人完成 - 如果你先行拆分并合并节点"以防万一"当你走在树上然后你就不必担心死锁,只需要一次锁定树的两个级别.同步开销会略高,但B树可能更快.

Answer 5

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

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

编辑:所以这是一个权衡:跳过列表使用更少的内存,冒着可能退化为不平衡树的风险.