1171842 - Use jump table to replace the nested if statements in style struct list

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Xidorn Quan [:xidorn] UTC+11]

Currently, we generate a tree of nested if statements to select compute function for a given SID. We should replace it with a method array of compute functions, and use a indirect call for it.

The main advantage of this change is that it should improve the performance. Multiple if statements have significantly negative effect on branch prediction. Using the method array could simply remove all of those conditions. It should also reduce the size of both the generated code and the final binary.

Comment 1

[Xidorn Quan [:xidorn] UTC+11]

Attachment: patch

Comment 2

[Xidorn Quan [:xidorn] UTC+11]

Seems to be the reverse of bug 210550 :)

It is said that jump table hurts pipeline and causes cache misses, but shouldn't failure of branch prediction hurt more performance?

Intel replaced the big switch in Python bytecode interpreter with a jump table, and saw 15%-20% performance gain, which is from the removal of one single condition check. [1]

Hmmm, but well, three condition vs. indirect function call. I'm not sure which is better. But as the pipeline of processors becoming longer, I suppose branch prediction failure should cost more.

[1] http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables

Comment 3

[Xidorn Quan [:xidorn] UTC+11]

It seems the main cost of an indirect call is that the processor needs to wait until the target is known. But the compiler should be able to rearrange the code and the processor could also do some out-of-order execution to mitigate this cost. If they can't, we could simply move the getting code to the beginning of WalkRuleTree function.

Comment 4

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 8615860 [details] [diff] [review]
patch

Please test the performance, and re-request review if it actually *is* faster.

Comment 5

[Xidorn Quan [:xidorn] UTC+11]

Attachment: walktree_pref.zip

You can run this pref test by executing "make" in the extracted directory. The column after "original: " is the time for the current if-tree style. The column after "new: " is the time for the jump table style.

In my machine, this test shows that the new method is at least ~17% faster than the if-tree style.

Comment 6

[Xidorn Quan [:xidorn] UTC+11]

If I move the rand() call out from the inner loops, via either moving that to the outer loop or initializing a random table at the very beginning, the test shows the jump table is ~40% faster than if-tree on my machine.

Comment 7

[Xidorn Quan [:xidorn] UTC+11]

Attachment: walktree_pref.zip

Comment 8

[Xidorn Quan [:xidorn] UTC+11]

Note that if LTO is enabled for this pref test, the if-tree one would take advantage, as the compiler will inline the target Compute*Data methods and then strip the whole WalkRuleTree1 method to a nop since nothing is actually done in it, while the compiler cannot reason out the same optimization for WalkRuleTree2.

However, if you add any code in the Compute*Data methods, even if the compiler can inline those methods and thus remove one function call for if-tree, jump table is still ~10% faster. As our Compute*Data methods are generally long enough that the compiler usually won't inline them, jump table is much faster.

Comment 9

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/2b37fea15848

Comment 10

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/2b37fea15848