Bug 66452 – Attempt at making CSSSelector a little easier to understand and a little less bug-prone.

• Component: New Bugs
• Status: RESOLVED FIXED

[Luke Macpherson]

Attempt at making CSSSelector a little easier to understand and a little less bug-prone.

[Luke Macpherson]

Created attachment 104306 [details]
Patch

[Darin Adler]

Comment on attachment 104306 [details]
Patch

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

> Source/WebCore/css/CSSSelector.h:284
> -        union DataUnion {
> -            DataUnion() : m_value(0) { }
> -            AtomicStringImpl* m_value;
> -            RareData* m_rareData;
> -        } m_data;
> +        AtomicString m_value;
> +        OwnPtr<RareData> m_rareData;

This adds a pointer to the object. We should find a way to make the code clear without making the object larger.

[Luke Macpherson]

Created attachment 104459 [details]
Patch

[Luke Macpherson]

FYI, I did some measurements. Roughly 25% of the time m_data is null. Roughly 5% of the time rare data is needed. I never saw m_isForPage set on a production website, so moved it into rare data.

[Eric Seidel (no email)]

Comment on attachment 104459 [details]
Patch

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

I'm confused as to how this works.  This doesn't seem very much like the rare-data system used on RenderStyle.  Data<> wrappers on RenderStyle are basically fancy RefPtrs which allow for COW and sharing between styles.  I assume that's not what's going on here.

> Source/WebCore/css/CSSSelector.cpp:64
> +        if (selector->isForPage())

Is this @page?  If so that's a printing-only selector and definitely rare.

> Source/WebCore/css/CSSSelector.cpp:671
> +    createRareData();

Sad that this is needed explicitly. :(

[Darin Adler]

Comment on attachment 104459 [details]
Patch

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

> Source/WebCore/css/CSSSelector.h:322
> +        OwnPtr<Data> m_data;

This is an admirable attempt to clean up the memory use here, but given that 3/4 of the time we have non-null data, we will be allocating an extra memory block 3/4 of the time. An extra memory block is quite costly. I don’t think this is a good change.

[Darin Adler]

Comment on attachment 104459 [details]
Patch

“cleaning up magic” is fine, but if it makes the objects larger I am not sure it’s good to do it.

Lets find a way to clean up and make the object smaller!

[Luke Macpherson]

Comment on attachment 104459 [details]
Patch

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

>> Source/WebCore/css/CSSSelector.cpp:671
>> +    createRareData();
> 
> Sad that this is needed explicitly. :(

Yeah, I originally wanted to have Data automatically upgrade itself to RareData if a rare setter was called, but that was hard to do without increasing the size of those structures with some kind of pointer back to the CSSSelector instance. If you can think of a solution let me know.

>> Source/WebCore/css/CSSSelector.h:322
>> +        OwnPtr<Data> m_data;
> 
> This is an admirable attempt to clean up the memory use here, but given that 3/4 of the time we have non-null data, we will be allocating an extra memory block 3/4 of the time. An extra memory block is quite costly. I don’t think this is a good change.

The existing code already allocates an extra memory object for m_data.m_value or m_data.m_rareData, so I don't think this change makes that situation any worse.
This patch actually makes CSSSelector itself a little bit tighter by moving several bits, though due to alignment you don't notice it on 64 bit architectures.
The original patch I had moved m_value onto the parent object to avoid this extra allocation for the 75% case, but obviously that costs you in the 25% where it isn't used.

[Darin Adler]

(In reply to comment #8)
> > This is an admirable attempt to clean up the memory use here, but given that 3/4 of the time we have non-null data, we will be allocating an extra memory block 3/4 of the time. An extra memory block is quite costly. I don’t think this is a good change.
> 
> The existing code already allocates an extra memory object for m_data.m_value or m_data.m_rareData

That’s incorrect. The m_data.m_value is an AtomicStringImpl*, which does not allocate any memory if it’s a string already in the atomic string table. Further, the new code allocates a block to hold the AtomicStringImpl*.

Unless I missed something, this definitely adds a new memory block. Please don’t add a new memory block.

[Luke Macpherson]

(In reply to comment #9)
> (In reply to comment #8)
> > > This is an admirable attempt to clean up the memory use here, but given that 3/4 of the time we have non-null data, we will be allocating an extra memory block 3/4 of the time. An extra memory block is quite costly. I don’t think this is a good change.
> > 
> > The existing code already allocates an extra memory object for m_data.m_value or m_data.m_rareData
> 
> That’s incorrect. The m_data.m_value is an AtomicStringImpl*, which does not allocate any memory if it’s a string already in the atomic string table. Further, the new code allocates a block to hold the AtomicStringImpl*.
> 
> Unless I missed something, this definitely adds a new memory block. Please don’t add a new memory block.

Right you are, but now I'm stumped. I think this code is clearly nicer, but am at a loss as to how to resolve this constraint. Extending AtomicStringImpl was all I could think of, and that seems to be pretty painful. Do you have any ideas?

[Luke Macpherson]

Created attachment 104790 [details]
Patch

[Darin Adler]

(In reply to comment #10)
> I think this code is clearly nicer, but am at a loss as to how to resolve this constraint. Extending AtomicStringImpl was all I could think of, and that seems to be pretty painful. Do you have any ideas?

If your goal is to make the union clearer, I think you could make a class to manage the union to keep the strangeness tightly encapsulated. The only problem with that is that the class needs both the pointer and a boolean and I’m not sure how to make the boolean share storage with the rest of the class.

There’s no reason that the code to manage the trickiness of the union needs to be spread out in the class, mixed in with other code, and isolating it could get the clarity without sacrificing memory size.

[Luke Macpherson]

(In reply to comment #12)
> (In reply to comment #10)
> > I think this code is clearly nicer, but am at a loss as to how to resolve this constraint. Extending AtomicStringImpl was all I could think of, and that seems to be pretty painful. Do you have any ideas?
> 
> If your goal is to make the union clearer, I think you could make a class to manage the union to keep the strangeness tightly encapsulated. The only problem with that is that the class needs both the pointer and a boolean and I’m not sure how to make the boolean share storage with the rest of the class.
> 
> There’s no reason that the code to manage the trickiness of the union needs to be spread out in the class, mixed in with other code, and isolating it could get the clarity without sacrificing memory size.

Yes, there are two problems as I see it:
1) The DIY reference counting appears to be wrong.
2) The union is a mess, and encapsulating the logic would help.

I have some more ideas... lets see how they pan out in code.

[Luke Macpherson]

(In reply to comment #13)
> (In reply to comment #12)
> > (In reply to comment #10)
> > > I think this code is clearly nicer, but am at a loss as to how to resolve this constraint. Extending AtomicStringImpl was all I could think of, and that seems to be pretty painful. Do you have any ideas?
> > 
> > If your goal is to make the union clearer, I think you could make a class to manage the union to keep the strangeness tightly encapsulated. The only problem with that is that the class needs both the pointer and a boolean and I’m not sure how to make the boolean share storage with the rest of the class.
> > 
> > There’s no reason that the code to manage the trickiness of the union needs to be spread out in the class, mixed in with other code, and isolating it could get the clarity without sacrificing memory size.
> 
> Yes, there are two problems as I see it:
> 1) The DIY reference counting appears to be wrong.
> 2) The union is a mess, and encapsulating the logic would help.
> 
> I have some more ideas... lets see how they pan out in code.

I spent some time writing a templated union class that used the low-order pointer bits to store determine which of the union values was in use and handled the refcounting. I don't think it was any better than the patch that is currently up though.

[Darin Adler]

(In reply to comment #14)
> I don't think it was any better than the patch that is currently up though.

I understand that’s your overall judgement, but could you explain the difference between the two? What are the pros and cons of that other one and the patch that is currently up? Does the patch that is currently up use a larger object?

[Luke Macpherson]

(In reply to comment #15)
> (In reply to comment #14)
> > I don't think it was any better than the patch that is currently up though.
> 
> I understand that’s your overall judgement, but could you explain the difference between the two? What are the pros and cons of that other one and the patch that is currently up? Does the patch that is currently up use a larger object?

The current patch:
1) Should not introduce a size overhead over the existing code.
2) Still uses the union.
3) Fixes the reference counting bugs I could see.
4) Passes AtomicString around by value where appropriate.

[Darin Adler]

Comment on attachment 104790 [details]
Patch

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

I don’t understand this change at all. It’s customary to pass reference counted objects like these by const& to avoid the reference count churn. If changing them all has some benefit, you’ll need to state it so the code is not just changed back!

> Source/WebCore/css/CSSSelector.cpp:382
> -CSSSelector::PseudoType CSSSelector::parsePseudoType(const AtomicString& name)
> +CSSSelector::PseudoType CSSSelector::parsePseudoType(AtomicString name)

Could you explain the motivation for this further? Generally passing a structure holding a RefPtr like this by value an anti-pattern that causes additional reference count churn, but I presume there is a good reason to not do it here of some sort. Since someone after you is likely to change this to const AtomicString& unless you add a comment, I think you should also add a comment here explaining the unusual situation.

> Source/WebCore/css/CSSSelector.cpp:391
> -bool CSSSelector::isUnknownPseudoType(const AtomicString& name)
> +bool CSSSelector::isUnknownPseudoType(AtomicString name)

Same question/comment as above.

> Source/WebCore/css/CSSSelector.cpp:530
> -    const AtomicString& prefix = m_tag.prefix();
> -    const AtomicString& localName = m_tag.localName();
> +    AtomicString prefix = m_tag.prefix();
> +    AtomicString localName = m_tag.localName();

Why the change?

> Source/WebCore/css/CSSSelector.cpp:585
> -            const AtomicString& prefix = cs->attribute().prefix();
> +            AtomicString prefix = cs->attribute().prefix();

Why the change?

[Luke Macpherson]

Comment on attachment 104790 [details]
Patch

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

>> Source/WebCore/css/CSSSelector.cpp:382
>> +CSSSelector::PseudoType CSSSelector::parsePseudoType(AtomicString name)
> 
> Could you explain the motivation for this further? Generally passing a structure holding a RefPtr like this by value an anti-pattern that causes additional reference count churn, but I presume there is a good reason to not do it here of some sort. Since someone after you is likely to change this to const AtomicString& unless you add a comment, I think you should also add a comment here explaining the unusual situation.

I had only just thought about that 5 minutes ago and was about to go back and change them.

>> Source/WebCore/css/CSSSelector.cpp:391
>> +bool CSSSelector::isUnknownPseudoType(AtomicString name)
> 
> Same question/comment as above.

Will revert.

>> Source/WebCore/css/CSSSelector.cpp:530
>> +    AtomicString localName = m_tag.localName();
> 
> Why the change?

Will revert.

>> Source/WebCore/css/CSSSelector.cpp:585
>> +            AtomicString prefix = cs->attribute().prefix();
> 
> Why the change?

Will revert.

> Source/WebCore/css/CSSSelector.h:-228
> -        const AtomicString& value() const { return *reinterpret_cast<const AtomicString*>(m_hasRareData ? &m_data.m_rareData->m_value : &m_data.m_value); }

Do you approve of this change? I think it's worth eliminating this cast - I had to trace through at least 5 classes to verify that this would actually work.

[Darin Adler]

Comment on attachment 104790 [details]
Patch

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

>> Source/WebCore/css/CSSSelector.h:-228

> 
> Do you approve of this change? I think it's worth eliminating this cast - I had to trace through at least 5 classes to verify that this would actually work.

Well, the cast had a direct benefit, less reference count churn. Given that we have verified that it works, what is the concrete benefit to changing this? I haven’t seen evidence that this has been causing us trouble in the past.

[Luke Macpherson]

(In reply to comment #19)
> (From update of attachment 104790 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=104790&action=review
> 
> >> Source/WebCore/css/CSSSelector.h:-228
> 
> > 
> > Do you approve of this change? I think it's worth eliminating this cast - I had to trace through at least 5 classes to verify that this would actually work.
> 
> Well, the cast had a direct benefit, less reference count churn. Given that we have verified that it works, what is the concrete benefit to changing this? I haven’t seen evidence that this has been causing us trouble in the past.

I verified that the types would line up, but not that the reference count would be correctly incremented and decremented. OTOH, it's surely not worth this level of dependence on the internals of so many classes just to avoid a single increment + decrement is it?

[Darin Adler]

The code definitely works. (In reply to comment #20)
> OTOH, it's surely not worth this level of dependence on the internals of so many classes just to avoid a single increment + decrement is it?

You’re being really dramatic about the cost! It works fine. It doesn’t seem important to change this.

[Luke Macpherson]

(In reply to comment #21)
> The code definitely works. (In reply to comment #20)
> > OTOH, it's surely not worth this level of dependence on the internals of so many classes just to avoid a single increment + decrement is it?
> 
> You’re being really dramatic about the cost! It works fine. It doesn’t seem important to change this.

I think the engineering cost of code that I can't easily read and verify the correctness of is high. The code comments seem to back this up. It's a tradeoff between engineering / stylistic cost and runtime cost, so you might see that apples vs oranges call slightly differently to me.

We have seen crashes in this code, so there is at least some evidence that being hard to understand could be leading to bugs.
http://code.google.com/p/chromium/issues/detail?id=92970

[Darin Adler]

Your argument seems to be this: “We are seeing crashes in this code, so we should rewrite the code so that it is more readable (to you at least). We do know this rewrite will make it at least ever so slightly less efficient. We have no evidence the rewrite fixes any bugs, but rewriting for clarity is good especially if we have some crash reports in the code being rewritten.”

I don’t think that’s a compelling argument for change. I’d be a lot more interested if we had actually reproduced a bug and were fixing it, or had an improvement other than, “We think this is more elegant and easier to read.”

I think shouldn’t take rewriting tested code lightly, even if we don’t like its style. In particular, I don’t like removing optimizations without even measuring the effect of doing so for personal taste reasons.

[Luke Macpherson]

I'm just going to keep improving the code. It's less emotive, and probably more productive than engaging in a debate on the philosophy of software engineering here.

[Darin Adler]

(In reply to comment #24)
> I'm just going to keep improving the code. It's less emotive, and probably more productive than engaging in a debate on the philosophy of software engineering here.

OK, I’ll just keep making the code worse with unpleasant debate!

[Darin Adler]

More seriously, though, I have no objections to making improvements here, but I think for the cost/benefit to be right I’d want it to both be cleaner and measurably as efficient or more efficient than we code we have.

I do think that can be accomplished by tighter encapsulation of the union trick. The type punning between AtomicString and AtomicStringImpl* is the same optimization as is done by HashMap, so maybe there’s some opportunity to make a helper in WTF for this.

[Luke Macpherson]

Created attachment 105296 [details]
Patch

[Darin Adler]

Comment on attachment 105296 [details]
Patch

Looks like this would lead to a storage leak. I wonder if there is a simple way to test for the leak.

[Luke Macpherson]

(In reply to comment #28)
> (From update of attachment 105296 [details])
> Looks like this would lead to a storage leak. I wonder if there is a simple way to test for the leak.

My best guess is that setValue() is usually not called multiple times in practice.

[Luke Macpherson]

Testing seems to confirm this. In the fast test cases and some general browsing setValue hasn't been called twice yet, so perhaps this is a theoretical leak rather than an actual one.

[WebKit Review Bot]

Comment on attachment 105296 [details]
Patch

Clearing flags on attachment: 105296

Committed r93952: <http://trac.webkit.org/changeset/93952>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.