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

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