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

VERIFIED FIXED in mozilla0.9

Status

()

Core
Layout
VERIFIED FIXED
17 years ago
16 years ago

People

(Reporter: Daniel Bratell, Assigned: Daniel Bratell)

Tracking

(Blocks: 1 bug, {perf})

Trunk
mozilla0.9
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: fix in hand waiting for r and sr, URL)

Attachments

(3 attachments)

(Assignee)

Description

17 years ago
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.
(Assignee)

Updated

17 years ago
Blocks: 54542
Status: NEW → ASSIGNED
Keywords: perf
(Assignee)

Comment 1

17 years ago
Created attachment 29438 [details] [diff] [review]
Fix to make the algorithm O(n)
(Assignee)

Comment 2

17 years ago
I've attached a fix of the same type as in bug 74319. (Why do error handling 
always make code ugly. :-( )
Keywords: mozilla0.9
(Assignee)

Updated

17 years ago
OS: Windows 2000 → All
Hardware: PC → All
Target Milestone: --- → mozilla0.9

Comment 3

17 years ago
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.
What waterson said, please attach a new patch and I'll sr

Great catch, Daniel!
(Assignee)

Comment 5

17 years ago
Created attachment 29575 [details] [diff] [review]
Updated patch
(Assignee)

Comment 6

17 years ago
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? 
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...
(Assignee)

Comment 8

17 years ago
Created attachment 29625 [details] [diff] [review]
Patch mk3. Now even better!
(Assignee)

Comment 9

17 years ago
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?
Keywords: patch
Whiteboard: fix in hand waiting for r and sr

Comment 10

17 years ago
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.
(Assignee)

Comment 11

17 years ago
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. 
:-)
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

17 years ago
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.
Blocks: 56854
(Assignee)

Comment 14

17 years ago
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.
Status: ASSIGNED → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → FIXED

Comment 15

17 years ago
Marking verified per last comments.
Status: RESOLVED → VERIFIED

Comment 16

16 years ago
Well, will anybody "Close" this bug? it's been fixed 10 months ago.
(Assignee)

Comment 17

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