When to check whether GC is needed?

Question

I am writing a compiler for a garbage collected language, and am confused about how I know when I should run the garbage collector.

There are two ways that I can think of:

1. To put a GC check before every heap allocation. Therefore, if any allocation is about to fail, we run the GC.

2. To run the GC check "periodically", and perform a GC sweep once we are "dangerously" low on space.

I am using the second scheme currently, thus I have a GC check at the beginning of every function entry to ensure that the GC check is performed often enough.

Does anyone know where I can find more information on this subject?

Answer 1

To your question "Does anyone know where I can find more information on this subject" the best reference is Paul Wilson's survey paper as pointed by the @ Raymond Chen .

To have overview of existing garbage collector algorithms please check this link

Among the two ways you have mentioned (1) and (2) , I feel check has to be made in both ways .

Assuming you have defined your heap with certain constraints .(prime constraints being size_t maximumSize , base , limit ,NoOfBytesAllocated) . So to that heap structure adding few more fields like limitForGcInSizeMinor ,limitForGcInSizeMajor limitForGcInObjects would tackle GC situation in better way(If your heap structure already has this fields please ignore).

SO whenever allocation >= limitForGcInSizeMinor perform GcMinor(can be stop the world mechanism or can be concurrent) . if allocation reaches limitForGcInSizeMajor then perform GCMajor(something like stop the world ). I main reason for dividing GCMinor and GCMajor is to reduce the effect of GC spike (when stop the world mechanism happens) to minimum .

So in all along GC we followed (2) way I mean periodicallyas well as checking it using heap allocation . Al-tough i borrowed it from CMS algorithm .