Description Jörg Kubitz 2021-08-04 10:00:59 EDT

Example use case: edit or create an Eclipse Launch Configuration of type "Eclipse Application" and in the "Plug-ins" tab set "Launch with"="plug-ins selected below only". Then type "org.eclipse" (just something) in the filter field. You will notice that after every character typed the TreeView below will update. That takes ~ 1sec with the 560 plugins of an eclipse workspace. 
My problem is that i have a lot more plugins in my workspace. It takes sometimes ~ 10sec to update the tree.

Most time is consumed by the following stacktrace:

Tree.getItems(long) line: 3336	
TreeItem.getItems() line: 767	
CachedCheckboxTreeViewer(TreeViewer).getChildren(Widget) line: 160	
CachedCheckboxTreeViewer(AbstractTreeViewer).createChildren(Widget, boolean) line: 798	
CachedCheckboxTreeViewer(TreeViewer).createChildren(Widget, boolean) line: 604	
CachedCheckboxTreeViewer(AbstractTreeViewer).createChildren(Widget) line: 777	
CachedCheckboxTreeViewer(AbstractTreeViewer).internalExpand(Object, boolean) line: 1688	
CachedCheckboxTreeViewer(CheckboxTreeViewer).setCheckedElements(Object[]) line: 470	
CachedCheckboxTreeViewer(ContainerCheckedTreeViewer).setCheckedElements(Object[]) line: 212	
CachedCheckboxTreeViewer.restoreLeafCheckState() line: 98	

The problem seems to be that setCheckedElements() contains a loop over all (selected) elements. And the resulting getItems() contains also a loop over all TreeItems. That gives an O(n^2) time for n selected items.

As far as i see
org.eclipse.jface.viewers.AbstractTreeViewer.createChildren(Widget, boolean) calls getChildren(widget) to optain ALL children. But in most cases it consumes only the first children ("// children already there!). We could just check for Tree.getItemCount()>0 instead of optaining the actual items. Then the O(n^2) could disappear.

----

The same O(n^2) problem occurs for this stacktrace:

CachedCheckboxTreeViewer(AbstractTreeViewer).internalFindChild(Widget, Object) line: 1838	
CachedCheckboxTreeViewer(AbstractTreeViewer).internalExpand(Object, boolean) line: 1690	
CachedCheckboxTreeViewer(CheckboxTreeViewer).setCheckedElements(Object[]) line: 470	
CachedCheckboxTreeViewer(ContainerCheckedTreeViewer).setCheckedElements(Object[]) line: 212	
CachedCheckboxTreeViewer.restoreLeafCheckState() line: 98	


There in org.eclipse.jface.viewers.AbstractTreeViewer.internalExpand(Object, boolean)
expand==false and the return value "w" is not used => we do not need to call internalFindChild at all.

---
Note that such optimization would also improve more common usages of the TreeView  (as the Package Explorer for example).


I do not plan to submit a patch to SWT myself.