74319 - RestoreFrame used in a O(n^2) way

Status: VERIFIED FIXED

(Core :: Layout, defect)

Description

[Daniel Bratell]

In nsPresShell::ContentAppended, RestoreFrame is used in a O(n^2) way. That 
hurts stuff like the big table stress case a lot (well, it's about 6% of the 
time).

For every time something is appended, the whole frame structure is traversed 
looking for something to do. It should only be necessary to do this on new 
frames.

Comment 1

[Daniel Bratell]

I have fix (structure suggested by waterson).

Comment 2

[Daniel Bratell]

Attachment: Fix to remove O(n^2) algorithm

Comment 3

[Daniel Bratell]

Can I get some comments on the fix (r and sr?). 

One question I have is all new frames are guaranteed to be found with this 
algorithm? Will all new frames be children of the container?

Comment 4

[Daniel Bratell]

For the black & white table it's a save of 17.5% of the time so it's an even 
bigger win when the style system isn't as abused as in the colour test case.

Comment 5

[Chris Waterson]

> One question I have is all new frames are guaranteed to be found with this 
> algorithm? Will all new frames be children of the container?

Adding hyatt to the cc list; do we need to worry about saved frame state for any
anonymous frames that might be created *between* aContainer and its children? I
think not, but verify.

I think the patch looks good; my only comments are stylistic...

+    for (PRInt32 i = aNewIndexInContainer; i < count; ++i) {
+      nsIFrame* frame;

Declare `frame' as near as possible to its first use, at [1] below.

+      nsIContent *newChild;
+      rv = aContainer->ChildAt(i, newChild);
+      if (!newChild) {
+        // We should never get here.
+        NS_ASSERTION(PR_FALSE, "Got a null child when restoring state!");

Use NS_ERROR(...) instead of NS_ASSERTION(PR_FALSE, ...).

+        continue;
+      }

[1] Declare `frame' here.

+      rv = GetPrimaryFrameFor(newChild, &frame);
+      if (NS_SUCCEEDED(rv) && nsnull != frame)
+        mFrameManager->RestoreFrameState(mPresContext, frame, mHistoryState);
+    }

This is a great catch! Be sure to give the layout regression tests a whirl.
r=waterson, but we should definitely get some feedback from hyatt here...

Comment 6

[Daniel Bratell]

I would be glad to do the layout regression tests. It's not like I'm know what 
I'm doing. :-)  How do I run them? 
I'll attach a cleaned up patch so you have something to look at during the time.

Comment 7

[Daniel Bratell]

Attachment: Cleaned up patch

Comment 8

[Daniel Bratell]

I've found one regression caused by this patch, but I don't understand it. When 
resizing http://mersenne.org/ips/accounts.html the password chars, "********", 
don't move with the field. The other text field works great so I'm inclined to 
believe it to be a bug in the password field code, that has to be fixed before 
landing this. 

Can anyone give me directions where to look or who to nag to get further?
Waterson?

Comment 9

[Daniel Bratell]

When I click in the (empty) password field the caret begins to blink among the 
"******" a little higher up on the page, but as soon as I write anything the 
stars and the caret moves to its proper position inside the field.

Comment 10

[David Hyatt]

No XBL problem here.  The frame tree has already been monkeyed with, so you can
walk it normally.

Comment 11

[Daniel Bratell]

I managed to reproduce the bug on http://mersenne.org/ips/accounts.html in a 
clean build so it wasn't my change. I'm still going through the layout tests and 
will continue that tonight. When I think that all fails are benign I will attach 
the updated patch. 

Btw, shouldn't someone from session history ok this? 

Comment 12

[Daniel Bratell]

Attachment: Patch mk3. Now even better.

Comment 13

[Daniel Bratell]

Then I will go for another round of reviews. The newly attached patch fixes the 
giant memory leak the previous one caused. Thanks to jst who saw it in bug 
74328. I have run the regression tests and the only differences I get is in 
the completely unpredictable image loaded flag which I blame on someone else.

Comment 14

[Chris Waterson]

r=waterson

Comment 15

[Marc Attinasi]

very nice! sr=attinasi

Comment 16

[Chris Waterson]

Daniel, please check this in. Let me know if you don't have CVS access, and I'll
check it in for you. This is related to bug 56854.

Comment 17

[Daniel Bratell]

Now it's in. I've been having time zone problems (you don't want to know how 
early in the morning it is here right now. :-) ).

Comment 18

[Chris Petersen]

Marking verified per last comments.