Re: [Caml-list] Re: How to re-implement the GC?

[Eray Ozkural <examachine@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 4540 bytes --]

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.

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

[-- Attachment #2: Type: text/html, Size: 6585 bytes --]