Mark and Sweep Garbage Collector


  • use free list, as in malloc+free, but do free automatically
  • mark all reachable objects
  • insert all unreachable objects into free list

How to determine reachable objects?

  • start from the set of roots (e.g. live local and global variables)
  • follow all reference variables in allocated objects
    • compiler generates information that indicates which fields and variables are of reference type
  • mark reachable objects using depth-first search

What are roots?

  • global reference variables
  • reference variables on stack
  • registers


  • inserting into a functional tree twice
  • not using middle tree
  • performing mark and sweep