1369141 - Hit testing in large tables has become extremely slow

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Markus Stange [:mstange]]

This is a regression from bug 929484.

Steps to reproduce:
 1. Go to https://hg.mozilla.org/releases/mozilla-beta/annotate/cf76e00dcd6f/layout/painting/FrameLayerBuilder.cpp and wait for it to load.
 2. Move your mouse around over the code on the page.
 3. Watch how the row highlight changes.

It's very janky.

Profile: https://perfht.ml/2rl2e0g

Are we maybe attempting to create display items for rows outside the dirty rect?

Comment 1

[Markus Stange [:mstange]]

Attachment: some basic dirty rect checking

This patch improves things by a fair amount but it's not enough.

Somebody needs to understand what this code wants to do and if there's a more straightforward way to do it. These nested loops certainly look like O(n^2) algorithms, possibly worse. We should have intersection tests as far outside as possible, e.g. check whether the row intersects before iterating over its cells. But for that we need to have a good understanding of the frame tree structure and of the way you can convert coordinates between the different frame types.

Comment 2

[Markus Stange [:mstange]]

[Tracking Requested - why for this release]: large performance regression when interacting with large tables

Comment 3

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

Bug 1367747 may also help because we create border display item unconditionally.

Comment 4

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

I mean, we create table border display item unconditionally now. If we fix it, the number of display item would greatly reduced.

Comment 5

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

Above comment was wrong. I found that the major overhead is in PaintRowGroupBackgroundByColIdx.

Comment 6

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

(In reply to Markus Stange [:mstange] from comment #1)
> Created attachment 8873182 [details] [diff] [review]
> some basic dirty rect checking
> 
> This patch improves things by a fair amount but it's not enough.
> 
> Somebody needs to understand what this code wants to do and if there's a
> more straightforward way to do it. These nested loops certainly look like
> O(n^2) algorithms, possibly worse. We should have intersection tests as far
> outside as possible, e.g. check whether the row intersects before iterating
> over its cells. But for that we need to have a good understanding of the
> frame tree structure and of the way you can convert coordinates between the
> different frame types.

The code simply want to draw the cell background which belong to specific column index. We don't have any api to query cell by column index. So I only query it by O(n^2) algorithm. Maybe we can move intersection tests to column frame instead?

Comment 7

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

Attachment: Add some basic dirty rect intersection checks so that we don't build unnecessary table part display items.

Markus, I do more aggressive check for intersection of aDirtyRect and table parts. In my local, performance seems much better. Can you try this patch to see if it helps? Thanks.

MozReview-Commit-ID: DoPptE60BD4

Comment 8

[Marcia Knous [:marcia]]

Tracking 55+ per comment 2.

Comment 9

[Markus Stange [:mstange]]

Comment on attachment 8873332 [details] [diff] [review]
Add some basic dirty rect intersection checks so that we don't build unnecessary table part display items.

Review of attachment 8873332 [details] [diff] [review]:
-----------------------------------------------------------------

This looks good!

If it passes tests, I think it should be good to go.

Comment 10

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

 https://treeherder.mozilla.org/#/jobs?repo=try&revision=64e46995aa7c65a5f519301767545a9036c761b5

Comment 11

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

Attachment: Add dirty rect intersection checks so that we don't build unnecessary table part display items.

Try looks good. Send review request again.

MozReview-Commit-ID: DoPptE60BD4

Comment 12

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

All the calls to GetNormalPosition() rather than GetPosition() make me worried that relative positioning will be broken.

Comment 13

[Morris Tseng [:mtseng] [:Morris] (Inactive)]

All this display item is for the case that cell is relative position but we need draw col, col group, row or row group background on normal position. So use GetNormalPosition() is ok. We should have test cases cover all relative position.

Comment 14

[Markus Stange [:mstange]]

I agree. I tested relative position before f+ing the patch, and indeed, all the table part types that we're touching here don't honor relative positioning. Only cells themselves do, and this patch does not affect how we build display items for cell backgrounds.

Comment 15

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/9d55c2ccf868
Add dirty rect intersection checks so that we don't build unnecessary table part display items. r=mstange

Comment 16

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/9d55c2ccf868