Поиск  
Always will be ready notify the world about expectations as easy as possible: job change page
Apr 8

.NET — LinkedList vs ToArray

.NET — LinkedList vs ToArray
Автор:
Источник:
Просмотров:
2791

Performance comparison between LinkedList and ToArray

Performance comparison between LinkedList and ToArray

Some weeks ago I created an article comparing the performance of ToList versus ToArray when creating short lived collections that won’t be mutated, usually used to prevent multiple enumerations when iterating over a temporary LINQ transformation or to ensure mapping exceptions will be thrown inside the corresponding application layer.

In that article I concluded ToArray is faster and more memory efficient than ToList for almost any collection sizes and in any .NET version — tests were conducted on .NET Framework 4.8, .NET 7 and .NET 8.

But then I began to wonder: If I’m creating a temporary collection of unknown size just to force enumeration, wouldn’t LinkedList be a more efficient collection since I’m only appending items to the end, which is O(1), instead of constantly allocating new arrays like ToArray does?

I believe that’s a valid point so I decided to do a performance comparison between the two, assuming ToArray as the baseline and try to give a detailed explanation for the observed results.

Performance test

The test consists in the creation of a collection that holds random integers, being the size defined by a parameter. To ensure the randomness does not affect the results, the values are cached into an array and, before invoking either ToArray or creating the LinkedList, they are converted into a new IEnumerable, not just a cast that could lead to internal optimizations.

This time I decided to do the performance comparison only on .NET Framework 4.8 and .NET 8.

[SimpleJob(RuntimeMoniker.Net48)]
[SimpleJob(RuntimeMoniker.Net80)]
[MemoryDiagnoser]
public class LinkedListVsToArray
{
    [Params(10, 100, 1000, 10000, 100000)]
    public int Size;

    private int[] _items;

    [GlobalSetup]
    public void Setup()
    {
        var random = new Random(123);

        _items = Enumerable.Range(0, Size).Select(_ => random.Next()).ToArray();
    }

    [Benchmark(Baseline = true)]
    public int[] ToArray()
    {
        var items = CreateItemsEnumerable();
        return items.ToArray();
    }

    [Benchmark]
    public LinkedList<int> ToLinkedList()
    {
        var items = CreateItemsEnumerable();
        return new LinkedList<int>(items);
    }

    private IEnumerable<int> CreateItemsEnumerable()
    {
        foreach (var item in _items)
            yield return item;
    }
}

Performance results

Because we want to decide, for a given application, between ToArray or LinkedList based on performance, let’s analyze the results for each framework version.

.NET Framework 4.8

| Method       | Size   | Mean           | Error        | StdDev       | Median         | Ratio | RatioSD | Gen0     | Gen1     | Gen2     | Allocated | Alloc Ratio |
|------------- |------- |---------------:|-------------:|-------------:|---------------:|------:|--------:|---------:|---------:|---------:|----------:|------------:|
| ToArray      | 10     |       143.4 ns |      2.82 ns |      2.64 ns |       143.5 ns |  1.00 |    0.00 |   0.0470 |        - |        - |     297 B |        1.00 |
| ToLinkedList | 10     |       175.4 ns |      1.57 ns |      1.39 ns |       175.6 ns |  1.23 |    0.02 |   0.0918 |        - |        - |     578 B |        1.95 |
| ToArray      | 100    |       891.6 ns |     17.68 ns |     27.00 ns |       883.8 ns |  1.00 |    0.00 |   0.2584 |        - |        - |    1629 B |        1.00 |
| ToLinkedList | 100    |     1,464.8 ns |     14.96 ns |     13.26 ns |     1,467.8 ns |  1.63 |    0.04 |   0.7801 |   0.0134 |        - |    4910 B |        3.01 |
| ToArray      | 1000   |     7,867.5 ns |    156.18 ns |    223.99 ns |     7,896.2 ns |  1.00 |    0.00 |   1.9836 |   0.0153 |        - |   12504 B |        1.00 |
| ToLinkedList | 1000   |    14,881.8 ns |    283.19 ns |    290.82 ns |    14,892.3 ns |  1.92 |    0.06 |   7.6599 |   1.0834 |        - |   48238 B |        3.86 |
| ToArray      | 10000  |    78,138.5 ns |  1,547.95 ns |  2,363.88 ns |    78,993.1 ns |  1.00 |    0.00 |  26.9775 |   5.3711 |        - |  171755 B |        1.00 |
| ToLinkedList | 10000  |   158,728.7 ns |  2,151.48 ns |  1,907.23 ns |   158,243.9 ns |  2.03 |    0.07 |  76.4160 |  12.4512 |        - |  481511 B |        2.80 |
| ToArray      | 100000 |   805,445.4 ns |  9,463.82 ns |  8,852.47 ns |   804,730.5 ns |  1.00 |    0.00 | 399.4141 | 399.4141 | 399.4141 | 1452144 B |        1.00 |
| ToLinkedList | 100000 | 3,632,195.6 ns | 49,765.42 ns | 46,550.60 ns | 3,633,088.3 ns |  4.51 |    0.08 | 757.8125 | 375.0000 |        - | 4814292 B |        3.32 |

The ToArray method is significantly faster and more memory efficient than creating a new LinkedList. Still, it does allocate more Gen2 memory for larger collections which may be something to consider.

.NET 8

| Method       | Size   | Mean           | Error        | StdDev       | Median         | Ratio | RatioSD | Gen0     | Gen1     | Gen2     | Allocated | Alloc Ratio |
|------------- |------- |---------------:|-------------:|-------------:|---------------:|------:|--------:|---------:|---------:|---------:|----------:|------------:|
| ToArray      | 10     |       108.8 ns |      2.14 ns |      2.99 ns |       109.0 ns |  1.00 |    0.00 |   0.0315 |        - |        - |     264 B |        1.00 |
| ToLinkedList | 10     |       125.7 ns |      2.57 ns |      7.25 ns |       125.9 ns |  1.13 |    0.06 |   0.0677 |        - |        - |     568 B |        2.15 |
| ToArray      | 100    |       433.3 ns |      7.93 ns |      7.03 ns |       434.0 ns |  1.00 |    0.00 |   0.1431 |        - |        - |    1200 B |        1.00 |
| ToLinkedList | 100    |       979.2 ns |     19.54 ns |     40.79 ns |       977.9 ns |  2.34 |    0.09 |   0.5836 |   0.0095 |        - |    4888 B |        4.07 |
| ToArray      | 1000   |     3,100.4 ns |     34.14 ns |     28.51 ns |     3,090.9 ns |  1.00 |    0.00 |   1.0185 |        - |        - |    8544 B |        1.00 |
| ToLinkedList | 1000   |     9,135.9 ns |    179.58 ns |    345.98 ns |     9,205.1 ns |  3.03 |    0.08 |   5.7373 |   0.8850 |        - |   48088 B |        5.63 |
| ToArray      | 10000  |    31,587.6 ns |    604.95 ns |  1,437.72 ns |    31,129.4 ns |  1.00 |    0.00 |  12.6343 |        - |        - |  106232 B |        1.00 |
| ToLinkedList | 10000  |   109,454.7 ns |  2,152.65 ns |  4,198.57 ns |   107,653.8 ns |  3.43 |    0.11 |  57.3730 |  32.9590 |        - |  480088 B |        4.52 |
| ToArray      | 100000 |   531,028.2 ns |  3,515.73 ns |  3,288.62 ns |   531,061.8 ns |  1.00 |    0.00 | 249.0234 | 249.0234 | 249.0234 |  925140 B |        1.00 |
| ToLinkedList | 100000 | 2,295,939.2 ns | 44,598.15 ns | 62,520.38 ns | 2,288,468.0 ns |  4.33 |    0.13 | 570.3125 | 535.1563 |        - | 4800090 B |        5.19 |

Same behavior as .NET Framework 4.8, being the ToArray method much faster and memory efficient while still allocating more Gen2 memory on larger collections.

.NET performance evolution

Since in my previous article I already covered the performance evolution of ToArray over the years, let’s just compare how initializing a LinkedList from an IEnumerable have changed for different frameworks.

| Runtime            | Size   | Mean           | Error        | StdDev       | Median         | RatioSD | Gen0     | Gen1     | Gen2     | Allocated |
|------------------- |------- |---------------:|-------------:|-------------:|---------------:|--------:|---------:|---------:|---------:|----------:|
| .NET 8.0           | 10     |       125.7 ns |      2.57 ns |      7.25 ns |       125.9 ns |    0.06 |   0.0677 |        - |        - |     568 B |
| .NET Framework 4.8 | 10     |       175.4 ns |      1.57 ns |      1.39 ns |       175.6 ns |    0.02 |   0.0918 |        - |        - |     578 B |
| .NET 8.0           | 100    |       979.2 ns |     19.54 ns |     40.79 ns |       977.9 ns |    0.09 |   0.5836 |   0.0095 |        - |    4888 B |
| .NET Framework 4.8 | 100    |     1,464.8 ns |     14.96 ns |     13.26 ns |     1,467.8 ns |    0.04 |   0.7801 |   0.0134 |        - |    4910 B |
| .NET 8.0           | 1000   |     9,135.9 ns |    179.58 ns |    345.98 ns |     9,205.1 ns |    0.08 |   5.7373 |   0.8850 |        - |   48088 B |
| .NET Framework 4.8 | 1000   |    14,881.8 ns |    283.19 ns |    290.82 ns |    14,892.3 ns |    0.06 |   7.6599 |   1.0834 |        - |   48238 B |
| .NET 8.0           | 10000  |   109,454.7 ns |  2,152.65 ns |  4,198.57 ns |   107,653.8 ns |    0.11 |  57.3730 |  32.9590 |        - |  480088 B |
| .NET Framework 4.8 | 10000  |   158,728.7 ns |  2,151.48 ns |  1,907.23 ns |   158,243.9 ns |    0.07 |  76.4160 |  12.4512 |        - |  481511 B |
| .NET 8.0           | 100000 | 2,295,939.2 ns | 44,598.15 ns | 62,520.38 ns | 2,288,468.0 ns |    0.13 | 570.3125 | 535.1563 |        - | 4800090 B |
| .NET Framework 4.8 | 100000 | 3,632,195.6 ns | 49,765.42 ns | 46,550.60 ns | 3,633,088.3 ns |    0.08 | 757.8125 | 375.0000 |        - | 4814292 B |

On average, .NET 8 is 51% faster than .NET Framework 4.8, a clear demonstration how performance has improved over the years.

Analyzing the results

Now that we have the results you are probably questioning why does a LinkedList use more memory and is slower than ToArray? Since we don’t know the collection size, shouldn’t the constant allocation of new arrays and then a final copy to a trimmed one be slower and take more memory?

Using more memory could actually be expectable since a LinkedList, for each item, creates a class that holds a reference for the previous and next node, but why is it slower since adding an item is always a O(1) operation?

Based on personal experience, most developers I questioned about the ToArray implementation assume the following code (I actually believe this Stack Overflow response is to blame):

static T[] ToArray<T>(IEnumerable<T> items)
{
    const int sizeIncrease = 8; // some arbitrary size increase

    var current = new T[sizeIncrease];
    var count = 0;
    
    foreach (var item in items)
    {
        if (count == current.Length)
        {
            var previous = current;
            current = new T[previous.Length + sizeIncrease];
            previous.CopyTo(current, 0);
        }

        current[count++] = item;
    }

    if (count is 0)
        return Array.Empty<T>();

    Array.Resize(ref current, count);

    return current;
}

It assumes the ToArray method behaves similar to a List, creating a bigger one every time the current is full and doing a copy, and in the end it trims the excess.

In reality, the implementation is more similar to this:

static T[] ToArray<T>(IEnumerable<T> items)
{
    const int sizeIncrease = 8; // some arbitrary size increase

    var arrayBuffer = new Queue<T[]>();

    var current = new T[sizeIncrease];
    var count = 0;
    var idx = 0;

    foreach (var item in items)
    {
        if (idx == sizeIncrease)
        {
            arrayBuffer.Enqueue(current);
            current = new T[sizeIncrease];
            idx = 0;
        }

        current[idx++] = item;
        ++count;
    }

    if (count is 0)
        return Array.Empty<T>();

    var currentIdx = idx;

    idx = 0;
    var final = new T[count];
    while (arrayBuffer.Count > 0)
    {
        var previous = arrayBuffer.Dequeue();
        previous.CopyTo(final, idx);
        idx += previous.Length;
    }

    Array.Copy(current, 0, final, idx, currentIdx);

    return final;
}

Instead of creating a bigger array every time it’s full and copying all items, it actually creates a buffer that stores the previously allocated arrays and when the iteration finishes it copies everything in sequence to the final array that has the expected size.

The actual ToArray method implementation as a lot of optimizations, for example, when an ICollection is received they can initialize a new array with the collection size and just call CopyTo. It also doesn’t use a Queue to keep track of previous initialized arrays but instead a simple version of a LinkedList concept.

Give a look to the internal classes EnumerableHelpers and ArrayBuilder for more implementation details.

Conclusion

In this article we compared the performance of initializing a LinkedList versus using ToArray and concluded that, on theory, LinkedList looked like a good fit when creating short lived collections were enumeration must be forced because of its O(1) nature when appending values, but due to internal optimizations of ToArray and since indexing is just faster while using less memory it significantly compensates having to allocate multiple arrays and copying their content.

Keep in mind that LinkedList still has its place, specially when storing collections too big to be stored into a single memory section and it’s nice to see that .NET keeps improving its performance.

Похожее
Sep 11, 2023
Author: Artem A. Semenov
When crafting elegant and scalable software in C#, a keen understanding of Dependency Injection (DI) is more than a luxury — it’s a necessity. It’s a design pattern that underpins many modern .NET applications, providing a solid foundation for managing...
Jan 16, 2023
C# AngleSharp tutorial shows how to parse HTML in C# with AngleSharp library.The library can also parse SVG, MathML, or XML.AngleSharp GitHub: https://github.com/AngleSharpDocument Object Model (DOM) is a standard tree structure, where each node contains one of the components from...
Jul 24, 2023
Author: Mario Bittencourt
We have been living in a distributed world for quite some time, and when considering how should you implement the communication between any two parties involved, the discussion seems to gravitate around two options: API or messaging.Instead of focusing on...
Sep 14, 2023
Author: Mina Pêcheux
Interfaces are at the heart of the “composition-over-inheritance” paradigm — let’s see what that means!As you probably know, C# is a statically typed language. And as such, it is very helpful with type-checking and safe data conversions. Your IDE most...
Написать сообщение
Почта
Имя
*Сообщение


© 1999–2024 WebDynamics
1980–... Sergey Drozdov
Area of interests: .NET Framework | .NET Core | C# | ASP.NET | Windows Forms | WPF | HTML5 | CSS3 | jQuery | AJAX | Angular | React | MS SQL Server | Transact-SQL | ADO.NET | Entity Framework | IIS | OOP | OOA | OOD | WCF | WPF | MSMQ | MVC | MVP | MVVM | Design Patterns | Enterprise Architecture | Scrum | Kanban