- Haskell-prime - Haskell.org

RE: Concurrency
by Simon Marlow 03 Apr '06

03 Apr '06

On 31 March 2006 13:41, John Meacham wrote: > I have tried to summarize the current thinking into a proposal on the > wiki. > > http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/Concurrenc y > > I split it into 3 parts. > > the standard - all haskell' compilers must implement > > optional preemption - ability to preempt pure code, fairness > guarentees, interleaved evaluation operators (merge, nmerge) > > optional OS threads - bound threads, SMP, reentrant concurrent FFI > calls supported. > > comment or modify it at will. Great. Apart from my misgivings about allowing cooperative scheduling at all, here's a few comments on the proposal: - I wouldn't include threadWaitRead, threadWaitWrite, or threadDelay at all. These can all be implemented using FFI, so don't belong in the concurrency library. Their presence is largely historical. - yield bothers me a little. If it weren't for cooperative systems, yield would be semantically a no-op, because the no-starvation guarantee means you never need it for correctness. I think it's ok, just a bit unsettling. - In the optional OS threads section it says "allows multiple haskell threads to run at once" - actually you can provide all that without allowing multiple haskell threads to run at once, eg. ghc-6.4.1 with -threaded. I'll modify it. Cheers, Simon

1 0

state threads
by John Meacham 03 Apr '06

03 Apr '06

In case anyone was wondering what this state-threads thing I keep talking about is, here is a sample implementation (in C) as well as a lot of documentation and FAQs that apply to haskell as well. http://state-threads.sourceforge.net/ it should be noted that the chief disadvantage of state threads in C is not an issue for haskell (requiring an alternate IO library) A form of state threads can be implemented in pure haskell using the Poor Man's Concurrency monad described here: http://citeseer.ist.psu.edu/claessen99functional.html assuming you have the ability to use an 'epoll' or 'select' mechanism. However, this is probably not a suitable implementation method for high performance haskell implementations and does not address foreign concurrent calls. John -- John Meacham - ⑆repetae.net⑆john⑈

1 0

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

01 Apr '06

On 28 March 2006 15:26, Malcolm Wallace wrote: > "Simon Marlow" <simonmar(a)microsoft.com> wrote: > >> Ok, I'll try to nail down what we should require in terms of fairness >> (which is the same as pre-emption). > > The terms are not entirely synonymous. > > Pre-emption means that (1) threads have priority levels, and (2) that > a higher priority thread can steal the processor from a > currently-running lower priority thread, and (3) it can do so > "immediately" it needs to, without waiting for some "safe" > synchronisation point. > > By those criteria, none of the current Haskell implementations are > pre-emptive, because no API assigns priorities to threads. So let's > not use the term pre-emption; instead let's agree to talk only about > fairness, since that is the real topic here. Ok, I won't argue this point. It depends which definition you read - I'm using the term preemption to mean that threads can be preempted by the execution engine. I won't use the term any more to avoid confusion. > As I see it, all current (and likely future) implementations of > concurrency in Haskell use co-operative scheduling. The only > differences are in the granularity and positioning of the 'yield' > calls. > > * For Hugs, yield is inserted at certain I/O actions. > * For ghc, yield is inserted after some count of allocations. > * For yhc, yield is inserted after some count of bytecode > instructions. That list is a useful implementation reference, but I think it misses the point. It's much more useful to reserve the term "cooperative" for when the burden is on the programmer to insert context-switch points, as is the case in Hugs. This is a significant difference from the programmer's point of view, whereas the difference in imlementation between GHC and YHC is to a very close approximation invisible. Let's stick to fairness. These are the requirements I think the standard should include: No runnable process will be indefinitely delayed. No thread can be blocked indefinitely on an MVar unless another thread holds the MVar indefinitely. Suitably annotated foreign calls run concurrently with other Haskell threads. That does preclude a cooperative implementation, and for good reasons. Manuel made the point that if a cooperative implementation is admitted by the standard, that makes it much harder to write portable concurrent code. Code written using GHC wouldn't neceessarily run properly on a cooperative implementation, despite the fact that both implementations would be conforming. I think Haskell' should avoid this pitfall. Cheers, Simon

4 3

FD improvement, variable quantification & generalised propagation
by Claus Reinke 01 Apr '06

01 Apr '06

I've had some interesting off-list discussion with Tom Schrijvers (one of the guys responsible for the K.U.Leuven CHR System, which is provided, eg., in SWI Prolog). particularly interesting was the difference in perspective (logic vs functional programming). I'd like to share two items from that discussion (haven't thought either of them through yet, but hope they both provide useful food for thought to those of you interested in the type class problem). 1. I didn't have to explain to him that FDs may lead to variable instantiation, but I did have to explain why without FDs, there is no variable instantiation, and why we even think about FD consistency without automatically implying unification (improvement). the main difference here seems to be that he was thinking of all variables as existentially quantified, whereas type variables are mostly universally quantified, so far. I hadn't given that much thought before, because FDs are meant to determine their range types, and there isn't much difference between universal and existential quantification if there is only one possible variable value, eg: (forall a in {Char}. T a) vs (exists a in {Char}. T a) but perhaps some of the interpretation disagreements we have with FDs could be mitigated if we interpreted FDs differently, depending on whether the range type variables are universally or existentially quantified. given some 'class C a b | a -> b', we could try something like: - forall a b. C a b => T a b: no improvement for b, the FD is used only for checking consistency - forall a. exists b. C a b => T a b improvement & consistency check for b 2. he suggested that the whole problem may be an instance of generalised propagation: Generalised Constraint Propagation Over the CLP Scheme, by Thierry Le Provost and Mark Wallace. Journal of Logic Programming 16, July 1993. Also [ECRC-92-1] http://eclipse.crosscoreop.com:8080/eclipse/reports/ecrc_genprop.ps.gz I agree that this might be a useful framework in which to discuss further developments (variable instantiation is a lot more limited in our context, but we think about why and how to change that; we need to reason in an open world, but at least theoretically, we can collect all instances; we don't have multiple solutions, but we do sometimes need to look at instances before knowing all variable instantiations, leaving us with multiple possible matches, so approximation may be a useful alternative to full search for us, rather than just the optimisation it is in the logic case). any thoughts?-) cheers, claus

1 0

Re: Concurrency
by John Meacham 31 Mar '06

31 Mar '06

On Fri, Mar 31, 2006 at 10:21:16AM -0600, John Goerzen wrote: > On Fri, Mar 31, 2006 at 04:41:06AM -0800, John Meacham wrote: > > optional preemption - ability to preempt pure code, fairness guarentees, > > interleaved evaluation operators (merge, nmerge) > > Under the "what is provided" section, did you intend that to apply to > all compilers, even ones that don't implement threading? the point is that all compilers will implement threading now and provide everything in that section. rather than having all of concurrency being an option, we have found a way to get a good portion of concurrency guarenteed to be supportable on all systems without any compromises in run-time for the non-concurrent case or restricting the range of future implementation techniques. > If so, we should specify what exception is raised if, say, forkIO is > called on such a system. We should also make it clear that > single-threaded implementations are required of things such as MVars. > Finally, we should add a function that indicates the level of threading > support on the running system. routines that are guarenteed to fail becaues they arn't supported should not exist, haskell tries hard to catch so many errors at compile time, it would seem odd to delegate the error of missing a whole subsystem to run-time :) John -- John Meacham - ⑆repetae.net⑆john⑈

2 3

RE: MVar semantics: proposal
by Simon Marlow 31 Mar '06

31 Mar '06

Sequence points... yes, all seems reasonable to me. On 31 March 2006 00:50, John Meacham wrote: > We should drop atomicModifyIORef since we have MVars, for > architectures > with only a test and set instruction and no atomic exchange, > supporting atomicModifyIORef would entail the same overhead as MVars. Slightly less overhead than an MVar, because you only need one lock/release to implement atomicModifyIORef, but two lock/release combinations are involved in an update of an MVar. atomicModifyIORef would be a sequence point, BTW. Semantically, think of it as having a hidden MVar attached to the IORef: withMVar m $ \_ -> do x <- readIORef r let (x',y) = f x writeIORef r x' return y as long as you have some way to enforce exclusion with respect to other atomicModifyIORef operations on a given IORef, you can implement it like this. > atomicModifyIORef also cannot (easily) be implemented on > implementations > that use update-in-place rather than indirections for thunk updates. I don't follow you - how would that make it harder? Cheers, Simon

3 2

RE: New syntax
by Simon Peyton-Jones 31 Mar '06

31 Mar '06

| > Template Haskell breaks expressions with $, | | It's very bad that with TH enabled you cannot write sections of the form ($ x) | anymore which are sometimes very handy. I'd prefer it if TH only sprang into action when you wrote $x or $(f x) That is, no space after the $. If you put spaces, you should get the H98 $. If anyone feels like fixing this, I think it'd be a good thing to do. S

2 1

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

31 Mar '06

On 30 March 2006 21:40, Claus Reinke wrote: >> I updated the ForeignBlocking wiki page with what I believe is the >> current state of this proposal; see > > didn't I mention that "concurrent" may be inappropriate and > misleading, and that I think it is bad practice to rely on the > programmer annotating the dangerous cases, instead of the safe cases? > > wouldn't the safe approach be to assume that the foreign call may do > anything, unless the programmer explicitly tells you about what things > it won't do (thus taking responsibility). This is the way it is right now in GHC: the default is "safe", and safe means both reentrant and concurrent. This is for the reason you give: the default should be the safest, in some sense. However, John has argued, and I agree, that requiring the combination of concurrent and reentrant to be supported is too much, and furthermore is often unnecessary. So we can't have the default (unanotated) foreign call be something that isn't required by the standard. Hence, the proposal states that concurrent foreign calls have to be annotated as such, and it is the specific case of 'concurrent' alone, as opposed to 'concurrent nonreentrant' that is an extension. http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/ForeignBlo cking Cheers, Simon

2 1

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

31 Mar '06

On 30 March 2006 22:01, Claus Reinke wrote: >>> 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? > > yes. I'm all for Haskell' having both ffi and concurrency, but that > means that the feature interactions have to be investigated. I know > you made a start on that, so I was just pointing out some further > corners that may need looking into: > > - if foreign code is used in Haskell' scheduling, what properties of > the foreign code need to be specified, how does long-running > foreign code interact with the scheduler, and are the current > annotations sufficient for all that? > > - if Haskell' code involving concurrency is foreign exported, what > does that mean? does it work out of the box, or what are the > limitations? Rather than answer these directly, I'll point to this paper which addresses these questions and more: http://www.haskell.org/~simonmar/papers/conc-ffi.pdf GHC implements exactly what is in that paper. For Haskell', I expect we won't require all of it, some will be relegated to extensions. > I was looking for a practical example involving concurrency and ffi > in such a way as to expose some of the questions that need to be > answered. you're mentioning forkIO, so that's an example of such > questions: why shouldn't we be able to foreign export that? The (slightly glib) answer to this question is "because it doesn't have a legal FFI type". If you want to foreign export forkIO, you'll have to give me a version that I can foreign export. And that involves some important decisions: just where do you want to run the IO() action, on the server, or the client? If it's on the server, then how to I get the IO() in the first place? YOu must provide some more API functions to build a FunPtr(IO()), or something. (by server I mean the library proferring the forkIO API, by client I mean the client of this API). Cheers, Simon

1 0

MVar semantics: proposal
by John Meacham 31 Mar '06

31 Mar '06

Based on discussion, I'd like to offer up this concrete proposal when it comes to MVars, IORefs, and what we can guarentee when it comes to their interaction with concurrency. My wording can use some cleaning up but I want to get this out there while it is fresh in mind and before I forget the subtleties that led me to this formulation. its primary goals are * let us reason sanely about and provide the tools needed to write concurrent programs. * not break SMP scalability. programs we write now should work on systems of the future. some definitions action - a memory read/write either MVar or IORef that is theoretically observable by a different thread, not necessarily atomic or ordered. sequence point - exactly and only the actions putMVar and takeMVar in a given thread, for some sequence of actions before a sequence point, and some sequence of actions after it. another particular thread may observe those actions in an arbitrary order, at an arbitrary time in the future, except actions may not cross the sequence point boundry. for example thread 1 : A B SP C thread 2 may observe A B C or B A C, but not A C B. another formulation would be that if any action after the sequence point is observable, then all actions before it are guarenteed to be observable in the current thread. putMVar and takeMVar are atomic. this is the _one and only_ guarentee when it comes to different threads observing the same memory locations. in particular, IORefs cannot safely be used except in a single-threaded manner. This is a _pairwise guarentee_ between specific threads, for threads 1,2,and 3 where thread 1 is writing to memory. threads 2 and 3 may observe completly different orderings but each is independently subject to the sequence point constraint. You cannot reason about the observable behavior of a group of threads except insofar as what you can infer by applying this rule pairwise to the members of the group. sequence points are _not_ atomic global events. for the case above thread 1: A B SP C thread 2 might see A B C before thread 3 even sees A. however both are guarenteed to see A and B before they see C. just because one thread reaches and passes a sequence point, it does not mean any other thread has done so. how this relates to IORefs: IORefs do not introduce sequence points nor are operations on them guarenteed to be atomic. given the sequence point constraint above, the following rule is needed for safety IORefs must be used in a single threaded manner, when IORefs are protected by an MVar, the MVar _must_ be locked by the same thread that is using the IORefs. so no locking an MVar and then telling another thread to go ahead and modify some IORefs as the other thread may not have even observed the 'locking' sequence point yet. I believe this lets us sanely reason about concurrent accesses to memory and won't hamper SMP scalable implementations of haskell. notes: We should drop atomicModifyIORef since we have MVars, for architectures with only a test and set instruction and no atomic exchange, supporting atomicModifyIORef would entail the same overhead as MVars. atomicModifyIORef also cannot (easily) be implemented on implementations that use update-in-place rather than indirections for thunk updates. IORefs are not even guarenteed to be atomic. so, if thread 1 writes A then B to an IORef, thread 2 is not even guarenteed to see A or B when it reads it. it may see an intermediate value or even crash the system. if however thread 1 creates a sequence point after writing to the IORef and thread 2 waits for that sequence point to be visible (by say waiting on an MVar) then it may safely read the IORef. if you have not guessed, sequence points correspond exactly to where memory barriers need to be placed in the instruction stream or the much more expensive bus locks on architectures that don't support true memory barriers (cough. x86.). Using the weaker memory barrier semantics for sequence points is a concious decision as it is vital vital for reasonable SMP scaling and global atomic sequence points can be simulated when needed with MVars between an arbitrary number of threads by pairwise sequenceing them. (perhaps we can provide some library routines to make this easy if it turns out to be a common thing people want?) John -- John Meacham - ⑆repetae.net⑆john⑈

1 1