Rework object grouping to never produce huge grouper array

• Component: WebKit Misc.
• Status: RESOLVED FIXED

[anton muhin]

[v8] Do not put the same handle into several groups: that can easily lead to huge array of items to be grouped

[anton muhin]

The original problem: http://code.google.com/p/chromium/issues/detail?id=73441

[anton muhin]

Created attachment 84098 [details]
Patch

[anton muhin]

Guys, I would really appreciate any algorithmic advice as well.  I hope that typically we shouldn't have too many group ids (~100).

[anton muhin]

Comment on attachment 84098 [details]
Patch

Mads and Vitaly suggested to investigate some better approaches.  So I am cancelling request for review for now.

[anton muhin]

Created attachment 84775 [details]
Patch

[Early Warning System Bot]

Attachment 84775 [details] did not build on qt:
Build output: http://queues.webkit.org/results/8083780

[Collabora GTK+ EWS bot]

Attachment 84775 [details] did not build on gtk:
Build output: http://queues.webkit.org/results/8088549

[Darin Adler]

Comment on attachment 84775 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=84775&action=review

> Source/WebCore/css/CSSRuleList.h:56
> +    PassRefPtr<StyleList> styleList()

A getter that is not passing ownership should return a raw pointer, not a PassRefPtr.

[WebKit Review Bot]

Attachment 84775 [details] did not build on mac:
Build output: http://queues.webkit.org/results/8083919

[anton muhin]

Created attachment 84858 [details]
Patch

[anton muhin]

(In reply to comment #8)
> (From update of attachment 84775 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=84775&action=review
> 
> > Source/WebCore/css/CSSRuleList.h:56
> > +    PassRefPtr<StyleList> styleList()
> 
> A getter that is not passing ownership should return a raw pointer, not a PassRefPtr.

Thanks a lot, Darin, fixed.

[Vitaly Repeshko]

(In reply to comment #10)
> Created an attachment (id=84858) [details]
> Patch

Looks good. It's way clearer than what we had before.

>-    void startMap()
>-    {
>-        m_grouper.shrink(0);
>-    }
>+            // Alas, CSSProperty---it's a type of items behind CSSMutableStyleDeclaration---doesn't
>+            // have uplink to the parent (and thus could be potentionally shared between several
>+            // declarations), so we need to iterate over them.

The comment is a bit hard to parse. How about "The object group for a CSSMutableStyleDeclaration must contain all its items (CSSProperties) that have wrappers. Unfortunately, a CSSProperty object can be be shared by a few declarations and doesn't have a link to them. So we have to add the items by iterating the declaration objects." Ok, it sucks too, but please make it clearer.

>+        // Group by sorting by the group id.
>+        std::sort(m_grouper.begin(), m_grouper.end());
>+
>+        // FIXME Should probably work in iterators here, but indexes were easier for my simple mind.
>+        for (size_t i = 0; i < m_grouper.size(); ) {

I don't think we should keep this comment.

>+            Vector<v8::Persistent<v8::Value> > group;
>+            group.reserveCapacity(nextKeyIndex - i);
>+            for (; i < nextKeyIndex; ++i) {
>+                v8::Persistent<v8::Value> wrapper = m_grouper[i].wrapper();
>+                if (!wrapper.IsEmpty())
>+                    group.append(wrapper);

How can a wrapper be empty here? If there are valid cases when this might happen, please add a comment. Otherwise, add an assert.

>+        bool isSubclass(const WrapperTypeInfo* that) const
>+        {
>+            
>+            for (const WrapperTypeInfo* current = this; current; current = current->parentClass)
>+                if (current == that)
>+                    return true;

Style nit. The loop body is now two lines and so needs {}, doesn't it?

>+    StyleList* styleList()
>+    {
>+        return m_list.get();
>+    }

Could be a one-liner.

>+    Document* document()
>+    {
>+        return m_doc;
>+    }

Ditto.

[anton muhin]

Created attachment 85166 [details]
Patch

[anton muhin]

(In reply to comment #12)
> (In reply to comment #10)
> > Created an attachment (id=84858) [details] [details]
> > Patch
> 
> Looks good. It's way clearer than what we had before.

Thanks a lot, Vitaly.  Just in case, Vitaly knows a lot about v8/bindings, but cannot r+ it, so I'd appreciate another look from someone with r+ privileges.

> 
> >-    void startMap()
> >-    {
> >-        m_grouper.shrink(0);
> >-    }
> >+            // Alas, CSSProperty---it's a type of items behind CSSMutableStyleDeclaration---doesn't
> >+            // have uplink to the parent (and thus could be potentionally shared between several
> >+            // declarations), so we need to iterate over them.
> 
> The comment is a bit hard to parse. How about "The object group for a CSSMutableStyleDeclaration must contain all its items (CSSProperties) that have wrappers. Unfortunately, a CSSProperty object can be be shared by a few declarations and doesn't have a link to them. So we have to add the items by iterating the declaration objects." Ok, it sucks too, but please make it clearer.

Rephrased.  May you have another look?

> 
> >+        // Group by sorting by the group id.
> >+        std::sort(m_grouper.begin(), m_grouper.end());
> >+
> >+        // FIXME Should probably work in iterators here, but indexes were easier for my simple mind.
> >+        for (size_t i = 0; i < m_grouper.size(); ) {
> 
> I don't think we should keep this comment.

Done.

> 
> >+            Vector<v8::Persistent<v8::Value> > group;
> >+            group.reserveCapacity(nextKeyIndex - i);
> >+            for (; i < nextKeyIndex; ++i) {
> >+                v8::Persistent<v8::Value> wrapper = m_grouper[i].wrapper();
> >+                if (!wrapper.IsEmpty())
> >+                    group.append(wrapper);
> 
> How can a wrapper be empty here? If there are valid cases when this might happen, please add a comment. Otherwise, add an assert.

Let's keep it as is now.  I'll try to turn that into assert, but don't want to do it in this patch which I'd like to bring to M11.

> 
> >+        bool isSubclass(const WrapperTypeInfo* that) const
> >+        {
> >+            
> >+            for (const WrapperTypeInfo* current = this; current; current = current->parentClass)
> >+                if (current == that)
> >+                    return true;
> 
> Style nit. The loop body is now two lines and so needs {}, doesn't it?

Done, but webkit style checker is fine with both versions.

> 
> >+    StyleList* styleList()
> >+    {
> >+        return m_list.get();
> >+    }
> 
> Could be a one-liner.

Yep, but I am following the style in this file (see create methods above)

> 
> >+    Document* document()
> >+    {
> >+        return m_doc;
> >+    }
> 
> Ditto.

Ditto, right above this method there is swap method, so I am just following the style around.  But if you insist on making this one-liners, definitely I'll do that.

[Vitaly Repeshko]

(In reply to comment #14)
> (In reply to comment #12)
> > (In reply to comment #10)
> > > Created an attachment (id=84858) [details] [details] [details]
> > > Patch

As bug 55899 shows sharing CSSProperties is really bad. I did a small investigation and found out that these guys are not only shared but are cached (CSSPrimitiveValueCache) and so putting a property object into a set of groups is going to retain much more than we'd like. We should switch from using objects groups for them to creating hidden dependencies. Hidden dependencies are a bit nastier because they require allocation (and also require locating the right wrapper to hold them), but OTOH they don't create a two-way strong reference.

[anton muhin]

(In reply to comment #15)
> (In reply to comment #14)
> > (In reply to comment #12)
> > > (In reply to comment #10)
> > > > Created an attachment (id=84858) [details] [details] [details] [details]
> > > > Patch
> 
> As bug 55899 shows sharing CSSProperties is really bad. I did a small investigation and found out that these guys are not only shared but are cached (CSSPrimitiveValueCache) and so putting a property object into a set of groups is going to retain much more than we'd like. We should switch from using objects groups for them to creating hidden dependencies. Hidden dependencies are a bit nastier because they require allocation (and also require locating the right wrapper to hold them), but OTOH they don't create a two-way strong reference.

That's indeed a problem.  And correct solution is to have one way references, but I don't think hidden refs is the right approach.  I can implement necessary v8 stuff though (as we discussed yesterday) and then fix it the right way.

Right now I see three ways out: 1) keep this logic and reevaluate it if we meet in the wild huge retained trees due to shared CSSPrimitiveValue, 2) slightly alter the logic and ignore not dirty wrappers (that improves our chances to survive), 3) just omit this grouping---that makes one layout test fail, but it might be bearable for time being.

I am personally for 1) or 3), slightly more in favour of 1) as correctness trumps performance imho.

And of course we can first wait for proper v8 extension.

Thoughts?

[Vitaly Repeshko]

(In reply to comment #16)
> (In reply to comment #15)
> > (In reply to comment #14)
> > > (In reply to comment #12)
> > > > (In reply to comment #10)
> > > > > Created an attachment (id=84858) [details] [details] [details] [details] [details]
> > > > > Patch
> > 
> > As bug 55899 shows sharing CSSProperties is really bad. I did a small investigation and found out that these guys are not only shared but are cached (CSSPrimitiveValueCache) and so putting a property object into a set of groups is going to retain much more than we'd like. We should switch from using objects groups for them to creating hidden dependencies. Hidden dependencies are a bit nastier because they require allocation (and also require locating the right wrapper to hold them), but OTOH they don't create a two-way strong reference.
> 
> That's indeed a problem.  And correct solution is to have one way references, but I don't think hidden refs is the right approach.  I can implement necessary v8 stuff though (as we discussed yesterday) and then fix it the right way.
> 
> Right now I see three ways out: 1) keep this logic and reevaluate it if we meet in the wild huge retained trees due to shared CSSPrimitiveValue, 2) slightly alter the logic and ignore not dirty wrappers (that improves our chances to survive), 3) just omit this grouping---that makes one layout test fail, but it might be bearable for time being.
> 
> I am personally for 1) or 3), slightly more in favour of 1) as correctness trumps performance imho.
> 
> And of course we can first wait for proper v8 extension.
> 
> Thoughts?

1) and even 2) are still not entirely correct in the GC sense, because they cause us to retain too much and avoiding the issue is as non-obvious for web developers as it gets. I vote for 3). The only bad consequence is that it becomes possible to detect GC by adding custom properties to primitive values like "50px". Yet because these objects are shared in unspecified (AFAIK) ways there shouldn't be anything that relies on custom properties on these objects.

[Adam Barth]

Comment on attachment 85166 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=85166&action=review

I like the approach.  This stuff is very subtle, so I'm not 100% sure that this change is correct, but I don't see anything wrong with it.  Some very minor style nits below.

> Source/WebCore/bindings/scripts/CodeGeneratorV8.pm:1715
> +    # find the super descriptor

This should be a complete sentence that starts with a capital letter and ends with a period.

> Source/WebCore/bindings/scripts/CodeGeneratorV8.pm:1720
> +        if ($parent eq "EventTarget") { next; }

Each statement should be on its own line.

> Source/WebCore/bindings/v8/V8GCController.cpp:237
> +    if (root->isStyleSheet())
> +        if (Node* ownerNode = static_cast<StyleSheet*>(root)->ownerNode())
> +            return calculateGroupId(ownerNode);

We need { } around the body of this if block.

> Source/WebCore/bindings/v8/V8GCController.cpp:281
> +            // CSSProperty (type of items in mutable style declaration) doesn't have a pointer to
> +            // its parent. Therefore we cannot treat them like other objects---traverse up to the
> +            // root when visiting a wrapper---and need to put them into the group directly.

I see.  We still need to walk down for these.  Ok.

> Source/WebCore/bindings/v8/WrapperTypeInfo.h:67
> +            

This blank line is empty.

> Source/WebCore/css/CSSRuleList.h:59
> +    StyleList* styleList()
> +    {
> +        return m_list.get();
> +    }

You can just put this all on one line if you like.  Simple getters can be on one line to preserve vertical space.

> Source/WebCore/css/StyleSheetList.h:57
> +    Document* document()
> +    {
> +        return m_doc;
> +    }

Same here.

[anton muhin]

Created attachment 85499 [details]
Patch

[Adam Barth]

Comment on attachment 85499 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=85499&action=review

> Source/WebCore/bindings/v8/V8GCController.cpp:293
> +#if 0

Maybe you forgot to remove this line?

> Source/WebCore/css/CSSRuleList.h:59
> +    StyleList* styleList()
> +    {
> +        return m_list.get();
> +    }

This are still multi-line...

[anton muhin]

Adam, thanks a lot for comments.  Sorry for delay---it took some time to merge it with my previous change due to differences in inline style handling.

I did all you asked except for one-liners.  As I explained to Vitaly before, I just try to follow the style of the corresponding files (see comment 14).  And again, if you think it's time to improve style of these files, I'll do that.

The main question for me right now---do we want to risk retaining huge graphs due to cached CSSPrimitiveValues?  I internally put offensive code into #if 0/#endif (to be removed before submit).

Vitaly think we should ignore them for now even though it'll introduce a minor bug.  Minor for that was a behaviour in Safari and Chromium in all the previous versions.

I think we could risk, but too concerned that OOMs due to this behaviour might be difficult to trace.  So now I am starting to linger on Vitaly's side.

What do you think?  For other options see comment 16.


(In reply to comment #18)
> (From update of attachment 85166 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=85166&action=review
> 
> I like the approach.  This stuff is very subtle, so I'm not 100% sure that this change is correct, but I don't see anything wrong with it.  Some very minor style nits below.
> 
> > Source/WebCore/bindings/scripts/CodeGeneratorV8.pm:1715
> > +    # find the super descriptor
> 
> This should be a complete sentence that starts with a capital letter and ends with a period.
> 
> > Source/WebCore/bindings/scripts/CodeGeneratorV8.pm:1720
> > +        if ($parent eq "EventTarget") { next; }
> 
> Each statement should be on its own line.
> 
> > Source/WebCore/bindings/v8/V8GCController.cpp:237
> > +    if (root->isStyleSheet())
> > +        if (Node* ownerNode = static_cast<StyleSheet*>(root)->ownerNode())
> > +            return calculateGroupId(ownerNode);
> 
> We need { } around the body of this if block.
> 
> > Source/WebCore/bindings/v8/V8GCController.cpp:281
> > +            // CSSProperty (type of items in mutable style declaration) doesn't have a pointer to
> > +            // its parent. Therefore we cannot treat them like other objects---traverse up to the
> > +            // root when visiting a wrapper---and need to put them into the group directly.
> 
> I see.  We still need to walk down for these.  Ok.
> 
> > Source/WebCore/bindings/v8/WrapperTypeInfo.h:67
> > +            
> 
> This blank line is empty.
> 
> > Source/WebCore/css/CSSRuleList.h:59
> > +    StyleList* styleList()
> > +    {
> > +        return m_list.get();
> > +    }
> 
> You can just put this all on one line if you like.  Simple getters can be on one line to preserve vertical space.
> 
> > Source/WebCore/css/StyleSheetList.h:57
> > +    Document* document()
> > +    {
> > +        return m_doc;
> > +    }
> 
> Same here.

[anton muhin]

Created attachment 85507 [details]
Patch

[anton muhin]

As discussed with Adam on IM, uploading a version that Vitaly and me prefer, so Adam can both r+ and cq+ it if he likes it.

(In reply to comment #22)
> Created an attachment (id=85507) [details]
> Patch

[Adam Barth]

Comment on attachment 85507 [details]
Patch

I'm sold.  :)

[WebKit Commit Bot]

Comment on attachment 85507 [details]
Patch

Clearing flags on attachment: 85507

Committed r81092: <http://trac.webkit.org/changeset/81092>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.