Skip to content

PriorityQueue: Apply Comparer<T>.Default optimization#48346

Merged
stephentoub merged 5 commits intodotnet:masterfrom
eiriktsarpalis:priorityqueue-default-comparer
Feb 17, 2021
Merged

PriorityQueue: Apply Comparer<T>.Default optimization#48346
stephentoub merged 5 commits intodotnet:masterfrom
eiriktsarpalis:priorityqueue-default-comparer

Conversation

@eiriktsarpalis
Copy link
Member

@eiriktsarpalis eiriktsarpalis commented Feb 16, 2021 •
edited
Loading

Make direct calls to Comparer<T>.Default.Compare when no custom IComparer<T> instance is specified, taking advantage of the optimizations in #48160.

Performance

Using benchmarks from dotnet/performance#1665

main

Method Size Mean Error StdDev Median Min Max Gen 0 Gen 1 Gen 2 Allocated
HeapSort 10 275.5 ns 4.72 ns 3.94 ns 274.3 ns 272.3 ns 284.7 ns - - - -
K_Min_Elements 10 188.2 ns 1.43 ns 1.34 ns 188.1 ns 186.4 ns 190.5 ns - - - -
HeapSort 100 5,831.1 ns 23.68 ns 20.99 ns 5,827.2 ns 5,790.5 ns 5,873.7 ns - - - -
K_Min_Elements 100 835.3 ns 5.56 ns 4.64 ns 835.9 ns 825.7 ns 842.4 ns - - - -
HeapSort 1000 104,618.2 ns 1,297.35 ns 1,213.54 ns 104,295.8 ns 103,134.7 ns 107,482.9 ns - - - -
K_Min_Elements 1000 5,109.5 ns 84.29 ns 74.72 ns 5,082.6 ns 5,035.9 ns 5,285.3 ns - - - -
HeapSort 10000 1,382,286.0 ns 17,339.01 ns 14,478.85 ns 1,378,520.1 ns 1,364,851.3 ns 1,418,781.0 ns - - - 1 B
K_Min_Elements 10000 43,600.4 ns 655.10 ns 547.04 ns 43,470.5 ns 42,982.0 ns 44,965.3 ns - - - -
HeapSort 100000 17,338,945.6 ns 127,125.13 ns 106,155.24 ns 17,342,100.0 ns 17,143,023.1 ns 17,486,884.6 ns - - - 11 B
K_Min_Elements 100000 461,078.6 ns 18,155.17 ns 20,907.53 ns 458,911.1 ns 428,690.8 ns 492,106.5 ns - - - -

PR branch

Method Size Mean Error StdDev Median Min Max Gen 0 Gen 1 Gen 2 Allocated
HeapSort 10 208.9 ns 6.34 ns 6.79 ns 208.6 ns 191.8 ns 217.7 ns - - - -
K_Min_Elements 10 147.3 ns 5.80 ns 6.68 ns 144.6 ns 136.6 ns 160.8 ns - - - -
HeapSort 100 3,553.9 ns 120.23 ns 133.63 ns 3,583.6 ns 3,261.7 ns 3,751.3 ns - - - -
K_Min_Elements 100 610.5 ns 18.93 ns 20.25 ns 615.2 ns 561.9 ns 647.7 ns - - - -
HeapSort 1000 82,091.4 ns 3,752.99 ns 4,321.94 ns 82,769.6 ns 74,755.7 ns 91,248.6 ns - - - -
K_Min_Elements 1000 4,042.3 ns 179.86 ns 207.13 ns 4,028.6 ns 3,687.8 ns 4,411.0 ns - - - -
HeapSort 10000 1,117,819.2 ns 38,606.25 ns 42,910.75 ns 1,108,901.0 ns 1,037,257.2 ns 1,176,602.9 ns - - - 1 B
K_Min_Elements 10000 34,393.6 ns 1,911.55 ns 2,124.68 ns 33,527.5 ns 31,757.1 ns 38,687.1 ns - - - -
HeapSort 100000 14,617,127.5 ns 510,218.11 ns 587,567.94 ns 14,697,175.0 ns 13,688,916.7 ns 15,793,872.2 ns - - - 8 B
K_Min_Elements 100000 337,853.6 ns 12,592.12 ns 14,501.10 ns 331,689.4 ns 316,677.5 ns 365,371.4 ns - - - -

@eiriktsarpalis eiriktsarpalis added this to the 6.0.0 milestone Feb 16, 2021
@eiriktsarpalis eiriktsarpalis self-assigned this Feb 16, 2021
@ghost
Copy link

ghost commented Feb 16, 2021

Tagging subscribers to this area: @eiriktsarpalis
See info in area-owners.md if you want to be subscribed.

Issue Details

Make direct calls to Comparer<T>.Default.Compare when no custom IComparer<T> instance is specified, taking advantage of the optimizations in #48160.

Performance

Using benchmarks from dotnet/performance#1665

main

Method Size Mean Error StdDev Median Min Max Gen 0 Gen 1 Gen 2 Allocated
HeapSort 10 275.5 ns 4.72 ns 3.94 ns 274.3 ns 272.3 ns 284.7 ns - - - -
K_Min_Elements 10 188.2 ns 1.43 ns 1.34 ns 188.1 ns 186.4 ns 190.5 ns - - - -
HeapSort 100 5,831.1 ns 23.68 ns 20.99 ns 5,827.2 ns 5,790.5 ns 5,873.7 ns - - - -
K_Min_Elements 100 835.3 ns 5.56 ns 4.64 ns 835.9 ns 825.7 ns 842.4 ns - - - -
HeapSort 1000 104,618.2 ns 1,297.35 ns 1,213.54 ns 104,295.8 ns 103,134.7 ns 107,482.9 ns - - - -
K_Min_Elements 1000 5,109.5 ns 84.29 ns 74.72 ns 5,082.6 ns 5,035.9 ns 5,285.3 ns - - - -
HeapSort 10000 1,382,286.0 ns 17,339.01 ns 14,478.85 ns 1,378,520.1 ns 1,364,851.3 ns 1,418,781.0 ns - - - 1 B
K_Min_Elements 10000 43,600.4 ns 655.10 ns 547.04 ns 43,470.5 ns 42,982.0 ns 44,965.3 ns - - - -
HeapSort 100000 17,338,945.6 ns 127,125.13 ns 106,155.24 ns 17,342,100.0 ns 17,143,023.1 ns 17,486,884.6 ns - - - 11 B
K_Min_Elements 100000 461,078.6 ns 18,155.17 ns 20,907.53 ns 458,911.1 ns 428,690.8 ns 492,106.5 ns - - - -

PR branch

Method Size Mean Error StdDev Median Min Max Gen 0 Gen 1 Gen 2 Allocated
HeapSort 10 223.5 ns 11.72 ns 13.50 ns 223.9 ns 201.8 ns 255.1 ns - - - -
K_Min_Elements 10 160.3 ns 7.04 ns 7.53 ns 161.3 ns 143.7 ns 177.5 ns - - - -
HeapSort 100 3,920.9 ns 174.22 ns 200.63 ns 3,846.8 ns 3,596.4 ns 4,260.7 ns - - - -
K_Min_Elements 100 673.7 ns 29.12 ns 32.37 ns 664.1 ns 600.0 ns 746.7 ns - - - -
HeapSort 1000 92,148.8 ns 5,169.56 ns 5,953.27 ns 90,795.5 ns 81,293.0 ns 101,454.3 ns - - - -
K_Min_Elements 1000 4,240.8 ns 218.07 ns 251.13 ns 4,216.7 ns 3,893.1 ns 4,756.2 ns - - - -
HeapSort 10000 1,190,499.1 ns 62,030.00 ns 68,946.18 ns 1,186,243.8 ns 1,078,781.2 ns 1,323,172.6 ns - - - -
K_Min_Elements 10000 35,666.2 ns 1,789.15 ns 2,060.39 ns 35,204.8 ns 32,366.7 ns 39,244.3 ns - - - -
HeapSort 100000 15,598,726.7 ns 925,264.89 ns 1,065,536.42 ns 15,555,280.0 ns 14,134,093.3 ns 17,881,353.3 ns - - - 3 B
K_Min_Elements 100000 341,994.9 ns 16,382.08 ns 18,865.63 ns 336,791.1 ns 318,997.7 ns 380,926.2 ns - - - -
Author: eiriktsarpalis
Assignees: eiriktsarpalis
Labels:

area-System.Collections
Milestone: 6.0.0

eiriktsarpalis
eiriktsarpalis commented Feb 16, 2021
View reviewed changes
src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs
// Restore the heap order
int lastNodeIndex = GetLastNodeIndex();
MoveUp((element, priority), lastNodeIndex);
if (_comparer == null)
Copy link
Member Author

@eiriktsarpalis eiriktsarpalis Feb 16, 2021 •
edited
Loading

Choose a reason for hiding this comment

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

This approach attempts to minimize the number of times we null check _comparer per API call, but perhaps things would be simpler if we moved everything behind one MoveUp/MoveDown method that performs the check, potentially redundantly.

@EgorBo EgorBo mentioned this pull request Feb 16, 2021
Closed
@eiriktsarpalis @stephentoub
Update src/libraries/System.Collections/src/System/Collections/Generi…
7f696a7 
…c/PriorityQueue.cs

Co-authored-by: Stephen Toub <stoub@microsoft.com>
stephentoub
stephentoub approved these changes Feb 16, 2021
View reviewed changes
Copy link
Member

@stephentoub stephentoub left a comment

Choose a reason for hiding this comment

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

Do we have sufficient tests now that we need to cover value types vs reference types with and without a custom comparer and where that comparer is and is not the default?

eiriktsarpalis and others added 2 commits February 16, 2021 20:54
@eiriktsarpalis
address feedback
e78d8bf
@eiriktsarpalis @stephentoub
Update src/libraries/System.Collections/src/System/Collections/Generi…
d4206a7 
…c/PriorityQueue.cs

Co-authored-by: Stephen Toub <stoub@microsoft.com>
@stephentoub stephentoub merged commit 9a3f001 into dotnet:master Feb 17, 2021
@eiriktsarpalis
Copy link
Member Author

eiriktsarpalis commented Feb 17, 2021

Do we have sufficient tests now that we need to cover value types vs reference types with and without a custom comparer and where that comparer is and is not the default?

I think we could do better. I'll follow up with another PR.

@eiriktsarpalis eiriktsarpalis deleted the priorityqueue-default-comparer branch February 17, 2021 10:29
@eiriktsarpalis eiriktsarpalis mentioned this pull request Feb 17, 2021
Merged
@ghost ghost locked as resolved and limited conversation to collaborators Mar 19, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Reviewers

@stephentoub stephentoub stephentoub approved these changes

Assignees

@eiriktsarpalis eiriktsarpalis

Labels

area-System.Collections

Projects

None yet

Milestone

6.0.0

Development

Successfully merging this pull request may close these issues.

2 participants

@eiriktsarpalis @stephentoub