Re: question about concurrency implementation
Dean, Alastair Reid wrote: Just to be sure we agree on terminology: some people like to distinguish between parallelism and concurrency. Parallelism is a way of going faster but doesn't change your programming model. Implemented correctly, a parallel implementation yields the same results as a sequential implementation - it just runs faster. (This is ignoring the effects of interaction with the outside world, of course - since that can also affect determinism.) Parallel Haskell adds par and friends (operations which have no effect on the semantics of your program). Concurrency changes your programming model. A concurrent program is allowed to give different results and interesting interactions (including race conditions) between threads. A concurrent program may run on a single processor. Concurrent Haskell adds forkIO, killThread, MVars, etc (operations which affect not just the semantics of your program but also the way the semantics are defined). We distinguish between parallel, concurrent and distributed depending on the number of processors and whether threads are *stateful*, i.e. access stateful objects like Mvars or Files, or *stateless*. That is: Sequential, e.g. Haskell 98: 1 PE, 1 Stateful thread, 0 stateless threads Concurrent, e.g. Concurrent Haskell: 1 PE, N Stateful thread, 0 stateless threads Parallel, e.g. GpH: N PEs, 1 Stateful thread, N stateless threads Distributed, e.g. GdH: N PEs, N Stateful thread, N stateless threads In fact these languages form an inclusion hierarchy, e.g. GdH is a superset of both GpH and Concurrent Haskell: GdH / \ GpH Conc. Haskell \ / Haskell 98 Dean Herington wrote: I've asked these questions in order to convince myself that multiple threads can (and will) cooperate in lazily evaluating a value they share, without need for any special programming. In particular, I plan to have multiple threads share values whose computations involve uses of `unsafePerformIO` (the safety of which my application's usage pattern guarantees). The key issue is whether the 'values' are stateful (e.g. Mvars or Files) or stateless (e.g. a shared Haskell variable). Sharing stateless objects between parallel, concurrent, or distributed threads preserves sequential semantics, but sharing stateful objects can introduce non-determinism, unless you have additional properties. Phil -- Phil Trinder Department of Computing and Electrical Engineering Heriot Watt University Riccarton Edinburgh, EH14 4AS E-mail: [EMAIL PROTECTED] Teleph: +44 (0)131 451 3435 Depart: +44 (0)131 451 3328 Fasmly: +44 (0)131 451 3327 Intrnt: http://www.cee.hw.ac.uk/~trinder ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: RE: question about concurrency implementation
Dean, If the costs are the same, does that rely on there being no true concurrency in the current implementations? It depends what you mean by true concurrency: from the point of view of the Haskell programmer, GHC's implementation of concurrency is almost preemptive, because we can context-switch at any allocation. Most computation does some allocation, but it's possible to write functions that don't (although these tend to be on the trivial side - an optimised nfib won't allocate, for example). We could artificially cause all computation to do some allocation to avoid this problem, but we haven't found it necessary so far. But I suspect by true concurrency you're referring at the kind of concurrent processes that can be executed on multiple CPUs simultaneously. We did investigate doing this a while back, and found that the locking required on thunks was very expensive (slowed down the program by at least 2x on the bog-standard SMP machine we had here). However there are some clever techniques that can be used to reduce the cost - giving each process its own private allocation area and only degrading to full locking for access to the shared portion of the heap is one such technique we experimented with briefly but I don't have any concrete benchmarks I'm afraid. Also you really need a multithreaded garbage collector, which is a lot of work. We've developed a Haskell extension that exhibit's true concurrency on multiple CPUs, it's called Glasgow distributed Haskell (GdH). It's primarily designed for distribution (i.e. multiple stateful threads on multiple processors), but can be used to build parallel programs too. For more info see http://www.cee.hw.ac.uk/~dsg/gdh/ Phil -- Phil Trinder Department of Computing and Electrical Engineering Heriot Watt University Riccarton Edinburgh, EH14 4AS E-mail: [EMAIL PROTECTED] Teleph: +44 (0)131 451 3435 Depart: +44 (0)131 451 3328 Fasmly: +44 (0)131 451 3327 Intrnt: http://www.cee.hw.ac.uk/~trinder ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: question about concurrency implementation
Dean | From Simon Marlow's reply, I gather that the current | implementations of Concurrent Haskell provide concurrency | but not parallelism, and that provision of parallelism is | not likely in the near term. That's more or less right. The trouble is that for shared-memory parallelism - you take a performance hit for fine-grain locking - so you need real parallelism to recover that performance All the pieces are there in GHC, mostly implemented; but making it all really work, really reliably, and somewhat portably, is a non-trivial task... and the reward (as I say above) can be elusive. | I've asked these questions in order to convince myself that | multiple threads can (and will) cooperate in lazily | evaluating a value they share, without need for any special | programming. In particular, I plan to have multiple threads | share values whose computations involve uses of | `unsafePerformIO` (the safety of which my application's usage | pattern guarantees). Do make sure you understand Concurrent Haskell (I'm sure you do), which is specifically about multiple threads each of which can perform I/O. (See Tackling the awkward squad on my home page.) You are on thin ice with unsafePerformIO, especially when concurrency is involved. Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: question about concurrency implementation
I'm curious about the implementation of Concurrent Haskell in GHC and Hugs. Does access to values possibly shared among threads cost the same in Concurrent Haskell as in regular Haskell? I'm guessing the answer is yes, because Concurrent Haskell is provided by default in GHC. yes If the costs are the same, does that rely on there being no true concurrency in the current implementations? It depends what you mean by true concurrency: from the point of view of the Haskell programmer, GHC's implementation of concurrency is almost preemptive, because we can context-switch at any allocation. Most computation does some allocation, but it's possible to write functions that don't (although these tend to be on the trivial side - an optimised nfib won't allocate, for example). We could artificially cause all computation to do some allocation to avoid this problem, but we haven't found it necessary so far. But I suspect by true concurrency you're referring at the kind of concurrent processes that can be executed on multiple CPUs simultaneously. We did investigate doing this a while back, and found that the locking required on thunks was very expensive (slowed down the program by at least 2x on the bog-standard SMP machine we had here). However there are some clever techniques that can be used to reduce the cost - giving each process its own private allocation area and only degrading to full locking for access to the shared portion of the heap is one such technique we experimented with briefly but I don't have any concrete benchmarks I'm afraid. Also you really need a multithreaded garbage collector, which is a lot of work. Cheers, Simon ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: question about concurrency implementation
I'm curious about the implementation of Concurrent Haskell in GHC and Hugs. Hugs' implementation of concurrency is non-preemptive wherease GHC's implementation is preemptive (or almost preemptive) as described by Simon. Does access to values possibly shared among threads cost the same in Concurrent Haskell as in regular Haskell? I'm guessing the answer is yes, because Concurrent Haskell is provided by default in GHC. The answer is yes for Hugs. If the costs are the same, does that rely on there being no true concurrency in the current implementations? Just to be sure we agree on terminology: some people like to distinguish between parallelism and concurrency. Parallelism is a way of going faster but doesn't change your programming model. Implemented correctly, a parallel implementation yields the same results as a sequential implementation - it just runs faster. (This is ignoring the effects of interaction with the outside world, of course - since that can also affect determinism.) Parallel Haskell adds par and friends (operations which have no effect on the semantics of your program). Concurrency changes your programming model. A concurrent program is allowed to give different results and interesting interactions (including race conditions) between threads. A concurrent program may run on a single processor. Concurrent Haskell adds forkIO, killThread, MVars, etc (operations which affect not just the semantics of your program but also the way the semantics are defined). You might want to use different words for those concepts but I hope the distinction is clear. (Note that the two concepts are rarely/never separated in imperative languages. Arguably, Esterel is an exception.) Using this terminology, I think what you're asking about is parallelism and not concurrency. -- Alastair Reid[EMAIL PROTECTED]http://www.cs.utah.edu/~reid/ ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell