Currently the floating RenderObjects are stored in a list and searched by using a linear search. When the number of floats increases the layout becomes very slow. A better structure should be used.
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.
Per discussion with David Hyatt: 1. We will go with interval trees. 2. Also other optimizations can be explored in order to avoid tree propagation through descendant blocks.
Created attachment 102931 [details] Patch
Created attachment 102936 [details] Patch Rebased the patch
Does this show a speed up on any tests? Can we construct a test that shows an improvement (something with a lot of floats)? Looking good though!
Created attachment 103014 [details] Simple Performance Test Created a simple performance test. On my machine I get nearly 7fps with nightly builds and about 18fps with this patch applied.
> Simple Performance Test Feel encouraged to put the perf test somewhere in this folder: http://trac.webkit.org/browser/trunk/PerformanceTests :)
(In reply to comment #7) > > Simple Performance Test > > Feel encouraged to put the perf test somewhere in this folder: > http://trac.webkit.org/browser/trunk/PerformanceTests > > :) I've added https://bugs.webkit.org/show_bug.cgi?id=65741 . I will submit a patch today.
Created attachment 103078 [details] Patch Removed the need to populate a vector.
Comment on attachment 103078 [details] Patch Attachment 103078 [details] did not pass chromium-ews (chromium-xvfb): Output: http://queues.webkit.org/results/9305871
Created attachment 103083 [details] Patch Fixed build.
(In reply to comment #6) > Created an attachment (id=103014) [details] > Simple Performance Test > > Created a simple performance test. > On my machine I get nearly 7fps with nightly builds and about 18fps with this patch applied. Very nice!
Comment on attachment 103083 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=103083&action=review Overall this looks pretty good. I have one major issue with the patch though, and that is that I would prefer it if the interval tree was built lazily if possible. I could be wrong about this but if you have something like this: <img style="float:left;width:10px;height:1000px"> <div><div><div>....lots more nested divs.... <div>Some text We propagate floating objects into all of the nested divs. This duplication is bad enough and is something we need to fix, but if you don't build the interval tree lazily you will also have tons of duplication in each div, even though nobody actually *tested* for overlap in any of the intermediate divs. It seems like you could have a notion of whether or not a float's overlap has been computed that is independent of being placed and add to the interval tree lazily when someone actually does an overlap test. I think I'd like to see a deeply nested div performance test in which many many floats intrude into all of those divs to verify the potential performance gain from the optimization I'm suggesting. That will also help us measure when we remove all of the duplicate FloatingObject construction down the road as well. > Source/WebCore/rendering/RenderBlock.cpp:94 > +#ifndef NDEBUG > +// These helpers are only used by the PODIntervalTree for debugging purposes. > +String ValueToString<int>::string(const int value) > +{ > + return String::number(value); > +} > + > +String ValueToString<RenderBlock::FloatingObject*>::string(const RenderBlock::FloatingObject* floatingObject) > +{ > + return String::format("%p (%dx%d %dx%d)", floatingObject, floatingObject->x(), floatingObject->y(), floatingObject->maxX(), floatingObject->maxY()); > +} > +#endif Can we put these at the end of the file along with the renderName dumping. > Source/WebCore/rendering/RenderBlock.cpp:1211 > + if (m_floatingObjects) > + m_floatingObjects->setHorizontalWritingMode(isHorizontalWritingMode()); Seems like you could do this inside clearFloats. > Source/WebCore/rendering/RenderBlock.cpp:3419 > floatingObject->setIsPlaced(); > + m_floatingObjects->addPlacedObject(floatingObject); You could move setIsPlaced inside addPlacedObject. > Source/WebCore/rendering/RenderBlock.cpp:3666 > floatingObject->setIsPlaced(true); > + m_floatingObjects->addPlacedObject(floatingObject); Again, you could move setIsPlaced inside addPlacedObject.
Note my comments about "You could move setIsPlaced inside addPlacedObject." don't apply if you do the lazy interval tree.
Created attachment 103242 [details] Patch Updated the floats test to also create some empty nested divs. It seems that the lazy init optimization makes a big difference. Thanks for the tip. Also addressed the other comments. Regarding "You could move setIsPlaced inside addPlacedObject" comment. I think it's ok to move it, even if I changed to lazy init now.
Comment on attachment 103242 [details] Patch Attachment 103242 [details] did not pass chromium-ews (chromium-xvfb): Output: http://queues.webkit.org/results/9329853 New failing tests: css2.1/t0905-c414-flt-wrap-00-e.html css2.1/t09-c5526c-display-00-e.html css2.1/t0905-c414-flt-03-c.html css1/box_properties/clear_float.html css1/box_properties/float_elements_in_series.html css1/box_properties/clear.html css1/formatting_model/vertical_formatting.html css1/box_properties/float_margin.html css2.1/t0905-c414-flt-04-c.html css2.1/t0905-c414-flt-02-c.html css2.1/t0905-c414-flt-00-d.html css2.1/t0905-c5525-fltblck-00-d-ag.html css1/formatting_model/floating_elements.html css2.1/t0905-c414-flt-wrap-01-d-g.html css1/box_properties/float.html css2.1/t0905-c414-flt-fit-01-d-g.html css1/box_properties/acid_test.html css2.1/t0905-c414-flt-01-d-g.html css1/box_properties/float_on_text_elements.html css2.1/t0905-c414-flt-fit-00-d.html
Created attachment 103246 [details] Fixed build
Created attachment 103247 [details] Patch
Created attachment 103252 [details] Patch
Comment on attachment 103252 [details] Patch All looks good! r=me!
Comment on attachment 103252 [details] Patch Clearing flags on attachment: 103252 Committed r92610: <http://trac.webkit.org/changeset/92610>
All reviewed patches have been landed. Closing bug.
This has been rolled out in bug 65868, correct?
(In reply to comment #23) > This has been rolled out in bug 65868, correct? Yes. I've added https://bugs.webkit.org/show_bug.cgi?id=65871 and submitted the patch on that bug.