Bug 94429 - TextIterator takes O(n^2) to iterate over n empty blocks
Summary: TextIterator takes O(n^2) to iterate over n empty blocks
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: HTML Editing (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2012-08-19 10:35 PDT by mitz
Modified: 2012-08-21 09:44 PDT (History)
3 users (show)

See Also:


Attachments
Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition (2.30 KB, patch)
2012-08-19 10:39 PDT, mitz
sam: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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>.