[gambit-list] parallel GC

Marc Feeley feeley at iro.umontreal.ca
Mon Nov 7 23:31:00 EST 2016


> On Nov 7, 2016, at 9:50 PM, Adam <adam.mlmb at gmail.com> wrote:
> 
> Aha. Just out of general interest,
> 
>  * Per GC cycle, how much time are we talking on a random 2Ghz machine, and presuming all GVM threads run all-safe-declared Scheme code only?

It depends on the number of CPUs on your machine (because the cost of synchronization goes up with the number of processors).  For 4 CPUs on a 2.6 GHz machine and a minimum size heap, a GC cycle (which of course includes all the synchronizations) takes about 100 microseconds.

> 
>  * What is the mechanism of the sync to initiate a GC iteration - the first initiating thread setting some global variable, msyinc:ing, and all other GVM threads polling it all the time, or/and by sending some kind of interrupt signal via OS facilities?
> 
>  * What is the mechanism of the sync for different GC stages - …?

The phases of the GC are:

1) Setup the stacks and heaps of all the processors
2) Mark the objects that are reachable strongly from roots
3) Mark the objects that are reachable weakly
4) Process gc hash tables and free unreachable still objects
5) Resize heap

These phases are separated by synchronization barriers (so all processors must have finished a phase before any processor starts the next one).

The barrier synchronizations are implemented using a binary tree like structure and time-limited spin-barriers to synchronize a parent processor with its 2 children.  So a barrier takes logarithmic time.

To initiate a garbage collection, a processor raises a flag in all the other processor state structures and sends each processor a dummy byte in its self-pipe that is always checked by "select" (this is to ensure that processors waiting on I/O will stop waiting and enter the garbage collector).

Marc





More information about the Gambit-list mailing list