<commit_before>\chapter{Garbage collector}

To fully appreciate the contents of this chapter, the reader should
have some basic knowledge of the usual techniques for garbage
collection.  We recommend ``The Garbage Collection Handbook''
\cite{Jones:2011:GCH:2025255} to acquire such basic knowledge.  We
also recommend <NAME>'s excellent survey paper
\cite{Wilson:1992:UGC:645648.664824}.

We think it would be good to use a per-thread nursery combined with a
global allocator for older objects.  This technique has been published
by Doligez and Leroy (see \cite{Doligez:1993:CGG:158511.158611}) and
perhaps in other papers as well.

In \refChap{chap-data-representation} we suggest a data representation
where every heap allocated object has a two-word header object.  If it
is a \texttt{cons} cell, then that is the entire object.  For other
heap-allocated objects (called \emph{genral instances}, the first of
the two words is a tagged pointer to the class object, and the second
of the two words is a raw pointer to the \emph{rack}.  In
this chapter, we describe the consequences of this suggested
representation to the garbage collector.

\section{Global collector}
No work has been done yet on the global collector.  

The global collector is a concurrent collector, i.e., it runs in
parallel with the mutator threads.  With modern processors, it is
probably practical to assign at least one core more or less
permanently to the global collector.  We suggest using a concurrent
mark-and-sweep collector.  With such a collector, objects
never move, a property which has several advantages.  For one thing,
pointers to objects can then freely be manipulated by foreign
functions without requiring that the foreign language be aware of when
the garbage collector is run.  Furthermore, objects that are keys in
an \texttt{eq} hash table can use the permanent address as a hash
value, and there is no need to reorganize the hash table as a result
of running the garbage collector. 

One main disadvantage of a memory-management system in which the
objects do not move is that \emph{fragmentation} can be a problem.
However, with our data representation, we imagine dividing the heap
into two parts; one part containing only header objects and another
part containing only racks.  Header object can, for
instance, be allocated at the beginning of the heap and rack
at the end of the heap, but there is no requirement that a
part be contiguous, nor for its size to be fixed.  Fragmentation in
the part containing header objects can now be eliminated because all
objects there have the same size.  Furthermore, since each rack
is referred to by exactly one header object, we can freely move
racks around%
\footnote{A rack can be moved only if no mutator register
  holds a pointer to one of its elements.  We have yet to work out the
  best way of making sure this restriction is respected.}  
without sacrificing our property that ``objects never move'', simply
because by ``object'' we mean the header object.  We suggest using bit
vectors to represent the ``color'' of each object.%
\footnote{Recall that \emph{black} means ``fully scanned'', \emph{white}
  means ``not yet seen'', and \emph{gray} means ``scanned but may
  refer to white objects''}
In a 64-bit system, 2 mark bits would be required for each 128-bit
header object.  Dead objects would be collected into a simply linked
list as usual. 

\section{Nursery collector}
The directory \texttt{Code/Garbage-collector} contains some code that
uses a different data representation from what we now suggest.  

For the nursery, we suggest using a copying collector to manage small
(a few megabytes) linear space.  Instead of promoting objects that
survive a collection, we suggest using a \emph{sliding collector} in
the nursery.  Such a collector gives a very precise idea of the age of
different objects, so objects would always be promoted in the order of
the oldest to the youngest.  This technique avoids the problem where
the allocation of some intermediate objects is immediately followed by
a collection, so these objects are promoted even though they are
likely to die soon after the collection.  In a sliding collector,
promotion will happen only when a collection leaves insufficient space
in the nursery, at which point only the number of objects required to
free up enough memory would be promoted, and in the strict order of
oldest to youngest.

We suggest allocating header objects from the beginning of the nursery
and racks from the end.  A garbage collection is triggered
when the two free pointers meet.  We preserve the relative order both
of header objects and of racks. 

In the \emph{mark phase}, a single mark bit per header object is
used.  Header objects and racks are scanned, but only
header objects are marked.  

In the \emph{header compaction phase}, live header objects are compacted
toward the beginning of the heap.  A \emph{source} and a \emph{target}
pointer follow blocks in the bitmap and live words are moved. 

In the \emph{table build phase}, the bitmap is used to construct an
\emph{offset table} at the end of the lower part of the heap.  The
offset table contains a sequence of pairs $<a,o>$ meaning that a
pointer with an address less than or equal to $a$ (and greater than
the corresponding field of the previous pair) should be adjusted by
offset $o$.  There is always enough room for this table, because it
can contain at most as many entries as there are dead header objects.  

In the \emph{adjust phase}, header objects and racks are
scanned, and fields containing pointers are adjusted according to the
offset table.  The offset table is searched using binary search. 

In the \emph{vector compaction phase}, header objects are scanned in
order of increasing addresses, and the corresponding racks
are compacted towards the end of the heap.

\section{Promotion}

Objects are typically promoted when the space recovered in the nursery
as a result of a thread-local garbage collection is deemed too small.%
\footnote{Here ``too small'' means that another garbage collection
  would be triggered very soon again, which is not desirable.}  When
this happens, a \emph{prefix} of the nursery (and the associated
racks in the suffix) is moved to the space managed by the
global collector.  Then, pointers are adjusted according to the size<commit_msg>Rewrote part of chapter to cite Kermany et al.<commit_after>\chapter{Garbage collector}

To fully appreciate the contents of this chapter, the reader should
have some basic knowledge of the usual techniques for garbage
collection.  We recommend ``The Garbage Collection Handbook''
\cite{Jones:2011:GCH:2025255} to acquire such basic knowledge.  We
also recommend <NAME>'s excellent survey paper
\cite{Wilson:1992:UGC:645648.664824}.

We think it would be good to use a per-thread nursery combined with a
global allocator for older objects.  This technique has been published
by Doligez and Leroy (see \cite{Doligez:1993:CGG:158511.158611}) and
perhaps in other papers as well.

In \refChap{chap-data-representation} we suggest a data representation
where every heap allocated object has a two-word header object.  If it
is a \texttt{cons} cell, then that is the entire object.  For other
heap-allocated objects (called \emph{genral instances}, the first of
the two words is a tagged pointer to the class object, and the second
of the two words is a raw pointer to the \emph{rack}.  In
this chapter, we describe the consequences of this suggested
representation to the garbage collector.

\section{Global collector}
No work has been done yet on the global collector.  

The global collector is a concurrent collector, i.e., it runs in
parallel with the mutator threads.  With modern processors, it is
probably practical to assign at least one core more or less
permanently to the global collector.  According to current thinking,
the global collector will be a combination of a mark-and-sweep
collector and a mark-and-compact collector as follows.  

We define a global heap where \texttt{cons} cells and the
\emph{headers} of general instances are allocated from the
\emph{beginning} of the heap and \emph{racks} are allocated from the
\emph{end}.  Since all general instances have a two-word header and
\texttt{cons} cells consist of two words as well, we can use a
mark-and-sweep collector for these objects without suffering any
fragmentation.  The advantage of a mark-and-sweep collector is that
objects will never move, which is an advantage when they are used as
keys in hash tables and when they are used to communicate with
code in foreign languages that assume that an address of an object is
fixed once and for all.

For the racks, we plan to use the sliding collector created by Kermany
et all \cite{Kermany:2006:CCI:1133981.1134023}.  Their collector uses
very little additional memory because, although it define two semi
spaces, nearly half of the pages will always be \emph{virtual}, i.e.,
without any backing store.  Furthermore, their collector is
\emph{parallel}, meaning that several threads can collect
simultaneously and \emph{concurrent}, i.e., it can work in parallel
with mutator threads.  We do not plan to use this collector for the
nurseries, because it uses memory-mapping techniques which incur
additional cost.

Even though racks more around, objects do not, simply because the
objects \emph{is} the header, and headers do not move.  

\section{Nursery collector}
The directory \texttt{Code/Garbage-collector} contains some code that
uses a different data representation from what we now suggest.  

For the nursery, we suggest using a copying collector to manage small
(a few megabytes) linear space.  Instead of promoting objects that
survive a collection, we suggest using a \emph{sliding collector} in
the nursery.  Such a collector gives a very precise idea of the age of
different objects, so objects would always be promoted in the order of
the oldest to the youngest.  This technique avoids the problem where
the allocation of some intermediate objects is immediately followed by
a collection, so these objects are promoted even though they are
likely to die soon after the collection.  In a sliding collector,
promotion will happen only when a collection leaves insufficient space
in the nursery, at which point only the number of objects required to
free up enough memory would be promoted, and in the strict order of
oldest to youngest.

We suggest allocating header objects from the beginning of the nursery
and racks from the end.  A garbage collection is triggered
when the two free pointers meet.  We preserve the relative order both
of header objects and of racks. 

In the \emph{mark phase}, a single mark bit per header object is
used.  Header objects and racks are scanned, but only
header objects are marked.  

In the \emph{header compaction phase}, live header objects are compacted
toward the beginning of the heap.  A \emph{source} and a \emph{target}
pointer follow blocks in the bitmap and live words are moved. 

In the \emph{table build phase}, the bitmap is used to construct an
\emph{offset table} at the end of the lower part of the heap.  The
offset table contains a sequence of pairs $<a,o>$ meaning that a
pointer with an address less than or equal to $a$ (and greater than
the corresponding field of the previous pair) should be adjusted by
offset $o$.  There is always enough room for this table, because it
can contain at most as many entries as there are dead header objects.  

In the \emph{adjust phase}, header objects and racks are
scanned, and fields containing pointers are adjusted according to the
offset table.  The offset table is searched using binary search,
except that a simple caching scheme is used to avoid a full binary
search in nearly all cases. 

In the \emph{rack compaction phase}, header objects are scanned in
order of increasing addresses, and the corresponding racks
are compacted towards the end of the heap.

\section{Promotion}

Objects are typically promoted when the space recovered in the nursery
as a result of a thread-local garbage collection is deemed too small.%
\footnote{Here ``too small'' means that another garbage collection
  would be triggered very soon again, which is not desirable.}  When
this happens, a \emph{prefix} of the nursery (and the associated
racks in the suffix) is moved to the space managed by the
global collector.  Then, pointers are adjusted according to the size
{'fraction_non_alphanumeric': 0.042577120822622105, 'fraction_numerical': 0.008836760925449872, 'mean_word_length': 4.481726111845002, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7473548', 'n_tokens_mistral': 3225, 'n_tokens_neox': 2999, 'n_words': 1939}