Powershell: Tab completion in large folders is very slow

[vors]

Steps to reproduce

Get a folder with a decent number of files (65k will do)
Try to do autocompletion on file name in this folder

Expected behavior

Respond time comparable with bash completion (about a second)

Actual behavior

No response for 12 seconds (appears like a hang)

For comparisons, ls | measure in the same folder takes about 4 seconds (3 times faster), which hints that there is a room for improvements even without a big rewrite for the completion logic.

Environment data

> $PSVersionTable
Name                           Value                                           
----                           -----                                           
PSVersion                      6.0.0-beta                                      
PSEdition                      Core                                            
GitCommitId                    v6.0.0-beta.5                                   
OS                             Darwin 16.7.0 Darwin Kernel Version 16.7.0: T...
Platform                       Unix                                            
PSCompatibleVersions           {1.0, 2.0, 3.0, 4.0...}                         
PSRemotingProtocolVersion      2.3                                             
SerializationVersion           1.1.0.1                                         
WSManStackVersion              3.0   

[Scholars-Mate]

I looked into this a little and here's what I found. I used 65,000 empty files in a tmpfs on Debian Stretch. Tab completion in this directory took more than 16 seconds to complete. Pretty much all of the time spent during tab completion is focused in two places:

The globbing done here took around 25% of the time:
https://github.com/PowerShell/PowerShell/blob/16d7a62195cb15156c134748e72ae23bd8923241/src/System.Management.Automation/engine/CommandCompletion/CompletionCompleters.cs#L4072-L4077
Globbing in general seems to be slower than Bash. Running Get-ChildItem * in PowerShell in the directory with 65,000 files takes around 12 seconds compared to less than a second for the Bash equivalent.

The remaining 75% of the time is spent in this large loop:
https://github.com/PowerShell/PowerShell/blob/16d7a62195cb15156c134748e72ae23bd8923241/src/System.Management.Automation/engine/CommandCompletion/CompletionCompleters.cs#L4215-L4373

This flame graph, can give some insight into areas that could be improved. The most notable functions are CompletionRequiresQuotes(), ExecuteCurrentPowerShell(), get_ProviderPath(), and NormalizeRelativePath(). @smaeul and @vors discussed how the provider path could be an easy target for optimization given that all of the results of the tab completion should share the same provider.

[vors]

Thank you @Scholars-Mate for investigating this!
Here is a small glimpse into the flame graph, to encourage others to take a look at it

[powercode]

There is a lot of work going on in .NET core in this area that we should get with the 2.1 release.

[vors]

@powercode do you mean perf tools or performance work we will benefit from? Are we getting something for free in the new dotnet core?

[powercode]

@vors They are doing a ton of work regarding efficient file enumeration/projection, and a lot of getting Span<T> based interfaces in place to reduce allocations. Looks very promising.

I'm a bit involved in getting better abstractions for efficient regex's so we can make Select-String fast.

[rjmholt]

@Scholars-Mate, @vors do you remember how you created that flame graph? It would be really nice to reproduce that for other performance issues!

[vors]

I think we followed this article http://blogs.microsoft.co.il/sasha/2017/02/27/profiling-a-net-core-application-on-linux/
There was not much customization, just make sure to run a debug build with symbols, so the names are populated.

[rjmholt]

Oh awesome! Thanks @vors!