Comparing the performance of concurrent hash tables implemented in Haskell

This paper presents seven concurrent hash table implementations in Haskell, ranging from low-level synchronization mechanisms to high-level ones such as transactional memories. The hash tables were compared using different initial sizes, load factors, data types and hash functions. We also present a...

Full description

Saved in:
Bibliographic Details
Published in:Science of computer programming 2019-03, Vol.173, p.56-70
Main Authors: Duarte, Rodrigo Medeiros, Du Bois, André Rauber, Pilla, Maurício Lima, Cavalheiro, Gerson Geraldo H., Reiser, Renata Hax Sander
Format: Article
Language:English
Subjects:
Concurrent programming
Haskell
Software transactional memory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents seven concurrent hash table implementations in Haskell, ranging from low-level synchronization mechanisms to high-level ones such as transactional memories. The hash tables were compared using different initial sizes, load factors, data types and hash functions. We also present a case study on implementing a color palette algorithm using the hash tables. The result of the comparison between the algorithms shows that the implementation using the STM Haskell transactional memory library and fine-grain synchronization provides the best performance and good scalability, followed by the implementation using lock striping and MVars. •The paper describes seven concurrent hash table implementations in Haskell.•Different abstractions were used: MVars, compare and swap, and transactional memory.•Detailed performance comparison of the hash tables is presented.•STM Haskell with fine-grain synchronization shows the best performance in overall.
ISSN:0167-6423
1872-7964
DOI:10.1016/j.scico.2018.06.004