Ulterior Reference Counting for DoD?
oz...@algorithm.com.au
I know approximately zero about the DoD and GC mechanisms which are
currently used by Parrot, but I did attend a talk a few weeks ago about
a promising new method of garbage collection called Ulterior Reference
Counting:
<http://www.cs.purdue.edu/homes/hosking/690M/urc-oopsla-2003.pdf>
Two-line summary:
* gives as good performance as the best generational garbage
collectors today, with
* even better latencies than the best reference counting mechanisms
today
In a nutshell, it combines the RC and generational techniques so that
generational collection is used for young objects in the nursery, and
RC is used for old objects.
I don't know if you guys would be keen on replacing the current DoD
mechanism with something more superior, but I thought I'd post a
heads-up about it if the GC needs to be reworked at some point in the
future.
Cheers,
--
% Andre Pang : trust.in.love.to.save
Luke Palmer
> Hi guys,
>
> I know approximately zero about the DoD and GC mechanisms which are
> currently used by Parrot, but I did attend a talk a few weeks ago about
> a promising new method of garbage collection called Ulterior Reference
> Counting:
>
> <http://www.cs.purdue.edu/homes/hosking/690M/urc-oopsla-2003.pdf>
>
> Two-line summary:
>
> * gives as good performance as the best generational garbage
> collectors today, with
> * even better latencies than the best reference counting mechanisms
> today
>
> In a nutshell, it combines the RC and generational techniques so that
> generational collection is used for young objects in the nursery, and
> RC is used for old objects.
It looks promising. I'm not sure if Parrot needs it, though. The DOD
phase is relatively low latency (as compared to, eg. Sun Java). But
parrot hasn't seen the likes of big, memory hungry projects yet.
I say it's worth looking into, and if not now, keeping it in mind if we
do run into problems.
Luke
Leopold Toetsch
> Hi guys,
> <http://www.cs.purdue.edu/homes/hosking/690M/urc-oopsla-2003.pdf>
> Two-line summary:
> * gives as good performance as the best generational garbage
> collectors today, with
All these generational collectors don't work with Parrot objects. We
guarantee that objects don't move around.
leo
oz...@algorithm.com.au
Oh, I didn't see a mention of this in a PDD. What's the reason for why
you provide such a guarantee? Just curious.
Leopold Toetsch
PMCs are passed on to (external) C code. When inmidst of C code the
PMC moves around things break horribly--as they now break with the
copying collector when you do:
char *c = string->strstart;
...
<GC runs e.g. triggered by string_compare>
...
do something with c
leo
Piers Cawley
I know it's extra indirection, but maybe we should be passing pointers
to pointers rather than plain pointers to C functions. It could be a
win if that gets us faster GC...
Gerald Butler
the update of the pointer to the pointer ATOMIC? If you don't, it doesn't
matter how many layers of indirection you have, it will still be a problem....
;^)
Leopold Toetsch <l...@toetsch.at> writes:
The information contained in this e-mail message is privileged and/or
confidential and is intended only for the use of the individual or entity
named above. If the reader of this message is not the intended recipient,
or the employee or agent responsible to deliver it to the intended
recipient, you are hereby notified that any dissemination, distribution or
copying of this communication is strictly prohibited. If you have received
this communication in error, please immediately notify us by telephone
(330-668-5000), and destroy the original message. Thank you.
Leopold Toetsch
[ message history rearranged - please don toppost - I hope that got the
right levels of indentation ]
> From: Piers Cawley [mailto:pdca...@bofh.org.uk]
>> Leopold Toetsch <l...@toetsch.at> writes:
>>> PMCs are passed on to (external) C code. When inmidst of C code the
>>> PMC moves around things break horribly--as they now break with the
>>> copying collector when you do:
>> I know it's extra indirection, but maybe we should be passing pointers
>> to pointers rather than plain pointers to C functions. It could be a
>> win if that gets us faster GC...
That *if* is the problem. And it depends on the number of active and
dead objects and possibly multiple other factors. "Normally" mark and
sweep collection is faster, there is no overhead like write barriers,
but you can of course construct benchmarks that reverse the result. You
can construct benchmarks for everything :)
And please note that all these GC papers (at least these what I have
read) are focused on JVM, which is a stack machine. I don't know, if
there is much difference, when it comes to GC, but anyway we don't have
any numbers that indicate a generational (or incremental or refcounting
or combined) scheme could be faster.
Translating some of these JVM spec benchs to PIR could show some
numbers but I didn't have a look at these programs and I don't know, how
complex they are.
> How do you make the copy/move of the object from one location in
> memory and the update of the pointer to the pointer ATOMIC? If you
> don't, it doesn't matter how many layers of indirection you have, it
> will still be a problem....
This is only relevant for incremetal collectors running in the
background. The double indirection could look like (AFAIK)
pmc->pool_pointer->pmc_memory
All code only sees the pmc pointer. During generational GC the
pool_pointer and its memory is moved into an area where the pool of old
generation isn't scanned for dead objects during each DOD run. The win
is, that you are only going through the short lived objects pool mosts of
the time.
This would of course mean that each PMC operation has it's indirection
penalty:
pmc->pool_pointer->vtable->do_something(interp,
pmc->pool_pointer->cache.int_val,
...
Incremental and/or background collectors additionally have to track each
object's pointer changes (e.g. a PMC reference now points to a different
PMC, or all changes to aggregate members) This all imposes a considerable
overhead, which isn't faster "normally".
leo
[ and please hide that mess behind a signature if possible ]
> The information contained
Piers Cawley
> How do you make the copy/move of the object from one location in
> memory and the update of the pointer to the pointer ATOMIC? If you
> don't, it doesn't matter how many layers of indirection you have, it
> will still be a problem.... ;^)
You only do it during allocation so nothing outside the allocator sees
anything move.