Which is faster?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
44 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: garbage collection thoughts... again?!

Wim Couwenberg-2
James McCartney wrote:
> If you want to read up on incremental GC :

Thanks for the pointers!  Important part that I missed: take care of changed
references in objects of the current parity into one of the opposite parity
(because those could possibly "revive" an otherwise collected object.)  The
object referred to should be (re)scheduled for marking.

Do you feel the scheme you implemented would be suitable for Lua?

Bye,
Wim



Reply | Threaded
Open this post in threaded view
|

Re: garbage collection thoughts... again?!

James McCartney

The Wilson+Johnstone scheme is very time efficient because it needs no sweep phase.

But it is less space efficient than other schemes because it segregates objects into size classes, which can cause fragmentation, and requires two links per object.

The size classes don't seem to be a problem in practice. I do sweep large objects and that eliminates most of the problem there. Since there are very few large objects, the excess cost of that is minimal.

If an overhead of two links per object were too much, as it would be for LISP cons pairs for example, then that could be a problem. For a language where the main object is a hash table I don't think it should be a problem. And memory is cheap now days.

On Sunday, June 1, 2003, at 09:50 AM, Wim Couwenberg wrote:

Do you feel the scheme you implemented would be suitable for Lua?

--
--- james mccartney   [hidden email]   <http://www.audiosynth.com>
SuperCollider - a real time audio synthesis programming language for MacOS X.


Reply | Threaded
Open this post in threaded view
|

Re: garbage collection thoughts... again?!

RLak-2
In reply to this post by Thatcher Ulrich
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.



Reply | Threaded
Open this post in threaded view
|

Re: garbage collection thoughts... again?!

Peter Hill-2
Wim:
> 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.

Rici:
> 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.

Not strictly true... but it would require a double-linked list to adjust the
pointers after a table resizing (so now we're talking two pointers rather
than one).

*cheers*
Peter Hill



123