Bug 531722 - Performance issue in EdgeLayoutUpdaterModelChangeTrigger
Summary: Performance issue in EdgeLayoutUpdaterModelChangeTrigger
Status: CLOSED FIXED
Alias: None
Product: Sirius
Classification: Modeling
Component: Diagram (show other bugs)
Version: 5.0.0   Edit
Hardware: All All
: P3 major (vote)
Target Milestone: 6.0.0   Edit
Assignee: Laurent Fasani CLA
QA Contact: Florian Barbin CLA
URL:
Whiteboard:
Keywords: performance, triaged
Depends on:
Blocks:
 
Reported: 2018-02-27 03:57 EST by Pierre-Charles David CLA
Modified: 2018-06-27 11:54 EDT (History)
2 users (show)

See Also:

Attachments
Sample project to reproduce the issue (434.38 KB, application/zip)
2018-02-27 03:57 EST, Pierre-Charles David CLA 		no flags Details
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Pierre-Charles David CLA 2018-02-27 03:57:51 EST 
Created attachment 272898 [details]
Sample project to reproduce the issue

Steps to reproduce:
1. Import the attached project.
2. Open the session.
3. Create a new diagram on the root EPackage. This is fast, the diagram is initially almost empty with only an helper to initialize it.
4. Double-click on the helper to populate the diagram: it is very, very long: more than 3 minutes on my (fast) machine.

Profiling shows that 67% of the time is spent in EdgeLayoutUpdaterModelChangeTrigger, which has two methods using O(N^2) algorithms: both isRefreshEdgeLayoutNeededForNotification and otherNotificationsAreConsequences are called once for each of the N changes in the transaction, and both methods get passed the full list of changes to iterate over.
Comment 1 Eclipse Genie CLA 2018-03-12 06:49:53 EDT 
New Gerrit change created: https://git.eclipse.org/r/119214
Comment 2 Laurent Fasani CLA 2018-03-12 07:18:51 EDT 
A first commit simply store Edge and Node, previously computed from a Notification, into two maps to avoid recompute it too many times.

The time passed in EdgeLayoutUpdaterModelChangeTrigger
|                | before  | with fix |
| time in ELUMCT | 153s    | 52s
| TOTAL time     | 214s    | 99s
| % time ELUMCT  | 72%     | 53%
Comment 3 Laurent Fasani CLA 2018-03-12 08:28:14 EDT 
So the time spent in EdgeLayoutUpdaterModelChangeTrigger has been divided by 3 but the global time has decreased of 25% only
Comment 4 Eclipse Genie CLA 2018-03-12 11:36:31 EDT 
New Gerrit change created: https://git.eclipse.org/r/119244
Comment 5 Laurent Fasani CLA 2018-03-13 04:53:15 EDT 
A new gerrit change Created (enhanced fix) : https://git.eclipse.org/r/#/c/119244/

The time passed in EdgeLayoutUpdaterModelChangeTrigger
|                | before  | with basic fix | with enhanced fix
| time in ELUMCT | 153s    | 52s            | 50ms
| TOTAL time     | 214s    | 99s            | 71s
| % time ELUMCT  | 72%     | 53%            | 0%

The algorithm has been change from O(n2) to O(n) and the View corresponding to Notification are computing once each.

This awesome result may seem supspect but I checked that we effectivel create 4012 CenterEdgeEndModelChangeOperation as before the changes.
Comment 8 Laurent Fasani CLA 2018-04-18 05:39:16 EDT 
Technical issue: no validation required
Comment 9 Florian Barbin CLA 2018-05-25 04:17:47 EDT 
It took around 80s to create and layout the diagram.
Comment 10 Laurent Redor CLA 2018-06-27 11:54:53 EDT 
Available in Sirius 6.0.0, see https://wiki.eclipse.org/Sirius/6.0.0 for details