C# internals: string switch statement

I really enjoy learning new architectures, design patterns, frameworks, libraries or in general – everything related to web development. I really do. But honestly, after quite long time all these stuff became a little bit… boring. To avoid possible burnout I decided to play with something completely different. My thoughts circled around functional programming (F#, Heskel), IoT, quantum programming in Q# and much more, but none of them felt right. Enlightenment came by accident when YouTube suggested me a video about… C# internals. For the very first time in my life, I had „flow” while watching something, not coding. The brave new world that seemed very similar and odd at the same time…
So, after this „literary” introduction I want to welcome you to new series of interesting C# internals. I believe that at least some of you will like it although the knowledge I’m going to pass is not very „practical” in everyday work. On the other hand, knowing exactly what’s happening under the hood of C# might be helpful in the future, especially when it comes to the performance. Oh, and one more thing before we start. I don’t have any plan specified for this series. I’m not that deep into the subject, I’m still discovering lots of things. Therefore I can’t tell you now, whether new parts will be published regularly and what exactly will be described. We will see. All right, let’s get started.

 

String switch statement in C#

In almost every programming language we can find switch statement and C# is no exception here. Of course, both syntax and circumstances in which it should be used are trivial, since it is a basic stuff that every beginner learns, right? If we would ask statistical C# developer when he uses a switch statement, he would probably say something like:

Well, if you have multiple conditions to check you should rather choose switch statement instead of multiple if statements… blah blah performance…. blah blah… jump tables

To be clear, I also used that kind of argumentation simply because I considered it to be true. But here’s the thing – it doesn’t have to be that way. At least not when it comes to C#… and switch based on a string.

What so special about string switch-case in C#? Well, first of all, the fact that it exists (unlike C, C++ or Java in versions lower than 7). That is weird when you think about an argument for using switch statement – performance. Comparing two integers is a simple thing because there’re instructions for that on the CPU level. Things are a little bit more complicated with the string because it’s a chain of characters. So in this case, we need to loop through the string and do the comparison with the corresponding character from the other one. Besides that, there’re some additional cases that need to be checked but I’ll leave it to you. If you’re curious how both comparisons are implemented in C#, below I put the links to referencesource.microsoft.com:

Back to the story, knowing that string is not the ideal candidate to be used inside switch statement we should ask the question. Does C# compiler do some optimization to make it more efficient? Let’s find out! Here’s a very simple example:

 


        public void Run(string argument)
        {
            switch (argument)
            {
                case "Case1":
                    Console.WriteLine("Case1");
                    break;
                case "Case2":
                    Console.WriteLine("Case2");
                    break;
                case "Case3":
                    Console.WriteLine("Case3");
                    break;
                case "Case4":
                    Console.WriteLine("Case4");
                    break;
                case "Case5":
                    Console.WriteLine("Case5");
                    break;
                case "Case6":
                    Console.WriteLine("Case6");
                    break;
            }
        }

 

In order to find out what is actually generated by the compiler, I’m going to use free .NET decompiler created by JetBrains called dotPeek. After loading the assembly with the above code we can see the following:

 


public void Run(string argument)
    {
      string str = argument;
      if (!(str == "Case1"))
      {
        if (!(str == "Case2"))
        {
          if (!(str == "Case3"))
          {
            if (!(str == "Case4"))
            {
              if (!(str == "Case5"))
              {
                if (!(str == "Case6"))
                  return;
                Console.WriteLine("Case6");
              }
              else
                Console.WriteLine("Case5");
            }
            else
              Console.WriteLine("Case4");
          }
          else
            Console.WriteLine("Case3");
        }
        else
          Console.WriteLine("Case2");
      }
      else
        Console.WriteLine("Case1");
    }

 

So it looks like, this whole story about the performance is just a myth, right? Why should we even use string switch statement if the compiler ignores that and generates a bunch of ifs instead. That’s ridiculous! Well, not exactly. Let me modify the code by adding one more case:

 


        public void Run(string argument)
        {
            switch (argument)
            {
                case "Case1":
                    Console.WriteLine("Case1");
                    break;
                case "Case2":
                    Console.WriteLine("Case2");
                    break;
                case "Case3":
                    Console.WriteLine("Case3");
                    break;
                case "Case4":
                    Console.WriteLine("Case4");
                    break;
                case "Case5":
                    Console.WriteLine("Case5");
                    break;
                case "Case6":
                    Console.WriteLine("Case6");
                    break;
                case "Case7": // <------ 7th case
                    Console.WriteLine("Case7");
                    break;
            }
        }

 

Take a look at the generated code right now:

 


public void Run(string argument)
    {
      string s = argument;
      uint stringHash = \u003CPrivateImplementationDetails\u003E.ComputeStringHash(s);
      if (stringHash <= 3830722905U)
      {
        if ((int) stringHash != -514577248)
        {
          if ((int) stringHash != -481022010)
          {
            if ((int) stringHash != -464244391 || !(s == "Case2"))
              return;
            Console.WriteLine("Case2");
          }
          else
          {
            if (!(s == "Case3"))
              return;
            Console.WriteLine("Case3");
          }
        }
        else
        {
          if (!(s == "Case1"))
            return;
          Console.WriteLine("Case1");
        }
      }
      else if (stringHash <= 3864278143U)
      {
        if ((int) stringHash != -447466772)
        {
          if ((int) stringHash != -430689153 || !(s == "Case4"))
            return;
          Console.WriteLine("Case4");
        }
        else
        {
          if (!(s == "Case5"))
            return;
          Console.WriteLine("Case5");
        }
      }
      else if ((int) stringHash != -413911534)
      {
        if ((int) stringHash != -397133915 || !(s == "Case6"))
          return;
        Console.WriteLine("Case6");
      }
      else
      {
        if (!(s == "Case7"))
          return;
        Console.WriteLine("Case7");
      }
    }

 

This looks completely different. Instead of comparing strings, there are some weird numbers compared with stringHash variable. What is that?! I think it’s a good time to ask more questions:

  • What are these number?
  • What contains PrivateImplementationDetails class
  • Do the „7 cases” are magic threshold for enabling the optimization?
  • Does it even pay off to do that?

Let’s start answering those questions one by one.

 

PrivateImplementationDetails class and weird numbers

In order to answer the first question, we shall start with answering the second one since it is PrivateImplementationDetails class which provides a stringHash variable for later comparisons. When we navigate in dotPeek to the actual implementation we can see the following code:

 


internal sealed class \u003CPrivateImplementationDetails\u003E
{
  internal static uint ComputeStringHash(string s)
  {
    uint num;
    if (s != null)
    {
      num = 2166136261U;
      for (int index = 0; index < s.Length; ++index)
        num = (uint) (((int) s[index] ^ (int) num) * 16777619);
    }
    return num;
  }
}

 

As you see this class contains only one method called ComputeStringHash which does some weird magic constant numbers, xor and multiplying. To find out what it actually does we can visit referencesource.microsoft.com once again and find something responsible for generating the above class. It is a MethodBodySynthesizer.Lowered.cs file which contains the following summary:

Compute the hashcode of a sub string using FNV-1a See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function

Nice, we’ve got it! A ComputeStringHash method is nothing more but the implementation of the Fowler–Noll–Vo non-cryptographic hash function. We can verify that by analyzing the pseudo code given by Wikipedia:

 


 hash = FNV_offset_basis
   for each byte_of_data to be hashed
        hash = hash XOR byte_of_data
        hash = hash × FNV_prime
   return hash

 

Indeed, the ComputeStringHash does exactly that. What’s worth to mention is the fact that both FNV_offset_basis (2166136261U) and FNV_prime (16777619) are calculated for 32 bits (according to the table in the wiki). These are fixed numbers placed inside MethodBodySynthesizer.Lowered class (lines 90 and 105).

Ok, we’ve already answered one question. PrivateImplementationDetails is responsible for calculating a numeric hash for given string argument using FNV-1a function. This is probably related to the problem described in the previous paragraph – comparing integers is much faster than comparing string. We still don’t know what are the numbers put into if statements. Let’s use discovered code to calculate a hash for each label we used in switch-case (i copied that to VS2017). The results are:

  • case1: 3780390048
  • case2: 3830722905
  • case3: 3813945286
  • case4: 3864278143
  • case5: 3847500524
  • case6: 3897833381

All the above numbers are UInt32 but when you go back to the weird numbers from the previous paragraph, you can spot that in most cases there’s an additional cast to Int32. Let’s do this for each number:

  • case1: 3780390048U -> -514577248
  • case2: 3830722905U -> -464244391
  • case3: 3813945286U -> -481022010
  • case4: 3864278143U -> -430689153
  • case5: 3847500524U -> -447466772
  • case6: 3897833381U -> -397133915

Now all is clear – all these weird numbers are nothing more but the results of the ComputeStringHash method for each string label. Then the compiler creates all if statements (in kinda weird order) and adds additional conditions for some of them like in here:

 


if ((int) stringHash != -464244391 || !(s == "Case2"))

 

I believe this is in case of possible collisions but I’m not 100% sure.

 

Discovering „breaking point” of optimization

In the first paragraph, I added a 7th case to the switch in order to enable the optimization. The question is whether this is a fixed number? Does it depend on other, unknown conditions? To find it out we are going to visit again… you know what. The hint is placed inside LocalRewriter_SwitchStatement.cs file:

For string switch statements, we need to determine if we are generating a hash table based jump table or a non hash jump table, i.e. linear string comparisons with each case label. We use the Dev10 Heuristic to determine this (see SwitchStringJumpTableEmitter.ShouldGenerateHashTableSwitch() for details).

All right, let’s see the implementation of the ShouldGenerateHashTableSwitch method:

 


        internal static bool ShouldGenerateHashTableSwitch(CommonPEModuleBuilder module, int labelsCount)
        {
            return module.SupportsPrivateImplClass && ShouldGenerateHashTableSwitch(labelsCount);
        }
 
        private static bool ShouldGenerateHashTableSwitch(int labelsCount)
        {
            // Heuristic used by Dev10 compiler for emitting string switch:
            //  Generate hash table based string switch jump table
            //  if we have at least 7 case labels. Otherwise emit
            //  direct string comparisons with each case label constant.
 
            return labelsCount >= 7;
        }

 

We have another answer! 7 is indeed a „breaking point” for enabling a hash table optimization.

 

Does it pay off?

So far we know that having more than 6 cases inside string switch causes the compiler to do some magic behind in order to increase the performance. The last question is very simple. Does this whole magic pay off? Is it faster than nonoptimized switch or bunch of else-if statements. Let’s measure it using a BenchmarkDotnet. I created a simple project which contains three classes (one for each variant) :

 


    [CoreJob]
    [AsciiDocExporter, HtmlExporter]
    public class ElseIf
    {
        [Params("Case1", "Case2", "Case3", "Case4", "Case5", "Case6")]
        public string Argument { get; set; }

        [Benchmark]
        public void Run()
        {
            if(Argument == "Case1")
            {
            }
            else if(Argument == "Case2")
            {
            }
            else if (Argument == "Case3")
            {
            }
            else if (Argument == "Case4")
            {
            }
            else if (Argument == "Case5")
            {
            }
            else if (Argument == "Case6")
            {
            }
            else if (Argument == "Case7")
            {
            }
        }
    }

    [CoreJob]
    [AsciiDocExporter, HtmlExporter]
    public class NonOptimizedSwitch
    {
        [Params("Case1", "Case2", "Case3", "Case4", "Case5", "Case6")]
        public string Argument { get; set; }

        [Benchmark]
        public void Run()
        {
            switch (Argument)
            {
                case "Case1":
                    break;
                case "Case2":
                    break;
                case "Case3":
                    break;
                case "Case4":
                    break;
                case "Case5":
                    break;
                case "Case6":
                    break;
            }
        }
    }

    [CoreJob]
    [AsciiDocExporter, HtmlExporter]
    public class OptimizedSwitch
    {
        [Params("Case1", "Case2", "Case3", "Case4", "Case5", "Case6")]
        public string Argument { get; set; }

        [Benchmark]
        public void Run()
        {
            switch (Argument)
            {
                case "Case1":
                    break;
                case "Case2":
                    break;
                case "Case3":
                    break;
                case "Case4":
                    break;
                case "Case5":
                    break;
                case "Case6":
                    break;
                case "Case7":
                    break;
            }
        }
    }

 

Each Run method will be called several times for each string label starting from „case1”, ending on „case6” (nonoptimized switch cannot have more). Below are the results in the Release without the attached debugger (so the VS2017 was closed):

 

optimized switch

 

nonoptimized switch

 

else-if

 

There are two, interesting things here. First, both elfe-if and nonoptimized switch had very close results. This is, of course, logical because as you’ve already known the compiler generates if statements if there are less than 7 cases. Therefore we could expect this kind of result here. The second thing is that optimized switch is actually slower only for „case1”. I believe that this is due to the code arrangement on the IL level. For all further cases, this solution is faster and more importantly, the execution time does not increase significantly. So to sum it up – yes, this whole magic behind the scenes actually pays off!

 

Summary

I hope you enjoyed the first part of this series (I really did!). As you see, the popular statement that switch-case is always faster in C# is not true. There’re some scenarios when this doesn’t matter that much. For your information, I put the benchmark app on my GitHub so you can easily clone it and try it yourself. And one more thing. Please share your opinions about this kind of article down in the comments. Maybe I could do something better 😉

You may also like...