classification
Title: decimal.py: performance in _power_exact
Type: performance Stage: commit review
Components: Library (Lib) Versions: Python 3.4, Python 3.3
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: haypo, mark.dickinson, python-dev, rhettinger, skrah
Priority: normal Keywords: patch

Created on 2011-05-15 08:28 by skrah, last changed 2011-06-04 17:59 by skrah. This issue is now closed.

Files
File name Uploaded Description Edit
issue12080.patch mark.dickinson, 2011-05-22 13:51 review
issue12080_v2.patch mark.dickinson, 2011-05-22 15:10 review
Messages (8)
msg136022 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2011-05-15 08:28
I found another performance issue in _power_exact:

>>> Decimal(4) ** Decimal("-1.2e-999999999")
^CTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/stefan/pydev/cpython/Lib/decimal.py", line 2343, in __pow__
    ans = self._power_exact(other, context.prec + 1)
  File "/home/stefan/pydev/cpython/Lib/decimal.py", line 2098, in _power_exact
    ten_pow = 10**-ye
KeyboardInterrupt



This one is in the power operation in line 2098. There are several
other places where huge integer powers are calculated if 'ye' is
sufficiently large.
msg136044 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-05-15 18:37
Thanks for the report;  I'll try to find some time to look at this.

This isn't the first time that I've thought that it might be better just to abandon the aim of getting correctly-rounded results for pow.
msg136524 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-05-22 13:51
Here's a patch. Stefan, could you please review?
msg136536 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-05-22 15:10
Here's a slightly improved version that adds guards against computing 10**ye for large ye in the case y < 0, ye > 0.
msg137652 - (view) Author: Roundup Robot (python-dev) Date: 2011-06-04 17:14
New changeset c3fe54781244 by Mark Dickinson in branch 'default':
Issue #12080: Fix a performance issue in Decimal._power_exact that causes some corner-case Decimal.__pow__ calls to take an unreasonably long time.
http://hg.python.org/cpython/rev/c3fe54781244
msg137653 - (view) Author: Roundup Robot (python-dev) Date: 2011-06-04 17:24
New changeset 78d79499e7de by Mark Dickinson in branch '2.7':
Issue #12080: Fix a performance issue in Decimal._power_exact that caused some corner-case Decimal.__pow__ calls to take an unreasonably long time.
http://hg.python.org/cpython/rev/78d79499e7de
msg137654 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2011-06-04 17:25
Fixed for 3.3 and 2.7.
msg137655 - (view) Author: Stefan Krah (skrah) * (Python committer) Date: 2011-06-04 17:59
Mark Dickinson <report@bugs.python.org> wrote:
> Here's a patch. Stefan, could you please review?

Mark, sorry for not replying earlier. The patch looks great.

I've also tested the patch in practice: I ran 700,000,000 random tests with
an exponent range of [-999999999, 999999999]. This took three days.

Without the patch, this would have been impossible; the range had to be
restricted to [-9999, 9999].

Unfortunately I got sidetracked reviewing the rest of the function (today
I started out on a mechanical proof of the nth-root part).

I *did* review the changes though, and I think they are correct.
History
Date User Action Args
2011-06-04 17:59:48skrahsetmessages: + msg137655
2011-06-04 17:25:22mark.dickinsonsetstatus: open -> closed
resolution: fixed
messages: + msg137654
2011-06-04 17:24:24python-devsetmessages: + msg137653
2011-06-04 17:14:33python-devsetnosy: + python-dev
messages: + msg137652
2011-05-22 15:10:22mark.dickinsonsetfiles: + issue12080_v2.patch

messages: + msg136536
2011-05-22 13:51:58mark.dickinsonsetstage: commit review
2011-05-22 13:51:31mark.dickinsonsetfiles: + issue12080.patch
keywords: + patch
messages: + msg136524
2011-05-15 21:18:54hayposetnosy: + haypo
2011-05-15 18:57:54rhettingersetnosy: + rhettinger
2011-05-15 18:37:22mark.dickinsonsetassignee: mark.dickinson
messages: + msg136044
2011-05-15 08:28:21skrahcreate