Memory Managment

Manual(c)

• how do we get memory -> malloc
• how do we indicate that we’re done with memory -> free

Automatic(Java/Python/Racket/…)

• how do we get memeory -> new/construction
• how do we indicate that we’re done with memroy -> (N/A?)

Manual

• Forget to free (memory leak)
• Hard to get right
• use after free (Really hard to debug)

Automatic

• Less control
• Typically more memory usage
• Typically slower
• Still could have bugs but they are outside your control

The garbage collector is a runtime algorithm that proves memory can be reclaimed.

Goals for a GC

• If the GC collects memory, then that memory was not used again. (soundness)
  • no use after free bugs
• If memory is not used again, then the GC will collect it. (completeness)
  • no memory leaks

Never have a garbage collection that looks at program but instead looks at the state of memory

We wo; ise “unreachable” as our proof that memory can be reclaimed

Mark and Sweep Algorithm O(memory)

1. Traverse reachable blocks of memory (DFS/BFS) and mark them O(Reachable)
2. Free all the unreachable blocks O(allocated memory)
   • concern: knowing where to put new memory!