\chapter{Generating Parallel Code}\label{generatingparallecode}
The JStar compiler provides several compiler flags to configure the code generation. The most important flags are the
sequential and parallel flags, which determine the kind of data structures used in the Gamma set and the Delta Tree.
Using non-thread-safe data structures in the parallel programs not only affects its performance, but causes the race
conditions, or using locks incorrectly can lead to the deadlock. Thus, this chapter introduces the compiler flags and
the performance of different data structures. In addition, we explore the optimization options of JStar compiler for
improving the performance of JStar programs.
\section{Sequential (-seq flag) versus Parallel Code (-par flag)}
The Delta tree and the Gamma database are the two main tuple storages during the execution of a JStar program. When a
new tuple is created by the rule, it is not processed immediately by the JStar runtime but queued in Delta tree in the
defined order. After the JStar runtime removes a tuple from the Delta tree, it inserts this tuple into the table in
Gamma, and triggers all of its associated rules. When the JStar runtime executes the rules, it may make queries into
the Gamma tables and return the query result. The result contains an iterable object, so that the rule can use a 
\emph{for} statement to traverse each tuples of the resulting set.
\par The \texttt{Fork/Join} framework is selected to execute the JStar programs in parallel because it provides a good
match for the semantics of the Delta tree. To be able to execute tasks concurrently, we want to have the only one thread
to traverse all the Delta nodes in the tree, and then the other threads to process the tasks on the behalf of the Delta
nodes. Besides, by recursively breaking down the size of tuples that needs to process at each iteration, the Fork/Join
framework can improve the efficiency of the JStar runtime: the working threads in the ForkJoinPool can split large tasks
into smaller tasks, and the available threads which have finished their tasks can run the tasks from other busy threads.
The work stealing strategy used in the Fork/Join framework can reduce the overhead costs of creating new threads and
improve the utilization of the existing threads in the pool.
\subsection{Tuple Lifecycle}
\begin{figure}[h]
 \centering
 \includegraphics[width=0.25\textwidth]{./jstarcompiler/figure/LifeCycleOfTuple.eps}
 \caption[The lifecycle of a JStar tuple.]{The lifecycle of a JStar tuple.}
\label{fig:LifecycleOfTuple}
\end{figure}
The lifecycle of a tuple has five phases:
\phase{Created}, \phase{Queued}, \phase{Processed}, \phase{Stored} and \phase{Retired}
(Figure~\ref{fig:LifecycleOfTuple}) After a tuple is created and put into the Delta tree, its status is moved from the
\phase{Created} phase to the \phase{Queued} phase. In the \phase{Queued} phase, the tuples are queued in different or
the same level of the Delta tree, and waiting for their turn to be processed by the JStar runtime. The JStar runtime
takes a set of \emph{minimal} tuples from the Delta tree and executes these tuples in parallel, using the Fork/Join
framework. When this tuple is removed from the Delta tree, it is moved to the \phase{Processed} phase.
\par In \phase{Processed} phase, the JStar runtime uses this tuple to trigger and execute its applicable rules, and then
inserts it to its own table in the Gamma database. Those tuples in the Gamma table are kept until the end of the
program, and could be queried by other rules. When one rule needs some tuples, it makes a query request to the table in
the Gamma database. After receiving the request, the JStar runtime calls the corresponding query method with the values,
which are parsed from the request. The query results are returned as a \emph{SortedSet} object, so that the rule can
iterate through each tuple in the collection. These queried tuples are in \phase{Stored} phase. At the end of the
program or when a tuple will never be queried again, the tuples enters the \phase{Retired} phase. The Java garbage
collector can reclaim the retired tuples.
\subsection{Optimisations}
\begin{figure}[h]
\centering
\subfloat[\flag{noDelta} optimization.]{
	\includegraphics[width=0.25\textwidth]{./jstarcompiler/figure/LifeCycleOfTuple.noDelta.eps}
	\label{fig:lifecycleoftuplenodelta}
}\quad
\subfloat[\flag{noGamma} optimization.]{
	\includegraphics[width=0.25\textwidth]{./jstarcompiler/figure/LifeCycleOfTuple.noGamma.eps}
	\label{fig:lifecycleoftuplenoGamma}
}\quad
\subfloat[\flag{noDelta} and \flag{noGamma} optimizations.]{
	\includegraphics[width=0.25\textwidth]{./jstarcompiler/figure/LifeCycleOfTuple.noDelta.noGamma.eps}
	\label{fig:lifecycleoftuplenodeltanoGamma}
}
\caption[The lifecyle of a JStar tuple with three optimisations.]
{The lifecyle graphs of a JStar tuple inlined with three optimisations.}
\label{fig:LifecycleOfTupleOptimisation}
\end{figure}
The optimisation strategies include noDelta and noGamma options. Applying \flag{noDelta} optimisation on a specific
tuple kind can omit the Delta tree insertion. Thus, instead of entering the \phase{Queued} phase, a \flag{noDelta} tuple
is move to the \phase{Processed} phase immediately after the \phase{Created} phase (Figure
~\ref{fig:LifecycleOfTupleOptimisation}~\subref{fig:lifecycleoftuplenodelta}). Similarly, the \flag{noGamma} option
omits the \phase{Stored} phase. As shown in the
Figure~\ref{fig:LifecycleOfTupleOptimisation}~\subref{fig:lifecycleoftuplenoGamma}, those tuple applied with \flag{noGamma}
option enters the \phase{Retired} phase after the \phase{Processed} phase. The details of optimisation strategies will
be described in Section~\ref{section:optimisation}.
\subsection{Code Generation}
The JStar compiler can generate different kinds of implementation with the parallelism compiler flag and two
optimization strategies. The parallelism flag of the JStar compiler is to specify what kind of data structures that
the JStar compiler should use to create data storage during execution. When the JStar compiler is given the 
\flag{-seq} flag, it uses the non-synchronized \class{TreeSet} class to create the tables in Gamma database and the primitive
DeltaNode implementations to create Delta node in Delta tree. If the compiler generates Java code with 
\flag{-par} flag, it uses \class{ConcurrentSkipListSet} class to construct the Gamma table and the parallel version of
the DeltaNode implementations to build up the Delta Tree.
\par The sequential version of a JStar program implements the Gamma database and the Delta Tree with primitive Java
collection classes:\class{TreeSet} and \class{DeltaNode}. The advantages of these data structures is that they provide
the guaranteed \texttt{log(n)} time cost for the basic operations (add, remove and contains). Thus, inserting a tuple
to the Delta tree or adding it to the Gamma database does not cause a long delay as the number of tuples increases. But
these two classes are not synchronized. If \class{TreeSet} or \class{DeltaNode} is accessed by multiple threads without
the external data synchronization, it would cause race conditions and possible data corruption.
\par The parallel version of a JStar program uses \class{ConcurrentSkipListSet} and \class{ParallelDeltaNode} as the
data structures for the Gamma database and the Delta tree respectively. The basic operations for these two collection
classes take the \texttt{log(n)} time on average and the operations are guaranteed to be executed atomically.
\section[Speed of the Gamma Database]{Speed of the Gamma Database: PvWattsGamma Results}
The JStar PvWattsGamma program is a testing program to understand the JStar system and provide a way of measuring the
performance of the JStar implementation. This example generates 16 million PvWatts tuples in total and inserts each one
of them to the table in Gamma database, and then ends the program. To measure the execution time of Gamma
database, PvWattsGamma program must be compiled with \phase{noDelta} optimisation on PvWatts tuples. Besides, JStar
PvWattsGamma program generates PvWatts tuples with a number of parallel tasks, which each of them has its own number
range to produce a set of date time values for each PvWatts tuple.
Thus, the key values of any PvWatts tuple is unique in the whole Gamma table so that the Gamma table does not filter
out any tuple whose key values are the same as existing one. The source code is listed in Listing~\ref{sourcecodeofpvwattsgamm}.
\begin{spacing}{1.0}
\begin{lstlisting}[label=sourcecodeofpvwattsgamm,caption=Source Code of the JStar PvWattsGamma Program.]
package jstar.examples.pvwattsgamma;
/**
 * This program measures the time taken to insert a given number of tuples
 * into the Gamma set.
 * To measure Gamma speed only, it should be compiled with -noDelta PvWatts.
 * Arguments: --threads=1 --benchmark=12 NNN
 * (NNN is the number of GenTuple tasks)
*/
val TOTAL_TUPLES = 16000000;
table PvWatts(
    int year, int month, int day, String time, int watts)
    orderby (PvWatts)
    inv 1000 < year && 1 <= month && month <= 12 && 1 <= day && day <= 31;
table CmdLineArg(int index, String value)
    orderby (CmdLineArgs)
    inv 0 <= index;
/**
 * A request to generate tuples: from (inclusive) .. to (exclusive)
 */
table GenTuples(int index, int from, int to)
    orderby (GenTuples)
    inv 0 <= index;
order CmdLineArgs < GenTuples < PvWatts < Int;
foreach (CmdLineArg arg) {
    val num = Integer::parseInt(arg.value);
    for (i : 0 .. num-1) {
        val from = TOTAL_TUPLES / num * i;
        val to = TOTAL_TUPLES / num * (i + 1);
        put new GenTuples(i, from, to)
    }
}
foreach (GenTuples gt) {    
    val time = "group" + gt.index;
    for (v : gt.from .. gt.to - 1) {
        val year = 1980 + (v % 9);
        val month = v % 12 + 1;
        val day = (v * 3) % 32;
        put new PvWatts(year, month, day, time, v)
    }
}
\end{lstlisting}
\end{spacing}
\par In the PvWattsGamma example, all PvWatts tuple are inserted into the same Delta tree, and then moved to the PvWatts table in
Gamma database. Because of the large number of PvWatts, insertion and query operation on Gamma database  take up
most of the total execution time, and result in a bottleneck and limit the speedup. Therefore, we need to have an
efficient Gamma database to improve the performance of JStar PvWatts program.
\subsection{The Gamma Table Data Structure Choices}
The performance of a Gamma database depends on its table implementation, which uses \class{NavigableSet} interface. Thus,
the data structure choice for each table affects the performance of overall Gamma database. As described in
previous section, the table implemented from different kinds of data structures has different insertion time and query
time. This section explores several JAVA collection classes and choose an appropriate data structure for the Gamma
database.
\begin{description}
  \item [TreeSet] is implemented from \class{NavigableSet} interface, which is a sorted set and provides several subset methods
  that are very useful for potential key queries.\cite{JDK7API} A new tuple is added to the Treeset if and only if it
  has not been present before. The nature orderings is used to determine whether a new tuple is equal to the existing
  tuples in a TreeSet.
  If PvWatts tuple are inserted to the TreeSet, then they are first sorted by their year field, then by the month, and
  then by the remaining primary key fields (from the left to the right).
  \item [ConcurrentSkipListSet] is the concurrent implementation of \class{NavigableSet} class.\cite{JDK7API} Like
  the TreeSet, PvWatts tuples in this set are sorted with their natural ordering. The Insertion, removal and query
  operation of the PvWatts tuples can be executed by multiple threads without causing any Thread-safe issue. Although
  the \class{size} method cause delay in operation as it needs to iterate through all tuples in the set.
  \item [HashMap] is a Hash table based on \class{Map} interface.\cite{JDK7API} It takes a constant time to insert a new
  tuple and retrieval an existing tuple from its table. Through its \method{Hash} function, the retrieval of tuples in a
  \class{HashMap} is similar to an array.
  \begin{figure}[h!]
	\centering
	\includegraphics[width=0.8\textwidth]{./jstarcompiler/figure/HashMap}
	\caption{The \class{HashMap} insertion behaviour diagram.}
	\label{fig:HashMapGraph}
  \end{figure}
  For example, PvWatts tuples can be keys in a HashMap with the \keyword{Boolean.True} being used as the value
  (Figure~\ref{fig:HashMapGraph}). It is also possible to use the \class{HashSet} class directly, but not all of the
  \class{Map} classes in the Java library have the \class{Set} equivalents. So we prefer to consistently use the 
  \class{Map} implementations when generating parallel code. When a new PvWatts tuple is put into a \class{HashMap},
  the \method{Hash} function finds an index in the array and then places it in the \keyword{Key} set. Instead of
  iterating all elements in the set, the array index provides an easy and direct way of accessing a tuple. But if there
  are the queries that return a subset of the table, the \class{HashMap} iteration time is proportional to its total
  number of elements, so a \class{HashMap} is unlikely to be a good choice of data structure in this case. If there are
  too many elements, the total searching time could be increased and thus the overall performance would be degraded.
  Besides, another factor which affects the performance of the \class{HashMap} is the initial capacity. When a large
  number of tuples are inserted into a small-sized \class{HashMap}, it will frequently spend the time resizing its table
  and therefore its performance will be slowed down. Like \class{TreeSet}, \class{HashMap} is also not thread-safe, so
  they are only suitable for sequential situation.
  \par The performance of a \class{HashMap} depends on two factors: \keyword{initial capacity} and \keyword{load factor}. The
  initial capacity is to set up the estimated size of a \class{HashMap} instance. The load factor determines how full the
  \class{HashMap} instance should be before its capacity is increased. For example, the PvWatts table is created with
  8 million initial capacity and 0.75 load factor. That is, the capacity threshold is 6 ($8 \times 0.75$) million
  tuples. When the total number of tuples in the PvWatts table exceeds this threshold, then the \class{HashMap} has
  to double its bucket size (16 million) to accept more insertion requests. Resizing a \class{HashMap} requires
  rebuilding its internal data structure, and thus causes a delay in execution time.
  \item [ConcurrentHashMap] is implemented from \class{HashMap}.\cite{JDK7API} Its retrival and update operations act
  like \class{HashMap} but provide the thread-safety. That is, \class{ConcurrentHashMap} can be accessed by multiple
  threads at the same time and still behaves correctly, but allow finer-grained concurrent access than \class{HashMap}.
  \item [ConcurrentHashMapV8] is developed by JSR-166.\cite{website:JSR-166} Its goal is to improve the
  \class{ConcurrentHashMap} class and provide higher efficiency and low memory usage. And its implementation obeys the
   method specifications of \class{HashMap}.
\end{description}
\subsection{The \class{PvWattsHashTable} Gamma Table}
The JStar built-in Gamma table implements the \class{NavigableSet} interface. Those classes based on the
\class{Map} interface can not be directly used to create a PvWatts Gamma table. The \class{PvWattsHashTable} class is
written as a container to make use of all the \class{Map} implementations. It uses an array of \class{Map} instances, 
each \class{Map} instance storing the PvWatts tuples of one month. For example, the first Map instance whose array index
is 0 stores the invalid tuples. The second one (index=1) retains the tuples whose month field is January, and followed
by February, March, and so on. To measure the effects of \keyword{initial capacity} on the performance, the
\class{PvWattsHashTable} constructor can initialize each Map instance with a specific capacity value. If the capacity
is not set or the Map implementation does not support to an initial capacity, the Map instance is constructed with the
default configuration. Besides, this array is implemented using the \class{AtomicReferenceArray} so that the
\class{PvWattsHashTable} can be guaranteed to be thread-safe and each Map instance can be read or written atomically.
\subsection{Benchmark Result of the Sequential Tuple Insertion}
Benchmarking the PvWattsGamma program requires several JStar runtime flags, including \flag{table}, \flag{debug},
\flag{benchmark} and \flag{threads}. The \flag{table} flag takes a string which contains the property settings of a
table and each property is separated by a comma. The program arguments in the following list are one example of the
PvWattsGamma benchmarks.
\begin{lstlisting}[label=pvwattsgammaarguments, caption=The Benchmarking Program Arguments.]
--table,GenTuples,group=1
--table,PvWatts,estimated=16000000,gamma=ConcurrentHashMap
--benchmark=30 --threads=4 24
\end{lstlisting}
The first argument means that each \class{GenTuples} will be treated as a separate task rather than several tuple being
grouped into one group. This is the optimal setting for this program because each \class{GenTuple} triggers a rule that
does quite a lot of work, so it is best handled as a separate task.
The second \flag{table} flag specifies \class{ConcurrentHashMap} as the data structure of the PvWatts table in Gamma.
And the initial capacity of PvWatts table is set to be 8 million. The \flag{benchmark} flag specifies the number of
repeated experiments. The \flag{Threads} flag creates 4 threads in the thread pool. The number \flag{24} means that
JStar runtime creates 24 GenTuples separate tasks.
% \begin{description}
% \item [The Sequential JStar PvWattsGamma Program]\hfill \\
\begin{figure}[h!]
\centering
\subfloat[Total execution time with varying initial capacity.]
{
\includegraphics[width=0.95\textwidth]{./jstarcompiler/figure/SEQ.PvWattsGamma.Time.eps}
\label{fig:SEQPvWattsGammaTime}
}\quad
\subfloat[Speedup with varying initial capacity.]{
\includegraphics[width=0.95\textwidth]{./jstarcompiler/figure/SEQ.PvWattsGamma.Speedup.eps}
\label{fig:SEQPvWattsGammaSpeedup}
}
\caption[Performance of inserting tuples in sequential into the Gamma table.]
{Performance of inserting 16 million PvWatts tuples in sequential into the Gamma table with three data
structures and varying the initial capacity on dual-CPU Intel Xeon W5590 @ 3.33GHz (total of 8 cores.)}
\label{fig:SEQPvWattsGamma}
\end{figure}
\par Figure~\ref{fig:SEQPvWattsGamma} shows that the performance of the sequential version of the JStar PvWattsGamma program.
The JStar PvWattsGamma program is compiled with the \flag{-seq} flag to generate the Java code and use both of the
synchronized and non-synchronized Java collection classes, such as the \class{HashMap}. The experiment creates the Gamma
PvWatts table with different kinds of data structures, including \class{HashMap}, \class{ConcurrentHashMap} and
\class{ConcurrentHashMapV8}.
\par To realize the effect of resizing the capacity on the performance of a data structure, the
experiment vary the initial capacity from 0 to 16 million at seven levels:
\begin{inparaenum}[\itshape i\upshape)]
\item 0(default),
\item 1 million,
\item 2 million,
\item 4 million,
\item 8 million,
\item 12 million,
\item and 16 million.
\end{inparaenum}
Each experiment is repeated 30 times. The average execution time skips the first 6 runs and averages the remaining
ones (from 7th to 30th). The speedup measures how many times faster than the average time of default capacity
(initial capacity = 0) for each data structure.
%\FloatBarrier
\par Figure~\ref{fig:SEQPvWattsGamma}\subref{fig:SEQPvWattsGammaTime} shows that \class{ConcurrentHashMapV8} has the
shortest total execution time at most initial capacity, except for the default value and 16 million. The
\class{HasMap} outperforms the other two data structures at the default value, and the \class{ConcurrentHashMap} has the
shortest running time at the 16 million. The speedup graph is shown in Figure~\ref{fig:SEQPvWattsGamma}\subref{fig:SEQPvWattsGammaSpeedup}.
The \class{ConcurrentHashMapV8} achieves the maximal speedup of 3.22 when the initial capacity is 4 million, but the
speedup decreases as the capacity increases from 4 million to 16 million. The speedup of \class{ConcurrentHashMap} has
the second best results, with the maximal speed of 2.36 at 8 million. Similarly, the speedup decreases from 8 million
to 16 million. The \class{HashMap} has the poorest speedup of 1.1 only when the initial capacity is 1 million, and
does not have any improvement on the speed at the other levels. This speedup illustrates that the resizing capacity
can affect the performance both on the \class{ConcurrentHashMap} and the \class{ConcurrentHashMapV8} but makes a little
change to the \class{HashMap}.
\par The effect of resizing capacity may cause the bias on the benchmarking results, so a suitable capacity for all the
\class{Map} based data structures is needed to avoid this resizing effect. From the Figure~\ref{fig:SEQPvWattsGamma},
the total execution time and the speedup of the \class{ConcurrentHashMapV8} are approximately close to those of the
\class{ConcurrentHashMap} at both of 12 million and 16 million. The \class{HashMap} also has nearly the same total
execution time and speedups at these two levels. Therefore, to fairly compare the performance of these three
\class{Map} implementations and avoid the resizing effect, the appropriate initial capacity should be either
12 million or 16 million. That is, when the \textbf{12} or \textbf{16 million} is used as the initial capacity for the PvWatts
table in the Gamma database, the \class{HashMap}, \class{ConcurrentHashMap} and \class{ConcurrentHashMapV8} will have
the stable performance.
% \item [The Parallel JStar PvWattsGamma Program]
\subsection{Benchmark Result of the Parallel Tuple Insertion}
\begin{figure}[h!]
\centering
\subfloat[Total execution time with varying Fork/Join pool size.]{
\includegraphics[width=0.95\textwidth]{./jstarcompiler/figure/PAR.PvWattsGamma.Time.eps}
\label{fig:PARPvWattsGammaTime}
}\quad
\subfloat[Speedup with varying Fork/Join pool size.]{
\includegraphics[width=0.95\textwidth]{./jstarcompiler/figure/PAR.PvWattsGamma.Speedup.eps}
\label{fig:PARPvWattsGammaSpeedup}
}
\caption[Performance of inserting tuples in parallel into the Gamma table.]
{Performance of inserting 16 million PvWatts tuples in parallel into the Gamma table with three data structures and
varying the Fork/Join pool size on dual-CPU Intel Xeon W5590 @ 3.33GHz (total of 8 cores.).}
\label{fig:PARPvWattsGamma}
\end{figure}
The benchmarking experiment for the parallel version of JStar PvWattsGamma program uses three kinds of concurrent
data structures (that is,\linebreak
\class{ConcurrentSkipListSet}, \class{ConcurrentHashMap} and \class{ConcurrentHashMapV8}), and
vary the number of threads in the pool for each one of the structures. From the benchmarking results of the sequential
PvWattsGamma programs, the parallel experiment uses 16 million as the fixed initial capacity for both of the
\class{ConcurrentHashMap} and the \class{ConcurrentHashMapV8}. The \class{HashMap} is not included in this experiments
because it requires the external synchronization to be used in the mult-threading environment.
\par The Figure~\ref{fig:PARPvWattsGamma}\subref{fig:PARPvWattsGammaTime} shows that the \class{ConcurrentHashMap}
outperforms both of the \class{ConcurrentHashMapV8} and the \class{ConcurrentSkipListSet} on the total execution time
and the speedup. When the number of threads increases, the total execution time of \class{ConcurrentHashMap} decreases
and achieves the shortest time with 8 threads. Followed by the \class{ConcurrentHashMapV8}, the
\class{ConcurrentSkipListSet} has the longest time from 1 to 8 threads. Therefore, With the initial capacity of 16
million, the \class{ConcurrentHashMap} is the fastest data structure for the PvWatts Gamma table. And its running time
can be regarded as the baseline to obtain the speedups for the parallel JStar PvWattsGamma program.
\par Figure~\ref{fig:PARPvWattsGamma}\subref{fig:PARPvWattsGammaSpeedup} is the absolute speedup graph, related to
the single-threaded time of the \class{ConcurrentHashMap}. It shows that the performance of \\
\class{ConcurrentHashMap} and \class{ConcurrentHashMapV8} can be scaled from 1 thread upto 8 threads whereas the
\class{ConcurrentSkipListSet} is scalable upto 7 threads. We conclude that the \class{ConcurrentHashMap} with the
initial capacity of 16 million and within the \class{PvWattsHashTable} is the best choice of concurrent data structure
for implementing the tables in Gamma database.
(It would have been better to do these experiments from 8 to 15 threads
if possible. Maybe \class{ConcurrentHashMapV8} has the better scalability with more threads.)
\section{Speed of the Delta Tree}
The insertion time into the Delta tree is an important factor to consider for the Delta tree data structure . As each
tuple needs to be inserted into this tree, longer insertion times will cause a delay in processing tuples and thus
increase the total execution time. Currently the Delta tree is implemented as a tree structure with fixed depth.
The \keyword{orderby} clause in the \keyword{Table} statements of a JStar program defines the tree depth and
the order of tuples.
\par The JStar Dijkstra program is used to measure the speed of Delta tree data structures. The detailed program will be
discussed in Chapter~\ref{ch:Dijkstra}. This program first generates a random graph of 1 million vertices connected with
2 million edges where each edge is assigned with a random length ranging from 1 to 10. Then it uses the
\keyword{Dijkstra} algorithm to find the shortest path from the root node (vertex=0) to the end node (vertex=1,000,000).
This program uses 7 kinds of tuples, but there is only one tuple kind inserting into the Delta tree after the
optimisation. Therefore, using this program to measure the speed of the Delta tree is more accurate than other JStar
programs. The Delta tuple is declared in the follows:
\begin{lstlisting}
    /** The estimated shortest-path distance from the origin to the given vertex. */
	table Estimate(int vertex, int distance) orderby (Int, seq distance, Estimate);
\end{lstlisting}
\par The Delta tree behaves like the \class{priority queue} in this test case. The \class{Estimate} tuples are inserted
into the Delta tree at the position in accordance with the \keyword{distance}, which is what we need in the JStar
Dijkstra program - a priority queue ordered by distance from the starting vertex.
The \class{Estimate} with the smallest \keyword{distance} value will be put in front of all the others. When the JStar
runtime takes out the tuples from the Delta tree, it will firstly process the root node (distance=0) and then spans all
the other nodes.
The \keyword{seq distance} expression defines their position in a subtree of the Delta tree: the tuple with the small
distance will be placed before the one with the large distance.
As the tuples in the front position will be processed earlier than those in the back, the \keyword{orderby} clause can
ensure that the distance of the \class{Estimate} tuple in the Delta tree acts like the \keyword{priority} and turns the
Delta tree into a \keyword{priority queue}.
Note that a sorting flag, the \flag{par} $e$ expression, allows tuples to be unsorted in the subtree, and thus the delta
subtree can be executed in parallel.
\subsection{The \class{DeltaNode} Data Structure Choices}
The performance of the Delta tree in the JStar Dijkstra program is determined by the \class{Estimate} Delta nodes,
which belong to the \class{Integer} data type. Three kinds of \class{Integer} Delta tree data structures have been
implemented in the JStar runtime, as described in the follows:
\begin{description}
  \item [DeltaNodeInt] is the sequential implementation of the nodes of the Delta tree. It stores the Delta nodes with a
  Java \class{TreeMap<Integer,DeltaNode>}, which is indexed by the integer field. For example, the \class{Estimate}
  tuple uses the \keyword{distance} field as its index, and thus the subtrees in the \class{DeltaNodeInt} are also
  indexed by the \keyword{distance}. When a \class{Estimate} tuple is inserted into the \class{DeltaNodeInt} node, the
  JStar runtime checks this tuple's distance and determines whether a subtree has been created in the TreeMap. If so,
  then the runtime inserts this tuple to the existing subtree. Otherwise, a new subtree is created and put into this
  \class{TreeMap} with the tuple's distance as the key.
  \par The \method{process} method of the \class{DeltaNodeInt} retrieves and processes the first Delta node from the
  \class{TreeMap}, and then removes the node from the \class{TreeMap}. In the JStar Dijkstra program, the first delta
  node in the \class{DeltaNodeInt} is the \class{Estimate} tuple which has the shortest distance among the others.
  \item [ParallelDeltaNodeInt] is the parallel Delta node implementation, which stores the Delta nodes with a Java
  \class{ConcurrentSkipListMap<Integer,DeltaNode>}. Its insertion and processing behaviors are similar to those of the
  \class{DeltaNodeInt}, except that it uses the thread-safe \method{putIfAbsent} method to put a subtree into its data
  storage.
  \item [ParallelDeltaNodeIntRange] is another parallel Delta node implementation, which stores the Delta nodes with a
  Java \class{AtomicReferenceArray}. 
\end{description}
\subsection{Benchmark Result}
The benchmarking experiment measures the total execution times of the JStar Dijkstra program, varying the data
structures for the Delta tree. As the \class{DeltaNodeInt} is not thread safe, we use its result as the baseline to
calculate the speeds for the two parallel Delta node implementations in a multi-core machine. As shown in
Section~\ref{sec:deltatreebenchmarks}, benchmark results on a dual-CPU Intel Xeon E5-2680 (total of 16 cores) show that
\class{ParallelDeltaNodeInt} reaches the absolute speedup of 6.37 and \class{ParallelDeltaNodeIntRange} has the
absolute speedup of 4.67 with 15 threads. We conclude that \class{ParallelDeltaNodeInt} has a slightly better
performance than \allowbreak \class{ParallelDeltaNodeIntRange}.
\section{Optimisation Strategy}\label{section:optimisation}
Tuples have different roles in a JStar program. In the PvWattsGamma example, \class{CmdLineArg} tuples are considered as
the trigger-only tuples. Their role is to pass the information from command line arguments to JStar PvWattsGamma. As
the \class{CmdLineArg} table in the Gamma database is never queried by other rules, there is no need to move 
the \class{CmdLineArg} tuples from the Delta tree to the table in Gamma. On the other hand, PvWatts tuples should be
moved into the Gamma set directly without needing any Delta tree insertion, because the \class{PvWatts} tuples do not
trigger any rule in this example. The current version of JStar compiler supports two kinds of optimization strategy:
\flag{noDelta} and \flag{noGamma}.
\subsection{\flag{noDelta} Optimisation}
The \flag{noDelta} optimisation usage is to run the JStar compiler with the \flag{-noDelta T} flag to translate a JStar
program to Java source code. For example, translating the PvWattsGamma JStar program with the \flag{-noDelta PvWatts}
flag will generate the Java code, which puts each of the \class{PvWatts} tuples to the table in the Gamma database and
immediately fires any rules that use it as the input.\cite{Utting:2013:JLP:2442992.2442996}
\par After the JStar runtime parses the program arguments, it labels the \class{PvWatts} as one of the tuple kinds whose
Delta tree insertion should be omitted. When the JStar compiler translates the statements which inserts the
\class{PvWatts} tuples into Delta tree, the compiler will replace the statement, which inserts the \class{PvWatts} to
the Delta tree, with the direct-processing statement. So then the JStar runtime executes PvWatts tuples directly instead
of putting them into the Delta tree and being executed later.
\par The advantages of the \flag{noDelta} optimisation is that it reduces the total number of Delta nodes in the Delta
tree and improves the speedup. This faster speedup results from the less workload of Delta tree and faster response
time of the comparison operation.
As the Delta tree contains the smaller number of Delta nodes, the JStar runtime spends less time on traversing each
level of the Delta nodes and searching for each new tuple. Thus, the total execution time is shortened. 
This improvement becomes more significant when one table greatly outnumbers the others in a program. For example, the
PvWattsGamma program generates over 16 million of \class{PvWatts} tuples in total. Applying the \flag{noDelta} flag on
the \class{PvWatts} tuples avoids the insertion of all \class{PvWatts} Delta nodes and reduces the total number of
tuples in the Delta tree from millions to 24 (the total number of \class{GenTuples}).
\par The effect the \flag{noDelta} optimisation is shown on the sequential JStar PvWattsGamma program. The speedup is
to measure how much the JStar program with \flag{noDelta} flag runs faster than the native one. Each program was run 30
times. The results of first 6 runs are ignored because of the JVM HotSpot warm-up and the remaining ones are take
to calculate the averaged execution time. The benchmark result reaches the 1.4X speedup with the \flag{noDelta} flag
on the sequential JStar PvWatts program.
\subsection{\flag{noGamma} Optimisation}
The \flag{noGamma} optimisation usage is similar to the \flag{noDelta} option. That is, compiling a JStar program with
\flag{-noGamma T} flag can generate the Java code, which omit the insertion of tuples from table T into Gamma.\cite{Utting:2013:JLP:2442992.2442996}
\par Consider the Dijkstra case, which finds the shortest path for the single-source graph and will be described in
Chapter~\ref{ch:Dijkstra}. The \class{Estimate} tuples should be applied with \flag{noGamma} optimisation as they are
never been queried by other rules. With the \flag{noGamma} optimisation, the JStar runtime can also reduce the time
processing the \class{Estimate} tuples. Before applying the \flag{noGamma} optimisation, the JStar runtime has to take
two actions for each \class{Estimate} tuple: moving the tuple to the Gamma database and executing the next rule. After
compiling the program with \flag{noGamma Estimate} flag, the generated Java source code is optimized to directly
trigger the rule associated with the \class{Estimate} tuple without any insertion in Gamma when the JStar runtime
processes each \class{Estimate} delta node from the Delta tree.
\par The benchmark experiments measure the total execution of the sequential JStar Dijkstra program with/without the
\flag{noGamma} optimisation.
The benchmark results on the Intel(R) Xeon(R) CPU W5590 (total of 8 cores) shows that the speedup is 1.6X. That is, the
sequential JStar Dijkstra program with the \flag{noGamma Estimate} optimisation can run 1.6 times faster than its native
implementation.
\section{Summary}
\begin{table}[h!]
\centering
\begin{tabularx}{1.0\textwidth}{|l|X|X|}
\toprule
\textbf{Compiler Flag} & \textbf{Description} & \textbf{Example of Usage}\\
\midrule
Output Folder&specifies the output folder where JStar compiler generates the Java source code.
& \flag{-d} $<folder>$\\\hline
Verbose Mode&details the process of JStar compilation. & \flag{-v}\\\hline
Sequential Code&generates sequential code and uses the \textbf{non-synchronized} data structure.&
\flag{-seq}\\\hline
Parallel Code&generates parallel code and uses \textbf{concurrent} data structure.&
\flag{-par}\\\hline
noDelta Optimisation&generates the Java code, which omit the insertion of the Delta tree.& 
\flag{-noDelta} $<tuple>$\\\hline
noGamma Optimisation&generates the Java code, which omit the insertion of the Gamma database.& \flag{-noGamma} $<tuple>$\\
\bottomrule
\end{tabularx}
\caption{The JStar compiler option list.}
\label{tab:JStarCompilerFlag}
\end{table}
% Table~\ref{tab:JStarCompilerFlag} lists new JStar compiler options to assist JStar programmers to apply optimisations
% to a JStar program.
\cleardoublepage