74328 - O(n^2) algorithm in nsHTMLDocument::ContentAppended

Status: VERIFIED FIXED

(Core :: Layout, defect)

Description

[Daniel Bratell]

As in bug 74319 there is a O(n^2) algorithm in nsHTMLDocument::ContentAppended 
that can easily be removed with the same method as there.

In this case it is RegisterNamedItems that is called 1.5 million times taking 
19% of the time (after the fix for bug 74319). I don't know if all that time can 
be reclaimed, but it probably can since all the time (almost) seems to be spent 
in function call overhead.

Comment 1

[Daniel Bratell]

Attachment: Fix to make the algorithm O(n)

Comment 2

[Daniel Bratell]

I've attached a fix of the same type as in bug 74319. (Why do error handling 
always make code ugly. :-( )

Comment 3

[Chris Waterson]

Make the code resilient: don't break out of the loop if RegisterNamedItems()
fails. Do that & r=waterson

cc'ing jst, who should sr= this patch.

Comment 4

[Johnny Stenback (:jst)]

What waterson said, please attach a new patch and I'll sr

Great catch, Daniel!

Comment 5

[Daniel Bratell]

Attachment: Updated patch

Comment 6

[Daniel Bratell]

New patch attached. 

I did the layout regression tests and though I got a bunch of frame state 
differences in SliderFrames I didn't see any difference when looking at the 
pages in viewer. So, jst, is this ready for checkin? 

Comment 7

[Johnny Stenback (:jst)]

Oops, I should've caught this earlier, this patch will cause a huge memory leak :-)

+    nsIContent *newChild;
+    aContainer->ChildAt(i, newChild);

'newChild' needs to be Releas'ed in this loop since ChildAt() addrefs it.
Ideally you'd make 'newChild' a 'nsCOMPtr<nsIContent> newChild' and call
ChildAt(i, *getter_AddRefs(newChild));', and 'newChild' should be defined
outside the loop.

Code style nits:

+  PRInt32 count; aContainer->ChildCount(count);

Split this onto separate lines, we're not trying to save code lines here.

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

Declare 'i' outside the loop statement, just in case someone tries to use it
later on outside the loop.

+    (void)RegisterNamedItems(newChild);

Skip the "(void)", it only makes the code less readable.

   }
-
+  
 ^^

Don't add those two spaces.

Make those changes and attach new patch, sorry to make you do this many
iterations, if it wasn't for the leak...

Comment 8

[Daniel Bratell]

Attachment: Patch mk3. Now even better!

Comment 9

[Daniel Bratell]

Thanks Johnny! I guess I really love these reviews right now. :-) It would have 
been quite bad checking it in with that bug (more like a bad alien monster). 

The new patch addresses jst's concerns and 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.

Can I get a r and sr. Waterson? jst?

Comment 10

[Chris Waterson]

FWIW, I'd have written it like this:

  PRInt32 count = 0;
  aContainer->ChildCount(count);

  for (PRInt32 i = 0; i < count; ++i) {
    nsCOMPtr<nsIContent> newChild;
    aContainer->ChildAt(i, *getter_AddRefs(newChild));
    NS_ASSERTION(newChild != nsnull, "Got a null child!");
    if (newChild)
      RegisterNamedItems(newChild);
  }

(This is C++, so you can declare variables more closely to where they are used, 
as well as declare them within `for'. Also, positive logic `if (newChild)' a 
little bit more understandable -- to me -- than the negative plus continue. 
But, these are nits, your code is equivalent, and jst is the module owner, so 
take 'em or leave 'em.)

Regardless, I think you should initialize `count' to zero if for some bizarre 
reason nsIContent::ChildCount() fails.

Do that, and r/sr=waterson, whichever helps.

Comment 11

[Daniel Bratell]

Style is difficult. You and jst are saying the exact opposite things and I get 
somewhat confused. 

I'll initialize count to 0, but leave the nscomptr outside which I think might 
be a little more efficient (depending on the implementation). I leave the 
declaration of i outside the loop too, since I have been bitten by different 
compilers doing different things when declaring it in the for. 

I'll move the code around a little and the new code will be:

  PRInt32 count=0;
  aContainer->ChildCount(count);

  PRInt32 i;
  nsCOMPtr<nsIContent> newChild;
  for (i = aNewIndexInContainer; i < count; ++i) {
    aContainer->ChildAt(i, *getter_AddRefs(newChild));
    if (newChild) 
      RegisterNamedItems(newChild);
  }

jst, is that fine with you? I only seems to be missing one or two letters now. 
:-)

Comment 12

[Johnny Stenback (:jst)]

Perfect! :-)

Yes, my reason for having the nsCOMPtr declared outside the loop is to avoid
calling the nsCOMPtr ctor and dtor for every iteration through the loop. Not a
big deal (we're probably talking about a few instructions per iteration here),
and maybe the compilers would optimize it away, who knows, it just "looks"
faster with the nsCOMPtr outside the loop :-)

With your above suggestion, sr/r=jst.

Check it in! And thanks for fixing this!

Comment 13

[Chris Waterson]

Daniel: puh-leeze check this in. Do you have CVS access? If not, let me know and
I'll check it in for you. This is related to bug 56854.

Comment 14

[Daniel Bratell]

Fix checked in. I have had trouble finding a time when the tree is open and I am 
home and awake. It's like really early in the morning here now.

Comment 15

[Chris Petersen]

Marking verified per last comments.

Comment 16

[Mehmet D. AKIN]

Well, will anybody "Close" this bug? it's been fixed 10 months ago.

Comment 17

[Daniel Bratell]

This bug is as "closed" as it gets. bugzilla.mozilla.org doesn't (yet) use the 
CLOSED state of Bugzilla if that what youre referring to.