Runtime: Iterating with ForEach over Immutable collections is very slow

[adamsitnik]

How to run the benchmarks:

git clone https://github.com/dotnet/performance.git
# if you have .NET Core 3.0 installed
dotnet run -c Release -f netcoreapp3.0 -p .\performance\src\benchmarks\micro\MicroBenchmarks.csproj --filter *IterateForEach<* --join
# if you don't have .NET Core 3.0 installed
py .\performance\scripts\benchmarks_ci.py -f netcoreapp3.0 --filter *IterateForEach<* --bdn-arguments="--join true"

| Type | Method | Size | Mean |
|----------------------- |-------------------------- |----- |-------------:|
| IterateForEach<Int32> | Array | 512 | 222.1 ns |
| IterateForEach<String> | Array | 512 | 216.8 ns |
| IterateForEach<Int32> | Span | 512 | 213.7 ns |
| IterateForEach<String> | Span | 512 | 230.2 ns |
| IterateForEach<Int32> | ReadOnlySpan | 512 | 210.6 ns |
| IterateForEach<String> | ReadOnlySpan | 512 | 227.8 ns |
| IterateForEach<Int32> | IEnumerable | 512 | 2,247.3 ns |
| IterateForEach<String> | IEnumerable | 512 | 2,465.8 ns |
| IterateForEach<Int32> | List | 512 | 1,125.1 ns |
| IterateForEach<String> | List | 512 | 2,401.7 ns |
| IterateForEach<Int32> | LinkedList | 512 | 1,972.2 ns |
| IterateForEach<String> | LinkedList | 512 | 3,284.3 ns |
| IterateForEach<Int32> | HashSet | 512 | 1,565.0 ns |
| IterateForEach<String> | HashSet | 512 | 2,344.5 ns |
| IterateForEach<Int32> | Dictionary | 512 | 3,432.4 ns |
| IterateForEach<String> | Dictionary | 512 | 3,159.9 ns |
| IterateForEach<Int32> | Queue | 512 | 1,539.8 ns |
| IterateForEach<String> | Queue | 512 | 3,834.0 ns |
| IterateForEach<Int32> | Stack | 512 | 1,806.3 ns |
| IterateForEach<String> | Stack | 512 | 3,876.8 ns |
| IterateForEach<Int32> | SortedList | 512 | 5,771.9 ns |
| IterateForEach<String> | SortedList | 512 | 7,221.3 ns |
| IterateForEach<Int32> | SortedSet | 512 | 8,825.5 ns |
| IterateForEach<String> | SortedSet | 512 | 9,210.3 ns |
| IterateForEach<Int32> | SortedDictionary | 512 | 9,784.2 ns |
| IterateForEach<String> | SortedDictionary | 512 | 13,343.0 ns |
| IterateForEach<Int32> | ConcurrentDictionary | 512 | 15,821.2 ns |
| IterateForEach<String> | ConcurrentDictionary | 512 | 21,915.9 ns |
| IterateForEach<Int32> | ConcurrentQueue | 512 | 4,228.2 ns |
| IterateForEach<String> | ConcurrentQueue | 512 | 5,546.4 ns |
| IterateForEach<Int32> | ConcurrentStack | 512 | 3,286.0 ns |
| IterateForEach<String> | ConcurrentStack | 512 | 4,345.6 ns |
| IterateForEach<Int32> | ConcurrentBag | 512 | 2,682.9 ns |
| IterateForEach<String> | ConcurrentBag | 512 | 4,924.7 ns |
| IterateForEach<Int32> | ImmutableArray | 512 | 1,137.9 ns |
| IterateForEach<String> | ImmutableArray | 512 | 1,137.7 ns |
| IterateForEach<Int32> | ImmutableDictionary | 512 | 57,456.2 ns |
| IterateForEach<String> | ImmutableDictionary | 512 | 88,192.5 ns |
| IterateForEach<Int32> | ImmutableHashSet | 512 | 66,958.3 ns |
| IterateForEach<String> | ImmutableHashSet | 512 | 107,369.1 ns |
| IterateForEach<Int32> | ImmutableList | 512 | 25,530.7 ns |
| IterateForEach<String> | ImmutableList | 512 | 45,287.9 ns |
| IterateForEach<Int32> | ImmutableQueue | 512 | 4,073.7 ns |
| IterateForEach<String> | ImmutableQueue | 512 | 4,510.7 ns |
| IterateForEach<Int32> | ImmutableStack | 512 | 3,891.0 ns |
| IterateForEach<String> | ImmutableStack | 512 | 4,181.2 ns |
| IterateForEach<Int32> | ImmutableSortedDictionary | 512 | 27,616.2 ns |
| IterateForEach<String> | ImmutableSortedDictionary | 512 | 44,664.0 ns |
| IterateForEach<Int32> | ImmutableSortedSet | 512 | 27,055.9 ns |
| IterateForEach<String> | ImmutableSortedSet | 512 | 45,142.9 ns |

Full docs for the new benchmarking workflow: https://github.com/dotnet/performance/blob/master/docs/benchmarking-workflow-corefx.md

[danmosemsft]

Do we allow benchmarks in the perf repo for corefxlab types? (I'm curious where DictionarySlim fits in this)

It's interesting that enumerating HashSet is signficantly faster than Dictionary. And the size is sufficiently small, that I would think (?) the better locality (smaller Entries) would not be relevant.

[adamsitnik]

Do we allow benchmarks in the perf repo for corefxlab types?

It would prolong the time it takes to run all the benchmarks. Also, the main focus in the perf repo is on the things we ship.

But we have a BDN based benchmarking solution in corefxlab which can be used to compare the perf https://github.com/dotnet/corefxlab/tree/master/tests/Benchmarks

[yahorsi]

Wait, iterating ofer Array is SO faster than over List? >5x times faster for Int's and omg 10 times for strings? Hell List is the base collection used basically 90% of the time, e.g. when we query database and neeed results. If List is Array based why it is so slower. Don't you think this is actually bigger issue than Immutable* ? I beleive List is used and iterated in the 100% of .NET programs unlike Immutable* collections

[huoyaoyuan]

@yahorsi List iterator must check that you haven't modified the list during the loop. Only rust-style immutable/mutable ownership checking can solve this gracefully. C++ chooses for speed but lacks safety.

[PiotrKowalski93]

It seems like interesting topic for me. Can work on it? I mean, I want to be a contributor but i have never worked on OpenSource. I can work in cooperation too :)

[Wraith2]

@PiotrKowalski93 no permission needed just go for it. The code standard here are high so be prepared to be able to justify and measure everything but improvements are always welcome.

[PiotrKowalski93]

Great, I wanted to debug the code but I hit the wall. Build went great. I wanted to see how the code is working in System.Collections.Immutable so I created .sln with simple console app in which I create ImmutableList and iterate through it.

Separately when I open solution System.Collections.Immutable.sln i can build code etc. but when I add System.Collections.Immutable.csproj to my "testing" .sln i see:

The TargetFramework value '' was not recognized. It may be misspelled. If not, then the TargetFrameworkIdentifier and/or TargetFrameworkVersion properties must be specified explicitly.

And indeed it is not specified and in properties of csproj i see empty list in TargetFramework property.

How can Debug this specific dll?

[Wraith2]

the build system relies on a lot of complex logic so you won't be able to easily get a project that needs it to compile without it. I'd suggest you take the code logic from the collections you want to debug and add that code directly to your project then debug it that way.

[PiotrKowalski93]

@Wraith2 Thank you, fair point, I will do that