Community
Participate
Working Groups
Adding child tree items to a tree has N^2 complexity with respect to the number of children. This is happening because the TreeItem constructor calls OS.gtk_tree_model_iter_nth_child, which traverses a linked list. Adding N TreeItems has N^2 complexity as a result. The algorithm can be improved by using gtk_tree_model_iter_next instead of gtk_tree_model_iter_nth_child when creating clild TreeItems sequentially.
Created attachment 248426 [details] Stack traces of the UI freeze caused by the inefficient algorithm
Thank you for the analysis. Once we get Eclipse to run a bit more stable on Gtk3 (bug 428852 bug 439884 to name a few) this is definetley something to investigate.
This article recommends implementing your own tree models rather than using GtkTreeStore or GtkListStore if we have a lot of data. http://scentric.net/tutorial/sec-treemodels.html This covers the documentation for the GTK tree model (which is the interface we need to implement to get faster random access). https://developer.gnome.org/gtk3/stable/GtkTreeModel.html This document describes the exact performance problem we're having - namely, that random access is slow (scroll down to "performance considerations"). https://developer.gnome.org/gtk3/stable/GtkListStore.html This tutorial describes how to build a custom model (unfortunately, it applies to GTK 2.0, not GTK 3.0): http://scentric.net/tutorial/sec-custom-models.html
Here's a representative example of a GTK 2.0 custom model: https://github.com/dinhviethoa/linux-sample/blob/master/gtk-ui/etpan-gtk-tree-model.c
(In reply to Stefan Xenos from comment #3) > This article recommends implementing your own tree models rather than using > GtkTreeStore or GtkListStore if we have a lot of data. > ... Interesting. Thanks for sharing.
This is the second-largest cause of UI freezes for Eclipse on GTK. Is there any chance it could get some love for M6?
Let's increase priority on this guy.
Moving to M7.
Note that we've improved our data collection and stats, and we're no longer seeing this as the #2 freeze. Assuming our preliminary stats can be trusted, bug 354842 is very much #1 accounting for 36% of total freeze duration on 4.7 with GTK2. This bug accounts for about 1.5% of total freeze duration.
(In reply to Stefan Xenos from comment #9) > Note that we've improved our data collection and stats, and we're no longer > seeing this as the #2 freeze. Assuming our preliminary stats can be trusted, > bug 354842 is very much #1 accounting for 36% of total freeze duration on > 4.7 with GTK2. This bug accounts for about 1.5% of total freeze duration. Thank you for posting, this is good to know.
Note that the low freeze duration is due to the fact that there are workarounds in all parts of the Eclipse code base that prevent any trees from growing too large. Fixing this bug would let us remove the workarounds... but our data shows that the workarounds are working effectively.
Moving away of 4.7. It's too late for drastic changes in this touchy area.
(In reply to Alexander Kurtakov from comment #12) > Moving away of 4.7. It's too late for drastic changes in this touchy area. Agree. Setting the target milestone to 4.8 so that it stays on the horizon and is not completely lost...
Moving to 4.9, please re-target as required.
The performance issue in combo: 489640 – (gtk3SlowCombobox) [GTK3] setting a lot of items to combobox is extremely slow (on gtk_combo_box_text_insert) https://bugs.eclipse.org/bugs/show_bug.cgi?id=489640 Was caused by the drop-down menu size being re-computed after every insertion/removal of an item. The fix was to dissabled wrapping during insert/removal. I wonder if we have a similar problem here where GtkTree does a re-size after every insert, where a re-size has to traverse the full tree to compute the size.
Just to add a test case: import all projects from eclipse.platform.ui and turn off "Use Limits" in the problems view. If I try to debug an runtime Eclipse, I get a very long freeze, here is a sample for the stack: Stack Trace at org.eclipse.swt.internal.gtk.GTK._gtk_tree_model_get_path(Native Method) at org.eclipse.swt.internal.gtk.GTK.gtk_tree_model_get_path(GTK.java:7224) at org.eclipse.swt.widgets.TreeItem.setExpanded(TreeItem.java:1285) at org.eclipse.jface.viewers.TreeViewer.setExpanded(TreeViewer.java:291) at org.eclipse.jface.viewers.AbstractTreeViewer.updateChildren(AbstractTreeViewer.java:2782) at org.eclipse.jface.viewers.AbstractTreeViewer.internalRefreshStruct(AbstractTreeViewer.java:1947) at org.eclipse.jface.viewers.TreeViewer.internalRefreshStruct(TreeViewer.java:674) at org.eclipse.jface.viewers.AbstractTreeViewer.internalRefreshStruct(AbstractTreeViewer.java:1953) at org.eclipse.jface.viewers.TreeViewer.internalRefreshStruct(TreeViewer.java:674) at org.eclipse.jface.viewers.AbstractTreeViewer.internalRefresh(AbstractTreeViewer.java:1923) at org.eclipse.jface.viewers.AbstractTreeViewer.internalRefresh(AbstractTreeViewer.java:1880) at org.eclipse.jface.viewers.StructuredViewer.lambda$3(StructuredViewer.java:1530) at org.eclipse.jface.viewers.StructuredViewer$$Lambda$355/1522506358.run(Unknown Source) at org.eclipse.jface.viewers.StructuredViewer.preservingSelection(StructuredViewer.java:1446) at org.eclipse.jface.viewers.TreeViewer.preservingSelection(TreeViewer.java:360) at org.eclipse.jface.viewers.StructuredViewer.preservingSelection(StructuredViewer.java:1407) at org.eclipse.jface.viewers.StructuredViewer.refresh(StructuredViewer.java:1530) at org.eclipse.jface.viewers.ColumnViewer.refresh(ColumnViewer.java:535) at org.eclipse.jface.viewers.StructuredViewer.refresh(StructuredViewer.java:1491) at org.eclipse.ui.internal.views.markers.UIUpdateJob.runInUIThread(UIUpdateJob.java:104) at org.eclipse.ui.progress.UIJob.lambda$0(UIJob.java:95) at org.eclipse.ui.progress.UIJob$$Lambda$326/809047088.run(Unknown Source) at org.eclipse.swt.widgets.RunnableLock.run(RunnableLock.java:37) at org.eclipse.swt.widgets.Synchronizer.runAsyncMessages(Synchronizer.java:182) at org.eclipse.swt.widgets.Display.runAsyncMessages(Display.java:4915) at org.eclipse.swt.widgets.Display.readAndDispatch(Display.java:4521) at org.eclipse.e4.ui.internal.workbench.swt.PartRenderingEngine$5.run(PartRenderingEngine.java:1170) at org.eclipse.core.databinding.observable.Realm.runWithDefault(Realm.java:336) at org.eclipse.e4.ui.internal.workbench.swt.PartRenderingEngine.run(PartRenderingEngine.java:1059) at org.eclipse.e4.ui.internal.workbench.E4Workbench.createAndRunUI(E4Workbench.java:153) at org.eclipse.ui.internal.Workbench.lambda$3(Workbench.java:667) at org.eclipse.ui.internal.Workbench$$Lambda$26/142302025.run(Unknown Source) at org.eclipse.core.databinding.observable.Realm.runWithDefault(Realm.java:336) at org.eclipse.ui.internal.Workbench.createAndRunWorkbench(Workbench.java:597) at org.eclipse.ui.PlatformUI.createAndRunWorkbench(PlatformUI.java:148) at org.eclipse.ui.internal.ide.application.IDEApplication.start(IDEApplication.java:152) at org.eclipse.equinox.internal.app.EclipseAppHandle.run(EclipseAppHandle.java:196) at org.eclipse.core.runtime.internal.adaptor.EclipseAppLauncher.runApplication(EclipseAppLauncher.java:134) at org.eclipse.core.runtime.internal.adaptor.EclipseAppLauncher.start(EclipseAppLauncher.java:104) at org.eclipse.core.runtime.adaptor.EclipseStarter.run(EclipseStarter.java:388) at org.eclipse.core.runtime.adaptor.EclipseStarter.run(EclipseStarter.java:243) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:498) at org.eclipse.equinox.launcher.Main.invokeFramework(Main.java:656) at org.eclipse.equinox.launcher.Main.basicRun(Main.java:592) at org.eclipse.equinox.launcher.Main.run(Main.java:1498) at org.eclipse.equinox.launcher.Main.main(Main.java:1471)
Resetting target, please re-target as required.
Is this bug caused by this as well? https://bugs.eclipse.org/bugs/show_bug.cgi?id=540805
(In reply to Anton Krug from comment #18) > Is this bug caused by this as well? > > https://bugs.eclipse.org/bugs/show_bug.cgi?id=540805 No. *This* bug has nothing to do with combos, it deals with trees.
Oh right, sorry for that. Tested my issue on 4.9 and it's sorted so closed mine.
This problem was touched by another bug 519164. I did try to fix this problem through SWT's implementation, by using the gtk_tree_model_iter_next. However, this did not improve performance that much. I believe the problem actually lies in the tree model in gtk, therefore implementing our own tree model may be the only way to fix this in SWT. Currently though createItem has gone through some improvements, eg. faster insertion if done in the front of the list. Therefore I have made the respective changes to JFace to take use of this. See https://bugs.eclipse.org/bugs/show_bug.cgi?id=564552
