Performance Battle: Which Collection is the Fastest in C#

Originally published on Medium · April 2, 2023 — examples target the tooling of that time.

C# gives you a lot of ways to store a bunch of integers, and it's easy to reach for whichever one is most convenient without thinking about what it costs you at runtime. I wanted actual numbers instead of gut feeling, so I picked six common collection types — arrays, lists, hashsets, sorted sets, IEnumerable, and Parallel.For — and benchmarked how each one performs when you just iterate over it.

Arrays

An array is a fixed-size contiguous block of memory that can hold a collection of elements of the same type. Arrays are implemented as a language feature in C# and are therefore a core part of the language. They offer very fast read and write performance, but they are not resizable, which means that if you need to add or remove elements, you'll need to create a new array.

Lists

A list is a dynamic collection of elements of the same type that can grow or shrink in size as needed. Lists are implemented as a generic class in C# and are based on an underlying array. They offer good read and write performance, and their dynamic nature makes them very flexible.

HashSet

A hashset is a collection of unique elements that are stored in a way that makes it easy to look up whether a particular element exists in the set or not. Hashsets are implemented as a generic class in C# and are based on an underlying hash table. They offer fast lookups and are well-suited for scenarios where you need to check whether an element is in the set or not.

SortedSet

A sorted set is a collection of unique elements that are stored in sorted order. Sorted sets are implemented as a generic class in C# and are based on an underlying red-black tree. They offer fast lookups and are well-suited for scenarios where you need to maintain a collection of elements in sorted order.

IEnumerable

An IEnumerable is an interface that represents a collection of elements that can be enumerated. This means that you can loop over the collection using a foreach loop or use LINQ extension methods to query the collection. IEnumerable is implemented by many different collection types in C#, including arrays, lists, hashsets, and sorted sets.

Parallel.For

Parallel.For is a method in the System.Threading.Tasks namespace that allows you to execute a loop in parallel using multiple threads. When used with an array, it can offer performance benefits for large collections, but the overhead of thread synchronization can make it slower than other collection types for smaller collections.

How I Benchmarked This

To compare the performance of each collection type, we'll be using the BenchmarkDotNet library. We'll be iterating over an array of integers and measuring the time it takes to iterate over the entire collection using each collection type.

Here's the code we'll use to test the performance of each collection type:

using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using BenchmarkDotNet.Attributes;

namespace Benchmarking.Tests;

[MemoryDiagnoser]
public class CollectionIterationPerformance
{
    private const int CollectionLength = 10_000_000;
    private readonly int[] _array;
    private readonly List<int> _list;
    private readonly HashSet<int> _hashSet;
    private readonly SortedSet<int> _sorterSet;
    private readonly IEnumerable<int> _enumerable;

    public CollectionIterationPerformance()
    {
        _array = Enumerable.Range(0, CollectionLength).ToArray();
        _list = Enumerable.Range(0, CollectionLength).ToList();
        _hashSet = new HashSet<int>(Enumerable.Range(0, CollectionLength));
        _sorterSet = new SortedSet<int>(Enumerable.Range(0, CollectionLength));
        _enumerable = Enumerable.Range(0, CollectionLength);
    }

    [Benchmark]
    public void EnumerableIteration()
    {
        var total = 0;
        foreach (var item in _enumerable)
            total += item;
    }

    [Benchmark]
    public void HashSetIteration()
    {
        var total = 0;
        foreach (var item in _hashSet)
            total += item;
    }

    [Benchmark]
    public void ArrayIteration()
    {
        var total = 0;
        foreach (var item in _array)
            total += item;
    }

    [Benchmark]
    public void ParallelForIteration()
    {
        var total = 0;
        Parallel.For(
            0,
            _array.Length,
            x => { total += x; });
    }

    [Benchmark]
    public void ListIteration()
    {
        var total = 0;
        foreach (var item in _list)
            total += item;
    }

    [Benchmark]
    public void SortedSetIteration()
    {
        var total = 0;
        foreach (var item in _sorterSet)
            total += item;
    }
}

Benchmark environment:

BenchmarkDotNet=v0.13.5, OS=Windows 11 (10.0.22621.1413/22H2/2022Update/SunValley2)
11th Gen Intel Core i7-1165G7 2.80GHz, 1 CPU, 8 logical and 4 physical cores
.NET SDK=7.0.100
  [Host]     : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2 [AttachedDebugger]
  DefaultJob : .NET 7.0.0 (7.0.22.51805), X64 RyuJIT AVX2

10,000,000 Iterations

| Method | Mean | Error | StdDev | Median | Allocated | |---|---|---|---|---|---| | ArrayIteration | 5.294 ms | 0.1049 ms | 0.1753 ms | 5.231 ms | 4 B | | ListIteration | 7.062 ms | 0.2264 ms | 0.6676 ms | 6.831 ms | 4 B | | HashSetIteration | 24.290 ms | 0.5808 ms | 1.6851 ms | 23.920 ms | 32 B | | EnumerableIteration | 28.508 ms | 0.3880 ms | 0.3240 ms | 28.423 ms | 56 B | | ParallelForIteration | 66.869 ms | 1.2559 ms | 2.8089 ms | 66.035 ms | 4534 B | | SortedSetIteration | 112.022 ms | 2.2353 ms | 2.3917 ms | 112.535 ms | 525 B |

1,000 Iterations

| Method | Mean | Error | StdDev | Gen0 | Allocated | |---|---|---|---|---|---| | ArrayIteration | 376.4 ns | 2.41 ns | 2.13 ns | - | - | | ListIteration | 498.4 ns | 6.78 ns | 6.34 ns | - | - | | HashSetIteration | 1,989.2 ns | 39.02 ns | 49.35 ns | - | - | | EnumerableIteration | 3,095.3 ns | 34.47 ns | 30.55 ns | 0.0038 | 40 B | | SortedSetIteration | 11,171.7 ns | 221.15 ns | 542.48 ns | 0.0305 | 200 B | | ParallelForIteration | 13,257.5 ns | 228.17 ns | 288.57 ns | 0.3662 | 2319 B |

Results

The array collection performed the fastest in both the 10,000,000 and 1,000 iteration cases. This is likely because arrays are contiguous blocks of memory that can be accessed quickly and efficiently. Additionally, arrays have a fixed size, so the compiler can optimize for their use, resulting in faster iteration.

In contrast, Parallel.For, surprisingly, did not produce the expected results. While parallelization can improve performance by distributing the work across multiple threads, it can also introduce overhead in certain cases. In this benchmark, it appears that the overhead of managing the parallel execution actually slowed down the iteration process compared to a regular loop. It's important to note that the performance benefits of parallelization can vary greatly depending on the nature of the workload and the hardware being used, so it's always worth experimenting and testing to find the best approach for a specific use case.