Calling "ToList()" for LINQ performance

18 Dec 2022 - by 'Maurits van der Schee'

While I was doing AdventOfCode 2022 I ran into an issue that made my code run more than 30 times slower than I expected. I didn't materialize the LINQ expression and I iterated over the sorted collection by position. To anyone understanding how LINQ does lazy evaluation this is an obvious error on my part, causing the sorting to be executed on every key access on the LINQ expression.

Can you spot the bug?

For anyone less familiar with LINQ the bug is hard to spot (especially in VB.net):

Dim elements = New List(Of Integer)()
For i = 0 To 9999
    elements.Add(i)
Next
Dim sorted = elements.OrderBy(Function(x) -x)
Dim count as Long = 0
For i = 0 To 9999
    count += sorted(i)
Next
Console.WriteLine(count)

In C# this becomes already a bit more obvious (as it requires the "ElementAt()" method):

var elements = new List<int>();
for (var i = 0; i < 10000; i++)
{
    elements.Add(i);
}
var sorted = elements.OrderBy(x => -x);
long count = 0;
for (var i = 0; i < 10000; i++)
{
    count += sorted.ElementAt(i);
}
Console.WriteLine(count);

The line:

var sorted = elements.OrderBy(x => -x);

should be:

var sorted = elements.OrderBy(x => -x).ToList();

With this change the code runs roughly 30x times faster (try it).

Enjoy programming!

Links

PS: Liked this article? Please share it on Facebook, Twitter or LinkedIn.

TQ
dev.com