Apophis
Mar23rd ’09 1:03 pm

if-else vs. switch vs. Dictionary of delegates (C#)

Posted by Apophis

,

2455 Comments

Fast Switching

While developing a Patch for the DCC support of SmartIrc4Net I rewrote the CTCP handling. Instead of a switch Statement I developed a Dictionary<string, ctcpDelegate> for the handling of the CTCP String. (i.e. I call the ctcp Handler after a Dictionary lookup of the CTCP String).

There are several Advantages to this:

  1. It's dynamic, you can add other CTCP handlers on runtime, even out of the library, since I exposed the Dictionary to the public interface. In that way even plugins can add new CTCP functionality, which doesn't belong to the library, like CTCP for XDCC downloads. The library only needs to support the bare minimum. I used it to add the DCC Handler in a seperate class.
  2. The "switch" can be splittet to different sections.
  3. The "switch" is pretty clean, the handling is done in seperate methodes. (can be negative, since you even need a Method for 1+1;
  4. You can use your own comparer for the dictionary, (like a case-insensitive one). 

Since CTCP has only rare occurences I didn't thought about a performance impact, even if it would be really slow, it wouldnt really matter. However right now I am developping a little IRC Daemon in C# for some experiments.

I searched with google for an answer, the only one I could find said, Dictionary is constant time, but DON'T use it for timecritical things. After the tests I have to massivly disagree, Dictionaries and Invoke are highly performant!

The protocol parsing has to switch on a long list of commands, "JOIN", "PART", "PRIVMSG" and so forth. And the switch gets really ugly, so a Methodcall might be interesting in some complexer cases, however there are very simple ones too. So I was interested in the impact of the switch vs. Dictionary Method.

So I wrote a program to mesaure the impact of the 3 different "switching method" a long list of "if else"-statements, a switch statement, the pretty Dictionary statement.

I made 3 tests, once with 5, 50 and 500 cases, each test was run 100 Million times, 5 times in a row (so JIT and cache could kick in) the if and switch cases did nothing in their respecitve blocks (no method call) the Dictionary case did the actual Invoke to an empty delegate.

The result:

5 cases - 100 Mio times

  • If: ~7.2 sec
  • Switch: ~7.0 sec
  • Dictionary: ~9.1 sec

50 cases - 100 Mio times

  • If: ~36 sec
  • Switch:  ~9.1 sec
  • Dictonary: ~6.9 sec

500 cases - 100 Mio times

  • If:  more than 300 seconds...
  • Switch: ~10 sec
  • Dictionary: ~6.8 sec

Now the result is more interesting than you might think, the If case scales undoubtatly linear! but it's competitive with upto 10 cases. with 5 cases it is still faster than any other method. ( O(n) )

The switch has a slight increase of about 1 seconds per 10 times more cases, this means it scales about logarthmically, which would also be correct if I remember correctly that the switch statement was actually implemented as some sort of tree. in a balanced tree a lookup should scale logarthmically. ( O(log(n)) )

The Dictionary now is a very strange case, it looks like it gets faster the more cases you add to the dictionary. Now we know, that's simply not possible. So what happened? 

My Theory: I distributed the testcases evenly on all cases, also on the default case. So in every 6th case in the first example we have a default (a failed dictionary lookup), in the following example its only every 51st and 501st case in which this happens. If we suppose a failed dictionary lookup takes more time than a successfull one this would exactly describe the observation. This method has a constant Time for our switch and the actual overhead is small but measurable and its the slowest method with less than maybe 10 cases. ( O(1) )

My conclusion: Dictionaries are not only not that bad in performance terms, they are actually more than just competitive for medium sized case lists and are by far the fastest method for huge case lists!

You want to test yourself? here is the source!

Comments

No one has commented on this page yet.

Post your comment

RSS feed for comments on this page | RSS feed for all comments

Infos

  • About
  • Privacy Policy

Hotlinks