Performance issues after undoing pasting a lot of content

[Reinmar]

🐞 Is this a bug report or feature request? (choose one)

• Bug report

💻 Version of CKEditor

📋 Steps to reproduce

1. Go to https://developer.mozilla.org/en-US/docs/Web/HTML/Element/table
2. Select all and copy
3. Paste into the editor.
4. Undo.

✅ Expected result

Undoing should not take disturbingly long (max 1s seems reasonable for this content).

❎ Actual result

Undoing takes a couple of secs.

📃 Other details that might be useful

See also: https://github.com/ckeditor/ckeditor5-undo/issues/65#issuecomment-313668491 and https://github.com/ckeditor/ckeditor5-engine/issues/897

[Reinmar]

Some observations and ideas:

1. The insertContent() method inserts nodes one by one. This means creating many operations for inserting one big blob of data which in turn means undoing them one by one which requires a lot of operation transformations.

   Instead, this method should batch content to be inserted in doc frags and insert those doc frags at once.

   This should actually fix the issue.

2. Another thing to investigate is the use of maps in the OT algoritms. According to my quick profiling session which looked like this:

   

   _updateContext() took 2.5s from the entire 6.5s. This isn't surprising because for undoing a simple batch with 5 weak insert ops (typing 5 lettets) I saw this on the console:

   

   after logging out wasAffected in here: https://github.com/ckeditor/ckeditor5-engine/blob/aba8e6864448f07da837bf4ce3a88a3d9d3141e2/src/model/delta/transform.js#L518-L520

   If we really need to store all this data two things should be checked:

   • whether all this data cannot be stored in one flat map – e.g. by creating keys based on deltas unique ids (e.g. ${ delta1.id }-${ delta2.id }-${ delta3.id })
   • whether we aren't abusing new Map() because it seems that we're cloning some information on and on instead of adding to existing maps

So these are two first places to look for speed.

[Reinmar]

I made such a change out of curiosity:

And it saved us 2.5s. Unfortunately, it doesn't seem to be correct because then all those new deltas will reuse the same map. But, surprise, surprise, all tests (engine/model,undo) pass :D So it's worth considering anyway.

[Reinmar]

whether all this data cannot be stored in one flat map – e.g. by creating keys based on deltas unique ids (e.g. ${ delta1.id }-${ delta2.id }-${ delta3.id })

@scofalik confirmed that this should be possible. Basically, we need to store a 2-dimensional map of (delta,delta=>value). Right now we use a nested maps for that (like [[],[],[]]). Instead, we could assign ids to all deltas and use ids of two deltas to create a string key in a 1-dimensional map. In this way we'll avoid creating maps.