[boost] [gc] new implementation in boost vault that solves the issue of finalization order

Subject: [boost] [gc] new implementation in boost vault that solves the issue of finalization order
From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2009-04-26 19:25:18

Hi.

I have posted a new gc implementation in the boost vault here:

http://www.boostpro.com/vault/index.php?action=downloadfile&filename=gc1.zip&directory=Memory&

The code included in the file is a garbage collector with the following 
differences from the previous one:

1) finalization order that respects destructor semantics, except when 
there are cycles. In the previous collector, the order of finalization 
was random. In the new collector, an unreachable object A that is 
pointed to by another unreachable object B will be finalized after B is 
finalized. This allows the use of gc ptrs within destructors.

2) O(1) detection of member ptrs: pointers registers themselves to the 
appropriate ptr list as they are created. In the previous collector, 
pointers where discovered in the collection phase by look-up on the 
sorted blocks.

The code is not completed or polished, but it is published for 
discussing possible implementation ideas.

The main bottleneck right now is how to locate blocks from pointers. The 
current solution is to sort the blocks by address at collection time, 
then use std::upper_bound to locate the blocks. This has O(log2(N)) 
complexity, where N is the number of blocks.