Repository navigation
speedup for / while / if with better bytecode #46711
Description
| BPO | 2459 |
|---|---|
| Nosy | @rhettinger, @gpshead, @jcea, @pitrou, @giampaolo, @tiran, @djc, @phsilva |
| 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 = None
closed_at = None
created_at = <Date 2008-03-22.22:25:03.988>
labels = ['interpreter-core', 'performance']
title = 'speedup for / while / if with better bytecode'
updated_at = <Date 2014-06-22.12:04:07.520>
user = 'https://github.com/pitrou'bugs.python.org fields:
activity = <Date 2014-06-22.12:04:07.520>
actor = 'BreamoreBoy'
assignee = 'jyasskin'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2008-03-22.22:25:03.988>
creator = 'pitrou'
dependencies = []
files = ['9877', '12923', '13227']
hgrepos = []
issue_num = 2459
keywords = ['patch']
message_count = 31.0
messages = ['64343', '64359', '64364', '64367', '64383', '64506', '64537', '64572', '64573', '64577', '64599', '64603', '66027', '68687', '80591', '80593', '80598', '80995', '81029', '81958', '81962', '81976', '82556', '82557', '83003', '83012', '83022', '83088', '106883', '192575', '221249']
nosy_count = 15.0
nosy_names = ['nnorwitz', 'collinwinter', 'rhettinger', 'gregory.p.smith', 'jcea', 'tzot', 'pitrou', 'giampaolo.rodola', 'christian.heimes', 'jyasskin', 'stutzbach', 'lauromoura', 'djc', 'phsilva', 'BreamoreBoy']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'languishing'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue2459'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4']
Activity
pitrou commentedon Mar 22, 2008
This is a preliminary patch to speedup for and while loops (it will also
be able to speedup list comps and gen comps, if I get to do it).
The patch works by putting the loop condition test at the end of loop,
which allows removing one JUMP_ABSOLUTE byte code out of the critical path.
For this two new opcodes are introduced:
jump if the iterator is /not/ exhausted (when other uses of FOR_ITER are
replaced with FOR_ITER2, we can of course restore the original naming)
if its value is true
Some micro-benchmarks:
./python -m timeit "for x in xrange(10000): pass"
Before: 1000 loops, best of 3: 782 usec per loop
After: 1000 loops, best of 3: 412 usec per loop
./python -m timeit "x=100" "while x: x -= 1"
Before: 10000 loops, best of 3: 22.1 usec per loop
After: 100000 loops, best of 3: 16.6 usec per loop
./python Tools/pybench/pybench.py -t ForLoops
Before: 365ms per round
After: 234ms per round
Also, pystone gets 5% faster (from 43300 to 45800).
Now for the less shiny things:
I'm having problems modifying the pure Python compiler module. For
some reasons it seems to have stricter requirements than compile.c
itself does (!); I get some assertion error in
compiler.pyassem.FlowGraph.fixupOrderHonorNext as soon as a loop gets
non-trivial.
Line numbers probably need to be fixed. The lnotab format may even
have to be adapted in order to accomodate non-monotonically increasing
line numbers.
Is there some interest in this patch? If yes, I'd like to have your
input on the two bullet points above :)
pitrou commentedon Mar 23, 2008
This new patch includes surgery to the compiler package (especially
flowgraph trickery) in order to make it work with the new opcodes. I
think my changes are sane but since the package seems basically
untested, unmaintained and almost unused, there may be some glitches.
However, test_compiler passes.
(test_dis will need to be updated for the new opcodes, not a big deal)
pitrou commentedon Mar 23, 2008
Removed latest patch, it was half-baked.
pitrou commentedon Mar 23, 2008
This new patch should be ok. The block ordering algorithm in
compiler.pyassem looks entirely clean now, to the extent that the
previous "fixup" hacks have been disabled.
Attaching loops3.py.
pitrou commentedon Mar 23, 2008
loops4.patch adds a mechanism to avoid blocking signal catching in empty
loops (such as "for x in it: pass" or "while x: pass"). Much of the
speedup is still retained.
./python -m timeit "for x in xrange(10000): pass"
Before: 1000 loops, best of 3: 737 usec per loop
After: 1000 loops, best of 3: 438 usec per loop
./python -m timeit "x=100" "while x: x -= 1"
Before: 10000 loops, best of 3: 21.7 usec per loop
After: 100000 loops, best of 3: 16.6 usec per loop
./python Tools/pybench/pybench.py -t ForLoops
Before: 364ms per round
After: 242ms per round
pitrou commentedon Mar 25, 2008
By the way, the compiler package fix has been isolated and cleaned up as
part of bpo-2472. Maybe it would be nice to start with that one.
pitrou commentedon Mar 26, 2008
This new patch also updates the code generation for list comprehensions.
Here are some micro-benchmarks:
./python -m timeit -s "l = range(100)" "[x for x in l]"
Before: 100000 loops, best of 3: 14.9 usec per loop
After: 100000 loops, best of 3: 12.5 usec per loop
./python -m timeit -s "l = range(100)" "[x for x in l if x]"
Before: 10000 loops, best of 3: 24.1 usec per loop
After: 100000 loops, best of 3: 18.8 usec per loop
./python -m timeit -s "l = range(100)" "[x for x in l if not x]"
Before: 100000 loops, best of 3: 15.5 usec per loop
After: 100000 loops, best of 3: 11.9 usec per loop
Please note that this patch is orthogonal with Neal's patch in bpo-2183, so
the two combined should be quite interesting for the list comprehensions
bytecode.
pitrou commentedon Mar 26, 2008
This new patch completes the bytecode modifications. For/while loops as
well as list comprehensions and generator expressions are a bit faster
now. Also, as a side effect I've introduced a speed improvement for "if"
statements and expressions...
Some micro-benchmarks (completing the ones already given above):
./python Tools/pybench/pybench.py -t IfThenElse
Before: 167ms per round
After: 136ms per round
./python -m timeit -s "y=range(100)" "sum(x for x in y)"
Before: 10000 loops, best of 3: 20.4 usec per loop
After: 100000 loops, best of 3: 17.9 usec per loop
./python -m timeit -s "y=range(100)" "sum(x for x in y if x)"
Before: 10000 loops, best of 3: 28.5 usec per loop
After: 10000 loops, best of 3: 23.3 usec per loop
./python -m timeit -s "y=range(100)" "sum(x for x in y if not x)"
Before: 100000 loops, best of 3: 16.4 usec per loop
After: 100000 loops, best of 3: 12.1 usec per loop
./python -m timeit -s "x,y,z=1,2,3" "x if y else z"
Before: 1000000 loops, best of 3: 0.218 usec per loop
After: 10000000 loops, best of 3: 0.159 usec per loop
A couple of tests seem to be failing in obscure ways in the test suite,
I'll try to examine them. Most of the test suite runs fine though.
pitrou commentedon Mar 26, 2008
Ok, the fix for the bizarre failures was really simple. Now the only
failing tests are in test_trace (because it makes assumptions regarding
the bytecode that aren't true anymore, I'll have to adapt the tests).
nnorwitz commentedon Mar 27, 2008
Antoine, I hope to look at this patch eventually. Unfortunately, there
are too many build/test problems that need to be resolved before the
next release. If you can help out with those, I will be able to review
this patch sooner.
arigo commentedon Mar 27, 2008
Can you see if this simpler patch also gives speed-ups?
(predict_loop.diff)
pitrou commentedon Mar 27, 2008
Armin, your patch gives a speed-up for "for" loops and comprehensions,
although a bit less. Also, it doesn't speed up "while" loops and "if"
statements at all. For some reasons it also appears to make pystone a
bit slower. Here are some micro-benchmarks:
./python -m timeit "for x in xrange(10000): pass"
Before: 1000 loops, best of 3: 758 usec per loop
After: 1000 loops, best of 3: 483 usec per loop
./python -m timeit "x=100" "while x: x -= 1"
Before: 10000 loops, best of 3: 21.8 usec per loop
After: 10000 loops, best of 3: 21.6 usec per loop
./python -m timeit -s "l = range(100)" "[x for x in l]"
Before: 100000 loops, best of 3: 14.9 usec per loop
After: 100000 loops, best of 3: 13.3 usec per loop
./python -m timeit -s "l = range(100)" "[x for x in l if x]"
Before: 10000 loops, best of 3: 23.9 usec per loop
After: 10000 loops, best of 3: 22.3 usec per loop
./python -m timeit -s "l = range(100)" "[x for x in l if not x]"
Before: 100000 loops, best of 3: 15.8 usec per loop
After: 100000 loops, best of 3: 13.9 usec per loop
./python Tools/pybench/pybench.py -t IfThenElse
Before: 164ms per round
After: 166ms per round
pitrou commentedon Apr 30, 2008
Finally I had to slightly change the lnotab format to have the right
tracing semantics: the change is that line number increments are now
signed bytes rather than unsigned.
Still, there is a small change in tracing behaviour (see test_trace.py):
the for statement is traced twice in the first loop iteration, that's
because the iterator object is retrieved (GET_ITER) at the beginning of
the loop while the next iterator value is fetched (FOR_ITER) at the end
of the loop. I don't believe this is very painful.
All in all, the whole test suite now passes fine. The performance
numbers are the same as before.
13 remaining items
pitrou commentedon Mar 2, 2009
Thanks a lot!
By the way, why do you bench cPickle? Does your test call Python code
significantly?
Overall, the results look positive although not overwhelming.
jyasskin commentedon Mar 2, 2009
No particular reason for cPickle. It sometimes shows when we've caused
problems by increasing the code size, and shows the size of any random
effects that the compiler causes by moving code around. Could you
double-check the patch to see if I did anything dumb?
jyasskin commentedon Mar 3, 2009
Hold off on reviewing this. There's one bug around the peepholer not
turning itself off when line numbers skip by more than 127, and another
around the traceback generator still assuming line numbers are unsigned.
I'll post another patch when those are fixed and tested. I may not get
to it for a day or two, so someone else is welcome to update the patch
instead. :)
djc commentedon Jun 2, 2010
Is this still relevant / will it get some love in the future?
tiran commentedon Jul 7, 2013
Is this enhancement still relevant?
BreamoreBoy commentedon Jun 22, 2014
As a lot of work has gone into this it saddens me to see it languishing. Surely if Python performance is to be improved the bytecode for conditionals and loops is one of the places if not the place to do it? Are there any names missing from the nosy list that ought to be there?
iritkatriel commentedon Sep 1, 2022
This experiment was abandoned over a decade ago and things have moved on since then. Unless someone objects I will close the issue.
pitrou commentedon Sep 1, 2022
Definitely outdated :-)