RefDoc
Haut

Faire une nouvelle recherche
Make a new search
Lancer la recherche


Titre du document / Document title

Lock-Free Dynamically Resizable Arrays

Auteur(s) / Author(s)

DECHEV Damian (1) ; PIRKELBAUER Peter (1) ; STROUSTRUP Bjarne (1) ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

(1) Texas A&M University, College Station, TX 77843-3112, ETATS-UNIS

Résumé / 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 (GAS) 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.

Revue / Journal Title

Lecture notes in computer science    ISSN  0302-9743 

Source / Source

Congrès
Principles of distributed systems :   ( 10th International conference, OPODIS 2006, Bordeaux, France, December 12-15, 2006 )  ( proceedings )
International Conference on Principles of Distributed Systems No10, Bordeaux , FRANCE (2006)
, vol. 4305, pp. 142-156[Note(s) : XIII-439 p., ] [Document : 15 p.] (27 ref.) ISBN 3-540-49990-3 ; 978-3-540-49990-9 ;  Illustration : Illustration ;

Langue / Language

Anglais

Editeur / Publisher

Springer, Berlin, ALLEMAGNE  (1973) (Revue)
Springer, Berlin, ALLEMAGNE  (Monographie)

Mots-clés anglais / English Keywords

Input output

;

Timed system

;

System core

;

Performance evaluation

;

Access time

;

Time management

;

Container

;

Database query

;

Cache memory

;

Random access

;

Storage management

;

Distributed system

;

Mots-clés français / French Keywords

Entrée sortie

;

Système temporisé

;

Noyau système

;

Evaluation performance

;

Temps accès

;

Gestion temps

;

Conteneur

;

Interrogation base donnée

;

Antémémoire

;

Accès aléatoire

;

Gestion mémoire

;

Système réparti

;

Mots-clés espagnols / Spanish Keywords

Entrada salida

;

Sistema temporizado

;

Núcleo sistema

;

Evaluación prestación

;

Tiempo acceso

;

Contenedor

;

Interrogación base datos

;

Antememoria

;

Acceso aleatorio

;

Gestión memoria

;

Sistema repartido

;

Localisation / Location

INIST-CNRS, Cote INIST : 16343, 35400017280612.0100

Nº notice refdoc (ud4) : 20015297



Faire une nouvelle recherche
Make a new search
Lancer la recherche
Bas