Skip to main content
gamedev.net
🔒 Locked

Reference Counting

Started by robinei Apr 14, 2005 at 8:37 AM 1 replies 800+ views
Original Post
robinei
robinei
I'm trying to make an interpreter for a Lisp-like language, and I intend to use reference counting for garbage collection. My idea so far is that when an object is bound to a symbol in a scope it's reference count is increased. If that symbol was already bound to an object, it's count will be decreased first. And finally when a scope is destroyed it will decrease the count of all it's bound objects. Then in the release() method of the objects I just call "delete this;" when the count reaches zero. Will this scheme suffice, or is it somehow flawed?
Extrarius
Extrarius
The problem with reference counting is that (especially in a Lisp-like language), there can be circles of reference that prevent reference counts from ever reaching zero.
For example, if you have a structure Node that has two elements (Data, and NextNode), you could have
A.NextNode = B
B.NextNode = C
C.NextNode = A
It is possible to detect cycles, but difficult and potentially very slow and memory intensive (since cycles can be of any length).

There are better garbage collection methods, such as the mark-sweep algorithm. Some sites on garbage collection:
Mostly Parallel Garbage Collection
A garbage collector for C and C++
Garbage collection in a large LISP system
The Memory Management Reference
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
Trap
Trap
Lisp in small pieces might be helpful, Peter Norvig thinks it is the best book on writing lisps. I ordered it yesterday.

Franz developer documentation of their GC implementation is a good read too, although it doesn't explain how to implement it.

Depending on how much data you expect a pure stop and copy gc might be good enough.

[Edited by - Trap on April 14, 2005 11:41:13 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.