Lazy TreeViewer reveal is quadratic on Linux

[basilevs]

Moved from Bug 516281
On large lazy tree models, TreeViewer.setSelection() and TreeViewer.reveal() are very slow.

Test steps

• Import attached Eclipse project in a PDE

• Add native SWT fragment to included launch configuration TreeViewerPerformanceTest.

• Alternatively create your own launch configuration to start TreeViewerPerformanceTest Junit plug-in test.

• Run the configuration/test

Expected

For virtual trees, the time to render should not depend on the model size.

Actual

On MacOS and Windows the time taken is at most linear, on Linux, reveal is very slow (quadratic).

MacOS

52 ms to process 10000 items
458 ms to process 100000 items
The time to select scales as O(n^0.94) as the size of the model grows from 10000 to 100000
36 ms to process 10000 items
384 ms to process 100000 items
The time to reveal scales as O(n^1.02) as the size of the model grows from 10000 to 100000

Windows

9 ms to process 10000 items
12 ms to process 100000 items
The time to select scales as O(n^0.16) as the size of the model grows from 10000 to 100000
6145 ms to process 10000 items
59166 ms to process 100000 items
The time to reveal scales as O(n^0.98) as the size of the model grows from 10000 to 100000

Linux

5 ms to process 10000 items
34 ms to process 100000 items
The time to select scales as O(n^0.83) as the size of the model grows from 10000 to 100000
3888 ms to process 10000 items
396560 ms to process 100000 items
The time to reveal scales as O(n^2.01) as the size of the model grows from 10000 to 100000

Example of a hot stacktrace:

"main" #1 prio=5 os_prio=0 cpu=73458.71ms elapsed=85.50s tid=0x00007fa6c4026000 nid=0x1b6ab3 runnable  [0x00007fa6c9e34000]
   java.lang.Thread.State: RUNNABLE
	at org.eclipse.swt.internal.gtk.GTK.gtk_tree_store_set(Native Method)
	at org.eclipse.swt.widgets.Tree.getId(Tree.java:254)
	at org.eclipse.swt.widgets.Tree._getItem(Tree.java:203)
	at org.eclipse.swt.widgets.Tree.getItems(Tree.java:1932)
	at org.eclipse.swt.widgets.TreeItem.getItems(TreeItem.java:821)
	at org.eclipse.jface.viewers.TreeViewer.getChildren(TreeViewer.java:160)
	at org.eclipse.jface.viewers.TreeViewer.createChildren(TreeViewer.java:597)
	at org.eclipse.jface.viewers.AbstractTreeViewer.createChildren(AbstractTreeViewer.java:790)
	at org.eclipse.jface.viewers.AbstractTreeViewer.internalExpand(AbstractTreeViewer.java:1701)
	at org.eclipse.jface.viewers.AbstractTreeViewer.reveal(AbstractTreeViewer.java:2333)
	at com.spirent.bug516281.TreeViewerPerformanceTest$$Lambda$143/0x0000000100219688.accept(Unknown Source)
	at com.spirent.bug516281.TreeViewerPerformanceTest.timeToRevealLast(TreeViewerPerformanceTest.java:112)
	at com.spirent.bug516281.TreeViewerPerformanceTest.lambda$4(TreeViewerPerformanceTest.java:58)
	at com.spirent.bug516281.TreeViewerPerformanceTest$$Lambda$142/0x0000000100219460.apply(Unknown Source)
	at com.spirent.bug516281.TreeViewerPerformanceTest.assertSlowGrowth(TreeViewerPerformanceTest.java:83)
	at com.spirent.bug516281.TreeViewerPerformanceTest.siblingRevealScaling(TreeViewerPerformanceTest.java:60)

Sampling profiler results:

[iloveeclipse]

@basilevs : did you intentionally created this in platform.ui tracker and not in SWT, or should it be moved to SWT?

[basilevs]

@iloveeclipse JFace TreeViewer forces eager creation of all sibling TreeItems for the one being revealed (see TreeViewer.createChildren()), so it is responsible for linear complexity. SWT seems to contribute another nested linear complexity.
I'm not sure that SWT is fixable, but maybe we could attack from JFace side?

[iloveeclipse]

@basilevs : I have no idea here, haven't looked into code. Feel free to attack from whichever side you like :-)
But may be it makes more sense to look in GTK/SWT implementation first, because it is the one that doesn't exist on other platforms?

[basilevs]

I suspect (have not checked) SWT/GTK complexity comes from native code, which is harder to deal with.
Also, all platforms suffer from linear complexity, so fixing cross-platform code will benefit more users.

[basilevs]

Related demonstration #975

[basilevs]

GTK returns children count in O(N):

static gint
gtk_tree_store_iter_n_children (GtkTreeModel *tree_model,
				GtkTreeIter  *iter)
{
  GNode *node;
  gint i = 0;

  g_return_val_if_fail (iter == NULL || iter->user_data != NULL, 0);

  if (iter == NULL)
    node = G_NODE (GTK_TREE_STORE (tree_model)->priv->root)->children;
  else
    node = G_NODE (iter->user_data)->children;

  while (node)
    {
      i++;
      node = node->next;
    }

  return i;
}

[basilevs]

org.eclipse.jface.viewers.AbstractTreeViewer.internalExpand(Object, boolean) initializes all children to find an index of a given element in its parent item. ILazyTreeContentProvider is requested to populate all children with data, because there is no other API to find which child corresponds to which element.