RESOLVED FIXED 13920
Line layout is O(n^2) (slower than Firefox) 
https://bugs.webkit.org/show_bug.cgi?id=13920
Summary Line layout is O(n^2) (slower than Firefox)
David Kilzer (:ddkilzer)
Reported 2007-05-29 21:08:26 PDT
When loading the URL referenced in this bug, a local debug build of WebKit nightly r21856 with Safari 2.0.4 (419.3) on Mac OS X 10.4.9 (8P135) takes a long time to load and consumes 100% CPU the whole time. Unofficial timing results (provided by a hand-operated stopwatch) by loading the file over the network on my Quad G5: Safari 2.0.4 (419.3): 1 minute 23.6 seconds (100%) LOCAL-DEBUG-BUILD-WebKit-r21856: 5 minutes 48.9 seconds (100%) WebKit-Nightly-r21869: 1 minute 5.4 seconds (100%) Firefox 2.0.0.3: 38.9 seconds (100%) Opera 9.21: 7 minutes 6.5 seconds (40%) [was 20% done at ~2 minutes] The WebKit nightly hasn't regressed from shipping Safari, but the nightly is 68% slower than Firefox 2. Opera seems to be hitting some kind of exponential algorithm. :( Also, Firefox renders everything on the page underlined--not sure what's going on there.
Attachments
Fix the invalidateVerticalPositions walk. (2.50 KB, patch)
2007-05-29 22:29 PDT, Dave Hyatt 		no flags
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
David Kilzer (:ddkilzer)
Comment 1 2007-05-29 21:10:01 PDT
Created attachment 14779
Dave Hyatt
Comment 2 2007-05-29 21:39:45 PDT
Interesting. We are pretty slow on this page yeah. Is it horribly misnested or something?
Dave Hyatt
Comment 3 2007-05-29 21:56:58 PDT
invalidateVerticalPositions() dominates the sample.
Dave Hyatt
Comment 4 2007-05-29 22:28:09 PDT
Line layout has a number of O(n^2) issues. This page is exposing them.
Dave Hyatt
Comment 5 2007-05-29 22:29:18 PDT
Created attachment 14780 [details] Fix the invalidateVerticalPositions walk. This improves the invalidateVerticalPosition walk and a bit of a speed boost.
Dave Hyatt
Comment 6 2007-05-29 22:43:10 PDT
Fix landed. Keep the bug open, as there's a lot more work to do. ddkilzer, could you retime us and see where we stand now?
Mark Rowe (bdash)
Comment 7 2007-05-29 22:53:37 PDT
Comment on attachment 14780 [details] Fix the invalidateVerticalPositions walk. Clearing review flag to get this out of the review queue now it's been landed.
David Kilzer (:ddkilzer)
Comment 8 2007-05-30 07:04:57 PDT
(In reply to comment #6) > Fix landed. r21879 > Keep the bug open, as there's a lot more work to do. ddkilzer, > could you retime us and see where we stand now? Will do!
David Kilzer (:ddkilzer)
Comment 9 2007-05-30 14:46:34 PDT
(In reply to comment #8) > (In reply to comment #6) > > Keep the bug open, as there's a lot more work to do. ddkilzer, > > could you retime us and see where we stand now? > > Will do! Switched to loading the file locally for the tests, so DO NOT compare these results to previous results. r21869: 0:60.5, 0:56.9, 0:57.4, 0:58.1 AVG: 0:58.2 r21900: 0:49.3, 0:53.8, 0:55.8, 0.48.5 AVG: 0.51.9 Still totally unofficial and timed by hand.
Gavin Sherlock
Comment 10 2009-02-01 10:08:33 PST
The test url no longer exists.
Note You need to log in before you can comment on or make changes to this bug.