Bug 314784

Description Christian Kadner 2010-05-27 18:08:35 EDT

Build Identifier: I3424I20100312

Performance bottleneck in TreeEditPart(AbstractEditPart).refreshChildren() when iterating over EContentsEList. The TreeEditPart is used in the diagram Outline view which is refreshed after resource change events. For each refresh there is an iteration over the list of all model children. One iteration of the model children has the runtime complexity of O(n*n) -- it should be O(n). 

Scenario: 1060 model elements, 416 resource changes, we found:
 - AbstractEditPart.refreshChildren():     416 invocations
 - AbstractSequentialList.get(int):    440,798 invocations
 - EContentsEList.listIterator(int):   440,798 invocations
 - EContentsEList$FeatureIteratorImpl.next(): 233,329,579 invocations

The problem is that during that iteration, the list elements are accessed by
index position ( List.get(int pos) ):

AbstractEditPart(TreeEditPart).refreshChildren():
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    protected void refreshChildren() {
        ...
        List modelObjects = getModelChildren();
        for (i = 0; i < modelObjects.size(); i++) {
            model = modelObjects .get(i);
            ...
        }
        ...
    }

Each access by index position causes a new ListIterator to be created: 

AbstractSequentialList.get(int):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    public E get(int location) {
        try {
            return listIterator(location).next();
        } ...
    }

In the underlying EContentsEList that new ListIterator is advanced (by
iterator.next()) to the requested index position:

EContentsEList.listIterator(int):
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    public ListIterator<E> listIterator(int index)
    {
        ...
        ListIterator<E> result = newListIterator();
        for (int i = 0; i < index; ++i)
        {
          result.next();
        }
        return result;
    }

That happens for EACH element in the list of model children of the Outline
view's TreeEditPart, resulting in a runtime complexity of O(n*n).


PART OF THE PROBLEM:

Today TreeContainerEditPart.getModelChildren() returns the underlying list as
it is:

    protected List getModelChildren() {
        if (getModel() instanceof View)
            return ((View) getModel()).getChildren(); //ViewImpl.getChildren()
        return Collections.EMPTY_LIST;
    }

ViewImpl.getChildren() returns a new EContentsEList:

    public EList getChildren() {
        return new EContentsEList(this, childrenFeatures);
    }

In contrast, GraphicalEditPart.getModelChildren() wraps the underlying list a
new ArrayList:

    protected List getModelChildren() {
        ...
        return new ArrayList(((View)model).getVisibleChildren());
    }


SUGGESTED RESOLUTION:

Either or both of the following:

1. Modify all the loops in AbstractEditPart.refreshChildren() to use
iterator.next() instead of List.get(i)

2. Wrap the EContentsEList in a new ArrayList in
TreeContainerEditPart.getModelChildren() -- as it is done in
GraphicalEditPart.getModelChildren()


WE WOULD NEED THE FIX DELIVERED IN IES 3.4.2

THANK YOU!

Reproducible: Always

Steps to Reproduce:
1. Open a GMF diagram with ~1000 node elements
2. Trigger a command that produces multiple resource change events
3. see the UI be unresponsive