Reference Counting Flashcards
What are the advantages of Reference Counting?
Immediate
Object local
Overhead distributed
Very simple naive implementation
What are the disadvantages of reference counting?
Maintain count (time and space overhead)
Cycles can’t be collected
Complex high performance implementation
What is reference counting?
Associate a reference count field for each objects to indicate how many pointers reference an object
Object can be deleted when nothing points to an object
Decrement count for all descendants of dead objects
What is write barrier?
Small piece of code
Used to intercept pointer writes
Generated by compiler
What is lazy freeing?
Problem: Uneven processing overhead
Cost of deleting last pointer to an object O depends on size of sub-graph rooted at O
Solution: Lazy Freeing
Free lazily with a stack
When last pointer to O deleted, push O to stack
During allocation, pop O from stack, free O, decrement children of O
If any of the children goes down to 0, push it to stack
What are the properties of lazy freeing?
What are the advantages and disadvantages of lazy freeing?
Splitting the costs of deletion evenly throughout the computation
Efficiency (almost) unchanged: deletion is just spread into many allocation operations
Complication of the allocation process
It may take time to realize that a large consecutive space has been freed
What is Sticky reference count?
Problem: Space overhead for ref counters
Theoretically, large enough to hold number of pointers in the heap
Idea: use small rc fields (may overflow)
When rc overflows, think of it as stuck
Stuck rc’s are not decremented/incremented
To reclaim objects with stuck rc, their rc values must be restored
How to restore sticky reference counts?
Auxiliary data structures
to store count of the overflowed objects
Hash Table can be used
Cycle collector Ignore them (let backup tracing collect stuck objects) Restore them (let backup tracing restore stuck counts)
What is deferred reference counting?
Problem: overhead on updating changes to stacks and registers is too high
Solution
Don’t update rc for stacks and registers
rc’s reflect only references from heap objects not from stack
We can’t delete objects whose rc drops to zero
Instead objects with rc = 0 are pushed to ZCT (Zero Count Table)
“Once in a while”: collect all objects with rc=0 that are not referenced from stacks and registers
What are the properties / advantage-disadvantages of deferred reference counting?
Advantages:
Deferred RC reduces overhead by 80%.
Disadvantages:
Immediacy of collection lost !
Space overhead for ZCT.
Used in most modern RC systems
How reference counting collectors collect garbage cycles?
Reference counting collectors employ one of 2 avenues to collect garbage cycles:
A backup tracing collector
Trace all live objects and sweep the entire heap
Can also restore reference counts
A cycle collector
Known as trial deletion
What are the 2 basic observation behind cycle collection?
Observation 1:
Garbage cycles can only be created when a rc is decremented to a non-zero value
Objects whose rc is decremented to a non-zero value become candidates
Observation 2:
In a garbage cycle all the reference counts are due to internal pointer of the cycle
For each candidate’s sub-graph, check if external pointers point to this sub-graph
What is sub-graph, external pointer and internal pointer?
Sub-graph of O
graph of objects reachable from O
External pointer (to a sub-graph) a pointer from a non sub-graph object to a sub-graph object
Internal pointer (of a sub-graph) a pointer between 2 sub-graph objects
How to implement cycle collector?
Object is colored black/gray/ white.
Whenever rc of an object ‘a’ is decremented to a non-zero, perform local traversals over the graph of objects of ‘a’.
Mark: Updates rc’s to reflect only pointers that are external to the graph of ‘a’, marking nodes in gray
Scan: Restores rc’s of the externally reachable objects, coloring them in black. Rest of the nodes are white.
Collect: collects garbage objects (the white ones).
Describe the design space of reference counting collectors?
Storing the count
- A word per object
- Some available bits
Maintaining the count
- Naive
- Deferred
- Coalescing
- Generational and Age-Oriented
Cycles
- Backup tracing
- Trial deletion