Bug 46592

A processor can predict branches, but can it predict calling through a pointer? This sounds like a dangerous direction to take performance-wise, although I'm not sure how hot this code is.

(In reply to comment #1) > A processor can predict branches, but can it predict calling through a pointer? This sounds like a dangerous direction to take performance-wise, although I'm not sure how hot this code is. Most "modern" x86 processors (Pentium M for Intel and K10 for AMD or later) implement indirect branch predictions.

Sure - but in practice, devirtualization of calls has been a huge source of performance wins for us.

Created attachment 76440 [details] WIP: proof of concept code

Debugging through these macros will be pretty miserable.

Comment on attachment 76440 [details] WIP: proof of concept code I like the concept. I don't like the name "applicator" though. CSSStyleApplier or CSSStyleMapper might be better, although they still feel somewhat redundant with the name CSSStyleSelector.

Well, I spent the last 1.5 days implementing a code generator to produce this stuff. Generating the header files is a good idea and I intend to do that, but the implementations contain so many special cases that it is exceedingly difficult to encode them all, and the code generator ends up being worse than just hand-writing the implementations and using marcos where appropriate. @smfr: are you happy with moving forward using a generator for the interface only?

Created attachment 77179 [details] Patch WIP

Last patch is just a WIP update. No need to review, but comments welcome.

Attachment 77179 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'WebCore/ChangeLog', u'WebCore/WebCore.xcodeproj/project.pbxproj', u'WebCore/css/CSSStyleApplicator.cpp', u'WebCore/css/CSSStyleSelector.cpp', u'WebCore/css/CSSStyleSelector.h']" exit_code: 1 Last 3072 characters of output: /CSSStyleApplicator.cpp:596: Place brace on its own line for function definitions. [whitespace/braces] [4] WebCore/css/CSSStyleApplicator.cpp:598: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:599: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:600: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:601: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:602: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:642: Place brace on its own line for function definitions. [whitespace/braces] [4] WebCore/css/CSSStyleApplicator.cpp:644: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:645: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:646: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:647: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:667: Place brace on its own line for function definitions. [whitespace/braces] [4] WebCore/css/CSSStyleApplicator.cpp:669: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:670: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:670: l is incorrectly named. Don't use the single letter 'l' as an identifier name. [readability/naming] [4] WebCore/css/CSSStyleApplicator.cpp:671: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:672: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:673: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:771: Place brace on its own line for function definitions. [whitespace/braces] [4] WebCore/css/CSSStyleApplicator.cpp:773: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:774: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:775: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:776: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:790: Place brace on its own line for function definitions. [whitespace/braces] [4] WebCore/css/CSSStyleApplicator.cpp:792: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:793: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:794: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:795: Tab found; better to use spaces [whitespace/tab] [1] WebCore/css/CSSStyleApplicator.cpp:883: More than one command on the same line [whitespace/newline] [4] WebCore/css/CSSStyleApplicator.cpp:898: More than one command on the same line [whitespace/newline] [4] Total errors found: 153 in 5 files If any of these errors are false positives, please file a bug against check-webkit-style.

Attachment 77179 [details] did not build on chromium: Build output: http://queues.webkit.org/results/7242087

Attachment 77179 [details] did not build on win: Build output: http://queues.webkit.org/results/7307102

Attachment 77179 [details] did not build on qt: Build output: http://queues.webkit.org/results/7334027

Comment on attachment 77179 [details] Patch WIP View in context: https://bugs.webkit.org/attachment.cgi?id=77179&action=review I mean, should we just autogenerate this? This fails on a zillion platforms, suggesting you need to update other build systems. I like the idea of reducing the boilerplate in CSSStyleSelector, but if we're going to go to macros, we might as well consider using a little python to autogenate the code instead (like we do with DOM bindings and WebKit2 IPC). > WebCore/ChangeLog:8 > + No new tests. (OOPS!) This is going to cause the cq to fail. You should mention what tests this fixes, or why testing is impossible (if that's the case). > WebCore/css/CSSStyleApplicator.cpp:7 > + * CSSStyleSelector.cpp > + * > + * Created on: Dec 9, 2010 > + * Author: macpherson > + */ > + You need a Google BSD copyright header here.

Seems OK to do this, but we need to measure performance rather than crossing our fingers.

(In reply to comment #5) > Debugging through these macros will be pretty miserable. That's my expectation, too. I have difficulties debugging through SVG code where it uses macros.

Splitting out the style application is a good idea. However, this undebuggable macro/function pointer salad is not an improvement either style or performance wise. I don't see the maintainability or hackability gains either. Any performance testing for this kind of stuff would need to be done on ARM too as indirect branch prediction may be less effective there.

Created attachment 79508 [details] WIP Patch

(In reply to comment #17) > Splitting out the style application is a good idea. However, this undebuggable macro/function pointer salad is not an improvement either style or performance wise. I don't see the maintainability or hackability gains either. I agree. I don't think using all these macros give us any coding-style improvement over the existing code. > Any performance testing for this kind of stuff would need to be done on ARM too as indirect branch prediction may be less effective there. We should probably be testing on both x86 and ARM processors because having lots of small functions may affect L1 & L2 cache hit-rate, and it's really hard to predict what happens. For example, when I implemented recursive and iterative implementations (they're identical otherwise) of merge sort a couple of years ago, recursive version was consistently faster by 10%-30% due to some caching.

1) Shouldn't this be done using a code generator? The header file contents and switch statement can easily be autogenerated from the list of CSS properties. I intend to do that shortly. It is not clear to me that using a code generator for the implementations would be beneficial in this case. I spent a few days implementing a generator before becoming convinced that it wasn't the right approach. The problem is the sheer amount of special case code that is contained here. The CSS property to RenderStyle mapping is not simple, and must be encoded somewhere. There are a substantial number of cases that must be hand-written individually. 2) Macros are hard to debug. Yes and no - there is always a tradeoff between code reuse as enabled by macros and difficulty of understanding the generated output, however using a modern IDE with inline macro expansion means that this isn't as hard as it may first appear. In any case, the existing code has at least as many macros as this code does, so it cannot be described as a net negative. 3) Are switch statements are faster on some architectures? This isn't really an important distinction - if a switch statement is genuinely faster one can always rewrite a function pointer array access in the form of a switch statement. This CL as it stands is still using a switch statement, even though it would now be trivial to switch to a function pointer array. http://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts/ "Since the BTB is only 16 entries long in the Pentium 4 processor, the prediction will eventually fail for loops that are longer than 16 iterations. This limitation can be avoided by unrolling a loop until it is only 16 iterations long. When this is done, a loop conditional will always fit into the BTB, and a branch misprediction will not occur on loop exit." Therefore I am somewhat doubtful that branch prediction will have a measurable impact on a switch statement with more than 300 cases, and that neglecting the many branches contained within. It also seems unlikely that ARM will see any difference in performance - it is a CPU with a much shorter pipeline and most use only static branch prediction. 4) There is no readability / maintainability / hackability gains in this CL. applyProperty() has a very complicated control flow contained in a 2500 line switch statement that is exceedingly difficult to follow. It has hundreds of fall-through cases, return statements hidden inside macros, lots of unreachable code, and lots of nested switch statements where the parent and child variables are shared. By splitting out each of the cases into individual functions it is possible to greatly clarify the flow and separation of this code, and this improves the readability, maintainability and hackability of this code.

Created attachment 80615 [details] Patch

The patch seem to be missing the new file. I'd like to hear actual performance testing results (that is, sampling before/after cases with a profiler) instead of theoretical arguments.

+// CSSPrimitiveValue* primitiveValue = 0; +// if (value->isPrimitiveValue()) +// primitiveValue = static_cast<CSSPrimitiveValue*>(value); +// +// Length l; You probably didn't intend to leave this in a posted patch. I agree with Antti that actual performance data for desktop and mobile platforms is needed to meaningfully discuss this.

Created attachment 80687 [details] Patch

Created attachment 80885 [details] Patch

Attachment 80885 [details] did not pass style-queue: Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1 Source/WebCore/css/CSSStyleApplyProperty.cpp:28: Found other header before a header this file implements. Should be: config.h, primary header, blank line, and then alphabetically sorted. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:32: Alphabetical sorting problem. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:58: Alphabetical sorting problem. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:90: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:312: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:342: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:346: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleSelector.cpp:3054: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleSelector.cpp:3064: Non-label code inside switch statements should be indented. [whitespace/indent] [4] Total errors found: 9 in 6 files If any of these errors are false positives, please file a bug against check-webkit-style.

Attachment 80885 [details] did not build on chromium: Build output: http://queues.webkit.org/results/7686708

Attachment 80885 [details] did not build on win: Build output: http://queues.webkit.org/results/7689069

Attachment 80885 [details] did not build on gtk: Build output: http://queues.webkit.org/results/7681992

Attachment 80885 [details] did not build on qt: Build output: http://queues.webkit.org/results/7686774

Created attachment 81029 [details] Patch

Attachment 81029 [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/CSSStyleApplyProperty.cpp:28: Found other header before a header this file implements. Should be: config.h, primary header, blank line, and then alphabetically sorted. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:32: Alphabetical sorting problem. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:59: Alphabetical sorting problem. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:91: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:313: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:343: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:347: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:3445: Should have a space between // and comment [whitespace/comments] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:3446: Should have a space between // and comment [whitespace/comments] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:3447: Should have a space between // and comment [whitespace/comments] [4] Source/WebCore/css/CSSStyleSelector.cpp:3036: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleSelector.cpp:3046: Non-label code inside switch statements should be indented. [whitespace/indent] [4] Total errors found: 12 in 10 files If any of these errors are false positives, please file a bug against check-webkit-style.

Attachment 81029 [details] did not build on win: Build output: http://queues.webkit.org/results/7692199

Created attachment 81125 [details] Patch

Please post some performance data before/after these patches.

(In reply to comment #35) > Please post some performance data before/after these patches. Will do. Planning to run the chrome page cyclers shortly.

Attachment 81125 [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/CSSStyleApplyProperty.cpp:28: Found other header before a header this file implements. Should be: config.h, primary header, blank line, and then alphabetically sorted. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:32: Alphabetical sorting problem. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:59: Alphabetical sorting problem. [build/include_order] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:91: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:313: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:343: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleApplyProperty.cpp:347: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleSelector.cpp:3036: Else clause should never be on same line as else (use 2 lines) [whitespace/newline] [4] Source/WebCore/css/CSSStyleSelector.cpp:3046: Non-label code inside switch statements should be indented. [whitespace/indent] [4] Total errors found: 9 in 11 files If any of these errors are false positives, please file a bug against check-webkit-style.

Ran the Chromium Page cyclers and didn't find any significant difference between before and after performance. Both builds were at webkit r77686 and run on a current 12-core Mac Pro. original (ms): 22719, 22872, 22464, 22563, 22574, 22563, 22683 avg: 22634 modified (ms): 22751, 22572, 22913, 22203, 22536, 22753, 22903 avg: 22665 This CL had no significant impact on overall page load times for the set of pages tested.

Comment on attachment 81125 [details] Patch I still feel like this isn't really a win. There's too much buried in macros, which will be hell to debug. Would something like AnimationBase's PropertyWrappers be more appropriate?

Created attachment 82281 [details] Template Demo

Comment on attachment 82281 [details] Template Demo Not for review, intended to demonstrate what using templates instead of macros would be like. Code becomes much more verbose, but I can understand why some people would consider it better style. I don't yet know the performance implications of doing it this way, and would need to convert the whole thing to find out.

Created attachment 82389 [details] Template Demo Clean Up

Comment on attachment 82389 [details] Template Demo Clean Up removing from r? queue since this isn't intended for landing

Created attachment 82701 [details] Patch

Did some page cycler runs with the last patch, it didn't appear to make any real difference to overall page load times. Modified Unmodified 22,331 22,832 22,440 22,454 22,474 22,622 22,419 23,930 22,661 22,578 22,486 22,615 22,568 22,465 22,331 22,480 22,268 22,585 22,303 22,404 average: 22,428 22,697 median: 22,430 22,582 stddev: 125 450 deleting row 4 (which looked like a possibly invalid result for the unmodified case) average: 22,429 22,559 median: 22,440 22,578 stddev: 132 129 How I'd like to proceed is with a bunch of small patches that implement a handful fo related properties at a time. That should make the reviews straightforward and allow incremental testing of the changes.

You should get buy-in from Dave Hyatt before proceeding.

macpherson: dhyatt: would you mind weighing in on https://bugs.webkit.org/show_bug.cgi?id=46592 ? smfr suggests your buy-in is required before proceeding. dhyatt: i lovet he idea of converting to function pointers dhyatt: been wanting to do that for ages macpherson: the latest patch isn't precisely function pointers though - it is doing dispatch through looking up an implementation object. dhyatt: anything to ditch the giant switch statement sounds good to me dhyatt: as long as it's fast macpherson: since the static function pointer implementation got a lot of objections on the grounds of too many macros. dhyatt: i see macpherson: i haven't seen any performance difference on the page cyclers (well, actually the runs doing lookups were slightly faster) macpherson: smfr: do you have anything in particular you wanted dhyatt to comment on? dhyatt: the approach looks fine to me, but i don't have strong feelings about it smfr: just whether he's ok with the general approach dhyatt: someone may care more than i do smfr: dhyatt: it's basically like the Animation ProperyWrapper things dhyatt: yup i saw dhyatt: it looks fine to me smfr: and i like the way those turned out

(In reply to comment #45) > Did some page cycler runs with the last patch, it didn't appear to make any real difference to overall page load times. I don't think "page cycler" is the right way to test performance here. You need to use profiler to measure the samples under applyProperty() on real world scenarios (over full page load of web sites). CSSStyleSelector::applyProperty is currently the seconds hottest single WebCore function on typical web sites and no regression here can be allowed.

Profiled some page loads using shark on OSX with the modifications in place. Total time spent in applyProperty for www.apple.com and mail.google.com was only 0.1%. I didn't actually see any samples hit in the new code.

(In reply to comment #49) > Profiled some page loads using shark on OSX with the modifications in place. Total time spent in applyProperty for www.apple.com and mail.google.com was only 0.1%. I didn't actually see any samples hit in the new code. Please test pages that have some serious styling. Here are some: news.bbc.co.uk engadget.com wsj.com

You may also find that it's more useful to instrument the code using currentTime().

Even on those pages it doesn't seem terribly hot: www.bbc.co.uk: 0.3% www.engadget.com: 0.1% www.wsj.com: 0.1% Since applyProperty doesn't do much - just maps a property/value pair onto a RenderStyle object, perhaps then it is unsurprising that the total cost isn't very significant.

That is strange. On news.bbc.co.uk I see this having ~2.5% of the engine thread samples (0.3% in a single function in a non-micro benchmark would be hot too). Anyway, that wasn't really the question I asked. If you attach a patch that applies to the current tot I can test it too.

Hi Antti, the current patch is at https://bugs.webkit.org/show_bug.cgi?id=54707

I followed Antti's measurement approach of counting profiler hits in applyProperty. Initially this did show some performance loss, we looked at the assembly output and found it was due to function call overheads. I have updated the hot code-paths to make them inline correctly and it now appears faster than the existing code by that metric. I have updated bug 54707 with the measurement details and a new patch that inlines the property map accessors.

This is a task bug with a long obsolete patch, marking resolved.