GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — Added -Top/-Bottom params to Sort-Object for Top/Bottom N sort and many Pester tests by KirkMunro · Pull Request #2518 · PowerShell/PowerShell

Conversation

@KirkMunro

@KirkMunro Kirk Munro (KirkMunro) commented Oct 21, 2016 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

This changeset addresses issue #2462, along with all feedback received in the comments for that issue.

The original issue was identified as an enhancement to add -Top support to Sort-Object, so that (a) you would get results back faster when you only wanted the top N, and (b) you would get code elegance by not having to pipe to Select-Object. Several commenters wanted -Bottom N support added for completeness, so an additional parameter set was created with a -Bottom <ìnt> parameter. Over 40 tests were written for Pester to compare the sort results using Sort -Top or Sort -Bottom with sort results when -Top and -Bottom are not used to ensure that we always get back the data we want according with how Sort-Object sorts data without -Top/-Bottom. That means that if Sort-Object is broken (if it returns results in a different order), these tests will pass; however, the intent of these tests is to compare the sort results with those of a basic Sort-Object invocation, and other tests exist to verify the order of the items returned from Sort-Object, so this is all good.

Additionally, performance testing was done and -Top/-Bottom sorts on very large data sets (1M integers) returned results about twice as fast as when using sort | select -First/-Last, as long as -Unique is not used. This performance improvement is partly because of the reduced pipeline and partly because of a faster sort algorithm (an indexed min-/max-heap sort is used to process Top N/Bottom N results more quickly).

Worth noting: Using -Top/-Bottom sorts using -Unique are really, really slow with very large data sets, just as sort | select -First/-Last are slow with very large data sets. This code is old, and while looking at it I felt it would be worth looking at SortedSet for -Unique sorts (SortedSet did not exist when sort-object was first written) to see if it would return unique sorted results more quickly. That investigation was outside of the scope of this PR though, so I'm simply mentioning it here so that I don't forget about the item. A separate issue should probably be created to investigate SortedSet with Sort-Object -Unique to see if it improves performance like I hope it will.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@KirkMunro
Added -Top/-Bottom params to Sort-Object for Top/Bottom N sorts; adde…
b92e354 
…d many Pester tests
@msftclas

Microsoft Contribution License Agreements (msftclas) commented Oct 21, 2016

Copy link
Copy Markdown

Hi Kirk Munro (@KirkMunro), I'm your friendly neighborhood Microsoft Pull Request Bot (You can call me MSBOT). Thanks for your contribution!
You've already signed the contribution license agreement. Thanks!

The agreement was validated by Microsoft and real humans are currently evaluating your PR.

TTYL, MSBOT;
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@msftclas Microsoft Contribution License Agreements (msftclas) added the cla-already-signed label Oct 21, 2016
Kirk Munro (KirkMunro) added 3 commits October 21, 2016 17:22
@KirkMunro
updated changelog
03d3764
@KirkMunro
Merge branch 'master' into sort-top-or-bottom
a45e847
@KirkMunro
updated CHANGELOG.md
d8889e3
@KirkMunro

Kirk Munro (KirkMunro) commented Oct 21, 2016

Copy link
Copy Markdown
Contributor Author

I'm not entirely sure what to do with the failures in AppVeyor/Travis CI. Saw on another PR thread that sergei (@vors) indicated there were some problems due to changes in .NET Core that he was looking into. These changes build fine on my machine, so pointers if I need to do anything would be helpful. Thanks.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@vors sergei (vors) closed this Oct 22, 2016
@vors sergei (vors) reopened this Oct 22, 2016
@msftclas

Microsoft Contribution License Agreements (msftclas) commented Oct 22, 2016

Copy link
Copy Markdown

Hi Kirk Munro (@KirkMunro), I'm your friendly neighborhood Microsoft Pull Request Bot (You can call me MSBOT). Thanks for your contribution!
You've already signed the contribution license agreement. Thanks!

The agreement was validated by Microsoft and real humans are currently evaluating your PR.

TTYL, MSBOT;
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@msftclas Microsoft Contribution License Agreements (msftclas) added the cla-already-signed label Oct 22, 2016
@vors

sergei (vors) commented Oct 22, 2016

Copy link
Copy Markdown
Collaborator

Reopened PR to re-trigger the execution on the fixed master
KirkMunro reacted with hooray emoji
All reactions
  • 🎉 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@KirkMunro
replaced Get-Service with Get-Alias in Pester tests
18c8668
iSazonov
Ilya (iSazonov) reviewed Oct 22, 2016
View reviewed changes
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated
}
}

} No newline at end of file

@iSazonov Ilya (iSazonov) Oct 22, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Add new line.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 22, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Why?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@iSazonov Ilya (iSazonov) Oct 22, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

http://stackoverflow.com/questions/729692/why-should-text-files-end-with-a-newline

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs
/// <summary>
///
/// </summary>
[Cmdlet("Sort", "Object", HelpUri = "https://go.microsoft.com/fwlink/?LinkID=113403", RemotingCapability = RemotingCapability.None)]

@iSazonov Ilya (iSazonov) Oct 22, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Avoid unnecessary formatting

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 22, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

The formatting is not unnecessary. I added DefaultParameterSetName to the Cmdlet attribute. The line becomes far too long and hard to read. Formatting makes the content readable without unnecessary side-scrolling. Unless the PS Team requires this change for some reason, this code stays as is.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1
}
}

Describe 'Sort-Object Top and Bottom Unit Tests' -Tags 'CI' {

@iSazonov Ilya (iSazonov) Oct 22, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Consider grouping similar tests below in Context

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 22, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

If I need to go into this PR to address issues with the logic I'll consider adding context to the Pester tests. Otherwise they are grouped as other tests in the file were grouped, and I'm comfortable with that.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated
Describe 'Sort-Object Top and Bottom Unit Tests' -Tags 'CI' {

It 'Return the top N integers sorted in ascending order' {
$unsortedData = 973474993,271612178,-1258909473,659770354,1829227828,-1709391247,-10835210,-1477737798,1125017828,813732193

@iSazonov Ilya (iSazonov) Oct 22, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

  1. Move duplicate initializers to BeforeAll {} (and throughout all code below too)
  2. Why do you use so complex data? I would prefer 1,2,-3,... a,b,z,... Enough 5 or 6 values.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 22, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

BeforeAll isn't documented (I didn't even know it existed), and I simply followed the model in the file already.

The numeric data used was intentionally generated using Get-Random with the range of all int values so that the test would result in a random outcome that covered a broad base of numeric input. With sorting and -Top/-Bottom, 5 or 6 values to start with is not always a sufficient test, so I'll leave it with 10 values.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@iSazonov Ilya (iSazonov) Oct 22, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Many tests on this repository contain BeforeAll. See these examples.

Simple source data easier to understand and easier to maintain. I would say that it is better to have the test which return results you can evaluate your own eyes.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

As per our test guidelines, please do use BeforeAll.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated
for ($i = 0; $i -lt $topNSortResults.Count; $i++) {
$topNSortResults[$i] | Should Be $fullSortResults[$i]
}
}

@iSazonov Ilya (iSazonov) Oct 22, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

It would be better to move repeated code to functions.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 22, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I had written a function at first, with the tests being simply one or two lines of code; this resulted in a complicated function which would have to be tested by itself. I really didn't like this model, and preferred a short test with a half-dozen lines of code or so, which allows anyone to review a failing test in place and see more easily why it may be failing, plus enable testing outside of Pester by simply copying and pasting the test contents.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@iSazonov

Ilya (iSazonov) commented Oct 22, 2016

Copy link
Copy Markdown
Collaborator

Kirk Munro (@KirkMunro) Thanks for Sort-Object improvements!

A separate issue should probably be created to investigate SortedSet with Sort-Object -Unique to see if it improves performance like I hope it will.

Feel free to open the Issue now! I believe that performance improving is the right direction.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@iSazonov

Ilya (iSazonov) commented Oct 22, 2016 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Collaborator

Kirk Munro (@KirkMunro) Could you please rebase your branch (and drop unnecessary commits) ? Your PR contains some merge commits.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
lzybkr
Jason Shirk (lzybkr) suggested changes Oct 24, 2016
View reviewed changes
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated
/// <summary>
/// This is a single entry in the min-/max-heap used for top N/bottom N sorts
/// </summary>
public sealed class IndexedMinMaxHeapEntry

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

This doesn't need to be public, right?
Also consider making this a struct, it seems like that would be a win performance wise.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 26, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Changed locally, will commit with other changes soon. On the struct comment, should this be a struct as well then, for the performance win?

    internal sealed class OrderByPropertyEntry
    {
        internal PSObject inputObject = null;
        internal List<ObjectCommandPropertyValue> orderValues = new List<ObjectCommandPropertyValue>();
    }

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated
}
}

internal OrderByPropertyEntry Entry { get; } = null;

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Avoid initializing properties with their default values. Old code may be doing this, but there is no reason to do so and we'll fix the old code eventually.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 26, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Fixed locally, will commit soon.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated

internal OrderByPropertyEntry Entry { get; } = null;
internal int Index { get; } = -1;
internal bool Sortable { get; } = false;

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Again, avoid initializing properties with their default values.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 26, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Fixed locally, will commit soon.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated
else
{
// The heap entry comparer will sort the items in the heap
var comparer = new IndexedMinMaxHeapComparer(orderByProperty.Comparer);

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

The actual sort should be in it's own method.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 26, 2016 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Moved entire body of else block except for WriteObject to new Heapify method, will commit soon.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated
{
// There may be a faster algorithm to sort while eliminating duplicates and retaining only
// the top N records; for now though, this gets the job done
listToOutput = listToOutput.GetRange(0, Top);

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

This needlessly creates a new list and copies the elements.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 26, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Replaced with RemoveRange, will commit soon.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@lzybkr Jason Shirk (lzybkr) Oct 26, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

RemoveRange might be worse - it copies and clears.

I was thinking of iterating over the range explicitly with integers instead of the enumerator of the list.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1
}

Describe "Sort-Object DRT Unit Tests" -Tags "CI" {
It "Sort-Object with object array should work"{

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

As per our guidelines, avoid formatting changes. I realize test files are inconsistent w.r.t. tabs vs. spaces, but we want to keep meaningful additions in different commits from formatting changes.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 26, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Jason Shirk (@lzybkr) Understood. So should I convert that file back to use tabs instead of spaces?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@lzybkr Jason Shirk (lzybkr) Oct 26, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Please do.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated
Describe 'Sort-Object Top and Bottom Unit Tests' -Tags 'CI' {

It 'Return the top N integers sorted in ascending order' {
$unsortedData = 973474993,271612178,-1258909473,659770354,1829227828,-1709391247,-10835210,-1477737798,1125017828,813732193

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

As per our test guidelines, please do use BeforeAll.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated

It 'Return the top N integers sorted in ascending order' {
$unsortedData = 973474993,271612178,-1258909473,659770354,1829227828,-1709391247,-10835210,-1477737798,1125017828,813732193
$baseSortParameters = @{}

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

It seems silly to splat an empty hashtable.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated

It 'Return the top N integers sorted in descending order' {
$unsortedData = 973474993,271612178,-1258909473,659770354,1829227828,-1709391247,-10835210,-1477737798,1125017828,813732193
$baseSortParameters = @{Descending=$true}

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

It seems a little silly to splat a single parameter here.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated
}

It 'Return the top N objects from a collection of different types of objects, sorted in descending order' {
$unsortedData = @(

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Why not create $unsortedData just once in BeforeAll?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@lzybkr Jason Shirk (lzybkr) Oct 24, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Actually, after a closer look, these tests are a good example of why Pester has a parameter -TestCases to It. Please consider changing the tests to use -TestCases, I think it will simplify these test quite a bit.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@vors sergei (vors) added the Review - Waiting on Author label Oct 27, 2016
@vors sergei (vors) assigned Jason Shirk (lzybkr) Oct 27, 2016
@KirkMunro
improved performance for -unique -top/-bottom, changed according to P…
f4be015 
…R feedback
@KirkMunro

Kirk Munro (KirkMunro) commented Oct 28, 2016

Copy link
Copy Markdown
Contributor Author

Jason Shirk (@lzybkr): All changes requested on this discussion have been addressed and committed to this PR. I'm not sure what I need to do to respond to your requested changes other than send this note. One very noteworthy change came out of this discussion: since you highlighted that List.Remove had a strong negative impact on performance vs in-place sorting of the items in the list, I was able to get a 5x performance improvement out of -Unique -Top/-Bottom sorts, which is great! On a collection of 250K random values between 1 and 175K, Sort -Unique performs 5x faster than before, it performs slightly faster than that with -Bottom N, and it performs faster than that with -Top N. Non-unique -Top/-Bottom N sorts perform more than 2x faster than a base sort (and even more than that with sort | select -First/-Last). As suggested by Ilya (@iSazonov), I will blog about this change set, probably in an article for PowerShell Magazine. I'm just waiting for results from appveyor/travis CI and will respond to any issues they have if they come up.
lzybkr reacted with heart emoji
All reactions
  • ❤️ 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@iSazonov

Ilya (iSazonov) commented Oct 28, 2016

Copy link
Copy Markdown
Collaborator

Kirk Munro (@KirkMunro) Please rebase your branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@KirkMunro

Kirk Munro (KirkMunro) commented Oct 28, 2016

Copy link
Copy Markdown
Contributor Author

Ilya (@iSazonov) I did rebase my branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@KirkMunro

Kirk Munro (KirkMunro) commented Oct 28, 2016 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

Something is clearly wrong because this PR now shows 26 files changed, yet when I compare my branch here (master...KirkMunro:sort-top-or-bottom) it properly shows 4 files have changed. sigh I didn't have this issue before I rebased my branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@iSazonov

Ilya (iSazonov) commented Oct 28, 2016

Copy link
Copy Markdown
Collaborator

Rebase is also my headache 😊
From my notes (maybe help you):

# rebase pull request on top of master
git chechout <branch>
git fetch PowerShell master
git pull --rebase PowerShell master
git push -f
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@lzybkr

Jason Shirk (lzybkr) commented Oct 28, 2016

Copy link
Copy Markdown
Contributor

I'm glad the improvements were notable. Please do fix the commits in the PR and I'll finish reviewing.

For future reference, when we merge, we decide if we'll squash, rebase, or commit with a merge commit, so it's not normally necessary for most folks to rebase themselves.

That said, it is useful to be comfortable with rebase.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@KirkMunro
added newlines to end of two files
5bee3fd
@KirkMunro
Kirk Munro (KirkMunro) force-pushed the sort-top-or-bottom branch from 7cd9e22 to 5bee3fd Compare October 28, 2016 17:46
Kirk Munro (KirkMunro) added 2 commits October 28, 2016 15:49
@KirkMunro
Removed whitespace changes
6f58e1d
@KirkMunro
Missed 2 whitespace changes to undo in last commit
0f4c36f
@KirkMunro
Updated to try to resolve merge issue
9e9ebea
@KirkMunro

Kirk Munro (KirkMunro) commented Oct 28, 2016 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

Jason Shirk (@lzybkr) Commit cleanup finished and checks passed, awaiting your review.

I should add one note: I didn't benchmark using struct vs class because I moved my additional properties into the existing class and changing that to a struct was non-trivial due to other dependencies (Compare-Object, Group-Object) and outside of the scope of this work.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@iSazonov

Ilya (iSazonov) commented Oct 28, 2016

Copy link
Copy Markdown
Collaborator

Kirk Munro (@KirkMunro) Great work!!!
I looked up the new tests. They are very elegant. But why haven't you moved a initialize codes in BeforeAll?
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
lzybkr
Jason Shirk (lzybkr) suggested changes Oct 28, 2016
View reviewed changes

@lzybkr Jason Shirk (lzybkr) left a comment

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

OK - this is looking pretty good.

I think it's easy to make -Unique much faster with -Top and -Bottom - can you take a look?

Other than that, I just noticed a couple little things that would be nice to clean up.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated
/// <summary>
/// Sort unsorted OrderByPropertyEntry data using an indexed min-/max-heap sort
/// </summary>
private List<OrderByPropertyEntry> Heapify(List<OrderByPropertyEntry> dataToSort, OrderByPropertyComparer orderByPropertyComparer, out int heapCount)

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Returning the heap suggests it's not done in place even though it is.

Maybe return heapCount instead?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 29, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Yeah, I should have made that change when I switched to in-place sorting. It's done locally now.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated
{
RemoveDuplicates(orderByProperty);
}
// Note: It may be worth compariing List.Sort with SortedSet.Sort when handling unique records in

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

spelling: compariing

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 29, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Fixed local, thanks.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs

// Min-heap: if the child item is larger than its parent, break
// Max-heap: if the child item is smaller than its parent, break
if (comparer.Compare(dataToSort[childIndex], dataToSort[parentIndex]) == comparator)

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Can you handle -Unique here too? If they compare equal, you just skip the item, right?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 29, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I don't think it's that simple. When I looked at supporting -Unique in heapify, my initial reaction was that it wouldn't work, at least not the way you might think. Since the data in the heap is not sorted, the challenge when checking for uniqueness of each value is which values you compare against. If the next value could go into the heap (as determined by comparing with the root), then I'd have to look at children of the current item (root) to see if I either find the same item or determine whether or not it would be possible to find the same item in a child of the item (in which case I'd have to recurse into that child item and repeat with its children). Worst case would result in N comparisons, where N is the size of the heap. Best case would be 1 comparison. Anyhow, that's roughly what I thought would be required. I could try it and see how well (or not) that performs vs the current method.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated
param($nSortEntry, $fullSortEntry)
if ($nSortEntry -is [System.Array]) {
# Arrays must be compared differently than everything else
$nSortEntry.Equals($fullSortEntry) | Should Be $true

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Array.Equals is reference equality - so this can't be what you meant.

Array does implement IStructuralEquatable, so if you can create an EqualityComparer, you could use something like:

([System.Collections.IStructuralEquatable]$nSortEntry).Equals($fullSortEntry,
    [System.Collections.Generic.EqualityComparer[int]]::Default) | Should Be $true

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Or if you really meant to use reference equality, use [object]::ReferenceEquality and add a comment why.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 29, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I'll add the comment and update to the other reference equality test you suggested. I use reference equality because I'm verifying arrays are sorted into the proper position.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread src/Microsoft.PowerShell.Commands.Utility/commands/utility/sort-object.cs Outdated

// If -Unique was used, if -Top & -Bottom were not used, or if -Top or -Bottom would return all objects, sort
// all objects, remove duplicates if necessary, and identify the list of items to return
if (_unique || (Top == 0 && Bottom == 0) || Top >= dataToProcess.Count || Bottom >= dataToProcess.Count)

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Am I mistaken in assuming you can easily handle -Unique in heapify?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 31, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Same comment about -Unique and heapify applies here. I'm testing something with it though to see what impact it might have.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated

It 'Return the <nSortType> N sorted in <orderType> order' -TestCases $topBottomAscendingDescending {
param([string]$nSortType, [string]$orderType)
$baseSortParameters = if ($orderType -eq 'Descending') {@{Descending = $true}} else {@{}}

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

As long as you're splatting, you can simplify with something like:

... = @{Descending = $orderType -eq 'descending'}

And you decide to change this, you might as well fix the case to be consistent.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 29, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

As is, if you're doing an ascending sort, no parameter is passed. If I change this then an ascending sort passes -Descending:$false. I suppose for my tests that doesn't matter much since I'm verifying output order and not explicitly testing the switch parameter, so I changed it to simplify the logic (that's what I had before anyway).

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1 Outdated
Context 'Heterogeneous n-sort' {

$unsortedData = @(
($item0 = 'x')

@lzybkr Jason Shirk (lzybkr) Oct 28, 2016

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

You aren't using any of the assignments, so can they be removed?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 29, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Sure, I removed them. I would use the assignments when testing various things outside of Pester, but it's good now so I took them out.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Kirk Munro (KirkMunro) added 2 commits October 29, 2016 11:00
@KirkMunro
change heapify return type, cleaned up test code
77b398f
@KirkMunro
Merge branch 'sort-top-or-bottom' of https://github.com/KirkMunro/Pow…
2f83ea9 
…erShell into sort-top-or-bottom
iSazonov
Ilya (iSazonov) reviewed Oct 29, 2016
View reviewed changes
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1
# Arrays must be compared differently than everything else
$nSortEntry.Equals($fullSortEntry) | Should Be $true
# Arrays are compared using reference equality to ensure that the original array was
# moved to the correct position in both sorts; value equality doesn't verify this

@iSazonov Ilya (iSazonov) Oct 29, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

My first thought was about Compare-Object, because many tests using it, but Sort-Object is specific. So maybe for the future explicitly add: 'Compare-Object is not applicable here!'

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
Comment thread test/powershell/Modules/Microsoft.PowerShell.Utility/Sort-Object.Tests.ps1
$topBottom = @(
@{nSortType='Top' }
@{nSortType='Bottom'}
)

@iSazonov Ilya (iSazonov) Oct 29, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Previously I had in mind, that these variables ($topBottom and $topBottomAscendingDescending) are good candidates to move in BeforeAll.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 31, 2016

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

That doesn't buy anything though -- those variables don't change.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@iSazonov Ilya (iSazonov) Oct 31, 2016

Copy link
Copy Markdown
Collaborator

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

The specificity is that this is not an ordinary script - Pester makes parsing and execution operators. BeforeAll is the result of the fact that it does not guarantee the order of execution. Thus all the common code (including function) within Describe must be inside BeforeAll.
You can see the most correct sample here

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions

@KirkMunro Kirk Munro (KirkMunro) Oct 31, 2016 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

it does not guarantee the order of execution

Where are you getting that from? Pester is not documented that way, and based on how PowerShell works I don't believe that's the case. And if it is changed to work that way, then plenty of Pester tests could start breaking.

You've shared one example where BeforeAll is being used to define functions, etc. however there are many other examples where BeforeAll is not being used in the test harness for PowerShell Core yet variables are assigned, functions are loaded, etc. There's nothing in the Pester documentation about it running tests asynchronously, and even if it did, it would still have to load those tests, which would execute the code for those tests. Changing that behaviour in Pester would be a breaking change.

Since they are not documented, and since I don't have time to go read the code to figure out what they do, I can only ascertain that BeforeAll/AfterAll are much like begin/end blocks, where you can do resource management, make sure certain things are loaded before tests and unloaded afterwards. Other than that, I don't believe there is any advantage whatsoever to using BeforeAll over defining the functions/variables inside of a Context block instead.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@KirkMunro
unique top/bottom N sorts are now 2-3 times faster
1def6c0
@KirkMunro

Kirk Munro (KirkMunro) commented Nov 2, 2016 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

I just committed an update that improves -unique -top/-bottom sorts performance substantially. On a collection of 500K integers that were generated randomly with values from 1 to 175K, sort -unique took 18 seconds to complete, and with the previous implementation a -Top/-Bottom N -Unique sort would finish slightly faster than that, in around 17 seconds. With these changes, the -Top/-Bottom N -Unique sort finishes in a little over 6 seconds.

I couldn't make this work with the min-/max-heap sort without either walking the heap to see if an item was already added, since an item could be anywhere in the heap. Walking the heap could result in comparing a new item with every item in the heap in the worst case. Instead I decided to add another collection to track the unique items. I use SortedSet to store anything unique that is added to the heap, and then skip items that are already in that set instead of adding them to the heap. This seems pretty efficient, and definitely improves the performance.

Jason Shirk (@lzybkr) Let me know what you think of this commit when you have time to review the most recent changes. Thanks!

[Update] I committed a follow-up change that removes a few lines that weren't necessary due to the changes I just made, and cleaned up the code in sort-object.cs based on my changes so that it's easier to follow.
iSazonov reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@KirkMunro
code cleanup (removed unused vars, simplified logic)
097247c
@lzybkr
Jason Shirk (lzybkr) merged commit 244827a into PowerShell:master Nov 4, 2016
@lzybkr

Jason Shirk (lzybkr) commented Nov 4, 2016

Copy link
Copy Markdown
Contributor

Great work Kirk Munro (@KirkMunro).

A Set should be fine for typical uses of Top/Bottom w/ -Unique because I'd expect Top/Bottom to be small relative to the total number of objects.

If that assumption is wrong, we could look at insertion sort.
KirkMunro reacted with hooray emoji
All reactions
  • 🎉 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@IISResetMe Mathias R. Jessen (IISResetMe) mentioned this pull request Sep 22, 2018
Sort-Object inappropriately sacrifices stability for performance #7846
Closed
@iSazonov Ilya (iSazonov) removed the Review - Waiting on Author label Nov 29, 2018
@KirkMunro Kirk Munro (KirkMunro) mentioned this pull request Nov 29, 2018
Add -Stable to Sort-Object and related tests #7862
Merged
7 of 11 tasks
@KirkMunro
Kirk Munro (KirkMunro) deleted the sort-top-or-bottom branch January 7, 2019 21:23
Thatgfsj (Thatgfsj) pushed a commit to Thatgfsj-contribs/PowerShell that referenced this pull request Aug 6, 2026
@KirkMunro @lzybkr
Added -Top/-Bottom params to Sort-Object for Top/Bottom N sort and ma…
fe71deb 
…ny Pester tests (PowerShell#2518)

* Added -Top/-Bottom params to Sort-Object for Top/Bottom N sorts; added many Pester tests

* updated changelog

* updated CHANGELOG.md

* replaced Get-Service with Get-Alias in Pester tests

* improved performance for -unique -top/-bottom, changed according to PR feedback

* added newlines to end of two files

* Removed whitespace changes

* Missed 2 whitespace changes to undo in last commit

* Updated to try to resolve merge issue

* change heapify return type, cleaned up test code

* unique top/bottom N sorts are now 2-3 times faster

* code cleanup (removed unused vars, simplified logic)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@iSazonov Ilya (iSazonov) iSazonov left review comments
+1 more reviewer
@lzybkr Jason Shirk (lzybkr) lzybkr requested changes
Reviewers whose approvals may not affect merge requirements

Uh oh!

There was an error while loading. Please reload this page.

Assignees

@lzybkr Jason Shirk (lzybkr)

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

5 participants

@KirkMunro @msftclas @vors @iSazonov @lzybkr
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.