switch: Chain, Table, or Binary Search

The point

switch is the first construct where the obvious implementation and the fast one genuinely differ, and where the right answer depends on the input.

Do this

1. Lower this by hand using dispatch-then-bodies. Get the fall-through right — case 2 has no break.

   switch (x) {
       case 1: print(10); break;
       case 2: print(20);
       case 3: print(30); break;
       default: print(0);
   }

2. Hand-execute for x = 1, 2, 3, 9. For x = 2, what prints? Two numbers. Be sure you can say why before implementing anything.
3. Design the jump-table version on paper for the same switch. What goes in the table? What happens for a value outside the range? What happens if the cases were 1 and 5 with nothing between?
4. Cost all three strategies against these four distributions, and say which you would choose for each:
   • 3 cases with values 1, 2, 3
   • 3 cases with values 1, 1000, 50000
   • 200 cases with values 1..200
   • 200 cases scattered over 0..2,000,000
5. Implement the linear chain and verify against your hand execution.
6. Add two semantic checks: at most one default, and no duplicate case values. Test both, and write one sentence saying why neither could be a grammar rule.