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

Explorer: Reduce call count of isEqualOrParent #45972

Closed
jrieken opened this issue Mar 16, 2018 · 1 comment · Fixed by #46235
Closed

Explorer: Reduce call count of isEqualOrParent #45972

jrieken opened this issue Mar 16, 2018 · 1 comment · Fixed by #46235
Assignees
Labels
perf release-notes Release notes issues verified Verification succeeded
Milestone

Comments

@jrieken
Copy link
Member

jrieken commented Mar 16, 2018

Similar to #45971. There are 500+ calls to isEqualOrParent and given that the explorer model is already a tree-data-model I understand why...

562 ->     at Object.isEqualOrParent (file:///Users/jrieken/Code/vscode/out/vs/base/common/paths.js:298:19)
    at Object.isEqualOrParent (file:///Users/jrieken/Code/vscode/out/vs/base/common/resources.js:14:26)
    at FileStat.find (file:///Users/jrieken/Code/vscode/out/vs/workbench/parts/files/common/explorerModel.js:280:52)
    at Model.findClosest (file:///Users/jrieken/Code/vscode/out/vs/workbench/parts/files/common/explorerModel.js:64:33)
@jrieken
Copy link
Member Author

jrieken commented Mar 19, 2018

/cc @bpasero who came up with this

It seems that FileStat.find is implemented in an expensive way. The FileStat-object seems to keep an array of children and the find-function loops over those, calling isEqualOrParent until it has found a matching child. So, given n-segements of a path with an average of m children the performance is O(nm). That's not good, esp. given that this is called during file-event-avanlanches.

Observations:

  • to know that a file/folder is contained inside another folder you only need to compare paths until the next path separator
  • sorting the children array would allow to use binary search and would bring down the runtime to O(log n)
  • using an index/map that stores FileStat-objects by name (not full path/uri) would bring down the runtime to O(1)

@isidorn isidorn added this to the March 2018 milestone Mar 19, 2018
@bpasero bpasero changed the title Reduce call count of isEqualOrParent Explorer_ Reduce call count of isEqualOrParent Mar 19, 2018
@bpasero bpasero changed the title Explorer_ Reduce call count of isEqualOrParent Explorer: Reduce call count of isEqualOrParent Mar 19, 2018
@isidorn isidorn added the release-notes Release notes issues label Mar 26, 2018
@roblourens roblourens added the verified Verification succeeded label Mar 30, 2018
@vscodebot vscodebot bot locked and limited conversation to collaborators May 6, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
perf release-notes Release notes issues verified Verification succeeded
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants