Name
Abstract | ||
|---|---|---|
We present a first lock-free design and implementation of a dynamically resizable array (vector). The most extensively used container in the C++ Standard Template Library (STL) is vector, offering a combination of dynamic memory management and constant-time random access. Our approach is based on a single 32-bit word atomic compare-and-swap (CAS) instruction. It provides a linearizable and highly parallelizable STL-like interface, lock-free memory allocation and management, and fast execution. Our current implementation is designed to be most efficient on multi-core architectures. Experiments on a dual-core Intel processor with shared L2 cache indicate that our lock-free vector outperforms its lock-based STL counterpart and the latest concurrent vector implementation provided by Intel by a large factor. The performance evaluation on a quad dual-core AMD system with non-shared L2 cache demonstrated timing results comparable to the best available lock-based techniques. The presented design implements the most common STL vector's interfaces, namely random access read and write, tail insertion and deletion, pre-allocation of memory, and query of the container's size. Using the current implementation, a user has to avoid one particular ABA problem. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11945529_11 | OPODIS'06 Proceedings of the 10th international conference on Principles of Distributed Systems |
Keywords | Field | DocType |
current implementation,L2 cache,common STL vector,latest concurrent vector implementation,lock-free vector,dynamic memory management,lock-based STL counterpart,lock-free design,lock-free memory allocation,available lock-based technique | Access time,Lock (computer science),Computer science,CPU cache,Non-blocking algorithm,Parallel computing,ABA problem,Memory management,Standard Template Library,Random access | Conference |
Volume | ISSN | ISBN |
4305 | 0302-9743 | 3-540-49990-3 |
Citations | PageRank | References |
1 | 0.35 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Damian Dechev | 1 | 81 | 22.87 |
| Peter Pirkelbauer | 2 | 52 | 9.37 |
| Bjarne Stroustrup | 3 | 362 | 96.58 |