Repository navigation
speedup for / while / if with better bytecode #46711
Description
Activity
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:
- FOR_ITER2 is the same as FOR_ITER except that it does an /absolute/
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) - JUMP_ABS_IF_TRUE /pops/ the top of the stack and does an absolute jump
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 roundAlso, 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 :)- FOR_ITER2 is the same as FOR_ITER except that it does an /absolute/
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)
Removed latest patch, it was half-baked.
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.
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 roundThis 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 loopPlease 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.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 loopA 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.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 commented
on Mar 27, 2008 nnorwitzmannequinMannequinAntoine, 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 commented
on Mar 27, 2008 arigomannequinMannequinCan you see if this simpler patch also gives speed-ups?
(predict_loop.diff)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 roundFinally 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
I've updated for_iter.patch to the latest trunk, merging in bpo-4715.
I also changed tracing a bit so that the first line of a loop doesn't
get traced twice in the first iteration, and added to test_dis to check
that decreasing line numbers work there.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 commented
on Mar 2, 2009 jyasskinmannequinMannequinNo 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 commented
on Mar 3, 2009 jyasskinmannequinMannequinHold 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. :)Is this still relevant / will it get some love in the future?
Is this enhancement still relevant?
BreamoreBoy commented
on Jun 22, 2014 BreamoreBoymannequinMannequinAs 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?
This experiment was abandoned over a decade ago and things have moved on since then. Unless someone objects I will close the issue.
Definitely outdated :-)
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:
bugs.python.org fields: