1 of 39

Garbage Collection

Mark and Sweep (with Copy Collection)

2 of 39

Garbage: Example

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Line

FP (a)

Heap (h)

1

200

{ 100 : 0, 200: {p : 0, f : 100}}

3

208

{ 100 : 0, 108 : 1, 200 : {p : 0, f : 100}, 208 : {p : 200, x : 108} }

7

208

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ),

200 : {p : 0, f : 116}, 208 : {p : 200, x : 108} }

8

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ),

200 : {p : 0, f : 116}, 208 : {p : 200, x : 108} }

9

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ), 124: 2,

200 : {p : 0, f : 116}, 208 : {p : 200, x : 124} , 216 : {p : 208} }

10

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ), 124: 2, 132:3,

200 : {p : 0, f : 116}, 208 : {p : 200, x : 132}, 216 : {p : 208},

224 : {p : 208} }

3 of 39

Garbage: Example

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Line

FP (a)

Heap (h)

1

200

{ 100 : 0, 200: {p : 0, f : 100}}

3

208

{ 100 : 0, 108 : 1, 200 : {p : 0, f : 100}, 208 : {p : 200, x : 108} }

7

208

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ),

200 : {p : 0, f : 116}, 208 : {p : 200, x : 108} }

8

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ),

200 : {p : 0, f : 116}, 208 : {p : 200, x : 108} }

9

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ), 124: 2,

200 : {p : 0, f : 116}, 208 : {p : 200, x : 124} , 216 : {p : 208} }

10

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ), 124: 2, 132:3,

200 : {p : 0, f : 116}, 208 : {p : 200, x : 132}, 216 : {p : 208},

224 : {p : 208} }

4 of 39

Reference Counting

  • Simplest way to approximate reachability
  • Idea: keep a count of how many references point to an object

​

5 of 39

Reference Counting: Challenges

  • Challenge 1: Performance
    • Almost every instruction has additional overhead
    • For many instructions the overhead could be significant

​

  • Challenge 2: Reference counting is an approximation of reachability

6 of 39

Cycles

  • Reference counting fails in the presence of cycles

x = {next: None} // object O1

y = {next: x } // object O2

x.next = y;

x = 0;

y = x;

x

y

0

c=2

  • Final Heap:

next:

c = 1

next:

c = 1

data:

c = 1

data:

c = 1

7 of 39

Mark and Sweep

  • Key idea: Deal with reachability explicitly.

​

  • How it works
    • Mark phase traverses all reachable objects
    • Sweep phase searches for all unreachable objects and deallocates them

8 of 39

Mark

  • Goal: traverse the entire reachable heap
    • Reachable from what?

​

  • Root set: initial set of pointers

9 of 39

Garbage: Example

1: var f = 0;

2: {

3: var x = 1;

4: f = fun(y) {

5: print(x);

6: x = x + 1;

7: };

8: }

9: f(1);

10: f(2);

Line

FP (a)

Heap (h)

1

200

{ 100 : 0, 200: {p : 0, f : 100}}

3

208

{ 100 : 0, 108 : 1, 200 : {p : 0, f : 100}, 208 : {p : 200, x : 108} }

7

208

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ),

200 : {p : 0, f : 116}, 208 : {p : 200, x : 108} }

8

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ),

200 : {p : 0, f : 116}, 208 : {p : 200, x : 108} }

9

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ), 124: 2,

200 : {p : 0, f : 116}, 208 : {p : 200, x : 124} , 216 : {p : 208} }

10

200

{ 100 : 0, 108 : 1, 116 : (208, y, {print(x); x = x + 1} ), 124: 2, 132:3,

200 : {p : 0, f : 116}, 208 : {p : 200, x : 132}, 216 : {p : 208},

224 : {p : 208} }

10 of 39

1

2

�x�y�z

S: “Hello world”

�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

R:

R:

11 of 39

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

12 of 39

Mark

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

In MITScript, (as in most scripting languages) the rootset is just the stack of stack frames

(and any other global pointers…e.g., None last slide)

13 of 39

After mark

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

14 of 39

Mark

  • It is important to follow every pointer, including
    • pointers from the operand stack to values
    • pointers from local variables to values
    • pointers from records to values
  • Some objects like records are actually composed of multiple small objects
    • the smaller objects do not need to be marked independently

15 of 39

Sweep

  • Goal is to deallocate everything that is not reachable.

​

  • How do we get to the non-reachable things?
    • (1) keep around a list of all the objects that have ever been allocated.
    • (2) Allocate objects in a way that makes them easy to reach

​

16 of 39

After mark

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

17 of 39

List of allocated objects

1

2

R:�x�y�z

S: “Hello world”

M�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

18 of 39

After mark

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

19 of 39

After sweep

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

Deallocated

20 of 39

Can we do better?

  • We can avoid keeping around separate structures for the list and objects

21 of 39

Can we do better? (Answer)

  • We can avoid keeping around separate structures for the list and objects

​

  • We want to add headers just like we did with reference counting, but with ‘next’ pointers instead of counts.

​

  • Can deallocate the entire node in one shot.

22 of 39

List of allocated objects

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

Halves memory overheard of garbage collector

23 of 39

List of allocated objects

1

2

R:�x�y�z

S: “Hello world”

R:�t

Stack Frame

Vars

x

y

z

Stack

o

o

o

Stack

o

24 of 39

Can we do even better?

  • We can avoid keeping around allocated list

25 of 39

An alternative: copying collector

  • Divide the heap into two regions
  • Allocate objects into region A first
    • pack them tightly to avoid overhead of having to track where the free memory is.

​

Heap A

Heap B

26 of 39

An alternative: copying collector

  • Divide the heap into two regions
  • Allocate objects into region A first
    • pack them tightly to avoid overhead of having to track where the free memory is.
  • Once region A is full, search all reachable objects and copy them to heap B

Heap A

Heap B

R1

R2

R3

R4

27 of 39

An alternative: copying collector

  • Divide the heap into two regions
  • Allocate objects into region A first
    • pack them tightly to avoid overhead of having to track where the free memory is.
  • Once region A is full, search all reachable objects and copy them to heap B
    • as you traverse, replace pointers to objects in Heap B to pointers to their twins in Heap B

Heap A

Heap B

R1

R2

R3

R4

R1

R2

R3

R4

28 of 39

An alternative: copying collector

  • Divide the heap into two regions
  • Allocate objects into region A first
    • pack them tightly to avoid overhead of having to track where the free memory is.
  • Once region A is full, search all reachable objects and copy them to heap B
    • as you traverse, replace pointers to objects in Heap B to pointers to their twins in Heap B
  • Deallocate in bulk all objects in Heap A
    • swap the roles of Heaps A and B and repeat

Heap A

Heap B

R1

R2

R3

R4

R1

R2

R3

R4

29 of 39

Object relocation

  • Key issue in copying collectors
    • When an object moves from one location in memory to another, all pointers to the old object need to be moved.
  • Idea 1: indirection
    • Replace pointers with entries into a table; when an object moves, there is only one location to modify
    • Problems:
      • introduces high runtime cost
      • reduces the locality advantage of copying collector
      • you now need to do resource management on the indirection table.

​

A

C

A

B

B

C

30 of 39

  • Idea 2: Leave a forwarding address

Old

New

Addr: A

Addr: B

Addr: C

Ptr to B

Ptr to B

31 of 39

  • Idea 2: Leave a forwarding address

Old

New

Addr: A

Addr: B

Addr: C

Ptr to B

Ptr to B

Addr: A’

Addr: B’

Addr: C’

Ptr to B

32 of 39

  • Idea 2: Leave a forwarding address

Old

New

Addr: A

Addr: B

Addr: C

Ptr to B

Ptr to B

Addr: A’

Addr: B’

Addr: C’

Ptr to B’

Forward �to B’

33 of 39

  • Idea 2: Leave a forwarding address

Old

New

Addr: A

Addr: B

Addr: C

Ptr to B

Ptr to B

Addr: A’

Addr: B’

Addr: C’

Ptr to B’

Forward �to B’

Ptr to B

34 of 39

  • Idea 2: Leave a forwarding address

Old

New

Addr: A

Addr: B

Addr: C

Ptr to B

Ptr to B

Addr: A’

Addr: B’

Addr: C’

Ptr to B’

Forward �to B’

Ptr to B

35 of 39

  • Idea 2: Leave a forwarding address

Old

New

Addr: A

Addr: B

Addr: C

Ptr to B

Ptr to B

Addr: A’

Addr: B’

Addr: C’

Ptr to B’

Forward �to B’

Ptr to B’

36 of 39

Reachability

  • Is marking exact for garbage collection?
  • “Any memory that will never be used again should be returned to the system"

37 of 39

Reachability

  • Is marking exact for garbage collection?
  • “Any memory that will never be used again should be returned to the system"

​

  • No. Semantic Garbage
    • Program allocates large data structure in global variable during initialization that is helpful for program startup
    • Program never touches data structure again after initialization
      • Data is still reachable, but it is garbage. Difficult verify that program never touches data again

​

38 of 39

Tradeoffs

    • Cost of reference counting is high but distributed through the execution

​

    • Cost of mark-sweep/copying collector is lower, but it comes in bulk, sometimes causing noticeable stalls in the application

​

    • Allocation can be very fast in copying collectors; compacting objects can also improve cache locality, but copying objects can get very expensive

39 of 39

Key issues with GC

  • Tradeoff between
    • Runtime overhead
      • (costs imposed by GC on normal program execution)
    • Space efficiency
      • how much extra space does the GC need?
      • how quickly is it able to reclaim objects?
    • GC latency
      • avoiding long pauses due to GC