\title{A2: Measurement}
\input{preamble.tex}
In this assignment some std algorithms are executed on vectors and
their performance measured.

A reuseable measurement mechanism based on RIAA, \texttt{class
Measure}, was made and a simple templated function, \texttt{measure}, was made
for executing multiple times and printing the results.
The RIAA class did not turn out as elegant as I originally
anticipated, but I decided to keep it anyway.
These are intended for re-use in the upcoming assigments.

As with assignment 1, I started out using modules instead of includes,
but I got some really wierd behaviour
from \texttt{std::this\_thread::sleep\_for()} and even a crash and
ended up having to go back to using \texttt{\#include} which solved
the issues.

I found the random mildly confusing although I can recognize how it is
very modular and customizable for a variety of purposes.

The assignment instructions are kept in the code as comments for easy
navigation.
Each sub-task is put in its own scope to not pollute scope and at the
same time give the reader some notion of where the blocks seperate.
Functions could also have been used, but I decided this was easier to
read.

I particularly enjoyed the fact that I could generate the random
characters directly as characters instead of having to generate
numbers and then convert them to characters afterwards.

\bigskip

The program is being compiled four times, with optimization levels set to 0
through 3.
The following pages shows the console outputs of the four being executed:

\noindent\begin{minipage}{0.5\textwidth}
Running measurement -O0:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
 100.11 ms passed
 100.293 ms passed
 100.145 ms passed
std::find 7 in the middle:
 23.2664 ms passed
 23.6302 ms passed
 23.3487 ms passed
std::find 7 not there:
 46.4612 ms passed
 46.3373 ms passed
 46.3307 ms passed
std::find_if x < 7 in the middle:
 30.6713 ms passed
 30.6191 ms passed
 30.4679 ms passed
std::find_if x < 7 not there:
 60.8465 ms passed
 60.7847 ms passed
 60.9189 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
 87.4575 ms passed
 87.0677 ms passed
 87.0778 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
 43.5735 ms passed
 43.6536 ms passed
 43.5371 ms passed
\end{verbatim}
\end{minipage}\hspace{1em}
\begin{minipage}{0.5\textwidth}
Running measurement -O1:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
 100.072 ms passed
 100.205 ms passed
 100.272 ms passed
std::find 7 in the middle:
 2.4489 ms passed
 2.27078 ms passed
 2.09195 ms passed
std::find 7 not there:
 3.48041 ms passed
 3.0423 ms passed
 3.26511 ms passed
std::find_if x < 7 in the middle:
 1.75712 ms passed
 1.67603 ms passed
 1.54085 ms passed
std::find_if x < 7 not there:
 3.49353 ms passed
 3.13966 ms passed
 3.02858 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
 19.4014 ms passed
 19.1675 ms passed
 19.199 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
 9.98892 ms passed
 9.75758 ms passed
 10.0103 ms passed
\end{verbatim}
\end{minipage}

\noindent\begin{minipage}{0.5\textwidth}
Running measurement -O2:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
 100.285 ms passed
 100.284 ms passed
 100.109 ms passed
std::find 7 in the middle:
 2.41485 ms passed
 2.24354 ms passed
 2.05605 ms passed
std::find 7 not there:
 3.3622 ms passed
 3.04281 ms passed
 3.19882 ms passed
std::find_if x < 7 in the middle:
 1.82075 ms passed
 1.64321 ms passed
 1.56913 ms passed
std::find_if x < 7 not there:
 3.4318 ms passed
 3.0527 ms passed
 3.00441 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
 19.4918 ms passed
 19.1717 ms passed
 19.1356 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
 9.77586 ms passed
 9.72502 ms passed
 9.92281 ms passed
\end{verbatim}
\end{minipage}\hspace{1em}
\begin{minipage}{0.5\textwidth}
Running measurement -O3:
\scriptsize\begin{verbatim}
Sanity check (sleep 100ms):
 100.289 ms passed
 100.131 ms passed
 100.278 ms passed
std::find 7 in the middle:
 2.88775 ms passed
 2.72746 ms passed
 2.34705 ms passed
std::find 7 not there:
 3.45066 ms passed
 3.20888 ms passed
 2.97772 ms passed
std::find_if x < 7 in the middle:
 1.67701 ms passed
 1.55496 ms passed
 1.5005 ms passed
std::find_if x < 7 not there:
 3.11582 ms passed
 3.02069 ms passed
 3.05484 ms passed
Find XXXXXXXXXXXXXXXXXXXX (not there):
 19.4556 ms passed
 19.0535 ms passed
 19.0312 ms passed
Find XXXXXXXXXXXXXXXXXXXX (in the middle):
 10.1083 ms passed
 9.98972 ms passed
 9.90104 ms passed
\end{verbatim}
\end{minipage}

\bigskip

Observing the one without optimization; The execution time of the
two \texttt{std::find} operations correllate nicely with the fact that
they are linear in execution time.
The same goes for the \texttt{std::find\_if} ones, and a slight
decrease in performance compared to the \texttt{std::find} one can be
attributed to the fact that the comparison is more involved than a
simple \texttt{==} (it is calling the lambda on each element.

On the optimized versions the lambda is probably inlined, so
difference between \texttt{std::find} and \texttt{std::find\_if} can
be expected to become smaller. This is also what can be observed.
It is interesting to see the  \texttt{std::find} actually becoming
slower than \texttt{std::find\_if} when optimizations are enabled -
that leaves food for thought...

Looking at the string searches, these are, as expected, an order of
magnitude slower than the integer ones, since more data must be
traversed (20 bytes instead of 4 bytes for the integers). And again,
being liniear, finding the string in the middle about halves the
execution time as expected.

\bigskip

I was expecting the execution time to gradually decrease as the
amount of optimization increased, but this did not seem to be the
case.

\end{document}