LARA

Simple Copying Garbage Collector

Some advantages compared to mark-and-sweep:

  • no fragmentation
  • fast allocation, as in MallocInfMem.scala
  • good when a lot of data allocated and thrown away (as in functional languages)

Disadvantage: double space consumption

  • note that fragmentation can (very infriquently) mean inability to allocate block even if there is e.g. 1000 times more space

Basic idea:

  • copy and compact useful data from from-space into the other half, to-space
    • in to-space we build (compactly laid out) isomorphic graph copy of graph in from-space
  • pronounce the other half empty and swap their roles

Note:

  • addresses of nodes change
  • must update all root pointers to new locations
  • must update reference fields of all non-garbage objects

Forwarding - key step (copies node if needed)

  • if p is a pointer in from-space, make it point into to-space
  • store in old copy where the new copy is (necessary for shared structures)

Consider example of moving a graph with sharing

Simple Collector

def forward(p) =
  if (p points to from-space) {
    if (p.f1 points to to-space) 
      p.f1 // moved already
    else {
      for (each field f_i of p)
        next.fi = p.fi
      p.f1 = next
      next = next + sizeof(p)
      p.f1
    }
  } else p
def collect = {
  scan = beginning-of-to-space
  next = scan
  for (each root r)
    r = forward(r)
  while (scan < next)
    for (each field f_i of record at scan)
      scan.fi = forward(scan.fi)
    scan = scan + sizeof(scan)
}

Note: for locality of reference want to do depth-first search instead