[issue26289] Optimize floor division for ints

[Roundup Robot]

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

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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.

Thanks.  Not sure how this happened :(

> 2. Talking of tests, it would be good to have tests (for both // and %) for 
> the case where the dividend is an exact multiple of the divisor.

Done.

> 3. Negative divisors almost never come up in real life, so you might also 
> consider restricting the optimisations to the case Py_SIZE(b) == 1 (rather 
> than ABS(Py_SIZE(b)) == 1). If that makes any speed difference at all for the 
> case of positive divisors, then it's probably worth it. If not, then don't 
> worry about it.

Tried it, the difference is very small.  For modulo division it's ~0.225 usec 
vs ~0.23 usec for [-m timeit -s "x=22331" 
"x%2;x%3;x%4;x%5;x%6;x%7;x%8;x%99;x%100;"]

--
Added file: http://bugs.python.org/file41886/fast_divmod_5.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

Changes by Yury Selivanov :


Added file: http://bugs.python.org/file41887/fast_divmod_6.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Mark Dickinson]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Mark Dickinson]

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 of tests, it would be good to have tests (for both // and %) for the 
case where the dividend is an exact multiple of the divisor.

3. Negative divisors almost never come up in real life, so you might also 
consider restricting the optimisations to the case Py_SIZE(b) == 1 (rather than 
ABS(Py_SIZE(b)) == 1). If that makes any speed difference at all for the case 
of positive divisors, then it's probably worth it. If not, then don't worry 
about it.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Mark Dickinson]

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Serhiy Storchaka]

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?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[STINNER Victor]

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 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.

Oh wait, I was confused by my own patch for #21955 inlining int operations in 
ceval.c.

Since recent benchmarks showed slow-down when ceval.c is modified, I think that 
it's ok to modify longobject.c rather than ceval.c (and maybe only 
longobject.c, but let's discuss that in issue #21955).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Mark Dickinson]

Changes by Mark Dickinson :


--
nosy: +mark.dickinson

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Mark Dickinson]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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 fast, but ** op becomes faster:

-m timeit -s "x=223" "x**2;x**-2;x**2;x**-3;x**3;x**-3;x**4.5;x**-4.5"
with patch: 1.2usec
without: 1.5usec

--
Added file: http://bugs.python.org/file41871/fast_divmod.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Mark Dickinson]

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 1
right = abs(b)
size_b = -1 if b < 0 else 1

# Compute mod: only one branch needed.
mod = left % right if size_a == size_b else right - 1 - (left - 1) % right
return mod * size_b

# Verify that we get the same results as the regular mod.
for n in range(-100, 100):
if n == 0:
continue
for d in range(-100, 100):
if d == 0:
continue
assert propermod(n, d) == n % d

It may well not have any significant effect here, though.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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;"
with patch: 0.321  without patch: 0.633

-m timeit -s "x=22331" "x%2;x%3;x%-4;x%5;x%6;x%-7;x%8;x%99;x%-100;"
with patch: 0.224  without patch: 0.66

-m timeit 
"divmod(100,20);divmod(7,3);divmod(121,99);divmod(123121,123);divmod(-1000,7);divmod(23423,-111)"
with patch: 0.839  without patch: 1.07


I'm in favour of fast_divmod_2.patch for solving both this issue and issue 
#26315.  Serhiy, what do you think?

--
Added file: http://bugs.python.org/file41875/fast_divmod_2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

Changes by Yury Selivanov :


Added file: http://bugs.python.org/file41876/fast_divmod_3.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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 be another matter.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

Changes by Yury Selivanov :


Added file: http://bugs.python.org/file41862/floor_div_3.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

Changes by Yury Selivanov :


--
assignee:  -> yselivanov

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

Added comments on Rietveld.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue26289] Optimize floor division for ints

[Yury Selivanov]

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" "x//2;x//3;x//4;x//5;x//6;x//7;x//8;x/99;x//100;"

with patch: 0.298
without:0.515

--
components: Interpreter Core
files: floor_div.patch
keywords: patch
messages: 259617
nosy: haypo, pitrou, serhiy.storchaka, yselivanov
priority: normal
severity: normal
stage: patch review
status: open
title: Optimize floor division for ints
type: performance
versions: Python 3.6
Added file: http://bugs.python.org/file41813/floor_div.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com