Project: Eclipse_Platform_UI
Bug 86958 [Viewers] Adding many adjacent children to a TreeViewer is slow
Reported: 2005-03-01 19:44:24 | Status: verified fixed

This is on 3.1M5a, GTK2 build. If you add several thousand children to a Tree, it can take several minutes to complete. A concrete example is browsing a CVS repository containing thousands of directories (e.g. cvs.fedora.redhat.com/cvs/dist). If you browse through that repo, the UI becomes unresponsive for several minutes while the tree is updated. This is unacceptable. Adding N children to a tree node is currently an O(N^2) operation (at least on GTK2; I haven't checked other platforms). This is because, for every child, an O(N) read of all the children on that node, and an O(N) linear search to check for duplicates, is performed. The attached patch reduces the "add N children" cost to O(N log N) - which in practice means that, for my CVS repo test case, the UI only takes a few seconds to update instead of several minutes - but only in the case of sorted trees, by doing two things: 1. AbstractTreeViewer.indexForElement now requests only the children that are actually needed in its binary search, rather than requesting all the children of the current node. 2. This optimisation is only performed for sorted trees: In AbstractTreeViewer.createAddedElement, given that we now know the index where we need to insert the new item, and given the reasonable assumption (which needs to be explicitly required in the Javadoc!) that the sorter is consistent with equals(), we don't have to search through all the children to find possible duplicates. We need only look at the item prior to that index, if the index is positive. If the index is 0, we know it is not a duplicate, because of the algorithm used in indexForElement. No new fields have been added, but some new public methods have been added. Unfortunately, because it straddles the platform-specific interface, if this patch were accepted, it would need to be implemented for every platform, and my patch only implements the GTK2 part of it, because I don't develop on Windows.

Files changed in fix:
bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/AbstractTreeViewer.java bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/TableTreeViewer.java bundles/org.eclipse.jface/src/org/eclipse/jface/viewers/TreeViewer.java