1 of 21

Garbage Collection

2 of 21

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 21

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 21

Garbage Collection

  • Up to this point we have only been allocating memory

​

  • Eventually, the memory is full of objects that you can never use

​

  • If you keep doing this, memory eventually runs out

5 of 21

Garbage Collection

  • Key problem:
    • Any memory that will never be used again should be returned to the system
    • We can’t predict the future, can we?

​

  • Reachability is a key *approximation*

6 of 21

Reference Counting

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

​

7 of 21

Example

x = 5;

y = 7;

z = x;

y = z;

5

7

c=1

c=1

x

y

z

None

c=1

c=2

c=4

c=3

c=2

c=3

c=0

Deallocate

8 of 21

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

9 of 21

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;

10 of 21

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

11 of 21

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

12 of 21

Mark

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

​

  • Root set: initial set of pointers

13 of 21

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} }

14 of 21

End�

15 of 21

OK, it’s a little more complicated

  • In the VM, assignments actually happen in two steps
    • RHS must be pushed to the stack
    • Value is then popped from the stack and assigned to rhs

16 of 21

Reference counting: Load and Store

store_local i

x = old object pointed to by variable i.

x.count -=1;

y = object popped from stack;

store object y to variable i

if( x.count == 0)

deallocate x;

​

store_local i

y = value object popped from stack;

store value object y to variable i

​

Without garbage collection

With reference counting

load_local i

x = read value object read from variable i

push x to the stack

load_local i

x = read value object read from variable i

x.count += 1

push x to the stack

Why do we not increment y.count?

17 of 21

MITScript VM

Globals

f

Locals

function {

functions = [ ],

constants = [None, 0, 1],

names = [f],

instructions = [

load_const 1

load_func 0

alloc_closure

store_global 0

load_global 0

load_const 2

call 1

pop

load_const 0

return

]}

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

add

store_local 1

load_const 0

return

]

}

IP

7

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Op Stack

​

​

Locals

y : 1

x : None

IP

0

Stack

Frame

Op Stack

​

​

1

18 of 21

MITScript VM

Globals

f

Locals

function {

functions = [ ],

constants = [None, 0, 1],

names = [f],

instructions = [

load_const 1

load_func 0

alloc_closure

store_global 0

load_global 0

load_const 2

call 1

pop

load_const 0

return

]}

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

add

store_local 1

load_const 0

return

]

}

IP

7

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Op Stack

​

1

Locals

y : 1

x : None

IP

1

Stack

Frame

Op Stack

​

​

1

19 of 21

MITScript VM

Globals

f

Locals

function {

functions = [ ],

constants = [None, 0, 1],

names = [f],

instructions = [

load_const 1

load_func 0

alloc_closure

store_global 0

load_global 0

load_const 2

call 1

pop

load_const 0

return

]}

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

add

store_local 1

load_const 0

return

]

}

IP

7

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Op Stack

1

2

Locals

y : 1

x : None

IP

2

Stack

Frame

Op Stack

​

​

1

20 of 21

MITScript VM

Globals

f

Locals

function {

functions = [ ],

constants = [None, 0, 1],

names = [f],

instructions = [

load_const 1

load_func 0

alloc_closure

store_global 0

load_global 0

load_const 2

call 1

pop

load_const 0

return

]}

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

add

store_local 1

load_const 0

return

]

}

IP

7

Heap

Stack

Frame

Closure { f : , ctx : [ ]}

Op Stack

​

3

Locals

y : 1

x : None

IP

3

Stack

Frame

Op Stack

​

​

1

21 of 21

Reference Counting Arithmetic

  • Arithmetic instructions allocate values and create and destroy objects

add

y = value popped from stack

y.count -=1;

x = value object popped from stack;

x.count -=1;

z = new Integer(x.ival()+y.ival())

z.count = 1

push z onto the stack

if( x.count == 0)

deallocate x;

if( y.count == 0)

deallocate y;

add

y = value popped from stack

x = value object popped from stack;

push new Integer(x.ival()+y.ival())

​

Without garbage collection

With reference counting