Re: GMC for dummies

7 views
Skip to first unread message

Nattfodd

unread,
Jul 15, 2005, 8:36:11 PM7/15/05
to perl6-i...@perl.org

Nattfodd

unread,
Jul 15, 2005, 8:24:09 PM7/15/05
to Leopold Toetsch, perl6-i...@perl.org
Hi,
I've produced a new document on GMC (Generational Mark & Compact), the
GC I'm trying to implement as a Summer of Code project. It's called gmc
for dummies and I hope it's plainly understandable (if not, tell me so
and I'll try to make it better). It should explain how things will
hopefully work.

Any comments are of course welcome.

Regards,
Alexandre

Leopold Toetsch

unread,
Jul 16, 2005, 5:38:41 AM7/16/05
to Nattfodd, perl6-i...@perl.org

On Jul 16, 2005, at 2:24, Nattfodd wrote:

>
> Hi,
> I've produced a new document on GMC (Generational Mark & Compact), the
> GC I'm trying to implement as a Summer of Code project. It's called gmc
> for dummies and I hope it's plainly understandable (if not, tell me so
> and I'll try to make it better). It should explain how things will
> hopefully work.
>
> It's here :
> http://perso.ens-lyon.fr/alexandre.buisse/divers/gmc_for_dummies.pod

This is not quite the scheme, we were pondering in previous mail and
IRC.

1) pmc_bodies have to be variable sized
2) the scheme is missing the invariant we keep:
C<< &younger_body < &older_body >>

ad 1)

a PMC is a 2 word structure { PMC_BODY *pmc_body; VTABLE *vtable }
a pmc_body of Integer PMC is eventually just { INTVAL int_val }, of a
Float PMC it's the double num_val,
a pmc_body of an object with 2 attributes is:
{ INTVAL n_attr; PMC *class; PMC *attr1; PMC *attr2 }
and a pmc_body of the Hash PMC is basically just the Hash structure w/o
any further indirections...

During the transition phase all pmc_bodies still have an 'UINTVAL
flags' field.

The gmc_header that is prepended to all pmc_bodies has a PMC *back_ptr
and gc flags + some type flags that identify the following PMC body for
gc operations. We need the size of the body for walking the pmc_body
memory and we have to mark the contents of the body, if any.

ad 2)

The free generation is lowest in memory followed by the youngest
generation, the oldest objects have highest memory addresses. Please
note: this invariant exists in the pmc_body area. Therefore the mark GC
operation is one pass:

- mark the root set
- walk the pmc_bodies from left (lowest mem) to right
- if the pmc_body is alive mark it's contents (if any) and proceed
- if the pmc_body isn't marked alive, it's dead

There is no need for any extra todo-list to mark the children of
objects.

We keep the invariant by several means:
a) aggregates/containers are allocated from the left of free
b) non-aggregates are allocated from the right of free
(with a) + b) containers already have their contents at higher
memory addresses)
c) a write barrier checks pointer stores into aggregates (by just
comparing 2 memory addresses - basically)
we can do either:
- make aggregate younger (move to left)
- make stored-into object older (move to right)
- remember in IGP
d) if we have to extend the allocation area, we usually we'll have to
move all existing objects "up", either by a full GC run or by just
copying, because you'll get usually higher memory regions from the OS.

These are of course just my ideas, how GMC could operate.
leo

Nattfodd

unread,
Jul 16, 2005, 8:46:53 AM7/16/05
to Leopold Toetsch, perl6-i...@perl.org
Leopold Toetsch wrote:

>
> On Jul 16, 2005, at 2:24, Nattfodd wrote:
>
>>
>> Hi,
>> I've produced a new document on GMC (Generational Mark & Compact), the
>> GC I'm trying to implement as a Summer of Code project. It's called gmc
>> for dummies and I hope it's plainly understandable (if not, tell me so
>> and I'll try to make it better). It should explain how things will
>> hopefully work.
>>
>> It's here :
>> http://perso.ens-lyon.fr/alexandre.buisse/divers/gmc_for_dummies.pod
>
>
> This is not quite the scheme, we were pondering in previous mail and IRC.
>
> 1) pmc_bodies have to be variable sized

Oh, I believed that we would use variable-sized pmc only if the gc
proved to work really well.

> 2) the scheme is missing the invariant we keep:
> C<< &younger_body < &older_body >>
>
> ad 1)
>
> a PMC is a 2 word structure { PMC_BODY *pmc_body; VTABLE *vtable }
> a pmc_body of Integer PMC is eventually just { INTVAL int_val }, of a
> Float PMC it's the double num_val,
> a pmc_body of an object with 2 attributes is:
> { INTVAL n_attr; PMC *class; PMC *attr1; PMC *attr2 }
> and a pmc_body of the Hash PMC is basically just the Hash structure
> w/o any further indirections...
>
> During the transition phase all pmc_bodies still have an 'UINTVAL
> flags' field.
>
> The gmc_header that is prepended to all pmc_bodies has a PMC *back_ptr
> and gc flags + some type flags that identify the following PMC body
> for gc operations. We need the size of the body for walking the
> pmc_body memory and we have to mark the contents of the body, if any.

Then we use a doubly linked list, but that should be no problem. The
structure becomes something like :

... | pmc_body || back_ptr | flags | prev | next | pmc_body || back_ptr
| ...

------------------------------------------------ ----------------

| |

v v
pmc_header pmc_body


pmc_body size is just (next - *(void**)next + sizeof(pmc_header)).

>
> ad 2)
>
> The free generation is lowest in memory followed by the youngest
> generation, the oldest objects have highest memory addresses. Please
> note: this invariant exists in the pmc_body area. Therefore the mark
> GC operation is one pass:
>
> - mark the root set
> - walk the pmc_bodies from left (lowest mem) to right
> - if the pmc_body is alive mark it's contents (if any) and proceed
> - if the pmc_body isn't marked alive, it's dead
>
> There is no need for any extra todo-list to mark the children of objects.

???
I believe that was pretty much what was described in the document. What
I called "pointers an object has to other objects" is simply its contents.

>
> We keep the invariant by several means:
> a) aggregates/containers are allocated from the left of free
> b) non-aggregates are allocated from the right of free
> (with a) + b) containers already have their contents at higher
> memory addresses)

So you mean that we allocate :

| xxx[aggregates]xxx... ...[free space]... ...xxx[non-aggregates]xxx |

Or rather, as I thought :

| ...[free space]... ...xxx[some aggregate][its contents][some
aggregate][its contents]xxx |

>
> c) a write barrier checks pointer stores into aggregates (by just
> comparing 2 memory addresses - basically)

Another question I had is how do we know when there is such a pointer
store ? It can happen at other moments than object allocation, right ?

> we can do either:
> - make aggregate younger (move to left)
> - make stored-into object older (move to right)
> - remember in IGP
> d) if we have to extend the allocation area, we usually we'll have to
> move all existing objects "up", either by a full GC run or by just
> copying, because you'll get usually higher memory regions from the OS.


Hum, I hadn't thought of this problem.


Bob Rogers

unread,
Jul 16, 2005, 11:26:56 AM7/16/05
to Leopold Toetsch, Nattfodd, perl6-i...@perl.org
From: Leopold Toetsch <l...@toetsch.at>
Date: Sat, 16 Jul 2005 11:38:41 +0200

. . .

We keep the invariant by several means:

. . .


c) a write barrier checks pointer stores into aggregates (by just
comparing 2 memory addresses - basically)
we can do either:
- make aggregate younger (move to left)
- make stored-into object older (move to right)
- remember in IGP

What happens when a store creates a cycle? And how would this be
detected?

-- Bob

Leopold Toetsch

unread,
Jul 17, 2005, 6:08:34 AM7/17/05
to Bob Rogers, Nattfodd, perl6-i...@perl.org

To keep the invariant we can't move the container nor the contained
object, *if* both are aggregates. Therefore the pointer store will be
recorded on the IGP list. Thus there is no need to detect cycles.

> -- Bob

leo

Nattfodd

unread,
Jul 17, 2005, 4:45:51 PM7/17/05
to Leopold Toetsch, perl6-i...@perl.org
Leopold Toetsch wrote:

> Nattfodd wrote:


>
>> Leopold Toetsch wrote:
>
>
>>> 1) pmc_bodies have to be variable sized
>>
>>
>> Oh, I believed that we would use variable-sized pmc only if the gc
>> proved to work really well.
>
>

> Well, with fixed sized bodies, we don't need the extra indirection.
>
> But I really like to have a more flexible object layout. Have a look
> at Parrot sources and draw a picture of an object with 2 attributes,
> or a FixedSizedXXArray or a Sub PMC ... All the interesting, needed
> and heavily used data are hanging off some extra pointers inside
> malloced structures. I just want that to be (in) the body.


>
>> Then we use a doubly linked list, but that should be no problem. The
>> structure becomes something like :
>
>

> Well, gc_gms has already this layout, with prev and next pointers
> inside the gc_header. But in gc_gms it is needed, because you can't
> move the PMC memory w/o indirection pointer into a different object
> generation.
>
> But I consider 4 words for GC + 1 indirection pointer as a very big
> overhead, even compared to the current situation. So I'd really not
> like to have these 2 extra pointers, and I don't think that they are
> needed.

I believe that if we want variable-sized body, we need at least one next
(or pmc_size) pointer in the header.
Unless there is some way to know where all the PMC* are, we could then
use two passes and need the nb_pmc words only during the gc run : first
pass is look at all the PMC* and copy PMC->pmc_body in a sorted array.
Then run through that array and that will tell us where all the gc
objects are.
That's adding some extra runtime for gc and we still need much space,
but we can free it at the end of the gc run.

I we can't know where all the PMC* are, then I think we need a next
pointer, but can still apply the previous trick to spare the prev pointer.

Do you see any other solution that could avoid prev and next ?

>
>>> There is no need for any extra todo-list to mark the children of
>>> objects.
>>
>>
>>
>> ???
>> I believe that was pretty much what was described in the document. What
>> I called "pointers an object has to other objects" is simply its
>> contents.
>
>

> You write in the pod:
> * Mark all elements of the root set and add them to a queue (or a
> stack, whatever) somewhere
>
> But it isn't really clear what you are trying to achieve here.

Sorry, this is crap, because I didn't know how exactly the root set was
to be treated. But the queue thing (which I'll remove entirely) is just
saying "iterate over the root set and mark its elements".

>
>> So you mean that we allocate :
>>
>> | xxx[aggregates]xxx... ...[free space]...
>> ...xxx[non-aggregates]xxx |
>
>

> Yep.


>
>> Or rather, as I thought :
>>
>> | ...[free space]... ...xxx[some aggregate][its contents][some
>> aggregate][its contents]xxx |
>
>

> That's probably suboptinal for ususal cases like filling an array with
> some values.


>
>>> c) a write barrier checks pointer stores into aggregates (by just
>>> comparing 2 memory addresses - basically)
>>
>>
>> Another question I had is how do we know when there is such a pointer
>> store ? It can happen at other moments than object allocation, right ?
>
>

> Well, that is exactly what the write barrier is for. Grep for
> WRITE_BARRIER in the parrot sources.

Thanks, I think I understand much better how everything is going on.

>
>>> we can do either:
>>> - make aggregate younger (move to left)
>>> - make stored-into object older (move to right)
>>> - remember in IGP
>>> d) if we have to extend the allocation area, we usually we'll have to
>>> move all existing objects "up", either by a full GC run or by just
>>> copying, because you'll get usually higher memory regions from the OS.
>>
>
>> Hum, I hadn't thought of this problem.
>
>

> You should :-)

As soon as we agree on the gc_object structure, I'll make a second
version of gmc_for_dummies.pod.

Thank you very much for your help !

Regards,
Alexandre

Bob Rogers

unread,
Jul 17, 2005, 8:17:50 PM7/17/05
to Nattfodd, Leopold Toetsch, perl6-i...@perl.org
From: Leopold Toetsch <l...@toetsch.at>
Date: Sun, 17 Jul 2005 12:08:34 +0200

> What happens when a store creates a cycle? And how would this be
> detected?

To keep the invariant we can't move the container nor the contained
object, *if* both are aggregates. Therefore the pointer store will be
recorded on the IGP list. Thus there is no need to detect cycles.

But when are objects taken off the IGP list? This is not contemplated
in [1], which explicitly mentions as a drawback that circular structures
cannot be recovered [2], and it is not (yet) addressed in the GMC design
[3]. Is one-pass mark-sweep really a suitable GC algorithm for Parrot?

-- Bob

[1] Armstrong & Virding, "One Pass Real-Time Generational Mark-Sweep
Garbage Collection" (1995),
http://citeseer.csail.mit.edu/armstrong95one.html

[2] ibid, p8.

[3] http://perso.ens-lyon.fr/alexandre.buisse/divers/gmc_design.pod

Leopold Toetsch

unread,
Jul 18, 2005, 10:39:14 AM7/18/05
to Nattfodd, perl6-i...@perl.org
Nattfodd wrote:
> Leopold Toetsch wrote:

> I believe that if we want variable-sized body, we need at least one next
> (or pmc_size) pointer in the header.

Not necessarily. We can have:

- some type bits in the gmc_header for fixed-sized and commonly used
objects, so that GMC knows the size
- alternatevily use an object size field in the vtable
- force variable sized objects to have a word-size at a known object
location e.g. just the first word (like PMC_int_val for current arrays)

Therefore we can always calculate the object size and walk the pmc_body
memory.

> Do you see any other solution that could avoid prev and next ?

We just need a next pointer for managing holes in the pmc_body memory
space. That's basically the same as in a memory allocator.

> Regards,
> Alexandre

leo

Leopold Toetsch

unread,
Jul 18, 2005, 11:08:53 AM7/18/05
to Bob Rogers, Nattfodd, perl6-i...@perl.org
Bob Rogers wrote:
> From: Leopold Toetsch <l...@toetsch.at>
> Date: Sun, 17 Jul 2005 12:08:34 +0200
>
> > What happens when a store creates a cycle? And how would this be
> > detected?
>
> To keep the invariant we can't move the container nor the contained
> object, *if* both are aggregates. Therefore the pointer store will be
> recorded on the IGP list. Thus there is no need to detect cycles.
>
> But when are objects taken off the IGP list? This is not contemplated
> in [1], which explicitly mentions as a drawback that circular structures
> cannot be recovered [2], and it is not (yet) addressed in the GMC design
> [3].

Circular or not isn't really the problem. With generational GC you'll
always have the chance of tenured garbage. E.g.

gen n | gen j
[ A ] | [ C ]
^ |
+----------------------+

We got a reverse pointer, which needs remembering on the IGP list of
generation n. IGPn then becomes part of the root set of this generation
n and the object A is marked and kept alive. So far so good.

Now due to some other pointer store the object C becomes dead. But as
long as we don't scan up to generation j, we don't realize this and
object A stays alive.

This is usually not a problem, just some waste of memory, except when
the object A needs timely destruction. In such a case we would have to
scan more generations, up to generation j in the above case.
As object C belongs to generation j, the IGP entry that marks A would
become invalid, because the object C (and its refered contents) have to
be anchored somwhere else to be alive.

gen n | gen j
[ A ] -> [ B ] -|-----> [ C ]
^ |
+----------------------+

A circular data structure doesn't really change the picture, except,
when again scanning up to generation j, and we find object C being
alive, we'd have to restart scanning at object A, by following the
backreference.
If non of A, B, or C is referenced from elsewhere, we would still delete
the whole reference loop.

> ... Is one-pass mark-sweep really a suitable GC algorithm for Parrot?

I still think it's suitable yes. It's only in the above case that we
can't immediately cleanup A, because of the invalidation of the IGP entry.

> -- Bob

leo

Bob Rogers

unread,
Jul 18, 2005, 10:36:25 PM7/18/05
to Nattfodd, Leopold Toetsch, perl6-i...@perl.org
From: Nattfodd <Natt...@gmail.com>
Date: Tue, 19 Jul 2005 04:03:49 +0200

Leopold Toetsch wrote:

>
> gen n | gen j
> [ A ] -> [ B ] -|-----> [ C ]
> ^ |
> +----------------------+
>
> A circular data structure doesn't really change the picture, except,
> when again scanning up to generation j, and we find object C being
> alive, we'd have to restart scanning at object A, by following the
> backreference.
> If non of A, B, or C is referenced from elsewhere, we would still
> delete the whole reference loop.

Hi,
I don't know how this could work. First, we need more than one pass (if
each alive object in the IGP needs to follow the backreference, this can
lead to between |alive_IGP_set| and 2^|alive_IGP_set| passes...).
And I don't see either how we could check if the loop is referenced from
elsewhere, as the mark is a single bit.

A solution I'm thinking of is using two bits for the marking . . .

I hope there's a (much) more simple way :/
And this is not at all one pass mark&sweep...

Regards,
Alexandre

That's what concerns me. Even if you devise an efficient way to detect
garbage in the IGP list, a straightforward two-pass implementation might
be simpler, and probably faster.

Of course, if you believe that circular structures are rare, then it
might be less of an issue. But that's a dangerous road to traverse; if
circular structures are supported poorly by Parrot, then their rarity
could become a self-fulfilling prophecy.

-- Bob

Nattfodd

unread,
Jul 18, 2005, 10:03:49 PM7/18/05
to Leopold Toetsch, perl6-i...@perl.org
Leopold Toetsch wrote:

>
> gen n | gen j
> [ A ] -> [ B ] -|-----> [ C ]
> ^ |
> +----------------------+
>
> A circular data structure doesn't really change the picture, except,
> when again scanning up to generation j, and we find object C being
> alive, we'd have to restart scanning at object A, by following the
> backreference.
> If non of A, B, or C is referenced from elsewhere, we would still
> delete the whole reference loop.

Hi,


I don't know how this could work. First, we need more than one pass (if
each alive object in the IGP needs to follow the backreference, this can
lead to between |alive_IGP_set| and 2^|alive_IGP_set| passes...).
And I don't see either how we could check if the loop is referenced from
elsewhere, as the mark is a single bit.

A solution I'm thinking of is using two bits for the marking : b0 is
"referenced by an element of the real root set or by an object with b0
set" and b1 is "referenced by an element of the IGP or by an object with
b1 set". Then if we come across such a loop with C being part of IGP, we
check the marking bits of A : if b0 is set, then A is definitely alive,
so do nothing. If b0 is not set, A could be dead. But the problem is
that A could also be referenced by a fourth object, D, which would also
be in the IGP set. The only way I can see to check if it really is dead
is the following : take temporarily C out of the IGP set, then redo
*all* of the marking pass. If b1 is not set, then only C was referencing
it, and we can safely delete it. We then have to mark A as "definitely
dead", set C back on IGP and do once again the marking pass...

Bob Rogers

unread,
Jul 18, 2005, 11:54:21 PM7/18/05
to Nattfodd, Leopold Toetsch, perl6-i...@perl.org
From: Leopold Toetsch <l...@toetsch.at>
Date: Mon, 18 Jul 2005 17:08:53 +0200

Circular or not isn't really the problem. With generational GC you'll

always have the chance of tenured garbage . . .

Now due to some other pointer store the object C becomes dead. But as
long as we don't scan up to generation j, we don't realize this and
object A stays alive.

That's true, but not my point. I don't understand how the IGP mechanism
permits cycles to be collected at all.

. . .

gen n | gen j
[ A ] -> [ B ] -|-----> [ C ]
^ |
+----------------------+

A circular data structure doesn't really change the picture, except,
when again scanning up to generation j, and we find object C being
alive, we'd have to restart scanning at object A, by following the
backreference.
If non of A, B, or C is referenced from elsewhere, we would still delete
the whole reference loop.

So that means you do not use the IGP pointer to A when collecting any
generation <= j, correct? Otherwise, I imagine you'd always decide that
A is alive, and hence B and C.

But what if A, B, and C are all in the same generation? You'd still
need an IGP entry, even though it's not inter-generational, in order to
handle the backpointer, but how would you then decide that it's invalid?

> ... Is one-pass mark-sweep really a suitable GC algorithm for Parrot?

I still think it's suitable yes. It's only in the above case that we
can't immediately cleanup A, because of the invalidation of the IGP entry.

leo

I am willing to believe that there could be an IGP mechanism that would
perform as described, but I haven't yet heard enough to understand it
myself. Perhaps you should save your (metaphorical) breath, and I'll
wait for a more detailed design.

-- Bob Rogers

Leopold Toetsch

unread,
Jul 20, 2005, 4:26:33 AM7/20/05
to Bob Rogers, Nattfodd, perl6-i...@perl.org
Bob Rogers wrote:

> So that means you do not use the IGP pointer to A when collecting any
> generation <= j, correct? Otherwise, I imagine you'd always decide that
> A is alive, and hence B and C.

IGPs entries that span the range of to be collected generations are not
considered (and very likely removed)

> But what if A, B, and C are all in the same generation? You'd still
> need an IGP entry, even though it's not inter-generational, in order to
> handle the backpointer, but how would you then decide that it's invalid?

I don't think this needs an IGP entry. Just a bit POSSIBLE_LOOP, which
prevents early collection of dead objects during the sweep.

> ... Perhaps you should save your (metaphorical) breath, and I'll


> wait for a more detailed design.

I'm waiting too :-)

> -- Bob Rogers

leo

Nattfodd

unread,
Jul 20, 2005, 9:22:04 PM7/20/05
to Leopold Toetsch, perl6-i...@perl.org
Leopold Toetsch wrote:

>> ... Perhaps you should save your (metaphorical) breath, and I'll
>> wait for a more detailed design.
>
>
> I'm waiting too :-)

Hi,
I believe I found a good workaround for the cycle problems. It is a
little bit slower and worst case (which never occurs, happily) is
|IGP_set| passes, but should really be about 2 passes. But we need of
course not to run it each time. We can have 'classical' gmc most of the
time and once in a while, run NLDC (Night of the Living Dead Collection)
to get rid of evil IGP dead cycles.

Here is how NLDC works :

We do not care at all about generations. First, make a normal marking
pass, but without even considering the IGP set at all. Just see members
of the IGP set (origin and destination of the pointer) as normal objects.
Then, operation "Night of the Living Dead" begins (hence the name) : get
out of their graves objects that shouldn't have been buried first. Run
through the IGP set in reverse order of age of origin pointers. For each
(p0 -> p1) element in the IGP, do the following : if p0 is marked dead,
then do nothing and leave it dead. If it is marked alive, apply a
recursive procedure :

to_process := [p1];
while (to_process != []) {
p = pop (to_process);
if (p is dead) {
mark p alive;
forall (p -> q) in IGP { push (q, to_process) }
push (all childrens of p, to_process);
}
}

And then proceed with compaction as usual. This ensures us that dead
cycles have been destroyed and that every alive object has been marked so.

Here is how it works. Consider a dead cycle :

[A] --> [B] --> [C]
^ |
+--------------------+

In the first run, the C->A link does not exist. Thus, as A, B and C are
not referenced from elsewhere, they are all marked dead. And in NLD
pass, C being dead, no object of the cycle comes back to life and it can
safely go to hell.

If now, for instance B is referenced from the vast outer world, A is
dead but B and C as marked alive after the first pass. Thus C is marked
alive and we apply the recursive function that just rescues A.

Some cases are just a little trickier :

For instance :

|
v
[A] --> [B] --> [C]
^ |
| +---+
| v
| [D] --> [E] --> [F]
| |
+----------------------------------------+


We have C->D and F->A in the IGP set, and B is referenced from the outer
world. Thus, the whole cycle is alive.
After the first pass, only B and C are marked alive. In NLD pass, we
first check F and find it dead, thus do nothing. Next is C, which is
alive. And, thanks to the "forall (p->q) in IGP...", we add D to the
living, and then the whole cycle.

I discussed it with friends and think it can even be proved to work
right (but that would take some time :/).

Does that sound reasonable to you ?

Regards,
Alexandre

Leopold Toetsch

unread,
Jul 16, 2005, 10:37:25 AM7/16/05
to Nattfodd, perl6-i...@perl.org
Nattfodd wrote:
> Leopold Toetsch wrote:

>>1) pmc_bodies have to be variable sized
>
> Oh, I believed that we would use variable-sized pmc only if the gc
> proved to work really well.

Well, with fixed sized bodies, we don't need the extra indirection.

But I really like to have a more flexible object layout. Have a look at
Parrot sources and draw a picture of an object with 2 attributes, or a
FixedSizedXXArray or a Sub PMC ... All the interesting, needed and
heavily used data are hanging off some extra pointers inside malloced
structures. I just want that to be (in) the body.

> Then we use a doubly linked list, but that should be no problem. The
> structure becomes something like :

Well, gc_gms has already this layout, with prev and next pointers inside

the gc_header. But in gc_gms it is needed, because you can't move the
PMC memory w/o indirection pointer into a different object generation.

But I consider 4 words for GC + 1 indirection pointer as a very big
overhead, even compared to the current situation. So I'd really not like
to have these 2 extra pointers, and I don't think that they are needed.

>>There is no need for any extra todo-list to mark the children of objects.


>
>
> ???
> I believe that was pretty much what was described in the document. What
> I called "pointers an object has to other objects" is simply its contents.

You write in the pod:


* Mark all elements of the root set and add them to a queue (or a
stack, whatever) somewhere

But it isn't really clear what you are trying to achieve here.

> So you mean that we allocate :


>
> | xxx[aggregates]xxx... ...[free space]... ...xxx[non-aggregates]xxx |

Yep.

> Or rather, as I thought :
>
> | ...[free space]... ...xxx[some aggregate][its contents][some
> aggregate][its contents]xxx |

That's probably suboptinal for ususal cases like filling an array with
some values.

>>c) a write barrier checks pointer stores into aggregates (by just


>>comparing 2 memory addresses - basically)
>
> Another question I had is how do we know when there is such a pointer
> store ? It can happen at other moments than object allocation, right ?

Well, that is exactly what the write barrier is for. Grep for

WRITE_BARRIER in the parrot sources.

>> we can do either:


>> - make aggregate younger (move to left)
>> - make stored-into object older (move to right)
>> - remember in IGP
>>d) if we have to extend the allocation area, we usually we'll have to
>>move all existing objects "up", either by a full GC run or by just
>>copying, because you'll get usually higher memory regions from the OS.

> Hum, I hadn't thought of this problem.

You should :-)

leo

Bob Rogers

unread,
Jul 24, 2005, 10:32:32 PM7/24/05
to Nattfodd, Leopold Toetsch, perl6-i...@perl.org
From: Nattfodd <Natt...@gmail.com>
Date: Thu, 21 Jul 2005 03:22:04 +0200

Leopold Toetsch wrote:

>> ... Perhaps you should save your (metaphorical) breath, and I'll
>> wait for a more detailed design.
>
>
> I'm waiting too :-)

Hi,
I believe I found a good workaround for the cycle problems. It is a
little bit slower and worst case (which never occurs, happily) is
|IGP_set| passes, but should really be about 2 passes. But we need of
course not to run it each time. We can have 'classical' gmc most of the
time and once in a while, run NLDC (Night of the Living Dead Collection)
to get rid of evil IGP dead cycles.

;-}

Here is how NLDC works :

We do not care at all about generations. First, make a normal marking
pass, but without even considering the IGP set at all. Just see members
of the IGP set (origin and destination of the pointer) as normal objects.
Then, operation "Night of the Living Dead" begins (hence the name) : get
out of their graves objects that shouldn't have been buried first. Run
through the IGP set in reverse order of age of origin pointers. For each
(p0 -> p1) element in the IGP, do the following : if p0 is marked dead,
then do nothing and leave it dead. If it is marked alive, apply a
recursive procedure :

to_process := [p1];
while (to_process != []) {
p = pop (to_process);
if (p is dead) {
mark p alive;
forall (p -> q) in IGP {
push (q, to_process);
}
push (all childrens of p, to_process);
}
}

I'm still digesting it (and trying to bone up on GC algorithms at the
same time), but it does sound like it should work. I assume that
"forall (p -> q)" above really means "forall (q0 -> q where q0 == p)",
i.e. process all IGP entries from p.

However, except for the IGP loop, this is essentially the mark phase
of a two-pass algorithm. So if we know that p is live, and we're going
to mark the children of p as live, then we shouldn't also have to go
through the IGP entries for p at this point, should we?

FWIW, it might be better if you were to add only dead children to the
to_process queue:

to_process := [p1];
while (to_process != []) {
p = pop (to_process);

# assume p is dead
mark p alive;
forall child in children(p) {
if (child is dead) {
push (child, to_process);
}
}
}

At the very least, this would require a smaller to_process queue in the
typical case.

For the record, is it acceptable in Parrot to use page
write-protection to record whether oldspace objects have been modified
since the last full GC? This is what CMUCL does on most ports, but it
occurs to me that this might be a porting headache for Parrot.

. . .

I discussed it with friends and think it can even be proved to work
right (but that would take some time :/).

Does that sound reasonable to you ?

Regards,
Alexandre

Even an outline of a proof would help to identify hidden assumptions.
Especially valuable would be to prove bounds on storage and time costs.
But of course it's your time, so it's your call. (I'll holler if I find
any counterexamples, but I've been short on time lately.)

-- Bob Rogers
http://rgrjr.dyndns.org/

Nicholas Clark

unread,
Jul 25, 2005, 5:15:33 AM7/25/05
to Bob Rogers, Nattfodd, Leopold Toetsch, perl6-i...@perl.org
On Sun, Jul 24, 2005 at 10:32:32PM -0400, Bob Rogers wrote:

> For the record, is it acceptable in Parrot to use page
> write-protection to record whether oldspace objects have been modified
> since the last full GC? This is what CMUCL does on most ports, but it
> occurs to me that this might be a porting headache for Parrot.

It's not a porting headache if it's not the only option. If it's viable
to use a different, slower strategy where this is not available, or a different
GC, then parrot will still run.

Nicholas Clark

Alexandre Buisse

unread,
Jul 25, 2005, 9:06:14 PM7/25/05
to Bob Rogers, perl6-i...@perl.org
On 7/25/05, Bob Rogers <rogers...@rgrjr.dyndns.org> wrote:
> I'm still digesting it (and trying to bone up on GC algorithms at the
> same time), but it does sound like it should work. I assume that
> "forall (p -> q)" above really means "forall (q0 -> q where q0 == p)",
> i.e. process all IGP entries from p.

Yes, that's what I meant.
I am sorry not to have told everyone before, but I discussed with leo
on IRC and the scheme he originally envisionned is actually very close
to NLDC and more simple : simply do the NLD pass at the same time than
the marking pass. But the underlying idea of collecting the IGP cycles
remains the same.
There is also the problem of no wanting to mark the whole memory but
only a given number of generations which is addresses this way.


> FWIW, it might be better if you were to add only dead children to the
> to_process queue:
>
> to_process := [p1];
> while (to_process != []) {
> p = pop (to_process);
> # assume p is dead
> mark p alive;
> forall child in children(p) {
> if (child is dead) {
> push (child, to_process);
> }
> }
> }
>
> At the very least, this would require a smaller to_process queue in the
> typical case.

That's a good idea, thanks.


> Even an outline of a proof would help to identify hidden assumptions.
> Especially valuable would be to prove bounds on storage and time costs.
> But of course it's your time, so it's your call. (I'll holler if I find
> any counterexamples, but I've been short on time lately.)

Well, I'll try to provide a sketch of it, but not now.
Actually, I had some laptop problems which should hopefully be fixed
soon. As time is beginning to run short (remember that the GC should
be functional by Sept. 1st), I'll rewrite GMC for dummies very soon
(tomorrow ?) and hope to begin coding just after that.

Regards,
Alexandre

Bob Rogers

unread,
Jul 25, 2005, 10:33:37 PM7/25/05
to Alexandre Buisse, perl6-i...@perl.org
From: Alexandre Buisse <natt...@gmail.com>
Date: Tue, 26 Jul 2005 03:06:14 +0200

I am sorry not to have told everyone before, but I discussed with leo
on IRC and the scheme he originally envisionned is actually very close
to NLDC and more simple : simply do the NLD pass at the same time than
the marking pass. But the underlying idea of collecting the IGP cycles
remains the same.
There is also the problem of no wanting to mark the whole memory but
only a given number of generations which is addresses this way.

This is sounding more and more like the CMUCL gencgc algorithm, which
uses what I understand is a classic approach. Instead of an IGP list,
it write-protects all oldspace pages (hence my earlier question),
unprotecting them transparently when one is stored into, so that it only
needs to scan writable pages to look for newspace pointers. It is my
intuition that this would be less overhead than an IGP list, but I
suspect this is data-dependent, and would take benchmarking to prove.

> Even an outline of a proof would help to identify hidden assumptions.
> Especially valuable would be to prove bounds on storage and time costs.

> But of course it's your time, so it's your call . . .

Well, I'll try to provide a sketch of it, but not now.

That's OK; if Leo believes it will work, then I'm sure it will. My
quibbles were about speed and complexity, and I don't want to distract
you with unproven assertions about things that might not matter.

Actually, I had some laptop problems which should hopefully be fixed
soon. As time is beginning to run short (remember that the GC should
be functional by Sept. 1st), I'll rewrite GMC for dummies very soon
(tomorrow ?) and hope to begin coding just after that.

Regards,
Alexandre

Great; I look forward to it.

-- Bob

Bob Rogers

unread,
Jul 25, 2005, 10:00:30 PM7/25/05
to Nicholas Clark, perl6-i...@perl.org
From: Nicholas Clark <ni...@ccl4.org>
Date: Mon, 25 Jul 2005 10:15:33 +0100

Nicholas Clark

Very true. But someone still has to decide whether the disadvantages
(greater code volume, platform-dependent bugs) are acceptable.

-- Bob

Nattfodd

unread,
Jul 26, 2005, 6:04:04 PM7/26/05
to perl6-i...@perl.org
Hi,

I began putting the ideas of the documents in form.
For now, only the data structures are there but I think they look quite
nice. There are still some things lacking (mainly how the UINTVAL flags;
field of Gc_gmc_hdr will be used : I think that one or two bits for
marking plus some bits for recognition of frequently used PMC would be
fine. Other PMC would have a size field in the vtable).

You can find a version of the modified file here :

http://perso.ens-lyon.fr/alexandre.buisse/gmc/smallobject.h


Leo, I don't know if you want me to commit my files to the svn ? I have
of course included #if PARROT_GC_GMC everywhere so it should be pretty
safe unless you set #PARROT_GC_SYSTEM to 3 in include/parrot/settings.h

If that's the case, my perl.org account is named 'heimdall' (I don't
know how to change it for 'Nattfodd', sorry).

Regards,
Alexandre

Ed Mooring

unread,
Jul 29, 2005, 2:44:34 AM7/29/05
to perl6-i...@perl.org
On Mon, Jul 25, 2005 at 10:33:37PM -0400, Bob Rogers wrote:
[snip]

>
> This is sounding more and more like the CMUCL gencgc algorithm, which
> uses what I understand is a classic approach. Instead of an IGP list,
> it write-protects all oldspace pages (hence my earlier question),
> unprotecting them transparently when one is stored into, so that it only
> needs to scan writable pages to look for newspace pointers. It is my
> intuition that this would be less overhead than an IGP list, but I
> suspect this is data-dependent, and would take benchmarking to prove.
>

On a POSIX-ish OS, this approach involves a system call to change the
protection on each page, plus a signal handler that gets invoked whenever
such a page is stored into, and then another system call to unprotect the
page.

[snip]


>
> That's OK; if Leo believes it will work, then I'm sure it will. My
> quibbles were about speed and complexity, and I don't want to distract
> you with unproven assertions about things that might not matter.

System calls aren't cheap, and page table manipulations are not
necessarilly cheap either. Whether this performance tradeoff is worth it
is going to be both OS- and processor-specific. It also lurches into the
realm of signal handlers, where POSIX guarantees very little behavior
that is portable behavior, but operating systems may allow much more,
but the allowed behaviors form an ever-changing and largely disjoint set.

In summary, just about any algorithm that avoids page table manipulations
and signal handlers is likely to be more portable, and will quite likely
be faster.
--
Ed M

Reply all
Reply to author
Forward
0 new messages