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

Details

Reference
bz52013

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().

(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.

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?

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?

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 ;)

(In reply to comment #3)

Suggestion from IRC, posting to the bug for prosperity:

s/prosperity/posterity/ ;-)

[cf. bug 49198 comment 5]

(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.

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

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

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

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

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

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

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

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

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

Merged and deployed.

Add Comment