Fast Dictionary of Generics in C#
Or How to replace a Dictionary with CLR?
Disclaimer
This article gives an overview of the techniques that can make your code harder to understand and maintain.
Clean code is the priority of development. Developers can effectively implement any performance optimizations only after setting up measurement for Clean code execution.
Dictionary of Generics
Example
Imagine the following hierarchy:
- ICar interface represents general Vehicle interface.
- IElecricCar, IDieselCar, and IGasolineCar implement ICar interface with additional functionality.
- Car A, CarB, Car C, etc., implement a specific interface from the layer above.
Now, let’s assume that we need to put all of these class instances inside some data structure that will allow us to access them by specific interfaces, like getting all IDieselCar or IElecticCar.
The default way to do it will look like that:
Or to reduce complete collection scanning on each get, we can use the Dictionary instead of List:
The downsides of these implementations are:
- Sneaky boxing present in Add method, which will be a NOP for reference-type generic arguments.
- Low type safety, as we can’t guarantee that all ICar in the list will implement interface from dictionary Key.
- And as a result of low type safety, we have extra allocations in the GetCar method caused by LINQ usage. (btw, you can find out more about LINQ and allocations in my other article)
Similar cases in the real world
I have my open-source package called QueryNinja. The main idea of the package is to build and execute queries against IQueryable dynamically.
A similar hierarchy in the example above is implemented to provide a flexible Extensibility Model that allows clients of the packages to extend Core functionality with something project-specific.
In my case, we can draw a few parallels:
- IQueryComponentExtension is like an ICar interface that represents any Extension.
- Any package that extends Core will define its interface on top of base one. Examples are IQueryBuilder or IQueryComponentFactory.
- Any package will define its implementations of these interfaces. Also, a client of the package can implement these interfaces and register implementation in the Core.
However, performance is one of the features of the QueryNinja. And so, the package should minimize any allocations to reduce overall GC pressure. Notice that for my use-case, the time needed to write in the dictionary does not matter. The hot path of the package includes only reading operations.
The Solution
I thought that it would be great to have a generic parameter instead of Type in that dictionary. In this case, we could use the same generic parameter for the list.
And then I recognized that my dictionary is static. After that, a weird idea comes into my mind. I will try to use a Generic static class instead of a dictionary.
In this case, CLR will give us a specific List of cars once we set a generic parameter there.
So, let’s set up some benchmarks on our example hierarchy, and let’s measure the change.
Benchmarks
Setup and Run
For benchmarking, I’m using BenchmarkDotNet.
I will create three classes each one will be static and provide implementation similar to shown in the examples below:
- CarsCollectionList
- CarsCollectionsDictionary
- CarsCollectionGeneric
During the startup, GlobalSetup will fill each collection with an equal amount of each car type.
We can see that even with three cars, the first two options need an extra allocation to get us desired collection of cars. However generic method was so fast that BenchmarkDotNet can’t distinguish it from an empty method call. Let’s try with 30 cars of each type, which will be closer to the QueryNinja case.
The same thing is happening for 30 cars of each type. Also, we can notice a 50% performance difference between List and Dictionary.
Let’s try the same test with 30K cars and look at IL for each method.
Even with the 30K Generic method works seamlessly.
As we can see, the only thing GetCarsGeneric does is a return of the pointer!
After that, I decided to perform this change in my project. Results can be found here.
Why is this happening?
- For List and Dictionary cases, search by specific Type is happening during runtime. List searches linearly, and Dictionary uses HastTable.
- List and Dictionary cases need
OfType<>()call to cast ICar to more specific interfaces. This results in allocations that grow with the number of Cars. - For each closed generic type
CarsCollectionGeneric<>CLR creates a separate static class with a specific type of List. So, each time you work with this static class, you will immediately get the car collection you need. - For
CarsCollectionGeneric<>Jit can inlineGetCars()and so you will immediately get a pointer to the specific list of Cars.
Conclusion
Generics are a powerful mechanism that can dramatically improve the performance of a particular application module.
We reviewed only a basic scenario that helps to reduce allocations and runtime search. There is much more. Check out one of my favorites talks on Micro optimizations in .Net.
Despite the benefits, the maintainability of such solutions remains questionable. Clean code has a more significant priority over performance, especially during the early development phase.
The benefits of any performance improvements can be guaranteed only using stable and repeatable metrics.
Resources
I’m not affiliated with any of the tools except QueryNinja. All recommendations here are tools that I’m using in my work.
