Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

So what happens when you write a complex switch statement that doesn't contain contiguous case elements?  Have you ever checked the IL to find out?  I am going to examine a large number of switch statements, their performance ramifications, and their IL.  My primary concern is how the C# compiler handles the degenerate case statement, and how I can optimize the system to fix potential issues.

First, let's start with a simple example.  We are going to switch on an int datatype with the case labels ranging from 0 to 2.  This should be simple enough (note this is the only time I'm going to show the C# code, with the remainder of the code samples being the IL generated):

using System;

public class SwitchFromZeroToTwo {
    private static void Main(string[] args) {
        int foo = int.Parse(args[0]);
       
        switch(foo) {
            case 0:
                Console.WriteLine(foo);
                break;
            case 1:
                Console.WriteLine(foo);
                break;
            case 2:
                Console.WriteLine(foo);
                break;
        }
    }
}

The resulting IL will make a lot of sense.  Turns out the switch statement in IL is fairly similar to the C# version, only it uses a jump table of labels in the beginning.  The statement pops a single value off the stack (in our case foo), and then compares it to the number of items in the jump table.  A value of zero for foo will map to the first jump table entry, while a value of jumpTableLength - 1 will map to the final entry in the jump table.  Note the jump table is contiguous and has jumpTableLength entries.  Here is the prominent IL:

IL_0002:  ldloc.0
IL_0003:  switch     (
                      IL_0016,
                      IL_001e,
                      IL_0026)
IL_0014:  br.s       IL_002e

So each label maps to one of our case labels.  That works.  So what happens when we offset our case statements?  Say the go from 3 to 5 instead of 0 to 2?  Well, we add a subtraction to the equation to realign the values so that a value of 3 will map to the first entry in the jump table.  This adds a bit of extra overhead and so a zero aligned series of case statements will always outperform an offset version, at least by a little bit.

    IL_0002:  ldloc.0
    IL_0003:  ldc.i4.3
    IL_0004:  sub
    IL_0005:  switch     (
                          IL_0018,
                          IL_0020,
                          IL_0028)
    IL_0016:  br.s       IL_0030

I want to mix it up a bit more though.  What happens if I go from 0 to 2, then jump to 4?  Well, hell, they insert 3 for me, however, it instantly jumps to the default case or out of the switch statement since I don't have one.  So now degenerate case statements can cause small amounts of memory bloat?  It appears so.  Even if it is only a single jump table offset in memory, are there ways we can force the compiler to create even more code bloat?

    IL_0002:  ldloc.0
    IL_0003:  switch     (
                          IL_001e,
                          IL_0026,
                          IL_002e,
                          IL_003e,
                          IL_0036)
    IL_001c:  br.s       IL_003e

So logically we should be able to find where the cut-off is.  I mean how much memory is wasted if we create degenerate case statements?  Well, jumping to both 5 and 6 simply filled in the gaps in the jump table.  Finally, after jumping up to 7, we get a new IL construct to talk about.  You see, we get the normal switch table for 0 to 2, but then we get a normal branching statement (similar to an if statement) for the 7 case.  I'm pretty sure once this happens you are losing some of the performance of the switch statement.  You see, to make a jump, a switch table only has to do a comparision to see if a value is greater than or equal to the length of the switch table.  Why only greater/equal and why aren't we checking for less than 0?  Because we are working with unsigned numbers.  the numbers less than 0 actually show up as greater than the length of the jump table.  Here is a small program demonstrating this short-cut:

using System;

public class LessButGreater {
    private static void Main(string[] args) {
        int foo = 30;
        int bar = -40;
       
        uint baz = (uint)bar;
       
        Console.WriteLine(bar < foo);
        Console.WriteLine(baz < foo);
    }
}

Okay, so now we know a single comparison is need to get into the jump table or jump past the switch.  That is pretty darn cool.  Individual if statements would require additional comparisons and logic for each value.  So adding the extra comparison will in some cases up to double our processing time.  The next change in the IL construct comes when I add another case statement for 8.  Now we have 0 to 2 and 7 to 8.  This sill immediately change our IL right back to the very fast switch statement, now with 5 real cases and 4 empty jump table slots.  That is a memory loss of almost 50%, but we are getting some great speed out of it.

    IL_0002:  ldloc.0
    IL_0003:  switch     (
                          IL_002e,
                          IL_0036,
                          IL_003e,
                          IL_0056,
                          IL_0056,
                          IL_0056,
                          IL_0056,
                          IL_0046,
                          IL_004e)
    IL_002c:  br.s       IL_0056

Yet again moving the range we discover one last IL construct.  This IL construct is the multiple switch block.  It turns out with the properly formatted degenerate set of case statements, we can really hammer the resulting code and enlarge it quite a bit.  We can have a fragmented heap of multiple switch statements and branching statements resulting from a single switch statement in our C# code.  Here is the resulting code from the 0 to 2, 8 to 9 case.

    IL_0002:  ldloc.0
    IL_0003:  switch     (
                          IL_0026,
                          IL_002e,
                          IL_0036)
    IL_0014:  ldloc.0
    IL_0015:  ldc.i4.8
    IL_0016:  sub
    IL_0017:  switch     (
                          IL_003e,
                          IL_0046)
    IL_0024:  br.s       IL_004e

Let's bring this home with some oddball cases.  How about Flags based enumerations?  You'd hope we would get a really nicely laid out jump table right?  Well, you are wrong my friend.  Of course we get at least one switch statement, but now it is oddly enough formatted as a branch statement, a switch statement, then a few more branch statements.  This is only going up to bit 6.  If you went through the rest of the bits, you'd be smacked in the face by a bunch of branch statements.  Now, stop me here, since normally, you wouldn't think of using flags in this manner, because multiple flags can be set at the same time.  I'll certainly agree with that.  I just used this to point out that if your enumeration values aren't contiguous the same fragmentation is going to be happening behind the scenes.

    IL_0004:  ldloc.1
    IL_0005:  ldc.i4.8
    IL_0006:  bgt.s      IL_0026

    IL_0008:  ldloc.1
    IL_0009:  ldc.i4.1
    IL_000a:  sub
    IL_000b:  switch     (
                          IL_0032,
                          IL_003a,
                          IL_0062,
                          IL_0042)
    IL_0020:  ldloc.1
    IL_0021:  ldc.i4.8
    IL_0022:  beq.s      IL_004a

    IL_0024:  br.s       IL_0062

    IL_0026:  ldloc.1
    IL_0027:  ldc.i4.s   16
    IL_0029:  beq.s      IL_0052

    IL_002b:  ldloc.1
    IL_002c:  ldc.i4.s   32
    IL_002e:  beq.s      IL_005a

    IL_0030:  br.s       IL_0062

Some tips for using switch statements in the future are what we need I think

  • I would highly recommend maintaining contiguous blocks since that seems to create the most compact switch statement.
  • Watch out for holes in your case ranges since they can definitely eat up extra memory.
  • Try not to use Flags enumerations in your switch statements.  I've seen some people make this mistake, so don't fall prey to it.
  • If you have multiple disparate ranges (0 to 2, 10 to 15, 24 to 80), try using an if statement instead.  It might turn out to be faster.
  • If you have evenly spaced numbers (3 6 9 12, etc...), then normalize the data first (div 3), and use the result.
  • Be aware that you are going to be adding a sub command for all non zero based case statements.  In many cases I think the C# compiler might fix this for you, but if you have something like 2 to 8, try adding a case 0 and 1, to get rid of the sub statement.
  • This isn't in the article, but always use chars instead of single character strings when doing that type of switch.  I've seen so many people make the mistake of a switch(foo.Substring(0, 1)), that it isn't even funny.  If you use foo[0], it will map to a char, and do a basic switch statement without enacting the string interning. 
  • Also, doing a switch on a single character string results in a branching version, until a special threshhold is met that enacts the Hashtable version.  The Hashtable version uses loads all of the strings, boxes the offsets into the jump table, and then compares the input against the hashtable to get the jump table bucket.  This bucket is then used instead of doing a bunch of branching statements.
Published Thursday, March 25, 2004 12:12 AM by Justin Rogers

Comments

Saturday, February 2, 2008 6:35 PM by drinian

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

Thanks! Very helpful!

Saturday, December 15, 2012 3:53 AM by detViara

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

buy <a href="http://e--store.com/ ">coach bags outlet</a>  online shopping   TfOZWYzt  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Saturday, December 15, 2012 5:05 AM by Priscimi

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

click to view <a href="http://e--store.com/ ">outlet coach</a>  , for special offer   akNXWEUz  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Sunday, December 16, 2012 7:59 AM by confiecy

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

you definitely love <a href="http://e--store.com/ ">loui vuitton outlet</a>  at my estore   mWlSeFpf  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Monday, December 17, 2012 3:57 PM by cyncNask

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

you love this?  <a href="http://e--store.com/ ">lv online</a>  for less   wMwePYea  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Monday, December 17, 2012 4:46 PM by Anedenaw

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

I'm sure the best for you <a href="http://e--store.com/ ">coach outlet online</a>  , just clicks away   wTJfTdIF  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Tuesday, December 18, 2012 1:13 AM by Anedenaw

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

I am sure you will love <a href="http://e--store.com/ ">prada outlet online</a>  with low price   vAjUNfTj  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Wednesday, December 19, 2012 5:29 AM by Priscimi

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

order an <a href="http://e--store.com/ ">loui vuitton outlet</a>  online   pMFMZBJx  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Thursday, December 20, 2012 1:49 AM by cyncNask

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

sell <a href="http://e--store.com/ ">lv online</a>  to your friends   SjqFpJbz  <a href="http://e--store.com/ "> http://e--store.com/ </a>

Tuesday, December 25, 2012 9:40 PM by Lowtwera

# re: Be careful what you switch for... (examining degenerate case statements, in the C# switch statement)

I'm sure the best for you <a href="http://e--store.com/ ">outlet louis vuitton</a>  with confident   DuJZFNyA  <a href="http://e--store.com/ "> http://e--store.com/ </a>