VisualEditor: Deleting plain text from a large page with backspace or delete is very slow
Closed, ResolvedPublic

Description

Using the backspace or delete key to delete plain text on a large page takes hundreds of milliseconds per character, predominantly because ve.dm.Document.prototype.commit() is called, which leads to ve.ce.ContentBranchNode.prototype.onChildUpdate(), which leads to ve.dm.Converter.openAndCloseAnnotations(), which calls containsComparableForSerialization(), which is apparently O(N).

Bug 52012 also affects backspace performance.


Version: unspecified
Severity: normal

bzimport set Reference to bz52013.
tstarling created this task.Via LegacyJul 25 2013, 5:01 AM
tstarling added a comment.Via ConduitJul 25 2013, 5:56 AM

The slowness of ve.dm.Converter.openAndCloseAnnotations() also dominates the performance of ve.dm.Converter.prototype.getDomFromData(), severely affecting both initial setup and "review changes". In both actions, on my favourite test case for today ([[Argentina]]), about 10s of CPU usage is attributable to openAndCloseAnnotations(), and about 80% of that is from oo.compare().

MZMcBride added a comment.Via ConduitJul 25 2013, 6:19 AM

(In reply to comment #1)

In both actions, on my favourite test case for today ([[Argentina]]), about
10s of CPU usage is attributable to openAndCloseAnnotations(), and about 80%
of that is from oo.compare().

Perhaps related to bug 51948.

Catrope added a comment.Via ConduitJul 25 2013, 11:01 PM

Suggestion from IRC, posting to the bug for prosperity:

[15:12] <RoanKattouw> TimStarling: As a hack, could you try to set ve.compare = function ( a, b ) { return ve.getHash( a ) === ve.getHash( b ); }; instead of ve.compare = oo.compare; (in ve.js) and see how much that mitigates the problem?

Catrope added a comment.Via ConduitJul 25 2013, 11:10 PM

Further suggestion: when we're comparing annotations, try to compare store indexes wherever possible. When we're comparing for identity, like when comparing for serialization when both annotations are generated, we could compare store indexes rather than using ve.compare(). And if we throw comparable objects into the store, we might be able to do index comparison there too.

Maybe ve.dm.Annotation instances should have properties that track the store index of their this.element and their comparable objects?

Ed, could you play with this?

Catrope added a comment.Via ConduitJul 26 2013, 12:11 AM

Even further suggestion from Tim: make the IVStore use a binary search tree, where the nodes are something like { index: number, value: Object } and the comparison operates on the objects, something similar to oo.compare() but returns < or >. This requires an ordering on the keys. We could do alphabetic order like in keySortReplacer, but it would be more efficient to have the ve.dm.Annotation object return an ordering on the keys. Or something. This is an incomplete thought and requires experimentation.

Giving this to Ed because he's a machine that turns vague incomplete suggestions into working code and fixes a few bugs in the process too ;)

MZMcBride added a comment.Via ConduitJul 26 2013, 1:22 AM

(In reply to comment #3)

Suggestion from IRC, posting to the bug for prosperity:

s/prosperity/posterity/ ;-)

[cf. bug 49198 comment 5]

tstarling added a comment.Via ConduitJul 26 2013, 1:42 AM

(In reply to comment #5)

Even further suggestion from Tim: make the IVStore use a binary search tree,
where the nodes are something like { index: number, value: Object } and the
comparison operates on the objects, something similar to oo.compare() but
returns < or >. This requires an ordering on the keys. We could do alphabetic
order like in keySortReplacer, but it would be more efficient to have the
ve.dm.Annotation object return an ordering on the keys. Or something. This is
an incomplete thought and requires experimentation.

The point of this would be to reduce the memory usage of IVStore by eliminating the duplication caused by using the JSON as a key, and also to reduce the CPU overhead of ve.getHash(). But note that neither of these things are confirmed as performance issues in the profiling I have done so far.

In any case, comparison of store indexes would obviously be faster than binary search followed by value comparison. So I think index comparison should be the priority, of the ideas discussed here, assuming it can be implemented in such a way that pressing backspace on plain text will predominantly hit index comparison rather than value comparison. After that is implemented, we can do more profiling and decide whether the use of ve.getHash() is a problem worthy of significant development time.

gerritbot added a comment.Via ConduitJul 26 2013, 2:43 PM

Change 76100 had a related patch set uploaded by Esanders:
Quick optimisation to avoid containsComparableForSerialization

https://gerrit.wikimedia.org/r/76100

gerritbot added a comment.Via ConduitJul 26 2013, 3:43 PM

Change 76110 had a related patch set uploaded by Esanders:
Further annotation optimisations

https://gerrit.wikimedia.org/r/76110

Esanders added a comment.Via ConduitJul 26 2013, 4:00 PM

With these two patches ^^^ getDomFromData has sped up from 1150ms to 180ms on my local copy of en:Argentina.

gerritbot added a comment.Via ConduitJul 26 2013, 11:14 PM

Change 76100 merged by jenkins-bot:
Quick optimisation to avoid containsComparableForSerialization

https://gerrit.wikimedia.org/r/76100

gerritbot added a comment.Via ConduitJul 27 2013, 1:13 AM

Change 76110 merged by jenkins-bot:
Speed up openAndCloseAnnotations by using store indexes

https://gerrit.wikimedia.org/r/76110

Jdforrester-WMF added a comment.Via ConduitJul 31 2013, 1:22 AM

Merged and deployed.

Add Comment