From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p2PCPC9A012811 for ; Fri, 25 Mar 2011 13:25:12 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArICAJ6IjE3U4xEIkGdsb2JhbACEQ6EQFAEBAgkJDQcUJYhNqi+RIAKBJYNLdwSIL4ga X-IronPort-AV: E=Sophos;i="4.63,242,1299452400"; d="scan'208";a="91122645" Received: from moutng.kundenserver.de ([212.227.17.8]) by mail4-smtp-sop.national.inria.fr with ESMTP; 25 Mar 2011 13:25:06 +0100 Received: from office1.lan.sumadev.de (dslb-188-097-077-012.pools.arcor-ip.net [188.97.77.12]) by mrelayeu.kundenserver.de (node=mreu2) with ESMTP (Nemesis) id 0MEaVh-1QEPfs3wtN-00FvPF; Fri, 25 Mar 2011 13:25:06 +0100 Received: from [192.168.1.111] (546BE640.cm-12-4d.dynamic.ziggo.nl [84.107.230.64]) by office1.lan.sumadev.de (Postfix) with ESMTPA id 691695F701; Fri, 25 Mar 2011 13:25:05 +0100 (CET) From: Gerd Stolpmann To: Hugo Ferreira Cc: Fabrice Le Fessant , caml-list@inria.fr In-Reply-To: <4D8C73C8.6020801@inescporto.pt> References: <2054357367.219171.1300974318806.JavaMail.root@zmbs4.inria.fr> <4D8BD02D.1010505@inria.fr> <4D8C73C8.6020801@inescporto.pt> Content-Type: text/plain; charset="UTF-8" Date: Fri, 25 Mar 2011 13:25:03 +0100 Message-ID: <1301055903.8429.314.camel@thinkpad> Mime-Version: 1.0 X-Mailer: Evolution 2.28.1 Content-Transfer-Encoding: 7bit X-Provags-ID: V02:K0:fkuo2ThXt+1trK6EXU1OVKuGKjY/0BdHv3eoYKQ57sa Qw3W+J5JPORujHPG9e6O8iD/1DYGjbIoaD2awvqBUNzgyL6VM9 uXVOtXc2o2s/TgAZh04O4GNimVYF8y5nqamvyD/RNuCLya4lFF bVEGBc70CgNa55F/CrYOnKOIazKbhu9bAPyOn3M/tFASKCxn2R 2RJh9a4qx0qEXP9BZ+D7w== Subject: Re: [Caml-list] Efficient OCaml multicore -- roadmap? Am Freitag, den 25.03.2011, 10:51 +0000 schrieb Hugo Ferreira: > Hello, > > First and foremost just let me say that I am not an expert on this > issue but I have a vested interest in Ocaml's support for parallel > execution, hence my comment. > > On 03/24/2011 11:13 PM, Fabrice Le Fessant wrote: > > Hi, > > > > Actually, I had a discussion two weeks ago with Xavier and Damien > > about this issue. There is some kind of agreement that the ocaml way of > > supporting multicore would be to have several runtimes running in the > > same process, in different threads. That way, the GC would still be > > mono-threaded, so almost no speed loss for mono-threaded programs (i.e. > > currently all OCaml programs ;-) ). There would be some kind of "fork" > > function, that would create a new thread running a function in a new > > heap, probably generated by a copy-on-need algorithm. The different > > threads would not share heap memory, but would be allowed to share > > structures outside of their heaps, probably for simple types like > > strings and int/float arrays (or using the Ancient library). > > > > I see the restriction that shared data be simple data types as a > significant disadvantage. Well, Fabrice was mentioning Ancient which is a code word for putting complex values to non-GC-managed memory. It's only that the application programmer is finally responsible for managing that memory (especially when to deallocate). > In my experience being able to access complex > data structure is crucial. Whenever I see this constraint I keep asking: > why not bite the bullet? Why not take the bull by the horns and do it as > well as possible? If not, I believe its a waste of precious time. > > That being said, I have a question: why will the proposal below not work? > > Assuming all shared data structures are immutable is it possible to: > > 1) Use a GC that is thread aware. > 2) Let each thread have its own thread-aware GC. > 4) Mark the shared data by tagging it with the owner of the data and > counting the number of threads using this data. > 5) Each thread has it own local GC. This GC only manages the thread's > local data that is not shared with any other. > 6) If data is shared, the thread that shares immediately marks it as > shared. > 7) If a thread terminates before the shared data can be collected (that > is when the shared counter is not 0), the ownership is reverted to any > one of the sharing threads. > 8) The last thread to hold a shared data structure is responsible for GC. > > Am I totally off the mark here? It would be a bit more complicated. You have two possible pointers: (1) From thread-specific memory to shared memory (2) From shared memory to shared memory Pointers from shared memory to thread-specific memory would be forbidden, of course. The problem is now that you can manage (1) with reference counting (where the counter would need some protection for concurrent accesses), but for (2) you would need, at least in the general view, a garbage collector that is able to deal with circular pointers. So, probably there is a solution to this, but it is very complex. You would need to extend the header of Ocaml values with counters when they are allocated in the shared space (or the counters are put elsewhere, but this would make it more costly to access them). There needs to be a special version of the garbage collector for the shared space. This is probably all possible, but the effort is not low to get this level of automatism. If we restrict ourselves to manually managed shared space (i.e. the app has to decide when to delete something), we can maybe get something soon. Gerd > > Regards, > Hugo F. > > P.S: Note that the above can be "enhanced" by for example identifying > read-only data in order to facilitate GC. > > > > Now, there are still two problems: > > (1) We don't know yet how to implement that in a portable way. TLS > > (Thread-local storage) is only available on a few architectures. And not > > using TLS implies non-backward compatible changes to the FFI > > (Foreign-Functions Interface), i.e. all stub libraries would have to be > > rewritten. > > (2) As Gerd pointed it, there are not so many programs that would > > benefit from that. So it is not currently on the top of our priority > > list, although I am planning to give it a try in the next months, at > > least for the TLS version. > > > > Cheers, > > -- ------------------------------------------------------------ Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany gerd@gerd-stolpmann.de http://www.gerd-stolpmann.de Phone: +49-6151-153855 Fax: +49-6151-997714 ------------------------------------------------------------