nsDOMWalker allocates and frees too much

RESOLVED FIXED

Status

()

RESOLVED FIXED
17 years ago
17 years ago

People

(Reporter: jesup, Assigned: adamlock)

Tracking

({perf})

Trunk
x86
All
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

(Reporter)

Description

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

Comment 1

17 years ago
Also, the nsVoidArray would probably be better as an nsAutoVoidArray, but it's
not very important.
(Reporter)

Updated

17 years ago
Blocks: 92256

Updated

17 years ago
Assignee: jst → adamlock
Hmm, I didn't even know there was such a class in mozilla, over to adam lock
whose name is all over that file.

Updated

17 years ago
Keywords: perf
(Assignee)

Comment 3

17 years ago
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
Depends on: 77909
(Reporter)

Comment 4

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

Comment 5

17 years ago
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 ***
Status: NEW → RESOLVED
Last Resolved: 17 years ago
Resolution: --- → DUPLICATE
(Reporter)

Comment 6

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

Comment 7

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

Comment 8

17 years ago
Created attachment 45824 [details] [diff] [review]
Patch makes stack recursion less new/delete heavy by reusing popped elements.
(Assignee)

Comment 9

17 years ago
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?
Status: RESOLVED → REOPENED
Resolution: DUPLICATE → ---
(Reporter)

Comment 10

17 years ago
Looks much better in terms of allocation.  Total peak memory use should be the
same.  r=rjesup@wgate.com (if I can)
-        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
(Assignee)

Comment 12

17 years ago
Created attachment 46229 [details] [diff] [review]
NS_STATIC_CAST's instead of C style casts. This version will be checked in when the tree is opened
(Assignee)

Comment 13

17 years ago
Fix is checked in
Status: REOPENED → RESOLVED
Last Resolved: 17 years ago17 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.