<gh_stars>0
\chapter{Experimental Evaluation}
\label{chap:experimental-evaluation}
	In this chapter we evaluate our implementation of the system for transforming data in the relational model to the document model and vice versa described in \cref{chap:tale-of-two-data-models}.  We cover the implementation details in \cref{sec:implementation}, and the methodology and evaluation in \cref{sec:runtime-evaluation}.
	
	\section{Implementation}
	\label{sec:implementation}
		The system was implemented in Clojure, which \textcquote{clj-home}{is a dynamic programming language that targets the \gls{jvm}}.  Clojure was chosen due to its rich, immutable, and persistent data structures, first-class concurrency support, and seamless \gls{jvm} interoperability.  These features were discussed in detail in \cref{sec:features-of-clojure}.
		
		\subsection{Code Base Statistics}
			The system consists of over 800 lines of Clojure, along with approximately 550 lines of Python.  The Python code is used to construct the data set by crawling the course information site, as well as to aggregate the benchmark data produced by the system, producing graphs.
			
			All development has occurred on GitHub \cite{molly-repo}.  The use of Git and GitHub permits collaboration between researchers.  With the code publicly available, future researchers may study, run, and, build upon it.
	
	\section{The Data Corpus}
	\label{sec:data-corpus}
		The data corpus was derived from the \gls{uoit} mycampus database.  It is not a standard dataset used in the literature, but a dataset unique to \gls{uoit}.
		
		An \gls{html} crawler was written in Python that scraped the information from the \gls{uoit} class schedule search page.  This data was parsed, normalized, then placed in a SQLite database.
		
		The data corpus consists of numerous classes of objects.  These are:  courses (\cref{tbl:corpus-course}), instructors (\cref{tbl:corpus-instructor}), schedules (\cref{tbl:corpus-schedule}), sections (\cref{tbl:corpus-section}), and teaches (\cref{tbl:corpus-teaches}).  A graph representation of how these classes of objects are related can be found in \cref{fig:schema-graph}.  The data corpus is defined in \cref{chap:data-corpus-def}
		
		The number of objects, as of the publication of this thesis, can be found in \cref{tbl:data-corpus-count}.
		
		\begin{table}
			\centering
			\begin{tabular}{lr}
			\toprule
			Class & Count \\
			\midrule
			Course & 1340 \\
			Instructor & 849 \\
			Schedule & 25755 \\
			Section & 14463 \\
			Teaches & 15358 \\
			\bottomrule
			\end{tabular}
			
			\caption{Number of objects in data corpus, grouped by class}
			\label{tbl:data-corpus-count}
		\end{table}
	
	\section{Runtime Evaluation}
	\label{sec:runtime-evaluation}
		Scripts were written to coordinate the execution, collection, and transformation of the performance data of our implementation.
		
		\subsection{Methodology}
			We used Criterium\footnote{\url{http://hugoduncan.org/criterium/}} to handle the execution of the benchmarks as it handles unique concerns stemming from benchmarking on the \gls{jvm}.  These issues, identified by \citeauthor{rob-java-bench-08} \cite{rob-java-bench-08}, include:
			
			\begin{itemize}
				\item Statistical processing of multiple evaluations
				\item Inclusion of a warm-up period which is intended to allow the JIT compiler to translate the Java byte code into native instructions
				\item Purging of the garbage collector before testing, to isolate timings from GC state prior to testing
				\item A final forced garbage collection after testing to estimate impact of cleanup on the timing results
			\end{itemize}
			
			As each function is invoked numerous times, this greatly increases the runtime.
			
			During evaluation, Criterium collects performance metrics.  Upon completion of the evaluation, it performs statistical analysis of these metrics using the bootstrap procedure developed by \citeauthor{efron-87} \cite{efron-87}.  These metrics include mean, samples, variance, quartiles, outliers, and more.
		
			\subsubsection{Data Collection}
			\label{sec:data-collection}
				The performance metrics computed by Criterium are returned as a Clojure map data structure.  The evaluation process may take several hours to complete, necessitating a separation between data collection and post-processing.  These metrics are stored offline for further processing.
				
				A data interchange format (\gls{json}) is used to utilize the Clojure output in Python.  The benchmark function writes the Criterium performance analysis out as a \gls{json} string to stdout and the output is captured by the benchmark script.  An example of this \gls{json} output is given in \cref{fig:criterium-json-output}.
				
				\begin{figure}
					\centering % Pointless, but who knows in the future.
					\begin{verbatim}
                    [{
                        "max-hops": ...,
                        "method": ...,
                        "results": {
                            "execution-count": ...,
                            "final-gc-time": ...,
                            "lower-q": [...],
                            "mean": [...],
                        ...
                    }, ...]
					\end{verbatim}
					
					\caption{Partial \gls{json} output from Criterium}
					\label{fig:criterium-json-output}
				\end{figure}
		
		\subsection{Performance}
		\label{sec:performance}
			Performance was measured for the system components.  An analysis of the metrics collected is presented in this section.
			
			\subsubsection{Indexing}
				The indexing process is computationally intensive but short lived.  After the initial \gls{jvm} warmup period, the time required to construct the index scales with the number of named tuples and relations between them.
				
				\begin{table}
					\centering
					\begin{tabular}{ll}
						\toprule
						Number of Groups & Elapsed Time (s) \\
						\midrule
						0 & 11.800 \\
						1 & 12.446 \\
						2 & 19.771 \\
						\bottomrule
					\end{tabular}
					
					\caption{Indexing time growth by number of entity groups, averaged over 5 runs}
					\label{tbl:index-growth-entity-groups}
				\end{table}
				
				We see in \cref{tbl:index-growth-entity-groups} the indexing time increases minimally between 0 and 1 group.  Few entity groups are created by the first entity schema.  Contrast this to the indexing time between 1 and 2 groups, which increases considerably.  The number of entity groups also grew considerably, explaining the time increase.
			
			\subsubsection{Graph Search}
				The worst-case performance of \gls{bfs} is \(\mathcal{O}(n^2)\).  This is reflected in \cref{fig:growth} which follows a polynomial growth curve.  In an attempt to mitigate the rapid increase in search time, concurrent variants of \gls{bfs} were also implemented and benchmarked.
				
				\begin{figure}
					\centering
					\input{figures/charts/lineplot.pgf}
					\caption{Growth of each graph search algorithm implementation by number of hops}
					\label{fig:growth}
				\end{figure}
				
				We see in \cref{fig:growth-bfs} the rate of growth of \gls{bfs} is as expected.  The rate of growth of \gls{bfs} with references (\cref{fig:growth-bfs-refs}) and \gls{bfs} with atoms (\cref{fig:growth-bfs-atoms}) is nearly linear.  The atom implementation is slightly more performant as it lacks some of the overhead associated with references.
				
				\begin{figure}
					\begin{subfigure}[b]{1.0\linewidth}
						\input{figures/charts/boxplot-bfs.pgf}
						\caption{Growth of \gls{bfs}}
						\label{fig:growth-bfs}
					\end{subfigure}
					\begin{subfigure}[b]{1.0\linewidth}
						\input{figures/charts/boxplot-bfs-atom.pgf}
						\caption{Growth of \gls{bfs} using atoms}
						\label{fig:growth-bfs-atoms}
					\end{subfigure}
					\begin{subfigure}[b]{1.0\linewidth}
						\input{figures/charts/boxplot-bfs-ref.pgf}
						\caption{Growth of \gls{bfs} using references}
						\label{fig:growth-bfs-refs}
					\end{subfigure}
					
					\caption{Growth of various \gls{bfs} implementations}
				\end{figure}
				
				The difference in rate of growth is further illustrated in \cref{fig:distribution-hops}.  As seen previously, \cref{subfig:1-hop} shows little difference in runtime between the three methods.  The difference becomes clearer in \cref{subfig:2-hops}, and by \cref{subfig:8-hops}, the difference is obvious.
				
				\begin{figure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-1-hops.pgf}
						\caption{1 Hop}
						\label{subfig:1-hop}
					\end{subfigure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-2-hops.pgf}
						\caption{2 Hops}
						\label{subfig:2-hops}
					\end{subfigure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-3-hops.pgf}
						\caption{3 Hops}
						\label{subfig:3-hops}
					\end{subfigure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-4-hops.pgf}
						\caption{4 Hops}
						\label{subfig:4-hops}
					\end{subfigure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-5-hops.pgf}
						\caption{5 Hops}
						\label{subfig:5-hops}
					\end{subfigure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-6-hops.pgf}
						\caption{6 Hops}
						\label{subfig:6-hops}
					\end{subfigure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-7-hops.pgf}
						\caption{7 Hops}
						\label{subfig:7-hops}
					\end{subfigure}
					\begin{subfigure}[b]{.5\linewidth}
						\input{figures/charts/boxplot-8-hops.pgf}
						\caption{8 Hops}
						\label{subfig:8-hops}
					\end{subfigure}
					
					\caption{Distribution of samples per method, broken down by hops}
					\label{fig:distribution-hops}
				\end{figure}
				
				By using a profiling tool\footnote{\url{http://yourkit.com/}}, we see the behaviour of Clojure's concurrency implementation.
				
				\begin{figure}
					\centering
					
					\includegraphics{figures/images/threads}
					
					\caption{Thread count while running \gls{bfs} atom benchmark}
					\label{fig:runtime-threads}
				\end{figure}
				
				In \cref{fig:runtime-threads} we see that a number of threads are created and destroyed.  Recall a new thread is created every time the frontier is populated.
	
	\section{Complexity Analysis}
	\label{sec:complexity-analysis}
		The initial part of the search operation, retrieval of one or more records, requires searching through a hash table.  In the best-case scenario, the time complexity lookup is constant time (\(\mathcal{O}(1)\)), while in the worst-case it is linear (\(\mathcal{O}(n)\)).
		
		The second part of the search operation, graph search, uses \gls{bfs}.  In the worst-case scenario, every vertex and edge in the graph must be visited, leading to a time complexity of \(\mathcal{O}(\abs{V} + \abs{E})\).  Depending on the sparsity of the graph, the complexity may be closer to \(\mathcal{O}(n^2)\).  This is clearly visible in \cref{fig:growth-bfs} which shows the growth of \gls{bfs}.
	
	\section{Threats to Validity}
	\label{sec:threats-to-validity}
		No experiment is without its flaws.  In this section we discuss the factors that may affect the validity of the experimental evaluation.  These factors are referred to as threats to validity.
		
		We used a non-standard dataset to evaluate the system.  This dataset was originally chosen due to its reasonable size.  It also originated from a relational database.  A standard dataset, such as DBLP\footnote{\url{http://dblp.uni-trier.de/}}, is semi-structured and thus unsuitable to demonstrate the transformation from relational data.  The choice of a non-standard dataset makes it difficult to compare performance across systems.
		
		The use of a single dataset presents another issue.  By only using one dataset, it is difficult to generalize the results.  Ideally multiple datasets, each with varying characteristics, would have been used for evaluation.  This is potential area for future work to be done.
	
	\section{Summary}
	\label{sec:eval-summary}
		The system was implemented primarily in Clojure with supporting code written in Python.  The Python code was used to produce the mycampus dataset which was used in the evaluation.  It was also used to orchestrate the execution of benchmarks.
		
		In \cref{sec:runtime-evaluation} we described the experimental methodology and data collection.  We then evaluated the performance of the system using said methodology.  The results demonstrated that the growth of \gls{bfs} can be mitigated by the use of concurrency.  Clojure facilitated a natural transition from a classical implementation of \gls{bfs} to a highly concurrent one.
		
		The assessment of system performance was not without its flaws.  These were discussed in \cref{sec:threats-to-validity}.  The primary threat to validity was the lack of comparison between other systems and datasets.  It is difficult to generalize the results as a result.
		
		Benchmarking any code is difficult.  The process may not have exclusive control over the processor, memory is paged in and out, disk I/O is cached, etc.  The \gls{jvm} complicates matters with \gls{jit} compilation and garbage collection.