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 p2PCwC9R014633 for ; Fri, 25 Mar 2011 13:58:12 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlsDAMGQjE3VhjEVd2dsb2JhbACEQ6ERFAEMCgoJFCWITaoRkSCBJ4NLdwSQSQY X-IronPort-AV: E=Sophos;i="4.63,242,1299452400"; d="scan'208";a="91124552" Received: from ihsmtp01cons.lis.interhost.com ([213.134.49.21]) by mail4-smtp-sop.national.inria.fr with ESMTP; 25 Mar 2011 13:58:07 +0100 Received: from [192.168.1.64] ([178.166.9.223]) by ihsmtp01cons.lis.interhost.com with Microsoft SMTPSVC(6.0.3790.3959); Fri, 25 Mar 2011 12:58:05 +0000 Message-ID: <4D8C915D.6090306@inescporto.pt> Date: Fri, 25 Mar 2011 12:58:05 +0000 From: Hugo Ferreira User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.14) Gecko/20110223 Thunderbird/3.1.8 MIME-Version: 1.0 To: Gerd Stolpmann CC: Fabrice Le Fessant , caml-list@inria.fr References: <2054357367.219171.1300974318806.JavaMail.root@zmbs4.inria.fr> <4D8BD02D.1010505@inria.fr> <4D8C73C8.6020801@inescporto.pt> <1301055903.8429.314.camel@thinkpad> In-Reply-To: <1301055903.8429.314.camel@thinkpad> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-OriginalArrivalTime: 25 Mar 2011 12:58:05.0983 (UTC) FILETIME=[4881AAF0:01CBEAEC] Subject: Re: [Caml-list] Efficient OCaml multicore -- roadmap? On 03/25/2011 12:25 PM, Gerd Stolpmann wrote: > Am Freitag, den 25.03.2011, 10:51 +0000 schrieb Hugo Ferreira: >> 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. I was assuming that this would not be possible given the construction of non-mutable data. > 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. Ok, circularity would certainly complicate assigning ownership to a thread GC. > > 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. > Which seems to bring us back to the initial issue: it would be difficult if not impossible to manipulate and change shared complex data structure manually. I am now wondering if disallowing sharing that causes cycles would make things easier. A sort of FILO stack of sharing. A thread may only share to its descendants. Problem: how to ensure only one of these remains owner. Going to give this some more thought. Thanks for the feedback. R, Hugo F. > 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, >> >> > >