March 2006 - Haskell-prime

Re: seq as a class method
by John Hughes 30 Mar '06

30 Mar '06

>it seems that there is not yet a ticket about putting seq into a type class >(again). > >In my opinion, having seq available for every type is a serious flaw. One >problem is that the law f = \x -> f x doesn't hold anymore since the equation >is false for f = _|_. There was also a discussion on one of the mailing >lists some time ago which revealed that the Monad instance for IO doesn't >satisfy the monad laws because of the availability of seq for IO, I think. > >In addition, the automatic definition of seq for every type can make >implementation details visible which were thought of as completely hidden. >For example, it might make a difference whether one uses data or newtype for >a one-alternative-one-field datatype, even if the data constructor is hidden. > >I therefore propose to declare a class like this: > > class Seq a where > seq :: a -> b -> b > > Oh please, no. This sounds like a good idea in principle, but it was a nightmare in practice. First, the implementation details and the difference between _|_ and const _|_ make a difference to space behaviour, and one needs a way to control that. Hiding the differences can make space leaks *impossible* to fix. Secondly, the need to insert and remove Seq contexts from type signatures during space debugging is a major overhead. In my practical experience such overheads made some desirable refactorings impossible to carry out in the time available for the project. Thirdly, the laws one loses are "nearly true" anyway, and that's very often enough. See "Fast and loose reasoning is morally correct", POPL 2006. We don't need to give up anything to make reasoning *as though* such laws held sound, in most cases. John

8 9

RE: Pre-emptive or co-operative concurrency (was: Concurrency)
by Simon Marlow 30 Mar '06

30 Mar '06

On 30 March 2006 12:44, Claus Reinke wrote: > so if we take that hypothetical example of foreign exporting GHC's > concurrency support, can we assume that the (IO a)s implemented in > foreign code will be given their own OS thread when using that > concurrency library? all of them, or only the non-atomic ones? I'm sorry, I completely fail to see what you're getting at with this line of discussion. Could you say in more detail how you expect to provide access to concurrency via the FFI? And what the point of it is? (it's not obvious how to foreign export forkIO, for example). > the point being: the FFI says something about how to integrate > foreign and Haskell memory management; should it also say something > about threadability of foreign code (wrt to scheduling, and wrt > thread-safety)? If Haskell' includes concurrency then of course it must say something about the behaviour of foreign calls with respect to concurrency (if that's what you mean by "threadability"). Is that what you're asking? Cheers, Simon

2 1

RE: Pre-emptive or co-operative concurrency (was: Concurrency)
by Simon Marlow 30 Mar '06

30 Mar '06

On 29 March 2006 17:34, Neil Mitchell wrote: >> context-switches happen only on specific events, which every >> thread will usually engage in, although it need not always do so: >> >> 1 only calls to yield >> 2 any calls to concurrency library api >> 3 any allocation > > The Yhc concurrency switches every n instructions, and therefore even > an "evil" thread cannot lock up the system. > > Of course, even with fully pre-emptive scheduling, you've still got > deadlocks... Neil, What does YHC do about in-progress thunk evaluations when a context switch happens? Does it use blackholing like GHC, or does it portentially duplicate the work, or something else? Cheers, Simon

3 2

RE: FFI, safe vs unsafe
by Simon Marlow 30 Mar '06

30 Mar '06

On 30 March 2006 13:05, John Meacham wrote: > 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. Actually +RTS -C0 already gives deterministic concurrency in GHC. And you're right, it's essential for debugging. SMP has made my life somewhat more painful of late :-) > 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'. Absolutely, but a preemptive implementation has no way to tell you if you missed out a 'yield', and that essentially is the same as non-portabiliy. It doesn't matter that the spec told you you needed the yield, if the implementation you're using works fine without it, non-portable software will be the result. What's more, in some cases it isn't even possible to insert enough yields. It's entirely reasonable to have an application that runs some CPU-bound pure computation in one thread and a GUI in some other threads. This type of application can't be implemented if the standard guarantees nothing more than cooperative scheduling. Worse, no static property of the code tells you that. > however > if it says something to the effect of 'runnable threads will be > timeshared via some fair algorithm for some definition of fair' No, I'm suggesting the specific fairness guarantees mentioned earlier (and on the wiki page). > 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. Given those fairness guarantees, programmers will not need to care whether the implementation is using preemption based on allocation, or one based on reductions, or arbitrary inter-instruction preemption. Because it is hard to write a program that can tell the difference, especially if you stick to using proper synchronisation primitives, nobody will do it by accident. Contrast this with a standard that allows both cooperative and preemptive scheduling. It's much easier to write a program that can show the difference, and I'm worried that people will do it all the time, by accident. That's bad. > 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? are we talking about the same compiler? YHC is fully interpreted, has no unboxed types, and AFAIK it is impossible to write any code that doesn't get preempted after a while. Cheers, Simon

2 1

RE: seq as a class method
by Simon Marlow 30 Mar '06

30 Mar '06

Hi Andy, This is a good question, and something we hit in GHC quite often too. Our "solution" is to use a mixture of strictness annotations, deepSeq, smart constructors, and hand-waving optimism that things will be evaluated soon enough anyway. Having to occasionally deepSeq the structore to force the thunks has quite a few problems, as you say. A better approach might be to establish a guarantee that the data type isn't leaky; that is, every field is either strict, or guaranteed to be deepSeq'd at construction by a smart constructor. To enforce the smart constructor, you might want ReadOnlyConstructors (see the Haskell' proposal). So for things like this: > regs :: !Array Int RegVal You either use a strict Array type, or deepSeq the Array when constructing the record. To support record update without having to re-deepSeq everything in the record you would want to provide record updaters as part of the abstract datatype. Hope this helps... Cheers, Simon

1 0

RE: FFI, safe vs unsafe
by Simon Marlow 30 Mar '06

30 Mar '06

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

3 3

RE: Pre-emptive or co-operative concurrency (was: Concurrency)
by Simon Marlow 30 Mar '06

30 Mar '06

On 29 March 2006 17:21, Claus Reinke wrote: > all of the concurrency implementations discussed so far seem to > be based on a mixture of preemptive and non-premptive scheduling. > context-switches happen only on specific events, which every > thread will usually engage in, although it need not always do so: > > 1 only calls to yield > 2 any calls to concurrency library api > 3 any allocation Not true - in GHC with SMP a thread doing no allocation can be running concurrently with any number of other threads. It's only the single-threaded implementation that has this bug where a thread that doesn't allocate can starve the other threads. In fact, even on a uniprocessor, you can use GHC's SMP mode to work around the bug by pretending you have 2 CPUs. GHC's SMP mode is truly preemptive, operations from multiple threads can be arbitrarily interleaved. So let's stop saying that all known implementations are non-preemptive, please ;-) Cheers, Simon

3 2

RE: FFI, safe vs unsafe
by Simon Marlow 30 Mar '06

30 Mar '06

On 29 March 2006 16:53, John Meacham wrote: > On Wed, Mar 29, 2006 at 04:11:56PM +0100, Simon Marlow wrote: >> Ok, let's explore how difficult it really is. >> >> Take a single-threaded implementation that forks OS threads for >> concurrent foreign calls. Let's call the OS thread running Haskell >> code the "runtime thread". An OS thread wanting to call a foreign >> export must make an RPC to the runtime thread. You could do this by: >> >> - have a channel for RPC requests >> >> - the callee creates a condition var for the result, and sends >> the call details down the channel with the condition var. >> >> - the runtime thread picks up the request in its event loop and >> forks a Haskell thread to handle it >> >> - when the Haskell thread completes it places the result in the >> right place and signals the condition variable >> >> - the callee picks up the result, frees the resources and >> continues on its merry way >> >> can't be more than a couple of days work, unless I'm missing >> something? It's not particularly fast, but then call-ins in GHC >> aren't fast either. > > still seems rather complicated for something that as far as I know has > never come up as needed :) and given that, it is certainly > unacceptable to pay that cost for every reentrant or blockable call > on the off chance it might want to do both. It's not just for callbacks: you need this working if you want to support call-ins in a multi-threaded environment. That is, implementing a library in Haskell with a C interface that can be called by multiple OS threads. For example, our Visual Studio plugin needed this to be working because Visual Studio likes to call APIs in the plugin from different threads. > Trading a single 'call' instruction for a condition variable, a rpc > call, and some value passing and many memory accesess and potential > SMP bus locks is more than just not particularly fast :) > > why are call-ins in ghc not very fast? with jhc they are just > straight C function calls. You're optimising for the single-threaded case, and that's fine. In GHC, a call-in is similar to what I outlined above except that we can optimise away the RPC and perform the call directly in the OS thread that requested it, due to the way bound threads are implemented. Doing that requires that a lot more of the runtime needs to be thread-safe, though. It's true that this is a fairly large overhead to impose on all Haskell implementations. I'm coming around to the idea that requiring this is too much, and perhaps multi-threaded call-ins should be an optional extra (including concurrent/reentrant foreign calls). Cheers, Simon

2 1

RE: Concurrency (was: RE: Re[2]: important news: refocusingdiscussion)
by Simon Marlow 30 Mar '06

30 Mar '06

On 29 March 2006 10:16, John Meacham wrote: > On Mon, Mar 27, 2006 at 03:36:55PM +0100, Simon Marlow wrote: >> >> (b) it is unlikely that Hugs or JHC will implement concurrency >> even if it goes into the standard > > Well, if the standard is unimplemented for certain compilers, I think > we need to work on the standard because that would be a deficiency of > it. I would very much like to be able to write portable concurrent > programs which doesn't necessarily mean GHC style concurrency or > nothing. > > given the choice between > > 1. a standard specifying something most people can't implement > 2. a widely available but not mentioned in the standard extension > > 2 seems much more preferable and we should err on that side. Fair enough - I take that as a vote for a concurrency addendum. I think it's a bit unfair to talk about "GHC-style concurrency". There are many different ways to implement exactly what GHC currently provides. In fact, we were very careful when designing it to ensure that this was the case: 1. one OS thread per Haskell thread, giant lock around the runtime 2. one OS thread for the runtime, fork OS threads for foreign calls 3. hybrid implementation with a pool of OS threads (GHC's implementation). You even mention another implementation that we hadn't considered: 4. one OS thread per Haskell thread but no lock around the runtime, with possibly repeated work. YHC uses (2), for reference. You're proposing (4) as one possibility for JHC. Cheers, Simon

3 2

Pre-emptive or co-operative concurrency (was: Concurrency)
by Simon Marlow 29 Mar '06

29 Mar '06

On 28 March 2006 11:14, Malcolm Wallace wrote: > There are certainly technical questions. If Hugs's implementation of > concurrency is not concurrency after all, on what basis do we make > that determination? Why is a definition of concurrency that > encompasses both ghc and Hugs models unacceptable? Ok, I'll try to nail down what we should require in terms of fairness (which is the same as pre-emption). The Concurrent Haskell paper [1] gives two requirements. These are: No runnable process will be indefinitely delayed No thread can be blocked indefinitely on an MVar unless another thread holds the MVar indefinitely. The spec also needs to say something about non-blocking foreign calls and concurrent I/O. Both are important, because one of the main uses of concurrency is as a way of structuring a program that interacts with asynchronous external agents. So I propose for the purposes of the standard/addendum, we adopt the above definitions of fairness, together with the requirement that "safe" (and maybe "blockable") foreign calls and I/O operations do not block other threads. That would mean that Hugs doesn't currently comply. My guess is that it could be made a lot closer than it currently is - eg. the IO monad's bind could be made to 'yield' occasionally, non-blocking foreign calls could be implemented, and the I/O library could be made to use them. But this is all real work. If you want to be really picky, GHC doesn't comply either, because a thread can avoid pre-emption by not doing any allocation (we consider this a bug). Cheers, Simon [1] http://www.haskell.org/ghc/docs/papers/concurrent-haskell.ps.gz

6 5