diff options
| -rw-r--r-- | a4/exercise.tex | 71 | ||||
| -rw-r--r-- | preamble.tex | 1 |
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} |