Bug 94429

Summary: TextIterator takes O(n^2) to iterate over n empty blocks
Product: WebKit Reporter: mitz
Component: HTML EditingAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal CC: enrica, mifenton, webkit.review.bot
Priority: P2 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+

mitz
Reported 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.
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+
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
mitz
Comment 1 2012-08-19 10:39:22 PDT
Created attachment 159299 [details] Improve shouldRepresentNodeOffsetZero()’s check for nodes that cannot contain a VisiblePosition
Sam Weinig
Comment 2 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?
mitz
Comment 3 2012-08-21 09:44:07 PDT
Fixed in <http://trac.webkit.org/r126164>.
Note You need to log in before you can comment on or make changes to this bug.