Bugzilla – Full Text Bug Listing
| Summary: | [Viewers] TreeViewer sort takes an inordinate amount of time | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Product: | [Eclipse Project] Platform | Reporter: | James Blackburn <jamesblackburn+eclipse> | ||||||||||
| Component: | SWT | Assignee: | Bogdan Gheorghe <gheorghe> | ||||||||||
| Status: | CLOSED WONTFIX | QA Contact: | |||||||||||
| Severity: | normal | ||||||||||||
| Priority: | P3 | CC: | bokowski, eclipse.felipe, ericwill, gautier.desaintmartinlacaze, gheorghe, snorthov, yevshif | ||||||||||
| Version: | 3.4 | Keywords: | triaged | ||||||||||
| Target Milestone: | --- | ||||||||||||
| Hardware: | PC | ||||||||||||
| OS: | Linux-GTK | ||||||||||||
| Whiteboard: | stalebug | ||||||||||||
| Bug Depends on: | |||||||||||||
| Bug Blocks: | 519166 | ||||||||||||
| Attachments: |
|
||||||||||||
(In reply to comment #0) > Using: > > TreeViewer#update(): > Sample ViewerSorter#sort (14803 elements) took: 51 > Viewer #update (14803 items) took: 6623 > > TreeViewer#refresh(): > Sample ViewerSorter#sort (14803 elements) took: 51 > Viewer #update (14803 items) took: 6623 These numbers aren't meant to be identical, but they're pretty close... Running it a few times I get pretty consistent results: #refresh: Sample ViewerSorter#sort (14803 elements) took: 61 Viewer update (14803 items) took: 6615 Sample ViewerSorter#sort (14803 elements) took: 51 Viewer update (14803 items) took: 6550 Sample ViewerSorter#sort (14803 elements) took: 51 Viewer update (14803 items) took: 6530 Sample ViewerSorter#sort (14803 elements) took: 51 Viewer update (14803 items) took: 6538 #update: Sample ViewerSorter#sort (14803 elements) took: 52 Viewer update (14803 items) took: 6567 Sample ViewerSorter#sort (14803 elements) took: 51 Viewer update (14803 items) took: 6569 Sample ViewerSorter#sort (14803 elements) took: 50 Viewer update (14803 items) took: 7130 Sample ViewerSorter#sort (14803 elements) took: 52 Viewer update (14803 items) took: 6594 Please provide a full example I can run here. UI Team, is that a known problem ? (In reply to comment #2) > Please provide a full example I can run here. > > UI Team, is that a known problem ? Will do. I've been tracing through the code a bit to see if I can find anything obvious... Nothing so far. I've bumped to jface HEAD, and tried a couple versions of gtk. Will try to put a test together. Created attachment 129303 [details]
Example Test
Attached is an example of how I'm using the API. It's a patch creating a test class in org.eclipse.jface.tests.performance. I've not used the performance testing infrastructure before, so in this example, it's just printing absolute times taken to the console.
The numbers I'm seeing using the simple TreeTest infrastructure appear broadly similar to my app. I've plotted the numbers and the #sort itself scales O(nlgn) whereas the overall #refresh / #update looks to be O(n^2)(?).
Elements Time ms (#Sort) Time ms (#refresh / #update)
5000 111 650
5000 320 2323
15000 4318
20000 593 7365
30000 846 16858
50000 1665 121307
In my app I've got a few more columns, so my overall update / refresh is slower, but my sorter is faster (I'm avoiding string comparisons).
Clearly I've got a lot of elements in the viewer, but the point is once I've built my model the view is pretty static (I don't update the labels or structure); the model is built on a non-UI thread. As the sort itself is quick, I'd like the update of the view to be similarly scalable...
This bug was still assigned to the SWT inbox.
James, have you tried using setRedraw? Something like:
_viewer.getTree().setRedraw(false);
try {
// ... change sorting / filtering etc.
} finally {
_viewer.getTree().setRedraw(true);
}
(In reply to comment #5) > This bug was still assigned to the SWT inbox. > > James, have you tried using setRedraw? Something like: Thank Boris, unfortunately it seems to make little / no difference :( I did some similar timings on my laptop (which runs os x cocoa) which seemed to scale more linearly with the number of items. Which suggests something odd happening in SWT GTK or perhaps GTK itself. Fundamentally it must be broken that, under a pretty beefy machine, it takes 0.5s for each tree view when there are 14k items... (In reply to comment #6) > it takes 0.5s for each tree view _item_ when there are 14k items... Is viewer.setUseHashLookup(true) being called by the superclass? (Sorry if this is a stupid question but I don't have an Eclipse open right now, just looking at the attached code.) (In reply to comment #8) > Is viewer.setUseHashLookup(true) being called by the superclass? (Sorry if this > is a stupid question but I don't have an Eclipse open right now, just looking > at the attached code.) In my app I've tried with an without #setUseHashLookup(true). It doesn't seem to make any difference. I found a page of SWT/GTK+ performance notes: http://vektor.ca/eclipse/gtk-performance-notes.html which states performance for large gtk trees is poor (compared with other widget toolkits). It claims one of the reasons is that rows dont' have fixed height by default and states: "GTK+ version 2.4 introduced a new "fixed-height-mode" property for tree views, but it has some limitations and is not used in their combo box implementation. This property is used if available by the SWT implementation of SWT.VIRTUAL for Trees, and maybe we can use it in more situations." (In reply to comment #6) > I did some similar timings on my laptop (which runs os x cocoa) which seemed to > scale more linearly with the number of items. Which suggests something odd > happening in SWT GTK or perhaps GTK itself. > > Fundamentally it must be broken that, under a pretty beefy machine, it takes > 0.5s for each tree view when there are 14k items... Moving back to SWT. I agree that if this runs well on Cocoa but not on GTK, it must be SWT or GTK itself. BG to investigate. Using the M7 build, I got the JFace Performance tests running on both my Win32 box and my Solaris x86 box (which is my fastest GTK box and slightly faster than the Win32)- but both are Core 2 Duos with 2Gb RAM. I patched the performance suite with James' attached test case and ran just the two test cases. My findings were that the refresh/update tests run in about the same amount of time on both machines (I'll attach the complete trace for both platforms): Win32 ===== Sort (avg.): 953 ms Viewer refresh: 2875 ms Sort (avg.): 954 ms Viewer update: 2864 ms GTK 2.14.3 =========== Sort (avg.): 381 ms Viewer refresh: 2937ms Sort (avg.): 551 ms Viewer update: 3076 ms Created attachment 135177 [details]
Win32 performance test output
Created attachment 135178 [details]
GTK test output
Given the similar test results, I'm not sure we can say that the timings indicate a GTK implementation problem. I'm removing this from the RC1 list, but I'm not sure if this should be returned to JFace or closed. Boris? Created attachment 135208 [details] test 2 (In reply to comment #15) > Given the similar test results, I'm not sure we can say that the timings > indicate a GTK implementation problem. Hmm I'm not sure one data point is enough... Attached is a slightly improved test which runs a few more iterations with increasing numbers of items. Cocoa looks reasonably linear, are you seeing a similar spread on your Windows & Solaris machines? testTreeSortRefresh: setUp... Viewer refresh (1024 items) sort: 111ms refresh total: 489ms Viewer refresh (2048 items) sort: 265ms refresh total: 964ms Viewer refresh (4096 items) sort: 767ms refresh total: 2988ms Viewer refresh (8192 items) sort: 1674ms refresh total: 5509ms Viewer refresh (16384 items) sort: 3423ms refresh total: 10137ms Win32: Viewer refresh (1024 items) sort: 36ms refresh total: 177ms Viewer refresh (2048 items) sort: 78ms refresh total: 349ms Viewer refresh (4096 items) sort: 208ms refresh total: 755ms Viewer refresh (8192 items) sort: 469ms refresh total: 1573ms Viewer refresh (16384 items) sort: 1151ms refresh total: 3557ms Viewer refresh (32768 items) sort: 2250ms refresh total: 6562ms Viewer update (1024 items) sort: 36ms update total: 171ms Viewer update (2048 items) sort: 83ms update total: 359ms Viewer update (4096 items) sort: 192ms update total: 729ms Viewer update (8192 items) sort: 442ms update total: 1588ms Viewer update (16384 items) sort: 1119ms update total: 3447ms Viewer update (32768 items) sort: 2270ms update total: 6838ms GTK: Viewer refresh (1024 items) sort: 27ms refresh total: 166ms Viewer refresh (2048 items) sort: 32ms refresh total: 190ms Viewer refresh (4096 items) sort: 77ms refresh total: 419ms Viewer refresh (8192 items) sort: 178ms refresh total: 1119ms Viewer refresh (16384 items) sort: 412ms refresh total: 3372ms Viewer refresh (32768 items) sort: 886ms refresh total: 11078ms Viewer update (1024 items) sort: 77ms update total: 135ms Viewer update (2048 items) sort: 189ms update total: 320ms Viewer update (4096 items) sort: 110ms update total: 442ms Viewer update (8192 items) sort: 252ms update total: 1183ms Viewer update (16384 items) sort: 607ms update total: 3548ms Viewer update (32768 items) sort: 1304ms update total: 11518ms GTK gets a bit long on the last case, but not too bad otherwise. (In reply to comment #19) > GTK gets a bit long on the last case, but not too bad otherwise. But that's my point. It doesn't scale O(n) like it does Windows & Mac OS. In an app with multiple columns, the actual upper pain threshold is smaller -- 15k items or fewer for us. This wouldn't be the case if the SWT/GTK treeview scaled like it does on windows. Is there a pure SWT snippet for this ticket? 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. |
I'm seeing a sort in a TreeViewer wrapped Tree control take an inordinate amount of time (0.4s per element). In this case the tree viewer contains a flat table of data (I'm using TreeViewer because it sometimes contains nested data). My tree has multiple columns (~10) and I've added a selectionListener to each TreeColumn in the usual way. I've #setSorter on the TreeViewer to use my own custom sorter. When the column is clicked, I #update() or #refresh() the tree viewer for the sort to take place. Inserting some print's I can see that the ViewerSorter#sort(...) takes 57ms to sort ~15000 elements, but the viewer update / refresh takes 6.5s. It doesn't matter whether I do #update or #refresh... Using: TreeViewer#update(): Sample ViewerSorter#sort (14803 elements) took: 51 Viewer #update (14803 items) took: 6623 TreeViewer#refresh(): Sample ViewerSorter#sort (14803 elements) took: 51 Viewer #update (14803 items) took: 6623 The code that produced this looks like this: // Listener for the sorter SelectionListener headerListener = new SelectionAdapter() { public void widgetSelected(SelectionEvent se) { int icol = _viewer.getTree().indexOf((TreeColumn) se.widget); TreeColumn col = _viewer.getTree().getColumns()[icol]; IMetricDisplay md = ...; SampleSorter sorter = (SampleSorter) _viewer.getSorter(); if (md == sorter.getColumn()) sorter.setReversed(!sorter.isReversed()); else sorter.setColumn(md); _viewer.getTree().setSortColumn(col); _viewer.getTree().setSortDirection(sorter.isReversed() ? SWT.DOWN : SWT.UP); long start = System.currentTimeMillis(); // _viewer.update(_viewer.getTree().getData(), new String[] {SampleSorter.SORT_REQUIRED}); _viewer.refresh(false); if (true) System.out.println("Viewer #update ("+ _viewer.getTree().getItemCount() + " items) took: " + (System.currentTimeMillis() - start)); } }; column.addSelectionListener(headerListener); And the sorter has wrapped #sort: public void sort(Viewer viewer, Object[] elements) { long start = System.currentTimeMillis(); super.sort(viewer, elements); if (DEBUG) System.out.println("Sample ViewerSorter#sort ("+ elements.length + " elements) took: " + (System.currentTimeMillis() - start)); } I was under the impression that #update on the JFace TreeViewer would be relatively efficient if the domain objects haven't changed: http://www.eclipse.org/articles/Article-TreeViewer/TreeViewerArticle.htm Nonetheless, having scoured google and the existing example docs (there isn't much on tree viewer sorting), I'm stumped as to why sorting in the viewer takes 0.4s per element... Versions: JFace: org.eclipse.jface_3.4.0.I20080606-1300.jar GTK: 2.12.11