\chapter{Experimental Results}
In this chapter we present the experimental results of our implementation and its limitations.


\section{Performance Measurements}
To measure performance of the implementation, we used a slightly modified version of our example application. We introduced \class{PERFORMANCE\hspace{0pt}\_TESTER\hspace{0pt}\_ATM\_UI}, that inherits from \class{ATM\_UI}. It simulates user input by depositing and withdrawing repeatedly (10'000 times in our tests) an amount from a bank account. For the measurements, all classes were observed by default, only the classes \class{ATM}, \class{PERFORMANCE\_TESTER\_ATM\_UI}, \class{CONSOLE} and \class{STD\_FILES} were unobserved.

We tested different scenarios for this application:

\begin{description}
 \item [Capture Phase] Running the application in capture mode.
 \item [Capture Phase - no events] All classes are in the observed set, capture mode is enabled.
 \item [Replay Phase] Running the application in replay mode, based on the log that was generated during the capture phase with regular observed and unobserved sets.
 \item [Capture and Replay Disabled] Running the application with disabled capture and replay.
 \item [Uninstrumented] Running the application without instrumentation, with no capture and replay management code involved.
\end{description}


\subsection{Execution Times}
The performance of the scenarios was measured using Eiffel Studio's built-in profiler, the results are in \tabref{tbl:execution_times}. The results show a significant increase in execution time, compared to the uninstrumented version; about 1000 times slower for the capture phase and more than 3000 times slower for the replay phase.\\
When comparing the two capture phase scenarios we can see that the generated events double the execution time. Therefore it is important to choose the boundaries between observed and unobserved set carefully. \\
The execution times show that the instrumentation code has an effect even when disabled, when comparing the scenarios \identifier{uninstrumented} and \identifier{capture and replay disabled}. The three additional \identifier{if} statements in each routine slow down the execution by the factor ten.

\begin{center}
 \begin{table}
	\begin{tabular}[ht]{|l|l|} 
	\hline
	\textbf{Setup} & \textbf{Total Execution Time} \\ \hline
	Uninstrumented & 0.5s \\ \hline 
	Capture and Replay Disabled & 4s \\ \hline
	Capture Phase & 9m \\ \hline
	Capture Phase - no events & 4m 25s \\ \hline
	Replay Phase & 27m 50s \\ \hline
	\end{tabular}
 \caption{Total Execution times of the Tested Setups}
 \label{tbl:execution_times}
 \end{table} 
\end{center}

\subsection{Possible Optimizations for the Capture Phase}
In the following we will discuss how the performance can be optimized for the capture phase. Improving the performance is more important for the capture phase than the replay phase, because ideally developers should enable capturing whenever they are testing an application, which is only realistic, if the performance is acceptable. \tabref{tbl:profiler_capture_phase} shows an excerpt of the profiler output for the capture phase.

\begin{table}[htbp]
\begin{tabular}{|l|r|r|r|}
\hline
\textbf{Feature} & \textbf{Calls} & \textbf{total time [s]} & \textbf{time [\%]} \\ \hline
RECORDER.enter & 1890359 & 0.88 & 0.16 \\ \hline
RECORDER.leave & 760147 & 0.38 & 0.07 \\ \hline
RECORDER.observed\_stack\_item & 760146 & 1.3 & 0.24 \\ \hline
RECORDER.put\_feature\_exit & 80019 & 52.32 & 9.74 \\ \hline
RECORDER.put\_feature\_invocation & 80019 & 198.95 & 37.05 \\ \hline
RECORDER.put\_to\_observed\_stack & 380073 & 0.76 & 0.14 \\ \hline
RECORDER.remove\_from\_observed\_stack & 380074 & 0.71 & 0.13 \\ \hline
TEXT\_SERIALIZER.basic\_types & 210041 & 0.08 & 0.01 \\ \hline
TEXT\_SERIALIZER.is\_basic\_type & 210041 & 61.71 & 11.49 \\ \hline
TEXT\_SERIALIZER.print\_debug & 770172 & 6.46 & 1.2 \\ \hline
TEXT\_SERIALIZER.program\_flow\_sink & 7711689 & 3.14 & 0.58 \\ \hline
TEXT\_SERIALIZER.write & 610134 & 13.78 & 2.57 \\ \hline
TEXT\_SERIALIZER.write\_arguments & 80019 & 73.78 & 13.74 \\ \hline
TEXT\_SERIALIZER.write\_basic & 40009 & 12.67 & 2.36 \\ \hline
TEXT\_SERIALIZER.write\_call & 80019 & 177.1 & 32.98 \\ \hline
TEXT\_SERIALIZER.write\_endline & 160038 & 8.64 & 1.61 \\ \hline
TEXT\_SERIALIZER.write\_incall & 80018 & 180.64 & 33.64 \\ \hline
TEXT\_SERIALIZER.write\_incallret & 80018 & 51.98 & 9.68 \\ \hline
TEXT\_SERIALIZER.write\_non\_basic & 170032 & 117.67 & 21.91 \\ \hline
TEXT\_SERIALIZER.write\_object & 210041 & 195.02 & 36.31 \\ \hline
TEXT\_SERIALIZER.write\_return & 80019 & 48.26 & 8.99 \\ \hline
UNOBSERVED\_SET.has\_class\_name & 1130212 & 191.32 & 35.63 \\ \hline
UNOBSERVED\_SET.has\_object & 1130212 & 260.87 & 48.58 \\ \hline
UNOBSERVED\_SET.program\_flow\_sink & 6781275 & 2.78 & 0.52 \\ \hline
\end{tabular}
\caption{Excerpt from the Profiler Output for the Capture Phase}
\label{tbl:profiler_capture_phase}
\end{table}


\subsubsection{The feature is\_observed}
During capture phase, more than 48\% of the time is spent in the feature \feature{has\_object} of class \class{UNOBSERVED\_SET}, which is called from \class{\{ANY\}}\feature{is\_observed}. As written in the section about this feature (\sectref{lbl:is_observed}), this implementation needs to be replaced by a better-performing, which should save at least 48\% execution time, because the execution of the feature \feature{is\_observed} itself,which uses the class \class{UNOBSERVED\_SET}  is not included in the 48\%.

\subsubsection{The class TEXT\_SERIALIZER}
Another big amount of time (43\%) is spent in the class \class{TEXT\_SERIALIZER}, which writes the events to the event log. This class can be further optimized by reducing the number of strings it allocates and optimizing the feature \feature{is\_basic\_type}, which takes 10\% of the overall time. This feature is implemented highly inefficient by using a look up table to determine whether the class name represents a basic type.\\
The time spent in \class{TEXT\_SERIALIZER} is proportional to the number of events that occur, in our example 160000. The number of generated events depends on the choice of observed and unobserved set. In our example two classes that communicate frequently, \class{BANK} and \class{ATM}, are divided by the boundary between observed and unobserved set, therefore many events are generated. A wise choice of observed and unobserved set together with a faster implementation of \class{TEXT\_SERIALIZER} will result in a significantly better performance.


\subsection {Possible Optimizations for the Replay Phase}
Not every time an application is captured, it will be replayed, too. In our use cases, an application will only be replayed when running a test or when trying to find a bug. Therefore optimizing the replay of applications is not as urgent as for the capture phase. Nonetheless we will point out some parts that slow down the replay of applications, based on the profiler output for the replay phase (\tabref{tbl:profile_replay}).


\begin{table}[htbp]
\begin{tabular}{|l|r|r|r|}
\hline
\textbf{Feature} & \textbf{Calls} & \textbf{total time [s]} & \textbf{time [\%]} \\ \hline
ERL\_CALLER.call & 80018 & 1650.2 & 98.92 \\ \hline
EVENT\_INPUT.read\_next\_event & 160039 & 1064 & 63.78 \\ \hline
PLAYER.consume\_event & 160039 & 1066.38 & 63.92 \\ \hline
PLAYER.handle\_incall\_event & 80018 & 1666.09 & 99.87 \\ \hline
PLAYER.play & 1 & 1668.26 & 100 \\ \hline
PLAYER.put\_feature\_exit & 80019 & 857.37 & 51.39 \\ \hline
PLAYER.put\_feature\_invocation & 80019 & 265.88 & 15.94 \\ \hline
PLAYER.set\_error\_status\_for\_call & 80019 & 26.56 & 1.59 \\ \hline
PLAYER.simulate\_unobserved\_body & 2 & 1668.26 & 100 \\ \hline
TEXT\_EVENT\_PARSER.consume & 790161 & 70.96 & 4.25 \\ \hline
TEXT\_EVENT\_PARSER.end\_of\_line & 2750567 & 23.76 & 1.42 \\ \hline
TEXT\_EVENT\_PARSER.item & 4600939 & 89.51 & 5.37 \\ \hline
TEXT\_EVENT\_PARSER.matches & 700151 & 61.88 & 3.71 \\ \hline
TEXT\_EVENT\_PARSER.parse\_event & 160039 & 1062.22 & 63.67 \\ \hline
TEXT\_EVENT\_PARSER.parse\_line & 160038 & 789.16 & 47.3 \\ \hline
TEXT\_EVENT\_PARSER.parse\_non\_basic & 170032 & 429.9 & 25.77 \\ \hline
TEXT\_EVENT\_PARSER.program\_flow\_sink & 42038769 & 16.76 & 1 \\ \hline
UNOBSERVED\_SET.has\_object & 1400263 & 295.3 & 17.7 \\ \hline
FUNCTION.call\_from\_cr\_management\_code & 40007 & 938.06 & 56.23 \\ \hline
FUNCTION.fast\_item & 40007 & 937.36 & 56.19 \\ \hline
PROCEDURE.call\_from\_cr\_management\_code & 40011 & 493.26 & 29.57 \\ \hline
PROCEDURE.fast\_call & 200049 & 496.91 & 29.79 \\ \hline
SPECIAL.copy\_data & 3690774 & 47.83 & 2.87 \\ \hline
ERL\_CLASS\_IMP\_BANK.feature\_ & 100014 & 18.35 & 1.1 \\ \hline
ERL\_CLASS\_IMP\_BANK.immediate\_feature & 100014 & 17.37 & 1.04 \\ \hline
ERL\_UNIVERSE\_IMP.class\_by\_name & 980228 & 128.07 & 7.68 \\ \hline
ERL\_UNIVERSE\_IMP.class\_by\_object & 80018 & 18.79 & 1.13 \\ \hline
ROOT\_CLASS.make & 1 & 1668.27 & 100 \\ \hline
\end{tabular}
\caption{Excerpt from the Profiler Output for the Replay Phase}
\label{tbl:profile_replay}
\end{table}


\subsubsection{The class TEXT\_EVENT\_PARSER}
More than 63\% of the time is spent in the class \class{TEXT\_EVENT\_PARSER} for parsing the events in feature \feature{parse\_event}. The parser was not optimized and heavily uses string processing, which is further slowed down by the instrumentation code. Because the parser is a \emph{recursive descent parser} \cite{aho86}, it frequently executes routine calls, as each symbol of the grammar is parsed in an own routine. By not instrumenting the \class{TEXT\_EVENT\_PARSER} it will be possible to make calls faster and thus speed up the parsing. With a more efficient implementation which minimizes the usage of strings, this will result in a significant performance improvement.

\subsubsection{The class ERL\_UNIVERSE\_IMP}
The class \class{ERL\_UNIVERSE\_IMP} returns the reflection class for a given object or object name. Our implementation uses it in the class \class{ERL\_CALLER} to find the reflection classes in order to replay INCALL events on objects, using the feature \feature{class\_by\_object} of \class{ERL\_UNIVERSE\_IMP}. Our test case triggers about 80'000 INCALL events, each resulting in a lookup for the reflection class during replay phase, using about 1\% of the total execution time. Due to the implementation of the reflection library, calling a routine can result in the lookup of the reflection classes of the target's ancestors. This is necessary, because each reflection class is only able to call the features that were implemented in the corresponding class; for the routines implemented in its ancestors, the reflection classes of the ancestors are used to call them. This approach results in the heavy usage of the feature \feature{class\_by\_name}  with 980'000 calls and more than 7.5\% of the execution time.

Native reflection support in Eiffel will certainly implement the features for calling routines more efficiently, which will result in a faster execution of the replay.


\subsection{Comparison with the Results of SCARPE}
In their paper about SCARPE, a tool for selective capture and replay for Java \cite{orso05may}, Joshi and Orso present efficiency measurements for their implementation, using \identifier{JABA} (Java Architecture for Bytecode Analysis) as target application. Depending on the analysis that \identifier{JABA} needed to perform, the authors measured an overhead between 3\% and 877\% for the capture phase.

SCARPE instruments statically in most cases, it determines whether an instruction leads to a boundary crossing event based on the static type. When choosing the observed set wisely, this allows large parts of the application to run without any performance penalty, which is the reason why applications instrumented with SCARPE have such a low overhead, at most about 900\% whereas our implementation has an overhead of 100'000\%. As we discussed earlier, such a static instrumentation is not realistic for Eiffel, because it would strongly limit the choice for the observed set.

 With a more efficient implementation, the overhead of our approach can be at least halved and by choosing the observed set in a way that minimizes the number of generated events, the overhead should drop further. But with the current instrumentation it will not be possible to reach the efficiency of SCARPE. Instrumentation of only one of the two parts of the application (either observed set or unobserved set), as presented in \sectref{lbl:single-sided_instrumentation}, promises to significantly raise the efficiency, because in that way, the uninstrumented set will execute without any overhead. When minimizing the instrumented set, the largest part of the application will be executed without overhead, which will result in a very efficient execution.

\section{Contribution}
The main parts of our technique were taken from the Java implementation of selective capture and replay from Joshi and Orso \cite{orso05may}, however there are some aspects that differ from their implementation and are to the best of our knowledge new:

\begin{itemize}
\item Our implementation of selective capture and replay targets Eiffel as a language.
\item We instrument applications in a way, so that the same executable can be used for both capture and replay phase. This makes it possible to replay an application immediately after it was captured, without recompiling it, which would take tens of minutes up to hours in Eiffel.
\item Our technique instruments code at the callee side, whereas Joshi and Orso instrument code at the caller side. 
\item Our instrumentation code determines whether an object is observed or unobserved dynamically, and we proposed a solution to do this check with only a small performance overhead. This enables equal instrumentation in all cases of inheritance, fully supporting dynamic binding. 
\end {itemize}

\section {Limitations}
Because of its limitations, the implementation that was made during this master thesis is to be seen as a proof of concept, only a small subset of programs can be captured and replayed. Here, we will provide a list of the known limitations:

\paragraph{Field Accesses}
The fact that there exists no automated code instrumentation for field accesses, limits the use of this implementation; however it has a weaker impact than it would have in Java, because in Eiffel, OUTREAD is the only type of field access that must be recorded in order to capture and replay an application. As a consequence of this limitation, only classes that don't read from unobserved fields can be put into the observed set.

\paragraph{Manifest Strings}
Manifest strings are directly initialized by the C code, that creates a string object and then directly writes the content of the manifest string into that object. Unlike the creation of the object, which is done using normal Eiffel routines, the initialization is directly done by the C code. This implies, that there is no instrumentation code invoked that could notice the change of the object's state.\\
If an observed manifest string created in unobserved code and then passed to observed code, this leads to a fault during replay, because no event is generated and the initialization of the string can not be replayed. By inserting manual instrumentation using \texttt{\{SPECIAL\}.note\_direct\_manipulation}, it is possible to solve this issue. However this solution is not satisfying as manifest strings are used in many places and requiring the developer to insert manual instrumentation in each of these places is not realistic. A better solution would be to change the C macros that are used by the generated code to create manifest strings, in order to invoke the management code whenever a manifest string is instantiated.

\paragraph{Selective Exports}
In Eiffel, a mechanism called \emph{selective exports} \cite{oosc2} lets classes decide, to which classes their features are exported. This mechanism can be seen as a generalization of Javas \emph{access level modifiers}. The problem arises whenever an observed class lets an unobserved class access a feature \identifier{f}, but prohibits the capture and replay management classes, especially class \class{CALLER}, from access to \identifier{f}. This leads to the situation where the event log contains an INCALL to the restricted feature, but \class{CALLER} is unable to call that feature during replay. A special case of selective exports are creation routines, that are often exported to \class{NONE} in order to restrict their usage exclusively to creation calls like \inlineeiffel{create foo.creation\_procedure}, which does not care about export restrictions.

The case of restricted creation procedures can be solved by treating them specially and only calling them in context of object creation. The reflection library generated by Erl-G already makes this distinction and can be used in order to replay them correctly. However, this only solves a part of the problem, all other cases of restricted access are not addressed by this solution. The only reasonable possibility to address all problems that come with selective exports, is a native reflection support in Eiffel with the option to ignore access restrictions. Native reflection support would improve the compile times of capture and replay enabled applications significantly, by not doubling the amount of classes and not making all classes part of the system. For a wider applicable implementation of selective capture and replay, native reflection support is indispensable.

\paragraph{Language Features}
At the moment only a subset of the Eiffel language features is supported. In the following we will present a list of missing features:

\begin{description}
 \item [Pre- and Postconditions] In Eiffel it is possible to add to every routine a pre- and a postcondition. The precondition, initiated by the \keyword{require} keyword, defines what the caller of the routine must ensure in order to safely call the routine. The postcondition, initiated by the \keyword{ensure} keyword, defines what the routine ensures after execution under the assumption that the precondition was met. The developer can activate the checking of these conditions, which results in a check of the precondition before and postcondition after every routine execution.\\
 Pre- and postcondition consist of a sequence of boolean Eiffel expressions, that contain function calls and attribute accesses. Thus when checking pre- and postconditions during application execution, additional events for selective capture and replay are triggered.\\
The technique must ensure that these function calls and attribute accesses do not take place during the replay phase if they are executed in the context of a unobserved routine, because it is required that unobserved code is not executed during replay phase. \\
Furthermore it is desirable that these events are all triggered in the context of the routine the corresponding pre- and postcondition belongs to. This implies, that the instrumentation code for routine invocation must be executed before the precondition is checked and the instrumentation code for routine exit is executed after the last postcondition is checked. Otherwise the events triggered by the assertion code is executed in the context of the caller.\\
At the moment selective capture and replay for Eiffel only works when checking of pre- and postconditions is disabled.

 \item [Class Invariants] In contrast to pre- and postconditions that express the properties of a routine, class invariants, which are initiated by the \keyword{invariant} keyword, express properties of a class. Like pre- and postconditions of routines, invariants are a sequence of boolean Eiffel expressions. They need to hold before and after all exported routines; an exception to that rule are creation procedures that establish the invariant, therefore the class invariant generally does not hold before the execution of a creation procedure.\\
The checking of the invariants can be enabled by the developer, according to the Eiffel ECMA standard \cite{Eiffel-ECMA}, they are then checked before and after every qualified routine call. As with pre- and postconditions of routines, this causes additional events during capture and replay phase, which is especially problematic for unobserved classes, which should not execute any code during replay phase. At the moment selective capture and replay for Eiffel only works with disabled invariant checking.

 \item [Exceptions] The original implementation of selective capture and replay creates an event whenever exceptions are thrown across the boundary. The current implementation for Eiffel ignores exceptions, which can cause an incorrect replay of the application, as exceptions have an impact on program flow. %Man koennte evtl. das default_rescue instrumentieren, um Exceptions einfach detektieren, allerdings muessten zusaetzlich auch alle rescue-clauses so instrumentiert werden, damit festgestellt werden kann, ob die routine eine Exception wirft --> keine einfache Sache!

 \item [Expanded Types] Variables of expanded type contain the object in contrast to regular variables that contain a reference to the object. Assigning a variable of expanded type to another variable (expanded or not) results in copying the object.\\
Expanded types were not incorporated in the implementation of selective capture and replay for Eiffel. In general, integrating support for expanded types is no problem, but there is one thing that must be considered: it is not possible to change an expanded object in another scope than the one it is defined in, because it is not possible to reference an expanded object. Therefore it is not possible to change an expanded object originated from application code in the management code. This makes the proposed solution for OUTREAD events, modifying the target object from management code before it is accessed, inapplicable for expanded objects. One solution to this problem is to change a copy of the expanded object and assign that copy back to the original object.

 \item [Agents] Eiffel agents make it possible to wrap routines in objects. The current implementation of selective capture and replay for Eiffel has no support for agents.

 \item [Once Routines] Once routines are routines that use the \keyword{once} keyword instead of the \keyword{do} keyword. As the name suggests, once routines are executed once, at least in single-threaded applications and if no special once key is defined (consult the Eiffel ECMA standard \cite{Eiffel-ECMA} for details).\\
The current implementation does not instrument once routines, hence they are not supported. When adding support for once routines, unobserved once routines must be treated specially, because it is possible that the first call of the once routine does not come from observed code. The technique must store the result nonetheless, because it is possible that a later call will come from observed code. Therefore the first call to once function must initialize its result correctly, because any subsequent call will return the same result.
\end{description}

\paragraph{Object IDs}
In the current implementation, object IDs are not supported for instances of class \class{TUPLE}. This was discovered a while after they were developed and is caused by the irregular object layout that instances of class \class{TUPLE} have. It is possible that there are some more special cases left, although with \class{SPECIAL} and \class{TUPLE}, the usual suspects are treated.

When an object is copied using the feature \feature{copy}, its object ID is copied, too. The correct behaviour in this case would be to request a new ID, because original and copy are two different objects and should therefore also have their own ID.

Another flaw regarding object IDs is that Eiffel's storable mechanism is not yet supported by the runtime with object ID support. Most probably this is also the reason, why Eiffel Studio using the modified runtime does not work properly.

\paragraph{Multi-Threading}
Selective capture and replay was not tested with a multi-threaded application, and some things were not designed with multi-threading in mind. One thing that certainly must be fixed in order to support multi-threading is the global counter for object IDs, which must be accessed using a mutex in order to avoid two objects, created by two threads, to have the same object ID.

When the whole management code is made thread safe, our implementation will still have the same limitation as SCARPE; it is required that multi-threading does not introduce any non determinism to the observed code.

\paragraph{Supported Compiler Backends}
At the moment, only frozen workbench code is supported, although most parts, like the automatically inserted instrumentation code also should work for other compiler backends, as they're implemented in pure Eiffel.
