Home

Lock-Free Data Structures using STMs in Haskell

Lock -Free Data Structures using STMs in Haskell. Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, and Satnam Singh. Submitted to FLOPS'06.

This paper explores the feasibility of re-expressing concurrent algorithms with explicit locks in terms of lock free code written using Haskell's implementation of Software Transactional Memory (STM). Preliminary experimental results are presented which show that for multi-processor systems the simpler lock free implementations offer competitive or superior performance when compared to their corresponding the lock based implementations.

The ArrayBlockingQueue class from JSR-166 is the basis for this experiment. A selection of representative methods from the three interfaces supported by this class is reimplemented in Haskell. Two implementations are provided: one using mutexes and semaphores from the IO monad and one based on STMs.

The performance of the two versions is compared and discussed.

By Ehud Lamm at 2005-11-30 20:55 | Parallel/Distributed | Software Engineering | other blogs | 15545 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Why is this not more wide spread?

It does seem that STM and the recent work on multiprocessor GHC has more or less "solved" the problem of shared state concurrency -- performance-wise and ease-wise. I've only seen the technique used in Haskell, but I'll seen (and coded) enough that I am a true believer. Not having to worry about exceptions, etc whilst writing concurrent code is an amazing experience -- after all the fun with mutexes in C++... The paper mentions the SXM library for C#, and I remember seeing it around a while back (at least half a year); why is this technique not used more often? Whilst most other languages cannot make the same promises of type safety, it would still be a much better abstraction than mutexes... I believe the Mnersia (is that how it's spelt?) database take a similar approach?

By genneth at Thu, 2005-12-01 00:20 | login or register to post comments

remaining challenges

I believe this is a question of time. Quoting from this article:

"That being said, though, challenges remain, Harris said: "working out all of implications of integrating atomic blocks in a language � how they interact with the garbage collector, how they interact with exception handling, how they interact with I/O devices. There are a lot of challenging problems in formulating what a complete, finished design would be. There are lot of these details that would need to be thought through before it's ready to use in a product," Harris stipulated."

On the desktop, multi-core processors are going to mainstream over the next 2-3 years and there is also an ongoing gradual shift from C/C++ to managed code i.e. C# and Java. So it makes a lot of sense to simplify concurrent programming because the developers of these desktop applications do not (typically) have all the skills for getting shared state concurrency right, and it's complex even with the right skills. Some steps have already been taken, see e.g. the new concurrency package in J2SE 5.0. In C#, I guess the SXM library may become part of the core language at some point if they can overcome all those "challenging problems" that separate a proof of concept from a fully thought out, robust implementation. In the meantime, we can have fun with STM in Haskell.

By Alain Rogister at Thu, 2005-12-01 11:31 | login or register to post comments

Re: C#

Since Peyton-Jones is at MS, I think all this kind of stuff will find its way into C#/.Net, hopefully sooner rather than later.

By raould at Mon, 2006-03-20 19:36 | login or register to post comments

Because...

the thesis that it's based on, which I must always cite when STM comes up as it is beautiful, was completed in 2004. The paper is Practical Lock-Freedom. (I came across it (and posted about it on LtU) not long before it was applied in Haskell; an extremely pleasant surprise.)

By Derek Elkins at Thu, 2005-12-01 16:22 | login or register to post comments

PDF, please

Can anyone generate pdf of this doc? It looks like crap in the ancient open office I have on my desktop.

By johan at Fri, 2005-12-02 18:11 | login or register to post comments

PDF

PDF

By Anton van Straaten at Fri, 2005-12-02 21:49 | login or register to post comments

thanks

n/t

By johan at Fri, 2005-12-02 23:08 | login or register to post comments

Confused

orElse is described as a sequencing operator, so that

a orElse b, will wait for a to run to completion or retry, returning the result of a or running b.

Transactional isolation allows us to start both a and b simulaneously, and immediately commit and return b if a does a retry.

What confuses me is that the implementation of pollTimeoutSTM appears to imply that orElse will take the result of whichever a or b finishes first, which is not how it was presented earlier.

Either that, or the only way I can read their implemenation is that it will always wait for the timeout, and then return Nothing. (as it doesn't call retry, but rather returns the empty Maybe value).

By johan at Mon, 2005-12-05 19:12 | login or register to post comments

readTChan

I guess that readTChan does an internal retry if there is nothing to be read in the channel.

But there is something in section 2 that I do not understand:


As an example, here is a procedure that atomically increments a TVar: 

 incT :: TVar Int -> IO () 
 incT v = atomically (do x <- readTVar v 
           writeTVar v (x+1))

The implementation guarantees that the body of a call to atomically runs atomically with respect to every other thread; for example, there is no possibility that another thread can read v between the readTVar and writeTVar of incT.

Let's call the code within atomically(..) "transaction a". I was under the impression that a different transaction "b" might well read v, and that b will even be successfully committed if it ends before "a" executes writeTVar v.
If, on the other end, "a" commits first, "b" will of course be retried.
Am I wrong?

By Wolfgang Meyer at Sun, 2006-03-19 21:01 | login or register to post comments