New generational GC Scheme
Alexandre Buisse
https://rt.perl.org/rt3//Ticket/Display.html?id=33922, here is the
scheme proposal for a new parrot GC (many thanks to leo for his help).
=================================================================
In order to allow more powerful GC schemes, we need to be able to copy
objects from a location of memory to another. There are problems with
this, though, as C structures can hold pointers to objects we are
moving, and we have no way (and don't want to) to make them update
this info.
So we add a level of indirection: objects consist of a header and the
actual data. Headers are allocated once and for all at object creation
and do not move. They only hold a pointer to the 'real' object, thus
making it possible to move objects anywhere in the memory. Outside
functions will see the header address as the object address and some
internal macros will handle the extra indirection.
The big disadvantage of this approach is that we use one or two words
(if objects need to know where their header is, which seems
reasonable) per object.
We then use a generational, incremental mark-and-sweep algorithm, such
as described by http://citeseer.csail.mit.edu/armstrong95one.html
We have different generations (in fact queues) of objects, from 1 to
n-1 (the value of n could be tuned dynamically). We also have two
special generations, n, where objects do not grow old (to take care of
timely destruction) and 0, where objects are very constant and
long-lived (mainly used during parrot init). Objects in a generation
are also sorted according to their age.
The idea is to have the following invariant: all pointers go from new
objects to old objects. Thus, we can mark all objects in only one
pass, starting from the newest objects, generation n (using a
Eratosthene-sieve-like method : if an object is not marked, leave it,
else mark all of its pointers). When an entire generation has been
processed, all non-marked objects are destroyed and the others are
compacted. Generation n becomes generation n-1, with the exceptions of
generation 0 and n.
Comparing the age of two objects then becomes very easy : if they are
in different generations, just compare their numbers. If not, the one
with the lower address is the youngest.
We can of course use a generational approach by limiting the number of
non-marked objects.
One problem is that our invariant can be broken. The solution is to
track down these inter-generational pointers (IGP) and simply add them
to the root set.
In order to reduce the number of IGP, we allocate an aggregate as
being artificially younger than scalars it has pointers to.
Keywords: generational, mark-and-sweep, copying
=================================================================
What do you think of it ?
Regards
Alexandre
Jerry Gay
alexandre on #parrot.
On 6/8/05, Alexandre Buisse <natt...@gmail.com> wrote:
> Following google SoC and TODO item,
> https://rt.perl.org/rt3//Ticket/Display.html?id=33922, here is the
> scheme proposal for a new parrot GC (many thanks to leo for his help).
>
> =================================================================
>
> In order to allow more powerful GC schemes, we need to be able to copy
> objects from a location of memory to another. There are problems with
> this, though, as C structures can hold pointers to objects we are
> moving, and we have no way (and don't want to) to make them update
> this info.
>
> So we add a level of indirection: objects consist of a header and the
> actual data. Headers are allocated once and for all at object creation
> and do not move. They only hold a pointer to the 'real' object, thus
> making it possible to move objects anywhere in the memory. Outside
> functions will see the header address as the object address and some
> internal macros will handle the extra indirection.
>
> The big disadvantage of this approach is that we use one or two words
> (if objects need to know where their header is, which seems
> reasonable) per object.
>
since threading issues haven't been mentioned here, i thought i'd make
sure they get discussed. now, if someone could say something
intelligent about threading issues with this gc scheme, we can start
the discussion :-)
>
> We then use a generational, incremental mark-and-sweep algorithm, such
> as described by http://citeseer.csail.mit.edu/armstrong95one.html
>
> We have different generations (in fact queues) of objects, from 1 to
> n-1 (the value of n could be tuned dynamically). We also have two
"tuned dynamically", as in at run-time? alexandre mentioned this may
be possible on #parrot, but there may be trouble with decreasing the
generation count. i don't know if run-time tuning of the generation
count is necessary, but if so, i imagine that decreasing the count at
run-time could be achieved by merging generations.
if this gc is tunable at build-time, it should be configurable such
that timely destruction can be disabled. after all, most languages
just don't need it, so why should they have the overhead?
> special generations, n, where objects do not grow old (to take care of
> timely destruction) and 0, where objects are very constant and
> long-lived (mainly used during parrot init). Objects in a generation
> are also sorted according to their age.
it's not mentioned specifically how timely destruction will be
addressed. i suggest that there be a special type of gc run on scope
exit which examines only the special "generation n", ensuring timely
destruction without the overhead of a full gc run.
> The idea is to have the following invariant: all pointers go from new
> objects to old objects. Thus, we can mark all objects in only one
> pass, starting from the newest objects, generation n (using a
> Eratosthene-sieve-like method : if an object is not marked, leave it,
> else mark all of its pointers). When an entire generation has been
> processed, all non-marked objects are destroyed and the others are
> compacted. Generation n becomes generation n-1, with the exceptions of
> generation 0 and n.
> Comparing the age of two objects then becomes very easy : if they are
> in different generations, just compare their numbers. If not, the one
> with the lower address is the youngest.
> We can of course use a generational approach by limiting the number of
> non-marked objects.
>
> One problem is that our invariant can be broken. The solution is to
> track down these inter-generational pointers (IGP) and simply add them
> to the root set.
> In order to reduce the number of IGP, we allocate an aggregate as
> being artificially younger than scalars it has pointers to.
>
>
> Keywords: generational, mark-and-sweep, copying
>
> =================================================================
>
> What do you think of it ?
>
good start! and since the gc is modular, it should be straightforward
to implement this without affecting the existing gc--that should make
it easier to develop and test.
>
> Regards
>
> Alexandre
>
~jerry
Klaas-Jan Stol
>"tuned dynamically", as in at run-time? alexandre mentioned this may
>be possible on #parrot, but there may be trouble with decreasing the
>generation count. i don't know if run-time tuning of the generation
>count is necessary, but if so, i imagine that decreasing the count at
>run-time could be achieved by merging generations.
>
>if this gc is tunable at build-time, it should be configurable such
>that timely destruction can be disabled. after all, most languages
>just don't need it, so why should they have the overhead?
>
>
this gc with timely destruction disabled, can't run languages that do
need the gc with timely destruction, right? (there goes your
inter-language operability...)
If so, then this would make that Parrot rather ... ehm, disabled :-)
(anyway, this is only important when this tuning is done at build-time)
klaas-jan
Leopold Toetsch
> i'm no gc expert, but here's my comments after discussions with
> alexandre on #parrot.
>
> On 6/8/05, Alexandre Buisse <natt...@gmail.com> wrote:
> since threading issues haven't been mentioned here, i thought i'd make
> sure they get discussed. now, if someone could say something
> intelligent about threading issues with this gc scheme, we can start
> the discussion :-)
A thread has typically some objects in it's local memory arena and may
refer to shared objects, located in some other arena. We now have two cases:
1) a local GC run in the threads arena
2) GC of the shared arena
Case 1) is simple as it's fully private to the thread. A non-shared
object can not be referenced by a shared one, therefore all local
garbage can be identified.
For the shared case 2) things get more complicated. Something like this
might happen:
- a "global GC start event" is triggered
- all threads must meet at a rendevous point
- all threads start a mark phase, shared items are marked either inside
a mutex lock or faster with an atomic BTS or CAS [1]
- threads can continue to run code or run a private GC too (as the mark
is already done)
- the owner of the shared arena waits for all threads to finish mark
- the owner of the shared arena collects garbage
>>We then use a generational, incremental mark-and-sweep algorithm, such
>>as described by http://citeseer.csail.mit.edu/armstrong95one.html
>>
>>We have different generations (in fact queues) of objects, from 1 to
>>n-1 (the value of n could be tuned dynamically). We also have two
>
> "tuned dynamically", as in at run-time? alexandre mentioned this may
> be possible on #parrot, but there may be trouble with decreasing the
> generation count. i don't know if run-time tuning of the generation
> count is necessary, but if so, i imagine that decreasing the count at
> run-time could be achieved by merging generations.
Yep. We'd have usually 3 generations: constant / old / new. But if a
scope emit's code that it need timely destruction it seems best to just
make this scope one generation. On scope exit all remaining objects get
merged with the previous generation.
> if this gc is tunable at build-time, it should be configurable such
> that timely destruction can be disabled. after all, most languages
> just don't need it, so why should they have the overhead?
You don't disable timely destruction. In the absence of some special
scope_enter / scope_exit opcodes, there is no timely destruction. It
only depends on the code that parrot executes.
> good start! and since the gc is modular, it should be straightforward
> to implement this without affecting the existing gc--that should make
> it easier to develop and test.
At the beginning GC is modular, yes. But if this concepts works and
works fast, then we have the opportunity to use variable-sized PMC
bodies. This simplifies e.g. objects vastly. An object is then just an
attribute count + a fixed sized piece of memory w/o any indirection
(plus the usual PMC stuff).
>>Regards
>>
>>Alexandre
>>
>
> ~jerry
leo
[1] bit test and set / compare and swap
Sam Vilain
> So we add a level of indirection: objects consist of a header and the
> actual data. Headers are allocated once and for all at object creation
> The big disadvantage of this approach is that we use one or two words
> (if objects need to know where their header is, which seems
> reasonable) per object.
AIUI, another effect of adding another indirection to every pointer lookup,
is that it will place a little extra stress on the memory caching systems,
as two regions will need to be accessed continually.
Sam.
Leopold Toetsch
> AIUI, another effect of adding another indirection to every pointer lookup,
> is that it will place a little extra stress on the memory caching systems,
> as two regions will need to be accessed continually.
Yes, that's of course true. But please compare:
now indirect access
pmc->int_val pmc->body->int_val # or num_val
pmc->pmc_ext->data[1] pmc->body[N + 1] # object 2nd attr
That means, we loose a bit with currently optimized Integer and Float
PMCs (for which we have natural data access too) and win with tuples
(fixed-sized or small arrays) and objects.
> Sam.
leo
Alexandre Buisse
On 6/8/05, Leopold Toetsch <l...@toetsch.at> wrote:
> jerry gay wrote:
> > i'm no gc expert, but here's my comments after discussions with
> > alexandre on #parrot.
> >
> > On 6/8/05, Alexandre Buisse <natt...@gmail.com> wrote:
>
> > since threading issues haven't been mentioned here, i thought i'd make
> > sure they get discussed. now, if someone could say something
> > intelligent about threading issues with this gc scheme, we can start
> > the discussion :-)
>
> A thread has typically some objects in it's local memory arena and may
> refer to shared objects, located in some other arena. We now have two cases:
>
> 1) a local GC run in the threads arena
> 2) GC of the shared arena
>
> Case 1) is simple as it's fully private to the thread. A non-shared
> object can not be referenced by a shared one, therefore all local
> garbage can be identified.
Does that mean that we have a gc structure in each arena (which, as
far as I understand parrot design, is similar to a process memory
space) ? Or is a gc rather attached to a thread or a shared arena ?
(My question could be restated in : "are we sure that a thread only
uses one arena for its local storage ?").
> For the shared case 2) things get more complicated. Something like this
> might happen:
>
> - a "global GC start event" is triggered
> - all threads must meet at a rendevous point
> - all threads start a mark phase, shared items are marked either inside
> a mutex lock or faster with an atomic BTS or CAS [1]
> - threads can continue to run code or run a private GC too (as the mark
> is already done)
> - the owner of the shared arena waits for all threads to finish mark
> - the owner of the shared arena collects garbage
This seems the simplest way to perform it. I am not sure I understand
why threads must meet at a rendezvous point, though. Couldn't they
just stop what they were doing, mark their shared items and go on ?
There is also something else about the locks (but it may be what you
call BTS or CAS) : it is the gc of the owner of the arena that should
have all the locks, and release them when he's done with the
compaction phase (because we know objects won't move anymore). And
then we'd need all the threads to meet at a rendezvous point, but only
_after_ the marking phase. They wait for the gc to have said "I have
all the locks" and then go on. Of course, if they want access of the
objects before the gc is done, they will have to sleep, which makes
this part really critical for the system speed and safety.
> >>We then use a generational, incremental mark-and-sweep algorithm, such
> >>as described by http://citeseer.csail.mit.edu/armstrong95one.html
> >>
> >>We have different generations (in fact queues) of objects, from 1 to
> >>n-1 (the value of n could be tuned dynamically). We also have two
> >
> > "tuned dynamically", as in at run-time? alexandre mentioned this may
> > be possible on #parrot, but there may be trouble with decreasing the
> > generation count. i don't know if run-time tuning of the generation
> > count is necessary, but if so, i imagine that decreasing the count at
> > run-time could be achieved by merging generations.
>
> Yep. We'd have usually 3 generations: constant / old / new. But if a
> scope emit's code that it need timely destruction it seems best to just
> make this scope one generation. On scope exit all remaining objects get
> merged with the previous generation.
I was thinking about the possible advantages of using more
generations. One could be that it allows more fine-tuning of memory we
allocate. I think we won't be malloc/freeing our generations all the
time, but only malloc the overhead when needed, and never free it. If
we want the generation to be a whole, we have to copy everything in it
(which costs much), if not, we have an array splitted in many parts,
which can be imho better described by several generations.
So allocating more space is adding a generation. And if we see that we
have many empty generations, we can just delete them and free the
unused memory.
> > if this gc is tunable at build-time, it should be configurable such
> > that timely destruction can be disabled. after all, most languages
> > just don't need it, so why should they have the overhead?
>
> You don't disable timely destruction. In the absence of some special
> scope_enter / scope_exit opcodes, there is no timely destruction. It
> only depends on the code that parrot executes.
>
> > good start! and since the gc is modular, it should be straightforward
> > to implement this without affecting the existing gc--that should make
> > it easier to develop and test.
>
> At the beginning GC is modular, yes. But if this concepts works and
> works fast, then we have the opportunity to use variable-sized PMC
> bodies. This simplifies e.g. objects vastly. An object is then just an
> attribute count + a fixed sized piece of memory w/o any indirection
> (plus the usual PMC stuff).
I will begin to dig into parrot source, and hope I will be able to
start coding soon, if everyone is ok with the current design.
Regards
Alexandre
PS: sorry, I had forgotten to Cc: perl6-internals
Leopold Toetsch
> On 6/8/05, Leopold Toetsch <l...@toetsch.at> wrote:
>>1) a local GC run in the threads arena
>>2) GC of the shared arena
>>
>>Case 1) is simple as it's fully private to the thread. A non-shared
>>object can not be referenced by a shared one, therefore all local
>>garbage can be identified.
>
>
> Does that mean that we have a gc structure in each arena (which, as
> far as I understand parrot design, is similar to a process memory
> space) ?
Object memory organization WRT threads isn't yet finally specified. But
to me it seems that separating memory areas for threads is the best
approach. Most of the objects created are temporaries and cleaning these
is therefore a thread-local operaion.
> ...Or is a gc rather attached to a thread or a shared arena ?
> (My question could be restated in : "are we sure that a thread only
> uses one arena for its local storage ?").
Yep. When a new )threaded) interpreter is created it also creates it's
own memory area (interpreter->arena_base). The question remains of
course, how the shared resources are managed.
>>For the shared case 2) things get more complicated. Something like this
>>might happen:
>>
>>- a "global GC start event" is triggered
>>- all threads must meet at a rendevous point
>>- all threads start a mark phase, shared items are marked either inside
>>a mutex lock or faster with an atomic BTS or CAS [1]
>>- threads can continue to run code or run a private GC too (as the mark
>>is already done)
>>- the owner of the shared arena waits for all threads to finish mark
>>- the owner of the shared arena collects garbage
>
>
> This seems the simplest way to perform it. I am not sure I understand
> why threads must meet at a rendezvous point, though. Couldn't they
> just stop what they were doing, mark their shared items and go on ?
Well, yes that is the rendevous point.
> I will begin to dig into parrot source, and hope I will be able to
> start coding soon, if everyone is ok with the current design.
Before coding I'd like to have a much more detaild paper WRT GC strategy
and implementation. This can of course be a src file too, with "the
plan" inside as comments and a code outline.
> Regards
>
> Alexandre
leo