In a switch vs dictionary for a value of Func, which is faster and why?

by

The short answer is that the switch statement executes linearly, while the dictionary executes logarithmically.

At the IL level, a small switch statement is usually implemented as a series of if-elseif statements comparing equality of the switched variable and each case. So, this statement will execute in a time linearly proportional to the number of valid options for myVar; the cases will be compared in the order they appear, and the worst-case scenario is that all the comparisons are tried and either the last one matches or none do. So, with 32 options, the worst case is that it’s none of them, and the code will have made 32 comparisons to determine this.

A Dictionary, on the other hand, uses an index-optimized collection to store values. In .NET, a Dictionary is based on a Hashtable, which has effectively constant access time (the disadvantage being extremely poor space efficiency). Other options commonly used for “mapping” collections like Dictionaries include balanced tree structures like red-black trees, which provide logarithmic access (and linear space efficiency). Any of these will allow the code to find the key corresponding to the proper “case” in the collection (or determine it does not exist) much faster than a switch statement can do the same.

EDIT: Other answers and commenters have touched on this, so in the interest of completeness I will as well. The Microsoft compiler does not always compile a switch to an if/elseif as I inferred originally. It typically does so with small numbers of cases, and/or with “sparse” cases (non-incremental values, like 1, 200, 4000). With larger sets of adjacent cases, the compiler will convert the switch into a “jump table” using a CIL statement. With large sets of sparse cases, the compiler can implement a binary search to narrow the field, and then “fall through” a small number of sparse cases or implement a jump table for adjacent cases.

However, the compiler will typically choose the implementation that is the best compromise of performance and space efficiency, so it will only use a jump table for a large number of densely-packed cases. This is because a jump table requires a space in memory on the order of the range of cases it must cover, which for sparse cases is terribly inefficient memory-wise. By using a Dictionary in source code, you basically force the compiler’s hand; it will do it your way, instead of compromising on performance to gain memory efficiency.

So, I would expect most cases in which either a switch statement or a Dictionary could be used in source to perform better when using a Dictionary. Large numbers of cases in switch statements are to be avoided anyway, as they are less maintainable.

More Related Contents:

  1. Static Generic Class as Dictionary
  2. How to read lines to dictionary with linQ [closed]
  3. Collection was modified; enumeration operation may not execute
  4. Casting vs using the ‘as’ keyword in the CLR
  5. Serialize Class containing Dictionary member
  6. ASP.NET MVC Binding to a dictionary
  7. Are C# uninitialized variables dangerous?
  8. Performance surprise with “as” and nullable types
  9. Get dictionary key by value
  10. How to call .NET methods from Excel VBA?
  11. Duplicate keys in .NET dictionaries?
  12. Is there an IDictionary implementation that, on missing key, returns the default value instead of throwing?
  13. What are major differences between C# and Java?
  14. Float vs Double Performance
  15. What’s the method representation in memory?
  16. Binding DataGrid to ObservableCollection
  17. Sorting a Dictionary in place with respect to keys
  18. How is GetHashCode() implemented for Int32?
  19. How are DLLs loaded by the CLR?
  20. How to switch between “possible” type of an object? [duplicate]
  21. Asynchronous iterator Task
  22. Reverse Sorted Dictionary in .NET
  23. How to debug System.TypeLoadException errors in .NET?
  24. Good way to get the key of the highest value of a Dictionary in C#
  25. How to sort a dictionary by key
  26. C# Convert List to Dictionary
  27. The given key was not present in the dictionary. Which key?
  28. Best way to change dictionary key
  29. Map two lists into a dictionary in C#
  30. Why value-types are stored onto Stacks?

Leave a Comment