[Webkit-unassigned] [Bug 65668] Optimize floating elements lookup

Thu Aug 4 00:29:39 PDT 2011

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

--- Comment #1 from Chiculita Alexandru <achicu at adobe.com>  2011-08-04 00:29:39 PST ---
Two options are currently available:
1. Use the shape algebra algorithm described in Graphics Gems II and implemented in Regions.cpp that is used by WebKit2 to track the dirty areas
2. Use the PODIntervalTree.h  that was used by the GPU rendering of polygons in WebCore

Regions:
* Regions.cpp seems to be very promising although the current implementation is not there yet. My current prototype is slower then the simple linear search. It needs to be highly optimized for our simple operation: adding a new rectangle (ie. no full memory copies, in-place updates, skipping spans before and after the rectangle)
* Uses less memory then interval trees for compact floats that have same height (eg. lots of floats per line)
* It is not able to query a list of floats that affect a line and that might later be needed for wrap-shape exclusions.
* Search time should be O(logN) where N is the amount of spans created by the algorithm.

Interval trees: 
* Current prototype is already very fast
* Uses a fixed amount of memory O(N) where N is number of floats, but I think that can be improved by merging the nodes for the compact floats. It should become similar to Regions and will also improve speed (because of having less nodes).
* Has O(logN) insert/remove/search times (N is the number of floats)
* Can query exact list of floats for a specific line

Regions.cpp uses a lot less memory when the floats are really compact. However, it seems to take a lot of time to update the structure. The memory increases when the floats are really small in height, because it will tend to create lots of spans.  However, the implementation in Regions is not optimized for lots of spans. There's an optimization mentioned at the end of the Graphics Gems chapter about skipping non-affected spans. Also we only need to unite a rect and in that case the operation can be further optimized. 

Memory allocations are also a big issue, a simple operation will copy the whole structure. The article optimizes the memory allocations by using a linked list and doing most of the updates in-place. The Regions.cpp implementation also tries to merge spans, but the article says it is not worth the time if the structure is not going to be used for a bigger amount of time. In our case the Region will always be recreated when a new layout is done. 

Indeed the query for rectangles at a specific height can be very fast, it would only require a search in a sorted list. It should always retrieve a maximum of two rectangles: one for all the floats on the left and one rectangle for all the floats on the right, so the actual calculation is pretty easy. That will get a little more complicated for positioned elements. However, when wrap-shapes will be implemented, it will need to know exactly what floats are on the line, so that the wrap-shape can be taken into account. Using this algorithm that information seems to be lost in the compression. The alternative would be to approximate the curves of the wrap-shape using rectangles and pollute the floats Region. Having that will create lots of spans and will only make it a lot slower. Moreover, such a solution will make it dependent on the resolution.

Removing the floats below a specified Y value can also be optimized by just removing all the spans after one point. That is needed when rewinding a line, for example for pagination purposes.
MarkAllDescendantsWithFloatsForLayout also removes the floats, but it looks like there's no need to update the Region in that case. That's because the layout will be forced on those blocks , so the region will be totally cleared anyway. In that case it seems it always just adds new rectangles, so a subtract is not actually needed, meaning that we can optimize only for a union between a Region and a LayoutRect.

An interval tree will create a node for each placed float. The implementation is based on a red/black balanced tree, so we got O(logN) for all the operations. The good news is that the implementation allocates the nodes in an arena, so it is very fast because no free or destroy callbacks are used. The arena goes away when the tree is cleared and that will happen at beginning of every layout. That is important because we tend to have few removals from the tree (only when a line is rewinded at the end of a column/region/page). The interval tree is very predictable,  it always uses a specific amount of memory O(n) where n is the number of floats and it has O(logN) insert/remove/search times. It also allows querying an exact list of floats that are affecting a line (needed for wrap-shape).

The memory of the interval tree may be improved by doing a search before adding a new interval. For example multiple same height floats on a single line can be merged together, all it needs to do is to update offset of the interval.

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