Contribution in edited book
Thread-Safe Priority Queues in Haskell Based on Skiplists



Publication Details
Authors:
Lesniak, M.
Editor:
Peña R, Page R
Publisher:
Springer Berlin Heidelberg
Place:
Madrid
Publication year:
2012
Pages range:
114-129
Book title:
Trends in Functional Programming
Title of series:
Lecture Notes in Computer Science
Volume number:
7193
ISBN:
978-3-642-32036-1

Abstract
Although thread-safe priority queues are fundamental building blocks for many parallel algorithms, there are currently no scalable implementations available in Haskell. An efficient structure to implement priority queues is the skiplist, which is a multi-level linked list with shortcuts. We developed three thread-safe skiplist variants, based on locks, software transactional memory, and atomic compare-and-swap, respectively. In our benchmarks, the lock-based and compare-and-swap variants scaled about equally well, while the transactional variant was by several orders of magnitude slower.


Research Areas


Last updated on 2019-25-07 at 13:20