Community
Participate
Working Groups
I will provide patches soon.
Improvement measured with 'org.eclipse.swt.tests.manual.Bug548982_TreeAddRemoveMany': 1) With LOCK_REDRAW (Scenarios without it are simply wrong) CreateTreeItems: 3755ms -> 1954 ms 2) With LOCK_REDRAW + CREATE_REVERSE_ORDER (the best way of inserting items) CreateTreeItems: 2030ms -> 330ms This gives impressive 6x speedup when used properly.
New Gerrit change created: https://git.eclipse.org/r/145918
New Gerrit change created: https://git.eclipse.org/r/145925
Forgot to give measurements for deleting items. Here go combined measurements: Improvement measured with 'org.eclipse.swt.tests.manual.Bug548982_TreeAddRemoveMany': CreateTreeItems --------------- 1) With LOCK_REDRAW (Scenarios without it are simply wrong) 3755ms -> 1954 ms 2) With LOCK_REDRAW + CREATE_REVERSE_ORDER (the best way of inserting items) 2030ms -> 330ms DeleteTreeItems --------------- 1) With LOCK_REDRAW 4580ms -> 3408ms 2) With LOCK_REDRAW + DELETE_AFTER_COLLAPSE (one of better ways to remove items) 2280ms -> 263ms So: 6x improvement for creating items in optimal way 8x improvement for typical better way for deleting items
Sigh, now I mixed up current patch and future patch. Why is there no Edit button for comments here? :) Improvement measured with 'org.eclipse.swt.tests.manual.Bug548982_TreeAddRemoveMany': CreateTreeItems --------------- 1) With LOCK_REDRAW (Scenarios without it are simply wrong) 3755ms -> 1954 ms 2) With LOCK_REDRAW + CREATE_REVERSE_ORDER (the best way of inserting items) 2030ms -> 330ms DeleteTreeItems --------------- 1) With LOCK_REDRAW 4580ms -> 3408ms 2) With LOCK_REDRAW + DELETE_AFTER_COLLAPSE (one of better ways to remove items) 2280ms -> 580ms So: 6x improvement for creating items in optimal way 4x improvement for typical better way for deleting items
Gerrit change https://git.eclipse.org/r/145918 was merged to [master]. Commit: http://git.eclipse.org/c/platform/eclipse.platform.swt.git/commit/?id=c989fbf5032fec9b056dbea3d1977e0d24da2574
Gerrit change https://git.eclipse.org/r/145925 was merged to [master]. Commit: http://git.eclipse.org/c/platform/eclipse.platform.swt.git/commit/?id=753cb9001e2768cac0d8a47e80ec1e886b10741c
First portion of patches are now merged to master. Lars, thanks for review! The other guys are quite lazy :/
Alexandr, is here still something to be done?
Yes, I was going to finish that, but then got distracted and forgot. I was going to implement `TVE_COLLAPSERESET`, see also Bug 565061 Comment 4
(In reply to Alexandr Miloslavskiy from comment #10) > Yes, I was going to finish that, but then got distracted and forgot. > > I was going to implement `TVE_COLLAPSERESET`, see also Bug 565061 Comment 4 Would be great if you still can do that, sounds like a interesting performance improvement.
Yes, I still remember about this. Will do once I get through higher priority issues.
Mass move out to 4.18
(In reply to Alexandr Miloslavskiy from comment #12) > Yes, I still remember about this. Will do once I get through higher priority > issues. Hi Alexandr, any change to get this change for 4.18M1?
This is considered lower priority, but is still on my list. Not sure about any specific date. If the Bug is standing in your way, it's fine if you just close it and I will reopen later.
(In reply to Alexandr Miloslavskiy from comment #15) > This is considered lower priority, but is still on my list. Not sure about > any specific date. If the Bug is standing in your way, it's fine if you just > close it and I will reopen later. Thanks for the response, no need to close this bug. I saw today a tweet about how slow Eclipse is compared to IJ with regards to trees and I had hope that this bug would help is removing that. See https://twitter.com/dashorst/status/1309107620259790849
Yes, this might be something that the patch will improve. Specifically, the patch I have in mind will make removing items faster on Windows. This will help because some Trees remove child items on collapse.
What I would recommend is the old thing often overlooked: just run this scenario under profiler. If it wasn't profiled before, then it's most likely that it would take an obvious and simple fix to make it some 10x faster.
Moving out of 4.18, please re-target as required.
I think to do some more tests and read I need more time to read on subsequent days. Because of this I have to postpone, sorry. For the moment I abandon https://git.eclipse.org/r/c/platform/eclipse.platform.swt/+/175293 . Hope to be able to pickup again soon.
No worries! If you make the patches any soon, that would be a lot faster than it took me :)
Resetting the target for now.
With Bug 562233 in place (it introduced 'ExceptionStash'), we finally have the way to optimize 'TreeItem.deleteAll()'. The approach would be like: 1) Begin 'try (... new ExceptionStash ())' block 2) Release all 'TreeItem' objects, which includes sending 'SWT.Dispose' for each item. If any exceptions are thrown from 'SWT.Dispose', put them into 'ExceptionStash' and continue as if there were no exceptions. 3) Send 'TVE_COLLAPSERESET' to 'TreeItem' on which '.deleteAll()' was called. This is an efficient way of deleting many items at once. 4) End 'try' block, which will cause 'ExceptionStash' to re-throw exceptions from step 2. Previously the major roadblock was that 'SWT.Dispose' could throw, which would bring SWT into one of these inconsistent states: a) If exception aborts 'TreeItem.deleteAll()', then the state will be that some 'TreeItem' objects are already disposed while the native Windows Tree still have the items because 'TVE_COLLAPSERESET' was not sent yet. b) If exception only aborts sending 'SWT.Dispose' and proceeds to 'TVE_COLLAPSERESET', then some 'TreeItem' objects will leak. c) If exceptions are ignored, then the problem is that exception is never delivered to user code. 'ExceptionStash' is specifically designed to solve these kinds of problems. Unfortunately I don't currently have the time to prepare a patch. If anyone volunteers, I could assist.
Some notes on bulk deleting items on Windows: (Note 1) Windows TreeView control internally keeps sibling items in a single linked list. This has a number of consequences: 1) Deleting item that is not the first child requires finding previous item in order to update its 'next' field in the linked list. 2) In single linked list, finding previous item requires to walk all items from the beginning of the list, making the operation cost O(pos), where 'pos' is the index of the child item in the list of child items. 3) As a result, deleting N sibling items from the Tree costs O(N) if first item is deleted repeatedly and O(N*N) if last item is deleted repeatedly. (Note 2) If parent item is NOT collapsed, then Windows TreeView also updates visible indices after deleting each item. This involves walking all siblings after the deleted items and updating an integer field there, so it's O(N-pos), where 'N' is number of items in the list and 'pos' is the index of deleted item. This makes O(N*N) if first item is deleted repeatedly and O(N) if last item is deleted repeatedly. As it can be seen, (Note 1) + (Note 2) means that both orders are bad. Reducing one cost increases the other cost. However, if parent item is collapsed, then (Note 2) is avoided, and deleting first item repeatedly is best. 'TVE_COLLAPSERESET' collapses parent item before deleting children, and then deletes first item repeatedly, that is, it implements the best approach. Unfortunately however, 'TVE_COLLAPSERESET' is ignored for the root item, which makes it impossible to bulk delete top level items quickly. I wasn't able to find a solution that doesn't involve some dirty hacks, such as manipulating private data structures of Windows TreeView. (Note 3) If 'Control.setRedraw(false)' is not in effect, then TreeView also recalculates Tree width whenever an item is deleted that had width equal to maximum width. It creates another O(N*N) problem if many items have width equal to max width. In my debugging, I noticed that 'Control.setRedraw(false)' did not always prevent that. Didn't have the time to investigate further. 'TVS_NOHSCROLL' window style seems to be another way to avoid that cost. Keywords: TVM_DELETEITEM, TVE_COLLAPSERESET, performance, fast
Thanks for the excellent detail summary.
Yes, thanks for writing this down. Could it be useful to add another two ideas?: - switching off the sorting while doing a bulk insert might be faster - a „real“ bulk import can improve performance further - see sample implementation at https://git.eclipse.org/r/c/platform/eclipse.platform.swt/+/175293 However to make use of it you have to change to a new api that alliws to add several items at once
