Reorganisation of the source tree

[ghc-hetmet.git] / docs / storage-mgt / ldv.tex

\documentclass{article}
\usepackage{code,a4wide}

\usepackage{graphics,epsfig,epic,eepic,epsfig}

\setlength{\parskip}{0.25cm}
\setlength{\parsep}{0.25cm}
\setlength{\topsep}{0cm}
\setlength{\parindent}{0cm}
\renewcommand{\textfraction}{0.2}
\renewcommand{\floatpagefraction}{0.7}


% Terminology
\newcommand{\block}{block}
\newcommand{\Block}{Block}
\newcommand{\segment}{segment}
\newcommand{\Segment}{Segment}
\newcommand{\step}{step}
\newcommand{\Step}{Step}

\newcommand{\note}[1]{{\em $\spadesuit$ #1}}

\begin{document}
\title{Implementation of Lag/Drag/Void/Use Profiling}
\author{Sungwoo Park \\ Simon Marlow}

\makeatactive
\maketitle

\section{Lag/Drag/Void/Use Profiling}

\emph{Lag/Drag/Void/Use} (LDVU) profiling~\cite{RR} is a profiling technique 
which yields a summary of the biography of all the dynamic closures created
during program execution.
In this profiling scheme,
the biography of a closure is determined by four important events associated
with the closure: \emph{creation}, \emph{first use}, 
\emph{last use}, and \emph{destruction} (see Figure~\ref{fig-ldv}).
The intervals between these successive events correspond to three phases
for the closure: \emph{lag} (between creation and first use), 
\emph{use} (between first use and last use), and 
\emph{drag} (between last use and destruction).
If the closure is never used, it is considered to remain in the \emph{void}
phase all its lifetime.

\begin{figure}[ht]
\begin{center}
\input{ldv.eepic}
\caption{The biography of a closure}
\label{fig-ldv}
\end{center}
\end{figure}

The LDVU profiler regularly performs heap censuses during program execution.
Each time a heap census is performed, the LDVU profiler increments a global
time, which is used for timing all the events (such as creation and destruction
of a closure) occurring during program execution.
Hence, for instance, all closures creating between two successive heap censuses
have the same creation time and belong to the same \emph{generation}.\footnote{In
this document, a generation is related with heap censuses, not garbage collections
as in other profiling schemes.}
After the program terminates, it yields a post-mortem report on how much 
of the \emph{live} graph is in one of the four phases at the moment of each 
heap census.

It must be emphasized that the LDVU profiler considers only live closures;
it should not take into consideration dead closures which do not constitute
the graph. Therefore, the result of LDVU profiling does not depend on the
frequency of garbage collections.

This document describes the implementation of LDVU profiling on the Glasgow
Haskell Compiler runtime system.\footnote{Unless otherwise noted, all identifiers
are defined in @LdvProfile.c@}.

\section{An Overview of the Implementation}

Every closure is augmented with an additional word in its profiling header
to accommodate three additional pieces of information: 
1) state flag indicating whether the closure has been used at least once or not.
2) creation time; 3) time of most recent use if any so far.
We refer to such a word as an LDV word.

The LDVU profiler maintains a global time, stored in @ldvTime@.
It is incremented each time a heap census is performed.
During a heap census, the profiler scans all live closures and computes the 
following: 
1) the total size of all closures which have never been used; 
2) the total size of all closures which have been used at least once 
in the past.\footnote{There is another category of closures, namely, 
\emph{inherently used} closures. We will explain 
in Section~\ref{sec-heap-censuses}.}
It is not until the whole program execution finishes that the profiler 
can actually decide the total size corresponding to each of the four phases for
a particular heap census. It is only when a closure is destroyed that the profiler
can determine how long the closure has been in a specific phase. 
Therefore, it is not sufficient to perform heap censuses periodically in order to
compute the profiling statistics: the runtime system needs to intercept
all events associated with any closures and update necessary information.

All events associated with closures are handled by one of the three 
macros defined
in @includes/StgLdv.h@: @LDV_recordCreate()@, @LDV_recordUse()@, and 
@LDV_recordDead()@.

\begin{itemize}
\item{@LDV_recordCreate()@} is called when a closure is created and updates its 
creation time field.

\item{@LDV_recordUse()@} is called when a closure is used and updates its most recent
use time field.

\item{@LDV_recordDead()@} is called when a closure @c@ is removed from the graph.
It does not update its LDV word (because @c@ is about to be destroyed).
Instead, it updates the statistics on LDVU profiling according to the following
observation:
if @c@ has never been used (which is indicated by the state flag in its LDV 
word), 
@c@ contributes to the void phase from its creation time to the last census
time; if @c@ was used at least once (which is also indicated by the state flag),
@c@ contributes to the @drag@ phase after its last use time. 
\end{itemize}

At the end of the program execution, the profiler performs a last census during
which all closures in the heap are declared to be dead and @LDV_recordDead()@
is invoked on each of them. 
Then, the profiler computes the final statistics. 

\section{LDV Words}

We choose to share the LDV word for both retainer profiling and LDVU 
profiling, which cannot take place simultaneously. 
This is the reason why there is a
union structure inside the @StgProHeader@ structure.
The field @hp.ldvw@ in the @StgProfHeader@ structure corresponds to the LDV 
word:
\begin{code}
typedef struct {
  ...
  union {
    retainerSet *rs;          // Retainer Set
    StgWord ldvw;             // Lag/Drag/Void Word
  } hp;
} StgProfHeader;
\end{code}
For instance, the LDV word of a closure @c@ can now be accessed with 
@c->header.prof.hp.ldvw@ (or by @LDVW(c)@ where @LDVW()@ is a macro in 
@includes/StgLdvProf.h@).

An LDV word is divided into three fields, whose position is specified
by three constants in @includes/StgLdvProf.h@:
\begin{itemize}
\item{@LDV_STATE_MASK@} corresponds to the state flag. 
\item{@LDV_CREATE_MASK@} corresponds to the creation time.
\item{@LDV_LAST_MASK@} corresponds to the most recent use time.
\end{itemize}
The constant @LDV_SHIFT@ specifies how many bits are allocated for 
creation time or most recent use time.
For instance, the creation time of a closure @c@ can be obtained by
@(LDVW(c) & LDV_CREATE_MASK) >> LDV_SHIFT@.

The creation time field and the most recent use time field can be set only by the 
macros @LDV_recordCreate()@ and @LDV_recordUse()@. 
@LDV_recordCreate()@ must be called whenever a new dynamic closure is created,
and this is handily accomplished by rewriting the macro @SET_PROF_HDR()@ 
(in @includes/ClosureMacros.h@) (we do not need to change @SET_STATIC_PROF_HDR()@
because static closures are not involved in LDVU profiling at all):

\begin{code}
#define SET_PROF_HDR(c,ccs_)            \
        ((c)->header.prof.ccs = ccs_,   \
        LDV_recordCreate((c)))
\end{code}

There are a few cases in which the info table of a closure changes through
an explicit invocation of @SET_INFO()@ or a direct assignment to its @header.info@
field: 1) an indirection closure is replaced by an old-generation 
indirection closure; 2) a thunk is replaced by a blackhole; 3) a thunk is replaced 
by an indirection closure when its evaluation result becomes available.

\emph{We regard such a situation as
the destruction of an old closure followed by the creation of a new closure
at the same memory address.}\footnote{This would be unnecessary if the two closures
are of the same size, but it is not always the case. We choose to distinguish
the two closures for the sake of consistency.}
For instance, when an @IND_PERM@ closure is replaced by an @IND_OLDGEN_PERM@
closures (during scavenging in @GC.c@), we wrap the invocation of @SET_INFO()@ with 
the invocations of @LDV_recordDead()@ and @LDV_recordCreate()@ as follows 
(@LDV_recordDead()@ requires the actual size of the closures being destroyed):

\begin{code}
  LDV_recordDead((StgClosure *)p, sizeofW(StgInd) - sizeofW(StgProfHeader));
  SET_INFO(((StgClosure *)p), &stg_IND_OLDGEN_PERM_info);
  LDV_recordCreate((StgClosure *)p);
\end{code}

\textbf{To do:}
A direct assignment to the @header.info@ field implies that its cost centre 
field is not initialized. This is no problem in the case of @EVACUATED@ closures 
because they will 
not be used again after a garbage collection. However, I am not sure if this is safe
for @BLACKHOLE_BQ@ closures (in @StgMiscClosures.hc@) when retainer profiling, 
which employs cost centre stacks, is going on. 
If it is safe, please leave a comment there.

@LDV_recordUse()@ is called on a closure whenever it is used, or \emph{entered}.
Its state flag changes if necessary to indicate that it has been used, and
the current global time is stored in its last use time field. 

\section{Global Time \texttt{ldvTime} and Retainer Profiling}

The global time, stored in @ldvTime@, records the current time period.
It is initialized to $1$ and incremented after each time a heap census
is completed through an invocation of @LdvCensus()@.  Note that each
value of @ldvTime@ represents a time \emph{period}, not a point in
time.

All closures created between two successive invocations of
@LdvCensus()@ have the same creation time.  If a closure is used at
least once between two successive heap censuses, we consider the
closure to be in the use phase during the corresponding time period
(because we just set its last use time field to the current value of
@ldvTime@ whenever it is used).  Notice that a closure with a creation
time $t_c$ may be destroyed before the actual heap census for time
$t_c$ and thus may \emph{not} be observed during the heap census for
time $t_c$.  Such a closure does not show up in the profile at all.

In addition, the value of @ldvTime@ indicates which of LDVU profiling
and retainer profiling is currently active: during LDVU profiling, it
is initialized to $1$ in @initLdvProfiling()@ and then increments as
LDVU profiling proceeds; during retainer profiling, however, it is
always fixed to $0$.  Thus, wherever a piece of code shared by both
retainer profiling and LDVU profiling comes to play, we usually need
to first examine the value of @ldvTime@ if necessary. For instance,
consider the macro @LDV_recordUse()@:

\begin{code}
#define LDV_recordUse(c)                              \
  if (ldvTime > 0)                                    \
    LDVW((c)) = (LDVW((c)) & LDV_CREATE_MASK) | ldvTime | LDV_STATE_USE; 
\end{code}

If retainer profiling is being performed, @ldvTime@ is equal to $0$,
and @LDV_recordUse()@ causes no side effect.\footnote{Due to this
interference with LDVU profiling, retainer profiling slows down a bit;
for instance, checking @ldvTime@ against $0$ in the above example
would always evaluate to @rtsFalse@ during retainer profiling.
However, this is the price to be paid for our decision not to employ a
separate field for LDVU profiling.}

As another example, consider @LDV_recordCreate()@:

\begin{code}
#define LDV_recordCreate(c)   \
  LDVW((c)) = (ldvTime << LDV_SHIFT) | LDV_STATE_CREATE
\end{code}

The above definition of @LDV_recordCreate()@ works without any problem
even for retainer profiling: during retainer profiling, 
a retainer set field (@hp.ldvw@) must be initialized to a null pointer.
Since @ldvTime@ is fixed to $0$, @LDV_recordCreate()@ initializes 
retainer set fields correctly.

\section{Heap Censuses}
\label{sec-heap-censuses}

The LDVU profiler performs heap censuses periodically by invoking the
function @LdvCensus()@.  Because we need to know exactly which
closures in the heap are live at census time, we always precede the
census with a major garbage collection.

During a census, we examine each closure one by one and compute the
following three quantities:

\begin{enumerate}
\item the total size of all \emph{inherently used} closures.
\item the total size of all closures which have not been used (yet).
\item the total size of all closures which have been used at least once. 
\end{enumerate}

For most closures, a \emph{use} consists of entering the closure.  For
unlifted objects which are never entered (eg. @ARR_WORDS@), it would
be difficult to determine their points of use because such points are
scattered around the implementation in various primitive operations.
For this reason we consider all unlifted objects as ``inherently
used''.  The following types of closures are considered to be
inherently used: @TSO@, @MVAR@, @MUT_ARR_PTRS@, @MUT_ARR_PTRS_FROZEN@,
@ARR_WORDS@, @WEAK@, @MUT_VAR@, @MUT_CONS@, @FOREIGN@, @BCO@, and
@STABLE_NAME@.

The three quantities are stored in an @LdvGenInfo@ array @gi[]@.
@gi[]@ is indexed by time period.  For instance, @gi[ldvTime]@ stores
the three quantaties for the current global time period.  The
structure @LdvGenInfo@ is defined as follows:

\begin{code}
typedef struct {
  ...
  int inherentlyUsed;   // total size of 'inherently used' closures
  int notUsed;          // total size of 'not used yet' closures
  int used;             // total size of 'used at least once' closures
  ...
} LdvGenInfo;
\end{code} 

The above three quantities account for mutually exclusive sets of closures.
In other words, if a closure is not inherently used, it belongs to 
either the second or the third.

\subsection{Taking a Census of the Live Heap}

During a heap census, we need to visit every live closure once, so we
perform a linear scan of the live heap after a major GC.  We can take
advantage of the following facts to implement a linear scan for heap
censuses:

\begin{itemize}
\item The nursery is empty. The small object pool and the large object pool, 
      however, may \emph{not} be empty. This is because the garbage collector
      invokes @scheduleFinalizer()@ after removing dead closures, and
      @scheduleFinalizer()@ may create new closures through @allocate()@.
\item @IND@, @IND_OLDGEN@, and @EVACUATED@ closures do not appear in
the live heap.
\end{itemize}

There is one small complication when traversing the live heap: the
garbage collector may have replaced @WEAK@ objects with @DEAD_WEAK@
objects, which have a smaller size and hence leave some space before
the next object.  To avoid this problem we change the size of
@DEAD_WEAK@ objects to match that of @WEAK@ objects when profiling is
enabled (see @StgMiscClosures.hc@).

\section{Destruction of Closures}

In order to compute the total size of closures for each of the four
phases, we must report the destruction of every closure (except
inherently used closures) to the LDVU profiler by invoking
@LDV_recordDead()@.  @LDV_recordDead()@ must not be called on any
inherently used closure because any invocation of @LDV_recordDead()@
affects the statistics regarding void and drag phases, which no
inherently used closure can be in.

@LDV_recordDead()@ updates two fields @voidNew@ and @dragNew@ in the
@LdvGenInfo@ array @gi[]@:

\begin{code}
typedef struct {
  ...
  int voidNew; 
  int dragnew;
  ...
} LdvGenInfo;
\end{code} 

@gi[ldvTime].voidNew@ accumulates the size of all closures satisfying
the following two conditions: 1) observed during the heap census at
time @ldvTime@; 2) now known to have been in the void phase at time
@ldvTime@.  It is updated when a closure which has never been used is
destroyed.  Suppose that a closure @c@ which has never been used is
about to be destroyed.  If its creation time is $t_c$, we judge that
@c@ has been in the void phase all its lifetime, namely, from time
$t_c$ to @ldvTime@.  Since @c@ will not be observed during the next
heap census, which corresponds to time @ldvTime@, @c@ contributes to
the void phase of times $t_c$ through @ldvTime@ - 1.  Therefore, we
increase the @voidNew@ field of @gi[@$t_c$@]@ through @gi[ldvTime - 1]@
 by the size of @c@.\footnote{In the actual implementation, we
update @gi[$t_c$]@ and @gi[ldvTime]@ (not @gi[ldvTime@$ - $1@]@) only:
@gi[$t_c$]@ and @gi[ldvTime]@ are increased and decreased by the size
of @c@, respectively.  After finishing the program execution, we can
correctly adjust all the fields as follows: @gi[$t_c$]@ is computed as
$\sum_{i=0}^{t_c}$@gi[$i$]@.  }

@gi[ldvTime].dragNew@ accumulates the size of all closures satisfying the following
two conditions: 1) observed during the heap census at time @ldvTime@;
2) now known to have been in the drag phase at time @ldvTime@.
It is updated when a closure which has been used at least once is destroyed.
Suppose that a closure @c@ which has been used last at time $t_l$ is about to
be destroyed.
We judge that @c@ has been in the drag phase from time $t_l + 1$ to 
time @ldvTime@$ - 1$ (if $t_l + 1 > $@ldvTime@$ - 1$, nothing happens).
Therefore, we increase the @dragNew@ field of @gi[@$t_l + 1$@]@ through 
@gi[ldvTime@$ - 1$@]@
by the size of @c@.\footnote{As in the case of @voidNew@, we update
@gi[@$t_l + 1$@]@ and @gi[ldvTime]@ only.}

Now we need to find out all the cases of closure destruction.
There are four cases in which a closure is destroyed:

\begin{enumerate}
\item A closure is overwritten with a blackhole: 
  @UPD_BH_UPDATABLE()@ and @UPD_BH_SINGLE_ENTRY()@ in @includes/StgMacros.h@,
  @threadLazyBlackHole()@ and @threadSqueezeStack()@ in @GC.c@,
  the entry code for @BLACKHOLE@ closures in @StgMiscClosures.hc@ (a 
  @BLACKHOLE@ closure is changed into a @BLACKHOLE_BQ@ closure).
  We call either @LDV_recordDead()@ or @LDV_recordDead_FILL_SLOP_DYNAMIC()@.

\item A weak pointer is overwritten with a dead weak pointer:
  @finalizzeWeakzh_fast()@ in @PrimOps.hc@, 
  @finalizeWeakPointersNow()@ and @scheduleFinalizers()@ in @Weak.c@.
  Since a weak pointer is inherently used, we do not call @LDV_recordDead()@.

\item A closure is overwritten with an indirection closure:
  @updateWithIndirection()@ and @updateWithPermIndirection()@ in @Storage.h@,
  @scavenge()@ in @GC.c@, in which an @IND_PERM@ closure is explicitly replaced
  with an @IND_OLDGEN_PERM@ closure during scavenging.
  We call either @LDV_recordDead()@ or @LDV_recordDead_FILL_SLOP_DYNAMIC()@.
  
\item Closures are removed permanently from the graph during garbage
collections.  We locate and dispose of all dead closures by linearly
scanning the from-space right before tidying up.  This is feasible
because any closures which is about to be removed from the graph still
remains in the from-space until tidying up is completed.  The next
subsection explains how to implement this idea.
\end{enumerate}

\subsection{Linear scan of the from-space during garbage collections}

In order to implement linear scan of the from-space during a garbage collection 
(before tidying up),
we need to take into consideration the following facts:

\begin{itemize}
\item The pointer @free@ of a block in the nursery may incorrectly point to
a byte past its actual boundary.
This happens because 
the Haskell mutator first increases @hpLim@ without comparing it with the
actual boundary when allocating fresh memory for a new closure.
@hpLim@ is later assigned to the pointer @free@ of the corresponding memory
block, which means that during a heap census, the pointer @hpLim@ may not
be trusted. 
Notice that @hpLim@ is not available during LDVU profiling; it is valid
only during the Haskell mutator time.

\item The from-space may well contain a good number of @EVACUATED@ closures,
and they must be skipped over.

\item The from-space includes the nursery. 
Furthermore, a closure in the nursery may not necessarily be adjacent to the next 
closure because slop words may lie between the two closures;
the Haskell mutator may allocate more space than actually needed in the
nursery when creating a closure, potentially leaving slop words. 
\end{itemize}

The first problem is easily solved by limiting the scan up to the
actual block boundary for each nursery block (see
@processNurseryForDead()@).  In other words, for a nursery block
descriptor @bd@, whichever of @bd->start@$ + $@BLOCK_SIZE_W@ and
@bd->free@ is smaller is used as the actual boundary.

We solve the second problem by exploiting LDV words of @EVACUATED@
closures: we store the size of an evacuated closure, which now resides
in the to-space, in the LDV word of the new @EVACUATED@ closure
occupying its memory.  This is easily implemented by inserting a call
to the macro @SET_EVACUAEE_FOR_LDV()@ in @copy()@ and @copyPart()@ (in
@GC.c@).  Thus, when we encounter an @EVACUATED@ closure while
linearly scanning the nursery, we can skip a correct number of words
by referring to its LDV word.

The third problem could be partially solved by always monitoring @Hp@
during the Haskell mutator time: whenever @Hp@ is increased, we fill
with zeroes as many words as the change of @HP@. Then, we could skip
any trailing zero words when linearly scanning the nursery.
Alternatively we could initialize the entire nursery with zeroes after
each garbage collection and not worry about any change made to @Hp@
during the Haskell mutator time.  The number of zero words to be
written to the nursery could be reduced in the first approach, for we
do not have to fill the header for a new closure.  Nevertheless we
choose to employ the second approach because it simplifies the
implementation code significantly (see @resetNurseries()@ in
@Storage.c@).  Moreover, the second approach compensates for its
redundant initialization cost by providing faster execution (due to a
single memory write loop in contrast to frequent memory write loops in
the first approach).  Also, we attribute the initialization cost to
the runtime system and thus the Haskell mutator behavior is little
affected.

There is further complication though: occasionally a closure is
overwritten with a closure of a smaller size, leaving some slop
between itself and the next closure in the heap.  There are two cases:

\begin{enumerate}
\item A closure is overwritten with a blackhole. 
\item A closure is overwritten with an indirection closure.
\end{enumerate}

In either case, an existing closure is destroyed after being replaced
with a new closure.  If the two closures are of the same size, no slop
words are introduced and we only need to invoke @LDV_recordDead()@ on
the existing closure, which cannot be an inherently used closure.  If
not, that is, the new closure is smaller than the existing closure
(the opposite cannot happen), we need to fill one or more slop words
with zeroes as well as invoke @LDV_recordDead()@ on the existing
closure.  The macro @LDV_recordDead_FILL_SLOP_DYNAMIC()@ accomplishes
these two tasks: it determines the size of the existing closure,
invokes @LDV_recordDead()@, and fills the slop words with zeroes.
After excluding all cases in which the two closures are of the same
size, we invoke @LDV_recordDead_FILL_SLOP_DYNAMIC()@ only from:

\begin{enumerate}
\item @threadLazyBlackHole()@ and @threadSqueezeStack()@ in @GC.c@
(for lazy blackholing),
\item @UPD_BH_UPDATABLE()@ and @UPD_BH_SINGLE_ENTRY()@ in
@includes/StgMacros.h@ (for eager blackholing, which isn't the
default),
\item @updateWithIndirection()@ and @updateWithPermIndirection()@ 
in @Storage.h@.\footnote{Actually slop words created in 
@updateWithIndirection()@ cannot survive major garbage collections.
Still we invoke @LDV\_recordDead\_FILL\_SLOP\_DYNAMIC()@ to support linear
scan of the heap during a garbage collection, which is discussed in the next
section.}
\end{enumerate}

The linear scan of the from-space is initiated by the garbage
collector.  From the function @LdvCensusForDead()@, every dead closure
in the from-space is visited through an invocation of
@processHeapClosureForDead()@.

\subsection{Final scan of the heap}

Since a closure surviving the final garbage collection is implicitly destroyed
when the runtime system shuts down, we must invoke @processHeapClosureForDead@
on \emph{every} closure in the heap once more after the final garbage collection.
The function @LdvCensusKillAll()@, which is invoked from @shutdownHaskell()@
in @RtsStartup.c@, traverses the entire heap and visits each closure.
It also stops LDVU profiling by resetting @ldvTime@ to $0$. 

It may be that after LDVU profiling stops, new closures may be created
and even garbage collections may be performed.
We choose to ignore these closures because they are all concerned about
finalizing weak pointers (in @finalizeWeakPointersNow()@).
It can be catastrophic to invoke @LdvCensusKillAll()@ after finishing
@finalizeWeakPointersNow()@: @finalizeWeakPointersNow()@ calls
@rts_evalIO()@, which is essentially initiating a new program execution,
and no assumptions made upon LDVU profiling hold any longer. 

\section{Time of Use}

In order to yield correct LDVU profiling results, we must make sure
that @LDV_recordUse()@ be called on a closure whenever it is used;
otherwise, most of closures would be reported to be in the void phase.
@includes/StgLdvProf.h@ provides an entry macro @LDV_ENTER@ which
expands to @LDV_recordUse()@.  The compiler arranges to invoke
@LDV_ENTER@ in the entry code for every dynamic closure it generates
code for (constructors, thunks and functions).  We also have to add
@LDV_ENTER@ calls to the closures statically compiled into the RTS:
@PAP@s, @AP_UPD@s, standard thunk forms (in @StgStdThunks.hc@, and
several others in @StgMiscClosures.hc@.

\section{Computing Final Statistics}

After the final scan of the heap, we can accurately determine the total
size of closures in one of the four phases at the moment of each heap census.
The structure @LdvGenInfo@ is augmented with two additional fields 
@voidTotal@ and @dragTotal@:

\begin{code}
typedef struct {
  ...
  int voidTotal;
  int dragTotal;
  ...
} LdvGenInfo;
\end{code} 

@gi[@$i$@].voidTotal@ and @gi[@$i$@].dragTotal@ are computed
from @gi[@$i$@].voidNew@ and @gi[@$i$@].dragNew@, respectively.\footnote{Due
to a slight optimization described before, @gi[@$i$@].voidTotal@ is actually
computed as $\sum_{1 \leq j \leq i}$@gi[@$j$@].voidNew@. 
@gi[@$i$@].dragTotal@ is computed in a similar way.}
Then, the total size of closures in the lag phase @gi[@$i$@].lagTotal@ is computed
as @gi[@$i$@].notUsed@$-$@gi[@$i$@].voidTotal@ (because any unused closure
is either in the void phase or in the lag phase).
Similarly, 
the total size of closures in the use phase @gi[@$i$@].useTotal@ is computed
as @gi[@$i$@].used@$-$@gi[@$i$@].dragTotal@ (because any used closure
is either in the use phase or in the drag phase).
@endLdvProfiling()@, called from @endHeapProfiling@ in @ProfHeap.c@, computes these 
final statistics.

\section{Usage}

The runtime system option @-hL@ tells the executable program to
perform LDVU profiling and produce a @.hp@ file:

\begin{code}
$ Foo.out +RTS -hL
\end{code}

The option @-i@ can be used to 
specify a desired interval at which LDVU profiling is performed.
The default and minimum value is half a second:

\begin{code}
$ Foo.out +RTS -hL -i2.5 -RTS
\end{code}

The @.hp@ file can be supplied to the @hp2ps@ program to create a postscript
file showing the progress of LDVU profiling in a graph:

\begin{code}
$ hp2ps Foo.hs
$ gv Foo.ps
\end{code}

The horizontal axis of the graph is in the Haskell mutator time, which excludes
the runtime system time such as garbage collection time and LDVU profiling
time. 
The Haskell mutator runs a bit slower than it would without performing
LDVU profiling, but the difference is minute.
Also, the timer employed to periodically perform retainer profiling
is not perfectly accurate. Therefore, the result may slightly vary for each
execution of retainer profiling.

\textbf{To do:} Currently the LDVU profiling is not supported with @-G1@ option.

\textbf{To do:} When we perform LDVU profiling, the Haskell mutator time seems to
be affected by @-S@ or @-s@ runtime option. For instance, the following 
two options should result in nearly same profiling outputs, but
the second run (without @-Sstderr@ option) spends almost twice as
long in the Haskell mutator as the first run:
1) @+RTS -Sstderr -hL -RTS@; 2) @+RTS -hL -RTS@.
This is quite a subtle bug because this wierd phenomenon is not 
observed in retainer profiling, yet the implementation of 
@mut_user_time_during_LDV()@ is completely analogous to that of 
@mut_user_time_during_RP()@. The overall shapes of the resultant graphs 
are almost the same, though.

\section{Files}

This section gives a summary of changes made to the GHC in 
implementing LDVU profiling.
Only three files (@includes/StgLdvProf.h@, @LdvProfile.c@, and 
@LdvProfile.h@) are new, and all others exist in the GHC.

@\includes@ directory:

\begin{description}
\item[StgLdvProf.h] defines type @LdvGenInfo@, constants, and macros related
with LDVU profiling.
\item[ClosureMacros.h] changes macro @SET_PROF_HDR()@.
\item[Stg.h] includes th header file @StgLdvProf.h@.
\item[StgMacros.h] changes macros @UPD_BH_UPDATABLE()@ and @UPD_BH_SINGLE_ENTRY()@.
\end{description}

@\rts@ directory:

\begin{description}
\item[GC.c] invokes @LdvCensusForDead()@ before tidying up, sets @hasBeenAnyGC@ to 
  @rtsTrue@, and changes @copy()@ and @copyPart()@.
  Invokes @LDV_recordDead()@ and @LDV_recordDead_FILL_SLOP_DYNAMIC()@.
\item[Itimer.c] changes @handle_tick()@.
\item[LdvProfile.c] implements the LDVU profiling engine. 
\item[LdvProfile.h] is the header for @LdvProfile.c@.
\item[PrimOps.hc] changes @finalizzeWeakzh_fast()@.
\item[ProfHeap.c] changes @initHeapProfiling()@ and @endHeapProfiling()@.
\item[Profiling.c] changes @initProfilingLogFile@ and @report_ccs_profiling()@.
\item[Proftimer.c] declares @ticks_to_retainer_ldv_profiling@,
  @performRetainerLdvProfiling@, and @doContextSwitch@.
\item[Proftimer.h] is the header for @Proftimer.c@. Defines @PROFILING_MIN_PERIOD@,
  which specifies the minimum profiling period and the default profiling period.
%\item[RtsAPI.c] implements @setProfileHeader()@.
\item[RtsFlags.c]
  sets @RtsFlags.ProfFlags.doHeapProfile@,
  adds a string to @usage_text[]@ in @setupRtsFlags()@.
\item[RtsFlags.h] defines constants @HEAP_BY_LDV@ and @LDVchar@.
\item[RtsStartup.c] changes @shutDownHaskell()@.
\item[Schedule.c] changes @schedule()@.
\item[Stats.c] 
  declares @LDV_start_time@, @LDV_tot_time@, @LDVe_start_time@, 
  @LDVe_tot_time@.
  Changes @mut_user_time_during_GC()@, @mut_user_time()@,
  @stat_startExit()@,
  @stat_endExit()@, and
  @stat_exit()@.
  Defines
  @mut_user_time_during_LDV()@,
  @stat_startLDV()@, and
  @stat_endLDV()@.
\item[Stats.h] is hte header for @Stats.c@.
\item[StgMiscClosures.hc] inserts entry macros in 
  @stg_IND_entry()@, @stg_IND_PERM_entry()@, @stg_IND_OLDGEN_entry()@,
  @stg_IND_OLDGEN_PERM_entry()@, @stg_BLACKHOLE_entry()@, @stg_BLACKHOLE_BQ_entry()@,
  and @stg_CAF_BLACKHOLE_entry()@.
  Invokes @LDV_recordDead()@ in @stg_BLACKHOLE_entry@.
  Redefines @stg_DEAD_WEAK_info@.
\item[Storage.c] changes @initStorage()@, @resetNurseries()@, and @allocNursery()@.
\item[Storage.h] changes @updateWithIndirection()@ and @updateWithPermIndirection()@.
\item[Updates.hc] inserts entry macros in @stg_PAP_entry()@ and @stg_AP_UPD_entry()@.
\item[Weak.c] changes @scheduleFinalizers()@.
\end{description}

\bibliographystyle{plain}
\bibliography{reference}

\end{document}