[Gc] [boehms-gc] Extend Boehm's GC disappearing link facility
petter.urkedal at nordita.dk
Thu Sep 21 09:55:54 PDT 2006
Laurynas Biveinis wrote:
> 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
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