[Webkit-unassigned] [Bug 55440] New: improve layout performance by reducing the traversal time of the floating objects

[bugzilla-daemon at webkit.org]

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

           Summary: improve layout performance by reducing the traversal
                    time of the floating objects
           Product: WebKit
           Version: 528+ (Nightly build)
          Platform: PC
               URL: http://ie.microsoft.com/testdrive/Performance/MazeSolv
                    er/Default.html
        OS/Version: All
            Status: UNCONFIRMED
          Severity: Normal
          Priority: P2
         Component: Layout and Rendering
        AssignedTo: webkit-unassigned at lists.webkit.org
        ReportedBy: yuqiang.xian at intel.com


The WebKit layout engine performs bad on the case of MazeSolver from Microsoft (http://ie.microsoft.com/testdrive/Performance/MazeSolver/Default.html), which is caused by large overhead on traversing the floating objects list in logicalLeftOffsetForLine() and logicalRightOffsetForLine() especially when the list becomes enormous, for example in the default 30x30 maze there're >3700 floating objects. When placing a new floating object the entire list (from begin to end) is traversed for multiple times, and it requires O(n^2) time when we do a re-layout to place all the floating objects.
We need to improve such performance issue either 1) by improving the efficiency of the traversal (possibly by using other data structures to hold the floating objects), or 2) by reducing the chances to do the traversal. 
There's a low hanging fruit for approach 2) which is especially applicable in logicalLeftOffsetForLine and logicalRightOffsetForLine. As the two routines either cares about FloatLeft objects or FloatRight objects only, if we know there's no corresponding type floating objects in the list we can avoid the traversal actually. One thing we could do is to record the number of FloatLeft objects and the number of FloatRight objects and add a check before doing the traversal. This can improve the 30x30 MazeSolver performance by 80~90% measured on N450 Netbook MeeGo using latest Chromium browser 11 (i.e. from 503s to 269s to resolve the 30x30 maze). 
We could also think about traversing from the last visited object instead of from the beginning of the list each time when placing a new floating object, as long as we know that the state of the existing objects in the list doesn't change since last traversal, which could ideally convert the O(n^2) to O(n) when placing all the floating objects. But this is a bit tricky and needs further investigation.

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