RIP Philo

memory management: garbage collection vs reference counting

so I understand reference counting.  I _thought_ I understood garbage collection, but now I suddenly think maybe I dont.

is anyone able to give me a quick overview?


thanks.
Permalink Send private email zestyZucchini 
March 10th, 2007 1:34am
When objects fall out of scope, they are put in a queue for the collector. Then, when the program is idle, the collector runs and frees those objects.

Trickiness is definition of 'out of scope'. Perhaps this means there are no pointers to it left? Or maybe it means it just hasn't been used in a while. If a function returns an object, when does the object go out of scope? Do you put it in the collector and risk freeing memory in use? Or do you wait too long and have the program's memory signature grow and grow? At this point, I must pass the explanation to experts, who will be along shortly.
Permalink Practical Economist 
March 10th, 2007 2:20am
You could say that one works in a forward direction while the other works in a backwards direction.

Reference counting stores information with each allocated chunk of memory so that the allocator can work backwards from the memory to find how many references to it exist and recycle the memory as soon as the reference count goes to zero.

Garbage collection stores no information with the allocated chunks of memory but instead periodically works forward from the beginning of the program following all pointers to see what memory can be reached. Any unreachable memory can then be collected and recycled. (Sometimes called "mark and sweep".)

Reference counting may fail with circular references, whereas garbage collection will catch those but may have more overhead.

This could be all wrong but it sounds nice.
Permalink Send private email bon vivant 
March 10th, 2007 2:30am
Our guys just use a big truck. They pile all the memory into the truck and take it to the dump. Some of it is recycled if it is valuable enough.
Permalink son of parnas 
March 10th, 2007 9:52am
Sometimes they take the kid's tricycle that was just in the driveway by accident.
Permalink Send private email strawberry snowflake 
March 10th, 2007 10:26am
Here is a reference to one koan that might help:
http://www.csd.uwo.ca/~magi/personal/humour/Computer_Folklore/The%20Garbage%20Collection%20Koan.html
Permalink Peter 
March 10th, 2007 12:12pm
groan koan. :)
Permalink Send private email strawberry snowflake 
March 10th, 2007 12:15pm
"Trickiness is definition of 'out of scope'. Perhaps this means there are no pointers to it left?"

Exactly. 

We start from a root set.  A collection of primary objects that are globally reachable.  We mark these as reachable.  This means every static reference in every class and everything currently on the stack including fuction arguments.  We look through all those primary objects and find links to other objects.  Everything we find we mark as found and look through them for other objects. And so on.  At some point we run out of links to new objects. 

We look at everything on the heap and take those things without marks and reclaim the memory.

Reference counting is like each object remembers how many people are using it and when no one is it can die.  The problem here is with circular references.  A is using B, B is using A.  Everyone else has forgotten about them.  They don't get collected.  In the GC scheme described above, A and B wouldn't be reachable from the root set and would be reclaimed.
Permalink zed 
March 10th, 2007 12:17pm
or, um, what bv said.
Permalink zed 
March 10th, 2007 12:18pm
thanks :)
Permalink Send private email zestyZucchini 
March 10th, 2007 12:29pm

This topic is archived. No further replies will be accepted.

Other topics: March, 2007 Other topics: March, 2007 Recent topics Recent topics