Last modified: 2013-07-31 01:22:19 UTC
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.
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.
