TreeItem.getItemCount() and TreeItem.getItem(int) have linear complexity on Linux

[basilevs]

The org.eclipse.swt.widgets.Tree is slow on Linux. In particular TreeItem.getItemCount() and TreeItem.getItem(int) have linear complexity (the time of execution is proportional to the number of children).

To Reproduce

Run JUnit test or following snippet:

import org.eclipse.swt.SWT;
import org.eclipse.swt.layout.FillLayout;
import org.eclipse.swt.widgets.Shell;
import org.eclipse.swt.widgets.Tree;
import org.eclipse.swt.widgets.TreeItem;

public class TreeTest {

	private Shell shell = new Shell();
	{
		shell.setLayout(new FillLayout());
		shell.open();
	}


	public void getItemShouldHaveConstantTime() {
		for (int i = 0; i < 1000; i++) {
			measureGetItemTime(100); // warmup
		}
		double elapsed_10 = measureGetItemTime(10);
		double elapsed_100000 = measureGetItemTime(100000);
		double ratio = elapsed_100000 / elapsed_10;

		System.out.printf("Time for 10 elements: %f ns\nTime for 100000 elements: %f ns\nRatio: %f\n",elapsed_10, elapsed_100000, ratio);
	}

	private long measureGetItemTime(int count) {
		Tree tree = createTree();
		try {
			TreeItem subject = new TreeItem(tree, SWT.NONE);

			createChildren(subject, count);
			readAndDispatch();

			// warmup
			for (int i = 0; i < 1000; i++) {
				System.nanoTime();
				subject.getItem(count - 1);
			}

			long start = System.nanoTime();
			for (int i = 0; i < 10000; i++) {
				subject.getItem(count - 1);
			}
			long stop = System.nanoTime();
			long elapsed = stop-start;
			return elapsed;
		} finally {
			tree.dispose();
		}
	}

	private void createChildren(TreeItem subject, int count) {
		for (int i = 0; i < count; i++) {
			new TreeItem(subject, SWT.NONE);
		}
	}

	private Tree createTree() {
		Tree result = new Tree(shell, SWT.NONE);
		return result;
	}

	private void readAndDispatch() {
		for (int i = 0; i < 10; i++ ) {
			while(shell.getDisplay().readAndDispatch()) {}
		}
	}


}

This test wrapped in a product:
testporduct.zip (sources)
slowGetItem.linux.gtk.x86_64.zip slowGetItem.linux.gtk.aarch64.zip (built product)

Expected behavior
Access time should not depend on the number of items.

Environment:

1. Select the platform(s) on which the behavior is seen:

• • All OS
• • Windows
• • Linux
• • macOS

2. Any GTK
3. Any JRE

Version since
Was there always?

Workaround (or) Additional context
Initially reported in eclipse-platform/eclipse.platform.ui#649 Jface algorithms make navigation time proportional to a square of child count due to this problem.

Workaround: eclipse-platform/eclipse.platform.ui#810

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]

I have not found a way to make TreeItem.getItemCount() without using this GTK API, but I have an idea of caching child count to help with JFace scenario, where child count does not change, but each child is accessed in sequence. Unfortunately, cache invalidation seems to quite complex with this approach.

[laeubi]

Just wondering, why do we need to query gtk at all? should not SWT/JFace be the one creating items and keep track of the count?

[SyntevoAlex]

Indeed GTK gtk_tree_store_iter_n_children() iterates a list of items to count children:
https://github.com/GNOME/gtk/blob/3.24.38/gtk/gtktreestore.c#L766-L771

Note that on Windows, SWT caches number of items:

eclipse.platform.swt/bundles/org.eclipse.swt/Eclipse SWT/win32/org/eclipse/swt/widgets/Tree.java

Lines 3340 to 3348 in eafdfbd

	if (hItem == cachedFirstItem) {
	if (cachedItemCount != -1) return cachedItemCount;
	hFirstItem = cachedIndexItem;
	count = cachedIndex;
	}
	while (hFirstItem != 0) {
	hFirstItem = OS.SendMessage (handle, OS.TVM_GETNEXTITEM, OS.TVGN_NEXT, hFirstItem);
	count++;
	}

[basilevs]

Naive caching helps with childCount(), but getChilld(int) is ~ (3N), and when the fix is applied it stays O(N). See my PR comment.

[laeubi]

@basilevs what I mean is that SWT itself is creating native items, so how could it be it does not knows (or could know) the number of items or the n-th item... so if the native implementation is to slow we probably should store an array of items on the java side that allows fast retrieval of childCount() and getChilld(int)

[laeubi]

We don't need a whole copy of the model:

1. Virtual only shows portions of the model that are visible
2. One only needs to store the pointers to the natives to get a fast count/getX by not iterate the whole model

[basilevs]

@laeubi as there no way to detect visible object going out of scope, it is impossible to clean the cache, which means we would store all the objects that had ever been shown indefinetly, which is not much better than whole model (indeed in context of Jface, this cache would have ALL items ever returned by content provider).
2. Storing pointers is effectively same as storing references to Java objects, given GTK implementation stores a cache of all(?) Java objects and has a way to transform pointers to references. In other words, given reference size, there is no benefit to store pointers instead of references - either way a cache of all items ever shown will form a copy of a model. (To clarify, I do not talk about model from JFace, I'm talking about model that native code holds, maybe I should use the term viewmodel).

[basilevs]

We can avoid cache cleanup problem by only holding children of one item of interest, and repopulating it when interest shifts (Windows implementation does it for its caches).

[basilevs]

@laeubi I've implemented the cache and fixed the quadratic complexity of traversal, but the solution (in #883) stinks (is very slow on depth-first traversals). I'm still thinking about either making TreeItem volatile or implementing your suggestion of full model mirror. Both are disruptive.

[basilevs]

I was wrong - efemeral Java TreeItems were never an option - strong references to them are held on all platforms.
The difference is : MacOS uses those strong references to keep track of parent-child relationship, while Linux and Windows create a convoluted system of identifiers to keep track of parents and children.

[laeubi]

@basilevs as slow Tree performance is a major concern I think it would be great to improve it even if it might be disruptive, if you can prepare things we can merge as soon as master is open and have a full cycle to test so don't worry as long as all tests pass 👍

[basilevs]

I went with my dumb caching approach and it works for the scenario I'm interested in. It fails to actually make children tracking sensible, in particular, depth-first traversal is slow.

I suggest not to close this issue until someone volunteers to rework SWT GTK to actually make getItem() constant time.

[iloveeclipse]

@SyntevoAlex : any chance you could look at #883 & remark there regarding the "complete" solution?

[SyntevoAlex]

I could have a look on wednesday, if I don't forget.

[basilevs]

The PR #883 is a failure. I've tested it on original testcase from eclipse-platform/eclipse.platform.ui#649 and the polynomial growth is 1.8 (approximation from three points) which for practical purposes is not different from the original 2.0. I give up for now. Sorry for all the noise!

[basilevs]

An example of ID use case:

org.eclipse.swt.widgets.Tree.getFocusItem() {
	long [] path = new long [1];
	GTK.gtk_tree_view_get_cursor (handle, path, null);
	if (path [0] == 0) return null;
	TreeItem item = null;
	long iter = OS.g_malloc (GTK.GtkTreeIter_sizeof ());
	if (GTK.gtk_tree_model_get_iter (modelHandle, iter, path [0])) {
		int [] index = new int [1];
		GTK.gtk_tree_model_get (modelHandle, iter, ID_COLUMN, index, -1);
		if (index [0] != -1) item = items [index [0]]; //TODO should we be creating this item when index is -1?
	}
	OS.g_free (iter);
	GTK.gtk_tree_path_free (path [0]);
	return item;
}

Here GTK returns an iterator and we need a TreeItem it corresponds to. As iterator is not a key, Tree has to use additional user data stored natively.
Same goes for event handler like org.eclipse.swt.widgets.Tree.cellDataProc(long, long, long, long, long) where items are addressed with iterators.

[basilevs]

Current status: #918 is ready for review.