Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Tree: b42f14e3c2
Fetching contributors…

Cannot retrieve contributors at this time

246 lines (207 sloc) 10.217 kB
\begin{enumerate}
\item heap \\
Most OCaml blocks are created in the minor(young) heap.
\begin{enumerate}[(a)]
\item minor heap ( \textit{32K words for 32 bit, 64K for 64 bit by default})
in my mac, i use ``ledit ocaml -init x'' to avoid loading startup
scripts, then
\begin{alternate}
Gc.stat ()
\end{alternate}
\begin{ocamlcode}
{Gc.minor_words = 104194.; Gc.promoted_words = 0.; Gc.major_words = 43979.;
Gc.minor_collections = 0; Gc.major_collections = 0; Gc.heap_words = 126976;
Gc.heap_chunks = 1; Gc.live_words = 43979; Gc.live_blocks = 8446;
Gc.free_words = 82997; Gc.free_blocks = 1; Gc.largest_free = 82997;
Gc.fragments = 0; Gc.compactions = 0; Gc.top_heap_words = 126976;
Gc.stack_size = 52}
\end{ocamlcode}
\begin{alternate}
78188 lsr 16 ;;
- : int = 1
\end{alternate}
\begin{bluetext}
+---------------------------------------------------------+
| unallocated |///allocated part/////////|
+---------------------------------------------------------+
^ ^
| |
caml_young_limit caml_young_ptr
<----- allocation proceeds
in this direction
\end{bluetext}
Consider \textit{the array of two elements}, the total size of this object \textit{will be 3 words (header + 2 words)}, so 24 bytes for 64-bit , so the fast path for allocation is
subtract size from caml\_young\_ptr.
If caml\_young\_ptr $<$ caml\_young\_limit, then take the slow path through the garbage collector.
The fast path just \textbf{ five machine instructions and no branches}. But even
five instructions are costly in inner loops, be careful.
\item major heap \\
when the minor heap runs out, it triggers a \textbf{minor collection}. The minor
collection starts at all the local roots and \textit{oldifies} them, basically copies
them by reallocating those objects (recursively) \textbf{ to the major heap}. After
this, any object left in the minor heap \textbf{ are unreachable}, so the minor heap
can be reused by resetting \textbf{ caml\_young\_ptr }.
\begin{bluetext}
reachable reachable
+---------+---------+------+----+----+-----------------+
| |/////////| |///-->///| |
+---------+---------+------+----+----+-----------------+
^ ^
| |
local root local root
\end{bluetext}
At runtime the garbage collector \textit{always} knows what is a pointer, and what is an int
or opaque data (like a string). Pointers get scanned so the GC can find unreachable
blocks. Ints and opaque data must not be scanned. \textit{This is the reason for having a tag
bit for integer-like values}, and one of the uses of the tag byte in the header.
\begin{bluetext}
"Tag byte space"
+----------+
| 0 | Array, tuple, etc.
+----------+
| 1 |
+----------+
| 2 |
~ ~
| | Tags in the range 0..245 are used for variants
~ ~
| 245 |
+----------+
| 246 | Lazy (before being forced)
+----------+
| 247 | Closure
+----------+
| 248 | Object ^
+----------+ | Block contains
| 249 | Used to implement closures | values which the
+----------+ | GC should scan
| 250 | Used to implement lazy values |
+----------+ <--------------------------- No_scan_tag
| 251 | Abstract data |
+----------+ | Block contains
| 252 | String | opaque data
+----------+ | which GC must
| 253 | Double V not scan
+----------+
| 254 | Array of doubles
+----------+
| 255 | Custom block
+----------+
\end{bluetext}
so, in the normal course of events, a small, long-lived object will start on the
minor heap and be copied into the major heap. \textbf{ Large objects go straight to
the major heap}
But there is another important structure used in the major heap, called the
\textbf{ page table}. The garbage collector must at all times know which pieces of
memory belong to the major heap, and which pieces of memory do not, and it uses
the page table to track this.
One reason \textbf{ why we always want to know where the major heap lies }
is so we can avoid
scanning pointers which point to C structs outside the OCaml heap.
The GC will not stray beyond its own heap, and treats all pointers outside as
opaque (it doesn't touch them or follow them).
In OCaml 3.10 the page table was implemented as a simple bitmap, with 1 bit per page
of virtual memory (major heap chunks are always page-aligned). This was
unsustainable for 64 bit address spaces where memory allocations can be very very
\textbf{ far apart}, so in OCaml 3.11 this was changed to a sparse hash table.
Because of the page table, C pointers can be stored directly as values, which
saves time and space. (However, if your C pointer later gets freed, you must NULL
the value-the reason is that the same memory address might later get malloced
for the OCaml major heap, thus \textit{suddenly} becoming a \textit{valid} address again.
THIS usually results in crash ).
In a functional language \textbf{ which does not allow any mutable references}, there's one
guarantee you can make which is there could \textbf{ never be a pointer going from the major heap
to something in the minor heap}, so when an object in an immutable language graduates from the
minor heap to the major heap, it is fixed forever(until it becomes unreachable), and can not
point back to the minor heap.
But ocaml is impure, so if the minor heap collection worked exactly as previous, then the outcome
wouldn't be good, maybe some object is not pointed at \textbf{ by any local root}, so it would
be \textit{unreachable} and would \textit{disappear}, leaving a \textbf{ dangling pointer}.
\textbf{ one solution would be to check the major heap, but that would be massively time-consuming:
minor-collections are supposed to be very quick }
What OCaml does instead is to have a separate \textit{refs} list. This contains a list of pointers
that point \textbf{ from the major heap to the minor heap}. During a minor heap collection, the
refs list is consulted for additional roots(and after the minor heap collection, the refs list
can be started anew).
The refs list however has to be updated, and it gets \textbf{ updated potentially every time we modify a mutable
field in a struct}. The code calls the c function \textbf{ caml\_modify} which both mutates the struct a
nd decides whether this is a major$\rightarrow$minor pointer to be
added to the refs list.
If you use mutable fields then this is \textbf{ much slower} than a
simple assignment. However, \textbf{ mutable integers} are ok, and
don't trigger the extra call. You can also \textbf{ mutate fields}
yourself, eg. from c functions or using Obj, \textbf{ provied you can
guarantee that this won't generate a pointer between the major and
minor heaps}.
The OCaml gc does not collect the major heap in one go. It spreads
the work over small \textbf{ slices}, and splices are grouped into
whole \emph{phases} of work.
\emph{A slice} is just a defined amount of work.
The phases are mark and sweep, and some additional sub-passes
dealing with weak pointers and finalization.
Finally there is \emph{a compaction phase} which is triggered when
there is no other work to do and the estimate of free space in the
heap has reached some threshold. This is tunable. You can schedule
when to compact the heap -- while waiting for a key-press or
between frames in a live simulation.
There is also a penalty for doing a slice of the major heap -- for
example if the minor heap is exhausted, then some activity in the
major heap is unavoidable. However if you make the \textbf{ minor heap
large enough}, you can completely control when GC work is
done. You can also move \emph{large structures out of the major
heap entirely},
\end{enumerate}
\item module Gc
\begin{bluetext}
Gc.compact () ;;
let checkpoint p = Gc.compact () ; prerr_endline ("checkpoint at poisition " ^ p )
\end{bluetext}
The checkpoint function does two things:
\textit{Gc.compact () } does a full major round of garbage
collection and compacts the heap. This is the most aggressive form of
Gc available, and it's highly likely to \textit{segfault} if the heap is corrupted.
\textit{prerr\_endline} prints a message to stderr and crucially
also flushes stderr, so you will see the message printed immediately.
you \textbf{should} grep for \verb|caml_heap_check| in byterun for details
\begin{ocamlcode}
void caml_compact_heap (void)
{
char *ch, *chend;
Assert (caml_gc_phase == Phase_idle);
caml_gc_message (0x10, "Compacting heap...\n", 0);
#ifdef DEBUG
caml_heap_check ();
#endif
#ifdef DEBUG
void caml_heap_check (void)
{
heap_stats (0);
}
#endif
#ifdef DEBUG
++ major_gc_counter;
caml_heap_check ();
#endif
\end{ocamlcode}
\item tune \\
problems can arise when you're building up ephemeral
data structures which are larger than the minor heap.
The data structure won't stay around overly long, but
it is a bit too large. Triggering major GC slices more
often can cause static data to be walked and re-walked
more often than is necessary.
\href{http://elehack.net/michael/blog/2010/06/ocaml-memory-tuning}{tuning} sample
\begin{ocamlcode}
let _ =
let gc = Gc.get () in
gc.Gc.max_overhead <- 1000000;
gc.Gc.space_overhead <- 500;
gc.Gc.major_heap_increment <- 10_000_000;
gc.Gc.minor_heap_size <- 10_000_000;
Gc.set gc
\end{ocamlcode}
\end{enumerate}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../master"
%%% End:
Jump to Line
Something went wrong with that request. Please try again.