Bug 94429

Summary:

TextIterator takes O(n^2) to iterate over n empty blocks

Product:

WebKit

Reporter:

mitz

Component:

HTML Editing

Assignee:

Nobody <webkit-unassigned>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

enrica, mifenton, webkit.review.bot

Priority:

Keywords:

InRadar

Version:

528+ (Nightly build)

Hardware:

Unspecified

OS:

Unspecified

Attachments:

Description	Flags
Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition	sam: review+

Description mitz 2012-08-19 10:35:15 PDT

<rdar://problem/12104508>

Iterating over a structure like
<div>
    <div></div>
    <div></div>
        ⋮
    <div></div>
</div>

using TextIterator takes O(n^2) in the number of blocks, since shouldRepresentNodeOffsetZero() creates a VisiblePosition for each block, which in turn requires iterating over all successive blocks.

Comment 1 mitz 2012-08-19 10:39:22 PDT

Created attachment 159299 [details]
Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition

Comment 2 Sam Weinig 2012-08-19 16:09:17 PDT

Comment on attachment 159299 [details]
Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition

Looks good. Is this a case where making a performance test that can detect n vs n^2 would be a good idea?

Comment 3 mitz 2012-08-21 09:44:07 PDT

Fixed in <http://trac.webkit.org/r126164>.