\section{Benchmark Code}
\label{sec:benchmarkcode}

This section contains the \nesl\ source code for the line-fit, selection
and sparse matrix-vector multiplication routines, and also describes
the test data used for the benchmarks.

%%%%%%%%%%%%%%%%%%

\subsection{Line-fit}

\begin{verbatim}
   function linefit(x, y) =
   let 
     n    = float(#x);
     xa   = sum(x)/n;
     ya   = sum(y)/n;
     Stt  = sum({(x - xa)^2: x});
     b    = sum({(x - xa) * y: x; y}) / Stt;
     a    = ya - xa*b;
     chi2 = sum({(y - a - b * x)^2: x; y});
     siga = sqrt((1.0 / n + xa^2 / Stt)* chi2 / n);
     sigb = sqrt((1.0 / Stt) * chi2 / n)
   in 
     (a, b, siga, sigb);
\end{verbatim}

\noindent
For the line-fit benchmarks, $x$ and $y$ were both copies of the
double-precision index vector $[0.0, 1.0, 2.0, \ldots]$.

%%%%%%%%%%%%%%%%%%

\subsection{Selection}

\begin{verbatim}
   function select_kth(s, k) =
   let pivot = s[#s/2]; 
       les = {e in s | e < pivot}
   in 
     if (k < #les) then
       select_kth(les, k)
     else 
       let grt = {e in s | e > pivot}
       in if (k >= #s - #grt) then
            select_kth(grt, k - (#s - #grt))
          else pivot;
\end{verbatim}

\noindent
For the selection benchmarks, $s$ was the integer index vector $[0, 1, 2,
\ldots]$, and $k$ was one third of the length of $s$.

%%%%%%%%%%%%%%%%%%

\subsection{Sparse matrix-vector multiplication}

\begin{verbatim}
   function nest(p, mlen) = 
     let vector(seg,vals) = p;
         (seg1,seg2) = mlen
     in vector(seg1,vector(seg2,vals));
   
   function MxV(Mval, Midx, Mlen, Vect) =
   let v = Vect -> Midx;
       p = {a * b: a in Mval; b in v}
   in 
     {sum(row) : row in nest(p, Mlen)};
\end{verbatim}

\noindent
For the sparse matrix-vector multiplication benchmarks, every row in the
matrix had a length of 5 and the matrix values were random double-precision
data.
