A2: Add measurement exercise..

4 files changed, 235 insertions, 38 deletions

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);