Select-Object -Unique is unnecessary slow and exhaustive

[heaths]

Steps to reproduce

# Contrived example; imagine a pipelined collection of a lot of large objects.
get-childitem c:\ -recurse -ea silentlycontinue | select-object Name -unique

Expected behavior

Items with a unique name are output immediately to the host.

Actual behavior

Items are buffered and require a large amount of memory and a ridiculous amount of time.

Reason

Passing -Unique creates a List<T> to store all items, and performance is O(n^2) based on this source. Instead, you could instead create a key based on properties selected or some other heuristic. In fact, using that same ObjectCommandComparer, you could probably even use its GetHashCode (if implemented properly). I have been using my own Select-Unique for years quite successfully. It has O(n) performance and uses very little memory. Its key algorithm is roughly copied from what Group-Object does.

I had to write this when I was trying to filter unique items in a huge graph of objects. In that particular case, Select-Object -Unique ended up throwing an OutOfMemoryException. My version didn't and was much faster to use even on smaller data sets.

Environment data

Name                           Value
----                           -----
PSVersion                      6.2.3
PSEdition                      Core
GitCommitId                    6.2.3
OS                             Microsoft Windows 10.0.18362 
Platform                       Win32NT
PSCompatibleVersions           {1.0, 2.0, 3.0, 4.0…}
PSRemotingProtocolVersion      2.3
SerializationVersion           1.1.0.1
WSManStackVersion              3.0

[iSazonov]

@heaths Thanks for raising the issue! Have you plans to contribute?

[heaths]

I was thinking about it. I need to see what the test suite is like. This is an oft-used cmdlet so the bar is extremely high.

[iSazonov]

Yes, the cmdlet is complex and sensitive. If you see any gaps in tests we could discuss and add new ones.
My concern is about switching from generated comparer to string keys. Perhaps @lzybkr and @KirkMunro could add more info.

[heaths]

A generated comparer could still work if it implements or works like IEqualityComparer<T>, which can still be used for maps. A string key in my implementation was a quick and simple little hack that has so far worked, but it doesn't get nearly the use select-object does.

[iRon7]

I just noticed the same behavior: Select-Object -Unique stalls the pipeline for no reason:

1,2,3,1,4 | ForEach-Object {Write-Host 'In:' $_; $_} |
Select-Object -Unique | ForEach-Object {Write-Host 'Out:' $_}
In: 1
In: 2
In: 3
In: 1
In: 4
Out: 1
Out: 2
Out: 3
Out: 4

Where I would expect it to return in this order:

In: 1
Out: 1
In: 2
Out: 2
In: 3
Out: 3
In: 1
In: 4
Out: 4

Related to StackOverflow question: Which way is better in PowerShell and why

[iSazonov]

@iRon7 It is easy to implement. Do you want pull PR?

Also we could cache a comparer in the code - while we get objects with the same type from pipeline we will get a perf win.

[iRon7]

@iSazonov, I think I might say that I some knowledge of PowerShell itself and programming in general, but I am still learning C# and haven't pulled any PR so far. I am afraid this is above my head.
Anyways, I am happy to investigate this a little deeper presuming that the first step for me is to get familiar with the processes behind this: see e.g. if I can compile a new Select-Object and run the related tests.
Can you point me to a general instruction of what processes I should follow?

[iSazonov]

@iRon7

I am still learning C#

I started from level zero. I liked C # and I was looking for a project where I could benefit. I chose this project because it is a high-quality code and the best experts. In these conditions, training is happening rapidly. I started by monitoring PRs. This provided an understanding of the process, style and key points. When you try to understand changes in a PR, it educates great. After that, you begin code review and commenting. You can spend it 5 minutes or an hour a day for your pleasure. Then you can try to prepare the environment and compile the project. But first you have to read documents in the repo. They can be outdated and you can update them in your first PRs to get experience with contributing process and git. This is my experience.

[vexx32]

@iRon7 I'd start from here: https://github.com/PowerShell/PowerShell/blob/master/README.md#building-the-repository

Once you can get it built, you can find most common commands in the src folder, sorted into subfolders based on which module they're part of. I believe Select-Object is in Microsoft.PowerShell.Utility so you should be able to find it in that folder. Most commands are named VerbNounCommand so I'd start looking for SelectObjectCommand, but there are some exceptions, so you might just want to search for SelectObject and see where that gets you.

You can sometimes find things searching the PS cmdlet name in full Select-Object, but that will typically only appear in documentation comments more than anything, so you might have trouble finding things using that.

If you're not used to C#, @iSazonov's suggestions will help a lot when it comes to getting familiar with it, but equally I'd say tinkering around with a cmdlet or two would also be a great way to get a feel for things.

---

On the most recent aspect of this issue specifically, where Select-Object seems to be waiting until the end of the pipeline to send off output when using -Unique, I'd think you can remedy that by simply outputting each object in ProcessRecord. It'll most likely be adding each unique object to some cached collection that it uses to ensure each object is unique, so you can build off of that by just outputting objects as they're added to the collection. Once that's working, just remember to remove the output in EndProcessing that most likely occurs when using -Unique, so you don't duplicate the output.

GitHub

PowerShell/PowerShell

PowerShell for every system! Contribute to PowerShell/PowerShell development by creating an account on GitHub.