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

Comments

Projects
None yet
3 participants
@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

This comment has been minimized.

Copy link
Member

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

@roblourens roblourens added the verified 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.