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.
Also, the nsVoidArray would probably be better as an nsAutoVoidArray, but it's not very important.
Hmm, I didn't even know there was such a class in mozilla, over to adam lock whose name is all over that file.
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
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.
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
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.
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.
Created attachment 45824 [details] [diff] [review] Patch makes stack recursion less new/delete heavy by reusing popped elements.
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 → ---
Looks much better in terms of allocation. Total peak memory use should be the same. firstname.lastname@example.org (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
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
Fix is checked in
Status: REOPENED → RESOLVED
Last Resolved: 17 years ago → 17 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.