O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine) |
||
Issue descriptionsetLogicalWidthForTextRun (LayoutBlockFlowLine) is O(#BidiRun x #WordMeasurement), which is similar to O(line-length!). When a line has a lot of words (#WordMeasurement increases) and has collapsible whitespaces or mixed RTL (#BidiRun increases), layout performance is not linear. Performance tests[1] demonstrate this issue: long-line-nowrap-collapse.html Canary: 1153ms Edge: 139ms Gecko: 38ms long-line-nowrap-spans-collapse.html Canary: 1140ms Edge: 225ms Gecko: 33ms [1] https://codereview.chromium.org/2284113003
,
Aug 31 2016
The following revision refers to this bug: https://chromium.googlesource.com/chromium/src.git/+/ccd49c63f329c36da86b128b30e277d72f5bc76d commit ccd49c63f329c36da86b128b30e277d72f5bc76d Author: kojii <kojii@chromium.org> Date: Wed Aug 31 16:17:44 2016 Fix O(n!) in setLogicalWidthForTextRun (LayoutBlockFlowLine) When there are multiple BidiRun in a line (multiple inline elements, whitespace collapsing, or RTL,) setLogicalWidthForTextRun has O(#BidiRun * #WordMeasurement), resulting similar characteristics as O(n!) for the line length. This patch fixes this for LTR. For RTL, we could improve up to log2(N) by using binary search, or better by using fast index for LineLayoutText for multiple elements case. It was once tried but removed due to its complexity, we can do it if they came up as real cases. Following performance tests are now 10-20x faster. The amount of text for these tests were increased by 12x, matching to long-line-nowrap.html. PerformanceTests/Layout/long-line-nowrap-collapse.html PerformanceTests/Layout/long-line-nowrap-spans-collapse.html BUG=583711, 642345 Review-Url: https://codereview.chromium.org/2285053002 Cr-Commit-Position: refs/heads/master@{#415647} [modify] https://crrev.com/ccd49c63f329c36da86b128b30e277d72f5bc76d/third_party/WebKit/PerformanceTests/Layout/long-line-nowrap-collapse.html [modify] https://crrev.com/ccd49c63f329c36da86b128b30e277d72f5bc76d/third_party/WebKit/PerformanceTests/Layout/long-line-nowrap-spans-collapse.html [modify] https://crrev.com/ccd49c63f329c36da86b128b30e277d72f5bc76d/third_party/WebKit/Source/core/layout/LayoutBlockFlowLine.cpp
,
Sep 1 2016
|
||
►
Sign in to add a comment |
||
Comment 1 by kojii@chromium.org
, Aug 30 2016