2017-03-18 - In IL: Prize Calculator (switch-2)

In IL

• Part 1 - Introduction
• Part 2 - Variables and Types
• Part 3 - Variables in Visual Basic .NET
• Part 4 - Instructions and the Stack
• Part 5 - Volume of a Cylinder (Operations)
• Part 6 - Branching Instructions
• Part 7 - Largest of Two Numbers (if-else)
• Part 8 - Largest of Three Numbers (If-ElseIf-Else)
• Part 9 - Switch instruction
• Part 10 - Grade Analyser (switch)
• Part 11 - Prize Calculator (switch-2)
• Part 12 - VB Grade Analyser (Select)
• Part 13 - Loop Instructions
• Part 14 - Print the Alphabet (while)
• Part 15 - Print the Alphabet (do while, for)
• Part 16 - Print the Alphabet (Do Until)
• Part 17 - Print the Alphabet (break, continue)
• Part 18 - Array Instructions
• Part 19 - Summing Arrays
• Part 20 - Other Instructions
• Part 21 - Assemblies
• Part 22 - Class Definitions
• Part 23 - C# Classes and Structs
• Part 24 - VB Classes, Modules and Structures
• Part 25 - Field Definitions
• Part 26 - Field Declarations

Last time we looked at a switch statement in C# which was implemented in IL by the switch instruction. The IL switch instruction is a lot more restrictive than the C# switch statement, for example the instruction expects its options to be continuous and only supports integers. The statement on the other hand can have large gaps between its options and also supports strings. So what happens when we have a switch statement that can't easily be implemented using the instruction?

The following program determines a user's prize based on a number. Only specific numbers get prizes and there's large gaps between winning numbers.

Their are 12 options with a range of 3009. That would require the switch instruction to have an array with 3009 addresses where 2997 of them point to the default case. Let's see what the compiler generates for us.

The compiler generated a ton of branching statements but no switch instructions. So what are those branching instructions doing? Let's map them out.

• Line 68: Branch if Position > 1054
  • Line 104: Branch if Position > 2513
    • Line 122: Branch if Position = 2668
      • Line 171: Print "You win a toque"
    • Line 126: Branch if Position = 2998
      • Line 175: Print "You win a pot of gold"
    • Line 130: Branch if Position = 3054
      • Line 179: Print "You win a mouse"
    • Line 132: Branch
      • Line 183: Print "You win nothing"
  • Line 108: Branch if Position = 2045
    • Line 159: Print "You win a carrot"
  • Line 112: Branch if Position = 2012
    • Line 163: Print "You win a teddy bear"
  • Line 116: Branch if Position = 2513
    • Line 167: Print "You win a double cheeseburger"
  • Line 118: Branch
    • Line 183: Print "You win nothing"
• Line 72: Branch if Position > 513
  • Line 90: Branch if Position = 668
    • Line 147: Print "You win a hat"
  • Line 94: Branch if Position = 998
    • Line 151: Print "You win a potted plant"
  • Line 98: Branch if Position = 1054
    • Line 155: Print "You win a house"
  • Line 100: Branch
    • Line 183: Print "You win nothing"
• Line 76: Branch if Position = 45
  • Line 135: Print "You win a car"
• Line 80: Branch if Position = 102
  • Line 139: Print "You win a TV"
• Line 84: Branch if Position = 513
  • Line 143: Print "You win a cheeseburger"
• Line 86: Branch
  • Line 183: Print "You win nothing"

It starts by branching if the number is greater than 1054. This is the middle option of our switch statement. If it is greater than 1054 it then branches if the value is greater than 2513, else it continues on and branches if the value is greater than 513. 2513 is the middle option of the block greater than 1054 and 513 is the middle option of the block less than or equal to 1054. You may recognize this process of repeatedly dividing the options in half and checking if the value is greater than or less than the half way value as binary search. Instead of checking every value it checks ranges and focuses in on the value. It only checks for equality when it gets down to a few remaining options. This way it only takes 5 comparisons to get to the largest value of 3054 instead of 12. Now let's go a step further and see what happens if we use strings instead of integers.

As you can see this program is similar to the first except it uses a string variable and string case statements. Let's see what it compiles into.

That's follows the same basic flows as the integer case but with a few differences. Firstly on line 68 the compiler used an internal function to generate a hash value for the string which is a unsigned integer and then it compares the computed hash against the pre-computed hashes for the string cases. Secondly instead of branching directly to the print statements it branches to a call to the string's equality function. This is to ensure that string actually matches the desired value and doesn't just have the same hash value.

Next time we will look at the Visual Basic .NET Select statement and see how it handles even more complicated cases.