309111 - Finding the prevsibling on a content insertion can be costly

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Boris Zbarsky [:bzbarsky]]

This is one of the causes of bug 304598.  Basically, the prev sibling content
node is a text node, so we end up doing an O(N) walk looking for the right
prevsibiling frame on each insertion, making the whole thing O(N^2).

I'm going to see whether I can make this a little smarter...

Comment 1

[Boris Zbarsky [:bzbarsky]]

Ah, the real problem is not just that the prevsibling is a text node, but also
that the previous element before the text node has an inline frame (which is
therefore not in the frame map).  So we call into FindPrimaryFrameFor() with no
hint.

My first instinct is to make the hint-finding code keep going backwards till it
finds a hint instead of stopping at the first element.  In the absolute
worst-case scenario (lots of preceding siblings with no frames) this will be
slow, of course (about double the current time, probably).  But if we have any
previous sibling at all after the point halfway between us and and the beginning
of our parent that has a frame, this ought to be a win, I think....

I'm still trying to think of a way that I could make this into a binary search
or something somehow.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Bug 500882 made this problem go away (in the sense that we don't have to do this FindPrimaryFrameFor stuff anymore).