[issue46218] Change long_pow() to sliding window algorithm

[Tim Peters]

Change by Tim Peters :


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

[issue46218] Change long_pow() to sliding window algorithm

[Tim Peters]

Tim Peters  added the comment:


New changeset 863729e9c6f599286f98ec37c8716e982c4ca9dd by Tim Peters in branch 
'main':
bpo-46218: Change long_pow() to sliding window algorithm (GH-30319)
https://github.com/python/cpython/commit/863729e9c6f599286f98ec37c8716e982c4ca9dd


--

___
Python tracker 

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

[issue46218] Change long_pow() to sliding window algorithm

[Tim Peters]

Tim Peters  added the comment:

Since cutting the window size by 1 cut the size of the dynamic precomputed 
table in half, the overhead of the sliding window method was correspondingly 
reduced. It can pay off at exponents of half the bit length now, so that 
threshold was also changed.

--

___
Python tracker 

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

[issue46218] Change long_pow() to sliding window algorithm

[Tim Peters]

Tim Peters  added the comment:

Nope, boosting the window size to 6 doesn't appear to really help at all, at 
least not on my box. Regardless of the window size, we have to do a bigint 
square for every bit position in the exponent. I don't know of any way to speed 
that (short of speeding multiplication, and we already make a special case of 
squaring).

So that dominates. Even for an exponent of a million solid 1-bits, the overall 
timing difference appears insignificant.

So I cut the window size back to 5 bits again. That has the benefit of cutting 
the old table size in half, which also cuts the precomputation time to fill it 
about in half, which should have some minor benefit for saner (smaller) 
exponents.

As a sanity check, I also tried cutting the window size to 3 bits. That had an 
obvious bad timing impact on huge exponents of solid 1 bits.

--

___
Python tracker 

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

[issue46218] Change long_pow() to sliding window algorithm

[Tim Peters]

Change by Tim Peters :


--
keywords: +patch
pull_requests: +28535
stage: needs patch -> patch review
pull_request: https://github.com/python/cpython/pull/30319

___
Python tracker 

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

[issue46218] Change long_pow() to sliding window algorithm

[Tim Peters]

New submission from Tim Peters :

As discussed on python-dev, it would be nice to break long_pow()'s reliance on 
that the number of bits in a CPython long "digit" is a multiple of 5.

Moving to the sliding-window algorithm would do that (it has to be able to 
cross digit boundaries to fill the current window), and would be better on some 
other counts too: the precomputed table can be half the size (or we can add an 
extra bit to the window for the same table size), and it can - depending on 
exponent bit patterns - sometimes reduce the number of multiplies needed too.

So I intend to do that, and bump the window size from 5 to 6 (which would yield 
a significant, although modest, speed improvement for giant-exponent cases).

--
assignee: tim.peters
components: Interpreter Core
messages: 409446
nosy: tim.peters
priority: normal
severity: normal
stage: needs patch
status: open
title: Change long_pow() to sliding window algorithm
type: performance
versions: Python 3.11

___
Python tracker 

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