[herbstein]

> The article mentions bounds checks, but gives no measurements. Have they ever measured?

Related, the prominent Rust community member "Shnatsel" wrote an article [1] about exactly that in January. It's a great look at the problem, and gives some actual data to evaluate with.

[1]: https://shnatsel.medium.com/how-to-avoid-bounds-checks-in-ru...

[titzer]

Thanks for the reference. Several of the examples given could benefit from loop versioning and/or iteration space partitioning, i.e. the compiler splitting a loop that it cannot prove is always in-bounds to an in-bounds part and a possibly-out-of-bounds part. The HotSpot C2 compiler does this under some circumstances.

E.g. the simplest case:

    for (i = 0; i < some_expr; i++) {
      a[i] = other_expr;  // cannot prove is in bounds
    }

Becomes:

    var t = some_expr;
    if (t <= a.length) {
       for (i = 0; i < t; i++) {
         a[i] = other_expr; // no bounds check necessary
       }
    } else {
       for (i = 0; i < a.length; i++) {
         a[i] = other_expr; // no bounds check necessary
       }
       throw OutOfBoundsError; // throw exception at first OOB iteration
    }

This approach will have exactly the same behavior as the original program and run without bounds checks in either case. It will even throw at the right time. The cost is having two copies of the loop and a check up-front. This specific case could be done with one version, and other cases can be done with a different partitioning of the loops.

I feel people are lacking imagination on what an awesome buffet of compiler transforms are available when it is both absolutely required to do bounds checks and absolutely necessary to try to eliminate them everywhere. In practice, many many loops are trivially in bounds, many other loops are cold enough or big enough that the cost of a bounds check isn't much. You don't need to unroll and version every loop in the program. And like I said, for the loops outside of this set, where iterations are not affine or the indexes are irregular, you either live with bounds checks or you go deeper on allowing static assertions to prove accesses are in bounds. That's exactly the cases where you probably want checks anyway.