Optimize floor division for ints

[1st1]

BPO	26289
Nosy	@mdickinson, @pitrou, @vstinner, @serhiy-storchaka, @1st1
Files	floor_div.patch floor_div_2.patch floor_div_3.patch floor_div_4.patch fast_divmod.patch fast_divmod_2.patch fast_divmod_3.patch fast_divmod_5.patch fast_divmod_6.patch

^{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 = 'https://github.com/1st1'
closed_at = <Date 2016-02-11.15:29:32.206>
created_at = <Date 2016-02-05.02:07:54.315>
labels = ['interpreter-core', 'performance']
title = 'Optimize floor division for ints'
updated_at = <Date 2016-02-11.15:29:32.205>
user = 'https://github.com/1st1'

bugs.python.org fields:

activity = <Date 2016-02-11.15:29:32.205>
actor = 'yselivanov'
assignee = 'yselivanov'
closed = True
closed_date = <Date 2016-02-11.15:29:32.206>
closer = 'yselivanov'
components = ['Interpreter Core']
creation = <Date 2016-02-05.02:07:54.315>
creator = 'yselivanov'
dependencies = []
files = ['41813', '41860', '41862', '41870', '41871', '41875', '41876', '41886', '41887']
hgrepos = []
issue_num = 26289
keywords = ['patch']
message_count = 19.0
messages = ['259617', '259803', '259889', '259893', '259896', '259909', '259932', '259934', '259935', '259938', '259940', '259942', '259944', '259955', '259994', '260019', '260025', '260110', '260112']
nosy_count = 6.0
nosy_names = ['mark.dickinson', 'pitrou', 'vstinner', 'python-dev', 'serhiy.storchaka', 'yselivanov']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue26289'
versions = ['Python 3.6']

[1st1]

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

[serhiy-storchaka]

Added comments on Rietveld.

[1st1]

Serhiy, Victor, thanks for the review. Attaching an updated version of the patch.

[vstinner]

This change looks related to the issue bpo-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?

[1st1]

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.

[1st1]

Also, every other operation for longs (except %, for which I created issue bpo-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.

[mdickinson]

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.

[mdickinson]

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

[vstinner]

STINNER Victor:

> This change looks related to the issue bpo-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 bpo-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 bpo-21955).

[serhiy-storchaka]

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?

[1st1]

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.

[1st1]

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