On 30 March 2006 11:42, John Meacham wrote:
Although I was skeptical at the beginning that we could come up with a standard based on forkIO that could encompass both models without compromising performance or implementation flexability, I now think that we can! and that is good, because it means we won't need to make concurrency an addendum or just accept the fact that many haskell-prime implementations will be incomplete!
Which sounds like a win-win, but the concern Manuel rose earlier in this thread still holds: namely that if we allow too much flexibility in the standard, it becomes too hard to write portable applications. Someone coding for GHC will almost certainly not insert enough 'yield's to make their program work properly on a cooperative implementation. (hmm, I wonder if GHC could be made to optionally behave like a cooperative scheduler without too much effort. That would help). Still, I think this makes an interesting proposal. Could you put it on the wiki, perhaps replacing Proposal 3?
A sticky point might be whether we say anything about duplicated work, however, the haskell report never really says anything about guarenteed sharing anyway so we can probably be silent on the matter.
Quite right, the standard doesn't need to mention this.
we certainly shouldn't treat state-threads as second class or a "lesser" implementation of the standard though! they can often be faster than OS threads but with their own set of tradeoffs.
glossary:
OS threaded - ghc -threaded, context switching at arbitrary points, not necessarily under the control of the haskell runtime.
state-threading - hugs,jhc context switching at block-points chosen by the implementation and user via yield.
yhc is somewhere in between. basically state-threading, but with more context switching under the control of the yhc run-time.
I'm not sure I'd separate YHC from GHC. They both satisfy the fairness properties we talked about earlier, and from a programmer's point of view would be indistinguishable (to a very close approximation). It's very hard to write a program that can tell them apart. I think if the standard were to go in this direction, then it would be helpful to establish two versions of the fairness properties: the strong version that includes GHC/YHC, and a weaker version that also admits Hugs (eg. the progress guarantee you mentioned earlier). An implementation would be required to say which of these it satisfies. Cheers, Simon
On Thu, Mar 30, 2006 at 12:26:58PM +0100, Simon Marlow wrote:
On 30 March 2006 11:42, John Meacham wrote:
Although I was skeptical at the beginning that we could come up with a standard based on forkIO that could encompass both models without compromising performance or implementation flexability, I now think that we can! and that is good, because it means we won't need to make concurrency an addendum or just accept the fact that many haskell-prime implementations will be incomplete!
Which sounds like a win-win, but the concern Manuel rose earlier in this thread still holds: namely that if we allow too much flexibility in the standard, it becomes too hard to write portable applications. Someone coding for GHC will almost certainly not insert enough 'yield's to make their program work properly on a cooperative implementation. (hmm, I wonder if GHC could be made to optionally behave like a cooperative scheduler without too much effort. That would help).
I was actually just thinking that if not using '-threaded' gave a true cooperative model, that could be useful. for pure IO multiplexing applications (editors,chat clients,web servers) it tends to be faster (hence the switch from pthreading to state-threading in many network servers). Though since ghc already has indirect function calls everywhere, the speed benefit might be neglegable. but the debugging/deterministic benefits could be useful. you could be guarenteed to reproduce a given sequence of context switches which could make finding concurrent heisenbugs easier. or something like concurrent 'hat' or another debugger might find it easier to work in such a mode. In any case, what I think of when I think of 'writing a portable app' is that from _the spec alone_ I can write something that I can expect to work on any compliant system. This goal can be achieved to various degrees. But if the specification says, 'the implementation might be cooperative' and I write assuming that, then it pretty much will definitly work anywhere perhaps with some spurious 'yields'. however if it says something to the effect of 'runnable threads will be timeshared via some fair algorithm for some definition of fair' then it doesn't help much writing portable apps since you would want to test on the various compilers to see what their definiton of "fair" is. It is not like inserting yields needs to be done much at all since we have progress guarentees, so we know the program is doing something and on any blocking call that could potentially take a while, the library will yield for you. at least it is clear from the spec exactly when you need to resort to implementation testing and that you shouldn't count on the scheduler behaving in too specific a way, which is just good advice in general when writing concurrent code.
Still, I think this makes an interesting proposal. Could you put it on the wiki, perhaps replacing Proposal 3?
Okay. I'll put something on the wiki along with the rationale. though, feel free to preempt (pun?) me with anything anyone wants to put there too.
A sticky point might be whether we say anything about duplicated work, however, the haskell report never really says anything about guarenteed sharing anyway so we can probably be silent on the matter.
Quite right, the standard doesn't need to mention this.
we certainly shouldn't treat state-threads as second class or a "lesser" implementation of the standard though! they can often be faster than OS threads but with their own set of tradeoffs.
glossary:
OS threaded - ghc -threaded, context switching at arbitrary points, not necessarily under the control of the haskell runtime.
state-threading - hugs,jhc context switching at block-points chosen by the implementation and user via yield.
yhc is somewhere in between. basically state-threading, but with more context switching under the control of the yhc run-time.
I'm not sure I'd separate YHC from GHC. They both satisfy the fairness properties we talked about earlier, and from a programmer's point of view would be indistinguishable (to a very close approximation). It's very hard to write a program that can tell them apart.
I thought yhc supported unboxed values, so a loop like count 0 = 0 count n = count (n - 1) count 100000 could block the runtime (assuming it was properly unboxed by the compiler) since it never calls back into it and is just a straight up countdown loop? in any case, even if not, yhc might want to support unboxed values one day at which point it might jump categories, but get a speed boost in the process or they will come up with some clever way to have their cake and eat it too :)
I think if the standard were to go in this direction, then it would be helpful to establish two versions of the fairness properties: the strong version that includes GHC/YHC, and a weaker version that also admits Hugs (eg. the progress guarantee you mentioned earlier). An implementation would be required to say which of these it satisfies.
sure. but I sort of object to the terms 'weak' and 'strong'. I think 'preemptive' vs 'cooperative' along with guarentees they make. of course, you might have things like semi-preemptive like nhc with unboxed values leading to possible loops that don't call back into the run-time that complicate things... in any case, we know we should definitly come to a concrete decision on what it means to support the 'weak' or 'cooperative' model and I think we have basically done so across all our threads. Probably some more discussion will be needed to figure out exactly what it means to support the 'strong' model. another case we might want to distinguish is the one where the system is _guarenteed_ to never preempt except at user decided points. though, perhaps this is getting too pedantic for the standard. John -- John Meacham - ⑆repetae.net⑆john⑈
It is not like inserting yields needs to be done much at all since we have progress guarentees, so we know the program is doing something and on any blocking call that could potentially take a while, the library will yield for you.
where do we get the progress guarantees from? do we need a "yield-analysis"? something that will automatically insert yields in the code after every n atomic steps, and complain if it cannot infer that some piece of code is atomic, but cannot insert a yield either? how much of the burden do you want to shift from the implementer to the programmer? cheers, claus
On Thu, Mar 30, 2006 at 01:16:08PM +0100, Claus Reinke wrote:
It is not like inserting yields needs to be done much at all since we have progress guarentees, so we know the program is doing something and on any blocking call that could potentially take a while, the library will yield for you.
where do we get the progress guarantees from? do we need a "yield-analysis"? something that will automatically insert yields in the code after every n atomic steps, and complain if it cannot infer that some piece of code is atomic, but cannot insert a yield either? how much of the burden do you want to shift from the implementer to the programmer?
no, because there are only certain defined actions that can switch a thread's state from 'runnable' to 'not-runnable'. In order to meet the progress guarentee you just need to make sure that when the current thread switches from 'runnable' to 'not-runnable' that another thread is chosen. examples of these points would be: - calling a foreign concurrent import - waiting for input on a handle - waiting for a UNIX signal - changing thread priorities (possibly) in any case, the compiler need do nothing special in general, it is basically a library issue. John -- John Meacham - ⑆repetae.net⑆john⑈
participants (3)
-
Claus Reinke -
John Meacham -
Simon Marlow