+++ /dev/null
-\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}
projects / ghc-hetmet.git / blobdiff