Performance modifying change to LINQ OrderBy(...).First{OrDefault}(...)

[danmoseley]

Complexity of OrderBy(...).First{OrDefault}(...) increased

[Brief description of the change]

Version introduced

.NET 5.0

Old behavior

As of .NET Core 1.0, OrderBy(...).First{OrDefault}(...) operated with O(N) complexity: since only the first (or default) element is required, it can simply complete the enumeration once to find it. However, the supplied predicate is invoked exactly N times.

Original change was dotnet/corefx#2401

New behavior

As of .NET 5.0, we reverted to the .NET Framework behavior. OrderBy(...).First{OrDefault}(...) operates with O(N log N) complexity, but may invoke the supplied predicate fewer than N times.

See issue dotnet/runtime#31554 and change dotnet/runtime#36643

Reason for change

Community feedback that the cost of potentially invoking the predicate more times outweighed the benefit of a lower complexity operation overall.

Recommended action

No action required.

Category

• Core .NET libraries

Affected APIs

The behavior change only occurs when using these API together.

Enumerable.FirstOrDefault
Enumerable.First
Enumerable.OrderBy

Issue metadata

• Issue type: breaking-change