starred/terminal
1
0
Fork 0
mirror of https://github.com/microsoft/terminal.git synced 2026-09-24 07:54:35 +00:00
Code Issues 19.0k Packages Projects Releases 20 Wiki Activity

_ReorderProfilesToMatchUserSettingsOrder could almost certainly not be O(N^2) #3831

New Issue
Closed
opened 2026-01-30 23:31:03 +00:00 by claunia · 3 comments
claunia commented 2026-01-30 23:31:03 +00:00
Owner
Copy Link

Originally created by @zadjii-msft on GitHub (Sep 11, 2019).

Follow up to #2603

In #2515, we added a function that reorders profiles to match the order in the user's profiles.json. Unfortunately, it runs in O(N^2), and it almost certainly can not. While we don't believe that the number of profiles is ever high enough that this n^2 loop is ever limiting, it could always be better.

This issue represents re-writing that method to be better.

Originally created by @zadjii-msft on GitHub (Sep 11, 2019). Follow up to #2603 In #2515, we added a function that reorders profiles to match the order in the user's `profiles.json`. Unfortunately, it runs in O(N^2), and it almost certainly can _not_. While we don't believe that the number of profiles is ever high enough that this n^2 loop is ever limiting, it could always be better. This issue represents re-writing that method to be better.
claunia commented 2026-01-30 23:31:05 +00:00
Author
Owner
Copy Link

@DHowett-MSFT commented on GitHub (Sep 16, 2019):

Pulling this one out of Backlog and into v1.0 -- people will have pathological case performance if they have a bunch of profiles :/

@DHowett-MSFT commented on GitHub (Sep 16, 2019): Pulling this one out of Backlog and into v1.0 -- people _will_ have pathological case performance if they have a bunch of profiles :/
claunia commented 2026-01-30 23:31:05 +00:00
Author
Owner
Copy Link

@ZhaoMJ commented on GitHub (Jan 12, 2020):

So I tried to optimize it to O(n) but the effect is minimal since even though it's O(n^2), the constant of swap sort is small and _ReorderProfilesToMatchUserSettingsOrder only costs <2% CPU usage on startup anyway. The actual bottleneck is _FindMatchingProfile, which takes >60% CPU usage and causes _LayerOrCreateProfile to be O(n^2) with a very large constant from ShouldBeLayered.
As per 8/2 Rule, I think _ReorderProfilesToMatchUserSettingsOrder is not worth any optimization, but if you still want an optimization, I'm of course willing to open a PR.
If we really want to optimize the loading of profiles, we have to change _FindMatchingProfile from iterating _profiles every time to an O(1) finding algorithm, probably using std::map as an indexer.

FYI, I tried thousands of hidden profiles and it would take ~10s to start up. Anyway, I think the time of loading is acceptable now since no one actually wants such a crazy number of profiles.

@ZhaoMJ commented on GitHub (Jan 12, 2020): So I tried to optimize it to O(n) but the effect is minimal since even though it's O(n^2), the constant of swap sort is small and `_ReorderProfilesToMatchUserSettingsOrder` only costs <2% CPU usage on startup anyway. The actual bottleneck is `_FindMatchingProfile`, which takes >60% CPU usage and causes `_LayerOrCreateProfile` to be O(n^2) with a very large constant from `ShouldBeLayered`. As per 8/2 Rule, I think `_ReorderProfilesToMatchUserSettingsOrder` is not worth any optimization, but if you still want an optimization, I'm of course willing to open a PR. If we really want to optimize the loading of profiles, we have to change `_FindMatchingProfile` from iterating _profiles every time to an O(1) finding algorithm, probably using std::map as an indexer. FYI, I tried thousands of hidden profiles and it would take ~10s to start up. Anyway, I think the time of loading is acceptable now since no one actually wants such a crazy number of profiles.
claunia commented 2026-01-30 23:31:05 +00:00
Author
Owner
Copy Link

@zadjii-msft commented on GitHub (Dec 9, 2021):

Oh look, that function doesn't exist anymore. Easy enough!

@zadjii-msft commented on GitHub (Dec 9, 2021): Oh look, that function doesn't exist anymore. Easy enough!
Sign in to join this conversation.
No Branch/Tag Specified
Branches Tags
Labels
Clear labels
⛺ Reserved
A11yCO
A11yMAS
A11ySev1
A11ySev2
A11ySev3
A11yTTValidated
A11yUsable
A11yVoiceAccess
A11yWCAG
Area-Accessibility
Area-AtlasEngine
Area-AzureShell
Area-Build
Area-Build
Area-Chat
Area-CmdPal
Area-CodeHealth
Area-Commandline
Area-CookedRead
Area-DefApp
Area-Extensibility
Area-Fonts
Area-GroupPolicy
Area-i18n
Area-Input
Area-Interaction
Area-Interop
Area-Localization
Area-Output
Area-Performance
Area-Portable
Area-Quality
Area-Remoting
Area-Rendering
Area-Schema
Area-Server
Area-Settings
Area-SettingsUI
Area-ShellExtension
Area-ShellExtension
Area-ShellExtension
Area-Suggestions
Area-Suggestions
Area-TerminalConnection
Area-TerminalControl
Area-Theming
Area-UserInterface
Area-VT
Area-Windowing
Area-WPFControl
AutoMerge
Blocking-Ingestion
Culprit-Centennial
Culprit-WinUI
Disability-All
Disability-Blind
Disability-LowVision
Disability-Mobility
External-Blocked-WinUI3
Fixed
Gathering-Data
good first issue
HCL-E+D
HCL-WindowsTerminal
Help Wanted
Impact-Compatibility
Impact-Compliance
Impact-Correctness
Impact-Visual
In-PR
InclusionBacklog
InclusionBacklog-Windows TerminalWin32
InclusionCommitted-202206
Issue-Bug
Issue-Docs
Issue-Feature
Issue-Feature
Issue-Question
Issue-Samples
Issue-Scenario
Issue-Task
Needs-Attention
Needs-Author-Feedback
Needs-Bisect
Needs-Discussion
Needs-Repro
Needs-Tag-Fix
Needs-Tag-Fix
Needs-Triage
No-Recent-Activity
Priority-0
Priority-1
Priority-2
Priority-3
Product-Cmd.exe
Product-Colortool
Product-Colortool
Product-Colortool
Product-Conhost
Product-Conpty
Product-Meta
Product-Powershell
Product-Terminal
Product-WSL
pull-request
Mirrored from GitHub Pull Request
 Resolution-Answered
Resolution-By-Design
Resolution-Duplicate
Resolution-External
Resolution-Fix-Available
Resolution-Fix-Committed
Resolution-No-Repro
Resolution-Won't-Fix
Severity-Blocking
Severity-Crash
Severity-DataLoss
spam
this-will-be-a-breaking-change
Tracking-External
WindowsTerminal_Win32
Work-Item
zAskModeBug
zInbox-Bug
No Label Area-CodeHealth Help Wanted Issue-Bug Needs-Tag-Fix Priority-3 Product-Terminal
Milestone
No items
No Milestone
Projects
Clear projects
No project
Assignees
Clear assignees
claunia
No Assignees
1 Participants
Notifications
Due Date
No due date set.
Dependencies

No dependencies set.

Reference: starred/terminal#3831
Delete Branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?