Beitrag in einem Sammelband
Thread-Safe Priority Queues in Haskell Based on Skiplists
Details zur Publikation
Autor(inn)en: | Lesniak, M. |
Herausgeber: | Peña R, Page R |
Verlag: | Springer Berlin Heidelberg |
Verlagsort / Veröffentlichungsort: | Madrid |
Publikationsjahr: | 2012 |
Seitenbereich: | 114-129 |
Buchtitel: | Trends in Functional Programming |
Titel der Buchreihe: | Lecture Notes in Computer Science |
Jahrgang/Band : | 7193 |
ISBN: | 978-3-642-32036-1 |
DOI-Link der Erstveröffentlichung: |
Zusammenfassung, 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.
