In each memory location store the number of incoming pointers
Free the block if the counter is zero
One day a student came to Moon and said, "I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons." Moon patiently told the student the following story: "One day a student came to Moon and said, `I understand how to make a better garbage collector...
What is the block has further pointers? - deallocation may take long time
- decrementing counts when the r is reused again
- ensures a bounded amount of work for each operation
Two problems of reference counting
- cost of field assignments = ?
- for which classes of graphs it works?
Data-flow analysis for avoiding reference count updates of local variables