From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 0DAB2BBC1 for ; Sun, 20 Apr 2008 18:13:00 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArwAAC4IC0jUGyokmmdsb2JhbACRVwEBAQEJBQkHFpcV X-IronPort-AV: E=Sophos;i="4.25,686,1199660400"; d="scan'208";a="9803694" Received: from concorde.inria.fr ([192.93.2.39]) by mail2-smtp-roc.national.inria.fr with ESMTP; 20 Apr 2008 18:12:59 +0200 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m3KGCxhN021212 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Sun, 20 Apr 2008 18:12:59 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArwAAC4IC0jUGyokmmdsb2JhbACRVwEBAQEJBQkHFpcV X-IronPort-AV: E=Sophos;i="4.25,686,1199660400"; d="scan'208";a="9803693" Received: from smtp6-g19.free.fr ([212.27.42.36]) by mail2-smtp-roc.national.inria.fr with ESMTP; 20 Apr 2008 18:12:59 +0200 Received: from smtp6-g19.free.fr (localhost.localdomain [127.0.0.1]) by smtp6-g19.free.fr (Postfix) with ESMTP id 0DF0B5FE4C; Sun, 20 Apr 2008 18:12:59 +0200 (CEST) Received: from [192.168.1.3] (che78-2-82-237-71-191.fbx.proxad.net [82.237.71.191]) by smtp6-g19.free.fr (Postfix) with ESMTP id 18AA05FE5D; Sun, 20 Apr 2008 18:12:58 +0200 (CEST) Message-ID: <480B6B89.2070403@inria.fr> Date: Sun, 20 Apr 2008 18:12:57 +0200 From: Xavier Leroy User-Agent: Thunderbird 2.0.0.4 (X11/20070620) MIME-Version: 1.0 To: Benjamin Canou Cc: Caml List , Philippe Wang , adrien jonquet , Benjamin Canou , Emmanuel Chailloux , Mathias Bourgoin Subject: Re: [Caml-list] OCaml Summer Project decisions are in References: <865618.45090.qm@web54601.mail.re2.yahoo.com> <1208546581.16295.108.camel@nyc-qws-018.delacy.com> <1208614908.6790.53.camel@benjamin-laptop> In-Reply-To: <1208614908.6790.53.camel@benjamin-laptop> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 480B6B8B.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 berke:01 durak:01 parallelism:01 speedup:01 bindings:01 hashtbl:01 threading:01 model:01 bindings:01 run-time:01 parallelism:01 ocaml:01 run-time:01 rewriting:01 Berke Durak wrote: > - How "stoppy" would a stop-the-world parallel GC be in practice? > The more parallelism you have, the more work is done, the higher the > frequency of a major collection. By Amdahl's law, a stop-the-world GC cannot scale well, but it might be good enough for 2 to 4 cores. For instance, assuming a sequential program that spends 25% of its time in garbage collection and parallelizes with low overhead, you would get a speedup of 2 on a 4-core machine. A related question is how long it takes to stop a large number of threads. But only experimentation can tell. > - I'm afraid true concurrency will introduce an awful lot of bugs in > native bindings. Thread-unsafe libraries will have to be replaced > (Str, etc.) Libraries with stateful APIs (such as Str, but also Hashtbl, etc) already need user-level locking to be safely used in concurrent programs, even with today's concurrent-but-not-parallel threading model for Caml. The only additional problem I can see is with C bindings that expose a functional API but have global state in their implementation, but I'm not sure there are many. So, I wouldn't worry too much about this at the moment. But there are more acute problems with global C state in the Caml run-time system itself (see below). > Also what would be the CPU and memory costs? Don't concurrent GCs > require extra colors? Not the ones I know. Benjamin Canou wrote: > So our proposal is to let this project be more "a first reusable step > toward parallelism in OCaml" than "a parallel OCaml". > More practically, we propose the following subtasks: > 1. To strip down the current run-time library, rewriting some parts > which are too much dependent on the current GC > 2. To clean the (small) parts of the compiler preventing us from > changing the allocator (for example, OCaml inlines some allocations by > directly emitting code which modifies the heap pointer). > 3. To define a clean and documented interface for adding new GCs, > ideally adding a run-time switch to choose the GC. > 4. To to reinject the current GC, or a simpler sequential GC we > already wrote for another work, using this interface to validate the > approach. > 5. To design a first parallel GC, simple enough for us to be able to > test and benchmark it before the end of the project and to implement it > within our interface. This sounds globally reasonable for a first step, although you should be careful not to completely shift your objectives from parallelism to plug-in GCs. There are two point that I'd like to emphasize. The first step towards any form of true parallelism in Caml (including message-passing between threads having their own heaps and sequential GCs) is to clean up the numerous global C variables that the run-time system uses. But maybe this was implicit in your point 1. Another crucial point is the ability to stop all threads and obtain their roots, which is not obvious at all and a prerequisite for any form of concurrent garbage collection. At any rate, it's probably better not to ask too many questions at this point and let you concentrate on the task at hand. Feel free to contact me and Damien Doligez for specific questions or general advice. - Xavier Leroy