What is the runtime cost of array bounds checks, and how does the JIT compiler optimize them away?

## The cost model A bounds check is logically inserted before **every** array access. In pseudo-machine terms `x = a[i]` becomes: ``` if (i < 0 || i >= a.length) throw AIOOBE; x = load a[base + i*scale]; ``` (The two comparisons are usually folded into **one unsigned compare**: treating `i` as unsigned, any negative value becomes a huge number, so `((unsigned)i >= length)` catches both `i < 0` and `i >= length` in a single instruction.) The runtime cost is therefore roughly **one compare + one branch per access**, plus the load of `a.length`. On modern CPUs a well-predicted branch is nearly free, but in a tight numeric loop these checks still add up and, more importantly, they can **block vectorization** and other optimizations. ## Why a JIT, and what 'hot' means The JVM first **interprets** bytecode, then the **JIT (Just-In-Time) compiler** — HotSpot's C1/C2 — compiles **hot** methods (frequently executed ones identified by profiling) to native code. It is at this stage that bounds checks can be optimized. ## Bounds-Check Elimination (BCE) **BCE** is the optimization that proves a check is unnecessary and deletes it. The compiler does **range/value analysis**: it tracks the possible range of the index variable. The textbook case is a counted loop bounded by the array's own length: ```java for (int i = 0; i < a.length; i++) { sum += a[i]; // i is provably in [0, a.length) -> check removed } ``` Here the loop condition `i < a.length` *guarantees* `i` is in range every iteration, so C2 removes the per-element check. Related techniques: - **Range-check elimination / loop predication:** instead of checking inside the loop, the JIT hoists a single check *before* the loop (a 'predicate'): if the whole range is known safe, run a fast checkless loop body; otherwise fall back. This converts N checks into ~1. - **Loop unrolling + main/post loops:** the compiler splits a loop into a checkless 'main' loop over the safe range and a small guarded remainder, enabling vectorization (SIMD) on the main part. - **Speculation + uncommon traps (deoptimization):** the JIT may *assume* an index stays in range based on profiling and emit code with no check. If that assumption is ever violated, it hits an **uncommon trap**, **deoptimizes** back to the interpreted/safe version, and re-checks. So correctness is never sacrificed — only the common-case cost. ## When BCE fails BCE depends on the compiler being able to *prove* safety. It is defeated by: - indices computed from opaque sources (method returns it can't analyze, complex arithmetic, `% `/bit tricks it can't bound), - accessing a *different* array than the one the loop is bounded by (the bound proves nothing about a second array), - writes that could change `length`-related state, or escaping references that confuse aliasing analysis. In those cases the check stays in, and you pay the per-access cost. ## Practical guidance - Write **simple, length-bounded `for` loops** (or enhanced `for`/`for-each`, which the JIT recognizes well) so BCE fires. - Avoid hand-rolled index arithmetic when a plain counted loop will do. - Don't try to 'beat' the checks with unsafe tricks; the JIT usually removes them, and `sun.misc.Unsafe`/foreign-memory bypasses sacrifice the safety guarantee. - Bounds checks are a **safety feature whose cost is largely a compile-time concern** — in steady-state hot code they typically cost close to zero. ## Key takeaways - A check is a single (unsigned) compare + branch + a `length` load per access. - HotSpot's C2 eliminates or hoists most of them via range analysis, loop predication, and unrolling. - Speculative removal is backed by deoptimization, so it never breaks correctness. - Idiomatic length-bounded loops are what let the optimizer succeed.