diff options
| -rw-r--r-- | Makefile | 3 | ||||
| -rw-r--r-- | a2/.gitignore | 4 | ||||
| -rw-r--r-- | a2/Makefile | 28 | ||||
| -rw-r--r-- | a2/exercise.tex | 200 | ||||
| -rw-r--r-- | a2/measurement.cc | 41 |
5 files changed, 237 insertions, 39 deletions
@@ -9,7 +9,8 @@ A1: rm -f ${PRE}$@.aux ${PRE}$@.log A2: - zip ${PRE}$@.zip a1/Makefile + zip ${PRE}$@.zip a2/Makefile + zip ${PRE}$@.zip a2/measurement.cc xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a2/exercise.tex rm -f ${PRE}$@.aux ${PRE}$@.log diff --git a/a2/.gitignore b/a2/.gitignore new file mode 100644 index 0000000..a64fb07 --- /dev/null +++ b/a2/.gitignore @@ -0,0 +1,4 @@ +measurement-O0 +measurement-O1 +measurement-O2 +measurement-O3 diff --git a/a2/Makefile b/a2/Makefile index 74f52b2..ae0cbeb 100644 --- a/a2/Makefile +++ b/a2/Makefile @@ -1,15 +1,13 @@ -all: measurement - -gcm.cache: Makefile - rm -Rf gcm.cache -# g++ -std=c++20 -fmodules-ts -x c++-system-header chrono -# g++ -std=c++20 -fmodules-ts -x c++-system-header vector -# g++ -std=c++20 -fmodules-ts -x c++-system-header iostream -# g++ -std=c++20 -fmodules-ts -x c++-system-header algorithm -# g++ -std=c++20 -fmodules-ts -x c++-system-header string -# g++ -std=c++20 -fmodules-ts -x c++-system-header thread - -measurement: measurement.cc Makefile -#gcm.cache -# g++ -Wall -Werror -Wextra -Wconversion -std=c++20 -fmodules-ts measurement.cc -o measurement - g++ -O2 -Wall -Werror -Wextra -Wconversion -std=c++20 measurement.cc -o measurement +all: measurement-O0 measurement-O1 measurement-O2 measurement-O3 + +measurement-O0: measurement.cc Makefile + g++ -O0 -Wall -Werror -Wextra -Wconversion -std=c++20 measurement.cc -o measurement-O0 + +measurement-O1: measurement.cc Makefile + g++ -O1 -Wall -Werror -Wextra -Wconversion -std=c++20 measurement.cc -o measurement-O1 + +measurement-O2: measurement.cc Makefile + g++ -O2 -Wall -Werror -Wextra -Wconversion -std=c++20 measurement.cc -o measurement-O2 + +measurement-O3: measurement.cc Makefile + g++ -O3 -Wall -Werror -Wextra -Wconversion -std=c++20 measurement.cc -o measurement-O3 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} diff --git a/a2/measurement.cc b/a2/measurement.cc index cf90d52..c624bfa 100644 --- a/a2/measurement.cc +++ b/a2/measurement.cc @@ -1,11 +1,3 @@ -#if 0 -import <chrono>; -import <vector>; -import <iostream>; -import <algorithm>; -import <string>; -import <thread>; -#else #include <chrono> #include <vector> #include <iostream> @@ -13,7 +5,6 @@ import <thread>; #include <string> #include <thread> #include <random> -#endif class Measure { @@ -51,7 +42,7 @@ int main() using namespace std::chrono_literals; // Sanity check measurement mechanism - measure("Sanity check (sleep 100ms):", + measure("Sanity check (sleep 100ms)", []() { std::this_thread::sleep_for(100ms); @@ -63,22 +54,28 @@ int main() // * Find the 7 in the middle of a vector<int> where all other elements are // not 7. { - std::vector<int> v(1'000'000, 42); // one million items with the int 42 + std::vector<int> v(10'000'000, 42); // one million items with the int 42 v[v.size() / 2] = 7; // set middle item to 7 measure("std::find 7 in the middle", [&v]() { - std::find(v.begin(), v.end(), 7); + if(std::find(v.begin(), v.end(), 7) == std::end(v)) + { + std::cout << "That was unexpected!\n"; + } }); } // * Try to find a 7 in a vector<int> where no element is 7 { - std::vector<int> v(1'000'000, 42); // one million items with the int 42 + std::vector<int> v(10'000'000, 42); // one million items with the int 42 measure("std::find 7 not there", [&v]() { - std::find(v.begin(), v.end(), 7); + if(std::find(v.begin(), v.end(), 7) != std::end(v)) + { + std::cout << "That was unexpected!\n"; + } }); } @@ -88,22 +85,28 @@ int main() // * Find the x < 7 in the middle of a vector<int> where all other elements // are >= 7. { - std::vector<int> v(1'000'000, 42); // one million items with the int 42 + std::vector<int> v(10'000'000, 42); // one million items with the int 42 v[v.size() / 2] = 5; // set middle item to 5 measure("std::find_if x < 7 in the middle", [&v]() { - std::find_if(v.begin(), v.end(), [](int x){ return x < 7;}); + if(std::find_if(v.begin(), v.end(), [](int x){ return x < 7;}) == std::end(v)) + { + std::cout << "That was unexpected!\n"; + } }); } // * Try to find an x < 7 in a vector<int> where all elements are >= 7. { - std::vector<int> v(1'000'000, 42); // one million items with the int 42 + std::vector<int> v(10'000'000, 42); // one million items with the int 42 measure("std::find_if x < 7 not there", [&v]() { - std::find_if(v.begin(), v.end(), [](int x){ return x < 7;}); + if(std::find_if(v.begin(), v.end(), [](int x){ return x < 7;}) != std::end(v)) + { + std::cout << "That was unexpected!\n"; + } }); } @@ -116,7 +119,7 @@ int main() std::uniform_int_distribution<char> distrib('A', 'Z'); std::vector<std::string> vs; - vs.resize(1'000'000); + vs.resize(10'000'000); for(auto &str: vs) { str.reserve(20); |