Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
On 2008-05-27, at 11:34, Martin Berger wrote: Here I disagree. Shared memory concurrency is a specific form of message passing: Writing to a memory cell is in fact sending a message to that cell carrying two items, the new value and a return channel that is used to inform the writer that sending has succeeded, and likewise for reading. [...] But broadcasting is a form of message-passing too! That wasn't my point. My point was that there is no return channel. If you want to know when your write is done, you have to use a lock or a memory barrier. Both are very expensive. -- Damien ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
On Wednesday 28 May 2008 12:18:37 Damien Doligez wrote: On 2008-05-27, at 11:34, Martin Berger wrote: Here I disagree. Shared memory concurrency is a specific form of message passing: Writing to a memory cell is in fact sending a message to that cell carrying two items, the new value and a return channel that is used to inform the writer that sending has succeeded, and likewise for reading. [...] But broadcasting is a form of message-passing too! That wasn't my point. My point was that there is no return channel. If you want to know when your write is done, you have to use a lock or a memory barrier. Both are very expensive. Very expensive compared to what? -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
David Teller wrote: IIRC, there are already type systems which may prevent deadlocks in pi-calculus. This is true but (1) these typing systems are quite complicated and it will take heroic educational efforts to push such new typing systems into programming mainstream; (2) these typing systems (or at least most of them, the Kobayashi/Igarashi scheme is extremely general) are relatively restrictive and many useful concurrent programming idioms turn out to be not typable. Regarding (1), I think using such typing systems for concurrency is completely unavoidable for a variety of reasons, and they will be adopted in the medium term (in about 10 years), but they are not ready for the mainstream yet. As to (2), extending the typing systems is an active research area, and these problems will be solved eventually. Moreover, recent success in extending Hoare Logics to concurrency mean that we don't have to rely on typing systems alone, instead with can take typing systems of medium complexity to prevent the great majority of concurrency bugs and have logics for rare hard cases. (Well, that's the hope anyway!) Martin ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
Gerd Stolpmann wrote: I cannot agree. Just use Ocamlnet! Or other libraries doing it for you. OK I was speaking carelessly. Of course one can use libraries for e.g. event-handling. On the contrary: Shared memory parallelization has the fundamental disadvantage that you cannot reason about it, and so the only way of checking the quality of the code is testing. Here I disagree. Shared memory concurrency is a specific form of message passing: Writing to a memory cell is in fact sending a message to that cell carrying two items, the new value and a return channel that is used to inform the writer that sending has succeeded, and likewise for reading. This way of thinking about shared memory concurrency has enabled the construction of powerful logics and typing systems to reason about shared memory. I agree with the spirit of your claim though: shared memory is a form of message passing that is especially difficult. With reasoning I don't necessarily mean formal techniques. The more frequent case is that the programmer thinks about the program guided by the laws of logic. The impossibility to do this with truly parallelized code is an important source of bugs, so I would say this code inherently more buggy. There is a lot of truth in what you say, but if you consider complex event handling programs, you essentially do concurrent programming, wether you like it or not. You just don't call it by that name. This is simply nonsense. Different concurrency techniques have different problems. For example, in event handling-based concurrency you do not need locks, hence you cannot run into deadlocks. I disagree, but as the issue has already been dealt with by other posters, I shall leave it at that. Maybe in a mainstream language, but in FP I found it always relatively easy to do it. Maybe you are an especially skilled programmer. Or maybe the applications that you have coded are not demanding in terms of concurrency. Martin ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
Ulf Wigner wrote: Going back to Jon's observation that you cannot exploit multicore with event-based programming, I'm inclined to agree, even though I think that message-passing concurrency is quite suitable for making use of multiple cores (albeit addressing a wholly different problem from data parallelism). As more and more core will be put on a single chip, most cores will be communicating via a network on chip. Hence message passing is unavoidable. And if it is unavoidable then maybe we should have it all the way. When scaling up message-passing (or event-based) concurrency, you have to do one of two things: 1) ensure that your code is stable in the face of timing variations and message reordering 2) calculate the entire event/state matrix That's right. Martin ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
Am Mittwoch, den 21.05.2008, 09:06 +0100 schrieb Martin Berger: Here I disagree. Shared memory concurrency is a specific form of message passing: Writing to a memory cell is in fact sending a message to that cell carrying two items, the new value and a return channel that is used to inform the writer that sending has succeeded, and likewise for reading. This way of thinking about shared memory concurrency has enabled the construction of powerful logics and typing systems to reason about shared memory. But this is still academic, right? The practice is that there is almost no utility that helps programmers to write (more) correct code. I agree with the spirit of your claim though: shared memory is a form of message passing that is especially difficult. With reasoning I don't necessarily mean formal techniques. The more frequent case is that the programmer thinks about the program guided by the laws of logic. The impossibility to do this with truly parallelized code is an important source of bugs, so I would say this code inherently more buggy. There is a lot of truth in what you say, but if you consider complex event handling programs, you essentially do concurrent programming, wether you like it or not. You just don't call it by that name. Of course, it is possible to e.g. develop locking mechanism in event handling programs, and then to run into the same problems. My experience is different, however. The worst thing I've encountered so far in practice is the forgotten continuation so that the event system freezes. Another result from using this is in practice is that it is comparatively easy to debug synchronization problems, because the debugging code is not itself concurrent code. This is different to e.g. multi-threaded programs where the whole program is concurrent, and you cannot locally escape from this environment. This is simply nonsense. Different concurrency techniques have different problems. For example, in event handling-based concurrency you do not need locks, hence you cannot run into deadlocks. I disagree, but as the issue has already been dealt with by other posters, I shall leave it at that. Granted, cannot run into deadlocks is too strong. Maybe in a mainstream language, but in FP I found it always relatively easy to do it. Maybe you are an especially skilled programmer. Or maybe the applications that you have coded are not demanding in terms of concurrency. Well, it's probably one of the biggest programs that has ever been coded in O'Caml... It's a search engine (wink.com), and I would say it is very demanding in terms of concurrency. Keep in mind that I am not a researcher. When I make statements, then from a practical point of view. My observation is simply that you run far quicker into complicated synchronization problems with shared memory concurrency than with the types of concurrency I prefer. Gerd -- Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany [EMAIL PROTECTED] http://www.gerd-stolpmann.de Phone: +49-6151-153855 Fax: +49-6151-997714 ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
Gerd Stolpmann skrev: This is simply nonsense. Different concurrency techniques have different problems. True. For example, in event handling-based concurrency you do not need locks, hence you cannot run into deadlocks. Yes you can. We've even had to write design rules to this effect to educate our commercial Erlang programmers. There seems to be a common belief that switching from synchronous to asynchronous communication will eliminate the risk for deadlock, but just like Jon noted, if two threads/processes wait for events from the other processes, they may deadlock*. Using asynchronous programming just makes the deadlock much more difficult to detect, than if the processes communicate synchronously. * In the sense that neither can continue. Deadlock doesn't require the presence of locks at all. Going back to Jon's observation that you cannot exploit multicore with event-based programming, I'm inclined to agree, even though I think that message-passing concurrency is quite suitable for making use of multiple cores (albeit addressing a wholly different problem from data parallelism). The problem with event-based programming is that it doesn't scale complexity-wise, and just as when programming with mutexes, introducing true parallelism just makes it worse. While there may be some simple applications which actually can scale up this way, doing so with more interesting concurrency patterns is courting disaster. I could list some juicy examples of important commercial products that are limited to a single core for this very reason, but alas I'm not permitted to. I have to ask you to take my word for it. When scaling up message-passing (or event-based) concurrency, you have to do one of two things: 1) ensure that your code is stable in the face of timing variations and message reordering 2) calculate the entire event/state matrix For hard real-time, you must do (2) anyway. For soft real-time, you don't have to, since a missed deadline can be viewed as a temporary glitch rather than a system error. And (2) suffers from the same problems as model checking - it doesn't scale well. For a phone system (soft real-time), if you pick up the phone and don't get dial tone, you replace the handset, then pick it up again - normally, it will work then. Everyone's experienced this, and it doesn't bother us unless it happens often. Similarly, we can accept if it occasionally takes a few seconds longer than usual. The same behavior would be extremely unnerving - possibly fatal - if the breaks on your car (hard real-time) started exhibiting it. BR, Ulf W ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
IIRC, there are already type systems which may prevent deadlocks in pi-calculus. And since pi-calculus is essentially the base for CML/OCaml's Event/lwt (I'm not 100% sure for lwt), my guess is that it shouldn't be too hard to get them to work for purely functional threaded code. The missing step would be to detect whether code is purely functional, which is a rather easy task (if tedious). The alternative to that missing step would be to detect whether impurities are localized to each thread -- something which I believe would also be quite feasible, provided you limit side-effects to the use of a well-defined, thread-local, API. Cheers, David On Tue, 2008-05-20 at 00:24 +0200, Berke Durak wrote: Given that shared, mutable global state accessed with multiple threads is a recipe for bugs that no amount of data hiding can solve (because -locking-sections-don't-compose-), did anyone invent and implement a usable type or other system for making concurrency and parallelism safe? If the answer is STM, please show me some non-trivial application that uses it, preferably in an impure language. -- David Teller Security of Distributed Systems http://www.univ-orleans.fr/lifo/Members/David.Teller Angry researcher: French Universities need reforms, but the LRU act brings liquidations. ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
Jon Harrop wrote: Similarly, avoiding threads removes concurrency bugs... I don't believe you have removed any concurrency bugs. I think you just pushed them around a bit. I couldn't agree more. If you 'avoid' concurrency by writing your own 'sequential' event handling code, you have not removed the concurrency, you just face it in a slightly different form, and you have to program the event handling code yourself, rather than relying on a tried and tested library, i.e. you have an additional source of bugs, without removing the problems that are inherent in concurrency (e.g. deadlocks, livelocks, fairness ...). There are reasons why writing your own concurrency mechanisms might be the way to go, but it's a highly non-trivial endeavor. Concurrency is hard, and no matter how one presents the concurrency (message passing, shared memory, event handling etc), the fundamental problems will always be there. Data parallelism in Microsoft's Task Parallel Library. I have no use for STM myself. Do you have industrial experience with STM? I wonder how it performs in industrial settings. Reading STM papers by their inventors makes them sound like the best thing since sliced bread, but I have a (probably irrational) feeling that it's difficult to beat fine grained locking if one can handle the programming difficulties their use imposes. Martin Berger ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
On Monday 19 May 2008 15:09:04 Gerd Stolpmann wrote: On the contrary: Shared memory parallelization has the fundamental disadvantage that you cannot reason about it, I have been reasoning about shared memory parallel programs for many years. and so the only way of checking the quality of the code is testing. I often assess the correctness of my parallel codes just by reading them. Event handing concurrency, while not giving you parallelization, is basically sequential programming, and it is possible to reason about such programs. Programs are parallelized in the interests of efficiency. Event handling concurrency is orders of magnitude less efficient in the context of CPU-intensive tasks that are not embarassingly parallel so it is not an alternative. With reasoning I don't necessarily mean formal techniques. The more frequent case is that the programmer thinks about the program guided by the laws of logic. Then it is a subjective belief. The impossibility to do this with truly parallelized code is an important source of bugs, so I would say this code inherently more buggy. Your remit is concurrency and not parallelism. i.e. you have an additional source of bugs, without removing the problems that are inherent in concurrency (e.g. deadlocks, livelocks, fairness ...). This is simply nonsense. Different concurrency techniques have different problems. For example, in event handling-based concurrency you do not need locks, hence you cannot run into deadlocks. Two agents cannot proceed because they are waiting on events from each other = they are deadlocked even though there are no mutexes. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
On Mon, May 19, 2008 at 11:47 PM, Jon Harrop [EMAIL PROTECTED] wrote: There are two problems with what you wrote in this context: 1. You are replying to a thread about shared-memory parallelism with a discussion of sequential concurrency, which is completely different. 2. You keep saying avoiding threads but what you mean is avoiding parallelism. No, because Ocaml threads today avoid parallelism, but you can still get inconsistency bugs. You'd only get them faster with parallel execution :) In essence, your solution to bugs that arise due to parallelism is to avoid parallelism. While true, that is not going to help anyone exploit multicores. We're going in circles again. I was just arguing, again, that Thread.create + Mutex.lock = more bugs than event-driven execution. Now, yes, that doesn't heat all your cores, so that's why I changed the subject to where is my shared-memory concurrency technology? - not a rhetorical question, but a real one. So, my question is : Given that shared, mutable global state accessed with multiple threads is a recipe for bugs that no amount of data hiding can solve (because -locking-sections-don't-compose-), did anyone invent and implement a usable type or other system for making concurrency and parallelism safe? If the answer is STM, please show me some non-trivial application that uses it, preferably in an impure language. -- Berke Durak ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
Re: [Caml-list] Re: Where's my non-classical shared memory concurrency technology?
If the answer is STM, please show me some non-trivial application that uses it, preferably in an impure language. yes, that would be interesting to see. presumably the example would have to come from Haskell, Clojure, or classically some SQL database? i am under the impression that STM is harder to optimize since generally you don't know what the transactions collided on. whereas with a hot lock you can see precisely what code uses that lock and what it locks. ___ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
