Make removing normal flow child frames in block frames faster (DoRemoveFrame)

NEW
Assigned to

Status

()

--
major
7 years ago
5 years ago

People

(Reporter: mats, Assigned: mats)

Tracking

(Blocks: 2 bugs, {perf})

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

(Assignee)

Description

7 years ago
DoRemoveFrame is slow because it needs to find the line the child frame
is on, which is a linear search, O(n) on the number of normal flow child
frames in the block.  Bug 726637 shows the problem with View Source on
a very large page that has much of the content on the same line (about 60%
of the time is in nsLineBox::IndexOf, all from DoRemoveFrame).
(Assignee)

Comment 1

7 years ago
Created attachment 597820 [details] [diff] [review]
Setup and use the line cursor

This is a somewhat scary patch that makes use of the line cursor property
to point out the last inline line that we started reflowing, and then use
that as the starting point for the search.  It fixes the DoRemoveFrame
part of bug 726637 completely.
(Assignee)

Comment 2

7 years ago
I'm going to try a less intrusive and safer approach next -- search the last few
lines (in reverse) first and then do the normal forward search...
I'll try to get some stats of where we find the frame also.
(Assignee)

Comment 4

7 years ago
Created attachment 598414 [details] [diff] [review]
Some statistics on DoRemoveFrame

Without the line cursor, the target line is usually near the start of the
block, with sloping numbers.  If the block is in reflow, the first line
is rarely hit, instead the slope starts from the second line.

The View Source testcase in bug 726637 stands out with high numbers for
lines in the middle of the block (not first/last 19 lines).

The line cursor patch changes the numbers so that pretty much all frames
are found on the next line after the cursor, in fact it's close to 100%
at first-frame-at-next-line, which makes sense.  There were no cases
where the frame was on a line *before* the line cursor.
The more reflow intensive, the higher chance there is a line cursor
available, which also makes sense since I set up the cursor just before
starting reflowing an inline line.

I don't see a simpler approach than using a line cursor, without
redesigning the data structures involved.

Updated

5 years ago
Keywords: perf
You need to log in before you can comment on or make changes to this bug.