ceval: use Wordcode, 16-bit bytecode

[serprex]

BPO	26647
Nosy	@brettcannon, @birkenfeld, @rhettinger, @ncoghlan, @vstinner, @benjaminp, @serhiy-storchaka, @1st1, @MojoVampire, @serprex, @dopplershift
Dependencies	bpo-26881: modulefinder should reuse the dis module
Files	wpy.patch wcpybm.txt: pybench, ccbench, EXTENDED_ARG counts, pycache size exarg_in_funcs.txt: Better EXTENDED_ARG counts 2to3re.txt: Benchmarks: 2to3, regex wpy2.patch: Changes from initial code review wpy3.patch wpy4.patch: f_lasti = -1 module_finder.patch wpy5.patch wpy6.patch wpy7.patch wpy7.patch: Regenerated for review wpy8.patch wpy8.patch: Regenerated for review wpy9.patch wpyA.patch wpyA.patch: Regenerated for review wpyB.patch wpyC.patch wpyD.patch default-May26-03-05-10.log wordcode.patch

^{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/serhiy-storchaka'
closed_at = <Date 2016-11-24.22:20:31.147>
created_at = <Date 2016-03-26.23:27:48.913>
labels = ['interpreter-core', 'performance']
title = 'ceval: use Wordcode, 16-bit bytecode'
updated_at = <Date 2018-03-19.16:29:10.271>
user = 'https://github.com/serprex'

bugs.python.org fields:

activity = <Date 2018-03-19.16:29:10.271>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2016-11-24.22:20:31.147>
closer = 'vstinner'
components = ['Interpreter Core']
creation = <Date 2016-03-26.23:27:48.913>
creator = 'Demur Rumed'
dependencies = ['26881']
files = ['42300', '42324', '42325', '42328', '42331', '42339', '42353', '42446', '42453', '42455', '42659', '42661', '42886', '42912', '42935', '42946', '42947', '42948', '42949', '42950', '43010', '43013']
hgrepos = []
issue_num = 26647
keywords = ['patch']
message_count = 68.0
messages = ['262501', '262542', '262597', '262616', '262622', '262624', '262646', '262647', '262648', '262658', '262660', '262662', '262671', '262677', '262684', '262716', '262758', '262787', '263094', '263263', '263265', '263278', '263334', '263335', '263336', '263337', '263339', '263340', '264256', '264470', '264495', '264496', '264536', '264558', '264604', '264610', '264643', '265285', '265346', '265799', '265917', '265918', '266045', '266053', '266060', '266078', '266090', '266092', '266096', '266101', '266110', '266112', '266114', '266233', '266234', '266240', '266377', '266388', '266407', '266408', '266417', '266420', '266425', '266426', '266432', '281656', '281663', '281789']
nosy_count = 13.0
nosy_names = ['brett.cannon', 'georg.brandl', 'rhettinger', 'ncoghlan', 'vstinner', 'benjamin.peterson', 'python-dev', 'serhiy.storchaka', 'yselivanov', 'abarnert', 'josh.r', 'Demur Rumed', 'Ryan May']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue26647'
versions = ['Python 3.6']

[serprex]

Originally started @ https://github.com/abarnert/cpython/tree/wpy

This patch is based off of https://github.com/serprex/cpython/tree/wpy

It omits importlib.h & importlib_external.h as those are generated

It omits https://github.com/serprex/cpython/blob/wpy/Python/wordcode.md

I got around to benchmarking against building on master rather than using my repo's packaged version, it's currently a 1% speed improvement (every bit counts). I'm testing on an Intel Atom 330 with Linux. Besides the minor perf increase, it generates smaller bytecode & is simpler (peephole now handles EXTENDED_ARG since it isn't too hard to track & while loops become for loops in dis)

Previous discussion: https://mail.python.org/pipermail/python-dev/2016-February/143357.html

pdb works without changes. coverage.py doesn't seem to rely on anything this changes

I modified byteplay to target this change mostly over the course of half an hour before work: https://github.com/serprex/byteplay/blob/master/wbyteplay.py

I'd be interested to hear if this encoding simplifies things for FAT python & the recent work to cache attribute/global lookup

Remaining code issues: peepholer could allocate half the space as it does now for basic block tracking, compile.c & peephole.c repeat themselves on computing instruction size given an argument & how to spit out an instruction given an argument

Breaking change in dis: I've removed HAVE_ARGUMENT. This is to help code fail fast. It could be replaced with IGNORES_ARGUMENT or, as abarnert suggested, a range(90,256) named after the other hasXXXs 'hasarg'

[serprex]

Also missing from this patch is modification of the bytecode magic number

[vstinner]

Sorry, I don't have the context. Can you please explain your change? What did you do? What is the rationale? Do you expect better performances? If yes, please run the Python benchmark suite and post results here. What is the new format of bytecode? etc.

[serprex]

I'll dig up benchmark results when I get home, but I'd be interested to get results on a less wannabe RISC CPU

The change is to have all instructions take an argument. This removes the branch on each instruction on whether to load oparg. It then also aligns instructions to always be 2 bytes rather than 1 or 3 by having arguments only take up 1 byte. In the case that an argument to an instruction is greater than 255, it can chain EXTENDED_ARG up to 3 times. In practice this rarely occurs, mostly only for jumps, & abarnert measured stdlib to be ~5% smaller

The rationale is that this offers 3 benefits: Smaller code size, simpler instruction iteration/indexing (One may now scan backwards, as peephole.c does in this patch), which between the two results in a small perf gain (the only way for perf to be negatively impacted is by an increase in EXTENDED_ARGs, when I post benchmarking I'll also post a count of how many more EXTENDED_ARGs are emitted)

This also means that if I want to create something like a tracer that tracks some information for each instruction, I can allocate an array of codesize/2 bytes, then index off of half the instruction index. This isn't currently done in peephole.c, nor does this include halving jump opargs

I've looked up the 'recent work to cache attribute/global lookup' issue I mentioned: http://bugs.python.org/issue26219
I believe that patch would benefit from this one, but it'd be better to get Yury's opinion that belief

[vstinner]

This also means that if I want to create something like a tracer that tracks some information for each instruction, I can allocate an array of codesize/2 bytes, then index off of half the instruction index. This isn't currently done in peephole.c, nor does this include halving jump opargs

There is something called "inline caching": put the cache between instructions, in the same memory block. Example of paper on CPython:

"Efficient Inline Caching without Dynamic Translation" by Stefan Brunthaler (2009)
https://www.sba-research.org/wp-content/uploads/publications/sac10.pdf

Yury's approach is a standard lookup table: offset => cache. In the issue bpo-26219, he even used two tables: co->co_opt_opcodemap is an array mapping an instruction offset to the offset in the cache, then the second offset is used to retrieve cache data from a second array. You have 3 structures (co_code, co_opt_opcodemap, co_opt), whereas inline caching propose to only use one flat structure (a single array).

The paper promises "improved data locality and instruction decoding effciency".

but "The new combined data-structure requires significantly more space—two native machine words for each instruction byte. To compensate for the additional space requirements, we use a profiling infrastructure to decide when to switch to this new instruction encoding at run time."

Memory footprint and detection of hot code is handled in the issue bpo-26219.

[vstinner]

The change is to have all instructions take an argument. This removes the branch on each instruction on whether to load oparg. (...)

Oh ok, I like that :-) I had the same idea.

Your patch contains unrelated changes, you should revert them to have a change simpler to review.

Removing HAVE_ARGUMENT from opcode.h/dis.py doesn't seem like a good idea. IMHO it's stil useful for dis to show a more compact bytcode. For example, I expect "DUP_TOP", not "DUP_TOP 0", or worse "DUP_TOP 5".

For backward compatibility, I also suggest to keep HAS_ARG() even if it must not be used to decode instructions anymore.

The following obvious change is to use a pointer aligned to 16-bits for co_code to be able to use 16-bit instructions rather than two 8-bit instructions to retrieve the opcode and then the argument in ceval.c (see the issue bpo-25823). I suggest to implement that later to keep the change as simple as possible.

[serprex]

I've attached some benchmarking results as requested

There is 1 failing test which doesn't fail in master for test_trace; the unit test for bpo-9936

[serprex]

To clarify format of extended arg listings: 1st column is the number of instances of EXTENDED_ARG being emitted, 2nd column is length of bytecode, followed by filename

The previous numbers were of modules, which generally are run-once and listing many constants. I've attached a modification where instead I iterated over the code objects inside co_consts from compiling the *.py file. Trunk currently only emits EXTENDED_ARGs for classes (Pdb, & then the rest in Lib/typing.py) so I've omitted it

[brettcannon]

Thanks for the benchmark results, Demur, but I think the benchmarks Victor was talking about hg.Python.org/benchmarks

[rhettinger]

Demur, I think you're on the right track here. It will nice to be rid of the HAVE_ARGUMENT tests and to not have to decode the arguments one-byte at a time. Overall, the patch looks good (although it includes several small unrelated changes). Besides the speed benefit, the code looks cleaner than before.

I was surprised to see that the peephole optimizer grew larger, but the handling of extended arguments is likely worth it even though it adds several new wordy chunks of code.

When it comes to benchmarks, expect a certain amount of noise (especially from those that use I/O or that exercise the C-API more than the pure python bytecode).

[rhettinger]

FWIW, I'm seeing about a 7% improvement to pystone.

[serprex]

While it's good to know benchmarking in core Python goes beyond the microbenchmarks included in the distribution, I'm having some trouble with hg.python.org/benchmarks due to my system only having 256MB of ram

I've attached results for 2 benchmarks: 2to3 & regex