Skip to content

Tab completion in large folders is very slow #4797

New issue
New issue
Closed
#19489
Closed
Tab completion in large folders is very slow#4797
#19489
Labels
HacktoberfestPotential candidate to participate in HacktoberfestResolution-FixedThe issue is fixed.Usability(LEGACY) Helps filter issues that might be higher priority because they directly affect usabilityWG-Engine-Performancecore PowerShell engine, interpreter, and runtime performanceWG-Interactive-IntelliSensetab completion

Description

@vors
sergei (vors)
opened on Sep 10, 2017

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

Activity

  1. sergei (vors)
    added
    Usability(LEGACY) Helps filter issues that might be higher priority because they directly affect usability
    on Sep 10, 2017
  2. Steve Lee (SteveL-MSFT)
    added
    WG-Interactive-IntelliSensetab completion
    on Sep 10, 2017
  3. sergei (vors)
    added
    HacktoberfestPotential candidate to participate in Hacktoberfest
    on Feb 20, 2018

  4. Scholars-Mate commented on Feb 25, 2018

    @Scholars-Mate
    Christopher Wong (Scholars-Mate)
    on Feb 25, 2018

    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:

    PowerShell/src/System.Management.Automation/engine/CommandCompletion/CompletionCompleters.cs

    Lines 4072 to 4077 in 16d7a62

    powerShellExecutionHelper
    .AddCommandWithPreferenceSetting("Microsoft.PowerShell.Management\\Resolve-Path")
    .AddParameter("Path", wordToComplete + "*");
    Exception exceptionThrown;
    var psobjs = powerShellExecutionHelper.ExecuteCurrentPowerShell(out exceptionThrown);

    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:

    PowerShell/src/System.Management.Automation/engine/CommandCompletion/CompletionCompleters.cs

    Lines 4215 to 4373 in 16d7a62

    foreach (PSObject psobj in sortedPsobjs)
    {
    object baseObj = PSObject.Base(psobj);
    string path = null, providerPath = null;
    // Get the path, the PSObject could be:
    // 1. a PathInfo object -- results of Resolve-Path
    // 2. a FileSystemInfo Object -- results of Get-ChildItem
    // 3. a string -- the path results return by the direct .NET API invocation
    var baseObjAsPathInfo = baseObj as PathInfo;
    if (baseObjAsPathInfo != null)
    {
    path = baseObjAsPathInfo.Path;
    providerPath = baseObjAsPathInfo.ProviderPath;
    }
    else if (baseObj is FileSystemInfo)
    {
    // The target provider is the FileSystem
    dynamic dirResult = psobj;
    providerPath = dirResult.FullName;
    path = wordContainsProviderId ? dirResult.PSPath : providerPath;
    }
    else
    {
    var baseObjAsString = baseObj as string;
    if (baseObjAsString != null)
    {
    // The target provider is the FileSystem
    providerPath = baseObjAsString;
    path = wordContainsProviderId
    ? FileSystemProvider.ProviderName + "::" + baseObjAsString
    : providerPath;
    }
    }
    if (path == null) continue;
    if (isFileSystem && providerPath == null) continue;
    string completionText;
    if (relativePaths)
    {
    try
    {
    var sessionStateInternal = executionContext.EngineSessionState;
    completionText = sessionStateInternal.NormalizeRelativePath(path, sessionStateInternal.CurrentLocation.ProviderPath);
    string parentDirectory = ".." + Path.DirectorySeparatorChar;
    if (!completionText.StartsWith(parentDirectory, StringComparison.Ordinal))
    completionText = Path.Combine(".", completionText);
    }
    catch (Exception)
    {
    // The object at the specified path is not accessable, such as c:\hiberfil.sys (for hibernation) or c:\pagefile.sys (for paging)
    // We ignore those files
    continue;
    }
    }
    else
    {
    completionText = path;
    }
    if (ProviderSpecified(completionText) && !wordContainsProviderId)
    {
    // Remove the provider id from the path: cd \\scratch2\scratch\dongbw
    var index = completionText.IndexOf(':');
    completionText = completionText.Substring(index + 2);
    }
    if (CompletionRequiresQuotes(completionText, !useLiteralPath))
    {
    var quoteInUse = quote == string.Empty ? "'" : quote;
    if (quoteInUse == "'")
    {
    completionText = completionText.Replace("'", "''");
    }
    else
    {
    // When double quote is in use, we have to escape the backtip and '$' even when using literal path
    // Get-Content -LiteralPath ".\a``g.txt"
    completionText = completionText.Replace("`", "``");
    completionText = completionText.Replace("$", "`$");
    }
    if (!useLiteralPath)
    {
    if (quoteInUse == "'")
    {
    completionText = completionText.Replace("[", "`[");
    completionText = completionText.Replace("]", "`]");
    }
    else
    {
    completionText = completionText.Replace("[", "``[");
    completionText = completionText.Replace("]", "``]");
    }
    }
    completionText = quoteInUse + completionText + quoteInUse;
    }
    else if (quote != string.Empty)
    {
    completionText = quote + completionText + quote;
    }
    if (isFileSystem)
    {
    // Use .NET APIs directly to reduce the time overhead
    var isContainer = Directory.Exists(providerPath);
    if (containerOnly && !isContainer)
    continue;
    if (!containerOnly && !isContainer && !CheckFileExtension(providerPath, extension))
    continue;
    string tooltip = providerPath, listItemText = Path.GetFileName(providerPath);
    results.Add(new CompletionResult(completionText, listItemText,
    isContainer ? CompletionResultType.ProviderContainer : CompletionResultType.ProviderItem,
    tooltip));
    }
    else
    {
    powerShellExecutionHelper
    .AddCommandWithPreferenceSetting("Microsoft.PowerShell.Management\\Get-Item")
    .AddParameter("LiteralPath", path);
    var items = powerShellExecutionHelper.ExecuteCurrentPowerShell(out exceptionThrown);
    if (items != null && items.Count == 1)
    {
    dynamic item = items[0];
    var isContainer = LanguagePrimitives.ConvertTo<bool>(item.PSIsContainer);
    if (containerOnly && !isContainer)
    continue;
    powerShellExecutionHelper
    .AddCommandWithPreferenceSetting("Microsoft.PowerShell.Management\\Convert-Path")
    .AddParameter("LiteralPath", item.PSPath);
    var tooltips = powerShellExecutionHelper.ExecuteCurrentPowerShell(out exceptionThrown);
    string tooltip = null, listItemText = item.PSChildName;
    if (tooltips != null && tooltips.Count == 1)
    {
    tooltip = PSObject.Base(tooltips[0]) as string;
    }
    if (string.IsNullOrEmpty(listItemText))
    {
    // For provider items that don't have PSChildName values, such as variable::error
    listItemText = item.Name;
    }
    results.Add(new CompletionResult(completionText, listItemText,
    isContainer ? CompletionResultType.ProviderContainer : CompletionResultType.ProviderItem,
    tooltip ?? path));
    }
    else
    {
    // We can get here when get-item fails, perhaps due an acl or whatever.
    results.Add(new CompletionResult(completionText));
    }
    } // End of not filesystem case
    } // End of foreach

    This flame graph, can give some insight into areas that could be improved. The most notable functions are CompletionRequiresQuotes(), ExecuteCurrentPowerShell(), get_ProviderPath(), and NormalizeRelativePath(). Samuel Holland (@smaeul) and sergei (@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.

  5. vors commented on Feb 25, 2018

    @vors
    sergei (vors)
    on Feb 25, 2018
    CollaboratorAuthor

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

    image

  6. powercode commented on Feb 26, 2018

    @powercode
    Staffan Gustafsson (powercode)
    on Feb 26, 2018
    Collaborator

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

  7. vors commented on Feb 27, 2018

    @vors
    sergei (vors)
    on Feb 27, 2018
    CollaboratorAuthor

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

  8. powercode commented on Feb 27, 2018

    @powercode
    Staffan Gustafsson (powercode)
    on Feb 27, 2018
    Collaborator

    sergei (@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.

  9. Rob Holt (rjmholt)
    added
    WG-Engine-Performancecore PowerShell engine, interpreter, and runtime performance
    on May 2, 2018

  10. rjmholt commented on Jul 18, 2018

    @rjmholt
    Rob Holt (rjmholt)
    on Jul 18, 2018
    Collaborator

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

  11. vors commented on Jul 19, 2018

    @vors
    sergei (vors)
    on Jul 19, 2018
    CollaboratorAuthor

    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.

  12. rjmholt commented on Jul 19, 2018

    @rjmholt
    Rob Holt (rjmholt)
    on Jul 19, 2018
    Collaborator

    Oh awesome! Thanks sergei (@vors)!

  13. ghost added
    In-PRIndicates that a PR is out for the issue
    on Apr 11, 2023
  14. Paul Higinbotham (PaulHigin)
    closed this as completedin #19489on May 22, 2023
  15. ghost removed
    In-PRIndicates that a PR is out for the issue
    on May 22, 2023
  16. ghost added
    Resolution-FixedThe issue is fixed.
    on May 22, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    HacktoberfestPotential candidate to participate in HacktoberfestResolution-FixedThe issue is fixed.Usability(LEGACY) Helps filter issues that might be higher priority because they directly affect usabilityWG-Engine-Performancecore PowerShell engine, interpreter, and runtime performanceWG-Interactive-IntelliSensetab completion

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions