Re: Divide and conquer GC algorithms

Some use of the "autorelease pool" concept found in many Objective-C environments gives programmer-defined coarser-grained bulk decrements, commonly used so that you can have things similar to scopes where you do a retain (increment) when you know you're using something in a scope, and you also send it an "autorelease" which sets it up to receive a release (decrement) when exiting the scope. This way the decrements get batched up. (But there is overhead in maintaining this list-of-things-to-be-decremented.)

Since these autorelease pools, similar to scopes, are often nested in a stack-like manner, one could actually replace all release (decrement) messages with autorelease, and then do the batch decrementing and reclamation then. The issues are when there are complicated finalizers to be run, or, if the decrementing of one object yields more to be decremented because of what it references and so on, limiting the amount of granularity to only the set of objects that were sent the autorelease message and are now dead.

Somehow in the back of my mind I am thinking there should be a way to combine this with generational approaches to ease this issue. For example, suppose that, when an object was freed, if instead of sending a release (decrement) message to everything that it referred to, we sent an autorelease (defer to decrement in bulk later) message to those items. But this has the issue that the stack depth might not always be greater than the length of the longest linked structure to be freed.

I suppose you could do something with the number of references into a page (or other easily calculable chunk), and if that dropped down to zero just free the whole page (assuming all objects are smaller than a page, but I am sure one could work around that), but then you have another set of reference counts to keep track of, which adds overhead, but perhaps through some other techniques you could minimize the added overhead to make the performance advantages of being able to free an entire page at once be greater than the overhead of two sets of updates for every reference count change.

So many tradeoffs....

On Nov 12, 2011, at 12:43 PM, Jon Harrop <[email protected]> wrote:

> Yes, traditional reference counting is extremely fine-grained but what if it
> could also handle coarser grains? For example, if values become unreachable
> in clumps then it is surely valuable to be able to track the number of
> references to either A or B in a pair (A, B) in order to deallocate both
> simultaneously if they both die at the same time. There could be fewer
> reference counts to increment and decrement and it would be possible to
> reclaim multiple heap-allocated blocks in a single operation. It might even
> be possible to replace the count of the number of direct references to each
> value with a count of the number of values from which it is reachable...
> 
>> -----Original Message-----
>> From: [email protected] [mailto:[email protected]] On
>> Behalf Of David S. Wise
>> Sent: 12 November 2011 15:26
>> To: Jon Harrop
>> Cc: [email protected]
>> Subject: Re: [gclist] Divide and conquer GC algorithms
>> 
>> On 2011 Nov 12, at 4:31, Jon Harrop wrote:
>>> gradually refine the granularity.
>> 
>> 
>> Absent the intervening degrees of graularity but....
>> 'Tis important to appreciate that, way down at or near each mutation,
> reference
>> counting is extremely granular and, therefore, remains most interesting
> for
>> supporting parallel processing.
>> And that is why---in the face of ubiquitous "But it doesn't work for
> circular
>> structures" dismissals---it is used every day by each of us to sustain our
>> persistent file systems (e.g. the Unix HFS).
>> d
>> ====
>> David S. Wise +1(360)582-9233 ;  fax: +1(360)582-9233
> [email protected]
>> Computer Science Emeritus, Indiana University
>>                    http://www.cs.indiana.edu/~dswise/
> 
>