8 May 2017

Exploring Multiple Dispatch in C# with BenchmarkDotNet

A few years ago, Jakub Chodounsk√Ĺ made an excellent post about Dynamic Dispatch in C#. He discussed the relations between static, dynamic, single, and multiple dispatch, and covered a few ways to get Multiple Dispatch behavior in C#:
  • Casting to Dynamic
  • Dictionary of types
  • Visitor pattern
If you're not familiar with some of these terms, I'd highly recommend reading his post.
In addition to the above approaches, C# 7 added pattern matching, which can be used in a similar way as the "Dictionary of types."
Out of all of these, 'Casting to Dynamic' appears to be the most elegant, but it comes at a performance cost. I was curious what sort of performance cost was involved: is it orders of magnitude slower? In this post, I'll benchmark these multiple dispatch approaches, using the BenchmarkDotNet library from Microsoft. From their README:
Benchmarking is really hard (especially microbenchmarking), you can easily make a mistake during performance measurements. BenchmarkDotNet will protect you from the common pitfalls (even for experienced developers) because it does all the dirty work for you: it generates an isolated project per each benchmark method, does several launches of this project, run multiple iterations of the method (include warm-up), and so on.
In the spirit of eating dessert first, here are the results of the benchmark. After the results, I'll walk through the benchmark code, or you can grab the full solution on github.

Dictionary-Based47.15 us0.3831 us0.3584 us
Casting to Dynamic71.28 us0.1822 us0.1423 us
If-Else Pattern Matching17.86 us0.1726 us0.1530 us
Switch-Case Pattern Matching17.75 us0.2170 us0.2030 us
Visitor Pattern19.76 us0.0667 us0.0482 us

Machine and Platform Specifications

BenchmarkDotNet=v0.10.5, OS=Windows 10.0.15063
Processor=Intel Core i5-4440 CPU 3.10GHz (Haswell), ProcessorCount=4
Frequency=3020349 Hz, Resolution=331.0876 ns, Timer=TSC
dotnet cli version=1.0.3
  [Host]     : .NET Core 4.6.25009.03, 64bit RyuJIT
  DefaultJob : .NET Core 4.6.25009.03, 64bit RyuJIT

Interpreting the Results

My interpretation of these results is that all of these approaches are in the same order of magnitude. The dynamic approach is 4 times slower than pattern matching with if/else or switch/case, but I don't think that will be a bottleneck in most applications. It should be fine to use dynamic in places that aren't high-throughput, critical paths.
Additionally, while these numbers can serve as a general guide, if you're finding the need to performance-tune your own system, you should benchmark that system and not rely on microbenchmarks like this.

Benchmarking with BenchmarkDotNet

The above results and graphs were generated with BenchmarkDotNet. Here are the types I dispatched and the methods I dispatched to:
When writing benchmarks in BenchmarkDotNet, you write a single class, and then each scenario you want to benchmark is a separate method in this class, decorated with the [Benchmark] attribute. This way, you can have shared input for the benchmark set up in the constructor. Our shared input is a random array of 1000 shapes:
After we have our input, it's as simple as writing a method for each implementation, and adding the [Benchmark] attribute. We make sure to return the calculated values from each benchmark, so we don't have issues with dead-code elimination optimizing away our benchmark!

(If you're not sure why we need the <dynamic, string> type parameters, you should go read Jakub's original blog post!)
The Dictionary benchmark is similar, but it needs to do some one-time setup of the dictionary:

Using Pattern Matching has a similar structure to the Dictionary-based approach:

And finally, the Visitor implementation. The visitor pattern requires us to modify our shapes to support visiting (which we do by implementing the IVisitee interface on each shape). We take our original shapes input and map it to these new ShapeVisitee classes. Then we have a standard Visitor pattern to dispatch these new objects:

And that's the end of benchmark script! Now we just need to invoke it:

For the best results when we run the application, we need to:
  • Compile the application in release mode
  • Run it from the command line, with all other applications closed
  • If you're on a laptop, make sure you're not running in low power mode
And that's it! You can find more information about BenchmarkDotNet on their website.