Re: How to re-implement the GC?

[Sylvain Le Gall <sylvain@le-gall.net>]

On 13-09-2010, Eray Ozkural <examachine@gmail.com> wrote:
> --===============0758070018==
> Content-Type: multipart/alternative; boundary=000e0cd18672fce48b049024b79e
>
> --000e0cd18672fce48b049024b79e
> Content-Type: text/plain; charset=ISO-8859-1
>
> 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 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.
>

<take this with care, I am still not a GC expert>
I think it provides an ultra quick way to allocate data on the minor
heap. For heavy allocating programming languages like FP, it is a good
speedup.

Other GC algorithm for Java/C# often made the assumption of long-living
objects with mutation. This is not the case for OCaml. 
</take this with care>

>>
>> >
>> >> 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?
>

Maybe this one:
http://www.algo-prog.info/ocmc/distribution/oc4mc-toronto-stack32k.tar.gz

It seems to be based on 3.11.1. I really don't know in fact, I am not a
oc4mc expert.

>
>> >> 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.
>

I really don't know how to answer, contact directly the OC4MC team. I
only answer you with the data they give at OCaml Meeting, back in April. 

Regards
Sylvain Le Gall