Refactor the CSSProperty handling infrastructure of CSSParser

[Eric Seidel (no email)]

CSSParser should use custom "vector-like" class for managing properties

Right now CSSParser has this ad hoc system of m_parsedProperties m_numParsedProperties and m_maxParsedProperties, along with a bunch of fastMalloc and fastRealloc statements.  We can't just replace this directly with a vector (unless we're comfortable changing away from the current allocation scheme.  But we should at least move to a custom class which encapulates this logic.  That would make parts of CSSParser much cleaner (no more direct array lookups, instead we would call things like

m_parseProperties.last(), etc.

[Dave Hyatt]

Why can't we just use a Vector?  As long as you make sure the minimum capacity is m_maxParsedProperties, I think it would work.

[Eric Seidel (no email)]

(In reply to comment #1)
> Why can't we just use a Vector?  As long as you make sure the minimum capacity
> is m_maxParsedProperties, I think it would work.
> 

I think we probably can just use vector.  But that will change the growth behavior (or at least the default growth behavior), we can manually grow it in equal sized chunks instead of letting vector grow itself by 2x each time it needs to.

[Alexey Proskuryakov]

Eric, can this bug be closed now?

[Andras Becsi]

The described approach is still the same whith m_parsedProperties being a CSSProperty** and CSSParser is still using fastMalloc and fastRealloc for managing it.
That's why I took ownership of the bug, but if this is of no concern any more, I can surely close it as wontfix.

[Andras Becsi]

Created attachment 93934 [details]
proposed patch

Implement CSSPropertyContainer which on removal marks entries as empty and sweeps them when the internal array grows too big. Use an internal HashMap to be able to efficiently find entries by ID and automatically discard duplicate properties.

In a follow-up patch CSSMutableStyleDeclaration can be simplified to use this container too, instead of maintaining its own vector-based infrastructure for managing parsed properties.

[Andras Becsi]

Created attachment 93936 [details]
updated patch

Updated to ToT.

[Gyuyoung Kim]

Comment on attachment 93936 [details]
updated patch

Attachment 93936 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/8708684

[Andras Becsi]

Created attachment 94075 [details]
updated patch

Also add CSSPropertyContainer to CMakeLists.txt to make it build on EFL.

[Andras Becsi]

Comment on attachment 94075 [details]
updated patch

Marking this obsolete and preparing an updated patch.

[Andras Becsi]

Created attachment 99473 [details]
proposed patch v2

[WebKit Review Bot]

Attachment 99473 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/CMakeLists.txt', u'Source/W..." exit_code: 1

Source/WebCore/css/CSSPropertyContainer.cpp:176:  Extra space after ( in if  [whitespace/parens] [5]
Total errors found: 1 in 16 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Andras Becsi]

Created attachment 99474 [details]
proposed patch v2

Remove extra whitespace.

[Andras Becsi]

Created attachment 99476 [details]
proposed patch v2

Fix the chromium build.

[WebKit Review Bot]

Comment on attachment 99476 [details]
proposed patch v2

Attachment 99476 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/8970501

[Collabora GTK+ EWS bot]

Comment on attachment 99476 [details]
proposed patch v2

Attachment 99476 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/8970509

[WebKit Review Bot]

Comment on attachment 99476 [details]
proposed patch v2

Attachment 99476 [details] did not pass cr-mac-ews (chromium):
Output: http://queues.webkit.org/results/8965888

[WebKit Review Bot]

Comment on attachment 99476 [details]
proposed patch v2

Attachment 99476 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/8977030

[WebKit Review Bot]

Comment on attachment 99476 [details]
proposed patch v2

Attachment 99476 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/8970545

[Gyuyoung Kim]

Comment on attachment 99476 [details]
proposed patch v2

Attachment 99476 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/8988024

[Andras Becsi]

Created attachment 99717 [details]
updated patch

Addressed build issues.

[WebKit Review Bot]

Attachment 99717 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Source/WebCore/css/CSSMutableStyleDeclaration.cpp:653:  Missing space before ( in if(  [whitespace/parens] [5]
Total errors found: 1 in 20 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Andras Becsi]

Created attachment 99723 [details]
proposed patch (style issue addressed)

[Andras Becsi]

With the patch we get around 2-3% gain with QtTestBrowser on the Methanol page loading test, which tests on 23 locally mirrored popular sites.
Even bigger speed-up should be possible if CSSMutableStyleDeclaration also uses this container for managing properties.

[Balazs Kelemen]

Comment on attachment 99723 [details]
proposed patch (style issue addressed)

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

Informal review from a workmate :)

> Source/WebCore/css/CSSProperty.h:37
> +    CSSProperty()
> +    {
> +    }

Please initialize the members or add a comment about why it is safe to not initializing them.

> Source/WebCore/css/CSSPropertyContainer.cpp:68
> +    if (m_usedSize + 1 >= m_properties.size())
> +        sweep();

|m_usedSize > m_properties.size()| as the condition would be more straightforward I think

> Source/WebCore/css/CSSPropertyContainer.cpp:77
> +    if (!propertyID || !m_idToPositionMap.contains(propertyID))
> +        return kInvalidPosition;

I don't think you need this checks because you never call it with a 0 propertyID (could be an ASSERT) and the second part is checked once again below.

> Source/WebCore/css/CSSPropertyContainer.cpp:82
> +    unsigned position = m_idToPositionMap.get(propertyID);
> +
> +    if (position == kInvalidPosition)
> +        return kInvalidPosition;

This is where you check it again but it is not clear. I guess it works because the value you define as kInvalidPosition is equal with HashTraits<unsigned>::empty(). However, these are not strictly the same thing so you should use the latter here.

> Source/WebCore/css/CSSPropertyContainer.cpp:95
> +    if (position >= m_usedSize || !m_properties[position].id())
> +        return;

I don't think you need the first part of the condition, it could be an ASSERT. Maybe the second part could be relaxed as well by taking care of that in the callers that know whether it is neccessary to check this.

> Source/WebCore/css/CSSPropertyContainer.cpp:106
> +    if (!propertyID)
> +        return;

ASSERT instead?

> Source/WebCore/css/CSSPropertyContainer.cpp:169
> +    return &m_properties.at(index);

nit: s/at/[] for consistency

> Source/WebCore/css/CSSPropertyContainer.cpp:179
> +    if (position == kInvalidPosition)
> +        return false;
> +
> +    return true;

I would say |return position != kInvalidPosition|

> Source/WebCore/css/CSSPropertyContainer.cpp:236
> +    for (int i = 0; i < 3; ++i) {

nit: s/3/sizeof(ids)

> Source/WebCore/css/CSSPropertyContainer.h:40
> +    CSSProperty* findPropertyWithId(int propertyID);

It is unused now, right? Maybe we should add this later.

> Source/WebCore/css/CSSPropertyContainer.h:46
> +    CSSProperty* operator[](size_t index);

Seems odd that it returns with a pointer and not a reference. Callers use  the return value without checking that it is not zero (there is an ASSERT at one of them) so a reference could work.

[Andras Becsi]

Created attachment 99830 [details]
proposed patch

Updated, comments taken into account.

[Andras Becsi]

(In reply to comment #24)

Thanks Balazs for taking a look at the patch.

> (From update of attachment 99723 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=99723&action=review
> 
> Informal review from a workmate :)
> 
> > Source/WebCore/css/CSSProperty.h:37
> > +    CSSProperty()
> > +    {
> > +    }
> 
> Please initialize the members or add a comment about why it is safe to not initializing them.
> 

Done.

> > Source/WebCore/css/CSSPropertyContainer.cpp:68
> > +    if (m_usedSize + 1 >= m_properties.size())
> > +        sweep();
> 
> |m_usedSize > m_properties.size()| as the condition would be more straightforward I think

Ditto.

> 
> > Source/WebCore/css/CSSPropertyContainer.cpp:77
> > +    if (!propertyID || !m_idToPositionMap.contains(propertyID))
> > +        return kInvalidPosition;
> 
> I don't think you need this checks because you never call it with a 0 propertyID (could be an ASSERT) and the second part is checked once again below.
> 
> > Source/WebCore/css/CSSPropertyContainer.cpp:82
> > +    unsigned position = m_idToPositionMap.get(propertyID);
> > +
> > +    if (position == kInvalidPosition)
> > +        return kInvalidPosition;
> 
> This is where you check it again but it is not clear. I guess it works because the value you define as kInvalidPosition is equal with HashTraits<unsigned>::empty(). However, these are not strictly the same thing so you should use the latter here.

invalidateByPosition sets kInvalidPosition as position value instead of removing the pair from the HashMap, so if there is no entry in the hash yet we had an early return.

But you are right, this doubles the look-ups, so now kInvalidPosition is HashTraits<unsigned>::emptyValue() which makes things simpler.

> 
> > Source/WebCore/css/CSSPropertyContainer.cpp:95
> > +    if (position >= m_usedSize || !m_properties[position].id())
> > +        return;
> 
> I don't think you need the first part of the condition, it could be an ASSERT. Maybe the second part could be relaxed as well by taking care of that in the callers that know whether it is neccessary to check this.

Redundant checks. Fixed.

> 
> > Source/WebCore/css/CSSPropertyContainer.cpp:106
> > +    if (!propertyID)
> > +        return;
> 
> ASSERT instead?

Done.
> 
> > Source/WebCore/css/CSSPropertyContainer.h:40
> > +    CSSProperty* findPropertyWithId(int propertyID);
> 
> It is unused now, right? Maybe we should add this later.

Yep, this was left accidentally in this patch.

> 
> > Source/WebCore/css/CSSPropertyContainer.h:46
> > +    CSSProperty* operator[](size_t index);
> 
> Seems odd that it returns with a pointer and not a reference. Callers use  the return value without checking that it is not zero (there is an ASSERT at one of them) so a reference could work.

I did not want to change all the callsites to use references since the patch got too big, and scares reviewers away, but now I changed it to return references.

[WebKit Review Bot]

Comment on attachment 99830 [details]
proposed patch

Attachment 99830 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/8995027

[WebKit Review Bot]

Comment on attachment 99830 [details]
proposed patch

Attachment 99830 [details] did not pass cr-mac-ews (chromium):
Output: http://queues.webkit.org/results/8984808

[Andras Becsi]

Created attachment 99842 [details]
proposed patch

Fix the chromium builds.

[WebKit Review Bot]

Comment on attachment 99842 [details]
proposed patch

Attachment 99842 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/8995063

[WebKit Review Bot]

Comment on attachment 99842 [details]
proposed patch

Attachment 99842 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/8987750

[Andras Becsi]

Created attachment 99991 [details]
updated patch

Use HashTraits<unsigned>::emptyValue() directly instead of assigning it to a global constant, to avoid creating global initializers on call sites.

[Andras Becsi]

Comment on attachment 99991 [details]
updated patch

As discussed with anttik on IRC it might be better to do a more extensive refactoring of the CSSProperty infrastructure.
Marking the patch obsolete.

[Antti Koivisto]

We discussed this with Andras in IRC. The conclusion was that he will take another shot of doing a wider refactoring of this very old code. My concern was that the current patch sort of encapsulates the assumptions (for example that the data structure here should look like a vector) of the old code into a class, with some performance improvements, whereas a bit wider look might bring much more improvements.

[Andras Becsi]

Created attachment 103266 [details]
proposed patch

[Andras Becsi]

Created attachment 103289 [details]
updated patch

[WebKit Review Bot]

Comment on attachment 103289 [details]
updated patch

Attachment 103289 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/9225115

New failing tests:
fast/css/invalidation-errors-2.html
fast/css/invalidation-errors.html

[Andras Becsi]

Created attachment 103911 [details]
updated patch

[Andras Becsi]

Comment on attachment 103911 [details]
updated patch

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

> Source/WebCore/ChangeLog:10
> +        In a follow-up CSSPropertyContainer can also be used to extract the property handling logic
> +        from CSSMutableStyleDeclaration which currently maintains its own fork of infrastructure
> +        for managing parsed properties.

I just realized that this might not be true since CSSMutableStyleDeclaration seem to need a Vector-based approach at least for it's item(unsigned) method so this simplification might not be possible with the ListHashSet based patch.

Although this patch has a simpler logic, the previous approach has more possibilities for removing logically duplicated code from CSSMutableStyleDeclaration. I'm going to look into this in more detail tomorrow.

[Antti Koivisto]

It should be possible to add special case optimization for that particular case by constructing a simple vector cache when item() is first called. I suspect it is rarely used as CSSOM API and internal use (if any) could be replaced.

[Andras Becsi]

(In reply to comment #40)
> It should be possible to add special case optimization for that particular case by constructing a simple vector cache when item() is first called. I suspect it is rarely used as CSSOM API and internal use (if any) could be replaced.

That's what I was experimenting with and it looks like it's going to work. I have a draft patch for BUG 61186 which is based on this data structure I'm measuring the impact now. I'm uploading here an updated patch soon just waiting for the update of my git-svn repo.

[Andras Becsi]

Created attachment 104356 [details]
updated patch

[Andras Becsi]

Created attachment 104869 [details]
updated to ToT

[Antti Koivisto]

I'm unsure if this is really a progression. It adds quite a bit of code lines for little obvious benefit. It might look different when CSSMutableStyleDeclaration is switched over to the new class. However, CSSPropertyContainer look far too heavy weight to be used there as is, CSS rules are high volume objects that need to size optimized.

[Andras Becsi]

Comment on attachment 104869 [details]
updated to ToT

Taking the patch out of the review queue. I might have time to revisit the issue soon.

[Andras Becsi]

*** This bug has been marked as a duplicate of bug 80653 ***