On 2008 Sep 8, at 21:00, Timothy Goddard wrote:

I am not a mathematician, I can't prove it, but I can't think of circumstances where I would need to put mutable references in a data structure except where the language and compiler can't handle immutable structures efficiently.

The status registers of memory-mapped devices come to mind. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

So this is the kind of problem I keep running into. There will seem to be consensus that you can do everything with isolated processes message passing (and note here that I include Actors in this scenario even if their mechanism is more complex). And then someone will pipe up and say "well, of course, you have to have threads" and the argument is usually "for efficiency." I make two observations here which I'd like comments on: 1) What good is more efficiency if the majority of programmers can never get it right? My position: if a programmer has to explicitly synchronize anywhere in the program, they'll get it wrong. This of course is a point of contention; I've met a number of people who say "well, I know you don't believe it, but *I* can write successful threaded programs." I used to think that, too. But now I think it's just a learning phase, and you aren't a reliable thread programmer until you say "it's impossible to get right" (yes, a conundrum). 2) What if you have lots of processors? Does that change the picture any? That is, if you use isolated processes with message passing and you have as many processors as you want, do you still think you need shared-memory threading? A comment on the issue of serialization -- note that any time you need to protect shared memory, you use some form of serialization. Even optimistic methods guarantee serialization, even if it happens after the memory is corrupted, by backing up to the uncorrupted state. The effect is the same; only one thread can access the shared state at a time. On Tue, Sep 9, 2008 at 4:03 AM, Sebastian Sylvan

wrote:

On Mon, Sep 8, 2008 at 8:33 PM, Bruce Eckel wrote:

...

As some of you on this list may know, I have struggled to understand concurrency, on and off for many years, but primarily in the C++ and Java domains. As time has passed and experience has stacked up, I have become more convinced that while the world runs in parallel, we think sequentially and so shared-memory concurrency is impossible for programmers to get right -- not only are we unable to think in such a way to solve the problem, the unnatural domain-cutting that happens in shared-memory concurrency always trips you up, especially when the scale increases.

I think that the inclusion of threads and locks in Java was just a knee-jerk response to solving the concurrency problem. Indeed, there were subtle threading bugs in the system until Java 5. I personally find the Actor model to be most attractive when talking about threading and objects, but I don't yet know where the limitations of Actors are.

However, I keep running across comments where people claim they "must" have shared memory concurrency. It's very hard for me to tell whether this is just because the person knows threads or if there is truth to it.

For correctness, maybe not, for efficiency, yes definitely!

Imagine a program where you have a huge set of data that needs to be modified (in some sense) over time by thousands of agents. E.g. a game simulation. Now, also imagine that every agent could *potentially* modify every single piece of data, but that every agent *typically* only touches two or three varibles here and there. I.e. the collisions between the potential read/write sets is 100%, while the collisions for the actual read/write sets is very very low.

How would you do this with threads and message passing? Well you could have one big thread owning all of your data that takes "update" messages, and then "updates" the world for you (immutably if you wish, by just replacing its "world" variable with a new one containing your update), but now you've effectively serialized all your interactions with the "world", so you're not really concurrent anymore!

So you could decompose the world into multiple threads using some application-specific logical sudivision, but then you're effectively just treating each thread as a mutable variable with an implicit lock (with the risks of deadlock that comes with it - remember we don't know the read/write set in advance - it could be the entire world - so we can't just order our updates in some global way here), so you're really just doing shared mutable state again, and gain little from having threads "simulate" your mutable cells...

What you really need for this is some way for each agent to update this shared state *in parallel*, without having to block all other agents pessimistically, but instead only block other agents if there was an *actual* conflict. STM seems to be the only real hope for that sort of thing right now. IMO my list of preferred methods goes like this: 1. Purely functional data parallelism 2. Purely functional task parallelism (using e.g. strategies) 3. Message passing with no (or very minimal) shared state (simulated using threads as "data servers" or otherwise) (3.5. Join patterns? Don't have enough experience with this, but seems sort of nice?) 4. Shared state concurrency using STM 5. Shared state concurrency using locks 6. Lockless programming.

So while I wouldn't resort to any shared state concurrency unless there are good reasons for why the other methods don't work well (performance is a good reason!), there are still situations where you need it, and a general purpose language had better supply a way of accessing those kinds of facilities.

-- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862

-- Bruce Eckel

2008/9/9 Jed Brown :

On Tue 2008-09-09 12:30, Bruce Eckel wrote:

...

So this is the kind of problem I keep running into. There will seem to be consensus that you can do everything with isolated processes message passing (and note here that I include Actors in this scenario even if their mechanism is more complex). And then someone will pipe up and say "well, of course, you have to have threads" and the argument is usually "for efficiency."

Some pipe up and say ``you can't do global shared memory because it's inefficient''. Ensuring cache coherency with many processors operating on shared memory is a nightmare and inevitably leads to poor performance. Perhaps some optimizations could be done if the programs were guaranteed to have no mutable state, but that's not realistic. Almost all high performance machines (think top500) are distributed memory with very few cores per node. Parallel programs are normally written using MPI for communication and they can achieve nearly linear scaling to 10^5 processors BlueGene/L for scientific problems with strong global coupling.

I should point out, however, that in my experience MPI programming involves deadlocks and synchronization handling that are at least as nasty as any I've run into doing shared-memory threading. This isn't an issue, of course, as long as you're letting lapack do all the message passing, but once you've got to deal with message passing between nodes, you've got bugs possible that are strikingly similar to the sorts of nasty bugs present in shared memory threaded code using locks. David

On Wed, Sep 10, 2008 at 03:30:50PM +0200, Jed Brown wrote:

On Wed 2008-09-10 09:05, David Roundy wrote:

...

2008/9/9 Jed Brown :

...

On Tue 2008-09-09 12:30, Bruce Eckel wrote:

...

So this is the kind of problem I keep running into. There will seem to be consensus that you can do everything with isolated processes message passing (and note here that I include Actors in this scenario even if their mechanism is more complex). And then someone will pipe up and say "well, of course, you have to have threads" and the argument is usually "for efficiency."

Some pipe up and say ``you can't do global shared memory because it's inefficient''. Ensuring cache coherency with many processors operating on shared memory is a nightmare and inevitably leads to poor performance. Perhaps some optimizations could be done if the programs were guaranteed to have no mutable state, but that's not realistic. Almost all high performance machines (think top500) are distributed memory with very few cores per node. Parallel programs are normally written using MPI for communication and they can achieve nearly linear scaling to 10^5 processors BlueGene/L for scientific problems with strong global coupling.

I should point out, however, that in my experience MPI programming involves deadlocks and synchronization handling that are at least as nasty as any I've run into doing shared-memory threading.

Absolutely, avoiding deadlock is the first priority (before error handling). If you use the non-blocking interface, you have to be very conscious of whether a buffer is being used or the call has completed. Regardless, the API requires the programmer to maintain a very clear distinction between locally owned and remote memory.

Even with the blocking interface, you had subtle bugs that I found pretty tricky to deal with. e.g. the reduce functions in lam3 (or was it lam4) at one point didn't actually manage to result in the same values on all nodes (with differences caused by roundoff error), which led to rare deadlocks, when it so happened that two nodes disagreed as to when a loop was completed. Perhaps someone made the mistake of assuming that addition was associative, or maybe it was something triggered by the non-IEEE floating point we were using. But in any case, it was pretty nasty. And it was precisely the kind of bug that won't show up except when you're doing something like MPI where you are pretty much forced to assume that the same (pure!) computation has the same effect on each node.

...

This isn't an issue, of course, as long as you're letting lapack do all the message passing, but once you've got to deal with message passing between nodes, you've got bugs possible that are strikingly similar to the sorts of nasty bugs present in shared memory threaded code using locks.

Lapack per-se does not do message passing. I assume you mean whatever parallel library you are working with, for instance, PETSc. Having the right abstractions goes a long way.

Right, I meant to say scalapack. If you've got nice simple abstractions (which isn't always possible), it doesn't matter if you're using message passing or shared-memory threading.

I'm happy to trade the issues with shared mutable state for distributed synchronization issues, but that is likely due to it's suitability for the problems I'm interested in. If the data model maps cleanly to distributed memory, I think it is easier than coarse-grained shared parallelism. (OpenMP is fine-grained; there is little or no shared mutable state and it is very easy.)

Indeed, data-parallel programming is nice and it's easy, but I'm not sure that it maps well to most problems. We're fortunate that it does map well to most scientific problems, but as "normal" programmers are thinking about parallelizing their code, I don't think data-parallel is the paradigm that we need to lead them towards. David

OK, let me throw another idea out here. When Allen Holub first explained Actors to me, he made the statement that Actors prevent deadlocks. In my subsequent understanding of them, I haven't seen anything that would disagree with that -- as long as you only use Actors and nothing else for parallelism. If someone were to create a programming system where you were only able to use Actors and nothing else for parallelism, could you do everything using Actors? Is there anything you couldn't do? I'm assuming again that we can throw lots of processors at a problem. On Thu, Sep 11, 2008 at 8:17 PM, Aaron Denney wrote:

On 2008-09-10, David Roundy wrote:

...

On Wed, Sep 10, 2008 at 03:30:50PM +0200, Jed Brown wrote:

...

On Wed 2008-09-10 09:05, David Roundy wrote:

...

I should point out, however, that in my experience MPI programming involves deadlocks and synchronization handling that are at least as nasty as any I've run into doing shared-memory threading.

Absolutely, avoiding deadlock is the first priority (before error handling). If you use the non-blocking interface, you have to be very conscious of whether a buffer is being used or the call has completed. Regardless, the API requires the programmer to maintain a very clear distinction between locally owned and remote memory.

Even with the blocking interface, you had subtle bugs that I found pretty tricky to deal with. e.g. the reduce functions in lam3 (or was it lam4) at one point didn't actually manage to result in the same values on all nodes (with differences caused by roundoff error), which led to rare deadlocks, when it so happened that two nodes disagreed as to when a loop was completed. Perhaps someone made the mistake of assuming that addition was associative, or maybe it was something triggered by the non-IEEE floating point we were using. But in any case, it was pretty nasty. And it was precisely the kind of bug that won't show up except when you're doing something like MPI where you are pretty much forced to assume that the same (pure!) computation has the same effect on each node.

Ah, okay. I think that's a real edge case, and probably not how most use MPI. I've used both threads and MPI; MPI, while cumbersome, never gave me any hard-to-debug deadlock problems.

-- Aaron Denney -><-

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Bruce Eckel

On Fri, Sep 12, 2008 at 4:07 PM, Bruce Eckel wrote:

OK, let me throw another idea out here. When Allen Holub first explained Actors to me, he made the statement that Actors prevent deadlocks. In my subsequent understanding of them, I haven't seen anything that would disagree with that -- as long as you only use Actors and nothing else for parallelism.

I think you need to specify what you mean by actors, because I can't see how they would eliminate deadlocks as I understand them. Could you not write an actor that holds a single cell mailbox (both reads and writes are blocking), then set up two classes that shuffles values from the same two mailboxes in the opposite direction? -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862

On Wed, Sep 10, 2008 at 2:55 AM, Maarten Hazewinkel wrote:

And a further note on sharing memory via a transactional resource (be it STM, a database or a single controlling thread). This situation always introduces the possibility that your update fails, and a lot of client code is not designed to deal with that. The most common pattern I see in database access code is to log the exception and continue as if nothing happened. The proper error handling only gets added in after a major screwup in production happens, and the usually only the the particular part of the code where it went wrong this time.

This seems to be a bit too much F.U.D. for STM. As long as you avoid unsafeIOToSTM (which you really should; that function is far more evil than unsafePerformIO), the only failure case for current Haskell STM is starvation; some thread will always be making progress and you do not have to explicitly handle failure. This is absolutely guaranteed by the semantics of STM: no effects are visible from a retrying transaction--it just runs again from the start. You don't have to write "proper error handling" code for transactional updates failing. The only reason why this isn't possible in most database code is that access to the database is happening concurrently with side effects to the local program state based on what is read from the database. Removing the ability to have side effects at that point is what makes STM great. It's easy to make side effects happen on commit, though, just return an IO action that you execute after the atomically block:

atomicallyWithCommitAction :: STM (IO a) -> IO a atomicallyWithCommitAction stm = join (atomically stm)

-- ryan

2008/9/9 Bruce Eckel

So this is the kind of problem I keep running into. There will seem to be consensus that you can do everything with isolated processes message passing (and note here that I include Actors in this scenario even if their mechanism is more complex). And then someone will pipe up and say "well, of course, you have to have threads" and the argument is usually "for efficiency." I make two observations here which I'd like comments on:

1) What good is more efficiency if the majority of programmers can never get it right? My position: if a programmer has to explicitly synchronize anywhere in the program, they'll get it wrong. This of course is a point of contention; I've met a number of people who say "well, I know you don't believe it, but *I* can write successful threaded programs." I used to think that, too. But now I think it's just a learning phase, and you aren't a reliable thread programmer until you say "it's impossible to get right" (yes, a conundrum).

I don't see why this needs to be a religious either-or issue? As I said, *when* isolated threads maps well to your problem, they are more attractive than shared memory solutions (for correctness reasons), but preferring isolated threads does not mean you should ignore the reality that they do not fit every scenario well. There's no single superior concurrency/parallelism paradigm (at least not yet), so the best we can do for general purpose languages is to recognize the relative strengths/weaknesses of each and provide all of them.

2) What if you have lots of processors? Does that change the picture any? That is, if you use isolated processes with message passing and you have as many processors as you want, do you still think you need shared-memory threading?

Not really. There are still situations where you have large pools of *potential* data with no way of figuring out ahead of time what pieces you'll need to modify . So for explicit synchronisation, e.g. using isolated threads to "own" the data, or with locks, you'll need to be conservative and lock the whole world, which means you might as well run everything sequentially. Note here that implementing this scenario using isolated threads with message passing effectively boils down to simulating locks and shared memory - so if you're using shared memory and locks anyway, why not have native (efficient) support for them? As I said earlier, though, I believe the best way to synchronize shared memory is currently STM, not using manual locks (simulated with threads or otherwise).

A comment on the issue of serialization -- note that any time you need to protect shared memory, you use some form of serialization. Even optimistic methods guarantee serialization, even if it happens after the memory is corrupted, by backing up to the uncorrupted state. The effect is the same; only one thread can access the shared state at a time.

Yes, the difference is that with isolated threads, or with manual locking, the programmer has to somehow figure out which pieces lock ahead of time, or write manual transaction protocols with rollbacks etc. The ideal case is that you have a runtime (possibly with hardware support) to let you off the hook and automatically do a very fine-grained locking with optimistic concurrency. Isolated threads and locks are on the same side of this argument - they both require the user to ahead of time partition the data up and decide how to serialize operations on the data (which is not always possible statically, leading to very very complicated code, or very low concurrency). -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862

Sebastian Sylvan wrote:

For correctness, maybe not, for efficiency, yes definitely!

In theory, decades of research and engineering went into shared memory on common hardware, so it should be faster. In practice, you give shared memory to spoiled kids (and seldom encourage them to use other paradigms), and they have no incentive to decompose their problems. They just gratuitously share all variables and therefore need to lock everything. So it becomes slower. If you think hard to decompose a problem, several possibilities occur: - Some problems need shared memory badly. - Most other problems need sharing so little that the way you use shared memory ends up simulating message passing. I encourage you to re-think how often your problems land in the second case. Because we are all spoiled by shared memory, it may be hard to notice.