Practical performance

A reliable benchmark runs the code many times, discards warm-up runs, uses its result (so the JIT cannot delete it), repeats, and reports the median or minimum. For serious work use JMH, the OpenJDK Java Microbenchmark Harness. A plain System.nanoTime loop is a rough check.

Never compare single runs, and measure with realistic input sizes.

1static long sink;   // consuming the result stops dead-code elimination
2static long time(Runnable r, int reps) {
3    long best = Long.MAX_VALUE;
4    for (int i = 0; i < reps; i++) {
5        long t0 = System.nanoTime();
6        r.run();
7        best = Math.min(best, System.nanoTime() - t0);
8    }
9    return best;
10}

The JVM starts by interpreting bytecode and compiles frequently used methods to machine code (the JIT compiler), later recompiling with more optimisations. The first runs of a method are therefore slow, and code can also be deoptimised if its assumptions change. Benchmarks must run until the timings are stable.

This is why the first call of a method can be 10 to 100 times slower than the thousandth.

Creating objects is cheap in Java but not free: each allocation needs a header and later garbage collection. Allocating inside a loop that runs 10⁷ times (new arrays, small objects, iterator objects, boxed values) increases GC activity and cache misses. Hoist allocations out of loops and reuse buffers.

Measure before optimising: the JIT sometimes removes allocation entirely through escape analysis.

1// allocates a new int[26] every call
2static boolean anagramSlow(String a, String b) { int[] f = new int[26]; /* ... */ return true; }
3// reuse one buffer: clear it instead of reallocating
4static final int[] F = new int[26];
5static void reset() { Arrays.fill(F, 0); }

Boxing wraps a primitive in an object (int → Integer). Each boxed value costs a 16-byte object plus a reference, adds pointer-chasing and GC load, and is slower to add up. For hot loops and large collections prefer primitive arrays (int[]) or specialised structures.

The two sums below return the same value; the boxed one is typically several times slower for large n.

1int n = 10_000_000;
2long a = 0; for (int i = 0; i < n; i++) a += i;               // primitive: no allocation
3Long b = 0L; for (int i = 0; i < n; i++) b += i;              // boxes a new Long on most iterations
4int[] prim = new int[n];
5List<Integer> boxed = new ArrayList<>(n);                    // about 5x the memory

Strings are immutable, so s += x creates a new string and copies all characters each time. Building a string of n characters this way costs O(n²). StringBuilder.append is amortised O(1) per character and builds the string in O(n) overall.

A single concatenation expression such as a + b + c is fine; the problem is concatenation inside a loop.

1String s = "";
2for (int i = 0; i < 100_000; i++) s += i;               // O(n^2): copies the whole string each time
3StringBuilder sb = new StringBuilder();
4for (int i = 0; i < 100_000; i++) sb.append(i);        // O(n)
5String t = sb.toString();

A CPU pipeline guesses which way each if will go and starts executing ahead. A correct guess is free; a wrong one throws away work and costs about 10 to 20 cycles. Predictable branches (always true, or following a pattern) are fast. Random ones, such as “is this random value above the median?”, are slow.

That is why summing only values above a threshold can be faster on sorted data than on the same data shuffled. The animation runs a 2-bit predictor over a pattern of your choice and counts mispredictions.

1long sum = 0;
2for (int x : data) if (x >= 128) sum += x;   // same work, but much faster when data is sorted

1long sum = 0;
2for (int x : data) {
3    if (x >= 50) {               // the CPU guesses taken / not taken BEFORE it knows x
4        sum += x;
5    }
6}
7// 2-bit saturating counter: 0,1 predict not-taken; 2,3 predict taken; each outcome moves it one step

The order in which loops visit memory decides how many cache lines are loaded. Iterate the innermost loop over the last array index (columns of a row), walk linked structures only when needed and store related fields together. Blocking (tiling) a big matrix operation into small tiles that fit in cache is a standard optimisation.

Compare row-order and column-order traversal on the same grid and read the hit and miss counts.

1int sumRowMajor(int[][] m) {                  // inner loop walks along a row
2    int sum = 0;
3    for (int r = 0; r < m.length; r++)
4        for (int c = 0; c < m[0].length; c++) sum += m[r][c];
5    return sum;
6}
7int sumColumnMajor(int[][] m) {               // inner loop jumps down a column
8    int sum = 0;
9    for (int c = 0; c < m[0].length; c++)
10        for (int r = 0; r < m.length; r++) sum += m[r][c];
11    return sum;
12}