Garbage collection

I am in the process of writing my own programming language and I would
like to use garbage collection as a means for automatic memory
management. I have decided that I want to implement a two-stage
generational copying collector.

I know how a copying and generational collector works but Im not sure
how they work when put together. In my mind, generational is similar
to coping in being that they both seperate the heap into two
semi-spaces, but use totaly different methods to collect garbage. Can
someone shield some light on this subject for me.

Thanks in advance.
[You might want to ask this on the GC list that spun off from
comp.compilers some time ago. -John]

wmccabe@hotmail.com (William McCabe) writes:
|> I am in the process of writing my own programming language and I would
|> like to use garbage collection as a means for automatic memory
|> management. I have decided that I want to implement a two-stage
|> generational copying collector.
|>
|> I know how a copying and generational collector works but Im not sure
|> how they work when put together. In my mind, generational is similar
|> to coping in being that they both seperate the heap into two
|> semi-spaces, but use totaly different methods to collect garbage. Can
|> someone shield some light on this subject for me.
|>
|> [You might want to ask this on the GC list that spun off from
|> comp.compilers some time ago. -John]

You might also want to start off by deciding what properties you
want your language to have (e.g. its target area), and therefore
what properties you want your garbage collector to have.  No
single garbage collector will be appropriate (or even work) for
all requirements.


Regards,
Nick Maclaren.

William McCabe wrote:
> I know how a copying and generational collector works but Im not sure
> how they work when put together. [snip] Can
> someone shield some light on this subject for me.

You can read the following 2-part article from MSDN. It quite nicely
explains how .Net garbage collector works -- it's also (partly*) copying &
generational collector at one (it even has 2 generations).

http://msdn.microsoft.com/msdnmag/issues/1100/GCI/
http://msdn.microsoft.com/msdnmag/issues/1200/GCI2/

*) it's copying GC for not too large objects (AFAIR less than 16KB), larger
objects are allocated from yet another heap and are unmoveable (as moving
large obiects to compact memory is too slow)

rgds
Sebastian Kaliszewski
--
"Never underestimate the power of human stupidity" -- from Notebooks of L.L.

wmccabe@hotmail.com (William McCabe) wrote
> I am in the process of writing my own programming language and I would
> like to use garbage collection as a means for automatic memory
> management. I have decided that I want to implement a two-stage
> generational copying collector.
>
> I know how a copying and generational collector works but Im not sure
> how they work when put together. In my mind, generational is similar
> to coping in being that they both seperate the heap into two
> semi-spaces, but use totaly different methods to collect garbage. Can
> someone shed some light on this subject for me.

You can try to check what is done in Java, they use 4 generations
with different GC methods for different groups for one of their last
GCs:

http://java.sun.com/docs/hotspot/gc1.4.2/index.html
http://www-106.ibm.com/developerwor...rary/j-jtp11253

Notice that there is a problem with references from the "old"
objects to the "new" objects, these references need special treatment.

BTW, I'm not sure that GC is a part of a compiler, it's usually a
part of runtime support of a language.
[It's runtime, but it's often useful to tweak the compiler to generate
code that makes GC easier. -John]

Le 28-07-2004, William McCabe <wmccabe@hotmail.com> a écrit_:
> I am in the process of writing my own programming language and I would
> like to use garbage collection as a means for automatic memory
> management. I have decided that I want to implement a two-stage
> generational copying collector.
>
> I know how a copying and generational collector works [...]

You need to read Lins&Jones' book on Garbage Collection.

If you want a generational copying GC callable from C (using some
specific coding style and calling conventions) you should consider
using my Qish garbage collector (opensource, LGPL):

http://starynkevitch.net/Basile/qishintro.html

I'll be delighted to offer help in using it if needed.


--
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net
aliases: basile<at>tunes<dot>org = bstarynk<at>nerim<dot>net
8, rue de la Faïencerie, 92340 Bourg La Reine, France

On 4 Aug 2004 02:45:19 -0400, Sebastian <sk@z.pl> wrote:

> [Microsoft garbage collector]
> *) it's copying GC for not too large objects (AFAIR less than 16KB),
> larger objects are allocated from yet another heap and are unmoveable
> (as moving large obiects to compact memory is too slow)

Sadly, I feel the need to add a caveat to this (helpfully meant)
advice, that, whilst it is indeed likely to be enlightening to read
articles published by Microsoft, it is also necessary to bear in mind
that past evidence suggests Microsoft is not exactly the fount of all
computing wisdom. I'm afraid I often find that their documentation is
enlightening in suggesting to me precisely how /not/ to do it.

I may add that I am not a knee-jerk Microsoft knocker. I feel there is
genuine evidence of their widespread technical inexpertise.

The above technique (taken on its own, as I am not myself familiar
with Microsoft technologies) seems to be evidence in my case. I find
it hard to believe that the designers just gave up on moving large
blocks!  I wonder if actually the idea is to allocate blocks greater
than a certain size page-aligned (in a different heap), so that they
can be moved by page table manipulation?

Anyway, my advice is simply to be cautious about Microsoft's
technology documents, and I suppose the same advice applies to other
companies.
--
Nick Roberts

"Nick Roberts" <nick.roberts@acm.org> schreibt:

>I wonder if actually the idea is to allocate blocks greater than a
>certain size page-aligned (in a different heap), so that they can be
>moved by page table manipulation?

The Intel (segmented) memory management technology imposes some
penalties on certain operations. Even if the idea of segment registers
was appropriate when moving from 16 bit code and 64 KB memory limits
to bigger memory (8086), but in later hardware generations (80386)
segment register manipulation and the maintenance of the related
(task, segment...) tables turned out to be too time expensive. This
was the time when the page-based flat memory model was "invented", as
a faster memory management model.

There may exist similar reasons for using different GC allocation
models, perhaps with regards to new I64 (dis)advantages, but I admit
that a general "too slow" argument is a too vague explication.

All in all I agree with your guess about page table manipulation for
fast block moves. Why move memory around byte by byte, when moving
bigger entitites (pages) costs about the same time, per entity?

DoDi

VBDis wrote:

(snip)

> The Intel (segmented) memory management technology imposes some
> penalties on certain operations. Even if the idea of segment registers
> was appropriate when moving from 16 bit code and 64 KB memory limits
> to bigger memory (8086), but in later hardware generations (80386)
> segment register manipulation and the maintenance of the related
> (task, segment...) tables turned out to be too time expensive. This
> was the time when the page-based flat memory model was "invented", as
> a faster memory management model.

A segment descriptor cache could speed up such segment load
operations.  I don't know which, if any, processors had one.
I have been told that some did, but have never seen it in any
Intel or AMD literature.

(snip)

> All in all I agree with your guess about page table manipulation for
> fast block moves. Why move memory around byte by byte, when moving
> bigger entitites (pages) costs about the same time, per entity?

As I understand it, it is common on many systems for the memory
allocation system to fill page tables with pointers to one zero filled
page, and then allocate a real page with the first write operation.
There is a story of someone testing the cache memory characteristics
of a machine with C code like:

int *a,*b,i;
a=malloc(100000000);
b=malloc(100000000);
for(i=0;i<100000000;i++) a[i]=b[i];

It would seem that this would require moving enough data to completely
flush the cache, but it might not.

-- glen

On 11 Aug 2004 12:58:25 -0400, glen herrmannsfeldt <gah@ugcs.caltech.edu>
wrote:

> A segment descriptor cache could speed up such segment load
> operations.  I don't know which, if any, processors had one.
> I have been told that some did, but have never seen it in any
> Intel or AMD literature.

As I understand it, they all have such a cache, except for certain
early steppings of the original Pentium. When it was discovered that
the omission of the cache had a disasterous effects on the execution
speed of some legacy (mostly 16-bit) software, Intel were quick to put
the cache back into their later models.

The Intel models have a cache of 96 extended descriptors, and the
AMD models have 128 I think.

To be honest, I'm not quite sure how the discussion got onto
segmentation in this thread, but never mind :-)
 
>
> As I understand it, it is common on many systems for the memory
> allocation system to fill page tables with pointers to one zero
> filled page, and then allocate a real page with the first write
> operation.

I don't understand why it is necessary for the PTEs to be set to
point to any frame. Why not just set the P bit to 0?

> There is a story of someone testing the cache memory
> characteristics of a machine with C code like:
>
> int *a,*b,i;
> a=malloc(100000000);
> b=malloc(100000000);
> for(i=0;i<100000000;i++) a[i]=b[i];
>
> It would seem that this would require moving enough data to
> completely flush the cache, but it might not.

An interesting test, but not really a fair test of a machine's
speed, since it is somewhat unrepresentative of real workloads.

--
Nick Roberts

Sebastian wrote:
> You can read the following 2-part article from MSDN. It quite nicely
> explains how .Net garbage collector works -- it's also (partly*) copying &
> generational collector at one (it even has 2 generations).

If it had only 1 generation, it wouldn't be generational.

Best regards,
Tom

--
.signature: Too many levels of symbolic links