RESOLVED FIXED Bug 94429
TextIterator takes O(n^2) to iterate over n empty blocks 
https://bugs.webkit.org/show_bug.cgi?id=94429
Summary TextIterator takes O(n^2) to iterate over n empty blocks
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.