A4: Finalize report

2 files changed, 40 insertions, 32 deletions

diff --git a/a4/exercise.tex b/a4/exercise.tex
index 6ddb081..e6e57ea 100644
--- a/a4/exercise.tex
+++ b/a4/exercise.tex
@@ -1,9 +1,9 @@
 \title{A4: List vs Vector}
 \input{preamble.tex}
 
-I wanted to experiment with co-routine generator for the random
-numbers but discovered the \texttt{std::generator} is not supplied
-with my compiler.
+In this exercise I had the idea that I wanted to experiment with
+co-routine generator for the random numbers but discovered
+the \texttt{std::generator} is not supplied with my compiler.
 Instead I found what seemed like a similar implementation here:
 \texttt{https://en.cppreference.com/w/cpp/language/coroutines}, which
 I have copied to the \texttt{generator.h} file for use in my program.
@@ -24,7 +24,7 @@ suit my needs for this assignment.
 
 \bigskip
 
-The main code for exercise is in the file
+\noindent{}The main code for exercise is in the file
 called \texttt{list\_vs\_vector.cc}
 
 \bigskip
@@ -36,9 +36,9 @@ For the ditto for removal indices, I used
 a \texttt{uniform\_distribution} thereby being able to gradually
 reduce the span as the container would be expected to shrink 1 in size
 for each iteration.
-Both random number generators were seeded with the iterator number
-(each size is being tested three times) to make sure the three
-iterations use unique sets of numbers.
+Both random number generators were seeded with the iteration number
+(each size, \texttt{N}, is being tested three times) to make sure the
+three iterations use unique sets of numbers.
 
 For the smaller sizes of \texttt{N} (the number of items to be
 inserted/removed) i print out the numbers to verify their
@@ -51,8 +51,11 @@ int with chars up to 1k. The log files for the executions are
 named \texttt{console.log} and \texttt{console-padding.log}
 respectively.
 
-For the insertion and removal two templated functions were written:
-\begin{lstlisting}[language=C++]
+\bigskip
+
+\noindent{}For the insertion and removal two templated functions were
+written:
+\footnotesize\begin{lstlisting}[language=C++]
 template<typename C, typename T>
 void sorted_insert(C& container, T element)
 {
@@ -76,7 +79,7 @@ void remove_index(C& container, int index)
 
 	container.erase(it);
 }
-\end{lstlisting}
+\end{lstlisting}\normalsize
 
 With the exception of set insertion, these two functions are used
 for all the timed container operations, ie. no clever stuff should be
@@ -95,11 +98,13 @@ that into the more optimized \texttt{vec.begin() + n} random access
 iterator lookup.
 At the same time the bad performance of \texttt{std::list} puzzled
 me. But it might be because the list has to allocate each of its
-elements on the freestore, which the \texttt{std::set} also has to
-do. So I'm not really sure what is going on there.
+elements on the freestore, which, on the other hand,
+the \texttt{std::set} also had to do. So I'm not really sure what is
+going on there.
 
-Similarly in \textit{figure \ref{remove}} the three containers are
-compared when removing the \texttt{int}s again by randomized index.
+Similarly in \textit{figure \ref{remove}} the performance of the three
+containers are compared when removing the \texttt{int}s again by
+randomized index.
 Again I was expecting the \texttt{std::vector} to outperform the other
 two, but not as much as it did.
 I was however expecting the \texttt{std::set} to be slightly slower
@@ -108,21 +113,21 @@ rebalancing the tree.
 
 \begin{figure}[!tbp]
   \makebox[\textwidth][c]{%
-  \subfloat[Insert]{\scalebox{1.7}{\includegraphics[scale=0.4]{a4/insert.pdf}}\label{insert}}
+  \subfloat[Insert]{\scalebox{1.7}{\includegraphics[scale=0.35]{a4/insert.pdf}}\label{insert}}
   \quad
-  \subfloat[Removal]{\scalebox{1.7}{\includegraphics[scale=0.4]{a4/remove.pdf}}\label{remove}}
+  \subfloat[Removal]{\scalebox{1.7}{\includegraphics[scale=0.35]{a4/remove.pdf}}\label{remove}}
   }
 \caption{Plot of operations on the three container types using regular \texttt{int}s}
 \end{figure}
 
-\bigskip
+\clearpage
 
 To see how much impact the data locality has on the performance of the
 three container types, the experiments are repeated with a much bigger
 value type.
 I decided to create a \texttt{struct}, \texttt{PaddedInt}, with the
 needed member functions for it to be storable inside the three containers:
-\begin{lstlisting}[language=C++]
+\footnotesize\begin{lstlisting}[language=C++]
 struct PaddedInt
 {
 	PaddedInt(int i) : i(i) {}
@@ -145,14 +150,15 @@ struct PaddedInt
 	int i;
 	char padding[1024 - sizeof(int)]{}; // pad up to 1k
 };
-\end{lstlisting}
-It add padding to each stored item is 1024 bytes.
+\end{lstlisting}\normalsize
+It adds padding to each stored item so that it ends up with a size of
+1024 bytes.
 
 \begin{figure}[!tbp]
   \makebox[\textwidth][c]{%
-  \subfloat[Insert of padded int]{\scalebox{1.7}{\includegraphics[scale=0.4]{a4/insert-padded.pdf}}\label{insert-padded}}
+  \subfloat[Insert of padded int]{\scalebox{1.7}{\includegraphics[scale=0.35]{a4/insert-padded.pdf}}\label{insert-padded}}
   \quad
-  \subfloat[Removal of padding int]{\scalebox{1.7}{\includegraphics[scale=0.4]{a4/remove-padded.pdf}}\label{remove-padded}}
+  \subfloat[Removal of padding int]{\scalebox{1.7}{\includegraphics[scale=0.35]{a4/remove-padded.pdf}}\label{remove-padded}}
   }
 \caption{Plot of operations on the three container types using structure with and \texttt{int} and padding up to 1kb}
 \end{figure}
@@ -168,24 +174,25 @@ Looking at \textit{figure \ref{insert-padded}} the performance of the
 insertion indeed seem to have become a lot worse for
 the \texttt{std::vector}. Looking at the absolute performance of
 the \texttt{std::list} and comparing it
-to \textit{figure \ref{insert}} it has become $~10\%$
+to \textit{figure \ref{insert}} it has become $\sim{}10\%$
 slower. \texttt{std::set} on the other hand seem to be largely
-unaffected by the increase in value type. This is likely because of
-its $O(log(n))$ lookup times, which means that it only have to do a
-fraction of the number of fetches from the free-store compared to the
-other two.
+unaffected by the increase in value type size. This is likely because of
+its $O(log(n))$ lookup/insertion times, which means that it only have
+to do a fraction of the number of fetches from the free-store compared
+to the other two (the full data of
+the \texttt{PaddedInt} \texttt{struct} is needed for each comparison).
 
 Removal of the padded elements from the \texttt{std::list}
 and \texttt{std::set} are expected to be unaffected by the increase if
 value type size, since they both just store pointers, and because the
-iteations used to find the index is not needing data from the value
-type.
+iterations used to find the index is not needing data from the value
+type; only the next pointer is needed.
 On the other hand, \texttt{std::vector} will have to do a lot copying
 of data (the entire tail will have to be copied one index to the
-left), when erasing item in the middle, which amounts top a lot of
+left), when erasing an item in the middle, which amounts to a lot of
 data.
-A can be seen in \textit{figure \ref{remove-padded}}, as expected, the
-performces of \texttt{std::list} and \texttt{std::set} are close to
+As can be seen in \textit{figure \ref{remove-padded}}, as expected, the
+performances of \texttt{std::list} and \texttt{std::set} are close to
 the \texttt{int} counterparts. And, also as expected,
 the \texttt{std::vector} is really being slowed down.
 
diff --git a/preamble.tex b/preamble.tex
index 30d475a..993fe82 100644
--- a/preamble.tex
+++ b/preamble.tex
@@ -4,6 +4,7 @@
 \usepackage{fancyhdr}
 \usepackage{listings}
 \usepackage{subfig}
+\renewcommand{\floatpagefraction}{.8}%
 %\renewcommand{\thesubfigure}{Figure \arabic{subfigure}}
 \captionsetup[subfigure]{labelformat=simple, labelsep=colon}
 \pagestyle{fancy}