Bug 56796 - Investigate whether line breaking algorithm is efficient
Summary: Investigate whether line breaking algorithm is efficient
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-03-21 18:56 PDT by Tony Gentilcore
Modified: 2013-08-22 14:25 PDT (History)
11 users (show)

See Also:


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

Note You need to log in before you can comment on or make changes to this bug.
Description Tony Gentilcore 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.
Comment 1 James Robinson 2011-03-22 00:16:40 PDT
Created attachment 86433 [details]
slightly more robust testcase
Comment 2 James Robinson 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.
Comment 3 James Robinson 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.