Repository navigation
Consider FOR_ITER family for specialization? #67
Description
Activity
- changed the title
[-]Consider FOR_ITER family of specialization?[/-][+]Consider FOR_ITER family for specialization?[/+]on Jul 13, 2021 I definitely don't think that
for x in (1, 2, 3)orfor x in [1, 2, 3]are common enough to bother. I have been eyeingfor i in range()myself, but before the specialization framework was implemented it seemed tricky.There may have been some previous hacks, see comments by user @heeres in #42. IIRC the idea was to reuse the integer object rather than allocating a new one. However, making sure that there are no other users of that same object is tricky.
Of course, if we ever get tagged integers, that would be the right approach.
Also, in case you hadn't looked yet, range() already has two entirely distinct implementations depending on whether the end points fit in a machine word. But of course this just saves doing the increment using integer objects, the result still has to be allocated. (A free list might help too?)
Reacted by Ken JinOops I didn't see that issue. It's cool that the solutions and problems somewhat converge with this issue. Also those are some really nice hacks by Heeres!
You mentioned trying out FOR_ITER/{STORE_NAME|STORE_FAST} combined instruction. This makes me wonder if the super instruction would be faster than individually specializing FOR_ITER and STORE. Or maybe the fastest would be specializing that combined instruction ;)?
We’ll, there’s not much to specialize about STORE_FAST, and STORE_NAME isn’t worth it (a for loop at the module level?!) So the super-instruction seems a good idea; specializing it for range() seems good too.
You might try to measure how often ‘for i in range(…)’ actually occurs. I think in my own code I use enumerate() more than range(), but that is harder to specialize (or is it?). It would be a nice win to avoid needing the tuple there (this would need help from the compiler).
One possible way to speed up tight
forloops is to add aFOR_ENDopcode, which would be likeFOR_ITERbut reverse the direction of branch. It would not branch when the iterator is exhausted.
Sofor x: bodywould compile to:FOR_ITER end loop: body FOR_END loop end:instead of
loop: FOR_ITER end body JUMP_ABSOLUTE loop end:I don't know if this would be profitable, but might be worth an experiment.
After some hacking around, I think my original approach is pretty naive --
next(iter)seems to be very little overhead (just callingtp_iternextwhich increments and creates aPyLong).User heeres is right that most of the overhead is from the memory allocation. I'm surprised though -- I expected with how pymalloc works, that
_PyObject_Mallocwould be very cheap.I will attempt to use the specializing interpreter features to apply their optimizations in a safer manner (with full credits given to them of course). And hopefully, it will have better results.
I'm abandoning this idea. I integrated the PyLong reuse hacks above into a specialized instruction, and it produces a significant pessimization on ranges with small longs [1].
Since there's a small int cache in CPython, any long from -5 to 256 is essentially free. So the overhead of an adaptive instruction is significant. I would expect such small ranges to cover most use cases.
Additionally, to get the full test suite to pass, I had to be extremely conservative. This means more than half the time it still had to allocate a new long. I don't see this going too far without the compiler's help.
There is some speedup on very large ranges, but it was only 10% on a microbench [2]. I'm not sure what settings user heeres was testing with (eg. debug, release, PGO?) for 50%, and I might have implemented things wrongly, so I can't provide an explanation. One guess is that pymalloc is quite efficient after PGO. Also if you're dealing with such large ranges, you're probably better off using numpy, cython, numba etc. Overall, even if we can fix the other shortcomings, for the complexity it introduces it's not profitable.
TLDR: Combined instructions or Mark's rearranged instructions look like a better fit. I would think
FOR_ITER+LOAD_FASTSTORE_FAST) would show benefits. But they cross basic blocks, so optimization is more difficult. Maybe interpreter specializations can be re-looked at again for late-stage optimizations.Note: All results were obtained on Windows with PGO. Also I know I should use pyperf instead, but I was short on time 😉 . Sorry.
[1]
python.exe -m timeit "for _ in range(0, 256): pass"
Before:
100000 loops, best of 5: 2.17 usec per loop
Specialized:
100000 loops, best of 5: 2.45 usec per loop[2]
python.exe -m timeit "for _ in range(256, 10000): pass"
Before:
2000 loops, best of 5: 138 usec per loop
Specialized:
2000 loops, best of 5: 126 usec per loopCommit: Fidget-Spinner/cpython@e5393d6
Thanks for doing all the research!
If you want to combine FOR_ITER and LOAD_FAST in the compiler, that could be a super-instruction (#16) added in the assembly phase. I have done a few of these, but never merged any upstream (https://github.com/faster-cpython/cpython/tree/super-instr). Also check out Mark's recent attempt (https://github.com/faster-cpython/cpython/tree/super-instructions).
Reacted by Ken JinReacted by Leandro de OliveiraI'm on a roll producing things with 0 speedups 😉 . FOR_ITER + STORE_FAST showed no speedups too. Seems like the existing
PREDICTmacro is doing a really good job. On Windows with PGO:python.exe -m timeit -s >> "def f(n): >> for _ in range(n): >> pass >> " "f(10_000)"Before:
2000 loops, best of 5: 138 usec per loop
2000 loops, best of 5: 141 usec per loop
2000 loops, best of 5: 138 usec per loopSuperinstruction:
2000 loops, best of 5: 140 usec per loop
2000 loops, best of 5: 137 usec per loop
2000 loops, best of 5: 137 usec per loopCommit: Fidget-Spinner/cpython@c8a1338
To close the loop:
It seems that Larry tried something similar (though with a different approach) back in 2015: https://bugs.python.org/issue24138. He decided it wasn't worth it in the end.
That spawned some attempts at a long freelist in https://bugs.python.org/issue24165. But the pyperformance numbers were a little murky, so that was abandoned too.
- Thanks for the links! I wonder if maybe we should look at that integer freelist again.
Once other operations are faster, the overhead of the integer allocation will be a bigger percentage. So maybe it will be noticeable in 3.11 :).
Oh, and one more really cool idea by Serhiy, which I think will probably get merged https://bugs.python.org/issue45026. In short, the PyLong to return is currently calculated by
(start + index * step)(index is the index of the iterator, not the return value). The change stores the previous Pylong instart, so the new PyLong uses just(start + step). Iterating ranges are 2x faster in his PR!I'm reopening this. Specialization of
FOR_ITERis worthwhile, if only for generators and coroutines. A specialization ofFOR_ITERfor generators can avoid consuming C stack in the same way as we currently do for calls to Python functions.
If we are going to specialize for generators anyway, additional specializations may be worthwhile.A specialization for list iterators might be worthwhile.
Handlingrangeis probably out of scope for PEP 659 specialization, as we want to perform scalar replacement of the iterator which is going to be a job for a higher tier optimizer.9 remaining items
bb->b_nofallthrough = 0;This should become
1, right? Maybe that's why it didn't work?bb->b_nofallthrough = 0;This should become
1, right? Maybe that's why it didn't work?FOR_END does fall through in one of the two branches, so
nofallthroughshould become false I believe (an unfortunate double-negative). Since the instruction was a JUMP_ABSOLUTE, nofallthrough should be true already I think? Without that line, some assertion about nofallthrough failed IIRC.Is it somehow problematic to take a basicblock that had no fallthrough and then add a fallthrough to it?
FOR_END does fall through in one of the two branches, so
nofallthroughshould become false I believe (an unfortunate double-negative).Ha, yep. Time for me to go home.
It may be the
bb->b_next = target->i_target;move, then. You might have gotten yourself into a situation where two different blocks fall through to the same target or something:if condition: # This FOR_ITER will be peepholed first, and the jump will be threaded # straight to baz()... for i in range(42): foo() # ...then, I *think* your new peephole optimization will stick a # FOR_END here that tries to fall through to baz()... else: bar() # ...but we already fall through to it here! baz()
If so, then adding an explicit
JUMP_FORWARDinstead might fix it.Reacted by Dennis SweeneyHi everyone,
my Python implementation did some specialization for the
FOR_ITERinstructions, which are documented in the PhD thesis and also in the ECOOP paper. So maybe it's worth to take a look and do some simple measurements whether this still makes sense on much more modern hardware.For generator optimization, we had some nifty idea that we prototyped in our ZipPy VM, which resulted in massive speedups. Some of the details may not directly apply to CPython, since this was done in Truffle/Graal, but there were some interpreter benefits as well AFAIR. This optimization was accepted at OOPSLA'14, and if there is some interest, I can look it up and provide the necessary details for discussion.
All the best,
--stefanReacted by Ken Jin and Eric SnowMy current attempt at replacing JUMP_ABSOLUTE/FOR_ITER with FOR_END at python/cpython@main...sweeneyde:for_end has a flaw in how it makes some tracing have to happen. For example, I have a failing test case
test_05_no_pop_tops (test.test_sys_settrace.TraceTestCase), which has the followingdef no_pop_tops(): # 0 x = 1 # 1 for a in range(2): # 2 if a: # 3 x = 1 # 4 else: # 5 x = 1 # 6 AssertionError: events did not match expectation: (0, 'call') (1, 'line') (2, 'line') + (2, 'line') (3, 'line') (6, 'line') + (2, 'line') (2, 'line') (3, 'line') (4, 'line') (2, 'line') (2, 'return')The dis output, with the two differing lines labelled:
>>> from test.test_sys_settrace import no_pop_tops >>> from dis import dis >>> dis(no_pop_tops) 116 0 RESUME 0 117 2 LOAD_CONST 1 (1) 4 STORE_FAST 0 (x) 118 6 LOAD_GLOBAL 1 (NULL + range) 18 LOAD_CONST 2 (2) 20 PRECALL 1 24 CALL 1 34 GET_ITER 36 JUMP_FORWARD 8 (to 54) # <=========== THIS IS NEW >> 38 STORE_FAST 1 (a) 119 40 LOAD_FAST 1 (a) 42 POP_JUMP_IF_FALSE 25 (to 50) 120 44 LOAD_CONST 1 (1) 46 STORE_FAST 0 (x) 48 JUMP_FORWARD 2 (to 54) 122 >> 50 LOAD_CONST 1 (1) 52 STORE_FAST 0 (x) 118 >> 54 FOR_END 19 (to 38) # <=========== THIS IS NEW 56 LOAD_CONST 0 (None) 58 RETURN_VALUESo either there's some fix to the tracing logic that I'm missing (I'm not super familiar), or FOR_ITER needs to stick around and duplicate most of the FOR_END logic, which isn't ideal IMO. Any suggestions?
Perhaps use
ADDOP_JUMP_NOLINEforFOR_END? You might need to manually insert aNOPwith the correct line number just before it (in the previous block, at the end of the loop), too. Not sure.This is where the magic happens, so you'll want to start there if you're going to be debugging weird traces. (Looking at it now, maybe that
i->i_linenoshould really be0 < i->i_lineno? It seems wrong in its current form.)I broke the trace in a similar way with a JUMP_BACK opcode. It turned out that I needed to patch this function in frameobject.c to add the new jump type to the switch. Maybe your problem is there as well.
Even if range() microbenchmarks are hard to budge, the code path for list iterators is a lot smaller, so there's probably a decent speedup possible from specializing there. Dict items and maybe enumerate (the next most common couple types in pyperformance) could be made to not have to construct a tuple at all, unpacking directly onto the stack. And then generators could speed up as well, if desired.
A FOR_ITER-->FOR_END change seems to make only microscopic improvements at best, but it seems like it could be good to make a decision about whether that's appropriate to do before trying to specialize. I opened a FOR_END issue at python/cpython#91432 and a PR at python/cpython#70016 that got the tracing bugs ironed out.
On the other hand, one wild idea would be to quicken
JUMP_BACKWARDtoFOR_END_ADAPTIVEwhen its target is aFOR_ITER. That way, we get the same old readable unquickend bytecode, but then get the benefits of one less opcode per loop. It would makeJUMP_BACKWARDtake some cache entries, but maybe that's okay, or maybe we could even make it only take up cache entries when it's in that situation.Dict items and maybe enumerate (the next most common couple types in pyperformance) could be made to not have to construct a tuple at all, unpacking directly onto the stack.
Just a heads-up: almost all built-in iterators that yield tuples already typically avoid constructing more than one (for exactly this reason), so this may not pay off much.
With the recent
NOTRACE_DISPATCH_SAME_OPARG()fix, I was able to get a plain-old FOR_ITER specialization working for lists and ranges. Code is here: python/cpython#91713Microbenchmarks show ~1.1x speedup for lists, ~1.5x speedup for small ranges, but ~2.9x speedup for larger ranges! This comes from modifying the target local in place. It's almost like taking two of @Fidget-Spinner's patches and squishing them together.
Pyperformance numbers coming soon.
Reacted by Dave Burkholder, Jelle Zijlstra and Ken Jin@sweeneyde, @markshannon: With python/cpython#91713 merged, is this issue finished?
I think this is done.
- We already have specializations for
range,list, andtuple. The function pointertp_nextis probably good enough for other classes. - Another approach to this is Virtual iterators #392
- Specializing for generators is covered by Specialization of generator iteration and coroutine await #457
- We already have specializations for
I haven't properly profiled anything. Throwing this idea here to see what people think.
Consider this fairly common pattern in Python:
Bytecode snippet:
Anecdotally, some users are surprised at how much overhead this has. For most simple for loops, users intend for the range objects to be used as the equivalent
for(int i=0; i < x; i++)loop in C. The range objects are created then thrownaway immediately.In those cases, calling
next(range_iterator)inFOR_ITERis unnecessary overhead. We can unbox this into a simplePyLongobject, thenPyLong_Addon it. This can be aFOR_ITER_RANGEopcode.This will have to be extremely conservative. We can only implement this on range objects with a reference count of 1 (ie used only for the for loop) and they must be the builtin range and not some monkeypatched version. Without the compiler’s help, the following would be very dangerous to optimize:
We can also do the same with lists and tuples (
FOR_ITER_LISTandFOR_ITER_TUPLE), but use the the nativePyTuple/List_GetIteminstead of iterator protocol. But I'm not sure how common something likefor x in (1,2,3)is. So maybe those aren't worth it (they're also much harder to rollback if the optimization breaks halfway).FOR_ITERisn't a common instruction. But I think when it's used it matters, because it tends to be rather loopy code.What do y'all think?