Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
zadjii-msft opened this issue Sep 10, 2019 · 3 comments
Labels
Area-CodeHealth Issues related to code cleanliness, linting, rules, warnings, errors, static analysis, etc. Help Wanted We encourage anyone to jump in on these. Issue-Bug It either shouldn't be doing this or needs an investigation. Needs-Tag-Fix Doesn't match tag requirements Priority-3 A description (P3) Product-Terminal The new Windows Terminal.

Comments

@zadjii-msft
Copy link
Member

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.

@zadjii-msft zadjii-msft added Help Wanted We encourage anyone to jump in on these. Issue-Bug It either shouldn't be doing this or needs an investigation. Product-Terminal The new Windows Terminal. Area-CodeHealth Issues related to code cleanliness, linting, rules, warnings, errors, static analysis, etc. labels Sep 10, 2019
@zadjii-msft zadjii-msft added this to the Terminal Backlog milestone Sep 10, 2019
@ghost ghost added the Needs-Triage It's a new issue that the core contributor team needs to triage at the next triage meeting label Sep 10, 2019
@DHowett-MSFT DHowett-MSFT removed the Needs-Triage It's a new issue that the core contributor team needs to triage at the next triage meeting label Sep 16, 2019
@DHowett-MSFT
Copy link
Contributor

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

@ZhaoMJ
Copy link
Contributor

ZhaoMJ commented 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.

@zadjii-msft
Copy link
Member Author

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

@ghost ghost added the Needs-Tag-Fix Doesn't match tag requirements label Dec 9, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Area-CodeHealth Issues related to code cleanliness, linting, rules, warnings, errors, static analysis, etc. Help Wanted We encourage anyone to jump in on these. Issue-Bug It either shouldn't be doing this or needs an investigation. Needs-Tag-Fix Doesn't match tag requirements Priority-3 A description (P3) Product-Terminal The new Windows Terminal.
Projects
None yet
Development

No branches or pull requests

4 participants