When trying to write a perf test for bug 1288761, I found another performance issue in inline layout which is unrelated to performance of bidi resolution. See the attached testcase. Firefox spends >20s to render that testcase, while Chrome only spends 0.5s. This is a profile of this case: https://perfht.ml/2fKHKsA

Probably O(N^2) behavior as a result of calling nsBlockFrame::DoRemoveFrame multiple times, since nsBlockFrame::DoRemoveFrame does a scan of the lines that's O(N)?

Yeah, that's my guess as well. Majority of time is spent inside nsLineBox::Contains from nsBlockFrame::DoRemoveFrame. And the latter is called from nsBlockFrame::DeleteNextInFlowChild by nsLineLayout::ReflowFrame when a given inline frame completes its reflow and it has next-in-flow. And we have lots of next-in-flow seems to be because of scrollbar change (from no scrollbar initially to scrollbar). And indeed the page has a much better performance on Mac when using overlay scrollbar. So it feels like this have a O(# of lines * # of frames) complexity. There are two possible solutions: Record all top level frame removal during reflowing block frame, and commit all of them in a one-off clean up at the end of nsBlockFrame::Reflow. This allows us to only scan all lines once, so that we don't have the O(n^2) complexity for this. Also we can probably try reflowing a page with scrollbar at top level first (rather than without), and fallback to no scrollbar when we find it's not necessary, since a large page tends to have scrollbar, and page without scrollbar is usually faster to reflow. This would allow us to avoid reflowing twice on relatively expensive pages with the cost of reflowing relatively cheap pages one more time. (The first one should be the real fix of this specific bug, but I guess we may also want to try the second one at some point?)