IEEE Transactions on Parallel and Distributed Systems · 2015 · 16 citations · 9 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureData StructuresOperating SystemsParallel Data StructuresSynchronization PrimitivesSynchronization OverheadSynchronization Overhead AnalysisSynchronization Overhead ReductionVector ProcessingVectorizationWait-free Data StructuresWait-free Programming
The vector is a fundamental data structure, which provides constant-time access to a dynamically-resizable range of elements. Currently, there exist no wait-free vectors. The only non-blocking version supports only a subset of the sequential vector API and exhibits significant synchronization overhead caused by supporting opposing operations. Since many applications operate in phases of execution, wherein each phase only a subset of operations are used, this overhead is unnecessary for the majority of the application. To address the limitations of the non-blocking version, we present a new design that is wait-free, supports more of the operations provided by the sequential vector, and provides alternative implementations of key operations. These alternatives allow the developer to balance the performance and functionality of the vector as requirements change throughout execution. Compared to the known non-blocking version and the concurrent vector found in Intel's TBB library, our design outperforms or provides comparable performance in the majority of tested scenarios. Over all tested scenarios, the presented design performs an average of 4.97 times more operations per second than the non-blocking vector and 1.54 more than the TBB vector. In a scenario designed to simulate the filling of a vector, performance improvement increases to 13.38 and 1.16 times. This work presents the first ABA-free non-blocking vector. Unlike the other non-blocking approach, all operations are wait-free and bounds-checked and elements are stored contiguously in memory.
9
A method for implementing lock-free shared-data structures
Greg Barnes · 1993 · 194 citations · Full text
A methodology for creating fast wait-free data structures
Alex Kogan, Erez Petrank · 2012 · 88 citations
David Detlefs, Paul Martin, Mark Moir et al. · 2001 · 78 citations