Comparing concurrent linked-list implementations in Haskell

Here’s a paper I wrote recently with Martin Sulzmann and Edmund Lam: Comparing the performance of concurrent linked-list implementations in Haskell (to be presented at DAMP’09).  The basic idea is to analyse the performance and scaling characteristics of the various concurrency synchronisation methods available in GHC: STM, MVars, and IORef with atomicModifyIORef, by using each of these to implement a concurrent linked-list abstraction.

The bottom line is that we found two orders of magnitude differences between the slowest (STM), and the fastest (IORef + atomicModifyIORef).  It’s not too surprising that STM is slow here, since each transaction is linear in the size of the data structure – this is a well-known problem that is the subject of a number of other research papers.  However, we did find we could make an STM-based solution that runs nearly as fast as the IORef version by adding a single operation: readTVarIO, which has the same behaviour as (atomically readTVar), but doesn’t have the overhead of setting up and committing a transaction.  Using a rewrite rule this could even be automated.

However, a major problem with all of the algorithms in our paper, except for the naive STM implementation, is that they don’t compose.  That’s what STM was for in the first place.  Fortunately there’s a way to have the best of both worlds: fast scalable concurrent data structures writen by Clever People(TM) using compare-and-swap, with the full composability of STM operations.  The idea is called transactional boosting and is due to Maurice Herlihy and Eric Koskinen. In some sense this is admitting defeat: we can’t get good performance from STM, so we’ll work around it. On the other hand, it seems unlikely that STM will ever achieve the performance of hand-tuned concurrent data structures, and after all, this technique just follows a long tradition in high-level programming languages of letting you embed low-level bits when you really need performance.

To implement this in GHC all we would need is a way to register actions to perform at transaction commit or abort time, which is something we’ve been meaning to implement for some time anyway.  Maybe there’s a budding GHC hacker out there who would like to take this on?

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s