[Webkit-unassigned] [Bug 114088] New: performance issue in WebCore::Editor::updateMarkersForWordsAffectedByEditing()

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=114088

           Summary: performance issue in
                    WebCore::Editor::updateMarkersForWordsAffectedByEditin
                    g()
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: All
        OS/Version: All
            Status: UNCONFIRMED
          Severity: Normal
          Priority: P2
         Component: WebCore Misc.
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: webkit-rth at hashimoto.us


The question at:

http://stackoverflow.com/questions/15751399/what-is-causing-this-long-delay-when-i-clear-a-form-input-in-chrome

describes the bug and links to this to reproduce the bug:

http://jsfiddle.net/jmilloy/dHFsQ/

Basically what happens is when an input text element is cleared in a table that contains many rows of an HTML entity, this browser temporarily hangs.  The bug was reported on Chrome (across many platforms) but also occurs on Safari.  I verified that the bug occurs on the WebKit nightly build from 06 April 2013: Version 6.0.3 (7536.28.10, 537+).

I did some investigation using Chromium.  The time is being consumed in calls to RuleBasedBreakIterator::handleNext() and RuleBasedBreakIterator::handlePrevious().  I believe what is happening is that WebKit is attempting to update markers on the surrounding content (not sure why since the change is within an input element).  WebKit tries to define a range to update that has a word boundary at the beginning and end of the range.  It searches for that boundary in this code from WebCore::nextBoundary():

    while (!it.atEnd()) {
        // Keep asking the iterator for chunks until the search function
        // returns an end value not equal to the length of the string passed to it.
        if (!inTextSecurityMode)
            string.append(it.characters(), it.length());
        else {
            // Treat bullets used in the text security mode as regular characters when looking for boundaries
            String iteratorString(it.characters(), it.length());
            iteratorString.fill('x');
            string.append(iteratorString.characters(), iteratorString.length());
        }
        next = searchFunction(string.data(), string.size(), prefixLength, MayHaveMoreContext, needMoreContext);
        if (next != string.size())
            break;
        it.advance();
    }

The problem occurs because boundary is not found until the end of the surrounding content, which in this case is thousands of characters long.  This search is O(n^2) in the length of the word found because this loop keeps adding a character to the string and testing if the result completes a word.  The string data looks like this:

0x69e0e400:    0x2c     0x00 0x0a 0x00 0x26 0x20 0x0a 0x00
0x69e0e408:    0x26 0x20 0x0a 0x00 0x26 0x20 0x0a 0x00
0x69e0e410:    0x26     0x20 0x0a 0x00 0x26 0x20 0x0a 0x00
0x69e0e418:    0x26     0x20 0x0a 0x00 0x26 0x20 0x0a 0x00
0x69e0e420:    0x26     0x20 0x0a 0x00 0x26 0x20 0x0a 0x00
0x69e0e428:    0x26     0x20 0x0a 0x00 0x26 0x20 0x0a 0x00
...

which appears to be UTF-16 for a comma/newline followed by thousands of ellipsis/newline pairs.

I don't understand (1) why any of the surrounding content needs markers updated when the edit was inside an input element and (2) why the word boundary search fails on a string that contains so many newlines.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.