Optimising getViewState tree traversal to improve performance on folders with too many children.

Context

We are currently running VSCode in a monorepo folder that has hundreds of thousands of subfolders/files. There are a few performance issues happening due to that and the getViewState has been identified as one of them.

Problem

Whenever a folder was opened, such as branches (88K children), the UI would freeze when opening new folders, changing tabs and also every few seconds. The reason for that was because the onWillSaveWorkspace is called every few secs and whenever VSCode becomes the active tab to save the list of folders that are expanded in storage so the user can refresh the page and still have their expanded folders open.

The issue was that the getViewState() function that returns a list of expanded folders was traversing the tree too slowly.

Solution

In this case, it does not matter by which order we traverse the tree to get all states. Array.shift() has O(n) performance while Array.pop() has O(1), therefore, changing it to pop makes it N times faster.

In the image below you can see that after changing from BFS traversal to DFS, the function improved from an average of 4.5 seconds to 4 milliseconds for the monorepo that contains a folder with a 100K children.

Before:

After: