source: doc/theses/andrew_beach_MMath/performance.tex @ 25d4e15

jacob/cs343-translation
Last change on this file since 25d4e15 was 25d4e15, checked in by Andrew Beach <ajbeach@…>, 3 months ago

Andrew MMath: That's the rest of the \todo items and everything needed for the initial submission.

  • Property mode set to 100644
File size: 18.9 KB
Line 
1\chapter{Performance}
2\label{c:performance}
3
4Performance is of secondary importance for most of this project.
5Instead, the focus was to get the features working. The only performance
6requirement is to ensure the tests for correctness run in a reasonable
7amount of time. Hence, a few basic performance tests were performed to
8check this requirement.
9
10\section{Test Set-Up}
11Tests were run in \CFA, C++, Java and Python.
12In addition there are two sets of tests for \CFA,
13one with termination and one with resumption.
14
15C++ is the most comparable language because both it and \CFA use the same
16framework, libunwind.
17In fact, the comparison is almost entirely in quality of implementation.
18Specifically, \CFA's EHM has had significantly less time to be optimized and
19does not generate its own assembly. It does have a slight advantage in that
20\Cpp has to do some extra bookkeeping to support its utility functions,
21but otherwise \Cpp should have a significant advantage.
22
23Java, a popular language with similar termination semantics,
24is implemented in a very different environment, a virtual machine with
25garbage collection.
26It also implements the finally clause on try blocks allowing for a direct
27feature-to-feature comparison.
28As with \Cpp, Java's implementation is mature, has more optimizations
29and extra features as compared to \CFA.
30
31Python is used as an alternative comparison because of the \CFA EHM's
32current performance goals, which is to not be prohibitively slow while the
33features are designed and examined. Python has similar performance goals for
34creating quick scripts and its wide use suggests it has achieved those goals.
35
36Unfortunately, there are no notable modern programming languages with
37resumption exceptions. Even the older programming languages with resumption
38seem to be notable only for having resumption.
39Instead, resumption is compared to its simulation in other programming
40languages: fixup functions that are explicitly passed into a function.
41
42All tests are run inside a main loop that repeatedly performs a test.
43This approach avoids start-up or tear-down time from
44affecting the timing results.
45The number of times the loop is run is configurable from the command line;
46the number used in the timing runs is given with the results per test.
47The Java tests run the main loop 1000 times before
48beginning the actual test to ``warm-up" the JVM.
49% All other languages are precompiled or interpreted.
50
51Timing is done internally, with time measured immediately before and
52after the test loop. The difference is calculated and printed.
53The loop structure and internal timing means it is impossible to test
54unhandled exceptions in \Cpp and Java as that would cause the process to
55terminate.
56Luckily, performance on the ``give-up and kill the process" path is not
57critical.
58
59The exceptions used in these tests are always based off of
60the base exception for the language.
61This requirement minimizes performance differences based
62on the object model used to represent the exception.
63
64All tests are designed to be as minimal as possible, while still preventing
65excessive optimizations.
66For example, empty inline assembly blocks are used in \CFA and \Cpp to
67prevent excessive optimizations while adding no actual work.
68
69% We don't use catch-alls but if we did:
70% Catch-alls are done by catching the root exception type (not using \Cpp's
71% \code{C++}{catch(...)}).
72
73When collecting data, each test is run eleven times. The top three and bottom
74three results are discarded and the remaining five values are averaged.
75The test are run with the latest (still pre-release) \CFA compiler,
76using gcc-10 10.3.0 as a backend.
77g++-10 10.3.0 is used for \Cpp.
78Java tests are complied and run with version 11.0.11.
79Python used version 3.8.10.
80The machines used to run the tests are:
81\begin{itemize}[nosep]
82\item ARM 2280 Kunpeng 920 48-core 2$\times$socket
83      \lstinline{@} 2.6 GHz running Linux v5.11.0-25
84\item AMD 6380 Abu Dhabi 16-core 4$\times$socket
85      \lstinline{@} 2.5 GHz running Linux v5.11.0-25
86\end{itemize}
87Representing the two major families of hardware architecture.
88
89\section{Tests}
90The following tests were selected to test the performance of different
91components of the exception system.
92They should provide a guide as to where the EHM's costs are found.
93
94\paragraph{Stack Traversal}
95This group measures the cost of traversing the stack,
96(and in termination, unwinding it).
97Inside the main loop is a call to a recursive function.
98This function calls itself F times before raising an exception.
99F is configurable from the command line, but is usually 100.
100This builds up many stack frames, and any contents they may have,
101before the raise.
102The exception is always handled at the base of the stack.
103For example the Empty test for \CFA resumption looks like:
104\begin{cfa}
105void unwind_empty(unsigned int frames) {
106        if (frames) {
107                unwind_empty(frames - 1);
108        } else {
109                throwResume (empty_exception){&empty_vt};
110        }
111}
112\end{cfa}
113Other test cases have additional code around the recursive call adding
114something besides simple stack frames to the stack.
115Note that both termination and resumption have to traverse over
116the stack but only termination has to unwind it.
117\begin{itemize}[nosep]
118% \item None:
119% Reuses the empty test code (see below) except that the number of frames
120% is set to 0 (this is the only test for which the number of frames is not
121% 100). This isolates the start-up and shut-down time of a throw.
122\item Empty:
123The repeating function is empty except for the necessary control code.
124As other traversal tests add to this, it is the baseline for the group
125as the cost comes from traversing over and unwinding a stack frame
126that has no other interactions with the exception system.
127\item Destructor:
128The repeating function creates an object with a destructor before calling
129itself.
130Comparing this to the empty test gives the time to traverse over and
131unwind a destructor.
132\item Finally:
133The repeating function calls itself inside a try block with a finally clause
134attached.
135Comparing this to the empty test gives the time to traverse over and
136unwind a finally clause.
137\item Other Handler:
138The repeating function calls itself inside a try block with a handler that
139does not match the raised exception, but is of the same kind of handler.
140This means that the EHM has to check each handler, and continue
141over all of them until it reaches the base of the stack.
142Comparing this to the empty test gives the time to traverse over and
143unwind a handler.
144\end{itemize}
145
146\paragraph{Cross Try Statement}
147This group of tests measures the cost for setting up exception handling,
148if it is
149not used (because the exceptional case did not occur).
150Tests repeatedly cross (enter, execute and leave) a try statement but never
151perform a raise.
152\begin{itemize}[nosep]
153\item Handler:
154The try statement has a handler (of the appropriate kind).
155\item Finally:
156The try statement has a finally clause.
157\end{itemize}
158
159\paragraph{Conditional Matching}
160This group measures the cost of conditional matching.
161Only \CFA implements the language level conditional match,
162the other languages mimic it with an ``unconditional" match (it still
163checks the exception's type) and conditional re-raise if it is not supposed
164to handle that exception.
165
166Here is the pattern shown in \CFA and \Cpp. Java and Python use the same
167pattern as \Cpp, but with their own syntax.
168
169\begin{minipage}{0.45\textwidth}
170\begin{cfa}
171try {
172        ...
173} catch (exception_t * e ;
174                should_catch(e)) {
175        ...
176}
177\end{cfa}
178\end{minipage}
179\begin{minipage}{0.55\textwidth}
180\begin{lstlisting}[language=C++]
181try {
182        ...
183} catch (std::exception & e) {
184        if (!should_catch(e)) throw;
185        ...
186}
187\end{lstlisting}
188\end{minipage}
189\begin{itemize}[nosep]
190\item Match All:
191The condition is always true. (Always matches or never re-raises.)
192\item Match None:
193The condition is always false. (Never matches or always re-raises.)
194\end{itemize}
195
196\paragraph{Resumption Simulation}
197A slightly altered version of the Empty Traversal test is used when comparing
198resumption to fix-up routines.
199The handler, the actual resumption handler or the fix-up routine,
200always captures a variable at the base of the loop,
201and receives a reference to a variable at the raise site, either as a
202field on the exception or an argument to the fix-up routine.
203% I don't actually know why that is here but not anywhere else.
204
205%\section{Cost in Size}
206%Using exceptions also has a cost in the size of the executable.
207%Although it is sometimes ignored
208%
209%There is a size cost to defining a personality function but the later problem
210%is the LSDA which will be generated for every function.
211%
212%(I haven't actually figured out how to compare this, probably using something
213%related to -fexceptions.)
214
215\section{Results}
216% First, introduce the tables.
217\autoref{t:PerformanceTermination},
218\autoref{t:PerformanceResumption}
219and~\autoref{t:PerformanceFixupRoutines}
220show the test results.
221In cases where a feature is not supported by a language, the test is skipped
222for that language and the result is marked N/A.
223There are also cases where the feature is supported but measuring its
224cost is impossible. This happened with Java, which uses a JIT that optimize
225away the tests and it cannot be stopped.\cite{Dice21}
226These tests are marked N/C.
227To get results in a consistent range (1 second to 1 minute is ideal,
228going higher is better than going low) N, the number of iterations of the
229main loop in each test, is varied between tests. It is also given in the
230results and has a value in the millions.
231
232An anomaly in some results came from \CFA's use of gcc nested functions.
233These nested functions are used to create closures that can access stack
234variables in their lexical scope.
235However, if they do so, then they can cause the benchmark's run-time to
236increase by an order of magnitude.
237The simplest solution is to make those values global variables instead
238of function local variables.
239% Do we know if editing a global inside nested function is a problem?
240Tests that had to be modified to avoid this problem have been marked
241with a ``*'' in the results.
242
243% Now come the tables themselves:
244% You might need a wider window for this.
245
246\begin{table}[htb]
247\centering
248\caption{Termination Performance Results (sec)}
249\label{t:PerformanceTermination}
250\begin{tabular}{|r|*{2}{|r r r r|}}
251\hline
252                       & \multicolumn{4}{c||}{AMD}         & \multicolumn{4}{c|}{ARM}  \\
253\cline{2-9}
254N\hspace{8pt}          & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
255                         \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
256\hline
257Empty Traversal (1M)   & 3.4   & 2.8   & 18.3  & 23.4      & 3.7   & 3.2   & 15.5  & 14.8  \\
258D'tor Traversal (1M)   & 48.4  & 23.6  & N/A   & N/A       & 64.2  & 29.0  & N/A   & N/A   \\
259Finally Traversal (1M) & 3.4*  & N/A   & 17.9  & 29.0      & 4.1*  & N/A   & 15.6  & 19.0  \\
260Other Traversal (1M)   & 3.6*  & 23.2  & 18.2  & 32.7      & 4.0*  & 24.5  & 15.5  & 21.4  \\
261Cross Handler (100M)   & 6.0   & 0.9   & N/C   & 37.4      & 10.0  & 0.8   & N/C   & 32.2  \\
262Cross Finally (100M)   & 0.9   & N/A   & N/C   & 44.1      & 0.8   & N/A   & N/C   & 37.3  \\
263Match All (10M)        & 32.9  & 20.7  & 13.4  & 4.9       & 36.2  & 24.5  & 12.0  & 3.1   \\
264Match None (10M)       & 32.7  & 50.3  & 11.0  & 5.1       & 36.3  & 71.9  & 12.3  & 4.2   \\
265\hline
266\end{tabular}
267\end{table}
268
269\begin{table}[htb]
270\centering
271\caption{Resumption Performance Results (sec)}
272\label{t:PerformanceResumption}
273\begin{tabular}{|r||r||r|}
274\hline
275N\hspace{8pt}
276                        & AMD     & ARM  \\
277\hline
278Empty Traversal (10M)   & 0.2     & 0.3  \\
279D'tor Traversal (10M)   & 1.8     & 1.0  \\
280Finally Traversal (10M) & 1.7     & 1.0  \\
281Other Traversal (10M)   & 22.6    & 25.9 \\
282Cross Handler (100M)    & 8.4     & 11.9 \\
283Match All (100M)        & 2.3     & 3.2  \\
284Match None (100M)       & 2.9     & 3.9  \\
285\hline
286\end{tabular}
287\end{table}
288
289\begin{table}[htb]
290\centering
291\small
292\caption{Resumption/Fixup Routine Comparison (sec)}
293\label{t:PerformanceFixupRoutines}
294\setlength{\tabcolsep}{5pt}
295\begin{tabular}{|r|*{2}{|r r r r r|}}
296\hline
297            & \multicolumn{5}{c||}{AMD}     & \multicolumn{5}{c|}{ARM}  \\
298\cline{2-11}
299N\hspace{8pt}       & \multicolumn{1}{c}{Raise} & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c||}{Python} &
300              \multicolumn{1}{c}{Raise} & \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{\Cpp} & \multicolumn{1}{c}{Java} & \multicolumn{1}{c|}{Python} \\
301\hline
302Resume Empty (10M)  & 1.5 & 1.5 & 14.7 & 2.3 & 176.1  & 1.0 & 1.4 & 8.9 & 1.2 & 119.9 \\
303\hline
304\end{tabular}
305\end{table}
306
307% Now discuss the results in the tables.
308One result not directly related to \CFA but important to keep in mind is that,
309for exceptions, the standard intuition about which languages should go
310faster often does not hold.
311For example, there are a few cases where Python out-performs
312\CFA, \Cpp and Java.
313% To be exact, the Match All and Match None cases.
314The most likely explanation is that, since exceptions
315are rarely considered to be the common case, the more optimized languages
316make that case expensive to improve other cases.
317In addition, languages with high-level representations have a much
318easier time scanning the stack as there is less to decode.
319
320As stated,
321the performance tests are not attempting to show \CFA has a new competitive
322way of implementing exception handling.
323The only performance requirement is to insure the \CFA EHM has reasonable
324performance for prototyping.
325Although that may be hard to exactly quantify, I believe it has succeeded
326in that regard.
327Details on the different test cases follow.
328
329\subsection{Termination \texorpdfstring{(\autoref{t:PerformanceTermination})}{}}
330
331\begin{description}
332\item[Empty Traversal]
333\CFA is slower than \Cpp, but is still faster than the other languages
334and closer to \Cpp than other languages.
335This result is to be expected,
336as \CFA is closer to \Cpp than the other languages.
337
338\item[D'tor Traversal]
339Running destructors causes a huge slowdown in the two languages that support
340them. \CFA has a higher proportionate slowdown but it is similar to \Cpp's.
341Considering the amount of work done in destructors is effectively zero
342(an assembly comment), the cost
343must come from the change of context required to run the destructor.
344
345\item[Finally Traversal]
346Performance is similar to Empty Traversal in all languages that support finally
347clauses. Only Python seems to have a larger than random noise change in
348its run-time and it is still not large.
349Despite the similarity between finally clauses and destructors,
350finally clauses seem to avoid the spike that run-time destructors have.
351Possibly some optimization removes the cost of changing contexts.
352
353\item[Other Traversal]
354For \Cpp, stopping to check if a handler applies seems to be about as
355expensive as stopping to run a destructor.
356This results in a significant jump.
357
358Other languages experience a small increase in run-time.
359The small increase likely comes from running the checks,
360but they could avoid the spike by not having the same kind of overhead for
361switching to the check's context.
362
363\item[Cross Handler]
364Here \CFA falls behind \Cpp by a much more significant margin.
365This is likely due to the fact \CFA has to insert two extra function
366calls, while \Cpp does not have to do execute any other instructions.
367Python is much further behind.
368
369\item[Cross Finally]
370\CFA's performance now matches \Cpp's from Cross Handler.
371If the code from the finally clause is being inlined,
372which is just an asm comment, than there are no additional instructions
373to execute again when exiting the try statement normally.
374
375\item[Conditional Match]
376Both of the conditional matching tests can be considered on their own.
377However for evaluating the value of conditional matching itself, the
378comparison of the two sets of results is useful.
379Consider the massive jump in run-time for \Cpp going from match all to match
380none, which none of the other languages have.
381Some strange interaction is causing run-time to more than double for doing
382twice as many raises.
383Java and Python avoid this problem and have similar run-time for both tests,
384possibly through resource reuse or their program representation.
385However \CFA is built like \Cpp and avoids the problem as well, this matches
386the pattern of the conditional match, which makes the two execution paths
387very similar.
388
389\end{description}
390
391\subsection{Resumption \texorpdfstring{(\autoref{t:PerformanceResumption})}{}}
392
393Moving on to resumption, there is one general note,
394resumption is \textit{fast}. The only test where it fell
395behind termination is Cross Handler.
396In every other case, the number of iterations had to be increased by a
397factor of 10 to get the run-time in an appropriate range
398and in some cases resumption still took less time.
399
400% I tried \paragraph and \subparagraph, maybe if I could adjust spacing
401% between paragraphs those would work.
402\begin{description}
403\item[Empty Traversal]
404See above for the general speed-up notes.
405This result is not surprising as resumption's linked-list approach
406means that traversing over stack frames without a resumption handler is
407$O(1)$.
408
409\item[D'tor Traversal]
410Resumption does have the same spike in run-time that termination has.
411The run-time is actually very similar to Finally Traversal.
412As resumption does not unwind the stack, both destructors and finally
413clauses are run while walking down the stack during the recursive returns.
414So it follows their performance is similar.
415
416\item[Finally Traversal]
417Same as D'tor Traversal,
418except termination did not have a spike in run-time on this test case.
419
420\item[Other Traversal]
421Traversing across handlers reduces resumption's advantage as it actually
422has to stop and check each one.
423Resumption still came out ahead (adjusting for iterations) but by much less
424than the other cases.
425
426\item[Cross Handler]
427The only test case where resumption could not keep up with termination,
428although the difference is not as significant as many other cases.
429It is simply a matter of where the costs come from,
430both termination and resumption have some work to set-up or tear-down a
431handler. It just so happens that resumption's work is slightly slower.
432
433\item[Conditional Match]
434Resumption shows a slight slowdown if the exception is not matched
435by the first handler, which follows from the fact the second handler now has
436to be checked. However the difference is not large.
437
438\end{description}
439
440\subsection{Resumption/Fixup \texorpdfstring{(\autoref{t:PerformanceFixupRoutines})}{}}
441
442Finally are the results of the resumption/fixup routine comparison.
443These results are surprisingly varied. It is possible that creating a closure
444has more to do with performance than passing the argument through layers of
445calls.
446At 100 stack frames, resumption and manual fixup routines have similar
447performance in \CFA.
448More experiments could try to tease out the exact trade-offs,
449but the prototype's only performance goal is to be reasonable.
450It has already in that range, and \CFA's fixup routine simulation is
451one of the faster simulations as well.
452Plus exceptions add features and remove syntactic overhead,
453so even at similar performance resumptions have advantages
454over fixup routines.
Note: See TracBrowser for help on using the repository browser.