Table II. Overheads of unoptimized vs. aggressive approximation (incl. unoptimized Steps 1–2).
Accounting optimization mode
No optimization With aggressive approx.
the predictions succeed, and the size of transformed class files will be substantially lower (see Section 7.3).
Since the static prediction of execution paths (SPP) is not an easy task, the probability of missing a prediction will remain non-negligible. Our goal is therefore to achieve a solution where even mispredicted branches will not, at least in theory, incur a higher overhead than with
our initial, Simple rewriting scheme.11 in Section 6.2.
This solution will be described
But first, we want to present another approach, called Aggressive approximation, to reducing the overhead of Step 3, which will exper- imentally give us a very low overhead for the accounting task, and hence provide valuable information on what maximal performance can be expected from SPP schemes.
6.1. Aggressive Approximation
Depending on the application, it may not always be necessary to do a very precise accounting of CPU consumption. There are e.g. many occurrences in Java code where the number of executed bytecodes only differs by one or two units between the two outcomes of a given con- ditional. Therefore, it might be acceptable to lose some precision in exchange for a lower run-time overhead. An extreme case is one where we only update the consumption once per method, or per loop body, i.e. essentially only in conjunction with polling sites in the code: this is what we call the aggressive approximation. The actual value to account may be chosen statically as the average length of all possible executions, or as the length of the longest, or most probable path.
Having implemented the latter solution, the resulting overhead is as indicated by Table II, compared to the completely unoptimized solution.
11 As shown later, there is some additional jumping required to implement the scheme, thus in practice the benefit may not be complete.