Bug 12833 – REGRESSION: Selecting text in 6.6MB txt file is sluggish as of the Feb 19th nightly

• Status: RESOLVED
• Resolution: FIXED
• Component: Text

[David Smith]

The impression I'm getting is that the speed is directly related to how far down the document the selection is. Try scrolling to the bottom to see it more clearly.

Wondering if r19734 changed anything in this regard.

(In reply to comment #1)
> Wondering if r19734 changed anything in this regard.
> 

Apparently it didn't.

One thing that my be slowing things down is that if the document is loaded in multiple chunks, then it turns into multiple text nodes. The parser could be taught how to append to a text node.

A lot of time seems to be spent iterating over inline boxes trying to find the one containing a given offset, e.g. in RenderText::inlineBox().

[Maciej Stachowiak]

<rdar://problem/5028159>

[Antti Koivisto]

Created attachment 13540 [details]
improve selection performance

This patch improved time it takes to do SelectionController::setSelection() at the end of http://dscoder.com/test.txt from 200ms range to around 20ms. Unfortunately it is still more sluggish than Tiger WebKit but at least it is sort-of usable (selection is quite a bit faster in release build than debug build too).

Basic idea is to do way less line box traversing than before. It is also possible that some of the stuff editing code is doing during selections is actually unnecessary, I can't really tell. This patch doesn't change anything in that respect.

Comment on attachment 13540 [details]
improve selection performance

textBoxesCoverAllPositions() doesn't necessarily give the right answer for renderers containing reversed text (it may return false when the text boxes do in fact cover all positions). I didn't check how the answer is used so I don't know whether it's okay to return true in this case or whether the question is really "do the text boxes cover all positions in logical order?"

Comment on attachment 13540 [details]
improve selection performance

+                textOffset > 0 && textOffset <= textRenderer->lastTextBox()->start() + textRenderer->lastTextBox()->end())

Are you sure start() + end() is correct?

[Antti Koivisto]

(In reply to comment #6)
> (From update of attachment 13540 [details] [edit])
> textBoxesCoverAllPositions() doesn't necessarily give the right answer for
> renderers containing reversed text (it may return false when the text boxes do
> in fact cover all positions). I didn't check how the answer is used so I don't
> know whether it's okay to return true in this case or whether the question is
> really "do the text boxes cover all positions in logical order?"
> 

Correct, it doesn't optimize reversed text case. Doing that would also require also changes in the caller. Maybe adding a FIXME is enough...

[Antti Koivisto]

(In reply to comment #7)
> (From update of attachment 13540 [details] [edit])
> +                textOffset > 0 && textOffset <=
> textRenderer->lastTextBox()->start() + textRenderer->lastTextBox()->end())
> 
> Are you sure start() + end() is correct?
> 

Ooops. Good catch.

[Antti Koivisto]

Comment on attachment 13540 [details]
improve selection performance

clearing review flag, i'm updating the patch

[Antti Koivisto]

Created attachment 13560 [details]
updated patch

- rename textBoxesCoverAllPositions() to textBoxesCoverAllPositionsInOrder()
- use textBoxesCoverAllPositionsInOrder() optimization in more places
- faster VisiblePosition construction
- fix issue pointed out by Mitz
- cleanups

[Darin Adler]

Comment on attachment 13560 [details]
updated patch

+                    return currentPos;
+                else
+                    continue;

We normally don't do "else after return".

-    DeprecatedString string;
+    String string;

String has pathologically slow behavior when you resize it that DeprecatedString does not; it does a realloc every time you make it bigger. Instead you should probably use a Vector<UChar>.

[Justin Garcia]

Comment on attachment 13560 [details]
updated patch

From VisiblePosition::init():

     // When not at a line wrap, make sure to end up with DOWNSTREAM affinity.
-    if (m_affinity == UPSTREAM && (isNull() || inSameLine(VisiblePosition(position, DOWNSTREAM), *this)))
-        m_affinity = DOWNSTREAM;
+    if (m_affinity == UPSTREAM) {
+        VisiblePosition downstream(*this);
+        downstream.m_affinity = DOWNSTREAM;
+        if (isNull() || inSameLine(downstream, *this))
+            m_affinity = DOWNSTREAM;
+    }

There's a FIXME in canonicalPosition about how it will eventually need to take in the affinity and use it to find the canonical position to fix a bug (9535).  At that time we'll have to remove the above optimization. I'd add a note and mention the bug number.

[Antti Koivisto]

Created attachment 13599 [details]
Divide large text blocks (>64kB) over multiple text nodes

Instead of trying to make editing code efficient (which would be nice, but is bit risky at this point) the problem can be more or less completely hidden by dividing large text blocks over multiple text nodes. Shorter linebox lists are faster to search.

Dividing is done for both text and html documents. Firefox seems to be dividing large text nodes too (in html).

[Alexey Proskuryakov]

Comment on attachment 13599 [details]
Divide large text blocks (>64kB) over multiple text nodes

Discussed with Antti over IRC - according to his testing, this doesn't properly handle decomposed characters that happen to be on the boundary. I believe this needs to be corrected first.

See a test case at <http://nypop.com/~ap/webkit/large-text.html>.

[Alexey Proskuryakov]

r=me with changes discussed in detail over IRC (using CharacterBreakIterator::textBreakPreceding, adding a layout test), assuming all tests pass.

[Antti Koivisto]

Per Alexey's comments commited as r20127, with layout test for composed characters. 

[Alexey Proskuryakov]

This has regressed again - I've filed bug 55898 for that.