I suspect the performance regression coincides with changes to multi-column painting and/or layout.

To chrishtr@ for confirmation on history of multicol changes.

Thank you for looking into this, @chrishtr! This issue costs me in thousands of lost users of my Android app since November, will do anything to help further. You may email me directly if any help or further input is needed.

I created a test page with text divided into columns, at:

http://hyperionics.com/test/LoremIpsum.html
or
https://hyperionics.com/test/LoremIpsum.html

Please open this page on Android Chrome latest version (now 63.0.3239.111), then tap any place in the text. It highlights elements, including sentences, marked with <span> elements, in yellow, another tap on the same element makes background white again. Note the delay.

On my Pixel 2 XL phone, so with a fast mobile processor, it takes about 2 seconds before any element turns yellow. Then test the same in Firefox browser - the background change happens instantly. Also if you downgrade Android's Chrome browser to older version (I uninstalled Chrome updates on my Pixel 2, which reverted Chrome browser to ver. 58.0.3029.125), the background change is instant.

Hope someone can help or a fix can be found quickly... Thank you!

Greg Kochaniak, Hyperionics

Tested the current Chrome Beta (ver. 64.0.3282.29) and Dev. (ver. 65.0.3299.6) from Google Play on the same device (Pixel 2 XL) - the problem is gone in both beta and dev versions, only the current release of Chrome (and the WebView it provides) are buggy.

Question: when will the current beta make it to full release, or the release will get this fix even without updating to full v64? My app loses hundreds of active users daily due to this issue. Also, is there a way to set Chrome Beta as the WebView control for apps?

I can reproduce the slowness on Chrome 63. Cannot reproduce it on Chrome 64 beta.
Next step is to bisect what fixed it.

Bisect results: https://chromium.googlesource.com/chromium/src/+log/b2e7ef01b15272ba2d39fff1965df80f63aa59fc..a3a235fd4439f981f37489c98bf61e3f4e82d444

It was fixed by this CL:

https://chromium.googlesource.com/chromium/src/+/2cff87c380b22ade36aa4d85a6f983387559178c

which made paint invalidation much faster for fragmented/paginated content.

This CL is in Chrome 64. Unfortunately it is too risky to merge it to Chrome 63
at this point.

However, I should note that paint invalidation for paginated content has been slow for a
number of releases.

Thank you again for looking into this! Pity it can't be fixed soon, a few more weeks with this buggy Chrome/WebView will probably put me out of business...

Just a note on @chrishtr comment: "note that paint invalidation for paginated content has been slow for a number of releases" - it could be that the change in the latest beta fixes a very old issue, however there was a recent change in release builds of Chrome, around late November of 1st half of December, that made rendering attribute changes in multi-column layout a lot, lot slower than in older versions. That other, breaking change may be unrelated to what you discovered about the fix in Chrome 64.

This bug was in Chrome 63, then when 64 and its corresponding WebView were released on Android it was fixed for a while. Now it is back again, multi-column layout is painfully slow, effectively making apps unresponsive for 30 seconds and longer. I tested the current releases of Chrome 64.0.3282.137 (current regular release in Google Play), Chrome Beta 65.0.3325.53, and Chrome Dev 66.0.3343.0 - the bug exists in all of them. PLEASE RE-OPEN THIS ISSUE. Please stop breaking Chrome, or at least Android WebView, over and over...

Do the results you described in comment 4 still apply? Is it still 2 seconds for you?

Right now on Pixel 2 XL and Chrome 64.0.3282.137 my test page https://hyperionics.com/test/LoremIpsum.html takes about 1 second to highlight each touched sentence, or hide the highlight. So it is faster than it was before in the broken version 63. I make the fonts 300% to force more columns also to magnify the effect. But compare the same text in Firefox on the same phone - I barely touch the sentence and it gets highlighted instantly, not after 1 second.

However my app needs to divide sometimes a long text into multiple "pages" - it's a kind of ebook/document/web page reader, the user may turn pages with horizontal scrolls like in a book. But it also reads aloud, highlighting each read sentence, and the user may double-tap sentences to highlight them and start reading from there. For about 160 kB long text (so nothing super long) the Pixel 2 XL takes 20-30 seconds to paginate the text now, and each double-tap or highlight hangs the app for 30 seconds again. When testing on an old slow device with Chrome 39 WebView, it's all instantaneous...

Thank you for looking into this again!

Greg

Any hope for resolution at all? I'm testing recent versions of Chrome Beta (65.0.3325.74) and Dev (66.0.3348.3) and the bug is still there.

Testing Chrome Beta 65.0.3325.85 released today, the bug is still there.

Tested Chrome Dev ver. 66.0.3352.3 released today - the bug persists. Why nobody cares to even comment on this, yet resolve it??? WebView on Android system is a mess, wish there was an alternative.

To be clear, the test page in the browser is adequate, though not great (that's what I'm seeing), but the app using WebView is slow?

What is the WebView version?

The app is extremely slow, on a fast phone takes about 10 seconds to highlight a new sentence, while permits versions was instant. WebView versions tested are exactly the same day Chrome versions I reported above.

I FINALLY nailed what the problem is: my LoremIpsum.html did not demonstrate it adequately, because it occurs only if the text is formatted as one very long paragraph. I modified it to make it one paragraph that is about 200 kB long - try now:

https://hyperionics.com/test/LoremIpsum.html

in Chrome browser on Android. Takes a long time to sub-divide into columns, then 6-12 seconds to highlight each sentence in the long paragraph. Try the same link in Firefox - no problem at all, everything is instant. Same on my old Android 5.1 emulator with old WebView v.39.something - instant.

Chrome versions tested today, where the issue occurs: general release in Google Play - ver. 64.0.3282.137, and Chrome Beta 65.0.3325.85

Funny thing - once a given span has been highlighted once, then the next tap to turn highlight off or on again is fast, but each new one takes 6-12 seconds... Also, Chrome Beta seems slightly faster now, on my Pixel 2 XL each tap on a span takes about 6 seconds in Beta, about 9 seconds in general release, before the highlight appears.

Thanks. Even on desktop there is a notable delay now with that test case.

I'll add notification times to make sure we look at this, but don't expect anything super quick.

Tested again all the Chrome versions I could find in Google Play, the issue is still present on all of them:

- general release Chrome 64.0.3282.137
- Chrome Beta 65.0.33.25.109
- Chrome Dev 66.0.3356.0
- Chrome Canary 67.0.3363.3

Meantime Google Play store is giving me for the first time a warning, ANRs for my app over the "good behavior" threshold. They should give this warning and grief to you, Chrome developers, not my humble app...

FYI, here is one of the stack traces of a most common ANR (Application Not Responding timeout) reports of my app. Probably from a device with TalkBack enabled? It's adding some info to web nodes of the document, and it seems to be also very slow, just like setting the background color in my test case:

From: Asus ZenFone 3 (ZE552KL) (ASUS_Z012D), 3027MB RAM, Android 8.0

  "main" prio=5 tid=1 Native
  | group="main" sCount=1 dsCount=0 flags=1 obj=0x745ec890 self=0x7316cc0a00
  | sysTid=19606 nice=-4 cgrp=default sched=0/0 handle=0x731b3639b0
  | state=S schedstat=( 23295100800 2117175079 24266 ) utm=2165 stm=164 core=7 HZ=100
  | stack=0x7fdafc8000-0x7fdafca000 stackSize=8MB
  | held mutexes=
 
  #00  pc 000000000001dd6c  /system/lib64/libc.so (syscall+28)
 
  #01  pc 00000000000e1a48  /system/lib64/libart.so (_ZN3art17ConditionVariable16WaitHoldingLocksEPNS_6ThreadE+152)
 
  #02  pc 0000000000325754  /system/lib64/libart.so (_ZN3art3JNI15CallVoidMethodVEP7_JNIEnvP8_jobjectP10_jmethodIDSt9__va_list+492)
 
  #03  pc 000000000070ffd0  /data/app/com.android.chrome-1/base.apk (???)
 
  at org.chromium.content.browser.accessibility.WebContentsAccessibility.nativePopulateAccessibilityNodeInfo (WebContentsAccessibility.java)
 
  at org.chromium.content.browser.accessibility.WebContentsAccessibility.createAccessibilityNodeInfo (WebContentsAccessibility.java:53)
 
  at android.view.accessibility.AccessibilityRecord.setSource (AccessibilityRecord.java:150)
 
  at org.chromium.content.browser.accessibility.WebContentsAccessibility.buildAccessibilityEvent (WebContentsAccessibility.java:274)
 
  at org.chromium.content.browser.accessibility.WebContentsAccessibility.sendAccessibilityEvent (WebContentsAccessibility.java:265)
 
  at org.chromium.content.browser.accessibility.WebContentsAccessibility.handleContentChanged (WebContentsAccessibility.java:313)
 
  at org.chromium.base.SystemMessageHandler.nativeDoRunLoopOnce (SystemMessageHandler.java)
 
  at org.chromium.base.SystemMessageHandler.handleMessage (SystemMessageHandler.java:9)
 
  at android.os.Handler.dispatchMessage (Handler.java:105)
 
  at android.os.Looper.loop (Looper.java:169)
 
  at android.app.ActivityThread.main (ActivityThread.java:6595)
 
  at java.lang.reflect.Method.invoke (Method.java)
 
  at com.android.internal.os.Zygote$MethodAndArgsCaller.run (Zygote.java:240)
 
  at com.android.internal.os.ZygoteInit.main (ZygoteInit.java:767)

This might be the same as https://bugs.chromium.org/p/chromium/issues/detail?id=795839

The NextAction date has arrived: 2018-03-12

Well, next action date came and passed, and nothing happens... I just updated Chrome Dev on my Pixel 2 XL phone, it's showing version 66.0.3359.30 now, and the issue is still there, absolutely nothing changed. Very disappointing...

Hello, this may or may not be related, but it seems that Chrome Webview either stops rendering after first 499 cols (v65) or repeates rendering 499th col (v66)

@thebeast, please star this issue too, maybe if we have 22,000 stars they will finally take us seriously...

There's a quadratic performance complexity issue when using columns.
See attachment. Try with 250 lines. Then try with 500 lines. Four times slower.

Deleted: quadratic-performance-complexity.html 815 bytes

quadratic-performance-complexity.html 815 bytes View Download

Well, quadratic or no, other browsers can do this in a blink of an eye, only Chrome got here slow after version 64 or 65. Before that it was fast too.

Chris, could you help explain what's causing this? Where's the code that gets executed 500*500 times when there's 500 columns?

The reason that the example in comment #29 has quadratic performance is that each of the
<br> elements spans all of the columns. Therefore there as many fragments for each <br>
as there are columns.

Since the atom of layout and painting going forward is the fragment rather than the element,
this means that we have to have in the worst case (# elements) * (fragments per element) total
objects for painting, which is a quadratic dependency.

How can each BR element span each column? Could you point me to some code that's executed columnCount^2 times?

See the for loop in PaintPropertyTreeBuilder::CreateFragmentContextsInFlowThread.

Regarding span each column: when I tested your page with N=400, each BR
had size 0,0 100x160000. Isn't this spanning all 400 columns?

Thanks! Errr, yes, that would be spanning a lot of columns! So now I wonder why we are building the world's tallest BRs. I'll have a look.

Debugged some more. Found that inlines defer to their containing block for
the value of object_bounding_box_in_flow_thread. Working on some code to
see if this can be improved to just the bounds.

Oh dear, that's pretty bad, and it explains why we have this bug. We should already have code that properly calculates the bounding box of inlines.

Yep, working on that now.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/51c414eb1d6d6903afea0018367d787ff219989b

commit 51c414eb1d6d6903afea0018367d787ff219989b
Author: Chris Harrelson <chrishtr@chromium.org>
Date: Thu May 24 23:05:17 2018

[PE] Use LocalVisualRect as the bounds of a non-box when computing fragmentation bounds

Previously, we used the bounds of the containing block. This can be very inefficient in cases
such as long paragraphs of text within a single block, leading to excessive numbers of column
fragments.

Bug:797591

Cq-Include-Trybots: master.tryserver.blink:linux_trusty_blink_rel;master.tryserver.chromium.linux:linux_layout_tests_slimming_paint_v2
Change-Id: I455ef37cad4d97f8069aa37dc3542e290b6aeab6
Reviewed-on: https://chromium-review.googlesource.com/1070562
Commit-Queue: Chris Harrelson <chrishtr@chromium.org>
Reviewed-by: Morten Stenshorne <mstensho@chromium.org>
Cr-Commit-Position: refs/heads/master@{#561676}
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/TestExpectations
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/paint/invalidation/multicol/multicol-with-inline-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/paint/invalidation/multicol/multicol-with-text-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/linux/paint/invalidation/multicol/multicol-repaint-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/linux/virtual/disable-spv175/paint/invalidation/multicol/multicol-repaint-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/linux/virtual/disable-spv175/paint/invalidation/multicol/multicol-with-inline-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/linux/virtual/disable-spv175/paint/invalidation/multicol/multicol-with-text-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac-mac10.12/paint/invalidation/multicol/multicol-repaint-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac-mac10.12/paint/invalidation/multicol/multicol-with-block-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac-mac10.12/paint/invalidation/multicol/multicol-with-inline-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac-mac10.12/paint/invalidation/multicol/multicol-with-text-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac/paint/invalidation/multicol/multicol-repaint-expected.txt
[add] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac/paint/invalidation/multicol/multicol-with-block-expected.txt
[add] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac/paint/invalidation/multicol/multicol-with-inline-expected.txt
[add] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/mac/paint/invalidation/multicol/multicol-with-text-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/WebKit/LayoutTests/platform/win/paint/invalidation/multicol/multicol-repaint-expected.txt
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/blink/renderer/core/paint/paint_property_tree_builder.cc
[modify] https://crrev.com/51c414eb1d6d6903afea0018367d787ff219989b/third_party/blink/renderer/core/paint/paint_property_tree_builder_test.cc

The change just made it into Chrome Canary channel on Android I guess. I updates and it really works great! The long LoremIpsum.html test file is instantly split into columns, no need to wait for several seconds until the columns are finally calculated and shown. And the touch to highlight sentences reacts in about 0.5 sec. on my Pixel 2 XL, previously it took over 5 seconds. Thank you very much for taking care of it! My faith in Chrome and this community is restored :)

Greg

Glad it worked well for you. The fix is in Chrome 68, which will reach the
stable channel in about 7 weeks.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/8bfde67eda6e02ab4e7a5abf603b95e53527f04f

commit 8bfde67eda6e02ab4e7a5abf603b95e53527f04f
Author: Morten Stenshorne <mstensho@chromium.org>
Date: Wed Aug 29 21:04:45 2018

[LayoutNG] Remove failure expectations for passing multicol tests.

TBR=cbiesinger@chromium.org, kojii@chromium.org

Bug: 591099, 635619,  797591 , 864156
Change-Id: Ibb3e27415a4b1e32055c9f2d156d3f36ca676085
Reviewed-on: https://chromium-review.googlesource.com/1194368
Reviewed-by: Morten Stenshorne <mstensho@chromium.org>
Commit-Queue: Morten Stenshorne <mstensho@chromium.org>
Cr-Commit-Position: refs/heads/master@{#587297}
[modify] https://crrev.com/8bfde67eda6e02ab4e7a5abf603b95e53527f04f/third_party/WebKit/LayoutTests/TestExpectations