Project: Eclipse_Platform_UI
Bug 90073 [Viewers] AbstractTreeViewer.add method slow for elements added at end
Reported: 2005-04-02 00:09:44 | Status: verified fixed

When implementing deferred loading for the TreeViewer I stumbled upon serious performance problems in the AbstractTreeViewer.add(Object parentElement, Object[] childElements) method. The amount of time this method takes grows exponentially with the size of the childElements array. After profiling it turns out that the problem is that the method is not optimized for loading multiple elements. It essentially adds each element separately. The main problem is that getItems(Item) method is called several times for each element in the childElements array. This method sends message to native Windows control to get children for a given item. The time it takes for getItems to execute grows exponentially with the each item added. We do not have control over the performance of the native widgets but we can optimize calls to them. I created OptimizedTreeViewer class that overrides the internalAdd method and uses a single call to getItems to load all the children. The difference in performance is huge. To add 5000 items in the original tree is ~10 sec with my implementation it takes less then 1 sec. The optimized class below. Thanks. Dimitry Fayerman /* Copyright 2005 Wyeth. All Rights Reserved. */ package com.wyeth.clinical.rcp.common; import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.Map; import org.eclipse.jface.viewers.TreeViewer; import org.eclipse.jface.viewers.ViewerSorter; import org.eclipse.swt.widgets.Composite; import org.eclipse.swt.widgets.Control; import org.eclipse.swt.widgets.Item; import org.eclipse.swt.widgets.Tree; import org.eclipse.swt.widgets.Widget; /** * The TreeViewer descendant that optimizes loading multiple the child elements * for a tree node (method * <code>add(Object parentElement, Object[] childElements)</code>). * <p> * This method is called in particular by the DeferredContentProvider to load * child elements asynchronosely. In this class the optimized method is 5 times * faster. * * @author Dimitry Fayerman (DF) * @version $Revision: 1.1 $, $Date: 2005/04/01 22:15:02 $ * @lastModifiedBy $Author: dfayerma $ */ public class OptimizedTreeViewer extends TreeViewer { // ========================================================================= // Static Attributes // ========================================================================= // ========================================================================= // Static Methods // ========================================================================= // ========================================================================= // Static Classes // ========================================================================= // ========================================================================= // Attributes // ========================================================================= /** * Indicates if this object should match newly added child elements to the * existing elements and if match found just refresh the existing nodes. * This is needed to make it compitable with current TreeViewer * implementation but comes with the performance overhead. By default this * option is disabled end can be enabled by calling * <code>setSupportMultipleEqualElements()</code> method. */ private boolean supportMultipleEqualElements = false; // ========================================================================= // Constructors // ========================================================================= /** * Creates a tree viewer on a newly-created tree control under the given * parent. The tree control is created using the SWT style bits * <code>MULTI, H_SCROLL, V_SCROLL,</code> and <code>BORDER</code>. The * viewer has no input, no content provider, a default label provider, no * sorter, and no filters. * * @param parent * the parent control */ public OptimizedTreeViewer(Composite parent) { super(parent); } /** * Creates a tree viewer on a newly-created tree control under the given * parent. The tree control is created using the given SWT style bits. The * viewer has no input, no content provider, a default label provider, no * sorter, and no filters. * * @param parent * the parent control * @param style * the SWT style bits used to create the tree. */ public OptimizedTreeViewer(Composite parent, int style) { super(parent, style); } /** * Creates a tree viewer on the given tree control. The viewer has no input, * no content provider, a default label provider, no sorter, and no filters. * * @param tree * the tree control */ public OptimizedTreeViewer(Tree tree) { super(tree); } // ========================================================================= // Methods // ========================================================================= /** * Indicates if this object should match newly added child elements to the * existing elements and if match found just refresh the existing nodes. * This is needed to make it compitable with current TreeViewer * implementation but comes with the performance overhead. By default this * option is disabled end can be enabled by calling * <code>setSupportMultipleEqualElements()</code> method. * * @return <code>true</code> if multiple equal elements are examined in * the add method. */ public boolean isSupportingMultipleEqualElements() { return supportMultipleEqualElements; } /** * Sets flag indicating if this object should match newly added child * elements to the existing elements and if match found just refresh the * existing nodes. This is needed to make it compitable with current * TreeViewer implementation but comes with the performance overhead. By * default this option is disabled end can be enabled by calling * <code>setSupportMultipleEqualElements()</code> method. * * @param value * the new value for the attribute */ public void setSupportMultipleEqualElements(boolean value) { this.supportMultipleEqualElements = value; } /** * Add multiple child elements to a given parent element. This method is * optimized by reducing number of costly calls to getItems(Item) method. In * the original implementation the getItems() is called several times for * each element being added. This implementation perfroms only one call to * getItems(Item) * * * @param widget * the Tree or parent Item to add children to * @param parentElement * the parent domain object * @param childElements * the array of domain objects to add to the parent */ protected void internalAdd( Widget widget, Object parentElement, Object[] childElements) { Control tree = getControl(); if (childElements.length > 0) { Object[] filtered = filter(childElements); Item[] items = getChildren(widget); if (supportMultipleEqualElements) { filtered = refreshMatchingAddedElements(widget, items, filtered); } createAddedElements(widget, items, filtered); } } /** * Refreshes items that correspond to elements in additions array. And * returns array of additions that did not match elements associated with * existing items. * * @param parent * the parent Tree or Item * @param items * the array of existing child items of the parent * @param additions * the array of objects to add. * @return the array that contains unique objects in the addition attribute * that did not match elements associated with Items in the items * array. */ private Object[] refreshMatchingAddedElements( Widget parent, Item[] items, Object[] additions) { // Add additions to the HashMap for faster lookup and to ensure // uniqueness. Map additionsMap = new HashMap(additions.length); for (int i = 0; i < additions.length; i++) { additionsMap.put(additions[i], additions[i]); } additionsMap.remove(parent.getData()); // If any of the new elements match an element associated with existing // items, refresh the item and skip adding the element for (int i = 0; i < items.length; i++) { Object match = additionsMap.remove(items[i].getData()); if (match != null) { // refresh the element in case it has new children refresh(match); } } if (additionsMap.size() == additions.length) { // we did not remove anything, just return the original array return additions; } else { // to preserve the order we have to drive from original array Object[] result = new Object[additionsMap.size()]; for (int i = 0, k = 0; i < additions.length; i++) { if (additionsMap.containsKey(additions[i])) { result[k] = additions[i]; k++; } } return result; } } /** * Create the new elements in the parent widget. * * @param widget * the parent Tree or Item * @param items * the array of existing child items * @param elements * the elements to add. * */ private void createAddedElements( Widget widget, Item[] items, Object[] elements) { final ViewerSorter sorter = getSorter(); // If we have sorter, sort elements to add // This way when calling indexForElement we do not have to worry about // new elements. if (sorter != null) { Arrays.sort(elements, new Comparator() { public int compare(Object o1, Object o2) { return sorter.compare(OptimizedTreeViewer.this, o1, o2); } }); } int position = 0; for (int i = 0; i < elements.length; i++) { Object element = elements[i]; position = indexForElement(items, position, element); createTreeItem(widget, element, position + i); } } /** * Returns the index where the item should be inserted. It uses sorter to * determine the correct position, if sorter is not assigned, returns the * index of the element after the last. * * @param items * the existing items * @param startIndex * the start index to start search for position from this allows * optimising search for multiple elements that are sorted * themself. * @param element * element to find position for. * @return the index to use when inserting the element. * */ protected int indexForElement(Item[] items, int startIndex, Object element) { ViewerSorter sorter = getSorter(); if (sorter == null) { return items.length; } int count = items.length; int min = startIndex, max = count - 1; while (min <= max) { int mid = (min + max) / 2; Object data = items[mid].getData(); int compare = sorter.compare(this, data, element); if (compare == 0) { // find first item > element while (compare == 0) { ++mid; if (mid >= count) { break; } data = items[mid].getData(); compare = sorter.compare(this, data, element); } return mid; } if (compare < 0) min = mid + 1; else max = mid - 1; } return min; } // ========================================================================= // Inner classes // ========================================================================= }

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