KEMBAR78
Reduce OrderBy overheads for default comparer by stephentoub · Pull Request #76418 · dotnet/runtime · GitHub
Skip to content

Conversation

stephentoub
Copy link
Member

If OrderBy is used with a value type key and and a default or no comparer is specified, we can use Comparer<TKey>.Default.Compare to avoid the interface dispatch. This optimization can be taken further, but for now it handles a common set of cases. (We can subsequently look into a variety of improvements, such as a cheaper way to implement a stable sort, doing the sort in-place in the buffered output when conditions are ammenable, extending these checks for using the default comparer into chained OrderBy/ThenBy cases, etc.)

[Params(10, 100, 1_000, 1_000_000)]
public int Length { get; set; }

private int[] _values;

[GlobalSetup]
public void Setup() => _values = Enumerable.Range(0, Length).Reverse().ToArray();

[Benchmark]
public int[] OrderByToArray() => _values.OrderBy(i => i).ToArray();
Method Toolchain Length Mean Ratio
OrderByToArray \main\corerun.exe 10 418.8 ns 1.00
OrderByToArray \pr\corerun.exe 10 314.6 ns 0.75
OrderByToArray \main\corerun.exe 100 4,291.3 ns 1.00
OrderByToArray \pr\corerun.exe 100 2,680.5 ns 0.63
OrderByToArray \main\corerun.exe 1000 71,427.6 ns 1.00
OrderByToArray \pr\corerun.exe 1000 40,393.7 ns 0.57
OrderByToArray \main\corerun.exe 1000000 180,572,845.2 ns 1.00
OrderByToArray \pr\corerun.exe 1000000 96,260,728.2 ns 0.53

If OrderBy is used with a value type key and and a default or no comparer is specified, we can use `Comparer<TKey>.Default.Compare` to avoid the interface dispatch.  This optimization can be taken further, but for now it handles a common set of cases.
@stephentoub stephentoub added area-System.Linq tenet-performance Performance related issue labels Sep 30, 2022
@stephentoub stephentoub added this to the 8.0.0 milestone Sep 30, 2022
@ghost ghost assigned stephentoub Sep 30, 2022
@ghost
Copy link

ghost commented Sep 30, 2022

Tagging subscribers to this area: @dotnet/area-system-linq
See info in area-owners.md if you want to be subscribed.

Issue Details

If OrderBy is used with a value type key and and a default or no comparer is specified, we can use Comparer<TKey>.Default.Compare to avoid the interface dispatch. This optimization can be taken further, but for now it handles a common set of cases. (We can subsequently look into a variety of improvements, such as a cheaper way to implement a stable sort, doing the sort in-place in the buffered output when conditions are ammenable, extending these checks for using the default comparer into chained OrderBy/ThenBy cases, etc.)

[Params(10, 100, 1_000, 1_000_000)]
public int Length { get; set; }

private int[] _values;

[GlobalSetup]
public void Setup() => _values = Enumerable.Range(0, Length).Reverse().ToArray();

[Benchmark]
public int[] OrderByToArray() => _values.OrderBy(i => i).ToArray();
Method Toolchain Length Mean Ratio
OrderByToArray \main\corerun.exe 10 418.8 ns 1.00
OrderByToArray \pr\corerun.exe 10 314.6 ns 0.75
OrderByToArray \main\corerun.exe 100 4,291.3 ns 1.00
OrderByToArray \pr\corerun.exe 100 2,680.5 ns 0.63
OrderByToArray \main\corerun.exe 1000 71,427.6 ns 1.00
OrderByToArray \pr\corerun.exe 1000 40,393.7 ns 0.57
OrderByToArray \main\corerun.exe 1000000 180,572,845.2 ns 1.00
OrderByToArray \pr\corerun.exe 1000000 96,260,728.2 ns 0.53
Author: stephentoub
Assignees: -
Labels:

area-System.Linq, tenet-performance

Milestone: 8.0.0

Copy link
Member

@eiriktsarpalis eiriktsarpalis left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

area-System.Linq tenet-performance Performance related issue

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants