Contribution in edited book
Thread-Safe Priority Queues in Haskell Based on Skiplists
Publication Details
Publisher: | Springer Berlin Heidelberg
|
Book title: | Trends in Functional Programming
|
Title of series: | Lecture Notes in Computer Science
|
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.