Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Concurrent Tries with Efficient Non-Blocking Snapshots
 
research article

Concurrent Tries with Efficient Non-Blocking Snapshots

Prokopec, Aleksandar  
•
Bronson, Nathan G.
•
Bagwell, Phil
Show more
2012
ACM SIGPLAN Notices

We describe a non-blocking concurrent hash trie based on shared-memory single-word compare-and-swap instructions. The hash trie supports standard mutable lock-free operations such as insertion, removal, lookup and their conditional variants. To ensure space-efficiency, removal operations compress the trie when necessary. We show how to implement an efficient lock-free snapshot operation for concurrent hash tries. The snapshot operation uses a single-word compare-and-swap and avoids copying the data structure eagerly. Snapshots are used to implement consistent iterators and a linearizable size retrieval. We compare concurrent hash trie performance with other concurrent data structures and evaluate the performance of the snapshot operation.

  • Details
  • Metrics
Type
research article
DOI
10.1145/2370036.2145836
Web of Science ID

WOS:000309350200015

Author(s)
Prokopec, Aleksandar  
Bronson, Nathan G.
Bagwell, Phil
Odersky, Martin  
Date Issued

2012

Publisher

Assoc Computing Machinery

Published in
ACM SIGPLAN Notices
Volume

47

Issue

8

Start page

151

End page

160

Subjects

Algorithms

•

hash trie

•

concurrent data structure

•

snapshot

•

non-blocking

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LAMP1  
Available on Infoscience
February 27, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/89679
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés