\documentclass{beamer}

\mode<presentation>
{
  \usetheme{Madrid}
}

\setbeamercolor{alerted text}{fg=blue!80!black}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{ulem}
\usepackage{scheme}
\usepackage{graphicx}

\usepackage{tikz}
\usetikzlibrary{calc}

\title{Managing Memory}
\subtitle{6.184 - Zombies drink caffeinated 6.001}

\author{Nelson Elhage}
\institute[MIT]{Massachusetts Institute of Technology}
\date{Lecture 6}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Implementing cons-cell memory}
  \begin{itemize}
  \item We've been using the \texttt{cons}-cell abstraction this whole
    class.
  \item Computer memory doesn't really work like that.
  \item Not going to go into \texttt{ec-eval}
  \end{itemize}
\end{frame}

\newcommand{\cell}[1]{\multicolumn{1}{|c|}{#1}}

\begin{frame}
  \frametitle{Computer Memory}

  \begin{itemize}
  \item Conventional memory is an array of locations, each of which
    has an integer \emph{address}, and stores a single value.
  \item Addresses are sequential, so we often move around memory by
    adding and subtracting values from addresses.
  \end{itemize}

  \begin{center}
    \begin{tabular}{ccccccccc}
      \hline
      \cell{}&\cell{}&\cell{}&\cell{}&\cell{}&\cell{}&\cell{}&\cell{}&\ldots \\
      \hline
      {\tiny 0} & {\tiny 1} & {\tiny 2} & {\tiny 3} & {\tiny 4} & {\tiny 5} & {\tiny 6} & {\tiny 7} & {\tiny \ldots}
    \end{tabular}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Vectors}
  \begin{itemize}
  \item We will model memory using \emph{vectors}.
  \item Also a generally-useful data structure (similar to arrays in
    other languages).
  \item Vectors support \emph{constant-time} access of an arbitrary
    element.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Vector Operations}
  \begin{itemize}[<+->]
  \item \texttt{(make-vector \textit{<size>})} $\rightarrow$ \texttt{<v>}
    \begin{itemize}[<1->]
    \item Returns a vector of the given size.
    \end{itemize}
  \item \texttt{(vector-ref \textit{<v>} \textit{<n>})} $\rightarrow$ \texttt{<elt>}
    \begin{itemize}[<1->]
    \item Return the \texttt{n}$^{th}$ element of \texttt{v} (0-indexed)
    \end{itemize}
  \item \texttt{(vector-set! \textit{<v>} \textit{<n>} \textit{<val>})}
    $\rightarrow$ \textit{undefined}
    \begin{itemize}[<1->]
    \item Sets the \texttt{n}$^{th}$ element of \texttt{v}.
    \end{itemize}
  \item \texttt{(vector-length \textit{<v>})} $\rightarrow$ \texttt{<size>}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Vectors and Lists}
  \begin{center}
    \begin{tabular}{p{.4\textwidth}|p{.4\textwidth}}
      {\large \bf Lists} & {\large \bf Vectors} \\
      \hline 
      Constant-time append at the beginning &
      No append at all \\
      \hline
      Constant-time insert at any point (with mutation) &
      No insert at all \\
      \hline
      Accessing the $n^{th}$ element takes $O(n)$ &
      Accessing the $n^{th}$ element takes constant time \\
      \hline
      Structure can be shared between different lists &
      Every vector is entirely disjoint \\
      \hline
      Rich set of built-in procedures (\texttt{map}, etc.) &
      Few built-ins (but you can build more)
    \end{tabular}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Representing \texttt{cons} cells}
  \begin{itemize}[<+->]
  \item We will represent \texttt{cons} cells using two vectors,
    \texttt{the-cars} and \texttt{the-cdrs}.
  \item A \texttt{cons} cell is an index $i$ into the arrays
    \begin{itemize}[<1->]
    \item Its \texttt{car} is \texttt{(vector-ref the-cars i)}
    \item Its \texttt{cdr} is \texttt{(vector-ref the-cdrs i)}
    \end{itemize}
  \item To represent other data, we'll use \emph{tagged pointers}.
    \begin{itemize}
    \item<4-> \texttt{n\textit{i}} is a \emph{n}umber with value $i$
    \item<4-> \texttt{p\textit{i}} is a \emph{p}air at index $i$
    \item<4-> \texttt{e0} is the special \emph{e}mpty list
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{An example}

  \begin{center}
    \includegraphics[width=0.8\textwidth]{memory}
  \end{center}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{cons}}
\begin{scheme}
(define (gc-cons car cdr)
  (let ((pair (gc-new-pair)))
    (gc-set-car! pair car)
    (gc-set-cdr! pair car)
    pair))
\end{scheme}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{car} and \texttt{cdr}}
\begin{scheme}
(define (gc-car pair)
  (vector-ref the-cars (pointer-value pair)))

(define (gc-cdr pair)
  (vector-ref the-cdrs (pointer-value pair)))

(define (gc-set-car! pair new-car)
  (vector-set! the-cars
               (pointer-value pair) new-car))

(define (gc-set-cdr! pair new-cdr)
  (vector-set! the-cdrs
               (pointer-value pair) new-cdr))
\end{scheme}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{gc-new-pair}}

\begin{scheme}
(define *free* 0)
(define (gc-new-pair)
  (let ((new-pair *free*))
    (set! *free* (+ *free* 1))
    (tag-pointer 'pair new-pair)))
\end{scheme}

  \begin{itemize}
  \item What's wrong?
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Re-using storage}
  \begin{itemize}
  \item Remember \texttt{find-primes}?
    \begin{itemize}
    \item \texttt{(2 3 4 5 6 7 8 9 10 11 12 \ldots)}
    \item \texttt{(2 3 5 7 9 11 13 15 17 19 \ldots)}
    \item \texttt{(2 3 5 7 11 13 17 19 23\ldots)}
    \end{itemize}
  \item Every \texttt{filter} step generates intermediate lists
  \item But those lists can never be accessed again!
  \item We can re-use that storage space
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{First try: Reference Counting}
  \begin{itemize}
  \item We could keep track of how many pointers there are to each
    object.
  \item Every time we generate a new reference to an object, we
    increase the reference count.
    \begin{itemize}
    \item \texttt{define}
    \item \texttt{set!}
    \item \texttt{apply} a compound procedure
    \item \ldots
    \end{itemize}
  \item Whenever we remove a reference to an object, decrease the
    count.
    \begin{itemize}
    \item \texttt{set!} (The old value)
    \item After \texttt{apply}ing a compound procedure.
    \item \ldots
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Reference Counting: Problems}
  \begin{itemize}
  \item Na\"ive refcounting leaks circular objects!
    \begin{scheme}
(define x (list 'a))
(set-cdr! x x)
(set! x 0)
    \end{scheme}
  \item Performance impact in many cases.
    \begin{itemize}
    \item Every time you leave a frame, you need to walk its variables
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Garbage Collection}
  \begin{itemize}
  \item There is a \emph{root set} of objects the evaluator holds onto
    directly.
    \begin{itemize}
    \item (On real hardware, these are the ``registers'')
    \end{itemize}
  \item Only objects reachable from this set by some sequence of
    \texttt{car} and \texttt{cdr} can \emph{ever matter}.
  \item Any memory that is not accessible in this way is
    \emph{garbage}, and can be reused.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{mark-and-sweep}
  \begin{itemize}[<+->]
  \item \emph{mark-and-sweep} is one of the simplest garbage
    collection algorithms, composed of two phases:
    \begin{enumerate}
    \item Starting from the root set, recursively \emph{mark} every
      reachable object.
    \item \emph{sweep} all of memory, collecting every unmarked object
      into the \emph{free list}.
    \end{enumerate}
  \item Allocation then takes place by removing new pairs from the
    free list.
  \end{itemize}
\end{frame}

\def\cons(#1)#2{%
  \draw (#1) rectangle +(2,1);%
  \draw (#1) node[anchor=north east] {\tiny #2} +(1,0) -- +(1,1);%
  \def\lastcons{(#1)}%
}

\def\nullcdr{\draw \lastcons ++(1,0) -- +(1,1);}
\def\nullcar{\draw \lastcons -- +(1,1);}

\def\consnumber(#1)#2{%
  \draw (#1) node[anchor=south west] {\small #2} rectangle +(1,1);%
}

\def\car#1{($ (#1) + (0.5,0.5) $)}
\def\cdr#1{($ (#1) + (1.5,0.5) $)}
\def\edgeT#1{($ (#1) + (0.5, 1.0) $)}
\def\edgeL#1{($ (#1) + (0, 0.5) $)}

\def\consArrow#1#2{%
  \draw[->] #1 -- #2;%
  \fill #1 circle (0.1);%
}

\def\fillcons#1#2{\fill[#1] (#2) rectangle +(2,1);}

\begin{frame}
  \begin{tikzpicture}[xscale=0.5,yscale=0.5]
    \coordinate (consA) at (0,0);
    \coordinate (consB) at (0,-3);
    \coordinate (numA)  at (0,-5);
    \coordinate (consC) at (3,-3);
    \coordinate (numB)  at (3,-5);
    \coordinate (consD) at (6,0);
    \coordinate (numC) at (6,-3);
    \coordinate (consE) at (10,0);
    \coordinate (numD) at (10,-3);

    \uncover<2->{\fillcons{blue!70}{consA}}
    \uncover<4->{\fillcons{blue!70}{consB}}
    \uncover<5->{\fillcons{blue!70}{consC}}
    \uncover<6->{\fillcons{blue!70}{consD}}
    \uncover<7->{\fillcons{blue!70}{consE}}

    \cons(consA){1}
    \cons(consB){5}
    \consnumber(numA){1}
    \cons(consC){7}\nullcdr
    \consnumber(numB){2}
    \cons(consD){2}
    \consnumber(numC){3}
    \cons(consE){4}10,0\nullcdr
    \consnumber(numD){4}

    \consArrow{\car{consA}}{\edgeT{consB}}
    \consArrow{\cdr{consA}}{\edgeL{consD}}
    \consArrow{\car{consB}}{\edgeT{numA}}
    \consArrow{\cdr{consB}}{\edgeL{consC}}
    \consArrow{\car{consC}}{\edgeT{numB}}
    \consArrow{\car{consD}}{\edgeT{numC}}
    \consArrow{\cdr{consD}}{\edgeL{consE}}
    \consArrow{\car{consE}}{\edgeT{numD}}

    \draw[->] (-2,0.5) node[anchor=east] {\texttt{root}} -- (0,0.5);

    \uncover<8->{
      \draw[->] (0,-6.5) node[anchor=east] {\texttt{free-list}} -- +(1,0);
    }

    \uncover<10-12>{
      \coordinate (freeA) at (1,-7);
    }
    \only<13-15>{
      \coordinate (freeA) at (4, -7);
      \coordinate (freeB) at (1, -7);
    }
    \only<16-18>{
      \coordinate (freeA) at (7, -7);
      \coordinate (freeB) at (4, -7);
      \coordinate (freeC) at (1, -7);
    }

    \only<19-20>{
      \coordinate (freeA) at (10, -7);
      \coordinate (freeB) at (7, -7);
      \coordinate (freeC) at (4, -7);
      \coordinate (freeD) at (1, -7);
    }

    \uncover<10->{
      \cons(freeA){8}\nullcar\nullcdr
    }
    \only<13->{
      \cons(freeB){6}\nullcar
      \consArrow{\cdr{freeB}}{\edgeL{freeA}}
    }
    \only<16->{
      \cons(freeC){3}\nullcar
      \consArrow{\cdr{freeC}}{\edgeL{freeB}}
    }
    \only<19->{
      \cons(freeD){0}\nullcar
      \consArrow{\cdr{freeD}}{\edgeL{freeC}}
    }

  \end{tikzpicture}

  \vspace{1cm}
  { \tt \small
  \begin{tabular}{rcccccccccl}
    Index & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \ldots \\
    \cline{2-11}
    the-cars & \cell{\uncover<19-20>{e0}} & \cell{p5} & \cell{n3} & \cell{\uncover<16->{e0}} & \cell{n4} & \cell{n1} 
    & \cell{\uncover<13->{e0}} & \cell{n2} & \cell{\uncover<10->{e0}} & \ldots \\
    \cline{2-11}
    the-cdrs & \cell{\uncover<19-20>{p3}} & \cell{p2} & \cell{p4} & \cell{\uncover<16->{p6}} & \cell{e0} & \cell{p7} 
    & \cell{\uncover<13->{p8}} & \cell{e0} & \cell{\uncover<10->{e0}} & \ldots \\
    \cline{2-11}
    the-marks 
    & % 0
    & \uncover<2->{\texttt{\#t}}
    & \uncover<6->{\texttt{\#t}}
    & 
    & \uncover<7->{\texttt{\#t}}
    & \uncover<4->{\texttt{\#t}} % 5
    & 
    & \uncover<5->{\texttt{\#t}}
    & 
    \\
    & \uncover<19>{$\uparrow$} % 0
    & \uncover<1-2>{$\uparrow$} \uncover<18>{$\uparrow$}
    & \uncover<6>{$\uparrow$}   \uncover<17>{$\uparrow$}
    & \uncover<16>{$\uparrow$}
    & \uncover<7>{$\uparrow$}   \uncover<15>{$\uparrow$}
    & \uncover<3-4>{$\uparrow$} \uncover<14>{$\uparrow$} % 5
    & \uncover<12-13>{$\uparrow$}
    & \uncover<5>{$\uparrow$} \uncover<11>{$\uparrow$}
    & \uncover<9-10>{$\uparrow$}
    & \uncover<8>{$\uparrow$}
  \end{tabular}}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{mark}}
  \begin{scheme}
(define (mark p)
  (if (and (gc-pair? p)
           (not (vector-ref
                 the-marks
                 (pointer-value p))))
      (begin
        (vector-set! the-marks
                     (pointer-value p)
                     \#t)
        (mark (gc-car p))
        (mark (gc-cdr p)))))
  \end{scheme}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{sweep}}
  \begin{scheme}
(define (sweep i)
  (if (not (vector-ref the-marks i))
      (begin
        (vector-set! the-cars i *gc-nil*)
        (vector-set! the-cdrs i *free-list*)
        (set! *free-list* (tag-pointer 'pair i))))
  (if (> i 0)
      (sweep (- i 1))))
  \end{scheme}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{mark-and-sweep}}
  \begin{scheme}
(define (mark-and-sweep root)
  (clear-all-marks)
  (mark root)
  (set! *free-list* *gc-nil*)
  (sweep (- *memory-size* 1)))
  \end{scheme}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{gc-new-pair} with a free list}
  \begin{scheme}
(define (mark-and-sweep-new-pair)
  (if (eq? *free-list* *gc-nil*)
      (error "Out of memory"))
  (let ((pair *free-list*))
    (set! *free-list*
          (gc-cdr *free-list*))
    pair))
  \end{scheme}
\end{frame}

\begin{frame}
  \frametitle{mark-and-sweep: problems}

  \begin{itemize}[<+->]
  \item How do we keep track of state during \texttt{mark}?
    \begin{itemize}
    \item What if all of memory is in one big list?
    \end{itemize}
  \item \texttt{sweep} needs to examine all of memory.
  \item \emph{Heap fragmentation} becomes a big problem.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{An alternate plan: Stop-and-copy}
  \begin{itemize}[<+->]
  \item To solve these problems, many real systems use some form of a
    \emph{copying} garbage collector.
  \item Our \emph{stop-and-copy} collector maintains two regions of
    memory, the \emph{working} memory and the \emph{free} memory.
  \item When we run out of memory, we \emph{copy} live objects into
    the free memory, and switch the roles of the halves.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Stop-and-Copy}
  \begin{itemize}
  \item We allocate pairs as we did initially with a \texttt{*free*}
    pointer.
  \item When we run out of memory, we switch the free and working
    memories, and we \emph{relocate} \texttt{root} into the new free
    memory.
  \item We use a new pointer, \texttt{scan}, initially pointing at the
    start of the new free memory.
  \item As long as \texttt{scan} < \texttt{*free*}, we relocate the
    \texttt{car} and \texttt{cdr} of \texttt{scan}, and increment
    \texttt{scan}.
  \end{itemize}
\end{frame}

\newcommand{\brokenheart}{\lower.5ex\hbox{\includegraphics[width=0.5em]{broken-heart}}}

\begin{frame}
  \frametitle{Relocation}
  \begin{itemize}
  \item To \emph{relocate} a pointer:
    \begin{itemize}
    \item If the value it points to has already been copied, update it
      to point at the new location.
    \item Otherwise, allocate a new pair, copy the pair it points to
      there, and
      \begin{itemize}
      \item Replace the \texttt{car} of the old pair with a tag known
        as a \emph{broken heart}(\brokenheart)
      \item Replace the \texttt{cdr} of the old pair with the pair's
        new address.
      \end{itemize}
     \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{tikzpicture}[scale=0.5]
    \coordinate (consA) at (0,0);
    \coordinate (consB) at (3,0);
    \coordinate (consC) at (6,0);
    \coordinate (consD) at (0,-3);
    \coordinate (consE) at (3,-3);
    \coordinate (numA)  at (6, -3);
    \coordinate (numB)  at (0, -6);
    \coordinate (numC)  at (3, -6);

    \cons(consA){1}
    \cons(consB){7}
    \cons(consC){3}\nullcdr
    \cons(consD){4}
    \cons(consE){6}\nullcdr
    \consnumber(numA){3}
    \consnumber(numB){1}
    \consnumber(numC){2}

    \consArrow{\car{consA}}{\edgeT{consD}}
    \consArrow{\cdr{consA}}{\edgeL{consB}}
    \consArrow{\car{consB}}{\edgeT{consE}}
    \consArrow{\cdr{consB}}{\edgeL{consC}}
    \consArrow{\car{consC}}{\edgeT{numA}}
    \consArrow{\car{consD}}{\edgeT{numB}}
    \consArrow{\cdr{consD}}{\edgeL{consE}}
    \consArrow{\car{consE}}{\edgeT{numC}}

    \draw[->] (-2,0.5) node[anchor=east] {\texttt{root}} -- (0,0.5);
  \end{tikzpicture}

  \vspace{1cm}

  \texttt{root: p1}

  \vspace{1cm}

  {\tt \small
  \begin{tabular}{rcccccccccl}
    Index & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \ldots \\
    \cline{2-11}
    the-cars 
    & \cell{} 
    & \cell{p4} 
    & \cell{} 
    & \cell{n3} 
    & \cell{n1} 
    & \cell{} 
    & \cell{n2} 
    & \cell{p6} 
    & \cell{} 
    & \ldots 
    \\ \cline{2-11}
    the-cdrs
    & \cell{} 
    & \cell{p7} 
    & \cell{} 
    & \cell{e0} 
    & \cell{p6} 
    & \cell{} 
    & \cell{e0} 
    & \cell{p3} 
    & \cell{} 
    & \ldots 
    \\ \cline{2-11}
  \end{tabular}}
\end{frame}

\begin{frame}
  \frametitle{}

  \texttt{root: \only<1-2>{p1}\only<3->{p0}}

  \vspace{1cm}

  {\tt \small
  \begin{tabular}{rcccccccccl}
    Index & 0 & \alert<3-4>{1} & 2 & \alert<13>{3} & \alert<5-7>{4} & 5 & \alert<10-11>{6} & \alert<8>{7} & 8 & \ldots \\
    \cline{2-11}
    \only<-16>{the}\only<17->{new}-cars
    & \cell{} 
    & \cell{\only<1-3>{p4}\only<4->{\brokenheart}} 
    & \cell{} 
    & \cell{\only<1-12>{n3}\only<13->{\brokenheart}} 
    & \cell{\only<1-6>{n1}\only<7->{\brokenheart}} 
    & \cell{} 
    & \cell{\only<1-9>{n2}\only<10->{\brokenheart}} 
    & \cell{\only<1-7>{p6}\only<8->{\brokenheart}} 
    & \cell{} 
    & \ldots
    \\ \cline{2-11}
    \only<-16>{the}\only<17->{new}-cdrs
    & \cell{} 
    & \cell{\only<1-3>{p7}\only<4->{p0}}
    & \cell{} 
    & \cell{\only<1-12>{e0}\only<13->{p4}}
    & \cell{\only<1-6>{p6}\only<7->{p1}}
    & \cell{} 
    & \cell{\only<1-9>{e0}\only<10->{p3}}
    & \cell{\only<1-7>{p3}\only<8->{p2}}
    & \cell{} 
    & \ldots
    \\ \cline{2-11}
    & 
    & 
    & 
    & 
    & 
    & 
    & 
    & 
    & 
    \\
    \\ *free*
    & \uncover<2>{$\downarrow$}
    & \uncover<3-5>{$\downarrow$}
    & \uncover<6-7>{$\downarrow$}
    & \uncover<8-9>{$\downarrow$}
    & \uncover<10-12>{$\downarrow$}
    & \uncover<13->{$\downarrow$}
    & 
    & 
    & 
    & \uncover<1>{$\uparrow$}
    \\
    & 
    & 
    & 
    & 
    & 
    & 
    & 
    & 
    & 
    & 
    \\ Index & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \ldots \\
    \cline{2-11}
    \only<-16>{new}\only<17->{the}--cars 
    & \cell{\alert<5-7>{\uncover<3->{\only<-5>{p4}\only<6->{p1}}}}
    & \cell{\uncover<6->{\alert<9>{n1}}} 
    & \cell{\alert<11-12>{\uncover<8->{\only<-11>{p6}\only<12->{p3}}}}
    & \cell{\alert<14>{\uncover<10->{n2}}}
    & \cell{\alert<15>{\uncover<13->{n3}}}
    & \cell{} 
    & \cell{} 
    & \cell{} 
    & \cell{} 
    & \ldots 
    \\ \cline{2-11}
    \only<-16>{new}\only<17->{the}-cdrs
    & \cell{\alert<8>{\uncover<3->{\only<-7>{p7}\only<8->{p2}}}}
    & \cell{\alert<10>{\uncover<6->{\only<-9>{p6}\only<10->{p3}}}} %\uncover<6->{p6}} 
    & \cell{\alert<13>{\uncover<8->{\only<-12>{p3}\only<13->{p4}}}}
    & \cell{\alert<14>{\uncover<10->{e0}}}
    & \cell{\alert<15>{\uncover<13->{e0}}}
    & \cell{} 
    & \cell{} 
    & \cell{} 
    & \cell{} 
    & \ldots 
    \\ \cline{2-11}
    \\ *scan*
    & \uncover<2-8>{$\uparrow$}
    & \uncover<9-10>{$\uparrow$}
    & \uncover<11-13>{$\uparrow$}
    & \uncover<14>{$\uparrow$}
    & \uncover<15>{$\uparrow$}
    & \uncover<16->{$\uparrow$}
    & 
    & 
    & 
    & 
  \end{tabular}}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{stop-and-copy}}
  \begin{scheme}
(define (stop-and-copy)
  (define (loop scan)
    (if (< scan *free*)
        (begin
          (vector-set! new-cars scan
                       (relocate
                        (vector-ref new-cars scan)))
          (vector-set! new-cdrs scan
                       (relocate
                        (vector-ref new-cdrs scan)))
          (loop (+ scan 1)))))
  (set! *free* 0)
  (set! *root* (relocate *root*))
  (loop 0)
  (swap-spaces))
  \end{scheme}
\end{frame}

\begin{frame}[fragile]
  \frametitle{\texttt{relocate}}
  \begin{scheme}
(define (relocate ptr)
  (if (gc-pair? ptr)
      (if (broken-heart? (gc-car pair))
          (gc-cdr pair)
          (let ((new-pair *free*))
            (set! *free* (+ 1 *free*))
            (vector-set! new-cars new-pair
                         (gc-car ptr))
            (vector-set! new-cdrs new-pair
                         (gc-cdr ptr))
            (gc-set-car! ptr *broken-heart*)
            (gc-set-cdr! ptr
                         (tag-pointer 'pair new-pair))
            (tag-pointer 'pair new-pair)))
      ptr))
  \end{scheme}
\end{frame}

\begin{frame}
  \frametitle{Properties of stop-and-copy}

  \begin{itemize}
  \item Since it moves things around, the garbage collector must know
    about \textit{every} pointer into the heap.
  \item Compacts used memory into a single chunk
    \begin{itemize}
    \item This means allocation is extremely efficient.
    \end{itemize}
  \item You only get to use half of your memory.
    \begin{itemize}
    \item But with mark-and-sweep you potentially needed that for the
      stack.
    \end{itemize}
  \item Most modern GCs use something that looks more like
    stop-and-copy than mark-and-sweep.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Generational GC}

  \begin{itemize}
  \item Think about the kinds of garbage a program creates.
  \item \texttt{find-primes} generated a lot of garbage, but it was
    very short-lived.
  \item In the adventure game, players, brains and items are created
    and destroyed, but tend to last a while first.
  \item This turns out to be true in general: A large amount of
    garbage is destroyed very quickly, whereas garbage that sticks
    around for a while is likely to stick around more.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Generational GC}
  \begin{itemize}
  \item Big Idea: Have two (or more!) memory pools.
  \item Allocate everything into a small one, and scan it every time
    you do a GC.
  \item If an object survives a few garbage collections, move it into
    a larger pool, which is only fully scanned rarely.
  \item Nearly every real modren GC works roughly this way.
  \end{itemize}
\end{frame}

\end{document}