Re: The goals of the concurrency standard?
Fortunatly, I don't expect these issues to be much of a problem in practice. (though, they certainly are real issues) the vast majority of programs, haskell ones included, are either interactive or batch. an interactive program spends most of its time waiting for user input or external events, responding, and in general using very little CPU, this is the sort of app threads are ideal for, text editors, chat clients, window managers, etc... batch programs are things like compilers or meresenne prime calcalculators, that tend to accept input, run for a while, and produce output. however, these types of programs rarely need concurrency. not that all programs fall into those categories, one can write their GUI enabled meresenne prime calculator, and then they will have to worry about such things. but at least with the standard they can now say 'this requires the OS threading option' rather than 'this requires GHC'. in any case, the situation you describe has been the case in GHC for a long time and has not seemed to hurt the use of concurrency for writing a lot of useful apps. However, I am also of the mind that preemtiveness alone doesn't buy enough to make the runtime cost of locking worth it which is why I plan for jhc to be fully cooperative or fully OS threaded with no middle ground. but the situation is different in compilers such as nhc, where preemptiveness can be added relatively easily due to its run-time design and absolute speed was never a goal. In any case, the standard should admit a range of implementations. though, your erlang example reminds me of a truely horrid hack I did with jhc once when experimenting with concurrency models, link two instances of haskell programs together and have them communicate via the FFI while running in different OS threads :) John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 08:41, John Meacham wrote: However, I am also of the mind that preemtiveness alone doesn't buy enough to make the runtime cost of locking worth it which is why I plan for jhc to be fully cooperative or fully OS threaded with no middle ground. but the situation is different in compilers such as nhc, where preemptiveness can be added relatively easily due to its run-time design and absolute speed was never a goal. In any case, the standard should admit a range of implementations. Couldn't pre-emption be implemented quite easily in JHC if you compiled to C--? And imprecise exceptions, for that matter. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 07:46, [EMAIL PROTECTED] wrote: I am afraid I must ask for the clarification of the goals of this discrimination between pre-emptive and cooperative scheduling -- which leads me to further questions. One one hand, I understand the motivation: providing guidance to the end programmer. In a cooperative thread system, the programmer just can't write code imagining the current thread is the only one. If the thread is to compute the Nth Mersenne prime, it would effectively hang the whole system. So, the user must specifically insert calls to yield -- which means that the whole code has to be converted into a monadic style, because yield is most certainly a monadic operation _and_ because we must be sure that computations before yield are indeed finished, rather than snowball up to the very end. So, we have to re-write pure functional code (like the Mersenne prime computation) into a monadic one, and thus explicitly serialize it. That negates one of the significant benefits of Haskell -- no longer code looks like a specification or mathematical notation. If we're forced to write everything in the A-normal form, we might as well use a better language for that, like SML. In a preemptive thread system, we can indeed program a thread as if it were the only thread in the system -- and the scheduler would do the rest. Problem solved? Only if threads do not interact, which is not likely. At least they have to write something, and so contend for the access to stdout (assuming multi-line output). A thread running a long computation while holding a critical resource can just as well hang the whole system, pre-emptive scheduler notwithstanding. Lazy evaluation of Haskell makes this problem quite subtle: do r - return (mersenne' 44) acquire'lock putStrLn Great success print r release'lock One may think that the long computation occurs in the r - ... line. Alas, it may just as well occur in the print r line, when the digits of the number are really required to print. So, we will be running a long computation while holding a lock. This isn't much better than the situation with the cooperative scheduling, is it? In cases where this happens, and it *does* happen, the programmer has to insert explicit seq or deepSeq. It's not a huge problem, at least no worse than the need to use seq/deepSeq to control resource usage or exception leakage. The code inside a lock/unlock sequence is usually quite short, and we can enumerate the free variables quite easily. One example where this happened in GHC is in the definition of putStr itself: our first implementation of putStr took the Handle lock, and then proceeded to traverse the string argument, filling the Handle's buffer with the characters. Unfortunately traversing the string takes arbitrary time, and might even invoke further putStrs (inside unsafePerformIO), so we had to rethink. The easy way is to deepSeq the string first, but that means traversing the string twice, and we don't like to make putStr any less efficient than it already is. So currently putStr works by grabbing a buffer from the Handle, and filling this buffer without holding the Handle lock. When the buffer is full, it gets committed. The Handle keeps a list of free buffers to avoid having to allocate a new one for each putStr. One side-effect of this is that putStrs from multiple threads can be interleaved in strange ways. Fortunately STM helps a lot here, too. (which doesn't mean much for Haskell', but at least it means we have a solution without completely redesigning Haskell'). If a transaction takes a long time because it is busy evaluating free variables, that doesn't prevent other transactions from completing. All that happens is the long-running transaction will probably be aborted due to conflicts with other transactions, but the next time it runs it will probably complete because the work already done isn't discarded. Conclusion: the programmer doesn't have to think about it. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 11:03, John Meacham wrote: On Wed, Apr 12, 2006 at 10:24:57AM +0100, Simon Marlow wrote: On 12 April 2006 08:41, John Meacham wrote: However, I am also of the mind that preemtiveness alone doesn't buy enough to make the runtime cost of locking worth it which is why I plan for jhc to be fully cooperative or fully OS threaded with no middle ground. but the situation is different in compilers such as nhc, where preemptiveness can be added relatively easily due to its run-time design and absolute speed was never a goal. In any case, the standard should admit a range of implementations. Couldn't pre-emption be implemented quite easily in JHC if you compiled to C--? And imprecise exceptions, for that matter. no, it doesn't really help, the main things C-- provides over C are continuations and the introspection into the stack needed for garbage collection. everything c-- continuations would be useful for I am already using longjmp and setjmp for for cooperative concurrency. mainly jumping between multiple C stacks (which are the same as haskell stacks). the issues facing a preemptive implemenentation are that there is no way to implement black-holing, multiple threads will happily waste time evaluating the same thunk, but worse, updates would have to be protected by some sort of mutex or lock. jhc updates nodes in place, meaning a single atomic write to an indirection can't be used, to avoid a context switch in the middle of an update, either locks need to be placed around it, or run-time checks need to be made at safe points (which is arguably not much different than cooperative scheduling). I'll argue that point :) GHC makes run-time checks at safe points and implements preemptive concurrency. Cooperative scheduling is when the *programmer* has to insert the safe points. The safe points don't even have to be very often: in GHC the context switch check is made after every 4k of allocation. Point taken about black holes. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
Re: The goals of the concurrency standard?
On Wed, Apr 12, 2006 at 11:19:53AM +0100, Simon Marlow wrote: I'll argue that point :) GHC makes run-time checks at safe points and implements preemptive concurrency. Cooperative scheduling is when the *programmer* has to insert the safe points. the programmer of the standard libraries or low level FFI interfaces. not the end programmer. I would be highly surprised if anyone other than system or very low level library implementors ever actually needed to use an explicit 'yield'. certainly a whole lot less often than they have to add 'seq's and it is a lot more clear when they are needed :) The safe points don't even have to be very often: in GHC the context switch check is made after every 4k of allocation. indeed, which means GHC technically doesn't meet the preemptive requirements since a tight mathematical non-allocating loop can halt it. in order to do true preemption, you'd need to respond to SIGALRM or something like that, which can be quite tricky. John -- John Meacham - ⑆repetae.net⑆john⑈ ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
On 12 April 2006 11:30, John Meacham wrote: On Wed, Apr 12, 2006 at 11:19:53AM +0100, Simon Marlow wrote: The safe points don't even have to be very often: in GHC the context switch check is made after every 4k of allocation. indeed, which means GHC technically doesn't meet the preemptive requirements since a tight mathematical non-allocating loop can halt it. in order to do true preemption, you'd need to respond to SIGALRM or something like that, which can be quite tricky. Not at all, we could make non-allocating loops bump the heap pointer and do heap checks, but we choose not to. It's just a bug that we don't do this, and it virtually never happens in practice. Cheers, Simon ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
RE: The goals of the concurrency standard?
Simon Marlow wrote: do r - return (mersenne' 44) acquire'lock putStrLn Great success print r release'lock One may think that the long computation occurs in the r - ... line. Alas, it may just as well occur in the print r line, when the digits of the number are really required to print. So, we will be running a long computation while holding a lock. This isn't much better than the situation with the cooperative scheduling, is it? In cases where this happens, and it *does* happen, the programmer has to insert explicit seq or deepSeq. It's not a huge problem, at least no worse than the need to use seq/deepSeq to control resource usage or exception leakage. The code inside a lock/unlock sequence is usually quite short, and we can enumerate the free variables quite easily. My main trouble is foundational. The very need to use seq/deepSeq is quite disturbing: in the above example, we must use those constructions (and so, deepSeq must be standardized, if we take this route). Evaluation time (and divergence) is certainly an effect; when composing with another effect such as locking, we must be able to specify the exact sequence of those effects. Essentially, the need for seq/deepSeq seems to tell that non-strict evaluation is an inadequate computational model in the example at hand. Incidentally, the need to manually insert deepSeq isn't that much different from the need to insert safe points? In both cases, the programmer must be aware how much of the computation has already been done at (some) program points, and be able to control the amount of computation done. Strictly speaking, none of that is possible under non-strict evaluation. Fortunately STM helps a lot here, too. Yes, it does. The previous message pointed out that the STM model seems to be similar to the one used in Erlang. With STM, we can keep lazy evaluation and the programmer does not need to think of seq/deepSeq, etc. But there is a price to pay: we can't use FFI while in the STM monad, we can't use IORefs and we can't use MVars. Right? So, if the STM model is to become the default one (which would be a great thing), FFI and the whole IO will have to be re-designed, and IORefs and MVars removed from the language. ___ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
