Bug 56796

Summary:

Investigate whether line breaking algorithm is efficient

Product:

WebKit

Reporter:

Tony Gentilcore <tonyg>

Component:

Layout and Rendering

Assignee:

Nobody <webkit-unassigned>

Status:

NEW

Severity:

Normal

CC:

abarth, darin, hyatt, igor.oliveira, jamesr, jchaffraix, mihaip, mitz, ned, tonikitoo, tonyg

Priority:

Version:

528+ (Nightly build)

Hardware:

All

OS:

All

Attachments:

Description	Flags
Line breaking test case	none
slightly more robust testcase	none

Tony Gentilcore

Reported 2011-03-21 18:56:02 PDT

Created attachment 86403 [details] Line breaking test case The attached test case loads 200k of compiled javascript in iframes of varying widths. According to the Inspector's timeline, when that frame is 300px wide, the layout takes ~50ms on my machine, however when it is 5px wide it takes ~550ms. In firefox, the layouts do get slower as width decreases, but it tops out at about 100ms instead of 550ms. It is worth noting that FF seems to break less often and thus might have a simpler algorithm. But we should make sure we are using a linear algorithm here if possible.

Attachments
Line breaking test case (554 bytes, text/html) 2011-03-21 18:56 PDT, Tony Gentilcore	no flags	Details
slightly more robust testcase (993 bytes, text/html) 2011-03-22 00:16 PDT, James Robinson	no flags	Details
View All Add attachment proposed patch, testcase, etc.

James Robinson

Comment 1 2011-03-22 00:16:40 PDT

Created attachment 86433 [details] slightly more robust testcase

James Robinson

Comment 2 2011-03-22 00:26:04 PDT

On the second testcase (download and run it locally, it violates same-origin policy like crazy) i get these times on my MacBook Pro with WebKit r local release build: time: 533 ms width: 0px height: 3086880 time: 531 ms width: 10px height: 3086880 time: 531 ms width: 20px height: 3086880 time: 547 ms width: 30px height: 3086880 time: 462 ms width: 40px height: 3081060 time: 269 ms width: 50px height: 1567230 time: 179 ms width: 60px height: 1066455 time: 148 ms width: 70px height: 809025 time: 107 ms width: 80px height: 555645 time: 98 ms width: 90px height: 479940 time: 88 ms width: 100px height: 423960 time: 84 ms width: 110px height: 380880 time: 74 ms width: 120px height: 317640 time: 73 ms width: 130px height: 294045 time: 71 ms width: 140px height: 273420 time: 69 ms width: 150px height: 255855 time: 64 ms width: 160px height: 227565 time: 64 ms width: 170px height: 215685 time: 63 ms width: 180px height: 204435 time: 58 ms width: 190px height: 195435 which indicates that the layout time is roughly fixed around 533 until the width exceeds 20px, after which it seems like fewer linebreaks are needed and the algorithm speeds up to a floor somewhere around 50ms. On firefox 3.6.15 (using a local copy of the data file to avoid violating S.O.P.) I get: time: 1218 ms width: 0px height: 2911048 time: 1092 ms width: 10px height: 2911048 time: 1830 ms width: 20px height: 2911048 time: 1871 ms width: 30px height: 2911048 time: 2050 ms width: 40px height: 1016834 time: 1166 ms width: 50px height: 777952 time: 925 ms width: 60px height: 640360 time: 700 ms width: 70px height: 545776 time: 582 ms width: 80px height: 418516 time: 526 ms width: 90px height: 375788 time: 486 ms width: 100px height: 343378 time: 420 ms width: 110px height: 291886 time: 374 ms width: 120px height: 271964 time: 340 ms width: 130px height: 254086 time: 324 ms width: 140px height: 238798 time: 306 ms width: 150px height: 213808 time: 293 ms width: 160px height: 202300 time: 309 ms width: 170px height: 193228 time: 269 ms width: 180px height: 176092 time: 259 ms width: 190px height: 168644 the shape of the curve is kind of interesting, and it seems that gecko is line breaking less often (the height is not as high) but overall we compare favorably to gecko in terms of raw perf. Minefield 4.0b13pre gets into an infinite loop in its line breaking algorithm on this page (I'll submit a Mozilla bug). Opera 11.01 build 1190 is just bizarre as Opera tends to be. I get this output: time: 136 ms width: 0px height: 0 time: 145 ms width: 10px height: 0 time: 279 ms width: 20px height: 0 time: 12303 ms width: 30px height: 0 time: 12101 ms width: 40px height: 0 time: 6870 ms width: 50px height: 0 time: 5692 ms width: 60px height: 0 time: 4223 ms width: 70px height: 0 time: 2594 ms width: 80px height: 0 time: 2060 ms width: 90px height: 0 time: 1657 ms width: 100px height: 0 time: 1356 ms width: 110px height: 0 time: 1009 ms width: 120px height: 0 time: 852 ms width: 130px height: 0 time: 759 ms width: 140px height: 0 time: 671 ms width: 150px height: 0 time: 562 ms width: 160px height: 0 time: 503 ms width: 170px height: 0 time: 470 ms width: 180px height: 0 time: 433 ms width: 190px height: 0 which has crazy times, but given that the heights are bogus I'm not sure wtf it is doing.

James Robinson

Comment 3 2011-03-22 01:41:07 PDT

Disregard the times from comment #2, I was getting confused by the 'save page as' feature. It seems like a large source of variance is how we treat the string data inside the <iframe> tag. We treat string data as if it were a large bag of text inside a <pre style="word-wrap: break-word; white-space: pre-wrap;"></pre> and do layout as such. Other browsers seem to do something much simpler (but not as pretty). Here's a test page with the most obvious variations: http://webstuff.nfshost.com/linebreak/. The test closest to the real website is http://webstuff.nfshost.com/linebreak/linebreak-js-as-js.html which loads the javascript as a .js referenced directly from .src. In this config, WebKit's load+layout times look like this: time: 594 ms width: 0px height: 3086880 time: 616 ms width: 10px height: 3086880 time: 629 ms width: 20px height: 3086880 time: 637 ms width: 30px height: 3086880 time: 582 ms width: 40px height: 3081060 time: 298 ms width: 50px height: 1567230 time: 215 ms width: 60px height: 1066455 time: 176 ms width: 70px height: 809025 time: 130 ms width: 80px height: 555645 time: 122 ms width: 90px height: 479940 time: 128 ms width: 100px height: 423960 time: 105 ms width: 110px height: 380880 time: 95 ms width: 120px height: 317640 time: 94 ms width: 130px height: 294045 time: 84 ms width: 140px height: 273420 time: 83 ms width: 150px height: 255855 time: 79 ms width: 160px height: 227565 time: 76 ms width: 170px height: 215685 time: 73 ms width: 180px height: 204435 time: 79 ms width: 190px height: 195435 compared to Firefox 4.0b13pre: time: 56 ms width: 0px height: 5432 time: 41 ms width: 10px height: 5432 time: 42 ms width: 20px height: 5432 time: 41 ms width: 30px height: 5432 time: 43 ms width: 40px height: 5432 time: 42 ms width: 50px height: 5432 time: 54 ms width: 60px height: 5432 time: 31 ms width: 70px height: 5432 time: 47 ms width: 80px height: 5432 time: 43 ms width: 90px height: 5432 time: 38 ms width: 100px height: 5432 time: 42 ms width: 110px height: 5432 time: 39 ms width: 120px height: 5432 time: 39 ms width: 130px height: 5432 time: 38 ms width: 140px height: 5432 time: 38 ms width: 150px height: 5432 time: 40 ms width: 160px height: 5432 time: 31 ms width: 170px height: 5432 time: 40 ms width: 180px height: 5432 time: 43 ms width: 190px height: 5432 clearly gecko just isn't doing much line breaking here. If, however, the two browsers are coerced into rendering the page the same way by HTML escaping the JS and wrapping it in an appropriate <pre> tag then the WebKit behavior is the same but Gecko produces this: time: 2364 ms width: 0px height: 2911048 time: 1689 ms width: 0px height: 2911048 time: 1709 ms width: 0px height: 2911048 time: 1014 ms width: 0px height: 2911048 (infinite loop here in the linebreaking code) which isn't nearly as impressive. firefox 3.6.15 can load the page: time: 1516 ms width: 0px height: 2911048 time: 1844 ms width: 10px height: 2911048 time: 1905 ms width: 20px height: 2911048 time: 1837 ms width: 30px height: 2911048 time: 2120 ms width: 40px height: 1016834 time: 1150 ms width: 50px height: 777952 time: 914 ms width: 60px height: 640360 time: 714 ms width: 70px height: 545776 time: 576 ms width: 80px height: 418516 time: 539 ms width: 90px height: 375788 time: 485 ms width: 100px height: 343378 time: 421 ms width: 110px height: 291886 time: 372 ms width: 120px height: 271964 time: 338 ms width: 130px height: 254086 time: 319 ms width: 140px height: 238798 time: 304 ms width: 150px height: 213808 time: 294 ms width: 160px height: 202300 time: 274 ms width: 170px height: 193228 time: 270 ms width: 180px height: 176092 time: 258 ms width: 190px height: 168644 so the overall shape of the curve looks similar but it's a good bit slower than WebKit the closest thing I can find to an apples-to-apples comparison is http://webstuff.nfshost.com/linebreak/linebreak-js-as-html.html where the JS is HTML escaped (so string literals aren't misparsed as html) and loaded as a .JS file. There the times and final metrics seem roughly comparable: WebKit: time: 54 ms width: 0px height: 650 time: 52 ms width: 10px height: 650 time: 53 ms width: 20px height: 650 time: 43 ms width: 30px height: 650 time: 64 ms width: 40px height: 650 time: 46 ms width: 50px height: 650 time: 122 ms width: 60px height: 635 time: 122 ms width: 70px height: 590 time: 115 ms width: 80px height: 560 time: 109 ms width: 90px height: 485 time: 113 ms width: 100px height: 427 time: 135 ms width: 110px height: 412 time: 118 ms width: 120px height: 382 time: 125 ms width: 130px height: 382 time: 108 ms width: 140px height: 367 time: 113 ms width: 150px height: 352 time: 117 ms width: 160px height: 337 time: 115 ms width: 170px height: 322 time: 117 ms width: 180px height: 322 time: 127 ms width: 190px height: 322 firefox 4.0b13pre: time: 53 ms width: 0px height: 727 time: 115 ms width: 10px height: 727 time: 119 ms width: 20px height: 727 time: 126 ms width: 30px height: 727 time: 138 ms width: 40px height: 711 time: 117 ms width: 50px height: 711 time: 139 ms width: 60px height: 645 time: 149 ms width: 70px height: 596 time: 174 ms width: 80px height: 530 time: 173 ms width: 90px height: 497 time: 139 ms width: 100px height: 481 time: 187 ms width: 110px height: 464 time: 218 ms width: 120px height: 448 time: 160 ms width: 130px height: 431 time: 130 ms width: 140px height: 415 time: 139 ms width: 150px height: 386 time: 121 ms width: 160px height: 370 time: 121 ms width: 170px height: 370 time: 142 ms width: 180px height: 370 time: 118 ms width: 190px height: 370 Opera produces weird results and just crashes randomly. Oh Opera. So in summary, I think our line breaking code is doing OK here relative to other browsers but the way we choose to format what we think is plain text inside an <iframe> causes a big perf hit for this particular "preloading" technique.

Note You need to log in before you can comment on or make changes to this bug.