diff options
Diffstat (limited to 'a2/exercise.tex')
| -rw-r--r-- | a2/exercise.tex | 200 |
1 files changed, 196 insertions, 4 deletions
diff --git a/a2/exercise.tex b/a2/exercise.tex index 4615e24..27e2f0c 100644 --- a/a2/exercise.tex +++ b/a2/exercise.tex @@ -1,10 +1,202 @@ \title{A2: Measurement} \input{preamble.tex} +In this assignment some std algorithms are executed on vectors and +their performance measured. -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} instead of modules, which -solved the issues. +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} |