ImmutableList<T> performance

This a short story followed by simple .NET hint that can increase performance in some areas of your application in 10 times or more.

In the HPS project I've implemented the same state machine simulation engine in three technologies: C++, .NET Core/C# and Go. It is a nice learning project if you are learning one of the language. At some moment, while benchmarking the solutions  I've noticed a dramatic difference in performance between .NET version and C++. In average, .NET version run by order of magnitude slower than C++ or Go. Hm...

I've read many times that the performance of a .NET version usually is very similar to C++, but usually C++ is a bit faster. 10x is definitely too big for "a bit" so I've started investigating.

While simulating, the HPS engine iterates many times over a list of state machines. List is a simple data structure. It is just a wrapper around the array. Iterating performance should be as fast as iterating over an array.

I found that the problem is iterating over the list. It is in many times slower that iterating vector in C++. Iterating over ImmutableList took more than 80% of the time. Ok, I've searched why it is so and found that ImmutableList is, in fact, a tree.

Um... Stop.

A tree.

I had been refactoring  the code and replaced one of the lists to its immutable version. I replaced List with ImmutableList. Well, I had List, I wanted immutable list, here is ImmutableList, no brainer.

But it is a tree.

Thee is a different data structure. Iterating trees is completely different from iterating arrays. The stack for current path should be maintained, there are a lot of going down and up. As the result, rough time estimation for iterating tree-like structure is very different from time estimation for iterating list. It is not that different in number of milliseconds for small lists. But I benchmarked with 10,000 of state machines and 1,000,000 of events and it was a bit surprising to see .NET version doing in 100 seconds what C++ done in 10.

Anyway, the story ended well. I've replaced ImmutableList with ImmutableArray and performance of the .NET version become aligned to C++, just 20% slower, which is actually Ok for me.

So the hint is to check and profile your code if you replaced List<T> with ImmutableList<T> and are not aware of considerable performance differences between them.

Happy coding.

⭐ my course on upcoming C# 8: modernise your code with C# 8 ⭐