Designing an efficient concurrent data structure is an important challenge that is not easy to meet. Intuitively, efficiency of an implementation is defined, in the first place, by its ability to process applied operations in parallel, without using unnecessary synchronization. As we show in this paper, even for a data structure as simple as a linked list used to implement the set type, the most efficient algorithms known so far are not concurrency-optimal: they may reject correct concurrent schedules. We propose a new algorithm for the list-based set based on a value-aware try-lock that we show to achieve optimal concurrency: it only rejects concurrent schedules that violate correctness of the implemented set type. We show empirically that reaching optimality does not induce a significant overhead. In fact, our implementation of the concurrency-optimal algorithm outperforms both the Lazy Linked List and the Harris-Michael state-of-the-art algorithms.
翻译：设计高效的并行数据结构是一项难于应对的重要难题。 直观地说,执行的效率首先取决于其平行处理应用操作的能力,而不必使用不必要的同步。 正如我们在本文件中所示,即使对于一个简单的数据结构,即使对于一个用于执行设定类型的链接列表如此简单的数据结构,迄今为止已知的最有效算法也并非货币最佳:它们可能拒绝正确的同时时间表。 我们为基于列表的套件提出了一个新的算法,这个套件是以我们所显示的价值认知试锁为基础,以实现最佳的共通货币:它只是拒绝违反已执行的设定类型正确性的同时列表。我们从经验上表明,达到最佳性不会带来重大间接费用。事实上,我们采用通货通货通配算法比拉兹链接列表和Harris-Michael state- of the artal 算法都好。
相关内容
微信扫码咨询专知VIP会员