Last Comment Bug 712743 - Investigate if we could reduce traversing by checking if node is black
: Investigate if we could reduce traversing by checking if node is black
Product: Core
Classification: Components
Component: DOM (show other bugs)
: 10 Branch
: All All
: -- normal (vote)
: mozilla12
Assigned To: Olli Pettay [:smaug]
Depends on:
  Show dependency treegraph
Reported: 2011-12-21 12:39 PST by Olli Pettay [:smaug]
Modified: 2012-02-01 13:27 PST (History)
9 users (show)
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---

WIP (2.25 KB, patch)
2011-12-21 14:18 PST, Olli Pettay [:smaug]
no flags Details | Diff | Splinter Review
no child nodes check (1.99 KB, patch)
2011-12-21 15:00 PST, Olli Pettay [:smaug]
continuation: review+
Details | Diff | Splinter Review
v3 (2.06 KB, patch)
2011-12-22 15:26 PST, Olli Pettay [:smaug]
jonas: review+
Details | Diff | Splinter Review
v4 (2.01 KB, patch)
2011-12-22 16:13 PST, Olli Pettay [:smaug]
christian: approval‑mozilla‑aurora+
christian: approval‑mozilla‑beta+
Details | Diff | Splinter Review

Description Olli Pettay [:smaug] 2011-12-21 12:39:36 PST

Comment 1 Olli Pettay [:smaug] 2011-12-21 14:18:32 PST
Created attachment 583627 [details] [diff] [review]

Pushing this to try.
IsBlackNode(tmp) and IsBlackNode(parent) seem to catch some cases,
child list check not so often. Though, it really depends on testcases.
Comment 2 Olli Pettay [:smaug] 2011-12-21 14:21:43 PST
Comment 3 Olli Pettay [:smaug] 2011-12-21 14:35:01 PST
I think the child nodes check is triggered so rarely and it can slow down
blackness checking significantly so it should be probably removed.

But XHR could have blackness check to prevent document traversing
Comment 4 Olli Pettay [:smaug] 2011-12-21 15:00:45 PST
Created attachment 583642 [details] [diff] [review]
no child nodes check

XHR blackness check didn't seem to be too useful.
Comment 5 Olli Pettay [:smaug] 2011-12-21 16:26:17 PST
With the latter patch I don't get high cc times with
Comment 6 Olli Pettay [:smaug] 2011-12-21 16:27:53 PST
But haven't got test results yet.

The patch applies cleanly to beta, so I pushed to try
Comment 7 Olli Pettay [:smaug] 2011-12-21 17:10:17 PST
And to clarify, this is something I'm thinking for FF10 (and maybe FF11). 
Bug 705582 is way more effective, but also a lot more riskier.
Comment 8 Olli Pettay [:smaug] 2011-12-21 17:27:45 PST
Comment on attachment 583642 [details] [diff] [review]
no child nodes check

s/in black document/in a black document/

So, perhaps we should try this. And if we want to land something to
FF10, it must happen real soon (first to trunk ofc)

This patch should be reasonable safe (hopefully it even passes tests :) ).
I tried to leave out anon content, since those are anyway usually only in
in-cc-generation documents, and who owns what is trickier with
anon content.

The idea with the patch is that although some parts of a dom tree can be traversed,
once there is something black, we stop. That will hopefully cut down
graph size significantly at least in many cases. Pathological cases are still
possible (like they are with weak parent nodes).
Comment 9 Olli Pettay [:smaug] 2011-12-21 18:00:09 PST
To clarify, non-native anon nodes somewhere inside non-native anon content can be handled, since
those are kind of just normal subtrees, but the boundaries of anon and normal content are tricky, 
and the flags should prevent the problematic cases.
Comment 10 Andrew McCreight [:mccr8] 2011-12-21 18:18:48 PST
Comment on attachment 583642 [details] [diff] [review]
no child nodes check

Review of attachment 583642 [details] [diff] [review]:

Looks good to me.  I don't really understand the problematicFlags stuff, so you should get somebody else to look at that.  It looked reasonable to me, and the other flags didn't seem like something to anything to worry about. r=me with that.

::: content/base/src/nsGenericElement.cpp
@@ +1246,5 @@
> +
> +      // If we're not in anonymous content and we have a black parent,
> +      // return early.
> +      nsIContent* parent = tmp->GetParent();
> +      if (parent && !IsXBL(parent) && !parent->HasFlag(problematicFlags) &&

Is there some reason you check IsXBL and HasFlag in a different order here than up above?
Comment 11 Olli Pettay [:smaug] 2011-12-21 18:26:26 PST
(In reply to Andrew McCreight [:mccr8] from comment #10)
> Is there some reason you check IsXBL and HasFlag in a different order here
> than up above?
No. I'll fix that.
Comment 12 Olli Pettay [:smaug] 2011-12-21 18:27:49 PST
And btw, the IsXBL thing is there so that we don't check the odd <content> element which
binding keeps alive, but which isn't really in document.
Comment 13 Olli Pettay [:smaug] 2011-12-21 18:28:39 PST
...well among other reasons. XBL elements don't usually have script objects, so checking
blackness doesn't make much sense.
Comment 14 Andrew McCreight [:mccr8] 2011-12-21 18:33:56 PST
Yeah, it seems reasonable to me to skip them.
Comment 15 Jonas Sicking (:sicking) PTO Until July 5th 2011-12-22 11:44:59 PST
Why do we need the problematic-flags check? Especially, why do we need to check the problematic flags if the node itself (rather than its document/parent) has a wrapper which is colored black?
Comment 16 Olli Pettay [:smaug] 2011-12-22 11:52:55 PST
Yeah, I started think that myself last night. We probably don't need to check.
Comment 17 Olli Pettay [:smaug] 2011-12-22 11:53:18 PST
We certainly do need to check parent though.
Comment 18 Olli Pettay [:smaug] 2011-12-22 12:05:10 PST
(In reply to Jonas Sicking (:sicking) from comment #15)
> Why do we need the problematic-flags check? Especially, why do we need to
> check the problematic flags if the node itself (rather than its
> document/parent) has a wrapper which is colored black?
Er, of course. If element is somewhere in anon content, document doesn't own it.
Comment 19 Olli Pettay [:smaug] 2011-12-22 12:06:27 PST
So, I prefer keeping as it is. It is just simpler and safer, and it shouldn't matter much, since
elements which are in anon content are almost always in in-cc-generation documents.
Comment 20 Jonas Sicking (:sicking) PTO Until July 5th 2011-12-22 13:55:45 PST
But if the element's wrapper is black, then someone clearly is holding onto the wrapper itself and the element isn't collectable. Removing that check seems to only remove code here, so I'm not fully getting the simpler argument.
Comment 21 Olli Pettay [:smaug] 2011-12-22 13:58:47 PST
It is not removing any code. Need to then check if node is "problematic" before checking whether
current document is black.

But  I can do that change if really wanted. I just don't see the point, since "problematic"
nodes really should be usually in a cc-generation document
Comment 22 Jonas Sicking (:sicking) PTO Until July 5th 2011-12-22 14:21:54 PST
Ah, well, it's not less code, it's basically the same amount though. So yes, I definitely think it's worth bailing any time the current node is black.

I'm also not sure why you need all of the flags that you are checking for here. All you're trying to do is to check for nodes that are anonymous, right? NODE_MAY_BE_IN_BINDING_MNGR and NODE_IS_INSERTION_PARENT definitely seems wrong for that. I would have thought that NODE_IS_IN_ANONYMOUS_SUBTREE is enough but I'd have to look it up.
Comment 23 Olli Pettay [:smaug] 2011-12-22 14:36:43 PST
NODE_MAY_BE_IN_BINDING_MNGR is definitely needed. The parent must not have a binding.
Using GetBindin() or such would be slow.
Comment 24 Olli Pettay [:smaug] 2011-12-22 14:37:43 PST
And again, I'd rather be safe for FF10 (if this could land there).
Comment 25 Olli Pettay [:smaug] 2011-12-22 14:39:10 PST
And... we don't have any good bits to check if something is in anon content (either native anon
or normal anon). GetBindingParent is easy way to check that, but it is possibly slow (virtual).
Comment 26 Jonas Sicking (:sicking) PTO Until July 5th 2011-12-22 14:54:55 PST
Why do we care if the parent has a binding if the node itself isn't in anonymous content?

I guess keeping all the flags are ok with me for now, but please remove the flags-check on the node itself. We should always bail if the node's wrapper is black.
Comment 27 Olli Pettay [:smaug] 2011-12-22 14:57:00 PST
Ah that case. We'll you just wanted to not check whether node is in anon content ;)
Comment 28 Olli Pettay [:smaug] 2011-12-22 15:26:25 PST
Created attachment 583950 [details] [diff] [review]
Comment 29 Olli Pettay [:smaug] 2011-12-22 15:33:33 PST
Comment 30 Jonas Sicking (:sicking) PTO Until July 5th 2011-12-22 15:47:25 PST
Comment on attachment 583950 [details] [diff] [review]

It's still more confusing than safe to me to be checking the flags on the parent.

But I can live with this I guess.
Comment 31 Jonas Sicking (:sicking) PTO Until July 5th 2011-12-22 15:48:07 PST
But please comment better on why you are checking those flags. I.e. something about that we want to make sure that the parent actually owns the child.
Comment 32 Olli Pettay [:smaug] 2011-12-22 16:13:47 PST
Created attachment 583960 [details] [diff] [review]

Even simpler. if this passes on try, I'll push this.
Comment 33 Olli Pettay [:smaug] 2011-12-23 15:52:09 PST
Comment 34 Olli Pettay [:smaug] 2011-12-29 06:22:41 PST
Comment on attachment 583960 [details] [diff] [review]

[Approval Request Comment]
Regression caused by (bug #): N/A 
Something in FF10 has regressed CC times, but I don't know what.

User impact if declined: N/A

Testing completed (on m-c, etc.):
Landed to m-c a week ago, and few devs have
tested tryserver builds (beta/FF10) and comments have been positive.
CC times have gone down a bit.

Risk to taking this patch (and alternatives if risky):
Risk is to find some bizarre bug which causes the black-ness check to
to be true too often. That could lead to leaks.
Comment 35 christian 2011-12-29 09:53:15 PST
Comment on attachment 583960 [details] [diff] [review]

[triage comment]
Approved for aurora and beta. If any issues are found we will back it out.
Comment 37 Anthony Hughes (:ashughes) [GFX][QA][Mentor] 2012-01-05 11:23:33 PST
Is there something QA can verify here?
Comment 38 Anthony Hughes (:ashughes) [GFX][QA][Mentor] 2012-02-01 12:55:01 PST
(In reply to Anthony Hughes, Mozilla QA (irc: ashughes) from comment #37)
> Is there something QA can verify here?

Comment 39 Andrew McCreight [:mccr8] 2012-02-01 13:26:48 PST

Note You need to log in before you can comment on or make changes to this bug.