Bug 87078 – Make CSSParser::filteredProperties() O(n) instead of O(n^2) and improve readability.

• Component: New Bugs
• Status: RESOLVED FIXED

[Luke Macpherson]

Make CSSParser::filteredProperties() O(n) instead of O(n^2) and improve readability.

[Luke Macpherson]

Created attachment 143188 [details]
Patch

[Luke Macpherson]

Out of interest I ran run-perf-tests --release PerformanceTests/Parser/html5-full-render.html and got:

With change:
RESULT Parser: html5-full-render= 21311.0 ms
median= 21311.0 ms, stdev= 37.0 ms, min= 21274.0 ms, max= 21348.0 ms
RESULT Parser: html5-full-render= 21241.0 ms
median= 21241.0 ms, stdev= 179.0 ms, min= 21062.0 ms, max= 21420.0 ms
RESULT Parser: html5-full-render= 21245.0 ms
median= 21245.0 ms, stdev= 198.0 ms, min= 21047.0 ms, max= 21443.0 ms

Without change:
RESULT Parser: html5-full-render= 21434.0 ms
median= 21434.0 ms, stdev= 101.0 ms, min= 21333.0 ms, max= 21535.0 ms
RESULT Parser: html5-full-render= 21248.5 ms
median= 21248.5 ms, stdev= 130.5 ms, min= 21118.0 ms, max= 21379.0 ms
RESULT Parser: html5-full-render= 21373.5 ms
median= 21373.5 ms, stdev= 129.5 ms, min= 21244.0 ms, max= 21503.0 ms

This is performance in the best-case scenario for the existing code because the html5 spec css doesn't have !important properties and I didn't notice any rules with duplicated properties. So the take-away is that this code is at least as fast in the straightforward case of no duplicated rules and no important properties, yet uses an algorithm that is much better for pages that do use those features.

[Antti Koivisto]

Comment on attachment 143188 [details]
Patch

I don't see the point. Duplicate properties are rare. You add two extra iterations (loop and reversal) to the common case.

[Luke Macpherson]

If we follow the logic of bug https://bugs.webkit.org/show_bug.cgi?id=82235 where order of properties returned to JS is not guaranteed, I can remove the reverse.

The other argument that there are two loops (one for important, one for unimportant) is unimportant, since the only difference is the cost of the actual increment operation - we still execute the loop body only once per input property.

[Luke Macpherson]

Created attachment 143416 [details]
Patch

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1
Source/WTF/ChangeLog:1:  ChangeLog entry has no bug number  [changelog/bugnumber] [5]
LayoutTests/ChangeLog:1:  ChangeLog entry has no bug number  [changelog/bugnumber] [5]
Total errors found: 2 in 6 files


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

[Luke Macpherson]

Created attachment 143423 [details]
Patch

[WebKit Review Bot]

Comment on attachment 143423 [details]
Patch

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

New failing tests:
fast/backgrounds/size/backgroundSize19.html
fast/dom/css-dom-read-2.html
fast/loader/loadInProgress.html
fast/loader/unload-form-post-about-blank.html
fast/backgrounds/background-clip-text.html
http/tests/cookies/simple-cookies-expired.html
fast/gradients/simple-gradients.html
fast/backgrounds/mask-composite.html
http/tests/cookies/simple-cookies-max-age.html
http/tests/security/script-crossorigin-loads-correctly.html
http/tests/cookies/multiple-cookies.html
fast/backgrounds/size/backgroundSize17.html
fast/dom/css-dom-read.html
fast/inspector-support/style.html
fast/backgrounds/size/backgroundSize13.html
fast/borders/border-image-scaled-gradient.html
fast/backgrounds/size/backgroundSize20.html
fast/backgrounds/background-origin-root-element.html
fast/borders/border-image-reset-by-border-shorthand.html
editing/pasteboard/style-from-rules.html
http/tests/cookies/single-quoted-value.html
fast/backgrounds/size/backgroundSize22.html
fast/backgrounds/size/backgroundSize18.html
fast/borders/border-image-repeat.html
fast/backgrounds/size/backgroundSize21.html

[WebKit Review Bot]

Created attachment 143447 [details]
Archive of layout-test-results from ec2-cr-linux-02

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: ec2-cr-linux-02  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.35-28-virtual-x86_64-with-Ubuntu-10.10-maverick

[Antti Koivisto]

Comment on attachment 143423 [details]
Patch

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

Do you have some real world benchmark that you are trying to improve? Otherwise this seems bit like changing code for the sake of changing code.

> Source/WebCore/ChangeLog:9
> +        1) Make the code more linearly readable by separating out handling of important and non-important properties.

I don't think it is any more readable.

> Source/WebCore/ChangeLog:10
> +        2) Eliminate one BitArray instance (reduces hot memory so more cache friendly).

This is unlikely to have any real effect considering how small BitArrays here are (48bytes).

> Source/WebCore/ChangeLog:11
> +        3) Use unchecked array appends (checking is not necessary because capacity has already been reserved).

This makes sense as a tiny micro-optimization.

> Source/WebCore/ChangeLog:14
> +        4) Remove O(n^2) behavior caused by scanning for and removing previously encountered definitions of each property.
> +           This was quite bad because we would remove early in the vector causing a move of all subsequent entries, then
> +           add at the end to keep the order correct.

The O(n^2) here is an artificial edge case (the same property repeated many times in a single rule).

> Source/WebCore/css/CSSParser.cpp:1133
> +    // Add important properties in reverse order, skipping already set properties.
> +    for (int i = m_parsedProperties.size() - 1; i >= 0; --i) {

!important properties are rare. This adds unnecessary loop for the common case.

[Luke Macpherson]

Created attachment 143695 [details]
Patch

[Luke Macpherson]

For the case you guys want to optimize, ie. non-repeated non-important properties:

Existing code:
For loop performs n increments
2n calls to CSSProperty::isImportant
n calculations of propertyIDIndex
2n calls to BitArray::get
n calls to BitArray::set
n vector sets
Total 5n branches.

New code:
For loops perform 2n increments
2n calls to CSSProperty::isImportant
n calculations of propertyIDIndex
n calls to BitArray::get
n calls to BitArray::set
n vector sets
Total 5n + 1 branches.

So basically you trade n calls to BitArray::get for n increments and one branch (that is not taken).

On the other hand, for all other cases. where property precedence takes effect and the current code become super-linear, the new code becomes substantially faster than the existing code. That case is more common than you might expect because authors frequently define both -webkit prefixed and non-prefixed versions within the same style rule, and in that case the parser maps to the same CSSPropertyID.

[Luke Macpherson]

Created attachment 143965 [details]
Patch

[Build Bot]

Comment on attachment 143965 [details]
Patch

Attachment 143965 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12808245

[Rafael Brandao]

Comment on attachment 143965 [details]
Patch

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

Nice changes.

> Source/WebCore/ChangeLog:24
> +        Add default constructor.

How this change helps to fix what is proposed on title?

> Source/WebCore/css/CSSParser.cpp:1172
> +    for (int important = 1; important >=0; --important) {

Nit: missing whitespace between >= and 0.

[Luke Macpherson]

Created attachment 144251 [details]
Patch

[Darin Adler]

Comment on attachment 144251 [details]
Patch

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

review- because of the VectorTraits mistake; the other comments are optional ideas for improvement

> Source/WebCore/ChangeLog:13
> +        3) Remove O(n^2) behavior caused by scanning for and removing previously encountered definitions of each property.
> +           This was quite bad because we would remove early in the vector causing a move of all subsequent entries, then
> +           add at the end to keep the order correct.

Given that we’re removing this, we should create a regression test to demonstrate it, perhaps with Ojan’s performance regression test system (in LayoutTests/perf). If not, the change log should say why not.

> Source/WebCore/css/CSSParser.cpp:1185
> +    size_t unused = m_parsedProperties.size();

Typically it’s better to have variable names be noun phrases rather than adjective phrases. So we need a noun to go after “unused”. Maybe unusedCount is a good choice.

> Source/WebCore/css/CSSParser.cpp:1186
> +    results.resize(unused);

It’s slightly more efficient to initialize the vector with this size rather than calling resize explicitly. Easy to do by just passing this number to the vector constructor.

> Source/WebCore/css/CSSParser.cpp:1189
> +    for (int important = 1; important >= 0; --important) {

While this will work just fine, I think it’s unconventional and so not all that readable.

A more readable alternative would be to put the inner loop in an inline function and call it twice, once for important and once for non-important properties.

> Source/WebCore/css/CSSParser.cpp:1203
> +    if (unused)
> +        results.remove(0, unused);

It’s probably OK to leave out the if statement; it’s not needed for correctness since remove(0, 0) will do nothing, so we should only keep it if we think it’s a significant optimization.

> Source/WebCore/css/CSSProperty.h:76
> +namespace WTF {
> +template <> struct VectorTraits<WebCore::CSSProperty> : SimpleClassVectorTraits { };
> +}

This is not quite correct. It will set canCompareWithMemcmp to true, and that should be false. Probably the best way to do this would be to inherit from VectorTraitsBase<false, WebCore::CSSProperty> and set canInitializeWithMemset and canMoveWithMemcpy to true. Inheriting from SimpleClassVectorTraits and setting canCompareWithMemcmp to false would be OK for now, but is less future-proof we add additional traits.

[Luke Macpherson]

Created attachment 144258 [details]
Patch

[Luke Macpherson]

Thanks for the code review Darin - reviews with such concrete change suggestions are very productive, so thanks for taking the time to make them.

I wrote a performance test, and found that the cost here gets lost in the noise until I crank it up to an unrealistic input size, so I'm not sure it is worth adding.

Also, I found we can hit the ASSERT(position < size()) case in Vector.h, so I've left the check that unusedEntries > 0 in place there. I take it this happens when m_parsedProperties contained no entries.

I think I've addressed all other comments as requested.

[Darin Adler]

(In reply to comment #19)
> I found we can hit the ASSERT(position < size()) case in Vector.h

I think that’s a bug in Vector.h. It should be <=. It's correct for the single-argument remove to assert that position is < size, but not for the double-argument one.

But you don’t need to fix that bug as part of this patch here. We should fix it, though!

[Darin Adler]

Comment on attachment 144258 [details]
Patch

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

The function template is counterproductive for making the function more readable, so review- because of that.

> Source/WebCore/css/CSSParser.cpp:1181
> +template<bool important, typename InputVector, typename OutputVector>
> +static inline void filterProperties(const InputVector& input, OutputVector& output, size_t& unusedEntries, BitArray<numCSSProperties>& seenProperties)

There is no need to make this a function template. It simply makes the code more indirect and harder to read.

Constant folding of an inline function does fine with a boolean argument; there is no need to make that a template argument instead of a function argument.

We know the type of both input and output; a normal function will do.

> Source/WebCore/css/CSSParser.cpp:1183
> +    for (int i = input.size() - 1; i >= 0; --i) {

Need a “why” comment here explaining why we need to iterate backward.

> Source/WebCore/css/CSSParser.cpp:1191
> +        if (property.isImportant() == important) {
> +            const unsigned propertyIDIndex = property.id() - firstCSSProperty;
> +            if (!seenProperties.get(propertyIDIndex)) {
> +                seenProperties.set(propertyIDIndex);
> +                output[--unusedEntries] = property;
> +            }
> +        }

Typically WebKit code does “early continue” rather than nesting the code deeper and deeper in if statements like this.

> Source/WebCore/css/CSSParser.cpp:1202
> +    filterProperties<true>(m_parsedProperties, results, unusedEntries, seenProperties);
> +    filterProperties<false>(m_parsedProperties, results, unusedEntries, seenProperties);

Need a “why” comment here explaining why we do true before false.

[Darin Adler]

One more thought on this patch: The value here is small, not even measurable, and local. Lets try to focus our efforts on changes with larger benefit or on ones that are one small step of a well understood larger improvement to WebKit.

[Luke Macpherson]

(In reply to comment #21)
> (From update of attachment 144258 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=144258&action=review
> 
> The function template is counterproductive for making the function more readable, so review- because of that.

I'll do it because you're asking for it, but I believe using a template is better because it hides the icky type details of having inline sizes of those vectors. This code doesn't care that one has 256 inline entries and the other 4 - the compiler is quite capable of inferring that for us, which is why I went for the template.

> > Source/WebCore/css/CSSParser.cpp:1181
> > +template<bool important, typename InputVector, typename OutputVector>
> > +static inline void filterProperties(const InputVector& input, OutputVector& output, size_t& unusedEntries, BitArray<numCSSProperties>& seenProperties)
> 
> There is no need to make this a function template. It simply makes the code more indirect and harder to read.
> 
> Constant folding of an inline function does fine with a boolean argument; there is no need to make that a template argument instead of a function argument.
>
> We know the type of both input and output; a normal function will do.
> 
> > Source/WebCore/css/CSSParser.cpp:1183
> > +    for (int i = input.size() - 1; i >= 0; --i) {
> 
> Need a “why” comment here explaining why we need to iterate backward.
> 
> > Source/WebCore/css/CSSParser.cpp:1191
> > +        if (property.isImportant() == important) {
> > +            const unsigned propertyIDIndex = property.id() - firstCSSProperty;
> > +            if (!seenProperties.get(propertyIDIndex)) {
> > +                seenProperties.set(propertyIDIndex);
> > +                output[--unusedEntries] = property;
> > +            }
> > +        }
> 
> Typically WebKit code does “early continue” rather than nesting the code deeper and deeper in if statements like this.
> 
> > Source/WebCore/css/CSSParser.cpp:1202
> > +    filterProperties<true>(m_parsedProperties, results, unusedEntries, seenProperties);
> > +    filterProperties<false>(m_parsedProperties, results, unusedEntries, seenProperties);
> 
> Need a “why” comment here explaining why we do true before false.

[Darin Adler]

(In reply to comment #23)
> (In reply to comment #21)
> > The function template is counterproductive for making the function more readable, so review- because of that.
> 
> I believe using a template is better because it hides the icky type details of having inline sizes of those vectors. This code doesn't care that one has 256 inline entries and the other 4 - the compiler is quite capable of inferring that for us, which is why I went for the template.

Yes, that should not have to be restated in the function. And that is best avoided by using a typedef for each of the two vector types. Not by making the function a template.

[Luke Macpherson]

(In reply to comment #22)
> One more thought on this patch: The value here is small, not even measurable, and local. Lets try to focus our efforts on changes with larger benefit or on ones that are one small step of a well understood larger improvement to WebKit.

To be honest I don't understand why this patch is getting so much resistance. I'm not looking at this code for the fun of it - I need it to be cleaned up so I can add variables in a reasonable manner. I think that falls into the category of "one small step of a well understood larger improvement to WebKit".

All the performance arguing on this thread is a distraction - it is frustrating to have to provide so much justification on that front even when it's pretty obvious that isn't that important.

[Darin Adler]

(In reply to comment #25)
> To be honest I don't understand why this patch is getting so much resistance.

I can’t speak for Antti, but since you have submitted many patches that refactor with the stated goal “improve readability” that makes me a bit more cautious than I would be with other contributors. There is no mention here of the fact that this relates to adding CSS variables or how. I’d love to review that aspect of the change as well. Until you mentioned it I did not see any connection with variables. And I’d generally like to know that context for patches I review.

[Luke Macpherson]

You can see the with-variables version of the code at https://bugs.webkit.org/attachment.cgi?id=143937 line 1166.

[Darin Adler]

To be clear, the only reason for the review- the last time around was the template function issue.

[Luke Macpherson]

Created attachment 144262 [details]
Patch

[Antti Koivisto]

(In reply to comment #25)
> All the performance arguing on this thread is a distraction - it is frustrating to have to provide so much justification on that front even when it's pretty obvious that isn't that important.

The bug title states that the goal is fixing a performance issue. You can expect reviewers to focus on that. Now it sounds like your actual goal was something else.

[Luke Macpherson]

(In reply to comment #30)
> (In reply to comment #25)
> > All the performance arguing on this thread is a distraction - it is frustrating to have to provide so much justification on that front even when it's pretty obvious that isn't that important.
> 
> The bug title states that the goal is fixing a performance issue. You can expect reviewers to focus on that. Now it sounds like your actual goal was something else.

That's fair - usually at the point of uploading a patch I'm just describing what the patch does. I'll try to provide more context in future.

[WebKit Review Bot]

Comment on attachment 144262 [details]
Patch

Clearing flags on attachment: 144262

Committed r118712: <http://trac.webkit.org/changeset/118712>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Hajime Morrita]

Reopening to attach new patch.

[Hajime Morrita]

Created attachment 144414 [details]
Patch

[Hajime Morrita]

Comment on attachment 144414 [details]
Patch

Oops, posting to wrong bug...