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).
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.
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.
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.
You need to log in before you can comment on or make changes to this bug.