summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--a4/exercise.tex71
-rw-r--r--preamble.tex1
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}