Community
Participate
Working Groups
Created attachment 220939 [details] Patch for a proposed fix Noticed when we added a linked folder containing two subdirectories, one with 20,000+ files, the other with 5,000+ files. UI is blocked in folder refresh for several (about 5 to 6) seconds. That may not appear too much, but is already not acceptable for our customers. Analysis turned up that Eclipse calls AbstractDataTreeNode.assembleWith(AbstractDataTreeNode[] oldNodes, AbstractDataTreeNode[] newNodes, boolean keepDeleted) repeatedly for each file, with oldNodes the files already added to the tree, and newNodes containing exactly one file: the next one to be added. That gives an overall performance of O((n+1)*n/2), i.e. quadratic. The attached patch fixes this by not going linearly through oldNodes. Instead, it figures out where the next node from newNodes would need to be inserted, and the bulk copies the "skipped" part of oldNodes, resulting in O(n*log(n)) for this case. Tested this with a linked folder containing two subfolders with 10,000 empty files each. The original algorithm ends up doing about 100,000,000 string comparisons in assembleWith() during the refresh of that linked folder (as expected). The modified algorithm brings this down by a factor of 400 to 250,000 (also as expected). The UI is no longer blocked, refresh of that linked folder runs through smoothly in less than a second. As I see that AbstractDataTreeNode.assembleWith() hasn't changed in master with respect to 3.7, I suspect this applies to all Eclipse versions.
Thank you for the bug report and patch. Your analysis confused me at first because it is still a linear copy operation. However I realize now you're just looking at complexity of string comparisons. I applied the patch. There were no test failures, and I could notice a 3-4 second time improvement with a wall-clock measurement of creating a link to a folder with 10,000 files in it. Released to master: http://git.eclipse.org/c/platform/eclipse.platform.resources.git/commit/?id=3e00d5c7b5f2ea672faf60c276d981015525bf79
Created attachment 221135 [details] Patch against master fixing a minor oversight in a condition There was a minor oversight in my original patch; nothing serious, but it makes it abandon the binary search branch a bit too early. This patch fixes that.
Reopened for consideration of the additional patch.
Pushed to master. Thanks again for your patch. http://git.eclipse.org/c/platform/eclipse.platform.resources.git/commit/?id=1ee7648e5251c89243cc020a6f22e0cf3d1b73cb
Verified in Kepler M2.
