Convert CSSStyleSelector::applyProperty to use function pointers

• Component: CSS
• Status: RESOLVED WONTFIX

[Dimitri Glazkov (Google)]

Instead of a huge switch/if statement, we should have a nice function pointer-based implementation that's more maintainable and hackable.

[Alexey Proskuryakov]

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.

[Ryosuke Niwa]

(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.

[Alexey Proskuryakov]

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

[Luke Macpherson]

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

[Simon Fraser (smfr)]

Debugging through these macros will be pretty miserable.

[Dave Hyatt]

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.

[Luke Macpherson]

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?

[Luke Macpherson]

Created attachment 77179 [details]
Patch WIP

[Luke Macpherson]

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

[WebKit Review Bot]

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.

[WebKit Review Bot]

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

[Build Bot]

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

[Early Warning System Bot]

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

[Eric Seidel (no email)]

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.

[Darin Adler]

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

[Alexey Proskuryakov]

(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.

[Antti Koivisto]

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.

[Luke Macpherson]

Created attachment 79508 [details]
WIP Patch

[Ryosuke Niwa]

(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.

[Luke Macpherson]

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.

[Luke Macpherson]

Created attachment 80615 [details]
Patch

[Antti Koivisto]

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.

[Alexey Proskuryakov]

+//    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.

[Luke Macpherson]

Created attachment 80687 [details]
Patch

[Luke Macpherson]

Created attachment 80885 [details]
Patch

[WebKit Review Bot]

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.

[WebKit Review Bot]

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

[Build Bot]

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

[Gustavo Noronha (kov)]

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

[Early Warning System Bot]

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

[Luke Macpherson]

Created attachment 81029 [details]
Patch

[WebKit Review Bot]

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.

[Build Bot]

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

[Luke Macpherson]

Created attachment 81125 [details]
Patch

[Simon Fraser (smfr)]

Please post some performance data before/after these patches.

[Luke Macpherson]

(In reply to comment #35)
> Please post some performance data before/after these patches.

Will do. Planning to run the chrome page cyclers shortly.

[WebKit Review Bot]

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.

[Luke Macpherson]

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.

[Simon Fraser (smfr)]

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?

[Luke Macpherson]

Created attachment 82281 [details]
Template Demo

[Luke Macpherson]

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.

[Luke Macpherson]

Created attachment 82389 [details]
Template Demo Clean Up

[James Robinson]

Comment on attachment 82389 [details]
Template Demo Clean Up

removing from r? queue since this isn't intended for landing

[Luke Macpherson]

Created attachment 82701 [details]
Patch

[Luke Macpherson]

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.

[Simon Fraser (smfr)]

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

[Luke Macpherson]

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

[Antti Koivisto]

(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.

[Luke Macpherson]

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.

[Antti Koivisto]

(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

[Simon Fraser (smfr)]

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

[Luke Macpherson]

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.

[Antti Koivisto]

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.

[Luke Macpherson]

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

[Luke Macpherson]

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.

[Alexey Proskuryakov]

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