[Webkit-unassigned] [Bug 56796] Investigate whether line breaking algorithm is efficient

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=56796


James Robinson <jamesr at chromium.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |darin at apple.com,
                   |                            |hyatt at apple.com,
                   |                            |mitz at webkit.org




--- Comment #2 from James Robinson <jamesr at chromium.org>  2011-03-22 00:26:04 PST ---
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.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.