| d57562ceb31842c7bcdb28c084c863631a844acd |
|
08-Dec-2017 |
Seigo Nonaka <nona@google.com> |
Implement new line breaker for greedy algorithm
The new greedy line breaker is 2x faster than current line breaker.
Current greedy line breaker does lots of unnecessary things.
- Hyphenation is not necessary until the word is too long for the line.
- Cost calculation and optimization for the cost is not necessary. Only
if the break point is inside email or url. This can be done in O(1).
The new line breaker is fully compatible with older line breaker except
for
- Overhang calculation is dropped since it is implemented partially but
not consistent with other line break strategy. Also it is not exposed
as Java API.
- The priority of desperate line breaking and hyphenation is not consistent
and current master implementation is broken. Sometimes the line
breaker exceeds the line width. The new line breaker has explicit
priority for the hyphenation and keep the line width under the limit.
(See Issue 70415793)
Compatibility:
To check the compatibility from current implementation, manually
compared the line break result for the UDHR text (http://unicode.org/udhr/).
Then verified new implementation completely replicate the same output as the
current implementaiton.
Here is the combination verified:
Langauge: ar, zh-CN, zh-TW, nl, fr, de, it, ja, ko, po, pl-PL, pl-BR,
ru, es-ES, th, tr, bg, ca, hr, cs, da, el, he, hi, hu, id,
lv, lt, no, ro, sr-Cyrl, sr-Latn, sk, sl, sv, uk, vi
Font Size: 14px, 15px, 16px, 17px, 18px, 19px
Line Width: 128px, 256px, 512px, 1024px
Performance:
Here is the performance score:
(All greedy algorithm, w/o patch -> w/ patch, median, N=100)
Random, No Style, Hyphenation OFF: 7,854,007 -> 7,780,766 (-0.93%)
Random, No Style, Hyphenation ON : 19,274,298 -> 7,762,346 (-60.0%)
Measured, No Style, Hyphenation OFF: 516,039 -> 424,173 (-18.0%)
Measured, No Style, Hyphenation ON : 11,772,800 -> 482,506 (-96.0%)
I'll remove old greedy line breaker once this is submitted.
Test: CtsTextTestCases:*
Test: CtsGraphicsTestCases:*
Test: CtsWidgetTestCases:*
Test: minikin_test
Bug: 70415793
Bug: 65024629
Bug: 64389125
Change-Id: Iaff9afed4bb6eebecb010e468546239f10852903
/frameworks/minikin/libs/minikin/LineBreakerUtil.cpp
|