Closed Bug 1369141 Opened 3 years ago Closed 3 years ago

Hit testing in large tables has become extremely slow

Categories

(Core :: Layout, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla55
Tracking Status
firefox-esr52 --- unaffected
firefox53 --- unaffected
firefox54 --- unaffected
firefox55 + fixed

People

(Reporter: mstange, Assigned: mtseng)

References

Details

(Keywords: perf, regression, Whiteboard: [qf:p1])

Attachments

(1 file, 2 obsolete files)

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?
Flags: needinfo?(mtseng)
Attached patch some basic dirty rect checking (obsolete) — Splinter Review
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.
Blocks: 1369125
[Tracking Requested - why for this release]: large performance regression when interacting with large tables
Bug 1367747 may also help because we create border display item unconditionally.
Flags: needinfo?(mtseng)
I mean, we create table border display item unconditionally now. If we fix it, the number of display item would greatly reduced.
Above comment was wrong. I found that the major overhead is in PaintRowGroupBackgroundByColIdx.
(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?
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
Attachment #8873332 - Flags: feedback?(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.
Attachment #8873332 - Flags: feedback?(mstange) → feedback+
Whiteboard: [qf] → [qf:p1]
Assignee: nobody → mtseng
Try looks good. Send review request again.

MozReview-Commit-ID: DoPptE60BD4
Attachment #8873689 - Flags: review?(mstange)
Attachment #8873182 - Attachment is obsolete: true
Attachment #8873332 - Attachment is obsolete: true
All the calls to GetNormalPosition() rather than GetPosition() make me worried that relative positioning will be broken.
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.
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.
Attachment #8873689 - Flags: review?(mstange) → review+
Pushed by mtseng@mozilla.com:
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
https://hg.mozilla.org/mozilla-central/rev/9d55c2ccf868
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Duplicate of this bug: 1369125
You need to log in before you can comment on or make changes to this bug.