Repository navigation
ceval: use Wordcode, 16-bit bytecode #70834
Description
| BPO | 26647 |
|---|---|
| Nosy | @brettcannon, @birkenfeld, @rhettinger, @ncoghlan, @vstinner, @benjaminp, @serhiy-storchaka, @1st1, @MojoVampire, @serprex, @dopplershift |
| Dependencies | |
| Files |
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']
Activity
serprex commentedon Mar 26, 2016
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 commentedon Mar 28, 2016
Also missing from this patch is modification of the bytecode magic number
vstinner commentedon Mar 29, 2016
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 commentedon Mar 29, 2016
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 commentedon Mar 29, 2016
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 commentedon Mar 29, 2016
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.
[-]Wordcode[/-][+]ceval: use Wordcode, 16-bit bytecode[/+]serprex commentedon Mar 30, 2016
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 commentedon Mar 30, 2016
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 commentedon Mar 30, 2016
Thanks for the benchmark results, Demur, but I think the benchmarks Victor was talking about hg.Python.org/benchmarks
rhettinger commentedon Mar 30, 2016
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 commentedon Mar 30, 2016
FWIW, I'm seeing about a 7% improvement to pystone.
serprex commentedon Mar 30, 2016
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
50 remaining items
vstinner commentedon May 26, 2016
Hi, I ran the CPython benchmark suite (my fork modified to be more stable) on ed4eec682199 (patched) vs 7a7f54fe0698 (base). The patched version contains wordcode (issue bpo-26647) + 16-bit fetch for opcode and oparg (issue bpo-27097).
The speedup is quite nice. Attached default-May26-03-05-10.log contains the full output.
Faster (27):
Slower (1):
Not significat (14):
serhiy-storchaka commentedon May 26, 2016
I think we should make yet few related changes:
These changes break compatibility (already broken by switching to 16-bit bytecode). The first one breaks compatibility with compiled bytecode and needs incrementing the magic number. That is why I think we should do this in this issue.
What is better, provide one large patch or separate simpler patches for every stage?
serhiy-storchaka commentedon May 26, 2016
Here is large patch (not including generated Python/importlib.h and Python/importlib_external.h).
vstinner commentedon May 26, 2016
Serhiy: please open a new issue for your change. While it's related, it's
different enough to deserve its own issue.
By the way , please don't include generated importlib .h file in your
patches.
serhiy-storchaka commentedon May 26, 2016
bpo-27129.
python-dev commentedon Nov 24, 2016
New changeset 303cedfb9e7a by Victor Stinner in branch '3.6':
Fix _PyGen_yf()
https://hg.python.org/cpython/rev/303cedfb9e7a
vstinner commentedon Nov 24, 2016
This issue is done: see issue bpo-27129 for the next step.
serhiy-storchaka commentedon Nov 26, 2016
I left this issue open for documenting the wordcode. Now opened separate bpo-28810 for this.