The just-in-time (JIT) compiler in OpenJDK improves Java performance through a number of optimizations, particularly in loops. Until recently, many optimizations worked only when the loop index was an `int`

variable. This article shows how the HotSpot virtual machine was upgraded to add the same optimizations for `long`

variables. The article covers particularly out-of-bounds checking (also called *range checks*).

## Why optimization was added for long variables

One of the important promises of Java, along with many other modern languages, is to catch out-of-bounds errors, such as when you mistakenly end a loop at `array.length`

instead of at `array.length-1`

. The HotSpot virtual machine eliminates range checks when possible as a performance optimization. As discussed in a previous article, the JIT compiler enables range checks when the compiler is not sure that an index will stay within the bounds of an array.

The JIT compiler implements range checks as follows:

```
for (int i = start; i < stop; i += stride)) {
if (scale * i + offset >=u array.length) { // range check
deoptimize();
}
// access to element scale * i + offset of array
}
```

In the previous code, `>=u`

is an unsigned comparison, and the `deoptimize()`

function causes execution of the thread to continue in the interpreter where the out of bound exception is thrown.

Until recent versions of OpenJDK, optimization of range checks worked only if the loop variable `i`

was an `int`

. For a `long`

, range checks would always be performed. Many other optimizations were also unavailable.

The reason for restricting loop optimization to `int`

indexes was that they were considered the only ones common enough to deserve special treatment. One reason is that loops commonly iterate over arrays. Because the size of a Java array is a 32-bit integer, an `int`

is the natural choice for the loop variable.

Usages are evolving, though. The Panama Project offers developers a better way to get access to off-heap memory areas. Offsets within memory are 64 bits, so loops that iterate over memory with that API tend to use a `long`

loop variable.

The lack of proper optimizations for `long`

counted loops initially was such a pain point for the Panama Project that it implemented workarounds in the library code to detect cases where the offsets fit into a 32-bit integer. In such cases, the project included special code that the JIT could better optimize. But once the improvements covered in this article were rolled out, those workarounds became unnecessary and could be removed. The end result is simplified library code with better overall performance.

The loop shape that needs to be optimized is as follows:

```
for (long i = start; i < stop; i += stride)) {
if (scale * i + offset >=u length) { // range check
deoptimize();
}
// access to memory at offset scale * i + offset
}
```

The discussion in this article assumes a loop that goes upward (that is, an index that increases), along with a positive `scale`

. The project has generalized the optimization to accommodate a decreasing loop and a negative `scale`

as well, but we won't include those cases because they would overcomplicate the discussion.

## Recognizing and optimizing long counted loops

Teaching the compiler to recognize the new loop shape with a `long`

loop variable instead of an `int`

loop variable is fairly straightforward, but is not sufficient to enable existing optimizations such as range check elimination, loop unrolling, and vectorization. Those optimization passes must be adapted to operate on a `long`

counted loop as well. Doing so is not a simple matter of including `long`

variables, because some of the optimizations have to deal with integer overflow. They were protected from overflow for `int`

variables by promoting some 32-bit integer values to 64-bit integers. Supporting these same optimizations on 64-bit integers would require promotion to the next larger integer type (probably 128 bits), for which the compiler lacks support.

Is there a way to upgrade the existing optimizations for a `long`

without having to rewrite these optimizations and incur a high risk of introducing bugs?

The solution we went with started by transforming the `long`

counted loop into a nested loop with an `int`

counted inner loop. The previous example was transformed roughly to:

```
for (long i = start; i < stop;) {
int j;
for (j = 0; j < min(stop - i, max_int); j += (int)stride) {
if (scale * (j + i) + offset >=u length) { // range check
deoptimize();
}
// access to memory at offset scale * (j+i) + offset
}
i += j;
}
```

Here, `max_int`

represents the largest signed 32-bit integer. The loop variable for the inner loop is also a 32-bit integer. That inner loop has the shape of a counted loop, so it's subject to existing counted loop optimizations such as unrolling. Adding an extra loop has some overhead, but if the original loop executes for a large number of iterations, most of the time should be spent in the inner loop and the cost of setting it up should be negligible.

Note that this transformation is valid only for `stride`

values that fit into a 32-bit integer, and pays off mostly if `stride`

is a relatively small 32-bit integer. (Otherwise, the inner loop executes only a small number of iterations and the overhead of nested loops is bigger.)

This extra transformation has the benefit of enabling several existing loop optimizations to `long`

loop counters. But one important optimization still isn't triggered by the transformed loop: Eliminating the range check. Indeed, the range check in the previous loop nest is still expressed in terms of 64-bit integers: `j+i`

and `length`

. The next section discusses how we make sure the range check has a proper shape so that the compiler recognizes it and enables range check optimization.

## A new API point for range checks

A prerequisite for range check elimination is to make sure the loop has a shape that the compiler can properly optimize. In particular, the range check in the loop has to follow a canonical shape like the following, with an unsigned comparison and a deoptimization if the range check fails:

```
if (scale * i + offset >=u length) {
deoptimize();
}
```

The array accesses in Java include a range check, so the compiler is free to generate the pattern that works best for optimization. In the Panama Project's memory access API, the range check is not built into the language. So the check would have to be performed explicitly by the API in code similar to:

```
long o = scale * i + offset;
if (o >= length || o < 0) {
throw new SomeException();
}
```

The JIT compiler would then have to recognize this code pattern as a range check, which would be complicated to perform reliably. After all, there would be more than one way to write this logic.

We have a more robust solution, which involves extending the core Java libraries with a new API point for range checks:

`long o = java.util.Objects.checkIndex(scale * i + offset, length);`

The `checkIndex()`

call already exists for `int`

arguments.

We have made the JIT compiler aware of the new API function. The compiler can use its own implementation for `checkIndex()`

as long as its behavior appears identical to the Java implementation to outside callers.

The technique of replacing a standard implementation of a function with one provided by the compiler is called a *compiler intrinsic*. That implementation can be carefully crafted to allow optimizations.

The new `checkIndex()`

function and the corresponding underlying intrinsic are available as of JDK 16. Note that the new function is not restricted to the memory access API. It offers a reliable way of performing range checks that can be optimized well by the virtual machine, making the function a valuable addition to the core libraries for all developers.

## Optimizing long-range checks

So far, we have discussed a transformation of the loop so that it becomes suitable for existing optimizations. In the same spirit, this section discusses how to transform range checks in order to trigger existing range check optimizations for `long`

indexes. We need to reshape the nested loop to:

```
for (long i = start; i < stop;) {
int j;
int scale' = ..;
int offset' = ..;
int length' = ..;
for (j = 0; j < min(stop - i, max_int); j += (int)stride) {
if (scale' * j + offset' >=u length') {
deoptimize();
}
// access to memory at offset scale * (j+i) + offset
}
i += j;
}
```

The `scale'`

, `offset'`

, and `length'`

variables end with a prime symbol (`'`

) to denote a variable that is derived from or related to another variable. These variables are 32-bit integers that are invariant in the inner loop. Because the range check is expressed as a 32-bit comparison that operates on the loop variable of the inner loop, which is itself a loop with a 32-bit index, existing optimizations are triggered.

Assuming for instance that loop predication optimizes this loop nest, the result would be roughly:

```
for (long i = start; i < stop;) {
int j;
int scale' = ..;
int offset' = ..;
int length' = ..;
if (scale' * 0 + offset' >=u length') {
deoptimize();
}
if (scale' * jmax + offset' >=u length') {
deoptimize();
}
for (j = 0; j < min(stop - i, max_int); j += (int)stride) {
// access to memory at offset scale * (j+i) + offset
}
i += j;
}
```

`jmax`

is the largest value `j`

takes in the inner loop for a particular iteration `i`

.

Assuming, as we did before, that the inner loop runs for a large number of iterations, the range check becomes essentially free.

`scale'`

, `offset'`

, and `length'`

have to be derivatives of `scale`

, `offset`

, `length`

, and `i`

, the variables of the initial range check. They are all 64-bit integers. Let's see how to compute them.

`scale'`

can be set to `scale`

, but only if it fits in a 32-bit integer. Otherwise, there's no way to transform the range check. Another tricky issue here is that `scale' * j`

could overflow the `int`

range. One easy way around that problem is to adjust the inner loop's bounds so that overflow never happens, such as:

```
for (long i = start; i < stop;) {
int j;
int scale' = scale;
int offset' = ..;
int length' = ..;
for (j = 0; j < min(stop - i, max_int / scale); j += (int)stride) {
if (scale' * j + offset' >=u length') {
deoptimize();
}
// access to memory at offset scale * (j+i) + offset
}
i += j;
}
```

If `scale`

turns out to be a relatively large 32-bit integer, the number of iterations of the inner loop is small and this transformation is unlikely to pay off. The Panama Project expects a small `scale`

. Typically, this variable is the size of some basic data type.

Let's note the range of values of `j`

for some iteration `i`

of the outer loop as`[0, jmax]`

. Then `scale * (i + j) + offset`

is in the range`[scale * i + offset, scale * (i + jmax) + offset]`

(remember that this discussion assumes a positive `scale`

). Let's call that interval `[range_min, range_max]`

. It's then possible to express `offset'`

and `length'`

in terms of `range_min`

and `range_max`

. In the simplest case (`range_min >= 0`

, no overflow), we set:

`offset' = 0`

`length' = max(range_min, min(length, range_max+1)) - range_min`

Let's see why that works as expected—that is, why the transformed range check (expressed with `j`

) succeeds whenever the initial range check (expressed with `i`

) succeeds, and fails when the initial check fails.

We know that `j`

falls within `[0, jmax]`

. Then `range`

has the value `scale * (i + j) + offset`

and `range'`

has the value `scale * j + offset'`

. Using variables we defined earlier, `range`

is in `[range_min, range_max]`

and `range = range' + range_min`

. What happens for various values of `length`

?

### When length is greater than range_max

In this case, the range check always succeeds. `length'`

is `range_max+1 - range_min`

. The range check becomes:

`range' <u range_max+1 - range_min`

This expression is always true because `range`

is within `[range_min, range_max]`

and so `range'`

is within `[0, range_max - range_min]`

.

### When length is less than range_min

In this case, the range check always fails. `length'`

is `0`

. The range check becomes `range'<u 0`

, which is always false (no unsigned value can be negative).

### When length is somewhere in [range_min, range_max]

If `length`

is in `[range_min, range_max]`

, the range check succeeds sometimes and fails other times. `length'`

is `length - range_min`

. The range check becomes:

`range' <u length - range_min`

which is equivalent to:

```
0 <= range' < length - range_min
```

or

```
range_min <= range' + range_min < length
```

or

`range_min <= range < length`

Because we assumed `range_min`

to be positive, this is the same as `range <u length`

, the range check before transformation.

`length'`

must be a 32-bit integer, but is computed in terms of 64-bit values. Note, however, that `range_max - range_min`

fits in a 32-bit integer, because loop bounds require `scale * j`

to fit in a 32-bit integer. That, in turn, guarantees that `length'`

can safely be stored as a 32-bit value.

## Extensive optimizations accommodate more Java loops

This article covered recent optimizations in the OpenJDK HotSpot virtual machine that support loops with `long`

loop variables, with a particular focus on range checks operating on it. I gave an overview of the code patterns that developers can expect to be properly optimized. The article also demonstrated how new APIs require special virtual machine support and how the entire Java platform evolves to meet changing usages. Finally, I showed how reshaping a loop with a `long`

index enables a range of optimizations.

The cases we didn't cover in this article—loops going downward and a negative `scale`

—are discussed in a lengthy comment added to the JDK change request, augmented by this follow-up.

*Last updated: August 14, 2023*