Haskell concurrency using simple IORef?

1.4k views Asked by At

I've been asking a few questions about concurrency in Haskell, particular TVar, and I've had concerns about livelock with TVar.

Instead, I've proposed this solution.

(1) Wrap all shared data in the program in one data structure, and wrap that in an IORef. (2) Simply do any changes using atomicModifyIORef.

I believe this prevents both deadlocks and livelocks (whereas TVar only prevents the former). Also, because atomicModifyIORef simply links another thunk into a chain (which is a couple of pointer operations) this is not a bottl neck. All of the actual operations on the data can be done in parallel, as long as they do not mutually depend on each other. The Haskell runtime system will work this out.

I however feel like this is too simple. Are there any "gotchas" I've missed?

3

There are 3 answers

3
dented42 On

Well, it's not going to compose well. And serializing all of your shared memory modifications through a single IORef will mean that only one thread will be able to modify shared memory at a time, all you've really done is made a global lock. Yes it will work, but it will be slow and nowhere near as flexible as TVars or even MVars.

7
John L On

This design would probably be ok if the following are true:

  • reads will be much more prevalent than writes
  • a number of reads will be interspersed between writes
  • (possibly) writes will affect only a small portion of the global data structure

Of course, given those conditions, pretty much any concurrency system would be fine. Since you're concerned about livelock, I suspect you're dealing with more complicated access pattern. In which case, read on.

Your design appears to be guided by the following chain of reasoning:

  1. atomicModifyIORef is very cheap, because it just creates thunks

  2. because atomicModifyIORef is cheap, it's not going to cause thread contention

  3. Cheap data access + no contention = Concurrency FTW!

Here's the missing step in this reasoning: your IORef modifications only create thunks, and you have no control over where thunks are evaluated. If you can't control where the data is evaluated, you have no real parallelism.

Since you haven't yet presented the intended data access patterns this is speculation, however I expect that what will happen is that your repeated modifications to the data will build up a chain of thunks. Then at some point you'll read from the data and force an evaluation, causing all of those thunks to be evaluated sequentially in one thread. At this point, you may as well have written single-threaded code to begin with.

The way around this is to ensure that your data is evaluated (at least as far as you would like it to be) before it's written into the IORef. This is what the return parameter of atomicModifyIORef is for.

Consider these functions, meant to modify aVar :: IORef [Int]

doubleList1 :: [Int] -> ([Int],())
doubleList1 xs = (map (*2) xs, ())

doubleList2 :: [Int] -> ([Int], [Int])
doubleList2 xs = let ys = map (*2) xs in (ys,ys)

doubleList3 :: [Int] -> ([Int], Int)
doubleList3 xs = let ys = map (*2) xs in (ys, sum ys)

Here's what happens when you use these functions as arguments:

  1. !() <- atomicModifyIORef aVar doubleList1 - only a thunk is created, no data is evaluated. An unpleasant surprise for whichever thread reads from aVar next!

  2. !oList <- atomicModifyIORef aVar doubleList2 - the new list is evaluated only so far as to determine the initial constructor, that is (:) or []. Still no real work has been done.

  3. !oSum <- atomicModifyIORef aVar doubleList3 - by evaluating the sum of the list, this guarantees that computation is fully evaluated.

In the first two cases, there's very little work being done so the atomicModifyIORef will exit quickly. But that work wasn't done in that thread, and now you don't know when it will happen.

In the third case, you know the work was done in the intended thread. First a thunk is created and the IORef updated, then the thread begins to evaluate the sum and finally returns the result. But suppose some other thread reads the data while the sum is being calculated. It may start evaluating the thunk itself, and now you've got two threads doing duplicate work.

In a nutshell, this design hasn't solved anything. It's likely to work in situations where your concurrency problems weren't hard, but for extreme cases like you've been considering, you're still going to be burning cycles with multiple threads doing duplicate work. And unlike STM, you have no control over how and when to retry. At least STM you can abort in the middle of a transaction, with thunk evaluation it's entirely out of your hands.

5
jberryman On

AFAICT if your computation leaves un-evaluated thunks after it does its thing with the IORef contents, that thunk will simply be evaluated in whatever thread tries to use the result, rather than being evaluated in parallel as you would like. See the gotchas section of MVar docs, here

It might be more interesting and helpful for others if you provided a concrete problem that you're trying to solve (or a simplified, but similar one).