Apache OpenOffice (AOO) Bugzilla – Issue 106127
Some speedups for basegfx in CWS vcl106
Last modified: 2009-12-08 12:05:50 UTC
While profiling the testcase for issue 105769 it showed that there are some opportunities for speedups by - reserving a reasonable size for a vector first instead of only relying on the vector's intrinsic reallocation - splitting up beziers at their extremas avoids the costly test for cusps and loops inside each curve - speeding up extremely often used methods in BasicRange etc.
Done in CWS vcl106: reserving enough so that reallocations during adaptiveSubdivide are usually avoided
@hdu: nice work; I assume this is commit aead6f479ffe (and some more to come)?
> I assume this is commit aead6f479ffe Yup. > (and some more to come)? Probably. Now that I also got issue 105769 I will probably focus on avoiding the costly basegfx methods altogether.
Done in CWS vcl106: avoiding the expensive part of the cubic-bezier self-intersection test if possible reduces the cost of these tests in the overall profile of the i105769-testcase from 49% to <0.2% :-)
Done in CWS vcl106: some of the most serious performance problems in basegfx are caused by having polygons with too many line-segments which were artificially created by bezier subdivision. Reducing the number of these line segments by splitting the bezier at optimal points resulting in less segments can improve the performance significantly. So I added a method B2DCubicBezier::getMaxDistancePositions() to find these optimal split points: The curve's maximum distance to the line through startpoint and endpoint are such candidates.
Done in CWS vcl106: with all the optimizations above the basegfx::solver still consumes 90% of the time in the i105769-testcase. Especially the current implementations of bezier-bezier and bezier-line solvers are expensive. They already were avoided in the many cases where there is no overlap at all between both candidates, but it they were still called too often. Even when the control-bounds just touched the calls were done. This is a good idea for non-neighboring edges but neighboring edges always touch because they have one edge-point in common -> solved by introducing Range::overlapsMore() and using it for neighboring edges. This reduces the cost of addPointsAtCutsAndTouches() by a factor of 2.3. There is still more potential as the neighboring edges first-segment and last-segments are still fully tested. Ideas for a better name for Range::overlapsMore() are welcome
Done in CWS vcl106: basegfx likes to create a lot of polygon on the fly. Now that the related vector reallocations are not a perf-problem anymore due to pre-allocations (see above) it shows that the use of generic vector.insertAtIndexWithCount() instead of a plain vector.push_back() costed 5% of the solver time! Fixed in CWS vcl106.
Enough for CWS vcl106. More speedups to come in the next CWS.
Still in CWS vcl106.
Got into DEV300_m65