Nicolas B. Pierron | tags: [ Tier ] categories: [ Concepts ]

# Introducing Use-Counts

One of the papers I like about Just-In-Time compilers is about dealing with a choice between multiple optimization toggles. The research paper Adapative Optimization in the Jalapeño JVM describes how a JIT should decide which optimization it should select when compiling.

The first thing this paper defines is that for each method we associate an
expected time `T`

. This time is an estimate of the time the function is expected
to run later on. A simple and intuitive way to define this time, is to assume
that functions are going to run as much time as we have seen the method run until
now, i-e. `T(t) = t`

.

Then, given the estimated time remaining to be executed, the question which we
are trying to solve is if it would be better to spend time `C`

to compile the
function in order to gain an estimated speed-up `S`

from it. Literally answering
the following equation `C + T / S < T`

.

If you have a choice between multiple compilers, or between multiple
optimization toggles, then you want to choose the configuration which minimizes
the remaining time, i.e. `min_i( C_i + T / S_i ) < T`

. The research paper stops
at this point.

This equation is interesting, but it would be better if the compiler time and
speed-up estimate (expected to be strictly larger than 1) were on the same side.
We can do that by moving all `T`

to the right, factoring by `T`

, and moving the
speed-up `S`

back next to the compilation time `C`

, resulting in the following
inegality `C * S / (S - 1) < T`

.

The nice property about this inequality is that the left hand side that we are
trying to minimize no longer depends on the expected time. However, the
compilation time depends on the size of the method, maybe as a function of the
number of operations `O`

. Thus instead of considering the expected time of a
method, we could consider the expected average time per operation. `C * S / (O * (S - 1)) < T / O`

.

The average expected time per operation is even more interesting when the compilation time is linear in the number of operations as the left-hand side becomes a constant, as is expected for a fast JIT compiler or a simple trace compiler. What this implies is that we can trigger such compilation by comparing the number of times a given operation got executed, also named use-count, with a constant. A use-count indirectly measures time by counting the number of times a given instruction has been executed.

In the general case, that is, for compilers which compilation time is not linear in the
number of operations, we would have to compute `C(O) / O * S / (S - 1)`

to
decide when is a good time to compile when comparing it against the use-count
of the method.