summaryrefslogtreecommitdiff
path: root/a4
diff options
context:
space:
mode:
Diffstat (limited to 'a4')
-rw-r--r--a4/exercise.tex163
1 files changed, 144 insertions, 19 deletions
diff --git a/a4/exercise.tex b/a4/exercise.tex
index af53ea5..6ddb081 100644
--- a/a4/exercise.tex
+++ b/a4/exercise.tex
@@ -24,6 +24,11 @@ suit my needs for this assignment.
\bigskip
+The main code for exercise is in the file
+called \texttt{list\_vs\_vector.cc}
+
+\bigskip
+
The random number generation for use in insertion I used the
co-routine as described above, inserting, while checking if the number
already exists.
@@ -36,32 +41,152 @@ Both random number generators were seeded with the iterator number
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 correctness.
+inserted/removed) i print out the numbers to verify their
+correctness. These numbers can be seen in the log files in the zip
+file.
+The program has been compiled and executed with both a built-in int as
+the value type of the three containers and a struct padding a single
+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++]
+template<typename C, typename T>
+void sorted_insert(C& container, T element)
+{
+ auto it = std::begin(container);
+ while(it != std::end(container) && *it < element)
+ {
+ ++it;
+ }
-\begin{figure}
- \includegraphics[scale=0.95]{a4/insert.pdf}
- \caption{Insert of int}
- \label{insert}
-\end{figure}
+ container.insert(it, element);
+}
-\begin{figure}
- \includegraphics[scale=.95]{a4/remove.pdf}
- \caption{Removal of int}
- \label{remove}
-\end{figure}
+template<typename C>
+void remove_index(C& container, int index)
+{
+ auto it = std::begin(container);
+ for(int i = 0; i < index; ++i)
+ {
+ ++it;
+ }
+
+ container.erase(it);
+}
+\end{lstlisting}
+
+With the exception of set insertion, these two functions are used
+for all the timed container operations, ie. no clever stuff should be
+going on in the index/iterator lookups.
+
+\bigskip
+
+In \textit{figure \ref{insert}} the insertion times for \texttt{int}s in the
+three container types \texttt{std::vector}, \texttt{std::list}
+and \texttt{std::set} can be seen.
+I was expecting the \texttt{std::vector} to outperform the othr two
+because of data locality, and this is indeed the case. I was however
+surprised how much it outperformed them, but this might be because the
+compiler could see through my ``slow'' iterator looping and convert
+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.
+
+Similarly in \textit{figure \ref{remove}} 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
+than the \texttt{std::list} because of the extra needed work for
+rebalancing the tree.
-\begin{figure}
- \includegraphics[scale=0.95]{a4/insert-padded.pdf}
- \caption{Insert of padded-int (1024 bytes pr. value)}
- \label{insert-padded}
+\begin{figure}[!tbp]
+ \makebox[\textwidth][c]{%
+ \subfloat[Insert]{\scalebox{1.7}{\includegraphics[scale=0.4]{a4/insert.pdf}}\label{insert}}
+ \quad
+ \subfloat[Removal]{\scalebox{1.7}{\includegraphics[scale=0.4]{a4/remove.pdf}}\label{remove}}
+ }
+\caption{Plot of operations on the three container types using regular \texttt{int}s}
\end{figure}
-\begin{figure}
- \includegraphics[scale=.95]{a4/remove-padded.pdf}
- \caption{Removal of padded-int (1024 bytes pr. value)}
- \label{remove-padded}
+\bigskip
+
+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++]
+struct PaddedInt
+{
+ PaddedInt(int i) : i(i) {}
+ int operator=(int other)
+ {
+ i = other;
+ return i;
+ }
+
+ bool operator<(int other) const
+ {
+ return i < other;
+ }
+
+ bool operator<(const PaddedInt& other) const
+ {
+ return i < other.i;
+ }
+
+ int i;
+ char padding[1024 - sizeof(int)]{}; // pad up to 1k
+};
+\end{lstlisting}
+It add padding to each stored item is 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}}
+ \quad
+ \subfloat[Removal of padding int]{\scalebox{1.7}{\includegraphics[scale=0.4]{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}
+With this configuration a decrease in the performance of
+the \texttt{std::vector} is expected as opposed to
+the \texttt{std::list} and \texttt{std::set} which only carry pointers
+to their items.
+
+\bigskip
+
+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\%$
+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.
+
+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.
+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
+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
+the \texttt{int} counterparts. And, also as expected,
+the \texttt{std::vector} is really being slowed down.
+
\end{document}