A Comparison of Lock-based and Lock-free Taskpool Implementations in Haskell

摘要

Today, synchronization of shared data structures in multithreaded software is mostly implemented using locks, which leads to difficult to understand and error-prone programs. Software Transactional Memory allows lock-free concurrent programming by handling the synchronization of shared variables implicitly. We show how to implement different instances of the widely-used taskpool pattern (global and private taskpools with and without task stealing) using both lock-based and lock-free synchronization mechanisms in the functional programming language Haskell. We examine their performance using two synthetic algorithms and LU decomposition and report our observations about parallel performance and the complexity of the implementation. Our results show that lock-free taskpools are not only on par with lock-based implementations concerning parallel performance but are also easier to comprehend and develop.