- Haskell-prime - Haskell.org

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 29 Mar '06

29 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

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

29 Mar '06

On 29 March 2006 14:35, John Meacham wrote: > On Wed, Mar 29, 2006 at 02:05:35PM +0100, Simon Marlow wrote: > >> What you are suggesting is that there may be implementations that do >> not support reentrant/blockable, but do support the others. And in >> that case, of course you really need to know the difference between >> blockable and reentrant. I'm just not sure the standard should >> allow such implementations. > > It would be a very odd thing to disallow, seeing as how it would rule > out or at least place fairly large implementation restrictions on > yhc,hugs and jhc and not a single foreign import in the standard > libraries needs to be 'blockable reentrant' as far as I can tell. > > though, I do need to look at hugs and yhcs source more carefully to > know whether that is the case for sure. it depends on a lot of > implementation details and how they handle OS-level threads and > blockable in general. 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. Cheers, Simon

4 3

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

29 Mar '06

On 29 March 2006 09:11, John Meacham wrote: > It would be nice if we can deprecate the not very informative 'safe' > and 'unsafe' names and use more descriptive ones that tell you what is > actually allowed. > > 'reentrant' - routine might call back into the haskell run-time > 'blockable' - routine might block indefinitly I've been meaning to bring this up. First, I don't think 'blockable' is the right term here. This relates to Malcolm's point too: > Another piece of terminology to clear up. By "non-blocking foreign > call", you actually mean a foreign call that *can* block. As a > consequence of the fairness policy, you wish to place the > requirement on implementations that such a blocking foreign call > _should_not_ block progress of other Haskell threads. The > thread-nature of the foreign call is "blocking". The Haskell-API > nature is desired to be "non-blocking". Malcolm correctly notes that when I say "non-blocking" I'm referring to the behaviour from Haskell's point of view, not a property of the foreign code being invoked. In fact, whether the foreign code being invoked blocks or not is largely immaterial. The property we want to capture is just this: During execution of the foreign call, other Haskell threads should make progress as usual. It doesn't matter whether the foreign call "blocks" or not (although that is a common use for this feature). I'd rather call it 'concurrent', to indicate that the foreign call runs concurrently with other Haskell threads. Back to 'reentrant' vs. 'blockable'. I'm not convinced that 'blockable unsafe' is that useful. The reason is that if other Haskell threads continue running during the call, at some point a GC will be required, at which point the runtime needs to traverse the stack of the thread involved in the foreign call, which means the call is subject to the same requirements as a 'reentrant' call anyway. I don't think it's necessary to add this finer distinction. Unless perhaps you have in mind an implementation that doesn't do GC in the traditional way... but then I'm concerned that this is requiring programmers to make a distinction in their code to improve performance for a minority implementation technique, and that's not good language design. If 'reentrant' in its full glory is too hard to implement, then by all means don't implement it, and emit a run-time error if someone tries to use it. Cheers, Simon

3 2

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

29 Mar '06

On 29 March 2006 13:17, John Meacham wrote: > On Wed, Mar 29, 2006 at 12:48:54PM +0100, Simon Marlow wrote: >> I agree with what you say, but let me summarise it if I may, because >> there's an assumption in what you're saying that's easy to miss. >> >> IF >> the combination of 'blockable' and 'reentrant' is not >> required by the standard, >> THEN >> we should allow foreign calls to be annotated with >> one or the other, rather than requiring both. >> >> I agree with this statement, but I don't necessarily agree that the >> predicate should be true. Indeed, given that it requires us to >> complicate the language and puts a greater burden on FFI library >> writers, there's a good argument not to. > > it is just an implementation fact. > > In jhc (and likely yhc and hugs may find themselves in the same boat) > > unsafe > blockable > reentrant > reentrant blockable > > will all have different concrete implementations and generate > different code. for correctness reasons, not efficiency ones. Well, for correctness all you need is reentrant/blockable. If you have that, all the others are efficiency hacks. What you are suggesting is that there may be implementations that do not support reentrant/blockable, but do support the others. And in that case, of course you really need to know the difference between blockable and reentrant. I'm just not sure the standard should allow such implementations. If we were to go down this route, we have to make reentrant the default: 'unsafe' is so-called for a good reason, you should be required to write 'unsafe' if you're doing something unsafe. So I'd suggest unsafe concurrent unsafe concurrent -- the hard one {- nothing -} Cheers, Simon

4 3

RE: Re[2]: important news: refocusing discussion
by Simon Marlow 29 Mar '06

29 Mar '06

On 28 March 2006 00:24, Ross Paterson wrote: > How about STM (minus retry/orElse) and TVars as the portable > interface? They're trivial for a single-threaded implementation, and > provide a comfortable interface for everyone. It just occurred to me that STM isn't completely trivial in a single-threaded implementation, because exceptions have to abort a transaction in progress. Cheers, Simon

3 3