
\chapter{Results}
\label{chap:results}

This chapter sums up results of the experiments performed as part of this diploma thesis.

First set of experiments is related to studying performance and potential of scheduler
algorithm described in the \hyperref[chap:scheduler]{Scheduler chapter}. For these
experiments simulation, which tries to mimic real-world scenarios, is used.

The second set of experiments is studying performance and behavior of the program static
analysis introduced in the \hyperref[chap:compiler]{Interpreter chapter}. For these
experiments, some real programs, written in the proposed programming language, are used.

\section{Performance of the scheduler}

To measure performance more precisely, real scheduler's implementation was used for
scheduling randomly generated list of messages. Processing of each message was set up to
take a specific number of milliseconds. Messages from the list are being sent to the
scheduler in the specified interval. To compare the impact of a different number of
workers and different scheduler types, the specific number of messages were fed to the
scheduler and total processing time of all messages was measured.

\subsection*{Message generation}

The scheduler operates on the system with \( |Vars| \) variables. Processing of each
generated message for the simulation reads and writes some of these variables.

The probability that processing of the message reads or writes \( x \) variables is following:
\begin{equation}
  p = \frac{1}{\sqrt{2 \pi |Vars|}}e^{-\frac{(x - \frac{|Vars|}{2})^2}{2 |Vars|}}
\end{equation}

This probability is computed based on the Gaussian distribution, as was discussed in the
\hyperref[chap:scheduler]{Scheduler chapter}. Point of choosing such complicated probability
function is to simulate the real-world behavior as precisely as possible.

\subsection*{Processing time of the message}

When \( |M_R| \) and \( |M_W| \) denotes the number of randomly chosen variables that
are read and written during message processing, following equation specify the duration
of simulated processing in milliseconds:
\begin{equation}
  t = 2 \cdot max\{1, |M_R|\}  + 4 \cdot max\{1, |M_W|\}
\end{equation}
Therefore, it means that writing is more expensive operation than reading, that also
mimics real-world behavior. Thanks to this, the simulation may be more precise.

\subsection*{Comparison tables}

Simulation described above was run with different parameters - variables count, workers
count (\textit{N}) and scheduler type. Following tables are comparing total simulation time.
All simulations with the same variables count were run over the same messages sequence.
Therefore any random anomalies across simulation runs are not present. All simulations
were run on the system with \textbf{one CPU with four cores}.

The tables are showing total \textit{processing time} in milliseconds for the simulation
runs with the different parameters. Smaller \textit{processing time} values means better
performance. The tables contain a \textit{performance gain} information, which compares
specific scheduler's processing time with the processing time of the scheduler with just
one worker, i.e., sequential scheduler. Higher \textit{performance gain} means the better
performance of the particular scheduler.

From the results, it seems that performance gain is stable and does not depend on the
number of processed messages. Using two workers instead of just one has increased
performance gain significantly. However, adding more workers does not have such significant
impact. Impact of more workers is even decreased when variables count is increased.

\begin{table}[H]
  \begin{tabular}{| C{2.5cm} | C{1cm} | C{3.75cm} | C{3.75cm} |}
    \hline
    \textbf{Type} & \textbf{N} & \textbf{Processing time} & \textbf{Performance gain} \\ \hline

    Sequential & 1 &
      5 variables - 9495 \newline 10 variables - 15459 \newline 20 variables - 29592 &
      reference values \\ \hline

    Read-write locking & 2 &
      5 variables - 5699 \newline 10 variables - 10942 \newline 20 variables - 24223 &
      5 variables - 39.53\% \newline 10 variables - 29.22\% \newline 20 variables - 18.14\% \\ \hline

    Read-write locking & 4 &
      5 variables - 4970 \newline 10 variables - 10329 \newline 20 variables - 23824 &
      5 variables - 47.26\% \newline 10 variables - 33.18\% \newline 20 variables - 19.49\% \\ \hline

    Write locking & 2 &
      5 variables - 5288 \newline 10 variables - 9115 \newline 20 variables - 19970 &
      5 variables - 43.89\% \newline 10 variables - 41.04\% \newline 20 variables - 32.52\% \\ \hline

    Write locking & 4 &
      5 variables - 4301 \newline 10 variables - 8131 \newline 20 variables - 19365 &
      5 variables - 54.36\% \newline 10 variables - 47.40\% \newline 20 variables - 34.56\% \\ \hline
  \end{tabular}
  \caption{Comparison table for processing 1000 messages}
\end{table}

\begin{table}[H]
  \begin{tabular}{| C{2.5cm} | C{1cm} | C{3.75cm} | C{3.75cm} |}
    \hline
    \textbf{Type} & \textbf{N} & \textbf{Processing time} & \textbf{Performance gain} \\ \hline

    Sequential & 1 &
      5 variables - 46868 \newline 10 variables - 77173 \newline 20 variables - 148457 &
      reference values \\ \hline

    Read-write locking & 2 &
      5 variables - 28085 \newline 10 variables - 53137 \newline 20 variables - 118816 &
      5 variables - 40.08\% \newline 10 variables - 31.15\% \newline 20 variables - 19.97\% \\ \hline

    Read-write locking & 4 &
      5 variables - 24634 \newline 10 variables - 50242 \newline 20 variables - 117840 &
      5 variables - 47.44\% \newline 10 variables - 34.90\% \newline 20 variables - 20.62\% \\ \hline

    Write locking & 2 &
      5 variables - 25777 \newline 10 variables - 46015 \newline 20 variables - 97542 &
      5 variables - 45.00\% \newline 10 variables - 40.37\% \newline 20 variables - 34.30\% \\ \hline

    Write locking & 4 &
      5 variables - 21248 \newline 10 variables - 41014 \newline 20 variables - 94227 &
      5 variables - 54.66\% \newline 10 variables - 46.85\% \newline 20 variables - 36.53\% \\ \hline
  \end{tabular}
  \caption{Comparison table for processing 5000 messages}
\end{table}

\begin{table}[H]
  \begin{tabular}{| C{2.5cm} | C{1cm} | C{3.75cm} | C{3.75cm} |}
    \hline
    \textbf{Type} & \textbf{N} & \textbf{Processing time} & \textbf{Performance gain} \\ \hline

    Sequential & 1 &
      5 variables - 93813 \newline 10 variables - 155388 \newline 20 variables - 297084 &
      reference values \\ \hline

    Read-write locking & 2 &
      5 variables - 55823 \newline 10 variables - 105807 \newline 20 variables - 236148 &
      5 variables - 40.49\% \newline 10 variables - 31.91\% \newline 20 variables - 20.51\% \\ \hline

    Read-write locking & 4 &
      5 variables - 49031 \newline 10 variables - 100972 \newline 20 variables - 233787 &
      5 variables - 47.74\% \newline 10 variables - 35.02\% \newline 20 variables - 21.31\% \\ \hline

    Write locking & 2 &
      5 variables - 51554 \newline 10 variables - 90769 \newline 20 variables - 194338 &
      5 variables - 45.05\% \newline 10 variables - 41.59\% \newline 20 variables - 34.58\% \\ \hline

    Write locking & 4 &
      5 variables - 42016 \newline 10 variables - 81417 \newline 20 variables - 185631 &
      5 variables - 55.21\% \newline 10 variables - 47.60\% \newline 20 variables - 37.52\% \\ \hline
  \end{tabular}
  \caption{Comparison table for processing 10000 messages}
\end{table}

According to the results, \textit{read-write} scheduler has worse performance than
scheduler which utilize only \textit{write} locking. This is expected behavior, but
in real programs, this difference might vanish because of added cloning overhead. As
stated in the \hyperref[chap:scheduler]{Scheduler chapter} state cloning has to performed
only for the \textit{write} locking scheduler.

To sum up, the performance of the scheduler, based on this simulation, seems to be promising.
Based on these results it looks like message-driven programs executed by the proposed scheduler
can exhibit significant performance improvement. However, this is still a theoretical simulation.
More realistic results are provided in the next sections, where real programs are studied.

\section{Accuracy of the static code analyzer}

To make the parallelization process automatic, it is necessary to automatically extract
boolean expressions for each global variable used in the program. This extraction is
performed by the static code analyzer described in the \hyperref[chap:compiler]{Interpreter chapter}.
This analyzer cannot always extract side-effect free boolean expressions. For such cases,
analyzer assumes that given variable is always read or written. This section shows some
general instances in which the extraction is or isn't entirely possible.

\subsection*{Simple message-dependent conditions}

Very often, processing type that program has to perform entirely depends on the data
carried by the message. Example of such program follows:

\begin{figure}[H]
  \begin{lstlisting}
  def main(msg)
      local.test = _eq(local.msg, "type1")
      if local.test
          global.type1data = "data"
      else
          global.type2Data = "otherData"
      end
  end
  \end{lstlisting}
  \caption{Example of the code using message-dependent conditions}
\end{figure}

For this program, it is expected that static analyzer will generate boolean expressions
that distinguish between the message of type \textit{"type1"} and of another type. Such
expressions were really correctly generated for the \textit{type1data} and \textit{type2data}
variables. In lisp notation:

\begin{figure}[H]
  \begin{lstlisting}
  type1data: (<_and> true (<_eq> local.msg "type1"))
  type2Data: (<_and> true (<_neg> (<_eq> local.msg "type1")))
  \end{lstlisting}
  \caption{Boolean expressions generated for the message-dependent conditions}
\end{figure}

\subsection*{Side-effect free, recursive call dependent conditions}

Programs often declare some utility functions that check some condition about retrieved
message data. This condition can be quite complicated, even recursive. Provided that
this condition check function does not read or write any global variables (i.e., is
side-effect free) it is also analyzable by the implemented static analyzer. Following
program shows usage of this feature:

\begin{figure}[H]
  \begin{lstlisting}
  def check(str, ch, index)
      # Code that can recursively call 'check'
      # function but cannot read or write any
      # global variable (or call function that does).
  end
  def main(msg)
      local.test = check(local.msg, 'g', 0)
      if local.test
          global.type1data = "data"
      else
          global.type2Data = "otherData"
      end
      return local.msg
  end
  \end{lstlisting}
  \caption{Example of the code using side-effect free, recursive call dependent conditions}
\end{figure}

Boolean expressions generated for this code can freely use the \textit{check} function
because it has no side effects. The implemented static code analyzer generates such expressions:

\begin{figure}[H]
  \begin{lstlisting}
  type1data: (<_and> true (<check> local.msg 'g' 0))
  type2Data: (<_and> true (<_neg> (<check> local.msg 'g' 0)))
  \end{lstlisting}
  \caption{Boolean expressions generated for the side-effect free, recursive call dependent conditions}
\end{figure}

\subsection*{Global variable dependent conditions}

Limitation of the implemented message-driven parallelization approach is the fact that
parallelization decision has to be based only on the message data. If the boolean
expression needs data from the global state, the scheduler cannot use this expression.
The global state may be used by the worker, so reading the data from it is generally
dangerous. Therefore, programs that contain such conditions have to be detected, and
the condition has to be rewritten to be always \textbf{true}. Example of such program:

\begin{figure}[H]
  \begin{lstlisting}
  def check(data)
    local.test = _eq(local.data, global.data)
    return local.test
  end
  def main(msg)
      local.test = check(local.msg)
      if local.test
          global.type1data = "data"
      else
          global.type2Data = "otherData"
      end
      return local.msg
  end
  \end{lstlisting}
  \caption{Example of the code using global variable dependent conditions}
\end{figure}

For this code, it was correctly identified that global variables' conditions depend
on the global variable, even though dependency is indirect through the function call.
Identified boolean expressions for the variables are following:

\begin{figure}[H]
  \begin{lstlisting}
  type1data: true
  type2Data: true
  \end{lstlisting}
  \caption{Boolean expressions generated for the global variable dependent conditions}
\end{figure}

\subsection*{Recursive side-effect function dependent conditions}

Another limitation of the static code analysis is a dependency on the recursive functions
that are reading or writing some global variables. If the result of the boolean expression
is found to use the return value of such function, whole value of the expression has to be
treated as always \textbf{true}. Example of the code that is analyzed this way is following:

\begin{figure}[H]
  \begin{lstlisting}
  def check(data, index)
      local.test = _eq(local.index, 0)
      if local.test
          return false
      end
      local.n = _add(local.index, global.n)
      local.test = check(local.data, local.n)
      return local.test
  end
  def main(msg)
      local.test = check(local.msg, 5)
      if local.test
          global.type1data = "data"
      else
          global.type2Data = "otherData"
      end
      return local.msg
  end
  \end{lstlisting}
  \caption{Example of the code using recursive side-effect function dependent conditions}
\end{figure}

For this code analyzer correctly identified that the \textit{check} function is the
problematic one, because it reads \textit{global.n} variable. Final boolean expressions
for the \textit{type1data} and \textit{type2data} variables are, therefore, always \textbf{true}:

\begin{figure}[H]
  \begin{lstlisting}
  type1data: true
  type2Data: true
  \end{lstlisting}
  \caption{Boolean expressions generated for the recursive side-effect function dependent conditions}
\end{figure}

\section{Performance of a scheduled processing by an interpreted code}

To measure scheduler's performance impact on real-world applications, interpretation of the
real code is considered. This code was written in the programming language proposed in the
\hyperref[chap:compiler]{Interpreter chapter}. Static code analysis, also described in the
previous chapter, was performed on the code to find out influenced global variables.

Experiments for two different programs were performed as part of this diploma thesis.
Both experiments consist of several steps:
\begin{enumerate}
  \item Parsing the program code written in the programming language introduced in the
  \hyperref[chap:compiler]{Interpreter chapter}.

  \item Analyzing the parsed AST with the static code analyzer described in the
  \hyperref[chap:compiler]{Interpreter chapter}.

  \item Starting the scheduler, which was proposed in the \hyperref[chap:scheduler]{Scheduler chapter},
  with \( N \) workers. Workers are set-up to interpret the parsed code. The scheduler is set-up
  to use boolean expressions provided by the static code analyzer to determine locked global variables.

  \item Schedule messages periodically over time period of \( T \) seconds. Messages are
  generated individually for each of the studied applications.
\end{enumerate}

During the experiment execution, statistics about the number of processed messages
are gathered. The performance impact of the scheduler can be determined based on the statistics.

Following sections describe programs and their messages, sum up the results of the
scheduler's performance impact, and discuss precision of the static code analyzer.

\subsection{Server-client application}

This application simulates the server-client behavior of the simple database system.
Such systems typically store and retrieve data from tables, or collections, or generally,
so-called, \textit{storage buckets}. In many use cases of such systems, the retrieve
requests are more frequent and sophisticated than the store requests.

The created implementation simulates the mentioned behavior in the following way:
\begin{enumerate}
  \item Maintains \textbf{4} \textit{storage buckets} in separate global variables.
  In the real application there might be real persistent data structures under these
  variables, for this simulation just empty strings are used and reads/writes are
  simulated by busy waiting.

  \item Can process \textit{read messages} that can inform program to retrieve data from 1, 2, 3 or 4
  \textit{storage buckets} at once. Reading one \textit{storage bucket} is simulated to take \textit{10 milliseconds}.

  \item Can process \textit{write messages} that can inform program to store data to one of the
  \textit{storage buckets}. This processing is simulated to take \textit{50 milliseconds}.
\end{enumerate}

Implementation code is included in this diploma thesis (see appendix~\ref{appendix:code_server}).
The code is written in the way that incoming message completely determines which \textit{storage buckets}
will be used during processing. Therefore, static code analyzer managed to correctly create
boolean expressions (see chapter~\ref{chap:compiler}) for each global variable.

Simulation of the application load is performed by the following message generation process:
\begin{enumerate}
  \item Every \textit{10 milliseconds} message that reads from \textbf{1} randomly chosen \textit{storage bucket}
  is generated and scheduled.

  \item Every \textit{20 milliseconds} message that reads from \textbf{2} randomly chosen \textit{storage buckets}
  is generated and scheduled.

  \item Every \textit{30 milliseconds} message that reads from all \textit{storage buckets} is generated and scheduled.

  \item Every \textit{50 milliseconds} message that writes to \textbf{1} randomly chosen \textit{storage bucket}
  is generated and scheduled.
\end{enumerate}

The described simulation was performed using the scheduler \textit{with} read variables
locking. Results of two simulation runs, for a different duration, are presented in the following tables:

\begin{table}[H]
  \begin{tabular}{| C{2.5cm} | C{6cm} | C{2.5cm} |}
    \hline
    \textbf{Workers count} & \textbf{Average processed messages count per second} & \textbf{Performance gain} \\ \hline

    1 & 45.56 & reference value \\ \hline

    2 & 80.9 & 77.57\% \\ \hline

    4 & 93.66 & 105.58\% \\ \hline
  \end{tabular}
  \caption{Server-Client application results table for a 50 seconds simulation}
\end{table}

\begin{table}[H]
  \begin{tabular}{| C{2.5cm} | C{6cm} | C{2.5cm} |}
    \hline
    \textbf{Workers count} & \textbf{Average processed messages count per second} & \textbf{Performance gain} \\ \hline

    1 & 43.99 & reference value \\ \hline

    2 & 79.51 & 80.75\% \\ \hline

    4 & 96.89 & 120.25\% \\ \hline
  \end{tabular}
  \caption{Server-Client application results table for a 100 seconds simulation}
\end{table}

The results show that performance gain is stable and does not depend on the length of the
simulation. Also, adding more workers increases the performance of the system. The performance
gain will stabilize at some number of workers - based on the number of \textit{storage buckets}
and mainly the number of processors available on a test machine. Simulations were run on the
test machine with a dual-core processor with a hyper-threading feature, i.e., it had,
theoretically, four processor cores.

\subsection{Graphical user interface application}

This application simulates the behavior of the graphical user interface (GUI) program.
The primary task of these programs is to render the interface and respond to the user
events such as a mouse move and mouse clicks. They also, typically, parse some data and
show them in the graphical interface.

The experimental implementation simulates this behavior with the following process:
\begin{enumerate}
  \item Maintains \textit{GUI state} under one global variable. In real applications,
  there will be complex data structure under this variable or even more global variables.
  For this simulation, just one global variable is used.

  \item Maintains \textit{data} and \textit{real-time data} under two separate global variables.
  In real applications, there will be complex data structure under these variables.
  For this simulation, just simple counters are used.

  \item Can process \textit{gui update messages} that inform the program to update the GUI state.
  Processing of this message is instant, i.e., without any busy waiting simulation.

  \item Can process \textit{data update messages} that inform the program to update the \textit{data}
  variable. This update is simulated by busy waiting that lasts \textit{50 milliseconds}.

  \item Can process \textit{real-time data update messages} that inform the program to update the \textit{real-time data}
  variable. This update is simulated by busy waiting that lasts \textit{10 milliseconds}.

  \item Can process \textit{render messages} that inform the program to render whole application.
  Rendering reads all global variables in the system. Rendering is simulated by busy waiting that
  lasts \textit{10 milliseconds}.
\end{enumerate}

Implementation code is included in this diploma thesis (see appendix~\ref{appendix:code_gui}).
Static code analyzer managed to correctly identify which global variables are read and written
by any of the messages.

Simulation of the application load is performed by the following message generation process:
\begin{enumerate}
  \item Every \textit{1 millisecond} message that updates \textit{GUI state} is generated
  and scheduled.

  \item Every \textit{500 milliseconds} message that updates \textit{data global variable} is generated
  and scheduled.

  \item Every \textit{50 milliseconds} message that updates \textit{real-time data global variable} is generated
  and scheduled.

  \item Every \textit{16 milliseconds} message that causes rendering of the graphical user interface is generated
  and scheduled.
\end{enumerate}

The simulation was performed using the scheduler \textbf{without} read variables locking.
This scheduler is especially suitable for this kind of the applications because of their
relatively small internal state that can be easily cloned. Results of two simulation runs,
that show count of all processed messages and number of processed render messages, are
included in the following tables:

\begin{table}[H]
  \begin{tabular}{| C{2cm} | C{6cm} | C{3.5cm} |}
    \hline
    \textbf{Workers count} & \textbf{Average processed messages count per second} & \textbf{Performance gain} \\ \hline

    1 &
     all - 495.94 \newline render - 30.42 &
     reference values \\ \hline

    2 &
      all - 875.9 \newline render - 57.06 &
      all - 76.61\% \newline render - 87.57\% \\ \hline

    4 &
      all - 978.12 \newline render - 61 &
      all - 97.23\% \newline render - 100.53\% \\ \hline
  \end{tabular}
  \caption{GUI application results table for a 50 seconds simulation}
\end{table}

\begin{table}[H]
  \begin{tabular}{| C{2cm} | C{6cm} | C{3.5cm} |}
    \hline
    \textbf{Workers count} & \textbf{Average processed messages count per second} & \textbf{Performance gain} \\ \hline

    1 &
     all - 501.74 \newline render - 30.72 &
     reference values \\ \hline

    2 &
      all - 864.18 \newline render - 55.51 &
      all - 72.24\% \newline render - 80.7\% \\ \hline

    4 &
      all - 988.32 \newline render - 61.12 &
      all - 96.98\% \newline render - 98.96\% \\ \hline
  \end{tabular}
  \caption{GUI application results table for a 100 seconds simulation}
\end{table}

The results show that performance gain is stable and does not depend on the duration of
the simulation. Adding more workers increased the overall performance. In this experiment,
it was also important to monitor \textit{render messages}. The frequency of these messages
was set to one per \textit{16 milliseconds} because this frequency is needed to get smooth
\textit{60 frames per second (FPS)}. The results show that using \textbf{4} workers helped
to achieve this goal. Only \textbf{1} or \textbf{2} workers were not sufficient to maintain
the smooth FPS.
