1838250 - High CPU usage and unresponsiveness on page with very long horizontal scroll

Status: RESOLVED FIXED

(Core :: Disability Access APIs, defect)

Description

[Matt Cosentino]

Attachment: logtest.html - data scrambled for privacy

User Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:109.0) Gecko/20100101 Firefox/116.0

Steps to reproduce:

I have a tool for viewing log files in the browser. Some of these log entry lines are very long and create a very long horizontal scroll. This has worked fine for a very long time, but in Firefox Nightly the page becomes unresponsive with high CPU usage. I get a spinner in the center of the page. Not part of my page, seems to be part of the browser. I've tested in troubleshooting mode to make sure it's not an extension problem, and I get the same thing. I have an old portable version of Firefox installed, version 109, and it works fine there. I've attached a copy of just a few log entries, under 1MB. I can view much larger files of many lines that aren't as long, so it's not a file size issue.

Comment 1

[Matt Cosentino]

I updated my Portable Firefox to the current 114 and the problem exists there too.

Comment 2

[BugBot [:suhaib / :marco/ :calixte]]

The Bugbug bot thinks this bug should belong to the 'Core::Disability Access APIs' component, and is moving the bug to that component. Please correct in case you think the bot is wrong.

Comment 3

[Emilio Cobos Álvarez (:emilio)]

Can't repro this off hand. Can you share a profile as per these instructions?

Comment 4

[Matt Cosentino]

Here is my profile: https://share.firefox.dev/3Cwn7ec

Comment 5

[Emilio Cobos Álvarez (:emilio)]

Thanks! I can reproduce if I force-enable a11y. Matt, are you using a screen reader? If not, can you attach your about:support data? Most users shouldn't have the a11y engine activated, so I wonder if what enabled it for you is an a11y tool or we somehow enabled it without needing it.

Jamie, Morgan, is this kind of issue known with CTW? Do we really need to know every single character rect for a bunch of actually-invisible text?

---

The Performance Impact Calculator has determined this bug's performance impact to be low. If you'd like to request re-triage, you can reset the Performance Impact flag to "?" or needinfo the triage sheriff.

Impact on site: Renders site effectively unusable
Configuration: Rare
Page load impact: Severe
Websites affected: Rare
[x] Causes severe resource usage
[x] Able to reproduce locally
[x] Bug affects multiple sites

Comment 6

[Morgan Reschenberg [:morgan]]

(In reply to Emilio Cobos Álvarez (:emilio) from comment #5)

Thanks! I can reproduce if I force-enable a11y. Matt, are you using a screen reader? If not, can you attach your about:support data? Most users shouldn't have the a11y engine activated, so I wonder if what enabled it for you is an a11y tool or we somehow enabled it without needing it.

Jamie, Morgan, is this kind of issue known with CTW? Do we really need to know every single character rect for a bunch of actually-invisible text?

This isn't a known issue, AFAIK.
By "invisible" do you mean offscreen? Inspecting the page, I'm not seeing hidden text just the long log lines

:Jamie is it possible to request char/text bounds on an offscreen leaf directly? Or does the leaf first have to become onscreen/be scrolled to?
I guess we could avoid pushing char rects here for offscreen chars, and then push a CacheDomain::Text update for text leaves we encounter when building the viewport cache.

What else is this info used for? I know we rely on char bounds for TextLeafPoint::ContainsPoint which gets used in OffsetAtPoint, but in theory that should only be used for hittesting items that are already on screen. It looks like ATK has calls for char extents and text bounds, but I'm not sure how they're used.

Comment 7

[James Teh [:Jamie]]

(In reply to Morgan Reschenberg [:morgan] from comment #6)

:Jamie is it possible to request char/text bounds on an offscreen leaf directly? Or does the leaf first have to become onscreen/be scrolled to?

It's certainly possible. As to whether anyone actually does it, NVDA doesn't and I doubt Orca or VoiceOver do. However, I'm not sure about JAWS; it tends to do some interesting stuff when building its buffer. I doubt any coords it retrieves from offscreen text would be particularly useful, though, so it's probably okay to not support this.

I guess we could avoid pushing char rects here for offscreen chars, and then push a CacheDomain::Text update for text leaves we encounter when building the viewport cache.

That's an interesting idea. On one hand, it would mean the coords would take longer to be available after scrolling. On the other hand, hit testing wouldn't work until the viewport cache arrives anyway, so clients wouldn't be able to get any useful info before that point. We'd need to make sure we fail gracefully when trying to retrieve offsets for a point which isn't in the cache. Also, I think we'd want to avoid pushing the text string or line offsets in this case, as those haven't changed unless the acc's relative bounds changed.

What else is this info used for? I know we rely on char bounds for TextLeafPoint::ContainsPoint which gets used in OffsetAtPoint, but in theory that should only be used for hittesting items that are already on screen. It looks like ATK has calls for char extents and text bounds, but I'm not sure how they're used.

It's also used to route cursors to particular points on screen, but again, that's only useful if the acc is on screen.

The other thing that might help here (not necessarily mutually exclusive) is caching granularity, bug 1794974. Assuming the client isn't ever asking for bounds (we have no evidence either way, but we can hope not), we don't need to cache them.

Comment 8

[James Teh [:Jamie]]

So I'm not entirely convinced that this is just due to caching a lot of character bounds alone. For one, this seems to be fine with Chromium and I'm pretty sure it too caches all the things. Second, Gecko a11y has loaded much larger documents than this without anywhere near the performance degradation we're seeing here.

Also, skipping offscreen Accessibles wouldn't skip the (large) parts of visible lines that are horizontally scrolled off screen. It would only skip lines that aren't visible at all. That's a partial optimisation, but if I understand correctly, there are only really a few "lines" in this sample, so it must be the long lines causing the problem. So, as soon as one of these long lines scrolls on screen, we'd hit this problem again.

Comment 9

[James Teh [:Jamie]]

Distilled test case, 1 million characters in a single text node:
data:text/html,<p>before</p><p id="p"></p><p>after</p><script> let t = ""; for (let i = 0; i < 1000000; ++i) t += "a"; p.textContent = t; </script>
This hangs badly. To work around this in a11y, we'd need to somehow only fetch the rects for the visible characters. I'm not quite sure how we'd do that.

Another test case, 1 million characters evenly split across 1 thousand text nodes:
data:text/html,<p>before</p><p id="p"></p><p>after</p><script> let t= ""; for (let i = 0; i < 1000; ++i) t += "a"; for (let i = 0; i < 1000; ++i) p.append(document.createTextNode(t)); </script>
Curiously, this doesn't hang at all. We fetch just as many rects, but across multiple nodes. Why does fetching character rects degrade so badly with many characters in a single node?

Comment 10

[James Teh [:Jamie]]

(In reply to James Teh [:Jamie] from comment #9)

To work around this in a11y, we'd need to somehow only fetch the rects for the visible characters.

That means we'd need to find the first and last visible offsets. But I worry calculating that information would be just as expensive as getting all the character rects, unless there's a fast path for that?

Comment 11

[James Teh [:Jamie]]

Also, we won't get viewport cache updates when scrolling horizontally in this case because the text node is always at least partially on screen. So we'd have to send cache updates for every text leaf within a scrollable area every time it scrolls. That isn't really feasible.

Comment 12

[Matt Cosentino]

So I checked and accessibility is activated, but the instantiator is unknown. This actually isn't the first time I've reported a bug and it's been caused by accessibility. https://bugzilla.mozilla.org/show_bug.cgi?id=1800028 Possible it is related to something on my HP laptop. I force disabled it back then to fix that problem, somehow that setting got reset. I can confirm that force disabling it again fixes this problem.

Comment 13

[Patricia Lawless]

setting Performance Impact (per comment 5)

Comment 15

[James Teh [:Jamie]]

I dug into this a bit further.

1. A11y calls GetCharacterRectsInRange, requesting all characters.
2. That calls nsTextFrame::GetPointFromIterator for each character. The range always gets a start of 0, but the end is the offset of the character we're currently querying; i.e. it increments by 1 from 0 to the end of the text.
3. Eventually, we call gfxTextRun::GetAdvanceForGlyphs. That walks from the start of the range to the end, calling GetAdvanceForGlyph for each offset.
4. Since the start of the range is always 0, we walk from the start of the text run here for every character, even though we've already calculated the rects for previous characters! So, we end up with O(n^2) instead of just O(n).

:jfkthame, are you able to help here? I don't really understand why we walk the entire text run before the character for each character. Can we cache the advance width in the iterator or similar? Or is there some way I can optimise this in the a11y code?

Comment 16

[James Teh [:Jamie]]

(In reply to James Teh [:Jamie] from comment #15)

4. Since the start of the range is always 0, we walk from the start of the text run here for every character, even though we've already calculated the rects for previous characters!

Uh... no, I'm wrong. Sorry. The range does get collapsed to one character by ShrinkToLigatureBoundaries. But that does still leave me at square 0 with the question of why this gets slower the longer the text run is.

Update: No, it seems GetAdvanceForGlyphs frequently gets called with a range starting at 0 and ending at the offset in question. I haven't worked out why yet.

Comment 17

[Jonathan Kew [:jfkthame]]

It looks to me like the GetPointFromIterator call here may be a problem, because if I'm reading the code right, it will always measure from the start of the frame to the current iterator position, which for a long frame will get increasingly slow.

We should refactor things so that GetCharacterRectsInRange can iterate over the text once, keeping track of position as it goes, instead of re-measuring the position from the origin for every character.

Comment 18

[Jonathan Kew [:jfkthame]]

Attachment: Bug 1838250 - Avoid O(n^2) behavior in nsTextFrame::GetCharacterRectsInRange. r=#layout-reviewers

Comment 19

[Jonathan Kew [:jfkthame]]

Something like this ought to help (not yet properly tested, though....)

Comment 20

[Jonathan Kew [:jfkthame]]

Try run: https://treeherder.mozilla.org/jobs?repo=try&revision=5a8ecff3d4cacdf3e49ad286ca3eed313d8c1213

Comment 21

[James Teh [:Jamie]]

(In reply to Jonathan Kew [:jfkthame] from comment #19)

Something like this ought to help (not yet properly tested, though....)

This makes the test case in comment 9, as well as the original test case in comment 0, almost instantaneous with accessibility. Thanks.

Comment 22

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/80b5d73986d6
Avoid O(n^2) behavior in nsTextFrame::GetCharacterRectsInRange. r=emilio

Comment 23

[Narcis Beleuzu [:NarcisB]]

https://hg.mozilla.org/mozilla-central/rev/80b5d73986d6