Re: garbage collection thoughts... again?!

[rlake@...]

Wim escribió:

> Unlike
> mentioned by Rici and Peter Hill (if I remember correctly) I would 
suggest
> not to link the key/value pairs themselves, partly because of the 
storage
> overhead, but mostly because key/value pairs _are_ relocatable.  On the
> other hand this means that an extra GC admin (i.e. outside of the common
> header) must be used for tracking sets of dependants.  But it's 
definitely
> worth the extra effort in my view.

Yes, good point. I'm agnostic on whether to link the key/value pairs or 
create separate structures; there are several ways of accomplishing the 
same purpose, and I was just casting about for one that "fit". It wouldn't 
fit with incremental garbage collection, as you point out. In a 
non-incremental garbage collector, key/value pairs are not relocatable, 
since rehashing at GC time would interfere with table iteration. 

I currently favour a pre-allocated dependency table. The idea is to try to 
allocate it sufficiently large right after the GC cycle has finished. 
Dependency slots can be recycled during garbage collection and delaying 
marking of weak tables should reduce the size requirement somewhat. 
Moreover, if an object has only one dependent, the dependent can be marked 
immediately rather than being stashed in the list; a single bit could 
track this fact. I think this would be quite a common case in most 
real-world programs.

If the dependency table overflows, it is not a tragedy. You just revert to 
the current Lua behaviour and remember to allocate a biggler table on the 
next GC cycle. This should only happen in pathological cases, anyway, if a 
reasonable estimate can be made for the size of the dependency table (it 
could be a function of the total size of all weak tables, which can be 
discovered at GC time) and in any event, it would only mean delaying 
collection rather than permanently losing the memory.