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?

Posted in Uncategorized | Leave a comment

Bootstrapping cabal-install

After installing GHC 6.10.1, you probably want to get cabal-install installed as quickly as possible, so you can grab all that Haskell library goodness from Hackage with the minimum of fuss.  Once the Haskell Platform is available, this will be much easier, but until then we have to bootstrap cabal-install using just Cabal.

After a release I find myself doing this on multiple machines, so today I made a little script to automate it, and I thought I’d share it.  Obviously it’s just a quick hack, only works with GHC 6.10.1, has no error-checking etc., but it does work on both Windows and Unix.  Enjoy!

Update: Duncan Coutts pointed out to me that there’s a Windows cabal.exe binary available.


#!/bin/sh

set -e

for i in $TMPDIR /tmp c:/temp; do
  if test -d $i; then
    dir=$i
    break
  fi
  dir=$HOME
done

cd $dir
wget http://hackage.haskell.org/packages/archive/zlib/0.5.0.0/zlib-0.5.0.0.tar.gz
tar xzf zlib-0.5.0.0.tar.gz
cd zlib-0.5.0.0
ghc --make Setup
./Setup configure --user
./Setup build
./Setup register --inplace --user

cd $dir
wget http://hackage.haskell.org/packages/archive/HTTP/3001.1.4/HTTP-3001.1.4.tar.gz
tar xzf HTTP-3001.1.4.tar.gz
cd HTTP-3001.1.4
ghc --make Setup
./Setup configure --user
./Setup build
./Setup register --inplace --user

cd $dir
wget http://hackage.haskell.org/packages/archive/cabal-install/0.6.0/cabal-install-0.6.0.tar.gz
tar xzf cabal-install-0.6.0.tar.gz
cd cabal-install-0.6.0
ghc --make Setup
./Setup configure --user
./Setup build

# Don't need these libs any more...
ghc-pkg unregister zlib-0.5.0.0
ghc-pkg unregister HTTP-3001.1.4

# Now use cabal-install to install itself and its dependencies
./dist/build/cabal/cabal update
./dist/build/cabal/cabal install cabal-install

# Clean up...
cd $dir
rm -rf zlib-0.5.0.0*
rm -rf HTTP-3001.1.4*
rm -rf cabal-install-0.6.0*

echo "ALL DONE!"

Posted in Uncategorized | 7 Comments

GHC 6.10.1 is out!

It seems appropriate to initialise this blog with a release announcement, so here it is: the GHC developers commend the new GHC 6.10.1 release to the community!

There’s plenty of juicy stuff in this release, here’s the headlines:

  • New language Features
  • Type families have been completely re-implemented
  • Now comes with Haddock 2, which supports all GHC extensions
  • Parallel garbage collection
  • Base provides extensible exceptions
  • The GHC API is easier to use
  • External core (output only) now works again
  • Data Parallel Haskell (DPH) comes as part of GHC

Get all the details in the full release notes.

What’s more, this release has undergone more testing and polishing than ever before, so we hope this will be one of the highest-quality GHC releases ever.  Our test suite has over 2200 individual test programs, each run 6 ways as part of our automated nightly builds, and at release time we had zero unexpected failures (that is, all known bugs are logged in the bug tracker).  The Haskell Platform team have also been testing GHC 6.10.1 pre-releases against all of the packages on Hackage, to ensure that we can make this transition as smooth as possible.

You might notice some other improvements, such as parallel performance: there is ongoing work to analyse and improve the performance of parallel code, and some of that work made it into into 6.10.1 (but there’s a lot more to come, some of which can be found in the HEAD).

We have a new parallel garbage collector, which should probably be considered a “technology preview”: you get it by default when enabling multi-core execution with e.g. +RTS -N4, but keep an eye on the GC time with +RTS -s.  If you find that parallel GC isn’t helping, or is even making things worse, then tell us about it, and disable the parallel gc with -g1.

Enjoy, and send us your bugs and feedback!

Posted in Announcements | Leave a comment