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 |
DOI-Link der Erstveröffentlichung: |
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.
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.
