Bug 548982 - [GTK] Optimize bulk inserting items to Tree

Change-Id: I1b6c19d043cc42ac244926129eef2ba71ef174ad
Signed-off-by: Alexandr Miloslavskiy <alexandr.miloslavskiy@syntevo.com>

6 files changed, 216 insertions, 10 deletions

diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c
index dfab9f7cd9..e0326b8506 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os.c
@@ -11008,6 +11008,16 @@ fail:
 }
 #endif
 
+#ifndef NO__1gtk_1tree_1store_1prepend
+JNIEXPORT void JNICALL GTK_NATIVE(_1gtk_1tree_1store_1prepend)
+	(JNIEnv *env, jclass that, jlong arg0, jlong arg1, jlong arg2)
+{
+	GTK_NATIVE_ENTER(env, that, _1gtk_1tree_1store_1prepend_FUNC);
+	gtk_tree_store_prepend((GtkTreeStore *)arg0, (GtkTreeIter *)arg1, (GtkTreeIter *)arg2);
+	GTK_NATIVE_EXIT(env, that, _1gtk_1tree_1store_1prepend_FUNC);
+}
+#endif
+
 #ifndef NO__1gtk_1tree_1store_1remove
 JNIEXPORT void JNICALL GTK_NATIVE(_1gtk_1tree_1store_1remove)
 	(JNIEnv *env, jclass that, jlong arg0, jlong arg1)
diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c
index 8589c73125..3512668735 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.c
@@ -875,6 +875,7 @@ char * GTK_nativeFunctionNames[] = {
 	"_1gtk_1tree_1store_1clear",
 	"_1gtk_1tree_1store_1insert",
 	"_1gtk_1tree_1store_1newv",
+	"_1gtk_1tree_1store_1prepend",
 	"_1gtk_1tree_1store_1remove",
 	"_1gtk_1tree_1store_1set__JJIII",
 	"_1gtk_1tree_1store_1set__JJIJI",
diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h
index 73994032b7..642bc88848 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/library/os_stats.h
@@ -873,6 +873,7 @@ typedef enum {
 	_1gtk_1tree_1store_1clear_FUNC,
 	_1gtk_1tree_1store_1insert_FUNC,
 	_1gtk_1tree_1store_1newv_FUNC,
+	_1gtk_1tree_1store_1prepend_FUNC,
 	_1gtk_1tree_1store_1remove_FUNC,
 	_1gtk_1tree_1store_1set__JJIII_FUNC,
 	_1gtk_1tree_1store_1set__JJIJI_FUNC,
diff --git a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java
index eae8f49f1e..5b811b8691 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java
+++ b/bundles/org.eclipse.swt/Eclipse SWT PI/gtk/org/eclipse/swt/internal/gtk/GTK.java
@@ -7565,6 +7565,20 @@ public class GTK extends OS {
 	/**
 	 * @param store cast=(GtkTreeStore *)
 	 * @param iter cast=(GtkTreeIter *)
+	 * @param parent cast=(GtkTreeIter *)
+	 */
+	public static final native void _gtk_tree_store_prepend(long store, long iter, long parent);
+	public static final void gtk_tree_store_prepend(long store, long iter, long parent) {
+		lock.lock();
+		try {
+			_gtk_tree_store_prepend(store, iter, parent);
+		} finally {
+			lock.unlock();
+		}
+	}
+	/**
+	 * @param store cast=(GtkTreeStore *)
+	 * @param iter cast=(GtkTreeIter *)
 	 */
 	public static final native void _gtk_tree_store_remove(long store, long iter);
 	public static final void gtk_tree_store_remove(long store, long iter) {
diff --git a/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Tree.java b/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Tree.java
index 0ef25d72fa..77975e12c4 100644
--- a/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Tree.java
+++ b/bundles/org.eclipse.swt/Eclipse SWT/gtk/org/eclipse/swt/widgets/Tree.java
@@ -890,21 +890,42 @@ void createItem (TreeColumn column, int index) {
 	}
 }
 
+/*
+ * NOTE: the fastest way to bulk-insert items is to insert every item
+ * at index 0 (insert in reverse to preserve order).
+ */
 void createItem (TreeItem item, long parentIter, int index) {
-	int count = GTK.gtk_tree_model_iter_n_children (modelHandle, parentIter);
-	if (index == -1) index = count;
-	if (!(0 <= index && index <= count)) error (SWT.ERROR_INVALID_RANGE);
-	item.handle = OS.g_malloc (GTK.GtkTreeIter_sizeof ());
-	if (item.handle == 0) error(SWT.ERROR_NO_HANDLES);
 	/*
-	* Feature in GTK.  It is much faster to append to a tree store
-	* than to insert at the end using gtk_tree_store_insert().
-	*/
-	if (index == count) {
+	 * Try to achieve maximum possible performance in bulk insert scenarios.
+	 * Even a single call to 'gtk_tree_model_iter_n_children' already
+	 * reduces performance 3x, so try to avoid any unneeded API calls.
+	 */
+	if (index == 0) {
+		item.handle = OS.g_malloc (GTK.GtkTreeIter_sizeof ());
+		if (item.handle == 0) error(SWT.ERROR_NO_HANDLES);
+		GTK.gtk_tree_store_prepend (modelHandle, item.handle, parentIter);
+	} else if (index == -1) {
+		item.handle = OS.g_malloc (GTK.GtkTreeIter_sizeof ());
+		if (item.handle == 0) error(SWT.ERROR_NO_HANDLES);
 		GTK.gtk_tree_store_append (modelHandle, item.handle, parentIter);
 	} else {
-		GTK.gtk_tree_store_insert (modelHandle, item.handle, parentIter, index);
+		int count = GTK.gtk_tree_model_iter_n_children (modelHandle, parentIter);
+		if (!(0 <= index && index <= count)) error (SWT.ERROR_INVALID_RANGE);
+
+		item.handle = OS.g_malloc (GTK.GtkTreeIter_sizeof ());
+		if (item.handle == 0) error(SWT.ERROR_NO_HANDLES);
+
+		/*
+		 * Feature in GTK.  It is much faster to append to a tree store
+		 * than to insert at the end using gtk_tree_store_insert().
+		 */
+		if (index == count) {
+			GTK.gtk_tree_store_append (modelHandle, item.handle, parentIter);
+		} else {
+			GTK.gtk_tree_store_insert (modelHandle, item.handle, parentIter, index);
+		}
 	}
+
 	int id = getId (item.handle, false);
 	items [id] = item;
 	modelChanged = true;
diff --git a/tests/org.eclipse.swt.tests/ManualTests/org/eclipse/swt/tests/manual/Bug548982_TreeAddRemoveMany.java b/tests/org.eclipse.swt.tests/ManualTests/org/eclipse/swt/tests/manual/Bug548982_TreeAddRemoveMany.java
new file mode 100644
index 0000000000..16ee502bab
--- /dev/null
+++ b/tests/org.eclipse.swt.tests/ManualTests/org/eclipse/swt/tests/manual/Bug548982_TreeAddRemoveMany.java
@@ -0,0 +1,159 @@
+/*******************************************************************************

+ * Copyright (c) 2019 Syntevo and others.

+ *

+ * This program and the accompanying materials

+ * are made available under the terms of the Eclipse Public License 2.0

+ * which accompanies this distribution, and is available at

+ * https://www.eclipse.org/legal/epl-2.0/

+ *

+ * SPDX-License-Identifier: EPL-2.0

+ *

+ * Contributors:

+ *     Syntevo - initial API and implementation

+ *******************************************************************************/

+package org.eclipse.swt.tests.manual;

+

+import org.eclipse.swt.*;

+import org.eclipse.swt.layout.*;

+import org.eclipse.swt.widgets.*;

+

+public final class Bug548982_TreeAddRemoveMany {

+	// Options

+	// Java only

+	private static boolean 	CREATE_CTOR_2PARAM 		= false;

+	// Native & Java

+	private static boolean 	LOCK_REDRAW 			= false;

+	private static boolean 	CREATE_AFTER_EXPAND 	= false;

+	private static boolean 	CREATE_REVERSE_ORDER	= false;

+	private static boolean 	DELETE_PARENT_ITEM 		= false;

+	private static boolean 	DELETE_AFTER_COLLAPSE 	= false;

+	private static int 		NUM_ITEMS 				= 20000;

+

+	private static Tree 	tree;

+	private static TreeItem rootItem;

+	private static int 		iteration = 0;

+

+	private static void CreateRootItem() {

+		rootItem = new TreeItem(tree, SWT.NONE, 0);

+		rootItem.setText("Root");

+

+		CreateExpanderSubItem();

+	}

+

+	private static void CreateExpanderSubItem() {

+		new TreeItem(rootItem, SWT.NONE);

+	}

+

+	private static void CreateTreeItems() {

+		iteration++;

+

+		final long start = System.currentTimeMillis();

+

+		if (LOCK_REDRAW) {

+			tree.setRedraw(false);

+		}

+

+		// Delete artificial item from 'CreateExpanderSubItem'

+		rootItem.removeAll();

+

+		if (CREATE_REVERSE_ORDER) {

+			for (int i = NUM_ITEMS - 1; i >= 0; i--) {

+				TreeItem child = new TreeItem(rootItem, SWT.NONE, 0);

+				child.setText("Item:" + iteration + ":" + i);

+			}

+		} else {

+			for (int i = 0; i < NUM_ITEMS; i++) {

+				TreeItem child;

+

+				if (CREATE_CTOR_2PARAM)

+					child = new TreeItem(rootItem, SWT.NONE);

+				else

+					child = new TreeItem(rootItem, SWT.NONE, i);

+

+				child.setText("Item:" + iteration + ":" + i);

+			}

+		}

+

+		if (LOCK_REDRAW) {

+			tree.setRedraw(true);

+		}

+

+		final long end = System.currentTimeMillis();

+		System.out.println("CreateTreeItems: " + (end - start) + " ms");

+	}

+

+	private static void DeleteTreeItems() {

+		final long start = System.currentTimeMillis();

+

+		if (LOCK_REDRAW) {

+			tree.setRedraw(false);

+		}

+

+		if (DELETE_PARENT_ITEM) {

+			rootItem.dispose();

+			CreateRootItem();

+		} else {

+			rootItem.removeAll();

+			CreateExpanderSubItem();

+		}

+

+		if (LOCK_REDRAW) {

+			tree.setRedraw(true);

+		}

+

+		final long end = System.currentTimeMillis();

+		System.out.println("DeleteTreeItems: " + (end - start) + " ms");

+	}

+

+	public static void main(String[] args) {

+		final Display display = new Display();

+		final Shell shell = new Shell(display);

+		shell.setLayout(new GridLayout());

+		shell.setSize(800, 600);

+

+		Label lblHint = new Label(shell, 0);

+		lblHint.setText("Expand/collapse tree item. Timings will be printed to console. Various options are available in code near // Options.");

+

+		tree = new Tree(shell, SWT.BORDER | SWT.VIRTUAL);

+		tree.setLayoutData(new GridData(GridData.FILL_HORIZONTAL | GridData.FILL_VERTICAL));

+		final TreeColumn col = new TreeColumn(tree, SWT.NONE);

+		col.setText("Column 1");

+		col.setWidth(400);

+

+		tree.addListener(SWT.Collapse, event -> {

+			if (!DELETE_AFTER_COLLAPSE) {

+				DeleteTreeItems();

+			} else {

+				display.asyncExec(new Runnable() {

+					@Override

+					public void run() {

+						DeleteTreeItems();

+					}

+				});

+			}

+		});

+

+		tree.addListener(SWT.Expand, event -> {

+			if (!CREATE_AFTER_EXPAND) {

+				CreateTreeItems();

+			} else {

+				display.asyncExec(new Runnable() {

+					@Override

+					public void run() {

+						CreateTreeItems();

+					}

+				});

+			}

+		});

+

+		CreateRootItem();

+

+		shell.open();

+		while (!shell.isDisposed()) {

+			if (!display.readAndDispatch()) {

+				display.sleep();

+			}

+		}

+		display.dispose();

+	}

+}
\ No newline at end of file