From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 3DC57BC58 for ; Mon, 13 Sep 2010 16:14:49 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmoCAEvOjUzRVdI2kGdsb2JhbACTRYV4AYc7RQgVAQEBAQkJDAcRAx+nOYkyghOGBi2HcgEBAwWFOwSERIVjhVxo X-IronPort-AV: E=Sophos;i="4.56,359,1280700000"; d="scan'208";a="57183015" Received: from mail-pz0-f54.google.com ([209.85.210.54]) by mail3-smtp-sop.national.inria.fr with ESMTP; 13 Sep 2010 16:14:48 +0200 Received: by pzk7 with SMTP id 7so2450297pzk.27 for ; Mon, 13 Sep 2010 07:14:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type; bh=XO0hCUO7pmtwZklGUA4H9rlQ5WpSZ6Hmg1m39zCi6ks=; b=kazBbdirOMgF72PcZzj7+dUyHHbYxtq/wLPVNIVUt0EVfbrYI70Rhm/S8TafQ/Pn9Y 0CmkPfBVyrOKMb5vz0Ed1JJ0Cs6lhKlBAqVUXx4kpIizbqI6vRm6j1llluBpeBKWQV/R us84Yl5qt7d+Q7GNszk2lCHWSJWubrLk6XHg8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=oVSp/vvt6du8bbHIhWLi2LomqmemMzjcaDYUmlgnTq0B5UcHtwmTtU0cDbtXdoGsA0 rzgl1BQpUZjgPjHsG14fkRVFLg2v3MZYF9NTlLt6Takh36t7qHQFuhlYxnce/4wHRIzX V7B+eK1Iur6sdedp9Pt8307JeSwlPNUPLSd4c= MIME-Version: 1.0 Received: by 10.142.185.5 with SMTP id i5mr2993445wff.225.1284387286868; Mon, 13 Sep 2010 07:14:46 -0700 (PDT) Received: by 10.231.159.131 with HTTP; Mon, 13 Sep 2010 07:14:46 -0700 (PDT) In-Reply-To: References: Date: Mon, 13 Sep 2010 17:14:46 +0300 Message-ID: Subject: Re: [Caml-list] Re: How to re-implement the GC? From: Eray Ozkural To: Sylvain Le Gall Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=000e0cd18672fce48b049024b79e X-Spam: no; 0.00; re-implement:01 eray:01 ozkural:01 le-gall:01 eray:01 ozkural:01 pitfalls:01 compiler:01 compiler:01 modular:01 afaik:01 pointer:01 speedup:01 pointer:01 ocaml:01 --000e0cd18672fce48b049024b79e Content-Type: text/plain; charset=ISO-8859-1 On Mon, Sep 13, 2010 at 3:22 PM, Sylvain Le Gall wrote: > On 13-09-2010, Eray Ozkural wrote: > >> On 13-09-2010, Eray Ozkural wrote: > >> > Hi there, > >> > > >> > What exactly are the requirements for substituting the current GC with > >> > another, preferably non-locking, GC? Any pitfalls I wouldn't see just > >> > reading the code? > >> > > >> > >> The GC is deeply interacting with the the rest of the compiler. I think > >> you will spend a lot of time on this task. > >> > >> > > Deeply interacting with the compiler, how? Not through the public > interface > > of GC? Do you mean it is not used in a clean way? > > > > I am not sure how you define "clean way". I think it is very efficient, > but not "modular or object-oriented". I would say that it is clean with > regard of the efficiency. But I won't use it to demonstrate how GC works > to student (but I won't either show them real world implementation of > other GC which are always more complex when optimization is required). > > Well, programming anything in C is messy, I suppose. > AFAIK, it uses some machine register to store a pointer to the minor > heap. But I am not a GC expert. > Ah, that's interesting. I wonder if it provides any real speedup on new architectures compared to storing the pointer in RAM. > > > > >> I would recommend you trying OC4MC, which is probably what you are > >> looking for: > >> http://www.algo-prog.info/ocmc/web/ > >> > >> > > Yes, I've seen it but it's a work in progress, and it's being rewritten > from > > scratch. > > > > > > If you stick to 3.11.1 OCaml version, you'll be able to compile with one > of their latest "stable" patch. > > http://www.algo-prog.info/ocmc/distribution/ Which one is it? > To be honest, I think that if you join your efforts with theirs, you'll > probably get something quicker than going alone on this path. But this > is only my opinion. > Yes, if I decide to carry on I would try to join efforts. But I really need to find out what's necessary first. Hence, all the pondering. > > At least, you will need the "fully-reentrant" runtime they are doing. > > Yes, fully-entrant is necessary for any proper POSIX threads code. If the runtime had some global state, you simply carry that to local state (plugging into function args etc.) and you're done. Depends on how much global state there is. In well-designed programs, there isn't much of a global state, it's unfortunate they didn't notice the runtime wasn't reentrant at first. They would also need to pay attention to such things as volatile memory and synchronization. It can actually get quite difficult to write POSIX threads code that won't deadlock or do unexpected things, while in theory it is quite easy to write. It would be nice to have a complete checklist of everything you need to do to make sure the multithreaded code is correct, which I believe I never had so I prefer message passing :) > >> They show quite interesting results using Thread at the last OCaml > >> Meeting, though they are still some bugs (almost linear speed-up with > >> multicore). > >> > > > > > > What exactly is the GC being used there? Is it a custom algorithm or a > known > > one? Could we plug our own algorithm to the oc4mc if it has already > provided > > the basic changes to substitute the GC? > > > > I think you won't be able to plugin your own GC. The one they provide is > a "stop the world"... I am not sure though, ask them directly. > > That's unfortunate, too, because from reading their source code I had had the impression that they had in mind an easy way to plug-in my GC. One with global lock isn't good enough though, it will not have good performance with memory intensive programs. Hence, my question, suppose this project actually made progress in other parts of the code (like making the runtime fully re-entrant) how do I go about implementing a state-of-the-art GC for this, are there any special requirements or do I just have to implement a minor heap and a major heap etc. to match the interface and the parameters and I am done? I mean, is this a garbage collector as we know it, or does it have any exotic features or requirements? I am looking to see if a competent programmer without an intimate knowledge of the whole compilation system can do it. Best, -- Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara http://groups.yahoo.com/group/ai-philosophy http://myspace.com/arizanesil http://myspace.com/malfunct --000e0cd18672fce48b049024b79e Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Mon, Sep 13, 2010 at 3:22 PM, Sylvain Le Gall <sylvain@le-gall.net> wrote= :
On 13-09-2010, Eray Ozkural <examachine@gmail.com> wrote:
>> On 13-09-2010, Eray Ozkural <examachine@gmail.com> wrote:
>> > Hi there,
>> >
>> > What exactly are the requirements for substituting the curren= t GC with
>> > another, preferably non-locking, GC? Any pitfalls I wouldn= 9;t see just
>> > reading the code?
>> >
>>
>> The GC is deeply interacting with the the rest of the compiler. I = think
>> you will spend a lot of time on this task.
>>
>>
> Deeply interacting with the compiler, how? Not through the public inte= rface
> of GC? Do you mean it is not used in a clean way?
>

I am not sure how you define "clean way". I think it is ver= y efficient,
but not "modular or object-oriented". I would say that it is clea= n with
regard of the efficiency. But I won't use it to demonstrate how GC work= s
to student (but I won't either show them real world implementation of other GC which are always more complex when optimization is required).


Well, programming anything in C is mes= sy, I suppose.
=A0
AFAIK, it uses some machine register to store a pointer to the minor
heap. But I am not a GC expert.

Ah, tha= t's interesting. I wonder if it provides any real speedup on new archit= ectures compared to storing the pointer in RAM.

>
>> I would recommend you trying OC4MC, which is probably what you are=
>> looking for:
>> = http://www.algo-prog.info/ocmc/web/
>>
>>
> Yes, I've seen it but it's a work in progress, and it's be= ing rewritten from
> scratch.
>
>

If you stick to 3.11.1 OCaml version, you'll be able to compile w= ith one
of their latest "stable" patch.

=A0

Which one is it?
=A0
To be honest, I think that if you join your efforts with theirs, you'll=
probably get something quicker than going alone on this path. But this
is only my opinion.

Yes, if I decide to= carry on I would try to join efforts. But I really need to find out what&#= 39;s necessary first. Hence, all the pondering.
=A0

At least, you will need the "fully-reentrant" runtime they are do= ing.


Yes, fully-ent= rant is necessary for any proper POSIX threads code. If the runtime had som= e global state, you simply carry that to local state (plugging into functio= n args etc.) and you're done. Depends on how much global state there is= . In well-designed programs, there isn't much of a global state, it'= ;s unfortunate they didn't notice the runtime wasn't reentrant at f= irst. They would also need to pay attention to such things as volatile memo= ry and synchronization. It can actually get quite difficult to write POSIX = threads code that won't deadlock or do unexpected things, while in theo= ry it is quite easy to write. It would be nice to have a complete checklist= of everything you need to do to make sure the multithreaded code is correc= t, which I believe I never had so I prefer message passing :)
=A0
>> They show quite interesting results using Thread at the last OCaml=
>> Meeting, though they are still some bugs (almost linear speed-up w= ith
>> multicore).
>>
>
>
> What exactly is the GC being used there? Is it a custom algorithm or a= known
> one? Could we plug our own algorithm to the oc4mc if it has already pr= ovided
> the basic changes to substitute the GC?
>

I think you won't be able to plugin your own GC. The one they pro= vide is
a "stop the world"... I am not sure though, ask them directly.
=A0

That's unfortunate, too, because from reading their source code = I had had the impression that they had in mind an easy way to plug-in my GC= . One with global lock isn't good enough though, it will not have good = performance with memory intensive programs. Hence, my question, suppose thi= s project actually made progress in other parts of the code (like making th= e runtime fully re-entrant) how do I go about implementing a state-of-the-a= rt GC for this, are there any special requirements or do I just have to imp= lement a minor heap and a major heap etc. to match the interface and the pa= rameters and I am done? I mean, is this a garbage collector as we know it, = or does it have any exotic features or requirements? I am looking to see if= a competent programmer without an intimate knowledge of the whole compilat= ion system can do it.

Best,
=A0
--
Eray Ozkural, PhD= candidate.=A0 Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/a= i-philosophy
http://myspace.com/arizanesil= http://myspace.com/malfunct
--000e0cd18672fce48b049024b79e--