Introduction to Switches

Java has two different forms of switches:

• tableswitch, table with keys and labels
• lookupswitch, table with only labels

tableswitch

Speed: O(1)

tableswitch utilises only labels.

It takes in the int value on top of the stack and uses it to index the table and identify the jump location and then immediately jump.

It is only applicable when there case values are dense and contiguous.

Bytecode Structure

A tableswitch is a variable-length instruction.

Break-down

Format	Data Type	Note
tableswitch opcode	unsigned byte
0 - 3 null bytes of padding		zeroed, ensures the following byte begins at an address multiple of 4.
default	signed 32 bit integer
low	signed 32 bit integer	must be less than or equal to high.
high	signed 32 bit integer
…	signed 32 bit integer	high - low + 1 offsets treated as a 0-based jump table.

Byte Break-down

tableswitch (0xaa)
0 - 3 byte padding
default byte 1
default byte 2
default byte 3
default byte 4
low byte 1
low byte 2
low byte 3
low byte 4
high byte 1
high byte 2
high byte 3
high byte 4
offsets…	stored as 32 bits, similar to default, low & high.

Target Address

The index popped from the stack must be an integer. If it is less than low or greater than high , the target address is calculated by adding either:

• default to the instruction address
• the offset (extracted) to instruction address

Pseudo code

int value = popStack();
if (value < lowValue || value > highValue) {
    programCounter += defaultOffset;
} else {
    programCounter += jumpOffset[value - lowValue];
}

Example

return switch (value) {
	case 1 -> "one";
	case 2 -> "two";
	case 3 -> "three";
	default -> "default";
}

would produce a result similar to:

tableswitch 1
		Label1
		Label2
		Label3
	default : Label4
 
Label1:
	ldc "one"
	...
 
Label2:
	ldc "two"
	...
 
Label3:
	ldc "three"
	...
 
Label4:
	ldc "default"
	...

lookupswitch

Speed: O(log n)

lookupswitch utilises both keys and labels.

It takes the int value on top of the stack and compares it against the keys until a match is found. The jump value next to this key is then used to perform the jump.

Bytecode Structure

A lookupswitch is a variable-length instruction.

Break-down

Format	Data Type	Note
lookupswitch byte	unsigned byte
0 - 3 null bytes of padding		zeroed, ensures the following byte begins at an address multiple of 4.
default	signed 32 bit integer
number of pairs	signed 32 bit integer	must be >= 0.
match-offset pairs…	match: signed 32 bit integer offset: signed 32 bit integer	must in in ascending order. sorted to support optimal searches, i.e., binary search.

Byte Break-down

lookupswitch (0xab)
0 - 3 byte padding
default byte 1
default byte 2
default byte 3
default byte 4
pairs…	stored as two 32 bit signed integers

Search

lookupswitch performs a binary search to identify the key, hence O(log n). This means that the table must be sorted in ascending order (smallest → largest).

Example

return switch (value) {
	case 1 -> "one";
	case 204 -> "two-hundred and four";
	case 7912 -> "seven-thousand nine-hundred and twelve";
	default -> "default";
}

would produce a result similar to:

lookupswitch
		1 : Label2
		2 : Label2
		3 : Label3
	default : Label4
 
Label1:
	ldc "one"
	...
 
Label2:
	ldc "two-hundred and four"
	...
 
Label3:
	ldc "seven-thousand nine-hundred and twelve"
	...
 
Label4:
	ldc "default"
	...

Research Sources

https://github.com/ndru83/desugaring-java/blob/master/switch-case-internals.adoc
https://docs.oracle.com/javase/specs/jvms/se24/html/jvms-6.html
https://stackoverflow.com/questions/10287700/difference-between-jvms-lookupswitch-and-tableswitch