Make CSSParser::filteredProperties() O(n) instead of O(n^2) and improve readability.
Created attachment 143188 [details] Patch
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.
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.
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.
Created attachment 143416 [details] Patch
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.
Created attachment 143423 [details] Patch
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
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
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.
Created attachment 143695 [details] Patch
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.
Created attachment 143965 [details] Patch
Comment on attachment 143965 [details] Patch Attachment 143965 [details] did not pass win-ews (win): Output: http://queues.webkit.org/results/12808245
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.
Created attachment 144251 [details] Patch
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.
Created attachment 144258 [details] Patch
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.
(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!
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.
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.
(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.
(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.
(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.
(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.
You can see the with-variables version of the code at https://bugs.webkit.org/attachment.cgi?id=143937 line 1166.
To be clear, the only reason for the review- the last time around was the template function issue.
Created attachment 144262 [details] Patch
(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.
(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.
Comment on attachment 144262 [details] Patch Clearing flags on attachment: 144262 Committed r118712: <http://trac.webkit.org/changeset/118712>
All reviewed patches have been landed. Closing bug.
Reopening to attach new patch.
Created attachment 144414 [details] Patch
Comment on attachment 144414 [details] Patch Oops, posting to wrong bug...