Use TextNode.replaceData and TextNode.appendData

[pjasiun]

We could consider using TextNode.replaceData and TextNode.appendData instead of overwriting data property. We should check if it improves anything. It may help browsers to properly introduce changes, not to move selection if it is in the node we change and helps avoiding breaking composition.

[f1ames]

The code change itself will not be very complex (will push PR soon) as we already have proper diff implementation (diff and diffToChanges) which plays nicely with CharacterData.insertData and CharacterData.deleteData.

However, the thing we should consider here is performance since this task changes simple value update:

https://github.com/ckeditor/ckeditor5-engine/blob/cb03a607624387be83dc790abe4e09d15bf233a7/src/view/renderer.js#L428-L430

to complex "diffing and partial updates" strategy (note from @pjasiun that the diff performance is poor when comparing two totally different strings).

When renderer._updateText is used?

First I took a look at in what cases renderer._updateText function is really executed to see what impact it may have. Honestly, I haven't found any simple case in which renderer._updateText is called. In most cases renderer._updateChildren is used (but it happens sometimes, for example, in ckeditor/ckeditor5-engine#1349 case when composed styled character is inserted outside currently focused node and renderer._updateChildren is used).

The reason for this is as follows (see also https://github.com/ckeditor/ckeditor5-engine/issues/1342#issuecomment-373778804). Even for simplest operations, like inserting single character, there are two types of mutations fired (to be precise characterData mutation and our change:children event):

• text
• children

Both text node and element node (or basically a family/subtree of elements) are marked to be updated by renderer. Then renderer assumes that if a text node which should be updated is inside element node which eventually will be updated too, there is no point in updating text node itself (makes perfect sense IMHO), so updating text is skipped (here we go back to Avoid unnecessary structure updates from ckeditor/ckeditor5-engine#1342).

I checked following scenarios on Chrome and FF:

• insert text
  • typing
  • pasting
  • composing
• remove text
  • via keyboard (collapsed / ranged selection)
  • select and cut
• replace text
  • select and type
  • select and paste
  • select and compose
• undo/redo
• inline/block styles insertion (and then typing inside) on collapsed/ranged selection

and for all of them renderer._updateChildren is used.

This is a state for now. The important thing is that the improvements in the renderer we will work in the future will alter this behaviour and renderer._updateText will be used more frequently. Two changes which probably will have the biggest impact on this behaviour: ckeditor/ckeditor5-engine#1125 (deep text nodes rerendering - already in review) and of course, already mentioned, Avoid unnecessary structure updates from ckeditor/ckeditor5-engine#1342 (we may get to the point where most operations on text nodes will only use renderer._updateText without touching element nodes if not really necessary).

[f1ames]

Performance

I started testing performance on editor instance, but it quickly became obvious that the bottleneck here is a diff function. To test it properly and see how it performs in various scenarios I created simple script which runs diff function simulating various text modifications (deleting, inserting, replacing text) to see how it performs.

The previous domText.data = expectedText; takes around less than 1ms in most scenarios and the difference between scenarios is very minimal.
With diff it varies greatly, depending on content modification. The biggest slowdown can be observed when text (or its part) is replaced by different text.

I placed the results here. It is clearly visible that replacing bigger part of the text causes diff to slow down for longer texts:

Initial text length - 381 characters:

Initial text length - 761 characters:

Initial text length - 1142 characters:

Initial text length - 1522 characters:

[f1ames]

Solution

One of the biggest improvement we hope to achieve is improving composition handling (especially during collaborative scenarios). From what I checked it is broken now (FF for example):

From some initial tests it seems this fix will not solve all issues I was able to generate with composition and programmatically inserting text (which simulates collaboration) in the same text node, but still there are other task waiting (#1342) so at the end it should improve composition/collaboration too IMHO.

Due to the fact of poor diff performance in some cases, I think we cannot use this solution for all scenarios. We may think of:

1. Not implementing it now, wait for other renderer improvements and get back to it when we will encounter issues directly caused by this (it will come sooner or later iMHO and then we will face the same problems as now - or maybe not and then we don't have to change it).
2. Go with the solution this ticket initially proposed, but limit diff usage to cases when compared texts are relatively short so we won't hit diff bottleneck. Still, performance depends on many external factors and there always be a case when someone has slower machine (so diff performs poorly) or encounters a case with longer texts which breaks something.
3. Look for other solution, but I'm not sure if there is any. Partial text node updates will always required some kind of diffing mechanism.
4. Use more performant diff function. The downside - there always will be some performance limit when such function starts to perform poorly. For faster functions it may be encounter just less frequently.
   From what I have searched I found fastDiff library (it is on Apache License 2.0 and takes 25 KB unminified so I'm not sure if it would be suitable for CKEditor 5 - but it shows diffing can be faster) which is visibly faster than our current diff:

Initial text length - 1522 characters:

WDYT @Reinmar @pjasiun?

[Reinmar]

One thing is unclear to me - how much does this solution help. You only mentioned that something is still broken on Firefox. But does it work better in general? Because, if it does, I'd continue this research. One thing that I'm planning for a long time is a simpler diff method which would scan both strings from both ends and find first different characters. Text between these indexes needs to be replaced. This should be much faster and, at the same time, completely sufficient for cases like typing and rendering. I'm not even sure whether typing doesn't use this diffing mechanism already.

…

Sent from my iPhone

On 22 Mar 2018, at 13:12, Krzysztof Krztoń ***@***.***> wrote: Solution One of the biggest improvement we hope to achieve is improving composition handling (especially during collaborative scenarios). From what I checked it is broken now (FF for example): From some initial tests it seems this fix will not solve all issues I was able to generate with composition and programmatically inserting text (which simulates collaboration) in the same text node, but still there are other task waiting (#1342) so at the end it should improve composition/collaboration too IMHO. Due to the fact of poor diff performance in some cases, I think we cannot use this solution for all scenarios. We may think of: Not implementing it now, wait for other renderer improvements and get back to it when we will encounter issues directly caused by this (it will come sooner or later iMHO and then we will face the same problems as now - or maybe not and then we don't have to change it). Go with the solution this ticket initially proposed, but limit diff usage to cases when compared texts are relatively short so we won't hit diff bottleneck. Still, performance depends on many external factors and there always be a case when someone has slower machine (so diff performs poorly) or encounters a case with longer texts which breaks something. Look for other solution, but I'm not sure if there is any. Partial text node updates will always required some kind of diffing mechanism. Use more performant diff function. The downside - there always will be some performance limit when such function starts to perform poorly. For faster functions it may be encounter just less frequently. From what I have searched I found fastDiff library (it is on Apache License 2.0 and takes 25 KB unminified so I'm not sure if it would be suitable for CKEditor 5 - but it shows diffing can be faster) which is visibly faster than our current diff: Initial text length - 1522 characters: WDYT @Reinmar @pjasiun? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[Reinmar]

PS. The idea behind this diff mechanism is that in our cases, atomic changes like typing are affecting only a narrow part of the text.

…

Sent from my iPhone

On 22 Mar 2018, at 13:12, Krzysztof Krztoń ***@***.***> wrote: Solution One of the biggest improvement we hope to achieve is improving composition handling (especially during collaborative scenarios). From what I checked it is broken now (FF for example): From some initial tests it seems this fix will not solve all issues I was able to generate with composition and programmatically inserting text (which simulates collaboration) in the same text node, but still there are other task waiting (#1342) so at the end it should improve composition/collaboration too IMHO. Due to the fact of poor diff performance in some cases, I think we cannot use this solution for all scenarios. We may think of: Not implementing it now, wait for other renderer improvements and get back to it when we will encounter issues directly caused by this (it will come sooner or later iMHO and then we will face the same problems as now - or maybe not and then we don't have to change it). Go with the solution this ticket initially proposed, but limit diff usage to cases when compared texts are relatively short so we won't hit diff bottleneck. Still, performance depends on many external factors and there always be a case when someone has slower machine (so diff performs poorly) or encounters a case with longer texts which breaks something. Look for other solution, but I'm not sure if there is any. Partial text node updates will always required some kind of diffing mechanism. Use more performant diff function. The downside - there always will be some performance limit when such function starts to perform poorly. For faster functions it may be encounter just less frequently. From what I have searched I found fastDiff library (it is on Apache License 2.0 and takes 25 KB unminified so I'm not sure if it would be suitable for CKEditor 5 - but it shows diffing can be faster) which is visibly faster than our current diff: Initial text length - 1522 characters: WDYT @Reinmar @pjasiun? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[f1ames]

Pushed initial changes to https://github.com/ckeditor/ckeditor5-engine/tree/t/403 (and also diff performance manual test to https://github.com/ckeditor/ckeditor5-utils/commits/t/ckeditor5-engine/403-diffperformance so it won't get lost on my local machine).

[f1ames]

@Reinmar, true I didn't dive deep enough into how it helps to say what is the real improvement. Partially because we have other things (like selection rerendering, element/children updates, etc) which we plan to improve, but the final flow may be hard to simulate so I can check how it helps in current state (and only try to simulate more or less how it will help with other improvements). I will take another look at it to see what is the real improvement.

One thing that I'm planning for a long time is a simpler diff method which would scan both strings from both ends and find first different characters. Text between these indexes needs to be replaced.

I was also thinking about how such approach (comparing start\end or if previous text is a substring of the new one) could help here and if it can help solve most of the issue (same as complex diff would).

[f1ames]

I did some testing with collaborative editing to check how this fix on its own may improve composition handling.

Tested scenarios:

• text inserted before/after selection
• text deleted before/after selection
• text replaced before/after selection (it's basically insert + delete so if something is broken in one of this two, it will be also broken during replace)
• inserting/moving markers (already reported in https://github.com/cksource/ckeditor5-collaboration/issues/169 and ckeditor/ckeditor5-engine#1384)

Tested on Chrome, FF and Safari with macOS accent panel, Spanish accent and Japanese Hiragana input:

• Chrome
  • accent - works fine
  • es - broken
  • jp - broken (especially when rerender happens during switching characters)
• FF
  • accent - broken
  • es - broken
  • jp - broken
• Safari
  • accent - broken
  • es - broken
  • jp - broken

The important thing to keep in mind is that it works (or rather doesn't work) the same way before and after applying the fix with smart text node rendering. The reason for this is mentioned in one of the comments above (https://github.com/ckeditor/ckeditor5-engine/issues/403#issuecomment-374646680):

Both text node and element node (or basically a family/subtree of elements) are marked to be updated by renderer. Then renderer assumes that if a text node which should be updated is inside element node which eventually will be updated too, there is no point in updating text node itself, so updating text is skipped.

So for all tested scenario simply renderer._updateChildren was executed which replaced whole text nodes. That's the reason improved code wasn't even run.

---

Then I changed the code by removing !this.markedChildren.has( node.parent ) && in
https://github.com/ckeditor/ckeditor5-engine/blob/8f66d9678b29a96ae4f42267650c04ecc90f07f6/src/view/renderer.js#L202 so even if text node is a child of element node marked to render, text node also will be rerendered. This simulates the situation when only necessary rerendering happens so it shows how composition handling will improve with this fix. There were some visible improvements:

• Chrome
  • accent - works fine (apart from ckeditor/ckeditor5-engine#1349)
  • es - works fine, broken only for text removal on the beginning of the paragraph (as renderer._updateChildren is still used in this case)
  • jp - same as with es
• FF
  • accent - breaks only when content before selection is manipulated
  • es - same as in Chrome
  • jp - same as with es
• Safari
  • accent - breaks only when content before selection is manipulated
  • es - breaks only when content before selection is manipulated
  • jp - breaks only when content before selection is manipulated

As for FF (haven't observed in other browsers) it seems that there is more general issue. When text before selection is manipulated between compostionstart and composing (inserting) some characters (this might be compositionupdate or compositionend event) the composed character is inserted in a wrong offset (which is selection offset +/- length of inserted/removed text before selection).

So there is visible improvement. Not for all cases, but this fix may definitely helps in some of them.

The other observation I had is that before this change (the temporary code change mentioned on the beginning of this section) whole text nodes were replaced by renderer._updateChildren. After the change, text nodes were rerendered so renderer._updateChildren didn't have to perform any replacing because text nodes were already synchronized. So maybe similar behaviour should be considered when working on avoiding unnecessary structure updates improvement.

[f1ames]

We have decided to try approach with the simpler diff:

One thing that I'm planning for a long time is a simpler diff method which would scan both strings from both ends and find first different characters. Text between these indexes needs to be replaced. This should be much faster and, at the same time, completely sufficient for cases like typing and rendering. I'm not even sure whether typing doesn't use this diffing mechanism already.

As mentioned in the above comment, similar technique is already used when handling text mutations.

---

The interesting thing is that also diff function is used there. So why performance issues described above are not visible there?

Mutations are only fired for typing so there are two basic cases:

• one character is inserted
• selected content is replaced by one inserted character

and those are not the cases in which diff has some visible performance issues. I only noticed some visible lag when instead of regular typing, composition is used (see https://github.com/ckeditor/ckeditor5-typing/issues/145).

[f1ames]

The diffing mechanism mentioned above will be introduced in https://github.com/ckeditor/ckeditor5-utils/issues/235.

[f1ames]

I switched to fastDiff and performance issues are gone as expected. Now, I will evaluate collaborative scenarios (same as in https://github.com/ckeditor/ckeditor5-engine/issues/403#issuecomment-376490425) to check if fastDiff have same benefits as diff.

[f1ames]

Results are the same when using diff (tested the same way with !this.markedChildren.has( node.parent ) removed). There are some cases in which diff may perform better as it provides full diff, and fastDiff will replace bigger part of text in such cases, but for regular typing results are the same for both. After testing fastDiff:

• Chrome
  • accent - works fine apart from ckeditor/ckeditor5-engine#1349,
  • es - works fine, broken for text removal on the beginning of the paragraph,
  • jp - works in the same manner as es.
• FF
  • accent - breaks only when content before selection is manipulated (happens only when total length of text changes so it might be something similar to ckeditor/ckeditor5-engine#1349),
  • es - works fine, broken for text removal on the beginning of the paragraph (also keep in mind FF general issue mentioned in https://github.com/ckeditor/ckeditor5-engine/issues/403#issuecomment-376490425),
  • jp - works in the same manner as es.
• Safari
  • accent - breaks only when content before selection is manipulated,
  • es - breaks only when content before selection is manipulated,
  • jp - breaks only when content before selection is manipulated.

This means fastDiff could be used instead of diff here. Important thing to notice is that this improvement will be not visible untill Avoid unnecessary structure updates (#1342) is implemented as mentioned in https://github.com/ckeditor/ckeditor5-engine/issues/403#issuecomment-376490425 before:

Both text node and element node (or basically a family/subtree of elements) are marked to be updated by renderer. Then renderer assumes that if a text node which should be updated is inside element node which eventually will be updated too, there is no point in updating text node itself, so updating text is skipped.