[Gc] [boehms-gc] Extend Boehm's GC disappearing link facility with callbacks-on-disappear

Petter Urkedal petter.urkedal at nordita.dk
Thu Sep 21 09:55:54 PDT 2006


Laurynas Biveinis wrote:
> Hi,
>
> Boehm's GC has weak pointer support, but sometimes setting the weak
> pointer to NULL when the object pointed by it disappears, is not what
> is required for the application, for example GCC hash tables use
> non-NULL values for deleted entries.
>
I hope I'm not too late responding here, I haven't followed the list 
very closely lately.

Since you are talking about hash tables, I suspect you may be doing the 
same as me, namely remove objects from hash tables as they are 
reclaimed.  Is that correct?  I tried to do this using finalisers, then 
with weak pointers.  The weak pointer solution was the most efficient, 
though as you mention it's not straight forward.

However, I have very tight requirements on efficiency and space 
overhead, since I am using this for hash-consing expression-trees, and 
since the tree nodes may consume the majority of memory for some 
applications (like automated logic provers).  Therefore, neither the 
finaliser nor the weak-pointer implementations are feasible in my case.  
Callbacks on weak-pointers would give the required functionality, but in 
my case I suspect overhead is still too big (at list memory-wise).

I have been using a new patch which takes a rather different approach 
from the one I posted.  Apologies to Boehm for not informing that I had 
abandoned the patch.

Assuming we are trying to solve the same problem, I think it would be 
good to figure out the best way to do this.  My suggestion is to add the 
most light-weight functionality possible to the collector, and to write 
a common library which implements auto-pruned hash-tables on top of that.

I wrote a description of the patch I'm currently using at

    http://www.eideticdew.org/culibs/bdwgc-rn.html

There is also a link to the patch itself, and if you follow the 'culibs' 
link at the top, you'll find a library which implements the hash-consing 
(which is essentially an auto-pruned hash-table).  See cu/hcons_rn.h and 
cu/hcons_rn.c in particular.  What I try to accomplish is

  * Do not run any per-object code at the critical point where marks are 
consistent.  This is to make sure the implementation scales well with 
many cores/CPUs when a significant part of memory is hash-consed.

  * Minimise the per-object space overhead, and make it fast.

Implementing an efficient auto-pruned hash-table on top of it can be a 
bit tricky, that's why I suggest a common library.  I have traded 
convenience for scalability here.  My benchmarks tells me that each 
hash-cons (including cleanup) is amortised about a factor 10 from 
tread-local allocation for the bad case when all objects are different, 
and about the same as thread-local alloc when hash-consing the same 
object repetitively.  This is still far better than what I managed with 
weak-pointers.  Also, the thread-local allocation I compare to is very fast.

Any suggestions for more efficient approaches are very welcome.



More information about the Gc mailing list