overview.tex

\subsection*{Introduction}

    When creating a piece of software, the measurement of a set of
    information of interest regarding performance
    --- for instance: CPU time, number of
    functions evaluated, number of iterations, memory usage, accuracy, or
    others --- is common.   \emph{Benchmarking} is the process of measuring
    the performance information of one piece of software relative to similar software.
    
    This is necessary when developing programs since it
    helps uncover software deficiencies  and usually leads
    to general software improvements~\cite
    {url:mittelmann,Mittelmann:1999fb,Dolan:2006kl}.

    Furthermore, given a set of software that solve the same problem, one 
    could compare them in order to choose the best one, or verify how their own
    software can be improved. To address this, \textcite{Dolan:2002du} developed 
    a tool to visualize optimization solvers benchmarks: the 
    \emph{performance profile}.

    Formally, a performance profile allows one to evaluate and compare the
    performance
    of a set $\Sset$ of solvers  on a given test set $\Pset$, with respect
    to a chosen evaluation parameter,
    which will be referenced as \emph{cost}.
    It is presented as
    a graphic that shows the cumulative distribution function of different
    solvers performances, according to the chosen cost metric.
    Note that the cost metric must be positive.

    This  method is mostly used for nonlinear optimization solvers,
    however, it is possible to extend it to other software comparison.
    For instance, some authors have used it in the context of algorithms for
    matrix functions \cite{al-mohy:2009, al-mohy:2011, al-mohy:2012,
    higham:2005, higham:2009, higham:2011, higham:2013}.
    Notice that, in some cases, a
    specialized test can be more significant than the performance profile with
    a specific cost.  For derivative-free optimization, for instance,
    \textcite{More:2009benchmarking} define a \emph{data profile}, using the
    number of function evaluations as the metric cost, nevertheless in a 
    different way of performance profile definition.

    For each
    problem $p \in \Pset$ and solver $s \in \Sset$, let $t_{p,s}$ be the
    cost required to solve problem $p$ by solver $s$ and
    \begin{align*}
      r_{p,s} = \frac{t_{p,s}}{\min\{t_{p,s}: s \in \Sset\}}
    \end{align*}
    be the performance ratio of solver $s$ for the problem $p$ when compared
    with the best performance by any solver on this problem.
    As a convention, we set $r_{p,s}$ to a large value, say $r_{\max}$, if
    the solver $s$ does not solve the problem $p$.

    The probability of a solver $s \in \Sset$  to solve one problem within a
    factor $\tau \in \mathds{R}$ of the best performance ratio is the function
    \begin{align*}
      \rho_s(\tau) = \frac{| \{p \in \Pset: r_{p,s} \leq \tau\} |}{| \Pset |}.
    \end{align*}
    For a given $\tau$, the best solver is the one with the highest value for
    $\rho_s(\tau)$, that is, the one with the highest probability to solve the
    problem.
    The value $\rho_s(\tau)$ represents the percentage of problems solved by
    algorithm $s$ with a cost at most $\tau$ times worse than the best
    algorithm. $\rho_s(1)$ is the percentage of problems solved as fast as the
    fastest algorithm, which gives the efficiency of solver $s$.
    On the other hand
    \[\displaystyle \lim_{\tau\rightarrow r^-_{\max}} \rho_s(\tau)\]
    is the total percentage of problems solved by solver $s$, or in
    other words, the robustness of solver $s$.

\subsection*{Motivation}

    To facilitate the reproduction of data set analysis, such as 
    benchmarking of solvers analysis provided by \textcite{Dolan:2002du}'s
    performance profile,  an open source tool that handles
    the production of performance profile plots should be available.

    Performance profile has been, over the years, the most used benchmark
    comparison tool used in optimization. Nevertheless, the production of such
    analysis is sometimes a dull task, that can lead a researcher to waste a lot
    of time and effort that should have been spent in developing the solver
    itself.

    There are other
    implementations to generate  performance profiles,
    some of them being reasonable well-known, such as a MatLab
    script from
    the same group that created  performance profile~\cite{url:cops},
    and a module written by Michael Friedlander inside NLPy~\cite{url:NLPy}.

    Some, perhaps unaware of these implementations or trying to avoid
    proprietary solutions, implemented their own solutions and then made
    them
    available. Solutions such as a Python function perfprof from \textcite
    {url:perfprof}
    and a  Julia module {\tt perfprof.jl} from \textcite{url:perfprofjl}, 
    both language dependent. A thorough search would possibly reveal many
    others.  However, there are features that some users need that these software have
    not implemented.

    This paper describes a straightforward open source tool that
    allows  one to create  performance profile pictures in a fast and easy
    manner called perprof-py.
    In addition, this tool  allows LaTeX users, a group which includes almost
    all of the optimization community, to generate performance profile
    plots as LaTeX code that will be processed later  with the rest of their document 
    or standalone PDF when needed.

    With these two main goals in mind,  perprof-py was developed and 
    implemented in Python 3 with internationalization features and direct LaTeX
    integration.

\subsection*{Implementation and architecture}

    Perprof-py was implemented as a Python 3 package
    and organized to allow addition of new backends.
    Core files are
    \begin{itemize}
      \item {\tt perprof/prof.py} that defines a class {\tt Pdata} that need to
        be extend for every backend;
      \item {\tt perprof/parse.py} that has the parser for the input files; and
      \item {\tt perprof/main.py} that has the command line interface.
    \end{itemize}

    The incompatibility of perprof-py  with Python 2
    was due (i) to the fact that unicode processing with Python 2 can be a
    nightmare, and
    (ii) to the authors' desire to push Python 3 forward.

    Users have a command line interface to use out of the box,
    however one can also use the package in their own software.

    Implementation is very straightforward. In fact, the algorithm:
    \begin{enumerate}
      \item parses the options passed as arguments, creating a
        structure with all  information;
      \item parses and process  input files, using the 
         performance function definition to create  data to be plotted;
      \item uses the chosen backend to plot  data.
    \end{enumerate}

\subsection*{Input}

    For each solver to be compared in  benchmarking, one must write a file in
    the following manner:

    \begin{verbatim}
---
YAML information
---
Problem01 exit01 time01
Problem02 exit02 time02
    \end{verbatim}

    YAML\cite{url:yaml,url:pyyaml} information is a list of keywords and values used to
    set the name of the solver and some
    flags for perprof-py.
    A legacy option remains, in which the user can instead put only the
    solver name using
\begin{verbatim}
#Name SOLVERNAME
Problem01 exit01 time01
Problem02 exit02 time02
\end{verbatim}
    nevertheless some users  may like to
    add more options.

    Each line of data has at least 3 columns.
    Columns' meanings, in the default order, are:
    \begin{itemize}
      \item Problem's name;
      \item Exit flag;
      \item Cost measure -- for instance, elapsed time.
    \end{itemize}
    Default exit flag is  {\tt c} or {\tt d} on the exit flag
    column, meaning convergence or divergence, respectively.

    One of the perprof-py solver examples  uses the following YAML information
\begin{verbatim}
algname: Alpha
success: converged
free_format: True
\end{verbatim}
    which means that the name appearing on the profile will be {\tt Alpha};
    that {\tt converged} is the word that means convergence,
    and that every other exit flag word means divergence.
    These options were set from {\tt algname}, {\tt success}, and {\tt
    free\_format} options, respectively.

    A user can, optionally, add more columns to add information.
    They can verify, for instance, that the optimality conditions are satisfied
    for each problem.
    Also, using  either YAML or command line options, a user can change each
    columns' meaning.
    Note that these options are not enabled by default. The user should
    consult the help and documentation files to see how to enable them.

\subsection*{Parsing process and output}

    To use perprof-py, one needs to issue a command of the type
\begin{verbatim}
$ perprof OPTIONS BACKEND FILES
\end{verbatim}
    where
    \begin{itemize}
      \item FILES are the input files described in the previous section. At
        least two files input are required;
      \item BACKEND is one of the options \verb+--tikz+, \verb+--mp+,
        \verb+--bokeh+ or
        \verb+--raw+, which represents whether the user wants to use
        TikZ/PGFPLOTS, matplotlib, Bokeh, or simply printing the performance
        ratios, respectively;
      \item OPTIONS are varied arguments that can be passed to perprof-py to
        customize the graphics or modify the performance functions. Some
        noteworthy options are
        \begin{itemize}
          \item \verb+--semilog+: the natural logarithmic scale is used on the
          abscissa axis;
          \item \verb+--success STR+: \verb+STR+ is a comma separated string
            of keys that was considered  \emph{success} by the solver;
          \item \verb+--black-and-white+: perprof-py creates the plots using
            only line styles and it colors them in black;
          \item \verb+--subset FILE+: perprof-py considers only the subset problems listed in \verb+FILE+, while creating the performance functions.
        \end{itemize}
    \end{itemize}
    In order to demonstrate such OPTIONS, Figures
    \ref{fig:example1}-\ref{fig:example4} show some examples of  performance
    profile graphics.
    Figure \ref{fig:example1} shows the performance profile graphic with default
    options. Note that the lines are clumped due to the maximum time allowed
    in the solver.
    \begin{figure}[!ht]
      \centering
      \includegraphics[width=0.4\textwidth]{plots/abc.pdf}
      \caption{Example of performance profile with default options.}
      \label{fig:example1}
    \end{figure}
    Figure \ref{fig:example2} shows the performance profile using  semilog
    option, which plots the graphic using a log scale on the abscissa.
    \begin{figure}[!ht]
      \centering
      \includegraphics[width=0.4\textwidth]{plots/abc-semilog.pdf}
      \caption{Example of performance profile with semilog option.}
      \label{fig:example2}
    \end{figure}
    Figure \ref{fig:example3} shows the performance profile using also the black
    and white option, which gives a printer-friendly graphic.
    \begin{figure}[!ht]
      \centering
      \includegraphics[width=0.4\textwidth]{plots/abc-semilog-bw.pdf}
      \caption{Example of performance profile with semilog and black and white
        options.}
      \label{fig:example3}
    \end{figure}
    Figure \ref{fig:example4} shows the performance profile using  subset
    and semilog options. In this case, we
    selected around 120
    problems, put their names in a file, and passed the file with the option.
    This limits the comparison to only those files.
    \begin{figure}[!ht]
      \centering
      \includegraphics[width=0.4\textwidth]{plots/abc-semilog-hs.pdf}
      \caption{Example of performance profile with semilog and subset options.}
      \label{fig:example4}
    \end{figure}

\subsection*{Quality control}

    Perprof-py code is tested using unit tests that verify if incorrect input
    information is captured. These tests are run automatically on Travis CI
    \cite{url:travis}, for Python 3.3 and 3.4.
    In addition, a script is run to generate several performance profile
    graphics. This script is also run on Travis CI, though the evaluation
    that perprof-py outputs the desired  graphics can only be done locally.

    This script uses artificial solver information accessible using \verb+--demo+
    as argument in the perprof-py call.
    For instance, to test that the TikZ installation is successful, one can run
\begin{verbatim}
perprof-py --demo -o tmp --tikz
\end{verbatim}
    If everything is correct, this will generate a file \verb+tmp.pdf+ with an
    example performance profile made using LaTeX and compiled to a standalone
    PDF.

    One can run the testing script
    by entering the folder
    \verb+perprof/examples+ relative to the package folder, and running
\begin{verbatim}
./make-examples.sh
\end{verbatim}
    Folder \verb+plots+ will contain the outputs in formats PNG and PDF.