Faster opcode dispatch on gcc

[pitrou]

BPO	4753
Nosy	@malemburg, @akuchling, @rhettinger, @facundobatista, @gpshead, @jcea, @db3l, @abalkin, @pitrou, @tiran, @devdanzin, @rbtcollins, @ned-deily, @djc, @bitdancer, @jab
Files	amd-athlon64-x2-pybench.txt intel-core2-mobile-pybench.txt amd-athlon64-x2-suncc-pybench.txt amd-athlon64-x2-gcc-sunos-pybench.txt threadedceval5.patch pybench.sum.PPC: Pybench summary for Mac G5 pybench.sum.Intel: Pybench summary for MacBook Pro (Intel Core2 Duo) amd-athlon64-x2-64bit-pybench.txt ceval.i.unthreaded: PPC (G5) unthreaded eval assembler ceval.i.threaded: PPC (G5) threaded eval assembler abstract-switch.diff abstract-switch-reduced.diff: Fixed version of abstract-switch.diff, without extraneous changes (IMHO) restore-old-oparg-load.diff: Additional fix, on top of threadedceval5.patch and abstract-switch-reduced.diff, to restore back performances and have no switch at all reenable-static-prediction.diff: Reenable static opcode prediction on top of the rest pitrou_dispatch_2.7.patch: threadedceval5.patch ported to trunk (2.7) vmgen_2.7.patch: vmgen (GForth)-based dispatch optimization with simple superinstructions threadedceval6.patch threadedceval6-py254.patch: threadedceval6 for Python 2.5.4 ceval.c.threadcode-tidyup.patch: threaded code tidy up in eval.c newfile.zip: ceval.c and opcode_targets.h cgoto_py2710_hg_final.patch: Computed Goto Patch for Python 2.7.10

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/gpshead'
closed_at = <Date 2010-07-19.23:55:22.123>
created_at = <Date 2008-12-26.21:09:38.283>
labels = ['interpreter-core', 'performance']
title = 'Faster opcode dispatch on gcc'
updated_at = <Date 2015-06-02.21:38:03.306>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2015-06-02.21:38:03.306>
actor = 'db3l'
assignee = 'gregory.p.smith'
closed = True
closed_date = <Date 2010-07-19.23:55:22.123>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2008-12-26.21:09:38.283>
creator = 'pitrou'
dependencies = []
files = ['12512', '12513', '12521', '12522', '12524', '12545', '12546', '12551', '12553', '12555', '12584', '12633', '12634', '12635', '12687', '12705', '12769', '12824', '13392', '14521', '39527']
hgrepos = []
issue_num = 4753
keywords = ['patch']
message_count = 117.0
messages = ['78306', '78307', '78362', '78363', '78364', '78616', '78620', '78628', '78629', '78651', '78653', '78656', '78657', '78658', '78660', '78663', '78685', '78686', '78687', '78688', '78689', '78691', '78708', '78711', '78722', '78730', '78731', '78735', '78736', '78748', '78808', '78828', '78831', '78834', '78837', '78871', '78872', '78898', '78899', '78910', '78911', '78915', '78921', '78923', '78925', '78956', '79032', '79033', '79034', '79035', '79037', '79051', '79053', '79056', '79058', '79077', '79080', '79105', '79123', '79264', '79302', '79321', '79335', '79365', '79505', '79530', '79532', '79536', '79537', '79539', '79541', '79545', '79605', '79627', '79688', '79695', '79699', '79720', '79722', '79734', '79835', '79980', '79984', '79985', '80324', '80489', '80515', '80571', '80669', '80717', '80828', '80832', '80833', '80834', '80838', '80867', '80881', '80882', '81120', '81166', '81341', '81361', '83959', '84736', '84764', '84770', '85838', '90688', '110842', '244229', '244231', '244256', '244329', '244617', '244620', '244628', '244693']
nosy_count = 31.0
nosy_names = ['lemburg', 'akuchling', 'collinwinter', 'rhettinger', 'facundobatista', 'gregory.p.smith', 'jcea', 'spiv', 'db3l', 'aimacintyre', 'belopolsky', 'ggenellina', 'pitrou', 'christian.heimes', 'ajaksu2', 'jyasskin', 'rbcollins', 'kevinwatters', 'ned.deily', 'djc', 'ralph.corderoy', 'bboissin', 'r.david.murray', 'blaisorblade', 'theatrus', 'Ringding', 'jab', 'mdionisio', 'willp', 'python-dev', 'parasa']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue4753'
versions = ['Python 3.1']

[pitrou]

This patch implements what is usually called "threaded code" for the
ceval loop on compilers which support it (only gcc). The idea is that
there is a separate opcode dispatch epilog at the end of each opcode,
which allows the CPU to make much better use of its branch prediction
capabilities. The net result is a 15-20% average speedup on pybench and
pystone, with higher speedups on very tight loops (see below for the
full pybench result chart).

The opcode jump table is generated by a separate script which is called
as part of the Makefile (just as the asdl building script already is).

On compilers other than gcc, performance will of course be unchanged.

Test minimum run-time average run-time
this other diff this other
diff
-------------------------------------------------------------------------------
BuiltinFunctionCalls: 100ms 107ms -7.1% 101ms 110ms
-8.2%
BuiltinMethodLookup: 76ms 106ms -28.1% 78ms 106ms
-26.5%
CompareFloats: 108ms 141ms -23.2% 108ms 141ms
-23.2%
CompareFloatsIntegers: 171ms 188ms -9.4% 173ms 204ms
-15.3%
CompareIntegers: 165ms 213ms -22.6% 168ms 224ms
-25.1%
CompareInternedStrings: 127ms 169ms -24.6% 127ms 169ms
-24.8%
CompareLongs: 95ms 124ms -23.1% 95ms 126ms
-24.5%
CompareStrings: 109ms 136ms -20.2% 111ms 139ms
-19.9%
ComplexPythonFunctionCalls: 131ms 150ms -12.4% 136ms 151ms
-10.2%
ConcatStrings: 159ms 171ms -6.9% 160ms 173ms
-7.4%
CreateInstances: 148ms 157ms -5.6% 150ms 158ms
-4.9%
CreateNewInstances: 112ms 117ms -4.3% 112ms 118ms
-4.6%
CreateStringsWithConcat: 144ms 198ms -27.3% 148ms 199ms
-25.7%
DictCreation: 90ms 104ms -13.3% 90ms 104ms
-13.1%
DictWithFloatKeys: 117ms 153ms -23.7% 117ms 154ms
-24.0%
DictWithIntegerKeys: 104ms 153ms -32.3% 104ms 154ms
-32.5%
DictWithStringKeys: 90ms 140ms -35.7% 90ms 141ms
-36.3%
ForLoops: 100ms 161ms -38.1% 100ms 161ms
-38.1%
IfThenElse: 123ms 170ms -28.0% 125ms 171ms
-27.1%
ListSlicing: 142ms 141ms +0.3% 142ms 142ms
+0.2%
NestedForLoops: 135ms 190ms -29.0% 135ms 190ms
-29.0%
NormalClassAttribute: 249ms 281ms -11.5% 249ms 281ms
-11.3%
NormalInstanceAttribute: 110ms 153ms -28.2% 111ms 154ms
-28.1%
PythonFunctionCalls: 106ms 130ms -18.7% 108ms 131ms
-17.2%
PythonMethodCalls: 151ms 169ms -10.1% 152ms 169ms
-9.8%
Recursion: 183ms 242ms -24.7% 191ms 243ms
-21.4%
SecondImport: 142ms 138ms +2.7% 144ms 139ms
+3.4%
SecondPackageImport: 146ms 149ms -2.3% 148ms 150ms
-1.5%
SecondSubmoduleImport: 201ms 193ms +3.9% 201ms 195ms
+3.4%
SimpleComplexArithmetic: 90ms 112ms -19.6% 90ms 112ms
-19.8%
SimpleDictManipulation: 172ms 230ms -25.2% 173ms 231ms
-25.0%
SimpleFloatArithmetic: 98ms 133ms -26.3% 99ms 137ms
-27.9%
SimpleIntFloatArithmetic: 134ms 175ms -23.6% 138ms 176ms
-21.6%
SimpleIntegerArithmetic: 134ms 183ms -26.8% 141ms 183ms
-23.1%
SimpleListManipulation: 91ms 143ms -36.3% 93ms 143ms
-35.1%
SimpleLongArithmetic: 88ms 108ms -17.9% 91ms 109ms
-16.2%
SmallLists: 127ms 162ms -21.6% 129ms 164ms
-21.2%
SmallTuples: 149ms 177ms -15.6% 151ms 178ms
-15.1%
SpecialClassAttribute: 423ms 426ms -0.7% 426ms 430ms
-0.9%
SpecialInstanceAttribute: 110ms 154ms -28.2% 111ms 154ms
-28.3%
StringMappings: 428ms 443ms -3.4% 432ms 449ms
-3.7%
StringPredicates: 124ms 161ms -23.1% 125ms 162ms
-22.7%
StringSlicing: 207ms 223ms -7.1% 208ms 228ms
-8.7%
TryExcept: 72ms 166ms -56.3% 73ms 166ms
-56.2%
TryFinally: 93ms 120ms -22.9% 93ms 124ms
-25.2%
TryRaiseExcept: 52ms 64ms -19.2% 52ms 65ms
-19.2%
TupleSlicing: 177ms 195ms -9.1% 178ms 198ms
-10.2%
WithFinally: 147ms 163ms -10.2% 147ms 164ms
-10.1%
WithRaiseExcept: 156ms 173ms -10.1% 157ms 174ms
-9.7%
-------------------------------------------------------------------------------
Totals: 6903ms 8356ms -17.4% 6982ms 8443ms
-17.3%

[pitrou]

Armin, by reading the pypy-dev mailing-list it looks like you were
interested in this.

[malemburg]

On 2008-12-26 22:09, Antoine Pitrou wrote:

This patch implements what is usually called "threaded code" for the
ceval loop on compilers which support it (only gcc). The idea is that
there is a separate opcode dispatch epilog at the end of each opcode,
which allows the CPU to make much better use of its branch prediction
capabilities. The net result is a 15-20% average speedup on pybench and
pystone, with higher speedups on very tight loops (see below for the
full pybench result chart).

Now I know why you want opcode stats in pybench :-)

This looks like a promising approach. Is is possible to backport
this change to Python 2.x as well ?

[pitrou]

This looks like a promising approach. Is is possible to backport
this change to Python 2.x as well ?

Certainly.

[pitrou]

This new patch uses a statically initialized jump table rather than
specific initialization code.

[tiran]

I'm having trouble understanding the technique of the jump table. Can
you provide some links to papers that explain the threaded code? I'm
interested in learning more.
How does your implementation compare to the GForth based threaded code
speedwise?

[pitrou]

I'm having trouble understanding the technique of the jump table. Can
you provide some links to papers that explain the threaded code? I'm
interested in learning more.

I haven't read any papers. Having a jump table in itself isn't special
(the compiler does exactly that when compiling the switch() statement).
What's special is that a dedicated indirect jump instruction at the end
of each opcode helps the CPU make a separate prediction for which opcode
follows the other one, which is not possible with a switch statement
where the jump instruction is shared by all opcodes. I believe that's
where most of the speedup comes from.

If you read the patch it will probably be easy to understand.

I had the idea to try this after a thread on pypy-dev, there are more
references there:
http://codespeak.net/pipermail/pypy-dev/2008q4/004916.html

How does your implementation compare to the GForth based threaded code
speedwise?

Don't know! Your experiments are welcome. My patch is far simpler to
integrate though (it's small, introduces very few changes and does not
break any existing tests).

[tiran]

I haven't read any papers. Having a jump table in itself isn't special
(the compiler does exactly that when compiling the switch() statement).
What's special is that a dedicated indirect jump instruction at the end
of each opcode helps the CPU make a separate prediction for which opcode
follows the other one, which is not possible with a switch statement
where the jump instruction is shared by all opcodes. I believe that's
where most of the speedup comes from.

If you read the patch it will probably be easy to understand.

You are right. It's easier to understand after I've learned how the
opcode_targets table is working. Previously I didn't know that one can
store the address of a label in an array. Before I got it I wondered
where the pointers were defined. Is this a special GCC feature? I
haven't seen it before.

Don't know! Your experiments are welcome. My patch is far simpler to
integrate though (it's small, introduces very few changes and does not
break any existing tests).

Yes, your patch is much smaller, less intrusive and easier to understand
with a little background in CS.

[pitrou]

Is this a special GCC feature?

Yes, it is.
http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

[pitrou]

This new patch adds some detailed comments, at Jason Orendorff's request.

[avassalotti]

You may want to check out bpo-1408710 in which a similar patch was
provided, but failed to deliver the desired results.

I didn't get the advertised ~15% speed-up, but only 4% on my Intel Core2
laptop and 8% on my AMD Athlon64 X2 desktop. I attached the benchmark
results.

The patch looks pretty clean. Here is a few things that caught my
attention while reading your patch.

First, you should rename opcode_targets.c to opcode_targets.h. This will
make it explicit that the file is not compiled, but just included.

Also, the macro USE_THREADED_CODE should be renamed to something else;
the word "thread" is too tightly associated with multi-threading.
Furthermore, threaded code simply refers to code consisting only of
function calls. Maybe, USE_COMPUTED_GOTO or USE_DIRECT_DISPATCH would be
better.

Finally, why do you disable your patch when DYNAMIC_EXECUTION_PROFILE or
LLTRACE is enabled? I tested your patch with both enabled and I didn't
see any test failures.

By the way, SUNCC also supports GCC's syntax for labels as values
(http://docs.sun.com/app/docs/doc/819-5265/bjabt?l=en&a=view).

[smontanaro]

Works pretty well for me on my MacBook Pro, but on my G5 it performed
abysmally. In fact, it ran so much worse that I cleaned up my sandbox
and did both checks all over again to make sure I didn't mess something
up. It looks like my MacBook Pro saw about a 7% improvement while my
G5 saw a 14% degradation. Both computers are running Mac OS X 10.5.6
with the latest Xcode - 3.1.2. On both computers gcc -v reports 4.0.1,
Apple build 5490.

If this is applied to the core I think it will have to select for more
than just gcc. It will also have to select based on the instruction set
architecture.

[pitrou]

Works pretty well for me on my MacBook Pro, but on my G5 it performed
abysmally. In fact, it ran so much worse that I cleaned up my sandbox
and did both checks all over again to make sure I didn't mess something
up. It looks like my MacBook Pro saw about a 14% degradation. Both
computers are running Mac OS X 10.5.6 with the latest Xcode - 3.1.2.
On both computers gcc -v reports 4.0.1, Apple build 5490.

You're sure you didn't compile in debug mode or something? Just
checking.