Re: OOC Garbage Collector Proposal

[Michael Griebling <grieblm@inforamp.net>]

>Hallo!
>
>Some statements, questions...
>
>> The following discussion is based on the ETH Report #156, "Oberon
>> Technical Notes", the second note entitled "An Integrated Heap
>> Allocator/Garbage Collector" and the fifth note entitled "Garbage
>> collection on Open Arrays."
>
>The Oberon-A compiler also implements a gc. It is mainly written in
>Assembler (680xx) but as it is fully documented it might be another
>resource of information.

I'll have a look at it.

>
>> appropriate free list.  The mark & sweep phases need to be
>> uninterrupted so that memory references and the stack contents remain
>> consistent.
>
>There are also aproaches that work more concurrent, thus avoiding some
>temporary "hanging" of the application while gc. Perhaps "Hanging" is

There are two other approaches that I've encountered: memory copying
and generational.  I'm a bit fuzzy on the details but the first
requires basically a lot more memory and there are some other
problems with the second as well.

>no problem on current machines, but on 680xx is was definitely
>existing. How about threads. Since you own a BeBox you must have
>thought about it?

Yes I have.  The BeOS threads all share the same memory space so
they all have to be collected at the same time.  The only way to
avoid the performance hit is 1) make the collector faster and/or
2) use a difficult algorithm which will probably have a memory
impact (ie. require the use of extra stack or memory).

Generally, I haven't really noticed the hit in OOC so it should
be much less noticeable with this proposed collector.

>> Finalization
>> ------------
>
>It could also be possible to assign a finalizer to a class instead to
>an object. This may have the advantage, that one need not to register
>every object but the class registers itself by adding some compiler
>pragma in front of the finalizer procedure. On the other hand different
>finalizers for different instances of a class may be usefull?

I thought about a class-based but switched to an object-based
implementation because of the problems with inherited classes
(Should they also inherit the finalization of the parent?)  There
may be other issues as well which is why the current Oberon Systems
use the object-based finalization.  I decided to learn from their
mistakes, rather than repeat them.  If anyone knows of a paper
from ETH where they talk about this -- I would appreciate reading
it.

>> OOC Support Required
>> --------------------
>
>> offsets of the pointers contained within that record.  Typically this
>> list of offsets can consist of a variable-length table which is
>> terminated by a negatively-valued sentinel.  The type-descriptor block
>> size will obviously depend on this table size.
>
>since as far as I know the type descriptor already owns a
>variable-length table (methods) this might be a performance problem,
>since the gc has one more indirection to take.

It doesn't have to be.  The current Oberon Systems generally extend
the methods to a maximum fixed limit.  The offsets typically are
found after the method table.

>> Secondly, it will be useful to store within a module's descriptor
>> block where the module's static data begins and its size.  This start
>
>This could be problematic with the current C backend which has no
>single block of memory for module global variables. Perhaps one mus use
>an array of void pointers.

Generally, we need the address of the first variable in this block.
That defines the start of the memory.  No special pointers or void
arrays are required.  I'm assuming that the compiler uses the simplest
arrangement of variables and allocates space on a first-come first-
allocated basis.

>> When To Collect Garbage
>> -----------------------
>
>I'm definitely against a explite call to the gc, it must be possible to
>let the gc be called implecitely. It is very difficult for some long

I'm not saying that the NEW wouldn't be calling GC when it is
necessary.  I would just like to limit these calls.

>running or huge ammounts of memory allocating programs to find an ideal
>position for garbage collection. Another idea is to put the gc cycle
>within the call to NEW but find some other criterium for gc. F.e. the
>gc must be called before the real memory (in difference to the virtual

That's how it works right now.  We only trace real memory.

>memory) runs out. What about tracing stack for legal object pointers.

This has to be done anyway.

>Are there any aproaches. It seems to me that this is neccessary for
>concurrent calls and its implementation sound difficult.

Not really.  You just have to "freeze" the program and check all
the stack space.

Michael