论文标题
并发大小
Concurrent Size
论文作者
论文摘要
数据结构的大小（即，其中元素的数量）是数据集的广泛使用属性。但是，对于并发程序，有效地获得正确的尺寸是非平凡的。实际上，文献没有提供同时数据集的正确（可线化）大小的机制，而无需求助于效率低下的解决方案，例如，在所有更新和大小操作中都拿出数据结构的完整快照来计算元素，或者在所有更新和大小操作中获取一个全局锁定。本文介绍了一种方法，用于在性能开销相对较低的集合和词典中添加同时线性化的尺寸操作。从理论上讲，所提出的大小操作是不含等候的，渐近复杂性在线程数（独立于数据结构大小）中是线性的。实际上，我们通过将大小添加到Java $中的各种并发数据结构 - 跳过列表，一个哈希表和一棵树中来评估性能开销。与现有的快照选择相比，所提出的可线尺寸操作通过数量级执行的速度更快，而在原始数据结构的操作中会产生$ 1 \％-20 \％$的吞吐量损失。
The size of a data structure (i.e., the number of elements in it) is a widely used property of a data set. However, for concurrent programs, obtaining a correct size efficiently is non-trivial. In fact, the literature does not offer a mechanism to obtain a correct (linearizable) size of a concurrent data set without resorting to inefficient solutions, such as taking a full snapshot of the data structure to count the elements, or acquiring one global lock in all update and size operations. This paper presents a methodology for adding a concurrent linearizable size operation to sets and dictionaries with a relatively low performance overhead. Theoretically, the proposed size operation is wait-free with asymptotic complexity linear in the number of threads (independently of data-structure size). Practically, we evaluated the performance overhead by adding size to various concurrent data structures in Java$-$a skip list, a hash table and a tree. The proposed linearizable size operation executes faster by orders of magnitude compared to the existing option of taking a snapshot, while incurring a throughput loss of $1\%-20\%$ on the original data structure's operations.
