Community
Participate
Working Groups
3.2M5 3224 win32. I have altered Snippet 144 to show both a virtual table and tree. The COUNT variable was reduced from 1 million or it would never complete on the tree. The virtual tree is incredibly slow. Table: 70ms Tree: 6810ms Further, scrolling up and down in the table is smooth. In the tree it is flickering and slow. public class Snippet144 { static final int COUNT = 20000; public static void main(String[] args) { Display display = new Display(); final Shell shell = new Shell(display); shell.setLayout(new RowLayout(SWT.VERTICAL)); final Table table = new Table(shell, SWT.VIRTUAL | SWT.BORDER | SWT.FULL_SELECTION); final Tree tree = new Tree(shell, SWT.VIRTUAL | SWT.BORDER | SWT.FULL_SELECTION); table.addListener(SWT.SetData, new Listener() { public void handleEvent(Event event) { TableItem item = (TableItem) event.item; int index = table.indexOf(item); item.setText("Item " + index); System.out.println("TABLE: " + item.getText()); } }); tree.addListener(SWT.SetData, new Listener() { public void handleEvent(Event event) { TreeItem item = (TreeItem) event.item; int index = tree.indexOf(item); item.setText("Item " + index); System.out.println("TREE: " + item.getText()); } }); table.setLayoutData(new RowData(200, 200)); tree.setLayoutData(new RowData(200, 200)); Button button = new Button(shell, SWT.PUSH); button.setText("Add Items"); final Label label = new Label(shell, SWT.NONE); final Label label2 = new Label(shell, SWT.NONE); button.addListener(SWT.Selection, new Listener() { public void handleEvent(Event event) { long t1 = System.currentTimeMillis(); table.setItemCount(COUNT); long t2 = System.currentTimeMillis(); label.setText("TABLE Items: " + COUNT + ", Time: " + (t2 - t1) + " (ms)"); t1 = System.currentTimeMillis(); tree.setItemCount(COUNT); t2 = System.currentTimeMillis(); label2.setText("TREE Items: " + COUNT + ", Time: " + (t2 - t1) + " (ms)"); shell.layout(); } }); shell.pack(); shell.open(); System.err.println(SWT.getVersion()); while (!shell.isDisposed()) { if (!display.readAndDispatch()) display.sleep(); } display.dispose(); } }
There is a hard limit on Windows around 32767 when adding items to a single level of a tree gets very slow. There's not much I can do about it.
Even with an item count less than 32767 there is quite a big difference. setItemCount: 2500 items: Table: 70ms, Tree: 260ms 5000 items: Table: 70ms, Tree: 639ms 10000 items: Table: 70ms, Tree: 3526ms 20000 items: Table: 70ms, Tree: 11528ms 30000 items: Table: 70ms, Tree: 15014ms 32700 items: Table: 70ms, Tree: 18290ms 40000 items: Table: 70ms, Tree: 27291ms 20000 < 32767
I believe that this is exact problem as BUG #113526. I ran some tests and here is a comparison between Linux (FC4) and windoze: Calling setItemCount on a virtual tree with number of nodes "n" yields: #of nodes Windows Linux (FC4) 10000 8s 0s 20000 29s 3s 30000 63s 7s 40000 103s 16s 50000 251s 27s 100000 - 127s ...because framework spends most of the time in Tree.createItem(...) method allocating space for a tree nodes.
*** Bug 149639 has been marked as a duplicate of this bug. ***
See http://support.microsoft.com/default.aspx?scid=kb;en-us;Q182231 for a description of the problem from the MSDN.
I think there s a more serious issue. Even once the tree is built, adding a single item takes a lot of time (linear in number of elements) because of setItemCount() which takes a time linear to the number of entries to update the item count because of this code : while (hItem != 0 && itemCount < count) { hItem = OS.SendMessage(handle, OS.TVM_GETNEXTITEM, OS.TVGN_NEXT, hItem); itemCount++; it looks like it tries to find the last item of the tree by starting from the root and then scanning the whole tree. Can't we make that more efficient ? (like caching the last item ? ) see BUG 200214
Can you prove that this loop is causing the problem? There is a cache that Tree.findIndex() and Tree.findItem() that could also be used in this case. These methods return the index or the item and keep track of the last index and HTREEITEM. It's a bit tricky because Tree.setItemCount() method needs both the count and the last HTREEITEM in case it needs to delete items instead of adding them but it is doable. The code is quite delecate and I'd like to make sure it makes a difference before changing it.
Yes I confirm the bottleneck is in this loop. I timed with a 75K items tree (under XP), and adding an element through the viewer.add() API takes 150 ms. That s exactly the time it takes to go over this loop (75k iterations): while (hItem != 0 && itemCount < count) { hItem = OS.SendMessage(handle, OS.TVM_GETNEXTITEM, OS.TVGN_NEXT, hItem); itemCount++; } Let me know if there s a patch/fix you want me to test (to leverage the cache you mentionned).
Please attach the benchmark code.
Created attachment 77040 [details] Perf test case for setItemCount() Run the test case, it will create a virtual tree with high number of entries. Then press the 'enter' key in the console to add an element. Put some timing around the Tree.setItemCount() loop code : long start = System.currentTimeMillis(); while (hItem != 0 && itemCount < count) { hItem = OS.SendMessage(handle, OS.TVM_GETNEXTITEM, OS.TVGN_NEXT, hItem); itemCount++; } System.err.println("setItemCount " + (System.currentTimeMillis() - start)); And you will see that this loop takes around 100 ms to complete.
My initial investigation shows that the optimization has no effect for 5000 items. I'm still looking into it to make sure that the caching code is running.
(In reply to comment #11) > My initial investigation shows that the optimization has no effect for 5000 > items. I'm still looking into it to make sure that the caching code is > running. > Depending on how fast your machine is, 5000 may not show much improvement. Try it with at least 50 000. (when I run 5000 items, I get 0 or 16 ms latency, which is probably due to context switching)
Steve, any luck ? Do you have anything i can test ?
*** Bug 207342 has been marked as a duplicate of this bug. ***
I20080207-1530 Steps to reproduce: The following time statistics have been acquired from a Tree loaded with tens of thousands of TreeItems, with a relatively small number of TreeItems parented in a single TreeItem (20 at most), and approximately 2/3 of them being expanded. The resulting times for each method are rounded to 65,000 invocations. The comparison is of the performance of the respective methods of Tree and TreeItem in the cases of Tree without and with the SWT.VIRTUAL flag. The time statistics are averages of 5 runs of each case, the "without" and the "with" runs are run one after the other once, then the cycle is repeated again in order to minimize the effects of the differences in the execution environment. What happens: Windows Mac OS X without with without with Tree.createItem 854 1439 111 123 TreeItem.setBackground 34 51 368 412 TreeItem.setForeground 3 8 4 5 TreeItem.setImage 598 827 19 31 TreeItem.setText 273 472 93 116 Mac OS X seems to be pretty fast in the described scenario and doesn't seem to show a noticeable difference between running without and with the SWT.VIRTUAL flag. However, the SWT Tree on Windows seems to perform noticeably slower in SWT.VIRTUAL mode. What should happen: The understanding is that SWT.VIRTUAL should allow for noticeably better performance on large hierarchies. I've been looking at the mentioned methods and I've been trying to understand the reason for SWT.VIRTUAL being slower and I'm adding this comment because I don't really see that much of a difference in the code of the said methods.
I confirm the bug here. When there are "many" (from 1000 to 10000, that's far less than 2^15-1): (1) In virtual mode (Win32) - The scrollbar SWT Virtual trees under Win32 is barely usable - Selecting items in the node lags seconds behind the actual click - Navigating with the keyboard is nearly impossible (2) Non Virtual mode (Win32) - The scrollbar behaves perfectly fine (very well in fact) - Selecting items in the node still lags seconds behind the actual click - Navigating with the keyboard is still nearly impossible (probably because of the selection) The main difference between (1) and (2) is the time required to open the parent node (obviously way faster with 1). Those problems are inexistent when running GNU/Linux + GTK. Now, from my non-scientific tests, snooping around and trying to get performance out of the tree widget for a few days, my idea is that there are two distinct problems: - the selection problem, under Win32, which has to do with bad random access performances in a node with many children (ie, selecting the nth children quickly) - the scrollbar problem is distinct and only happens in virtual mode, I believe it has to do with the cost of creating the TreeItems while scrolling (maybe Windows doesn't like that in its UI thread, but then again I have no knowledge of Win32). You got my vote for this bug.
(In reply to comment #13) > Steve, any luck ? > Do you have anything i can test ? Hi Irwin, Steve is no longer working here. As much as I can I'll be working on the bugs that are assigned to him. For while loop you refer to in comment 8, I removed the entire loop (my testcase never calls setItemCount to decrease the number of items). I got no performance improvement removing the loop. The time is not there.
Is there any news for that bug, any chance to get it fixed for Helios or very soon thereafter? It is a major blocker for our application.
Created attachment 164096 [details] testcase I don't have a fix for this problem. In win32, Table (ListView) has native support for virtual (see LVS_OWNERDATA and LVM_SETITEMCOUNT) does not. Tree (Tree-View) does not have the same support. Try the attachemnt, see that an unsubclassed TreeView is just as slow as the SWT Tree. All the time is in TVM_INSERTITEM, which we are forced to call.
Hi, unfortunately I met the same problem as you are describing in this forum. In the last comment there is reference to MSDN I am newbie in SWT but I think there is possibility to implement virtual tree with this flag I_CHILDRENCALLBACK. Maybe you can see the following article http://www.codeguru.com/cpp/cpp/cpp_mfc/callbacks/article.php/c16667 Is it possible to use this callback technique in SWT tree? Thanks, Jan
I also find the virtual tree very slow in Linux/GTK not only for Windows. If I increase the item count of Snippet202 to say 20000, it needs about 10 seconds for the window coming up.
I find the virtual tree very slow in SWT3.7 I dynamic change setItemCount, performance has improved. ------------------------------------------------------------------------- package com.swt.example; import org.eclipse.swt.SWT; import org.eclipse.swt.events.TreeAdapter; import org.eclipse.swt.events.TreeEvent; import org.eclipse.swt.layout.FillLayout; import org.eclipse.swt.layout.GridData; import org.eclipse.swt.layout.GridLayout; import org.eclipse.swt.widgets.Composite; import org.eclipse.swt.widgets.Display; import org.eclipse.swt.widgets.Event; import org.eclipse.swt.widgets.Listener; import org.eclipse.swt.widgets.Shell; import org.eclipse.swt.widgets.Tree; import org.eclipse.swt.widgets.TreeItem; /** * @author LuYang * www.suntodo.com */ public class TestTreeVirtual extends Shell { public static int TEST_COUNTS = 100000; /** * Launch the application. * @param args */ public static void main(String args[]) { try { Display display = Display.getDefault(); TestTreeVirtual shell = new TestTreeVirtual(display); shell.open(); shell.layout(); while (!shell.isDisposed()) { if (!display.readAndDispatch()) { display.sleep(); } } } catch (Exception e) { e.printStackTrace(); } } /** * Create the shell. * @param display */ public TestTreeVirtual(Display display) { super(display, SWT.SHELL_TRIM); setLayout(new FillLayout(SWT.HORIZONTAL)); Composite composite = new TreeVirtualDynamicExample(this, SWT.NONE); createContents(); } /** * Create contents of the shell. */ protected void createContents() { setText("SWT Application"); setSize(450, 300); } @Override protected void checkSubclass() { // Disable the check that prevents subclassing of SWT components } } class TreeVirtualDynamicExample extends Composite{ private Tree tree; public static String TREEITEM_LOADING = "TREEITEM_LOADING"; /** * Create the composite. * @param parent * @param style */ public TreeVirtualDynamicExample(Composite parent, int style) { super(parent, style); setLayout(new GridLayout(1, false)); tree = new Tree(this, SWT.BORDER | SWT.VIRTUAL); tree.setLinesVisible(true); tree.setLayoutData(new GridData(SWT.FILL, SWT.FILL, true, true, 1, 1)); // create Virtual Tree String root1 = new String("Root1"); String root2 = new String("Root2"); createTree(tree, new Object[]{root1,root2}); } public void createTree(final Tree tree, final Object[] roots) { class TreeSetDataListener implements Listener { public void handleEvent(Event event) { TreeItem currentItem = (TreeItem)event.item; TreeItem parentItem = currentItem.getParentItem(); final Object child; Object[] currentAndBrother = null; int currentItemIndex;// int currentIndex = 0;// if (parentItem == null) {// root Item currentAndBrother = (Object[]) tree.getData(); currentItemIndex = tree.indexOf(currentItem); currentIndex = currentItemIndex; child = currentAndBrother[currentIndex]; createOwnLoadingItem(currentItem); }else{// not root node Object data = (Object) parentItem.getData(); // loading Item if(data!=null && data.equals(TREEITEM_LOADING)){ currentItem.setText("loading"); child = null; // a Item }else if(data!=null && data instanceof Object[]){ currentAndBrother =(Object[]) data; currentItemIndex = parentItem.indexOf(currentItem); currentIndex = currentItemIndex-1; // check currentIndex if(currentIndex>=0 && currentIndex<currentAndBrother.length) child = currentAndBrother[currentIndex]; else child = null; createOwnLoadingItem(currentItem); }else{ child = null; } } if(child!=null) { currentItem.setText(getText(child)); TreeItem belongLoading = getBelongLoadingItem(currentItem); updateLoadingItem(currentItem, currentIndex-1, currentAndBrother, belongLoading); disposeLoadingItem(currentItem, currentIndex-1, currentAndBrother, belongLoading); if(parentItem!=null && parentItem.getItemCount() <= currentAndBrother.length){ parentItem.setItemCount(parentItem.getItemCount()+1); } } } } class TreeListener extends TreeAdapter { @Override public void treeExpanded(TreeEvent e) { TreeItem currentItem = (TreeItem) e.item; createChildren(currentItem); } } tree.addListener(SWT.SetData, new TreeSetDataListener()); tree.addTreeListener(new TreeListener()); // create virtual Tree createRoots(tree, roots); } public void createRoots(Tree tree, Object[] roots) { tree.setData(roots); tree.setItemCount(roots.length); } public void createChildren(final TreeItem currentItem){ final Object child = currentItem.getData(); Thread thread = new Thread() { public void run() { if (tree.isDisposed()) return; final Object[] children = getChildren(child); Display.getDefault().asyncExec(new Runnable () { //Display.getDefault().syncExec(new Runnable() { public void run() { if(!currentItem.isDisposed()){ //currentItem.clearAll(true); currentItem.setData(children); currentItem.setItemCount(currentItem.getItemCount()+1);// display + } }; }); }; }; thread.start(); } public TreeItem createOwnLoadingItem(TreeItem currentItem) { TreeItem ownLoading=null; if(currentItem.getItemCount()==0){ //currentItem.setItemCount(1); ownLoading = new TreeItem(currentItem, 0); ownLoading.setText("loading..."); } return ownLoading; } public TreeItem getBelongLoadingItem(TreeItem currentItem) { TreeItem loading = null; if(currentItem.getParentItem()!=null){ loading=currentItem.getParentItem().getItems()[0]; if(loading!=null && loading.getData()!=null) { if(loading.getData().equals(TREEITEM_LOADING)) return loading; } } return loading; } public void updateLoadingItem(TreeItem currentItem, int currentIndex, Object[] currentAndBorther, TreeItem belongLoading){ if(belongLoading!=null && !belongLoading.isDisposed()) belongLoading.setText((currentIndex+1)+"/"+currentAndBorther.length); } public void disposeLoadingItem(TreeItem currentItem, int currentIndex, Object[] currentAndBorther, TreeItem belongLoading){ if(belongLoading!=null && !belongLoading.isDisposed() && currentIndex+1==currentAndBorther.length){ belongLoading.dispose(); } } public Object[] getChildren(Object parent){ String[] children = new String[TestTreeVirtual.TEST_COUNTS]; for (int i = 0; i < children.length; i++) { children[i] = "child"+"-"+i; } return children; } public String getText(Object element){ return element.toString(); } @Override protected void checkSubclass() { // Disable the check that prevents subclassing of SWT components } public Tree getTree() { return tree; } }
Unfortunately almost 10 years later I am still seeing this same performance issue in our Eclipse RCP application using Windows 8 and the (somewhat outdated) SWT version 3.7.2. I am using an SWT Tree through the JFace TreeViewer. Populating a non-virtual tree with 4000 root items takes about 1 second which is even longer than the delay caused by our database query! This is rather annoying for a good user experience. This issue can easily be reproduced by copy/pasting Snippet002TreeViewer and adjusting the number of nodes. I thought SWT.VIRTUAL was supposed to address this issue, but similar to what is seen in Comment 15, the tree now takes about 50% longer to create. (I copy/pasted/adjusted Snippet047VirtualLazyTreeViewer). Are there any known ways of improving this? I found a workaround that may be (barely) acceptable for user experience: creating a single "All items" root node and adding the 4000 tree items. This tree can be created in about 10ms instead of 1000ms. Expanding the root node takes around 500ms instead of 1000ms. Perhaps creating artificial categories (A, B, C .. Z) can help even more.
I ran the altered Snippet144. It's interesting that 10 years later on a very high end pc, the virtual table takes about the same time, even more: 7090ms. The table now takes 20ms. Is this some kind of Windows task scheduling policy that has never changed?
(In reply to Henno Vermeulen from comment #24) Correction, the virtual tree takes 7090ms. (Virtual tables are very fast in my experience)
I can confirm that the bottleneck is in the OS.SendMessage call of type TVM_INSERTITEM as mentioned in Comment 19. It's in this line in Tree.createItem: hNewItem = OS.SendMessage(handle, OS.TVM_INSERTITEM, 0, tvInsert); Creating 5000 tree items takes 1103ms of which 1024ms is spent in this line of code.
I investigated this deeper and I'm afraid there's not much there can be done except looking for alternatives, such as: - other technology such as Nebula nattable or use Swing's JTree - reduce the number of children per node by adding extra tree nodes. Even putting all items below a single root node seems to help a bit. - reusing the same Tree instead of destroying and rebuilding it. - when using JFace's TreeViewer and setting different input, perhaps the SWT Tree could internally keep existing tree items around and reuse them for the new input instead of destroying + re-adding them Details: The following line in Tree.createItem is the culprit: hNewItem = OS.SendMessage(handle, OS.TVM_INSERTITEM, 0, tvInsert); The tvInsert structure contains a hInsertAfter handle to the item after which the new item is to be inserted. According to MSDN's documentation on TVINSERTSTRUCT https://msdn.microsoft.com/en-us/library/windows/desktop/bb773452(v=vs.85).aspx "Important: Using TVI_LAST to insert an item into a tree-view node that already contains a large number of items can take a long time, causing the application to stop responding until the insert operation completes." So I tried a few alternatives: TVI_ROOT, the previous handle, the first handle, and TVI_FIRST. Using the first handle or TVI_FIRST takes about 10% less time for 5000 nodes and about 30% for 20000 nodes. It is something but not the performance increase I was hoping for. According to this blog http://www.virtualdub.org/blog/pivot/entry.php?id=184 the Win32 tree view internally stores its nodes as a singly-linked list and adding an item to the end takes linear time according to the number of items. It suggests to add nodes in reverse order. When inserting in the front, the time doesn't drastically decrease so there must still be something else going on why the OS call is so slow.
This bug hasn't had any activity in quite some time. Maybe the problem got resolved, was a duplicate of something else, or became less pressing for some reason - or maybe it's still relevant but just hasn't been looked at yet. As such, we're closing this bug. If you have further information on the current state of the bug, please add it and reopen this bug. The information can be, for example, that the problem still occurs, that you still want the feature, that more information is needed, or that the bug is (for whatever reason) no longer relevant. -- The automated Eclipse Genie.
