Bug 55399 - Rework object grouping to never produce huge grouper array
Summary: Rework object grouping to never produce huge grouper array
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: WebKit Misc. (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: anton muhin
URL:
Keywords:
Depends on:
Blocks: 55899
  Show dependency treegraph
 
Reported: 2011-02-28 12:33 PST by anton muhin
Modified: 2011-03-14 18:19 PDT (History)
9 users (show)

See Also:


Attachments
Patch (5.75 KB, patch)
2011-02-28 12:43 PST, anton muhin
no flags Details | Formatted Diff | Diff
Patch (24.21 KB, patch)
2011-03-04 10:19 PST, anton muhin
no flags Details | Formatted Diff | Diff
Patch (24.19 KB, patch)
2011-03-05 03:55 PST, anton muhin
no flags Details | Formatted Diff | Diff
Patch (24.13 KB, patch)
2011-03-09 05:57 PST, anton muhin
no flags Details | Formatted Diff | Diff
Patch (26.93 KB, patch)
2011-03-11 11:21 PST, anton muhin
no flags Details | Formatted Diff | Diff
Patch (27.83 KB, patch)
2011-03-11 12:02 PST, anton muhin
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description anton muhin 2011-02-28 12:33:17 PST
[v8] Do not put the same handle into several groups: that can easily lead to huge array of items to be grouped
Comment 1 anton muhin 2011-02-28 12:35:05 PST
The original problem: http://code.google.com/p/chromium/issues/detail?id=73441
Comment 2 anton muhin 2011-02-28 12:43:32 PST
Created attachment 84098 [details]
Patch
Comment 3 anton muhin 2011-02-28 12:44:38 PST
Guys, I would really appreciate any algorithmic advice as well.  I hope that typically we shouldn't have too many group ids (~100).
Comment 4 anton muhin 2011-03-02 07:29:30 PST
Comment on attachment 84098 [details]
Patch

Mads and Vitaly suggested to investigate some better approaches.  So I am cancelling request for review for now.
Comment 5 anton muhin 2011-03-04 10:19:27 PST
Created attachment 84775 [details]
Patch
Comment 6 Early Warning System Bot 2011-03-04 12:13:33 PST
Attachment 84775 [details] did not build on qt:
Build output: http://queues.webkit.org/results/8083780
Comment 7 Collabora GTK+ EWS bot 2011-03-04 12:57:14 PST
Attachment 84775 [details] did not build on gtk:
Build output: http://queues.webkit.org/results/8088549
Comment 8 Darin Adler 2011-03-04 16:12:47 PST
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.
Comment 9 WebKit Review Bot 2011-03-04 20:26:09 PST
Attachment 84775 [details] did not build on mac:
Build output: http://queues.webkit.org/results/8083919
Comment 10 anton muhin 2011-03-05 03:55:37 PST
Created attachment 84858 [details]
Patch
Comment 11 anton muhin 2011-03-05 03:56:47 PST
(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.
Comment 12 Vitaly Repeshko 2011-03-05 09:24:44 PST
(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.
Comment 13 anton muhin 2011-03-09 05:57:00 PST
Created attachment 85166 [details]
Patch
Comment 14 anton muhin 2011-03-09 06:02:33 PST
(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.
Comment 15 Vitaly Repeshko 2011-03-09 07:22:27 PST
(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.
Comment 16 anton muhin 2011-03-10 07:13:32 PST
(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?
Comment 17 Vitaly Repeshko 2011-03-10 10:14:56 PST
(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.
Comment 18 Adam Barth 2011-03-10 12:51:47 PST
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.
Comment 19 anton muhin 2011-03-11 11:21:53 PST
Created attachment 85499 [details]
Patch
Comment 20 Adam Barth 2011-03-11 11:24:29 PST
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...
Comment 21 anton muhin 2011-03-11 11:27:39 PST
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.
Comment 22 anton muhin 2011-03-11 12:02:40 PST
Created attachment 85507 [details]
Patch
Comment 23 anton muhin 2011-03-11 12:03:38 PST
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
Comment 24 Adam Barth 2011-03-14 14:05:28 PDT
Comment on attachment 85507 [details]
Patch

I'm sold.  :)
Comment 25 WebKit Commit Bot 2011-03-14 18:19:35 PDT
Comment on attachment 85507 [details]
Patch

Clearing flags on attachment: 85507

Committed r81092: <http://trac.webkit.org/changeset/81092>
Comment 26 WebKit Commit Bot 2011-03-14 18:19:40 PDT
All reviewed patches have been landed.  Closing bug.