The time complexity analysis is correct, but tracing shows that the slowness should be attributed to something else.

Experimented with http://www.crossui.com/test/test.html (taken from  issue 246093 ):
1. Open the page. Do not perform any action; just wait until page load.
2. Start tracing
3. Click inside the <textarea>. Wait until all red underlines appear
4. Stop tracing

Tracing result shows that, while SpellChecker::markAndReplaceFor took a lot of time, most of its time was taken by updateMarkerRenderedRect, which is a static function in DocumentMarkerController.cpp. Further analysis shows that Range::boundingBox took most of the running time.

Deleted: Screenshot from 2016-12-06 15:27:47.png 102 KB

	Screenshot from 2016-12-06 15:27:47.png 102 KB View Download

The slowness of Range::boundingBox is due to iterating over all the InlineTextBoxes under a LayoutText, which is hard to optimize.

On the other hand, maybe we don't need to updated rendered rectangle for spelling markers. The only client of class RenderedDocumentMarker is FrameView::getTickmarks, which is called by Scrollbar to render the tickmarks for each text match.

Hence, I don't think we need to maintain rendered rectangles for other types of document markers.

Removing Blink>DOM since we do not consider optimizing Range::boundingBox as a solution.

Another idea is to postpone the calculation of rendered rect until needed. Since DocumentMarkerController::renderedRectsForMarkers() is the only direct client of RenderedDocumentMarker, and the function already calls updateMarkerRenderedRectIfNeeded, it is guaranteed to get correct result even if we do not call updateMarkerRenderedRect in DocumentMarkerController::addMarker.

Hence, we should be able to safely remove updateMarkerRenderedRect from addMarker.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/f6763007a1508ccbff5f635202c950367769855e

commit f6763007a1508ccbff5f635202c950367769855e
Author: xiaochengh <xiaochengh@chromium.org>
Date: Tue Dec 06 09:30:05 2016

Make calculation of document marker's rendered rect on demand

Currently, when adding a document marker, we calculate its rendered
rectangle synchronously by calling updateMarkerRenderedRect in
DocumentMarkerController::addMarker.

This is not needed, since when we retrieve the rendered rectangles
(only possible via DMC::renderedRectsForMarkers),
updateMarkerRenderedRectIfNeed is also called, calculating the marker's
rendered rectangle if we haven't done it before.

Hence, this patch removes the updateMarkerRenderedRect call from
DMC::addMarker as a performance improvement.

BUG= 668408 

Review-Url: https://codereview.chromium.org/2557563003
Cr-Commit-Position: refs/heads/master@{#436553}

[modify] https://crrev.com/f6763007a1508ccbff5f635202c950367769855e/third_party/WebKit/Source/core/editing/markers/DocumentMarkerController.cpp

In retrospect, the time complexity analysis may be less significant than we thought.

Though the running time is indeed quadratic, the text length of each request is bounded by kChunkSize=16384 (defined in SpellChecker::chunkAndMarkAllMisspellings). The time spent on text iterating is a product of:
- The number of (nodes + lines) of text checked by the request
- The number of misspellings
which is typically at the order of 10000.

As the only observed source of slowness is fixed, we mark this issue as fixed.