SWT Tree construction performance

From: Florian Buchholz (idontlikespam_at_florianatpurduedotedu.org)
Date: 10/24/04 

Date: Sun, 24 Oct 2004 04:58:07 GMT

Hi,

I am working on a Java project where we need to display large amounts of
hierachichal data in a Tree view. So far, we have been using the Swing
libraries but I am pondering a switch to JFace/SWT for various reasons.
So I started testing around with SWT and came across the following
problem: it seems that adding a TreeItem to a Tree takes O(n) time where
n is the number of items already contained in the tree. Under Swing
using a custom TreeModel it only takes O(log n) and the log n actually
comes from my underlying data structure (a binary search tree). The poor
performance of SWT strikes me as very odd, especially because all that
happens is that a TreeItem is appended at the end of the Tree.

Included below is the JFace application I used to test the performance
under Eclipse and the output when I run it on my (slow) laptop. I am
using Eclipse 3.0.1 under Linux-gtk. My questions are

1) am I doing anything wrong that causes performance to be so bad? I had
also tried the JFace content provider with similar results.

2) is this an SWT issue or could it be gtk?

3) is this a bug? I don't know for what amount of data Trees where
created for, but we need it to handle several hundred thousands of items
and 90 minutes for 128l items is unacceptable (Swing does it for me in
20 seconds).

Thanks for any help,

Florian

The class below creates SWT Trees from sizes 128 through 131072,
doubling the number of items in each iteration. I get the following output:

Creating tree with 128 nodes: 131 ms
Creating tree with 256 nodes: 51 ms
Creating tree with 512 nodes: 107 ms
Creating tree with 1024 nodes: 229 ms
Creating tree with 2048 nodes: 409 ms
Creating tree with 4096 nodes: 1245 ms
Creating tree with 8192 nodes: 6303 ms
Creating tree with 16384 nodes: 54340 ms
Creating tree with 32768 nodes: 307698 ms
Creating tree with 65536 nodes: 1322601 ms
Creating tree with 131072 nodes: 5166384 ms

after we get out of the "small" number regions every time the number of
items is doubled, the time it takes to create the tree at least
quadruples. There is an increase of a factor of about 9 going from 8k to
16k, which I also cannot explain.

import java.util.Date;

import org.eclipse.jface.window.ApplicationWindow;
import org.eclipse.swt.SWT;
import org.eclipse.swt.widgets.Composite;
import org.eclipse.swt.widgets.Control;
import org.eclipse.swt.widgets.Display;
import org.eclipse.swt.widgets.Tree;
import org.eclipse.swt.widgets.TreeItem;

public class TreePerformer extends ApplicationWindow{

         public TreePerformer() {
                 super(null);
         }

         private Tree createTree(Composite parent, long num_items) {

                 Date before = new Date();

                 Tree tr = new Tree(parent, SWT.MULTI);
                 TreeItem root = new TreeItem(tr, SWT.NULL);
                 root.setText("Tree Root");

                 for (long i = 0; i < num_items; i++) {
                         TreeItem item = new TreeItem(root, SWT.NULL);
                         item.setText("Item " + i);
                 }

                 Date after = new Date();

                 System.out.println("Creating tree with " + num_items
                                 + " nodes: "
                                 + (after.getTime()-before.getTime())
                                 + " ms");
                 return tr;
         }

         protected Control createContents(Composite parent) {

                 Tree tr = null;

                 for (long i = 128; i <= 100000; i = i * 2) {
                         if (tr != null)
                                 tr.dispose();
                         tr = createTree(parent, i);
                 }
                 return tr;
         }

         public static void main(String[] args) {
             TreePerformer tp = new TreePerformer();
             tp.setBlockOnOpen(true);
             tp.open();
             Display.getCurrent().dispose();
         }
}