Runtime: Immutable collection read are way too slow than Normal collections

Created on 1 Jun 2019 · 5Comments · Source: dotnet/runtime

As i think immutable collection read operations will not do checks with concurrent access, it should be faster than normal collection. but test shows a different result.

// * Summary *

BenchmarkDotNet=v0.11.5, OS=Windows 10.0.17763.503 (1809/October2018Update/Redstone5)
Intel Core i5-7300U CPU 2.60GHz (Kaby Lake), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=2.2.204
[Host] : .NET Core 2.2.5 (CoreCLR 4.6.27617.05, CoreFX 4.6.27618.01), 64bit RyuJIT
DefaultJob : .NET Core 2.2.5 (CoreCLR 4.6.27617.05, CoreFX 4.6.27618.01), 64bit RyuJIT

| Method | Count | Mean | Error | StdDev | Median |
|--------------------- |------ |-----------:|---------:|----------:|-----------:|
| TestHash | 5 | 898.1 ns | 26.41 ns | 76.21 ns | 873.2 ns |
| TestImmutableHashset | 5 | 2,485.9 ns | 73.78 ns | 212.86 ns | 2,438.5 ns |
| TestHash | 200 | 904.7 ns | 18.36 ns | 36.24 ns | 898.7 ns |
| TestImmutableHashset | 200 | 3,980.9 ns | 79.65 ns | 130.86 ns | 3,971.3 ns |

// * Summary *

| Method | Count | Mean | Error | StdDev |
|------------------ |------ |------------:|-----------:|-----------:|
| UseArray | 5 | 160.6 ns | 3.203 ns | 2.839 ns |
| UseList | 5 | 204.6 ns | 2.791 ns | 2.330 ns |
| UseImmutableArray | 5 | 276.5 ns | 4.826 ns | 4.278 ns |
| UseImmutableList | 5 | 1,581.7 ns | 21.870 ns | 20.457 ns |
| UseArray | 200 | 3,180.2 ns | 52.322 ns | 48.942 ns |
| UseList | 200 | 4,196.8 ns | 64.607 ns | 50.441 ns |
| UseImmutableArray | 200 | 3,210.4 ns | 33.345 ns | 29.559 ns |
| UseImmutableList | 200 | 31,295.6 ns | 485.202 ns | 453.858 ns |

Test code shown below

public class TestHashset
    {
        [Params(5, 200)]
        public int Count { get; set; }

        private HashSet<int> hashSet;

        private ImmutableHashSet<int> immutableHashSet;

        [GlobalSetup]
        public void Setup()
        {
            var rnd = new Random();
            this.hashSet = new HashSet<int>();

            for (int i = 0; i < this.Count; i++)
            {
                this.hashSet.Add(rnd.Next(1000));
            }

            this.immutableHashSet = this.hashSet.ToImmutableHashSet();
        }

        [Benchmark]
        public int TestHash()
        {
            int got = 0;
            for (int i = 0; i < 100; i++)
            {
                if (this.hashSet.Contains(i))
                {
                    got++;
                }
            }

            return got;
        }

        [Benchmark]
        public int TestImmutableHashset()
        {
            int got = 0;
            for (int i = 0; i < 100; i++)
            {
                if (this.immutableHashSet.Contains(i))
                {
                    got++;
                }
            }

            return got;
        }
    }

      public class TestCollection
    {
        [Params(5, 200)]
        public int Count { get; set; }

        private List<(string s, double l)> list;


        [GlobalSetup]
        public void Setup()
        {
            var rnd = new Random();
            this.list = new List<(string s, double l)>();
            for (int i = 0; i < this.Count; i++)
            {
                var v = rnd.NextDouble();
                this.list.Add((v.ToString(), v));
            }
        }

        private double TestEnumable(IEnumerable<double> local)
        {
            var all = 0d;

            foreach (var d in local)
            {
                all += d;
            }

            var max = 0d;

            foreach (var d in local)
            {
                max = max > d ? max : d;
            }

            return max + all;
        }

        [Benchmark]
        public double UseArray()
        {
            return this.TestEnumable(this.list.Select(s => s.l).ToArray());
        }
        [Benchmark]
        public double UseList()
        {
            return this.TestEnumable(this.list.Select(s => s.l).ToList());
        }
        [Benchmark]
        public double UseImmutableArray()
        {
            return this.TestEnumable(this.list.Select(s => s.l).ToImmutableArray());
        }
        [Benchmark]
        public double UseImmutableList()
        {
            return this.TestEnumable(this.list.Select(s => s.l).ToImmutableList());
        }

    }

Source

ares128

Most helpful comment

As i think immutable collection read operations will not do checks with concurrent access, it should be faster than normal collection. but test shows a different result.

The normal collections don't check for concurrent access which is why they aren't safe, not doing work is generally faster than doing work so they're also fast

The immutable collections are slower because every mutation operation has to produce a new instance. The immutable types do this by trying not to consume all your memory so they do a lot of work to be both safe and re-use information. More work, more time.

So I think your assumptions are wrong. Take a look at the code in this repository for each of they collection types and judge for yourself. You may also want to look at the Concurrent namespace

Wraith2 on 1 Jun 2019

👍2

All 5 comments

As i think immutable collection read operations will not do checks with concurrent access, it should be faster than normal collection. but test shows a different result.

The normal collections don't check for concurrent access which is why they aren't safe, not doing work is generally faster than doing work so they're also fast

So I think your assumptions are wrong. Take a look at the code in this repository for each of they collection types and judge for yourself. You may also want to look at the Concurrent namespace

Wraith2 on 1 Jun 2019

👍2

As i think immutable collection read operations will not do checks with concurrent access, it should be faster than normal collection. but test shows a different result.

The immutable collections use fundamentally different data structures optimized for different things, and as such, while it's easy to make this assumption, it's not a valid one. They are optimized for the use case of creating new collections from previous ones, e.g. ImmutableDictionary.Add creating a new instance that's able to share most of the state of the previous collection.

stephentoub on 1 Jun 2019

👍1

MarcoRossignoli on 1 Jun 2019

As was pointed out, immutability comes with a price tag. That being said, I do agree that lookup speed in particular is unfortunate with ImmutableDictionary<,>. It's because the dictionary is basically a tree. I wish dictionaries would mirror what we did with lists: we have ImmutableList<T>, which optimizes for reducing copying by using a tree, and ImmutableArray<T>, which optimizes for lookup speed by copying the array. Not sure about the naming, but ideally we'd have a type that (logically) behaves like Dictionary<TKey, TValue> when reading but does a full copy when writing.

Either I'm reading your data wrong or the benchmark is a bit weird, especially these rows:

Method | Count | Mean | Error | StdDev
-- | -- | -- | -- | --
UseArray | 200 | 3,180.2 ns | 52.322 ns | 48.942 ns
UseImmutableArray | 200 | 3,210.4 ns | 33.345 ns | 29.559 ns

ImmutableArray<> just uses an array inside with as close to zero overhead as we can muster. If anything, immutable array should be the same as array or slightly slower. But not faster. That's probably because the number of iterations and sizes you've chosen are too small and thus the difference is within the noise of what can be measured. So I'd be careful what you read into these.