Control Flow

The previous lesson turned up a branch instruction as an operator’s byproduct: short-circuit evaluation was a jump that never entered the second operand at all. This lesson makes the branch its main subject. Forms written separately in the source as if, switch, for, while, break, and continue do not find this variety in the class file. There, only a handful of instruction kinds exist: a conditional branch, an unconditional jump, and two kinds of selection instruction.

The Programming Fundamentals course established conditional branching, loops, and loop control as concepts — those are not repeated here. There, what a flow form does was explained. What is measured here is which instruction the same behavior compiles to, and that two separate instructions carry separate lookup costs.

Flow Form and Flow Instruction

Two separate instructions answer a selection in the class file, and the compiler decides which to use by looking at how the labels are distributed.

• A dense selection instruction holds a table: one entry for every value from the smallest label to the largest. The given value indexes directly into the table; there is no search, there is a single position calculation. In return, the table also holds space for the gaps in between.
• A sparse selection instruction holds only the real labels, in order, and searches for the given value within that ordered list. It holds no space, but a search is paid on every selection.

There is a third path too: writing the same behavior as an if chain. Then there is no selection instruction at all; as many conditional branches as there are labels are strung one after another, and for the last label all of them are tried. This lesson measures all three forms on the warehouse’s shelf number, carried through the course, then moves on to loop forms.

The Measurement Core

The core is the previous lessons’ core; this lesson reads two measurements. The first is branch instruction count. The second, when a method has a selection instruction, is which one it is: for dense selection the range the table covers is printed, for sparse selection the number of labels held is printed.

• BS16 — Branch count is the number of conditional and unconditional jump instructions in the class file; not how many times they run, but how many are written is counted.
• BS17 — A selection instruction is found at most once in a single method; when the column is empty, that method has no selection instruction at all.

// Gauge.java — reads which instruction a flow form compiles to in the class file
import java.io.PrintWriter;
import java.io.Writer;
import java.lang.classfile.*;
import java.lang.classfile.instruction.*;
import java.nio.file.*;
import java.util.*;
import java.util.spi.ToolProvider;

class Gauge {
    record Method(String name, int instructions, int branches, String select, List<String> added) {}

    static List<Method> read(String source, String className) throws Exception {
        Path d = Files.createTempDirectory("gauge");
        Files.writeString(d.resolve(className + ".java"), source);
        PrintWriter sink = new PrintWriter(Writer.nullWriter());
        if (ToolProvider.findFirst("javac").orElseThrow().run(sink, sink, "-d", d.toString(),
                d.resolve(className + ".java").toString()) != 0)
            throw new IllegalStateException("did not compile: " + className);
        List<Method> methods = new ArrayList<>();
        for (MethodModel m : ClassFile.of().parse(d.resolve(className + ".class")).methods()) {
            if (m.code().isEmpty()) continue;
            List<String> added = new ArrayList<>();
            String select = "-";
            int instructions = 0, branches = 0;
            for (CodeElement e : m.code().get()) {
                if (e instanceof Instruction) instructions++;
                if (e instanceof BranchInstruction) branches++;
                else if (e instanceof TableSwitchInstruction t)
                    select = "dense " + t.lowValue() + ".." + t.highValue();
                else if (e instanceof LookupSwitchInstruction l)
                    select = "sparse " + l.cases().size() + " labels";
                else if (e instanceof InvokeInstruction iv)
                    added.add(iv.name().stringValue());
                else if (e instanceof TypeCheckInstruction tc && tc.opcode() == Opcode.CHECKCAST)
                    added.add("type check");
            }
            methods.add(new Method(m.methodName().stringValue(), instructions, branches, select, added));
        }
        return methods;
    }
}

Ten Flow Forms

The measured class’s first three methods give the same form of writing with three separate label distributions; the fourth writes the third’s mapping as an if chain. The next four compute the same sum over an array and a list, with the enhanced for and with a manually unrolled form. The last two show two ways of exiting two nested loops.

// Flow.java — ten flow forms, which instruction in the class file
public class Flow {
    static final String SOURCE = """
        import java.util.Iterator;
        import java.util.List;
        class Warehouse {
            static int denseSelect(int shelf) {
                switch (shelf) { case 1: return 10; case 2: return 20;
                               case 3: return 30; case 4: return 40; default: return 0; }
            }
            static int withGaps(int shelf) {
                switch (shelf) { case 1: return 10; case 2: return 20;
                               case 3: return 30; case 10: return 40; default: return 0; }
            }
            static int sparseSelect(int shelf) {
                switch (shelf) { case 1: return 10; case 100: return 20;
                               case 10000: return 30; case 1000000: return 40; default: return 0; }
            }
            static int ifChain(int shelf) {
                if (shelf == 1) return 10;
                if (shelf == 100) return 20;
                if (shelf == 10000) return 30;
                if (shelf == 1000000) return 40;
                return 0;
            }
            static int arraySum(int[] counts) { int t = 0; for (int x : counts) t += x; return t; }
            static int arrayIndexed(int[] counts) {
                int t = 0;
                for (int i = 0; i < counts.length; i++) t += counts[i];
                return t;
            }
            static int listSum(List<Integer> counts) { int t = 0; for (int x : counts) t += x; return t; }
            static int manualIterator(List<Integer> counts) {
                int t = 0;
                for (Iterator<Integer> y = counts.iterator(); y.hasNext(); ) { int x = y.next(); t += x; }
                return t;
            }
            static int labeled(int[][] warehouse, int wanted) {
                int row = -1;
                outer:
                for (int i = 0; i < warehouse.length; i++)
                    for (int j = 0; j < warehouse[i].length; j++)
                        if (warehouse[i][j] == wanted) { row = i; break outer; }
                return row;
            }
            static int flagged(int[][] warehouse, int wanted) {
                int row = -1;
                boolean found = false;
                for (int i = 0; i < warehouse.length && found == false; i++)
                    for (int j = 0; j < warehouse[i].length; j++)
                        if (warehouse[i][j] == wanted) { row = i; found = true; break; }
                return row;
            }
        }
        """;

    public static void main(String[] args) throws Exception {
        System.out.printf("%-16s %6s %4s %-16s %s%n",
                "method", "instr", "br", "select instr", "step not written in source");
        for (Gauge.Method y : Gauge.read(SOURCE, "Warehouse")) {
            if (y.name().startsWith("<")) continue;
            System.out.printf("%-16s %6d %4d %-16s %s%n", y.name(), y.instructions(), y.branches(), y.select(),
                    y.added().isEmpty() ? "-" : String.join(", ", y.added()));
        }
    }
}

method            instr   br select instr     step not written in source
denseSelect          12    0 dense 1..4       -
withGaps             12    0 dense 1..10      -
sparseSelect         12    0 sparse 4 labels  -
ifChain              22    4 -                -
arraySum             24    2 -                -
arrayIndexed         18    2 -                -
listSum              20    2 -                iterator, hasNext, next, type check, intValue
manualIterator       20    2 -                iterator, hasNext, next, type check, intValue
labeled              32    6 -                -
flagged              38    7 -                -

The first three rows are the lesson’s central measurement. All three methods carry four labels and a default branch, are written with the same form, and turn into the same 12 instructions in the class file. But the selection instruction is not the same: when labels spread from 1 to 4, a dense instruction is produced; when they spread into the millions, a sparse instruction is produced. There is no structural difference at all between the two switch statements in the source; the difference is only in the numbers’ values, and the compiler chose a separate instruction by looking at those values. Instruction count does not see this — what has to be counted here is not instruction count, it is which instruction.

The second row shows how the decision is made. withGaps carries only four labels, but its smallest is 1, its largest is 10; the compiler still chooses the dense instruction and the table stretches from 1 to 10. So the class file also holds space for six unused entries. The compiler’s decision is a tradeoff: the gaps that fill it take up space in the file, and in return every selection does a single index instead of a search. Once labels spread far enough, the tradeoff flips.

The fourth row is selection’s alternative. When the same mapping is written as an if chain, there is no selection instruction at all: 22 instructions and 4 branches. What the four branches mean is that to find the last label, the previous three all have to be tried too. Selection instructions reduce this trying to a single step; an if chain grows with label count. The same behavior, two separate costs.

The Same Loop, Two Separate Steps

The four rows in the middle show that the enhanced for loop is not a single form of writing.

arraySum produces 24 instructions and no step at all unwritten in the source: the compiler opens the enhanced for form into a counted loop. listSum finishes the same body in 20 instructions but carries five added steps — an iterator is taken, queried twice, the returned object is checked, and opened into a number. These numbers were read as boxing’s cost in the first lesson; here their reading is different. The same form of writing compiles to two separate loops depending on the type of what is walked. One syntax, two instructions.

The two rows beside them prove this. arrayIndexed is a hand-written counted loop and produces 18 instructions — six fewer than the enhanced form, because the enhanced form copies the array reference and the length into separate slots. manualIterator is a hand-written iterator loop and comes out exactly identical to listSum: the same 20 instructions, the same two branches, the same five steps. The enhanced for over a list is exactly this loop’s shorthand; over an array it is a slightly more generously written form of the counted loop.

The last two rows are the next section’s subject: labeled jump is 32 instructions and 6 branches, the flagged form is 38 instructions and 7 branches.

Labeled Jump’s Measured Gain

Java offers three ways to exit two nested loops at once: putting a label on the outer loop and writing break outer, holding a flag variable, or just writing break and exiting only the inner loop. The three do not give the same program.

• BS18 — The warehouse carries three rows and four records per row; the sought name is found in two rows, the first being the second row’s third record. The correct answer is 1.
• BS19 — The step counter is incremented only in the inner loop’s body, meaning it counts the number of records compared; no duration is measured.

// Jump.java — three exit forms, how many steps and which row
public class Jump {
    record Item(String name, int count, long weight) {}

    static int steps = 0;

    static Item[][] warehouse() {
        return new Item[][] {
            { new Item("bolt", 4, 40L), new Item("washer", 9, 5L),
              new Item("nut", 2, 12L), new Item("pin", 1, 300L) },
            { new Item("gasket", 7, 8L), new Item("spring", 3, 15L),
              new Item("screw", 5, 90L), new Item("ball", 6, 20L) },
            { new Item("screw", 2, 90L), new Item("wedge", 8, 30L),
              new Item("bushing", 4, 60L), new Item("bearing", 1, 250L) },
        };
    }

    static int labeled(Item[][] d, String wanted) {
        int row = -1;
        outer:
        for (int i = 0; i < d.length; i++)
            for (int j = 0; j < d[i].length; j++) {
                steps++;
                if (d[i][j].name().equals(wanted)) { row = i; break outer; }
            }
        return row;
    }

    static int flagged(Item[][] d, String wanted) {
        int row = -1;
        boolean found = false;
        for (int i = 0; i < d.length && found == false; i++)
            for (int j = 0; j < d[i].length; j++) {
                steps++;
                if (d[i][j].name().equals(wanted)) { row = i; found = true; break; }
            }
        return row;
    }

    static int plainBreak(Item[][] d, String wanted) {
        int row = -1;
        for (int i = 0; i < d.length; i++)
            for (int j = 0; j < d[i].length; j++) {
                steps++;
                if (d[i][j].name().equals(wanted)) { row = i; break; }
            }
        return row;
    }

    public static void main(String[] args) {
        Item[][] d = warehouse();
        System.out.printf("%-12s %6s %8s%n", "form", "row", "steps");
        steps = 0;
        System.out.printf("%-12s %6d %8d%n", "labeled", labeled(d, "screw"), steps);
        steps = 0;
        System.out.printf("%-12s %6d %8d%n", "flagged", flagged(d, "screw"), steps);
        steps = 0;
        System.out.printf("%-12s %6d %8d%n", "plain break", plainBreak(d, "screw"), steps);
    }
}

form            row    steps
labeled           1        7
flagged           1        7
plain break       2        8

The third row is the measurement’s most important part, and it is not a performance difference. A plain break exits only the inner loop; the outer loop keeps going from where it was, and after the match on the second row is found, the third row is scanned too and the row variable is overwritten. The result is 2, that is, wrong. One extra step was paid, and that step produced the wrong answer. In nested loops, which loop a break belongs to is not a matter of style.

The first two rows, by contrast, bound labeled jump’s real gain. The labeled form and the flagged form find the same row and pay the same 7 steps. Labeled jump’s run-time gain against the flagged form is zero.

The Bounding Measurement: Where the Gain Is, Where the Cost Is

Labeled jump’s measurable gain sits in two places, and both are small.

• BS20 — The comparison is the labeled and flagged methods in the class-file measurement; both carry the same signature and return the same result.

The first is in the class file: the labeled form produces 32 instructions and 6 branches, the flagged form 38 instructions and 7 branches — six instructions and one branch fewer. The flag holds a slot, is read at the start of every outer round, and is written on a match; all of this is instructions. The second is in the source: in the flagged form, the exit condition is spread across two places — the outer loop’s header and the inner loop’s body. In the labeled form, the exit is on a single line.

The cost has to be written too. A label sends the reader’s eye backward in the source: someone reading the break outer line has to look up to find which loop the outer label sits on. In two loops this look is short; at three or four levels, and with a continue in between too, labels make the flow hard to follow. The measurement does not decide, it only says how much of what: the gain is six instructions and one slot, it is zero as a run-time step, and the cost is the reader having to look up.

This boundary also completes the lesson’s thesis. The choice between flow forms mostly changes instruction count but does not change the step paid. The one place that genuinely changes is where the form makes incorrect behavior possible — as with the plain break line.

Summary

• The same selection compiles to two separate instructions depending on label distribution: a table that indexes directly under dense distribution, an instruction that searches among labels under sparse distribution. Instruction count is 12 in all three; what changes is which instruction it is.
• The dense instruction’s table stretches from the smallest label to the largest: a four-label selection can hold space from 1 to 10. The decision is a tradeoff, file size against search.
• When the same mapping is written as an if chain, there is no selection instruction at all: 22 instructions and 4 branches, and for the last label all of them are tried.
• The enhanced for is not a single form of writing: it produces 24 instructions and 0 added steps over an array, 20 instructions and 5 added steps over a list; the list form is exactly identical to a hand-written iterator loop.
• Labeled jump earns both a step and the correct row against a plain break; against the flagged form its gain is six instructions, zero as a run-time step, and its cost is the reader having to look up for the label.

Next Step

This lesson measured which instruction flow forms compile to: the same selection turned into two separate lookup instructions, the same enhanced for loop turned into separate steps over an array and a list. All these measurements walked over something, and that thing itself was never questioned. What is left is the thing walked over. The next lesson measures the array: how many instructions the line new int[3] leaves in the class file, whether the form d.length is a field read or an instruction of its own, and where in the source the step that checks an array’s bound sits.