6.001/Recitation 13

Rob Speer

Contents 1 Garbage collection 2 Reference counting 3 Mark and sweep 4 Stop and copy

Garbage collection

We're going to do garbage collection in a hypothetical Scheme world where pairs and atoms really are the only data types, except we have two big vectors to represent the pairs.

Reference counting

• Tack on a count to every pair that says how many things point to it.
• Garbage collect things with 0 references.
• It's easy! It's fast! It doesn't always work!

Mark and sweep

1. Mark the root
2. Whenever you mark something, recursively mark its car and cdr
3. Scan all of memory and check for unmarked cells
4. Join unmarked cells together into free list

(define (mark obj)
  (cond ((not (pair? object)) #f)
        ((not (= 1 (vector-ref the-marks object)))
            (vector-set! the-marks object 1)
            (mark (car object))
            (mark (cdr object)))))

(define (sweep i)
  (cond ((not (< i 0))
      (if (= 1 (vector-ref the-marks i))
          (vector-set! the-marks i 0)
          (begin
            (set-cdr! (int-to-pointer i) free)
            (set! free (int-to-pointer i))))
      (sweep (- i 1)))))

(define (gc root)
  (mark root)
  (sweep (vector-size the-cars)))

• You can make a cons that uses the free list
• Can have stack issues

Stop and copy

1. Set free and scan to point to beginning of new memory (new-cars, new-cdrs)
2. "Forward" the root pointer
3. Scan through new memory looking up each pointer, and forwarding those too
4. Mark forwarded pairs with a symbol ("broken heart") in the car, and the forwarding pointer in the cdr
5. Increment scan and repeat until catches up to free

How to forward

1. look up pointers in old memory
2. relocate car
3. relocate cdr

How to relocate

1. If it's forwarded already, just look up new address
2. copy into free pair
3. increment free
4. store forwarding pointer

(define (stop-and-copy root)
  (let ((free 0))

    (define (gccopy scan)
      (if (not (= scan free))
          (begin
            (vector-set! the-cars scan (forward (vector-ref the-cars scan)))
            (vector-set! the-cdrs scan (forward (vector-ref the-cdrs scan)))
            (gccopy (+ scan 1)))))

    (define (forward pointer)
      (if (not (pair? pointer))
        pointer
        (let (oldcar (car pointer))
          (if (forwarded? oldcar)
            (int-to-pointer oldcar)
            (begin
             (vector-set! new-cars free oldcar)
             (vector-set! new-cdrs free (cdr pointer))
             (set! free (+ 1 free))
             (set-car! pointer (int-to-pointer free)))))))

    (forward root)
    (gccopy 0)
    (swap the-cars new-cars)
    (swap the-cdrs new-cdrs)))