Lock-Free Data Structures using STMs in Haskell
SPJ and the rest of the crowd have a new paper they’ve put together for FLOPS’06: Lock-Free Data Structures using STMs in Haskell. In it, they present two implementations of ArrayBlockingQueue, a data structure taken from JSR-166.
One uses traditional explicit locking (mutexes and semaphores), the other uses Software Transactional Memory (see my earlier post). Otherwise, the two implementations have been made as similar as possible.
Due to the immaturity and lack of optimization in the parallel Haskell runtime and the STM library itself, the results are highly preliminary… but they are very interesting nonetheless.
Traditional locking beat the STM approach on a single processor, but as a soon as another processor was introduced, STM became significantly faster and remained consistently so as more CPUs were introduced.
The STM version was also significantly simpler, and unlike the traditional locking version, would automatically roll back changes if an exception occurred. Adding similar error-handling code to the locking version would have introduced additional overhead.
Annoying: the paper is currently available only in Microsoft Word format.
(Hat Tip: Lambda the Ultimate)