Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
On 10 Sep 2008, at 20:28, Ryan Ingram wrote: On Wed, Sep 10, 2008 at 2:55 AM, Maarten Hazewinkel <[EMAIL PROTECTED]> wrote: [on transaction failures in databases and STM] 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. Thanks for the clarification Ryan. As a hobbyist I haven't actually used STM, so I was grouping it with databases as the only transactional system I am directly familiar with. I suppose I could have guessed that the Haskell community would come up with something that's a class better than a normal shared database. Regards, Maarten Hazewinkel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
On Wed, Sep 10, 2008 at 2:55 AM, Maarten Hazewinkel <[EMAIL PROTECTED]> 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
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 <[EMAIL PROTECTED]>: > > > 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
On Wed 2008-09-10 09:05, David Roundy wrote: > 2008/9/9 Jed Brown <[EMAIL PROTECTED]>: > > 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. > 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. 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.) Jed pgpGjPCgsQQbZ.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
2008/9/9 Jed Brown <[EMAIL PROTECTED]>: > 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
2008/9/9 Bruce Eckel <[EMAIL PROTECTED]> > 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
Hi Bruce, Some comments from an 11 year Java professional and occasional Haskell hobbyist. On 9 Sep 2008, at 20: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." One important distinction to make, which can make a lot of difference in performance, is that shared memory itself is not a problem. It's when multiple threads/processes can update a single shared area that you get into trouble. A single updating thread is OK as long as other threads don't depend on instant propagation of the update or on an update being visible to all other threads at the exact same time. 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). In general I agree. I'm (in all modesty) the best multi-thread programmer I've ever met, and even if you were to get it right, the next requirements change tends to hit your house of cards with a large bucket of water. And never mind trying to explain the design to other developers. I currently maintain a critical multi-threaded component (inherited from another developer who left), and my comment on the design is "I cannot even properly explain it to myself, let alone someone else". Which is why I have a new design based on java.util.concurrent queues on the table. 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? In such a setup I think you usually don't have directly shared memory at the hardware level, so the processors themselves have to use message passing to access shared data structures. Which IMHO means that you might as well design your software that way too. 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. 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. Kind regards, Maarten Hazewinkel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
Bruce Eckel <[EMAIL PROTECTED]> wrote: > ...shared-memory concurrency is impossible for programmers to > get right... Explicit locking is impractical to get right. Transactional interfaces take much of the pain out of that -- even web monkeys can get shared memory right with SQL! When two instances of a web app interact with the database, they are sharing the database's memory. So you have locking, mutual corruption and all that jazz -- yet you seem to be message passing! More generally, applications backed by network services -- which are presented through a message passing interface -- are shared memory applications much of the time (though a bright service can tell when modifications are unrelated and run them in parallel). Message passing certainly makes it easier to write parallel applications, but does it provide any help to manage shared state? No. None whatsoever. If you have a bunch of programs that never share state with one another, they are a single application in name only. Using locking as your default mode of IPC is harrowing, but you can do anything with it. Using message passing is simpler in most cases, but you'll have to implement locking yourself once in awhile. Language level, transactional interfaces to memory are going to cover all your bases, but are rare indeed -- as far as I'm aware, only Haskell's STM offers one. > ...the unnatural domain-cutting that happens in shared-memory > concurrency always trips you up, especially when the scale > increases. This is true even with transactional interfaces. Message passing is _like the network_ and makes you think about the network -- so when it's time to get two servers and hook them together, you are already ready for it already. Transactional shared memory is not at all like the network. Why not? In a transactional system, a transaction can not both be approved and unwritten. On the network, though, these are separate messages, going in different directions -- they can fail independently. -- _jsn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
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 encourage you to browse these slides for some perspective on very large scale coupled computation. Most problems commercial/industrial tasks are much easier since the global coupling is much looser. http://www.xergi.no/upload/IKT/9011/SimOslo/eVITA/2008/PetaflopsGeilo.pdf Jed pgptYTng0IGCZ.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
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 <[EMAIL PROTECTED] > wrote: > > > On Mon, Sep 8, 2008 at 8:33 PM, Bruce Eckel <[EMAIL PROTECTED]> 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) >
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
On Mon, Sep 8, 2008 at 8:33 PM, Bruce Eckel <[EMAIL PROTECTED]> 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
On 9 Sep 2008, at 8:15 am, Kyle Consalus wrote:
Anyway, for the time being I believe there are operations that can be
done with shared memory
that can't be done with message passing if we make "good performance"
a requirement.
One of our people here has been working on Distributed Shared Memory
for some years. It's a programming model where you write AS IF you
had shared memory, but you really don't. He actually uses plain C
with a library, but I've got a student project to wrap some syntax
around that.
typedef struct Foo { ... variables ... } Foo;
typedef struct Bar { ... variables ... } Bar;
shared Foo foo;
shared Bar bar;
shared (const *f = &foo) {
... here we have read access to f->variables ...
}
shared (*b = &bar) {
... here we have read-write access to b->variables ...
}
Underneath, it's message passing. When you get a view on a
shared region, a copy is fetched from the cheapest source that has
a current copy. When you release a write view, you become the
holder of the only current copy. Compressed differences are
sent around the local net. Zhiyi Huang's library is called VODCA.
There's a plug-compatible version developed by his colleagues in
China called Maotai, so the _same_ code can be run on a multicore
system or on a network of workstations. The trick is to choose the
chunk size of your problem so that computation and communication
costs are in the right balance. This certainly seems to be adequate
for numerical software, raytracing, game playing, ...
One issue is that real shared memory comes at a price that most
people don't know they are paying. We wouldn't need MOESI
protocols or the related bus traffic if there were known to be
no sharing, and one of the things that gets in the way of
massive multicore is keeping caches coherent. No shared memory
=> no coherence problem => no extra bus traffic => faster.
--
If stupidity were a crime, who'd 'scape hanging?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
I think the demonstration is in Hoare's book on co-operating
sequential processes, but if you have pure processes and
message passing, you can simulate conventional variables.
Here's an Erlang version:
variable_loop(State) ->
receive
{ask,Sender} -> Sender!{self(),State}, variable_loop(State)
; {tell,New_State} -> variable_loop(New_State)
end.
new_variable(Initial_State) ->
spawn(fun () -> variable_loop(Initial_State) end).
fetch(Variable) ->
Variable!{ask,self()},
receive {Variable,State} -> State end.
store(Variable, New_State) ->
Variable!{tell,New_State}.
new_array(Size, Initial_State) ->
list_to_tuple([new_variable(Initial_State)
|| Dummy <- lists:seq(1, Size)]).
fetch(Array, Index) ->
fetch(element(Index, Array)).
store(Array, Index, New_State) ->
store(element(Index, Array), New_State).
The simulation of (shared) mutable variables and arrays in pure
CSP is very similar. This pretty much _has_ to be possible in
any language that has concurrent processes that can communicate
in some fashion. There are also quite elementary ways to
simulate locking. So we can solve any concurrent problem that,
say, C++ with Intel's TBB library, or Java with java.util.concurrent,
or any other such language can solve. We can even get ourselves
just as far into extremely serious trouble as we can using those
languages, it's just that we don't _have_ to.
--
If stupidity were a crime, who'd 'scape hanging?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
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] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
On Tue, 09 Sep 2008 07:33:24 Bruce Eckel wrote: > I know that both Haskell and Erlang only allow separated memory spaces > with message passing between processes, and they seem to be able to > solve a large range of problems -- but are there problems that they > cannot solve? I recently listened to an interview with Simon > Peyton-Jones where he seemed to suggest that this newsgroup might be a > helpful place to answer such questions. Thanks for any insights -- it > would be especially useful if I can point to some kind of proof one > way or another. In Haskell it is simply irrelevant whether parts of the structures being passed between threads are shared or not because the structures are immutable. We keep our code side-effect free and as a result it is incredibly easy to make parallel. This is so solid that we can also add implicit threading to the code with simple annotations such as 'par' and 'seq'. Having said this, it is possible to generate structures which are mutable and only accessible in the IO monad. As a general rule, IO code using shared memory has the same threading issues as in any other language while pure code is guaranteed safe. Haskell is capable of working with both models, but mutable data structures are deliberately restricted in their use and are rare in practice. A great deal of parallelism can be added to pure code without any risk. I can't assist with mathematical proofs, but can't think of any reason why shared, manipulable memory would be absolutely necessary. In the worst case, all operations on the data structure can be converted to messages to a central thread which manages that structure and serialises access. Any procedure call can become an asynchronous pair of request, response messages. 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. Tim ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
Depending on definitions and how much we want to be concerned with distributed systems, I believe either model can be used to emulate the other (though it is harder to emulate the possible pitfalls of shared memory with CSP). To me, it seems somewhat similar to garbage collection vs manually memory management. You can choose the potential to be more clever than the computer at the risk of finding the problem is more clever than you are. Anyway, for the time being I believe there are operations that can be done with shared memory that can't be done with message passing if we make "good performance" a requirement. On Mon, Sep 8, 2008 at 12:33 PM, Bruce Eckel <[EMAIL PROTECTED]> 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. The only semi-specific comment I've heard refers to data > parallelism, which I assumed was something like matrix inversion, but > when I checked this with an expert, he replied that matrix inversion > decomposes very nicely to separate processes without shared memory, so > now I'm not clear on what the "data parallelism requires threads" > issue refers to. > > I know that both Haskell and Erlang only allow separated memory spaces > with message passing between processes, and they seem to be able to > solve a large range of problems -- but are there problems that they > cannot solve? I recently listened to an interview with Simon > Peyton-Jones where he seemed to suggest that this newsgroup might be a > helpful place to answer such questions. Thanks for any insights -- it > would be especially useful if I can point to some kind of proof one > way or another. > > -- > Bruce Eckel > ___ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Can you do everything without shared-memory concurrency?
Hi Bruce, On Mon, Sep 8, 2008 at 21:33, Bruce Eckel <[EMAIL PROTECTED]> wrote: > I know that both Haskell and Erlang only allow separated memory spaces > with message passing between processes, and they seem to be able to > solve a large range of problems -- but are there problems that they > cannot solve? Modern Haskell has shared memory variables, so that statement "[Haskell] only allows seperated memory spaces..." is not true in practice. In fact, Haskell probably has the (semantically) cleanest and best implementation of STM (Software Transactional Memory) there is imho, which removes most of the headaches of shared memory based concurrency without sacrificing shared memory itself. As for the question "Is there something that the Actor model cannot do but you can with shared memory?", I'd say the answer is probably no. After all, you could just simulate shared memory by having one actor manage all "shared" state. > I recently listened to an interview with Simon > Peyton-Jones where he seemed to suggest that this newsgroup might be a > helpful place to answer such questions. Thanks for any insights -- it > would be especially useful if I can point to some kind of proof one > way or another. I may be completely missing your point, and if so I apologize, but does the simulation argument above suffice as a proof? cheers, Arnar ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Can you do everything without shared-memory concurrency?
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. The only semi-specific comment I've heard refers to data parallelism, which I assumed was something like matrix inversion, but when I checked this with an expert, he replied that matrix inversion decomposes very nicely to separate processes without shared memory, so now I'm not clear on what the "data parallelism requires threads" issue refers to. I know that both Haskell and Erlang only allow separated memory spaces with message passing between processes, and they seem to be able to solve a large range of problems -- but are there problems that they cannot solve? I recently listened to an interview with Simon Peyton-Jones where he seemed to suggest that this newsgroup might be a helpful place to answer such questions. Thanks for any insights -- it would be especially useful if I can point to some kind of proof one way or another. -- Bruce Eckel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
