[issue41487] Builtin bigint modulo operation can be made faster when the base is divisible by a large power of 2 (i.e: has many trailing 0 digits in binary)

[Mark Dickinson]

Change by Mark Dickinson :


--
resolution:  -> rejected
stage:  -> 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

[issue41487] Builtin bigint modulo operation can be made faster when the base is divisible by a large power of 2 (i.e: has many trailing 0 digits in binary)

[Mark Dickinson]

Change by Mark Dickinson :


--
nosy: +tim.peters

___
Python tracker 

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

[issue41487] Builtin bigint modulo operation can be made faster when the base is divisible by a large power of 2 (i.e: has many trailing 0 digits in binary)

[Mark Dickinson]

Mark Dickinson  added the comment:

I'd be opposed to changing Python's `int` implementation in this way: it adds 
complication to the codebase and potentially also slows down "normal" cases. If 
a user knows in advance (a) that they're using a divisor that's highly divisble 
by 2, and (b) that the division or modulo operation is performance critical, 
then they can take the appropriate steps to optimize their code.

--

___
Python tracker 

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

[issue41487] Builtin bigint modulo operation can be made faster when the base is divisible by a large power of 2 (i.e: has many trailing 0 digits in binary)

[Karthikeyan Singaravelan]

Change by Karthikeyan Singaravelan :


--
nosy: +lemburg, mark.dickinson, rhettinger, stutzbach

___
Python tracker 

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

[issue41487] Builtin bigint modulo operation can be made faster when the base is divisible by a large power of 2 (i.e: has many trailing 0 digits in binary)

[Shlomi Fish]

New submission from Shlomi Fish :

As the pure-Python code below demonstrates, when called as `python3 test.py 
jitshift` it is much faster than when called as `python3 test.py builtinops` 
(which takes many seconds/minutes past the 24th iteration). I am using fedora 
32 x86-64 on a Cannon lake intel core i5 NUC. Tested with latest cpython3 git 
master and with /usr/bin/pypy3

The improvement was done in pure-python / userland and may be improved upon 
further given these or others: https://gmplib.org/ and 
https://github.com/ridiculousfish/libdivide .

```
#!/usr/bin/env python3

# The Expat License
#
# Copyright (c) 2020, Shlomi Fish
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
import sys

OPT = "builtinops"


def mytest(p):
pint2p = p << p
myrange = range(1000)
if OPT == "builtinpow":
ret = pow(2, (1 << p), pint2p)
elif OPT == "builtinops":
ret = 2
for i in myrange:
print('sq', i, flush=True)
ret *= ret
print('mod', i, flush=True)
ret %= pint2p
print('after mod', i, (ret % 10 ** 20), flush=True)
else:
class ShiftMod:
"""docstring for ShiftMod:d"""
def __init__(self, base, shift):
self.base = base
self.shift = shift
self.mask = (1 << shift) - 1
self.n = base << shift

def mod(self, inp):
if inp < self.n:
return inp
return inp >> self.shift) % self.base)
 << self.shift) | (inp & self.mask))

def gen_shift_mod(x):
s = 0
for offset in (20, 2, 2000, 200, 20, 1):
bits_mask = (1 << offset) - 1
while x & bits_mask == 0:
s += offset
x >>= offset
return ShiftMod(x, s)

ret = 2
if OPT == "shiftmodpre":
m = ShiftMod(p, p)
for i in myrange:
print('sq', i, flush=True)
ret *= ret
print('mod', i, flush=True)
# m = gen_shift_mod(pint2p)
ret = m.mod(ret)
print('after mod', i, (ret % 10 ** 20), flush=True)
elif OPT == "gen_shift_mod":
m = gen_shift_mod(pint2p)
for i in myrange:
print('sq', i, flush=True)
ret *= ret
print('mod', i, flush=True)
ret = m.mod(ret)
print('after mod', i, (ret % 10 ** 20), flush=True)
elif OPT == "jitshift":
for i in myrange:
print('sq', i, flush=True)
ret *= ret
print('mod', i, flush=True)
ret = gen_shift_mod(pint2p).mod(ret)
print('after mod', i, (ret % 10 ** 20), flush=True)
return ret % (p*p) // p


def main(which):
global OPT
OPT = which
'''
if which == "builtinpow":
OPT = 1
elif which == "builtinops":
OPT = 0
elif which == "shiftmod":
OPT = 2
else:
raise Exception("unknown choice")
'''
x = mytest(9816593)
print(x)
return


if __name__ == "__main__":
main(sys.argv[1])

```

--
components: Interpreter Core
files: modtest.py
messages: 374869
nosy: shlomif2
priority: normal
severity: normal
status: open
title: Builtin bigint modulo operation can be made faster when the base is 
divisible by a large power of 2 (i.e: has many trailing 0 digits in binary)
type: performance
versions: Python 3.10
Added file: https://bugs.python.org/file49369/modtest.py

___
Python tracker 

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