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.

Dictionary of Generics

Example

Imagine the following hierarchy:

  • IElecricCar, IDieselCar, and IGasolineCar implement ICar interface with additional functionality.
  • Car A, CarB, Car C, etc., implement a specific interface from the layer above.
Visualized hierarchy example
Example of Cars Collections
Example of Generic Dictionary
  • 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.

  • 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.

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.

The Solution

Benchmarks

Setup and Run

For benchmarking, I’m using BenchmarkDotNet.

  • CarsCollectionsDictionary
  • CarsCollectionGeneric
Benchmark Code
3 Cars
30 Cars
30k Cars
GetCarsGeneric IL

Why is this happening?

  1. For List and Dictionary cases, search by specific Type is happening during runtime. List searches linearly, and Dictionary uses HastTable.
  2. 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.
  3. 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.
  4. For CarsCollectionGeneric<> Jit can inline GetCars() 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.

Resources

I’m not affiliated with any of the tools except QueryNinja. All recommendations here are tools that I’m using in my work.

Source Code

Articles

Tools Used

Lead Software Engineer at EPAM

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store