[issue26289] Optimize floor division for ints

Roundup Robot added the comment: New changeset 37bacf3fa1f5 by Yury Selivanov in branch 'default': Issues #26289 and #26315: Optimize floor/modulo div for single-digit longs https://hg.python.org/cpython/rev/37bacf3fa1f5 -- nosy: +python-dev ___

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: Committed. Thank you Serhiy, Mark and Victor for helping with the patch! -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: Attaching an updated patch. > 1. I think you're missing the final multiplication by Py_SIZE(b) in the > fast_mod code. Which is odd, because your tests should catch that. So either > you didn't run the tests, or that code path isn't being used somehow.

[issue26289] Optimize floor division for ints

Changes by Yury Selivanov : Added file: http://bugs.python.org/file41887/fast_divmod_6.patch ___ Python tracker ___

[issue26289] Optimize floor division for ints

Mark Dickinson added the comment: Thanks for the updates! No further comments from me - the patch looks good as far as I'm concerned. -- ___ Python tracker

[issue26289] Optimize floor division for ints

Mark Dickinson added the comment: A couple more observations: 1. I think you're missing the final multiplication by Py_SIZE(b) in the fast_mod code. Which is odd, because your tests should catch that. So either you didn't run the tests, or that code path isn't being used somehow. 2. Talking

[issue26289] Optimize floor division for ints

Mark Dickinson added the comment: ... though on second thoughts, it's probably better to spell that div = -1 - (left - 1) / right to avoid compiler warnings about bit operations on signed types. A good compiler should be able to optimise `-1 - x` to `~x` anyway. --

[issue26289] Optimize floor division for ints

Serhiy Storchaka added the comment: Since the patch is changed (and may be changed further if accept Mark's suggestion), benchmarks results should be updated. Is it worth to move the optimization inside l_divmod? Will this speed up or slow down other operations that use l_divmod? --

[issue26289] Optimize floor division for ints

STINNER Victor added the comment: STINNER Victor: >> This change looks related to the issue #21955. IMHO we should take the same >> decision. I mean, maybe it's better to implement the fast-path only in >> ceval.c? Or maybe in ceval.c and longobject.c? Yury Selivanov: > There is no drastic

[issue26289] Optimize floor division for ints

Changes by Mark Dickinson : -- nosy: +mark.dickinson ___ Python tracker ___ ___

[issue26289] Optimize floor division for ints

Mark Dickinson added the comment: A slightly neater way to compute the result in the case that the signs differ is div = ~((left - 1) / right) That saves the extra multiplication and equality check. -- ___ Python tracker

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: Attaching a new patch -- big thanks to Mark and Serhiy. > div = ~((left - 1) / right) The updated code works slightly faster - ~0.285 usec vs ~0.3 usec. -- Added file: http://bugs.python.org/file41870/floor_div_4.patch

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: > Is it worth to move the optimization inside l_divmod? Will this speed up or > slow down other operations that use l_divmod? Attaching a new patch -- fast_divmod.patch It combines patches for this issue and issue #26315. Individual timeit benchmarks work as

[issue26289] Optimize floor division for ints

Mark Dickinson added the comment: Just for the record, there's a less-branchy analog of the floor division code I suggested for modulo. In Python-land, it looks like this: def propermod(a, b): # mimic the C setup assert a != 0 and b != 0 left = abs(a) size_a = -1 if a < 0 else

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: > mod = left % right if size_a == size_b else right - 1 - (left - 1) % right This works, Mark! Again, the difference in performance is very subtle, but the code is more compact. -m timeit -s "x=22331" "x//2;x//-3;x//4;x//5;x//-6;x//7;x//8;x//-99;x//100;"

[issue26289] Optimize floor division for ints

Changes by Yury Selivanov : Added file: http://bugs.python.org/file41876/fast_divmod_3.patch ___ Python tracker ___

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: Also, every other operation for longs (except %, for which I created issue #26315) is optimized for single digit longs. This optimization is also important for users of operator.floordiv etc. Even if we decide to provide a fast path in ceval, it's going to

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: Serhiy, Victor, thanks for the review. Attaching an updated version of the patch. -- Added file: http://bugs.python.org/file41860/floor_div_2.patch ___ Python tracker

[issue26289] Optimize floor division for ints

Yury Selivanov added the comment: There is no drastic difference on where you implement the fast path. I'd implement all specializations/optimizations in longobject.c and optimize ceval to call slots directly. That way, the implact on ceval performance would be minimal. --

[issue26289] Optimize floor division for ints

Changes by Yury Selivanov : Added file: http://bugs.python.org/file41862/floor_div_3.patch ___ Python tracker ___

[issue26289] Optimize floor division for ints

Changes by Yury Selivanov : -- assignee: -> yselivanov ___ Python tracker ___ ___

[issue26289] Optimize floor division for ints

Serhiy Storchaka added the comment: Added comments on Rietveld. -- ___ Python tracker ___ ___

[issue26289] Optimize floor division for ints

New submission from Yury Selivanov: The attached patch optimizes floor division for ints. ### spectral_norm ### Min: 0.319087 -> 0.289172: 1.10x faster Avg: 0.322564 -> 0.294319: 1.10x faster Significant (t=21.71) Stddev: 0.00249 -> 0.01277: 5.1180x larger -m timeit -s "x=22331"