A3: Concurrency exercise..

9 files changed, 848 insertions, 41 deletions

diff --git a/Makefile b/Makefile
index 17776c9..a975039 100644
--- a/Makefile
+++ b/Makefile
@@ -17,6 +17,8 @@ A2:
 A3:
 	zip ${PRE}$@.zip a3/Makefile
 	zip ${PRE}$@.zip a3/concurrency.cc
+	zip ${PRE}$@.zip a3/console.log
+	xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a3/exercise.tex
 	xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a3/exercise.tex
 	rm -f ${PRE}$@.aux ${PRE}$@.log
 
diff --git a/a3/concurrency.cc b/a3/concurrency.cc
index da7b51e..9838212 100644
--- a/a3/concurrency.cc
+++ b/a3/concurrency.cc
@@ -41,6 +41,47 @@ void measure(const std::string& text, Callable c)
 	}
 }
 
+template<typename T>
+std::vector<T> get_random_vector(std::size_t size,
+                                 T min = std::numeric_limits<T>::min(),
+                                 T max = std::numeric_limits<T>::max())
+{
+	std::default_random_engine generator;
+	// Randomly generate T-values from the range [min; max]
+	std::uniform_int_distribution<T> distrib(min, max);
+
+	std::vector<T> v;
+	v.resize(size);
+	for(auto& item : v)
+	{
+		item = distrib(generator);
+	}
+
+	return v;
+}
+
+std::vector<std::string> get_random_strings(std::size_t size,
+                                            std::size_t length,
+                                            char min, char max)
+{
+	std::default_random_engine generator;
+	// Randomly generate T-values from the range [min; max]
+	std::uniform_int_distribution<char> distrib(min, max);
+
+	std::vector<std::string> v;
+	v.resize(size);
+	for(auto& str : v)
+	{
+		str.reserve(length);
+		for(auto i = 0u; i < str.capacity(); ++i)
+		{
+			str += distrib(generator);
+		}
+	}
+
+	return v;
+}
+
 template<typename C, typename T>
 //	requires std::forward_iterator<Iter>
 	requires std:: ranges::input_range<C>
@@ -116,47 +157,6 @@ std::vector<const T*> find_all(const C& v, const T& key, std::size_t n)
 	return res;
 }
 
-template<typename T>
-std::vector<T> get_random_vector(std::size_t size,
-                                 T min = std::numeric_limits<T>::min(),
-                                 T max = std::numeric_limits<T>::max())
-{
-	std::default_random_engine generator;
-	// Randomly generate T-values from the range [min; max]
-	std::uniform_int_distribution<T> distrib(min, max);
-
-	std::vector<T> v;
-	v.resize(size);
-	for(auto& item : v)
-	{
-		item = distrib(generator);
-	}
-
-	return v;
-}
-
-std::vector<std::string> get_random_strings(std::size_t size,
-                                            std::size_t length,
-                                            char min, char max)
-{
-	std::default_random_engine generator;
-	// Randomly generate T-values from the range [min; max]
-	std::uniform_int_distribution<char> distrib(min, max);
-
-	std::vector<std::string> v;
-	v.resize(size);
-	for(auto& str : v)
-	{
-		str.reserve(length);
-		for(auto i = 0u; i < str.capacity(); ++i)
-		{
-			str += distrib(generator);
-		}
-	}
-
-	return v;
-}
-
 int main()
 {
 	{
diff --git a/a3/console.log b/a3/console.log
new file mode 100644
index 0000000..cc6ca55
--- /dev/null
+++ b/a3/console.log
@@ -0,0 +1,136 @@
+Single threaded search for int:
+ 99.0755 ms passed
+ 99.502 ms passed
+ 98.4946 ms passed
+Multi threaded (1) search for int:
+ 100.361 ms passed
+ 101.444 ms passed
+ 99.3357 ms passed
+Multi threaded (2) search for int:
+ 51.6977 ms passed
+ 51.4575 ms passed
+ 51.7779 ms passed
+Multi threaded (3) search for int:
+ 34.7178 ms passed
+ 34.4771 ms passed
+ 34.3003 ms passed
+Multi threaded (4) search for int:
+ 25.9185 ms passed
+ 25.8058 ms passed
+ 25.7757 ms passed
+Multi threaded (5) search for int:
+ 32.3892 ms passed
+ 31.1645 ms passed
+ 32.3938 ms passed
+Multi threaded (6) search for int:
+ 26.9827 ms passed
+ 27.004 ms passed
+ 26.9901 ms passed
+Multi threaded (7) search for int:
+ 23.3415 ms passed
+ 23.2642 ms passed
+ 23.6421 ms passed
+Multi threaded (8) search for int:
+ 21.0321 ms passed
+ 26.3786 ms passed
+ 20.651 ms passed
+Multi threaded (9) search for int:
+ 26.4053 ms passed
+ 26.0672 ms passed
+ 25.8895 ms passed
+Multi threaded (10) search for int:
+ 25.8863 ms passed
+ 29.3205 ms passed
+ 24.2901 ms passed
+Multi threaded (11) search for int:
+ 28.1128 ms passed
+ 27.3005 ms passed
+ 24.1081 ms passed
+Multi threaded (12) search for int:
+ 26.8832 ms passed
+ 26.7973 ms passed
+ 25.3346 ms passed
+Multi threaded (13) search for int:
+ 24.995 ms passed
+ 23.6564 ms passed
+ 24.9819 ms passed
+Multi threaded (14) search for int:
+ 23.1928 ms passed
+ 23.1057 ms passed
+ 23.4752 ms passed
+Multi threaded (15) search for int:
+ 23.096 ms passed
+ 24.1333 ms passed
+ 22.1936 ms passed
+Multi threaded (16) search for int:
+ 24.4629 ms passed
+ 20.9868 ms passed
+ 22.8824 ms passed
+Single threaded search for string:
+ 266.31 ms passed
+ 264.754 ms passed
+ 265.04 ms passed
+Multi threaded (1) search for string:
+ 262.007 ms passed
+ 261.643 ms passed
+ 260.548 ms passed
+Multi threaded (2) search for string:
+ 136.218 ms passed
+ 136.152 ms passed
+ 136.74 ms passed
+Multi threaded (3) search for string:
+ 91.529 ms passed
+ 91.1464 ms passed
+ 91.6109 ms passed
+Multi threaded (4) search for string:
+ 77.8617 ms passed
+ 80.5186 ms passed
+ 68.423 ms passed
+Multi threaded (5) search for string:
+ 76.2207 ms passed
+ 70.712 ms passed
+ 76.2605 ms passed
+Multi threaded (6) search for string:
+ 63.9025 ms passed
+ 63.9237 ms passed
+ 63.8663 ms passed
+Multi threaded (7) search for string:
+ 55.3068 ms passed
+ 55.0763 ms passed
+ 55.4004 ms passed
+Multi threaded (8) search for string:
+ 51.9505 ms passed
+ 50.4089 ms passed
+ 51.307 ms passed
+Multi threaded (9) search for string:
+ 59.1842 ms passed
+ 60.9649 ms passed
+ 61.4107 ms passed
+Multi threaded (10) search for string:
+ 58.4679 ms passed
+ 58.8267 ms passed
+ 57.1795 ms passed
+Multi threaded (11) search for string:
+ 60.2347 ms passed
+ 55.0205 ms passed
+ 61.8008 ms passed
+Multi threaded (12) search for string:
+ 59.427 ms passed
+ 54.7694 ms passed
+ 57.2314 ms passed
+Multi threaded (13) search for string:
+ 57.0578 ms passed
+ 56.0438 ms passed
+ 52.5656 ms passed
+Multi threaded (14) search for string:
+ 54.9454 ms passed
+ 53.1546 ms passed
+ 56.7422 ms passed
+Multi threaded (15) search for string:
+ 54.7158 ms passed
+ 55.0651 ms passed
+ 56.6704 ms passed
+Multi threaded (16) search for string:
+ 50.825 ms passed
+ 55.0096 ms passed
+ 53.4777 ms passed
diff --git a/a3/exercise.tex b/a3/exercise.tex
new file mode 100644
index 0000000..92e5cc4
--- /dev/null
+++ b/a3/exercise.tex
@@ -0,0 +1,110 @@
+\title{A3: Concurrency}
+\input{preamble.tex}
+In this assignment experiments with doing multithreaded searches in
+containers is performed measured and evaluated.
+
+A few attempts at using concepts for some generalized utility
+functions were made and any comments on the (success or lack thereof)
+on these is highly welcome.
+
+The utility functions are the following:
+\begin{itemize}
+\item The \texttt{measure} function and \texttt{Measure} class from
+  previous assignment, doing time measurement and printing the result.
+\item \texttt{get\_random\_vector} which is a templated function that
+  generates and returns a \texttt{std::vector} of a given size with
+  random values in a specified range.
+\item \texttt{get\_random\_strings} which is a function that generates
+  a \texttt{std::vector} og \texttt{std::string}s of a specified
+  length (all the same length) and with random characters picked from
+  a specified range.
+\end{itemize}
+
+The two generator function are likely far more generalized than
+necessary for this exercise, but the idea is to be able to re-use them
+in future exercises, facilitate good readability of the code in the
+\texttt{main} function and play around a bit with concepts.
+
+\bigskip
+
+The first task is to implement a \texttt{find\_all} function that
+returns a \texttt{std::vector<T*>} of found keys in the supplied input
+container.
+As the wording later in the assignment are ``How large must the
+\textbf{array} be,...'', I decided to make the function work on any
+container type by using the range concept instead of hard-coding it to
+\texttt{std::vector}. Any comments on how this has been done are more
+than welcome.
+At the top of the \texttt{main} function there are two examples of
+other container types I tried using with the functions (commented
+out); \texttt{std::array} and c-style array.
+
+\bigskip
+
+The next task was to write a 10-way parallel \texttt{find\_all} with
+the same functionality as the first one but executing 10 threads
+working on a 10th of the input container.
+I generalized this to \textit{n} threads in my first implementation (I
+hadn't seen that this was a requirement further down in the
+assignment).
+
+The threads are running through \texttt{std::async(std::launch::async, ...)}
+and each thread is initially blocking on a
+\texttt{std::condition\_variable} to make it possible to start
+measureing the execution time only after spawning all the threads.
+Each threads then simply executes the initial non-threaded
+implementation of \texttt{find\_all} with their respective sub-ranges
+and returns their result in each its own \texttt{std::vector<T*>}
+through a \texttt{std::future}.
+Finally all sub-range results are accumulated in on
+\texttt{std::vector<T*>} and returned to the \texttt{main} function.
+
+\bigskip
+
+Vectors of 10 million elements of both \texttt{int}s and
+\texttt{std::string}s are used for the tests and each of the two are
+tested in single-threaded \texttt{find\_all}, and multithreaded
+\texttt{find\_all} with 1 through 16 threads.
+
+Each run is timed and printed to the console and since the output is
+rather large is is attached in the \texttt{console.log} file alongside
+this report.
+
+\bigskip
+
+The machine used for the tests is an Intel i7 with 4 cores, each hyper
+threaded, so 8 ``virtual'' cores, each sharing parts of the cache with
+one of the others.
+
+\bigskip
+
+Looking at the results for \texttt{int}; non-threaded search took
+about 100ms and (not surprising really) so did the 1-threaded search. From
+there the search performed better and better flattening out.
+
+\begin{figure}
+  \caption{\label{ints} Showing execution times vs number of threads
+    searching for \texttt{int}s.}
+  \includegraphics[scale=0.55]{a3/int.pdf}
+\end{figure}
+
+\begin{figure}
+  \caption{\label{strings} Showing execution times vs number of threads
+    searching for \texttt{std::string}s.}
+  \includegraphics[scale=0.55]{a3/string.pdf}
+\end{figure}
+
+As seen in figure \ref{ints} the performance increase stagnates
+already at around 4 threads, suggesting that the memory pipeline/cache
+is a bottleneck that makes the threads do a lot of waiting for data
+rather than execute instructions.
+
+\bigskip
+
+Similar results are seen on the \texttt{std::string}
+searches. Although there seem to be more calculation going on so the
+memory/cache bottleneck is less dominating. This can be seen in figure
+\ref{strings} the graph seem to flatten out at bit at around 4 threads
+but keeps performing better until all 8 hyperthreads are active.
+
+\end{document}
diff --git a/a3/int.eps b/a3/int.eps
new file mode 100644
index 0000000..493e3a9
--- /dev/null
+++ b/a3/int.eps
@@ -0,0 +1,279 @@
+%!PS-Adobe-3.0 EPSF-3.0
+%%Title: gl2ps_renderer figure
+%%Creator: GL2PS 1.4.2, (C) 1999-2020 C. Geuzaine
+%%For: Octave
+%%CreationDate: Thu Jul 27 17:26:15 2023
+%%LanguageLevel: 3
+%%DocumentData: Clean7Bit
+%%Pages: 1
+%%BoundingBox: 0 0 576 432
+%%EndComments
+%%BeginProlog
+/gl2psdict 64 dict def gl2psdict begin
+/tryPS3shading false def % set to false to force subdivision
+/rThreshold 0.064 def % red component subdivision threshold
+/gThreshold 0.034 def % green component subdivision threshold
+/bThreshold 0.1 def % blue component subdivision threshold
+/BD { bind def } bind def
+/C  { setrgbcolor } BD
+/G  { 0.082 mul exch 0.6094 mul add exch 0.3086 mul add neg 1.0 add setgray } BD
+/W  { setlinewidth } BD
+/LC  { setlinecap } BD
+/LJ  { setlinejoin } BD
+/FC { findfont exch /SH exch def SH scalefont setfont } BD
+/SW { dup stringwidth pop } BD
+/S  { FC moveto show } BD
+/SBC{ FC moveto SW -2 div 0 rmoveto show } BD
+/SBR{ FC moveto SW neg 0 rmoveto show } BD
+/SCL{ FC moveto 0 SH -2 div rmoveto show } BD
+/SCC{ FC moveto SW -2 div SH -2 div rmoveto show } BD
+/SCR{ FC moveto SW neg SH -2 div rmoveto show } BD
+/STL{ FC moveto 0 SH neg rmoveto show } BD
+/STC{ FC moveto SW -2 div SH neg rmoveto show } BD
+/STR{ FC moveto SW neg SH neg rmoveto show } BD
+/FCT { FC translate 0 0 } BD
+/SR  { gsave FCT moveto rotate show grestore } BD
+/SRX  { gsave FCT moveto rotate xshow grestore } BD
+/SBCR{ gsave FCT moveto rotate SW -2 div 0 rmoveto show grestore } BD
+/SBRR{ gsave FCT moveto rotate SW neg 0 rmoveto show grestore } BD
+/SCLR{ gsave FCT moveto rotate 0 SH -2 div rmoveto show grestore} BD
+/SCCR{ gsave FCT moveto rotate SW -2 div SH -2 div rmoveto show grestore} BD
+/SCRR{ gsave FCT moveto rotate SW neg SH -2 div rmoveto show grestore} BD
+/STLR{ gsave FCT moveto rotate 0 SH neg rmoveto show grestore } BD
+/STCR{ gsave FCT moveto rotate SW -2 div SH neg rmoveto show grestore } BD
+/STRR{ gsave FCT moveto rotate SW neg SH neg rmoveto show grestore } BD
+/P  { newpath 0.0 360.0 arc closepath fill } BD
+/LS { newpath moveto } BD
+/L  { lineto } BD
+/LE { lineto stroke } BD
+/T  { newpath moveto lineto lineto closepath fill } BD
+/STshfill {
+      /b1 exch def /g1 exch def /r1 exch def /y1 exch def /x1 exch def
+      /b2 exch def /g2 exch def /r2 exch def /y2 exch def /x2 exch def
+      /b3 exch def /g3 exch def /r3 exch def /y3 exch def /x3 exch def
+      gsave << /ShadingType 4 /ColorSpace [/DeviceRGB]
+      /DataSource [ 0 x1 y1 r1 g1 b1 0 x2 y2 r2 g2 b2 0 x3 y3 r3 g3 b3 ] >>
+      shfill grestore } BD
+/Tm { 3 -1 roll 8 -1 roll 13 -1 roll add add 3 div
+      3 -1 roll 7 -1 roll 11 -1 roll add add 3 div
+      3 -1 roll 6 -1 roll 9 -1 roll add add 3 div C T } BD
+/STsplit {
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      5 copy 5 copy 25 15 roll
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      5 copy 5 copy 35 5 roll 25 5 roll 15 5 roll
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      5 copy 5 copy 40 5 roll 25 5 roll 15 5 roll 25 5 roll
+      STnoshfill STnoshfill STnoshfill STnoshfill } BD
+/STnoshfill {
+      2 index 8 index sub abs rThreshold gt
+      { STsplit }
+      { 1 index 7 index sub abs gThreshold gt
+        { STsplit }
+        { dup 6 index sub abs bThreshold gt
+          { STsplit }
+          { 2 index 13 index sub abs rThreshold gt
+            { STsplit }
+            { 1 index 12 index sub abs gThreshold gt
+              { STsplit }
+              { dup 11 index sub abs bThreshold gt
+                { STsplit }
+                { 7 index 13 index sub abs rThreshold gt
+                  { STsplit }
+                  { 6 index 12 index sub abs gThreshold gt
+                    { STsplit }
+                    { 5 index 11 index sub abs bThreshold gt
+                      { STsplit }
+                      { Tm }
+                      ifelse }
+                    ifelse }
+                  ifelse }
+                ifelse }
+              ifelse }
+            ifelse }
+          ifelse }
+        ifelse }
+      ifelse } BD
+tryPS3shading
+{ /shfill where
+  { /ST { STshfill } BD }
+  { /ST { STnoshfill } BD }
+  ifelse }
+{ /ST { STnoshfill } BD }
+ifelse
+end
+%%EndProlog
+%%BeginSetup
+/DeviceRGB setcolorspace
+gl2psdict begin
+%%EndSetup
+%%Page: 1 1
+%%BeginPageSetup
+%%EndPageSetup
+mark
+gsave
+1.0 1.0 scale
+1 1 1 C
+newpath 0 0 moveto 576 0 lineto 576 432 lineto 0 432 lineto
+closepath fill
+gsave
+1.0 1.0 scale
+1 1 1 C
+newpath 0 0 moveto 576 0 lineto 576 432 lineto 0 432 lineto
+closepath fill
+newpath 0 0 moveto 576 0 lineto 576 432 lineto 0 432 lineto
+closepath clip
+1 1 1 C
+74.88 399.6 521.28 47.52 74.88 47.52 T
+74.88 399.6 521.28 399.6 521.28 47.52 T
+0.5 W
+0.15 0.15 0.15 C
+74.88 47.52 LS
+74.88 51.985 LE
+74.88 399.6 LS
+74.88 395.135 LE
+186.48 47.52 LS
+186.48 51.985 LE
+186.48 399.6 LS
+186.48 395.135 LE
+298.08 47.52 LS
+298.08 51.985 LE
+298.08 399.6 LS
+298.08 395.135 LE
+409.68 47.52 LS
+409.68 51.985 LE
+409.68 399.6 LS
+409.68 395.135 LE
+521.28 47.52 LS
+521.28 51.985 LE
+521.28 399.6 LS
+521.28 395.135 LE
+gsave
+0.14902 0.14902 0.14902 C
+(0) [10] 0 71.88 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(5) [10] 0 183.48 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(10) [6 10] 0 292.08 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(15) [6 10] 0 403.68 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(20) [6 10] 0 515.28 32.0183 10 /Helvetica SRX
+grestore
+
+74.88 47.52 LS
+79.348 47.52 LE
+521.28 47.52 LS
+516.812 47.52 LE
+74.88 117.936 LS
+79.348 117.936 LE
+521.28 117.936 LS
+516.812 117.936 LE
+74.88 188.352 LS
+79.348 188.352 LE
+521.28 188.352 LS
+516.812 188.352 LE
+74.88 258.768 LS
+79.348 258.768 LE
+521.28 258.768 LS
+516.812 258.768 LE
+74.88 329.184 LS
+79.348 329.184 LE
+521.28 329.184 LS
+516.812 329.184 LE
+74.88 399.6 LS
+79.348 399.6 LE
+521.28 399.6 LS
+516.812 399.6 LE
+gsave
+0.14902 0.14902 0.14902 C
+(20) [6 10] 0 57.8755 43.52 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(40) [6 10] 0 57.8755 113.936 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(60) [6 10] 0 57.8755 184.352 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(80) [6 10] 0 57.8755 254.768 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(100) [6 6 10] 0 51.8755 325.184 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(120) [6 6 10] 0 51.8755 395.6 10 /Helvetica SRX
+grestore
+
+2 LC
+[16 0] 0 setdash
+74.88 47.52 LS
+521.28 47.52 LE
+74.88 399.6 LS
+521.28 399.6 LE
+74.88 47.52 LS
+74.88 399.6 LE
+521.28 47.52 LS
+521.28 399.6 LE
+0 LC
+1 LJ
+[] 0 setdash
+0.34524 0.34524 0.34524 C
+97.2 330.455 LS
+119.52 159.121 L
+141.84 99.3384 L
+164.16 68.3578 L
+186.48 91.1399 L
+208.8 72.1047 L
+231.12 59.2847 L
+253.44 51.1538 L
+275.76 70.0718 L
+298.08 68.2445 L
+320.4 76.0835 L
+342.72 71.7544 L
+365.04 65.1064 L
+387.36 58.7612 L
+409.68 58.4204 L
+432 63.233 LE
+grestore
+grestore
+showpage
+cleartomark
+%%PageTrailer
+%%Trailer
+end
+%%EOF
diff --git a/a3/int.pdf b/a3/int.pdf
new file mode 100644
index 0000000..79de095
--- /dev/null
+++ b/a3/int.pdf
diff --git a/a3/string.eps b/a3/string.eps
new file mode 100644
index 0000000..f9f5aa0
--- /dev/null
+++ b/a3/string.eps
@@ -0,0 +1,279 @@
+%!PS-Adobe-3.0 EPSF-3.0
+%%Title: gl2ps_renderer figure
+%%Creator: GL2PS 1.4.2, (C) 1999-2020 C. Geuzaine
+%%For: Octave
+%%CreationDate: Thu Jul 27 17:29:03 2023
+%%LanguageLevel: 3
+%%DocumentData: Clean7Bit
+%%Pages: 1
+%%BoundingBox: 0 0 576 432
+%%EndComments
+%%BeginProlog
+/gl2psdict 64 dict def gl2psdict begin
+/tryPS3shading false def % set to false to force subdivision
+/rThreshold 0.064 def % red component subdivision threshold
+/gThreshold 0.034 def % green component subdivision threshold
+/bThreshold 0.1 def % blue component subdivision threshold
+/BD { bind def } bind def
+/C  { setrgbcolor } BD
+/G  { 0.082 mul exch 0.6094 mul add exch 0.3086 mul add neg 1.0 add setgray } BD
+/W  { setlinewidth } BD
+/LC  { setlinecap } BD
+/LJ  { setlinejoin } BD
+/FC { findfont exch /SH exch def SH scalefont setfont } BD
+/SW { dup stringwidth pop } BD
+/S  { FC moveto show } BD
+/SBC{ FC moveto SW -2 div 0 rmoveto show } BD
+/SBR{ FC moveto SW neg 0 rmoveto show } BD
+/SCL{ FC moveto 0 SH -2 div rmoveto show } BD
+/SCC{ FC moveto SW -2 div SH -2 div rmoveto show } BD
+/SCR{ FC moveto SW neg SH -2 div rmoveto show } BD
+/STL{ FC moveto 0 SH neg rmoveto show } BD
+/STC{ FC moveto SW -2 div SH neg rmoveto show } BD
+/STR{ FC moveto SW neg SH neg rmoveto show } BD
+/FCT { FC translate 0 0 } BD
+/SR  { gsave FCT moveto rotate show grestore } BD
+/SRX  { gsave FCT moveto rotate xshow grestore } BD
+/SBCR{ gsave FCT moveto rotate SW -2 div 0 rmoveto show grestore } BD
+/SBRR{ gsave FCT moveto rotate SW neg 0 rmoveto show grestore } BD
+/SCLR{ gsave FCT moveto rotate 0 SH -2 div rmoveto show grestore} BD
+/SCCR{ gsave FCT moveto rotate SW -2 div SH -2 div rmoveto show grestore} BD
+/SCRR{ gsave FCT moveto rotate SW neg SH -2 div rmoveto show grestore} BD
+/STLR{ gsave FCT moveto rotate 0 SH neg rmoveto show grestore } BD
+/STCR{ gsave FCT moveto rotate SW -2 div SH neg rmoveto show grestore } BD
+/STRR{ gsave FCT moveto rotate SW neg SH neg rmoveto show grestore } BD
+/P  { newpath 0.0 360.0 arc closepath fill } BD
+/LS { newpath moveto } BD
+/L  { lineto } BD
+/LE { lineto stroke } BD
+/T  { newpath moveto lineto lineto closepath fill } BD
+/STshfill {
+      /b1 exch def /g1 exch def /r1 exch def /y1 exch def /x1 exch def
+      /b2 exch def /g2 exch def /r2 exch def /y2 exch def /x2 exch def
+      /b3 exch def /g3 exch def /r3 exch def /y3 exch def /x3 exch def
+      gsave << /ShadingType 4 /ColorSpace [/DeviceRGB]
+      /DataSource [ 0 x1 y1 r1 g1 b1 0 x2 y2 r2 g2 b2 0 x3 y3 r3 g3 b3 ] >>
+      shfill grestore } BD
+/Tm { 3 -1 roll 8 -1 roll 13 -1 roll add add 3 div
+      3 -1 roll 7 -1 roll 11 -1 roll add add 3 div
+      3 -1 roll 6 -1 roll 9 -1 roll add add 3 div C T } BD
+/STsplit {
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      4 index 15 index add 0.5 mul
+      5 copy 5 copy 25 15 roll
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      9 index 30 index add 0.5 mul
+      5 copy 5 copy 35 5 roll 25 5 roll 15 5 roll
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      4 index 10 index add 0.5 mul
+      5 copy 5 copy 40 5 roll 25 5 roll 15 5 roll 25 5 roll
+      STnoshfill STnoshfill STnoshfill STnoshfill } BD
+/STnoshfill {
+      2 index 8 index sub abs rThreshold gt
+      { STsplit }
+      { 1 index 7 index sub abs gThreshold gt
+        { STsplit }
+        { dup 6 index sub abs bThreshold gt
+          { STsplit }
+          { 2 index 13 index sub abs rThreshold gt
+            { STsplit }
+            { 1 index 12 index sub abs gThreshold gt
+              { STsplit }
+              { dup 11 index sub abs bThreshold gt
+                { STsplit }
+                { 7 index 13 index sub abs rThreshold gt
+                  { STsplit }
+                  { 6 index 12 index sub abs gThreshold gt
+                    { STsplit }
+                    { 5 index 11 index sub abs bThreshold gt
+                      { STsplit }
+                      { Tm }
+                      ifelse }
+                    ifelse }
+                  ifelse }
+                ifelse }
+              ifelse }
+            ifelse }
+          ifelse }
+        ifelse }
+      ifelse } BD
+tryPS3shading
+{ /shfill where
+  { /ST { STshfill } BD }
+  { /ST { STnoshfill } BD }
+  ifelse }
+{ /ST { STnoshfill } BD }
+ifelse
+end
+%%EndProlog
+%%BeginSetup
+/DeviceRGB setcolorspace
+gl2psdict begin
+%%EndSetup
+%%Page: 1 1
+%%BeginPageSetup
+%%EndPageSetup
+mark
+gsave
+1.0 1.0 scale
+1 1 1 C
+newpath 0 0 moveto 576 0 lineto 576 432 lineto 0 432 lineto
+closepath fill
+gsave
+1.0 1.0 scale
+1 1 1 C
+newpath 0 0 moveto 576 0 lineto 576 432 lineto 0 432 lineto
+closepath fill
+newpath 0 0 moveto 576 0 lineto 576 432 lineto 0 432 lineto
+closepath clip
+1 1 1 C
+74.88 399.6 521.28 47.52 74.88 47.52 T
+74.88 399.6 521.28 399.6 521.28 47.52 T
+0.5 W
+0.15 0.15 0.15 C
+74.88 47.52 LS
+74.88 51.985 LE
+74.88 399.6 LS
+74.88 395.135 LE
+186.48 47.52 LS
+186.48 51.985 LE
+186.48 399.6 LS
+186.48 395.135 LE
+298.08 47.52 LS
+298.08 51.985 LE
+298.08 399.6 LS
+298.08 395.135 LE
+409.68 47.52 LS
+409.68 51.985 LE
+409.68 399.6 LS
+409.68 395.135 LE
+521.28 47.52 LS
+521.28 51.985 LE
+521.28 399.6 LS
+521.28 395.135 LE
+gsave
+0.14902 0.14902 0.14902 C
+(0) [10] 0 71.88 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(5) [10] 0 183.48 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(10) [6 10] 0 292.08 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(15) [6 10] 0 403.68 32.0183 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(20) [6 10] 0 515.28 32.0183 10 /Helvetica SRX
+grestore
+
+74.88 47.52 LS
+79.348 47.52 LE
+521.28 47.52 LS
+516.812 47.52 LE
+74.88 117.936 LS
+79.348 117.936 LE
+521.28 117.936 LS
+516.812 117.936 LE
+74.88 188.352 LS
+79.348 188.352 LE
+521.28 188.352 LS
+516.812 188.352 LE
+74.88 258.768 LS
+79.348 258.768 LE
+521.28 258.768 LS
+516.812 258.768 LE
+74.88 329.184 LS
+79.348 329.184 LE
+521.28 329.184 LS
+516.812 329.184 LE
+74.88 399.6 LS
+79.348 399.6 LE
+521.28 399.6 LS
+516.812 399.6 LE
+gsave
+0.14902 0.14902 0.14902 C
+(50) [6 10] 0 57.8755 43.52 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(100) [6 6 10] 0 51.8755 113.936 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(150) [6 6 10] 0 51.8755 184.352 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(200) [6 6 10] 0 51.8755 254.768 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(250) [6 6 10] 0 51.8755 325.184 10 /Helvetica SRX
+grestore
+
+gsave
+0.14902 0.14902 0.14902 C
+(300) [6 6 10] 0 51.8755 395.6 10 /Helvetica SRX
+grestore
+
+2 LC
+[16 0] 0 setdash
+74.88 47.52 LS
+521.28 47.52 LE
+74.88 399.6 LS
+521.28 399.6 LE
+74.88 47.52 LS
+74.88 399.6 LE
+521.28 47.52 LS
+521.28 399.6 LE
+0 LC
+1 LJ
+[] 0 setdash
+0.34524 0.34524 0.34524 C
+97.2 346.094 LS
+119.52 168.943 L
+141.84 106.006 L
+164.16 86.7582 L
+186.48 84.4471 L
+208.8 67.0992 L
+231.12 54.9937 L
+253.44 50.2669 L
+275.76 60.4543 L
+298.08 59.4455 L
+320.4 61.9337 L
+342.72 60.7962 L
+365.04 57.4596 L
+387.36 54.4847 L
+409.68 54.1613 L
+432 48.6819 LE
+grestore
+grestore
+showpage
+cleartomark
+%%PageTrailer
+%%Trailer
+end
+%%EOF
diff --git a/a3/string.pdf b/a3/string.pdf
new file mode 100644
index 0000000..af4cfc2
--- /dev/null
+++ b/a3/string.pdf
diff --git a/preamble.tex b/preamble.tex
index ced8266..8571b61 100644
--- a/preamble.tex
+++ b/preamble.tex
@@ -1,4 +1,5 @@
 \documentclass[11pt]{article}
+\usepackage{graphicx}
 \usepackage{fancyhdr}
 \pagestyle{fancy}
 \author{Bent Bisballe Nyeng <deva@aasimon.org> University of Aarhus}