Reference Counting Flashcards

1
Q

What are the advantages of Reference Counting?

A

Immediate
Object local
Overhead distributed
Very simple naive implementation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the disadvantages of reference counting?

A

Maintain count (time and space overhead)
Cycles can’t be collected
Complex high performance implementation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is reference counting?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is write barrier?

A

Small piece of code
Used to intercept pointer writes
Generated by compiler

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is lazy freeing?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the properties of lazy freeing?

What are the advantages and disadvantages of lazy freeing?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is Sticky reference count?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How to restore sticky reference counts?

A

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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is deferred reference counting?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the properties / advantage-disadvantages of deferred reference counting?

A

Advantages:
Deferred RC reduces overhead by 80%.

Disadvantages:
Immediacy of collection lost !
Space overhead for ZCT.

Used in most modern RC systems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How reference counting collectors collect garbage cycles?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the 2 basic observation behind cycle collection?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is sub-graph, external pointer and internal pointer?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How to implement cycle collector?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Describe the design space of reference counting collectors?

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Discuss the space requirement for storing counts in a RC GC?

A

Space

  • Dedicated word (32 bits) per object
  • Steal bits from each object’s header
17
Q

Describe the trade offs in maintaining the count is a RC GC?

A

Naive RC

  • requires inc and dec on every pointer mutation
  • Easy to implement only write barriers, no GC maps

Deferred RC

  • ignores changes to stacks and register
  • Temporary increment used to fake liveness of roots
  • Normal incs and decs deferred until collection time
  • Much faster than naive but requires GC maps

Coalescing RC

  • ignores many changes to heap
  • Coalesce pointer mutations record just first and last in chain of changes
18
Q

What are the sources of ref count incs and decs?

A

New objects

Mutations to:

  • non-new scalar objects
  • non-new array objects

Temporary operations due to root reachability

Cycle collection-generated decrements

19
Q

What improvements can be made in storing the counts?

A

Findings:
Max count < 8 in most cases
Very few overflows - The percentage of stuck objects is very low

Design: Handling stuck objects
Auxiliary data structure to store count of the overflowed objects
Ignore them let backup tracing collect stuck objects
Restore them let backup tracing restore stuck counts

20
Q

What improvements can be made in maintaining the count?

A

Findings:
New objects are the source of most incs and decs
Survival ratio is low

New objects a fruitful focus

21
Q

How new objects are handled previously?

A

Implicitly dirty
Marked as dirty and enqueued
Inc applied to each referent at next collection

Implicitly live
Initial count of one
Dec enqueued, processed at next collection

22
Q

What is the new way to handle new objects?

A

Implicitly clean
Lazily dirty at collection time only if (transitively) inc’d by old object or roots
Non-surviving objects never processed

Implicitly dead
Lazily increment at collection time only if (transitively) inc’d by old object or roots
Available to free list unless they are incremented

Minor change to existing RC, not hybrid of two collectors