StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The answer lies in the bytecode:</p> <p><strong>SwitchTest10.java</strong></p> <pre><code>public class SwitchTest10 { public static void main(String[] args) { int n = 0; switcher(n); } public static void switcher(int n) { switch(n) { case 0: System.out.println(0); break; case 1: System.out.println(1); break; case 2: System.out.println(2); break; case 3: System.out.println(3); break; case 4: System.out.println(4); break; case 5: System.out.println(5); break; case 6: System.out.println(6); break; case 7: System.out.println(7); break; case 8: System.out.println(8); break; case 9: System.out.println(9); break; case 10: System.out.println(10); break; default: System.out.println("test"); } } } </code></pre> <p><strong>Corresponding bytecode; only relevant parts shown:</strong></p> <pre><code>public static void switcher(int); Code: 0: iload_0 1: tableswitch{ //0 to 10 0: 60; 1: 70; 2: 80; 3: 90; 4: 100; 5: 110; 6: 120; 7: 131; 8: 142; 9: 153; 10: 164; default: 175 } </code></pre> <p><strong>SwitchTest22.java:</strong></p> <pre><code>public class SwitchTest22 { public static void main(String[] args) { int n = 0; switcher(n); } public static void switcher(int n) { switch(n) { case 0: System.out.println(0); break; case 1: System.out.println(1); break; case 2: System.out.println(2); break; case 3: System.out.println(3); break; case 4: System.out.println(4); break; case 5: System.out.println(5); break; case 6: System.out.println(6); break; case 7: System.out.println(7); break; case 8: System.out.println(8); break; case 9: System.out.println(9); break; case 100: System.out.println(10); break; case 110: System.out.println(10); break; case 120: System.out.println(10); break; case 130: System.out.println(10); break; case 140: System.out.println(10); break; case 150: System.out.println(10); break; case 160: System.out.println(10); break; case 170: System.out.println(10); break; case 180: System.out.println(10); break; case 190: System.out.println(10); break; case 200: System.out.println(10); break; case 210: System.out.println(10); break; case 220: System.out.println(10); break; default: System.out.println("test"); } } } </code></pre> <p><strong>Corresponding bytecode; again, only relevant parts shown:</strong></p> <pre><code>public static void switcher(int); Code: 0: iload_0 1: lookupswitch{ //23 0: 196; 1: 206; 2: 216; 3: 226; 4: 236; 5: 246; 6: 256; 7: 267; 8: 278; 9: 289; 100: 300; 110: 311; 120: 322; 130: 333; 140: 344; 150: 355; 160: 366; 170: 377; 180: 388; 190: 399; 200: 410; 210: 421; 220: 432; default: 443 } </code></pre> <p>In the first case, with narrow ranges, the compiled bytecode uses a <code>tableswitch</code>. In the second case, the compiled bytecode uses a <code>lookupswitch</code>. </p> <p>In <code>tableswitch</code>, the integer value on the top of the stack is used to index into the table, to find the branch/jump target. This jump/branch is then performed immediately. Hence, this is an <code>O(1)</code> operation.</p> <p>A <code>lookupswitch</code> is more complicated. In this case, the integer value needs to be compared against all the keys in the table until the correct key is found. After the key is found, the branch/jump target (that this key is mapped to) is used for the jump. The table that is used in <code>lookupswitch</code> is sorted and a binary-search algorithm can be used to find the correct key. Performance for a binary search is <code>O(log n)</code>, and the entire process is also <code>O(log n)</code>, because the jump is still <code>O(1)</code>. So the reason the performance is lower in the case of sparse ranges is that the correct key must first be looked up because you cannot index into the table directly.</p> <p>If there are sparse values and you only had a <code>tableswitch</code> to use, table would essentially contain dummy entries that point to the <code>default</code> option. For example, assuming that the last entry in <code>SwitchTest10.java</code> was <code>21</code> instead of <code>10</code>, you get:</p> <pre><code>public static void switcher(int); Code: 0: iload_0 1: tableswitch{ //0 to 21 0: 104; 1: 114; 2: 124; 3: 134; 4: 144; 5: 154; 6: 164; 7: 175; 8: 186; 9: 197; 10: 219; 11: 219; 12: 219; 13: 219; 14: 219; 15: 219; 16: 219; 17: 219; 18: 219; 19: 219; 20: 219; 21: 208; default: 219 } </code></pre> <p>So the compiler basically creates this huge table containing dummy entries between the gaps, pointing to the branch target of the <code>default</code> instruction. Even if there isn't a <code>default</code>, it will contain entries pointing to the instruction <em>after</em> the switch block. I did some basic tests, and I found that if the gap between the last index and the previous one (<code>9</code>) is greater than <code>35</code>, it uses a <code>lookupswitch</code> instead of a <code>tableswitch</code>. </p> <p>The behavior of the <code>switch</code> statement is defined in <a href="http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-3.html" rel="noreferrer">Java Virtual Machine Specification (§3.10)</a>:</p> <blockquote> <p>Where the cases of the switch are sparse, the table representation of the tableswitch instruction becomes inefficient in terms of space. The lookupswitch instruction may be used instead. The lookupswitch instruction pairs int keys (the values of the case labels) with target offsets in a table. When a lookupswitch instruction is executed, the value of the expression of the switch is compared against the keys in the table. If one of the keys matches the value of the expression, execution continues at the associated target offset. If no key matches, execution continues at the default target. [...]</p> </blockquote>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload