rts_reorder.tex

\section{Independent conjunction reordering}
\label{sec:rts_reorder}

\plan{Acknowledge results of previous section}
We have shown that right recursion suffers from a context limit problem.
Right recursive programs also get smaller speedups when compared with left
recursive programs.
The problem with right recursion is the large number of contexts needed.
This is memory intensive, and CPU intensive once we consider that
the Boehm GC must scan these context's stacks to check for pointers.
This can happen whenever the second or later
conjunct of a parallel conjunction
takes longer to execute than the first conjunct;
the first conjunct becomes blocked on the later conjunct(s).

\plan{Describe the intuition for the transformation.}
On the other hand left recursion works well:
using work stealing we are able to get very good speedups (3.92 for
mandelbrot when using four Mercury engines).
When the conjunction is independent,
Mercury's purity allows us to reorder the conjuncts of the computation and
transform right recursion into left recursion.
For example it would transform the procedure in
Figure~\ref{fig:map_right_recursive} into the one in
Figure~\ref{fig:map_left_recursive} (page~\pageref{fig:map_right_recursive}).

\begin{algorithm}
\begin{algorithmic}[1]
\Procedure{reorder}{$SCC$, $Conjs$}
    \If{$Conjs = $ \nil}
        \State \Return \nil
    \Else
        \State \cons{Conj}{ConjsTail} $\gets Conjs$
        \State $ConjsTail \gets$ reorder($SCC$, $ConjsTail$)
        \If{$Conj$ contains a call to $SCC$}
            \State \Return \cons{Conj}{ConjsTail}
        \Else
            \State \Return try\_push\_conj\_later($Conj$, $ConjsTail$)
        \EndIf
    \EndIf
\EndProcedure
\Procedure{try\_push\_conj\_later}{$Goal$, $Conjs$}
    \If{$Conjs =$ \nil}
        \State \Return \single{Goal}
    \Else
        \State \cons{Pivot}{Rest} $\gets Conjs$
        \If{can\_swap($Goal$, $Pivot$)}
            \State $Pushed \gets$ try\_push\_conj\_later($Goal$, $Rest$)
            \State \Return \cons{Pivot}{Pushed}
        \Else
            \State \Return \cons{Goal}{Conjs}
        \EndIf
    \EndIf
\EndProcedure
\end{algorithmic}
\caption{Reorder independent conjunctions}
\label{alg:reorder_conjunction}
\end{algorithm}

\plan{Describe the transformation}
We only reorder completely independent conjunctions.
It may be possible to find independent sections of dependent conjunctions
and reorder them,
but we have not needed to.
\reorder is invoked on parallel conjunctions without shared variables;
its code is shown in Algorithm~\ref{alg:reorder_conjunction}.
Its arguments are a reference to the current strongly connected component (SCC)
and a list of the parallel conjunction's conjuncts.
\reorder iterates over these goals in reverse order by means of the
recursive call on line 6.
For each goal it tests if that goal makes a call to the current SCC.
If so, it leaves the goal where it is,
if not \reorder will attempt to push the goal towards the end of the
list using \trypushconjlater.
\trypushconjlater takes the current goal (\var{Goal}) and the list
representing the rest of the conjunction (\var{Conjs}).
It iterates down this list attempting to swap \var{Goal} with the goal at
the front of the list (\var{Pivot}).
Not all swaps are legal,
for example a goal cannot be swapped with an impure goal,
therefore \trypushconjlater may not always push a goal all the way to the
end of the list.

\plan{Discuss reasoning for not showing results.}
We have benchmarked and tested this to confirm that independent right recursion
now performs the same as independent left recursion.
We expected these programs to perform identically
because independent right recursion is transformed into independent
left recursion.