92534 - nsDOMWalker allocates and frees too much

Status: RESOLVED FIXED

(Core :: DOM: Core & HTML, defect)

Description

[Randell Jesup [:jesup] (needinfo me)]

Found by inspection:  nsDOMWalker.cpp allocates and frees DOMTreePos objects far
more than it needs to do in order to traverse a tree.  It does one allocation
and one free (minimum) plus an AddRef and Release (and
AppendElement/RemoveElementAt) for every node in the DOM tree it's walking.

I'll develop a patch for this.

Comment 1

[Randell Jesup [:jesup] (needinfo me)]

Also, the nsVoidArray would probably be better as an nsAutoVoidArray, but it's
not very important.

Comment 2

[Johnny Stenback (:jst)]

Hmm, I didn't even know there was such a class in mozilla, over to adam lock
whose name is all over that file.

Comment 3

[Adam Lock]

I will make this part of the bug 77909 work.

I can see that there is a slight inefficiency in that a DOMTreePos can be
deleted and then recreated in some circumstances during traversal. Is that what
you're referring to?

http://lxr.mozilla.org/seamonkey/source/embedding/browser/webBrowser/nsDOMWalker.cpp#55
http://lxr.mozilla.org/seamonkey/source/embedding/browser/webBrowser/nsDOMWalker.cpp#81

Comment 4

[Randell Jesup [:jesup] (needinfo me)]

That's mostly it.  It deletes and then recreates any entry with children.  I'm
also somewhat inconvinced this is the best algorithm (with heavy reliance on
new/delete), however that wasn't what the bug was about directly.

Comment 5

[Adam Lock]

Folding this work into bug 77909.

I will definitely use nsAutoVoidArray but I am more dubious about spending an
hour reworking the code just to save a few addrefs and a new/delete. 

*** This bug has been marked as a duplicate of 77909 ***

Comment 6

[Randell Jesup [:jesup] (needinfo me)]

Well, we'd be saving those addrefs and far more importantly the new/delete for
every node in the DOM.  N thousand new's/deletes really do add up (if for no
other reason than the thread locks that are required).  In any case, it was just
a note about the issue.  Bug 31770 is another instance of a content iterator
that was causing problems just because it called IndexOf() on every Next()
method.  IndexOf() is far less expensive than new/delete.

Comment 7

[Adam Lock]

The potential of an unnecessary new and delete only occurs for the first
iteration of the " while (current)" loop and only then when the node has
children. So it doesn't happen every time.

I think to catch just these instances would make a mess of the loop. Instead it
might be possible to change how I add and remove items from the array to make it
more efficient. For example, by not calling RemoveElementAt/delete to pop an
item and decrementing a stack size counter instead. Then when something is
pushed on the stack the pointer at that index can then be reused and the counter
increased instead of needing a new/AppendElement.
I will investigate.

Comment 8

[Adam Lock]

Attachment: Patch makes stack recursion less new/delete heavy by reusing popped elements.

Comment 9

[Adam Lock]

I'll reopen this bug since I have a not too objectionable way to make the
recursion less allocation intensive. The new version doesn't remove elements
once they're added to the array, instead they get reused if the stack size is
smaller than the array.

Can I have a review on this please?

Comment 10

[Randell Jesup [:jesup] (needinfo me)]

Looks much better in terms of allocation.  Total peak memory use should be the
same.  r=[e-mail] (if I can)

Comment 11

[Christopher Blizzard (:blizzard)]

-        DOMTreePos *pos = (DOMTreePos *) stack.ElementAt(stack.Count() - 1);

What ever happened to NS_STATIC_CAST()?  You aren't using that at all in this
patch.  Fix those and you've got an sr=blizzard

Comment 12

[Adam Lock]

Attachment: NS_STATIC_CAST's instead of C style casts. This version will be checked in when the tree is opened

Comment 13

[Adam Lock]

Fix is checked in