Created on 2008-03-25 21:36 by mark.dickinson, last changed 2012-03-16 08:09 by mark.dickinson. This issue is now closed.
|decimal_bytes.patch||mark.dickinson, 2008-03-26 00:55||review|
|deccoeff.c||mark.dickinson, 2008-05-03 15:35||Decimal coefficient module (alpha)|
|deccoeff.tar.gz||mark.dickinson, 2008-09-23 15:20||v0.2 of Deccoeff type, with working decimal.py|
|msg64521 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2008-03-25 21:36|
The Python 3.0 version of decimal.py currently stores the coefficient of a Decimal number (or the payload of a NaN) as a string, all of whose characters are in the range '0' through '9'. It may be more time-efficient to store the coefficient as a bytes instance instead, since bytes -> int conversion is likely to be faster than str -> int conversion. On the other hand, int -> bytes conversion has to go through str, so may be significantly slower than int -> str conversion... Bottom line: this needs testing. One other option: it may even be worth considering storing the coefficient directly as a Python integer. I've argued against this before, on the basis that it makes direct access to the decimal digits of a number harder, and this direct access is useful for rounding as well as for some of the more esoteric Decimal operations (logical operations, shifts and rotations). But it may be worth a look. (I think it's clear what the *right* option is, given unlimited developer time and energy: decimal.py should represent the coefficient using a long integer implementation written in C, with wordsize a power of 10---probably either 10**4 or 10**9.) See related discussion at issue 2482 and at http://mail.python.org/pipermail/python-dev/2008-March/078189.html
|msg64531 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2008-03-26 00:55|
Here's a first try at a patch that converts the Decimal coefficient from type str to type bytes. It needs some work: here are some timings for a complete run of the test suite (best of 3 in each case) on my MacBook. Python 3.0, str: 12.880s Python 3.0, bytes: 13.294s Python 2.6: 9.279s Python 2.5: 9.212s There's still some room for speedup with the bytes patch, but at the moment it doesn't look as though performance alone is a compelling reason to make this change.
|msg64538 - (view)||Author: Nick Coghlan (ncoghlan) *||Date: 2008-03-26 02:30|
Hmm, I forgot there wasn't currently a direct path back from int -> bytes. I think your numbers *do* show that we need to do something about the performance of the Python 3.0 version of decimal. A 25% increase in runtime is a pretty big performance hit.
|msg66155 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2008-05-03 15:35|
I've made some progress here: I have a version of decimal.py for Python 3.0 that uses a Deccoeff instead of a string for the Decimal coefficient. It still needs a little work to make things efficient, but it already passes all the tests in test_decimal. There are no API changes. What's a Deccoeff? Read on, and/or see attached file. Deccoeff (for *Dec*imal *coeff*icient) is an extension type for Python 3.0 that combines some of the most useful aspects of both the integer and string types. First, you can do arithmetic directly with Deccoeff instances: >>> from deccoeff import Deccoeff >>> x = Deccoeff('7') >>> y = Deccoeff('11') >>> x + y Deccoeff('18') >>> x * y Deccoeff('77') >>> y - x Deccoeff('4') >>> x < y True Only nonnegative integers can be represented as Deccoeff instances, since that's all that's needed for Decimal: a subtraction that would produce a negative result instead raises OverflowError: >>> x-y Traceback (most recent call last): File "<stdin>", line 1, in <module> OverflowError: difference is negative and cannot be represented as a Deccoeff Powering also works: >>> x ** y Deccoeff('1977326743') >>> y ** x Deccoeff('19487171') So much for arithmetic: a Deccoeff instance can also be treated as a sequence: it can be sliced (though the 'step' argument is not supported): >>> x = Deccoeff('123456789') >>> x[2:] Deccoeff('1234567') >>> x[:5] Deccoeff('56789') and indexed: >>> x Deccoeff('6') The length gives the total number of digits: >>> len(x) 9 Note that the indices work in the opposite direction to the one you might expect by looking at the string representation of a Deccoeff: indexing is set up so that index 0 refers to the units digit, 1 to the tens digit, 2 to the hundreds digit, etc. Negative indices also make sense (but not in the usual Python sense of counting from the end of the object): you should imagine the Deccoeff as a finite string of digits padded with zeros infinitely on both the left and right. Then it makes sense to do, for example: >>> x[-2:] Deccoeff('12345678900') >>> x[-3:4] Deccoeff('6789000') This provides a convenient way to do a 'decimal shift left'. There are many places in Decimal where it's appropriate to use x[n:] without knowing in advance whether n is positive or negative. This is a work in progress... Comments very welcome.
|msg66161 - (view)||Author: Nick Coghlan (ncoghlan) *||Date: 2008-05-03 17:56|
(I changed the issue title to better reflect where the discussion has moved to) I really like the approach of a custom internal type for the mantissa storage (the module containing would probably best be called _decimal). Then it should be possible to focus on letting C do what it does best (high speed arithmetic) and Python do what it does best (provide the nice API and context management features)
|msg66211 - (view)||Author: Facundo Batista (facundobatista) *||Date: 2008-05-04 14:37|
I like this path, also. Beyond Deccoeff, this module could hold in the future other functions that are speed critical. Great work, Mark!
|msg72342 - (view)||Author: Nick Coghlan (ncoghlan) *||Date: 2008-09-02 14:37|
Looks like we'll be living with the slowdown for 3.0, so marking this as a high priority item for 3.1. (Given that the API doesn't change, I wonder if this could be included in a 3.0.1 release?)
|msg72350 - (view)||Author: Facundo Batista (facundobatista) *||Date: 2008-09-02 16:10|
Can not get into this now, but I'll be able to deal with this in some weeks...
|msg73266 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2008-09-15 15:49|
Sorry for the silence: new country + new job + no internet connection outside work = not many opportunities to spend time on this (or any other part of Python) at the moment. I do now have a version 0.2 of the deccoeff type, and more importantly a version of decimal.py that's adapted to use it; all tests in test_decimal.py pass, which is a start. But there's significant work to be done tidying up the code, identifying speed-critical bits, and moving those bits from Python to C. I'm wondering where to post the code; I could post a tarball here but it's a bit unwieldy. Perhaps it would be worth creating a new branch to work on this? This definitely seems like a (>=) two-person task; any help would be much appreciated! Thanks Facundo and Nick for comments so far. I also wonder whether there are alternative approaches that might do better. If we follow this approach, I'm doubtful about doing this for 3.0.1; even though the API is unchanged, this seems like too big a change for a bugfix release, with too great a risk of breakage.
|msg73281 - (view)||Author: Nick Coghlan (ncoghlan) *||Date: 2008-09-15 21:07|
This is the kind of project where the sandbox is useful - Facundo's original decimal work was done there, as was the attempt at a complete rewrite of the decimal module in C (which turned out to be a less than optimal approach to the speed problem). So I would suggest either a new directory in the sandbox, or re-using Facundo's original directory (which includes the telco benchmark) http://svn.python.org/view/sandbox/trunk/decimal And I agree that it is far more sensible to target 2.7/3.1 at this stage - the 3.0 slowdown, while real, actually isn't as bad as I expected, and even if it's large enough to be unacceptable to heavy users of Decimal, the only consequence is that they will have to hold off on migrating to 3.x for 12-18 months. Should we add something specific to the 3.0 release notes pointing out that there is approximately a 25% slowdown in the decimal module relative to 2.x?
|msg73286 - (view)||Author: Facundo Batista (facundobatista) *||Date: 2008-09-15 23:55|
Nick said: > So I would suggest either a new directory in the sandbox, or > re-using Facundo's original directory (which includes the > telco benchmark) +1 > And I agree that it is far more sensible to target 2.7/3.1 at > this stage - the 3.0 slowdown, while real, actually isn't as bad > as I expected, and even if it's large enough to be unacceptable > to heavy users of Decimal, the only consequence is that they will I'm not seeing this job as a way to solve the 3.0 slowdown, but more as the way to slowly, but steadily, replace parts of Decimal from Python to C as needed. So, I'm +1 to target this to 3.1, and I'm -0 to register the slowdown in the releases notes (those who use Decimal aren't really in it for speed...). Thank you!!
|msg73644 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2008-09-23 15:20|
> So I would suggest either a new directory in the sandbox, or re-using > Facundo's original directory (which includes the telco benchmark) Makes sense---thanks for the suggestion! But since it seems I don't have any open ssh ports it looks like I'll just have to post a tarball for now. The module is written to work with Python 3.x, on the basis that it's probably easier to backport to 2.x later than to try to maintain two separate versions. On Unix, untar, edit the top line of the Makefile to point to a Python 3.0 executable, and do ./configure && make "make test" runs the decimal test-suite.
|msg76926 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2008-12-04 20:50|
Just a quick note to say I am still working on this. I'll post some new code soon.
|msg79560 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2009-01-10 17:42|
(Adding Raymond to the nosy list.) In r68494, I've checked in some work towards rewriting Decimal (or parts of Decimal) in C. I reused Facundo's old /decimal directory in the sandbox, so the URL is: http://svn.python.org/view/sandbox/trunk/decimal/decimal_in_c/ What's there is a fully functional hybrid Python and C implementation of decimal. All the existing decimal tests pass, at least on my machine. There's very little performance increase to boast of at the moment, but that may change. To try it, check out the directory and follow the README instructions. This probably doesn't work on Windows; help fixing that would be appreciated. The code is for py3k only; I started out maintaining versions for both 2.x and 3.x, but that was just too painful. I'd rather get the py3k version working, then backport. The main files are: deccoeff.c: contains classes Deccoeff and _Decimal. Deccoeff implements base 10 nonnegative integer arithmetic: its instances can be treated as integers, but also sliced as though they were strings, which makes rounding and shifting operations simple. _Decimal is a minimal base class for Decimal; the idea is to move functions from Decimal to _Decimal over time. decimal.py: version of Lib/decimal.py, fixed to use Deccoeff instead of string for the coefficient. As I see it, there are two goals for this work: (1) Speed decimal up. (2) Bring proposals to add a decimal literal to C closer to realizability. By the way, presumably it's not a prerequisite for (2) that *all* of the decimal.py functionality be recoded in C? I could imagine a situation where the decimal literals are present in the core, but an 'import decimal' was necessary to get complete functionality.
|msg79563 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2009-01-10 17:46|
Changing title and assignee. (But all help is appreciated: if anyone wants to commit changes to the sandbox directory, please go ahead!)
|msg79565 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2009-01-10 18:10|
> (2) Bring proposals to add a decimal literal to C ... That should be "to Python", not "to C", of course.
|msg79566 - (view)||Author: Antoine Pitrou (pitrou) *||Date: 2009-01-10 18:14|
> By the way, presumably it's not a prerequisite for (2) that *all* of the > decimal.py functionality be recoded in C? I could imagine a situation > where the decimal literals are present in the core, but an 'import > decimal' was necessary to get complete functionality. We already have this situation with builtin open() and "import io", so I guess that wouldn't be out of question.
|msg79587 - (view)||Author: Raymond Hettinger (rhettinger) *||Date: 2009-01-11 04:57|
FWIW, I'm currently seeking project sponsorship to work on this. To do it right, a substantial portion of the module should be coded in C and needs to function independently of Python, with accessors provided to for Python to wrap around. Once, there is a fast C version, a discussion of a decimal literal can become a reasonable possibility. It will be an uphill battle though. Many decimal apps have few internal constants -- most of the data comes into the program from and external source and gets written back. A literal itself doesn't have much utility except for playing around at the command line. Also, there would need to be a PEP talking about how decimals should interact with binary floats and the rest of the language (which pretty much ignores decimals).
|msg79700 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2009-01-12 20:34|
Guess that makes this a bit of a wasted effort on my part, then. Darn. > a substantial portion of the module should be coded in C and > needs to function independently of Python, with accessors provided to > for Python to wrap around. I'm curious what sort of memory model you have in mind for this: would you implement separate memory management code that could easily be swapped in or out for the standard Python object allocator? Or does the functioning independently of Python bit not go as far as memory management? In any case, let me know if there's anything I can do to help out, whether it's coding, or review, or whatever. For what it's worth, I'm hoping to check in a significantly simpler (and I hope faster!) version of the log, log10 and exp functions to decimal.py in the near future, which should make rewriting that portion a little easier. The pow stuff could use some work, too.
|msg79702 - (view)||Author: Nick Coghlan (ncoghlan) *||Date: 2009-01-12 20:44|
FWIW, I actually prefer Mark's graduated approach to the Python->C migration since we have a continuously working module that will get incrementally faster over time. As profiling finds performance bottlenecks in the Python code, those parts can be migrated to C (e.g. as has been done initially with the manipulation of the coefficient, which has been one of the main time sinks in the decimal module since the days when it was still stored as a tuple instead of a string). Having most of the module in C should be the endpoint, not where we attempt to start (as I recall, attempts to rewrite the whole module in C in one go have already been made, and they failed miserably).
|msg155994 - (view)||Author: Ramchandra Apte (Ramchandra Apte) *||Date: 2012-03-16 06:17|
If issue7652 finishes. There's no point in fixing this bug.
|msg156004 - (view)||Author: Mark Dickinson (mark.dickinson) *||Date: 2012-03-16 07:28|
No, this should be closed.
|2012-03-16 08:09:48||mark.dickinson||set||status: open -> closed|
|2012-03-16 07:28:21||mark.dickinson||set||messages: + msg156004|
|2012-03-16 06:17:47||Ramchandra Apte||set||nosy:
+ Ramchandra Apte|
messages: + msg155994
|2010-08-21 23:47:49||georg.brandl||set||assignee: skrah|
nosy: + skrah
|2009-01-12 20:44:46||ncoghlan||set||messages: + msg79702|
|2009-01-12 20:34:54||mark.dickinson||set||assignee: mark.dickinson -> (no value)|
messages: + msg79700
|2009-01-11 04:57:55||rhettinger||set||priority: high -> normal|
messages: + msg79587
messages: + msg79566
|2009-01-10 18:10:50||mark.dickinson||set||messages: + msg79565|
|2009-01-10 17:47:07||mark.dickinson||set||assignee: facundobatista -> mark.dickinson|
title: Decimal slowdown in 3.0 due to str/unicode changes -> Recode (parts of) decimal module in C
|2009-01-10 17:46:42||mark.dickinson||set||messages: + msg79563|
|2009-01-10 17:45:10||pitrou||set||nosy: + rhettinger|
|2009-01-10 17:42:48||mark.dickinson||set||messages: + msg79560|
|2008-12-04 20:50:19||mark.dickinson||set||messages: + msg76926|
messages: + msg73644
|2008-09-15 23:55:26||facundobatista||set||messages: + msg73286|
|2008-09-15 21:07:19||ncoghlan||set||messages: + msg73281|
|2008-09-15 15:49:44||mark.dickinson||set||messages: + msg73266|
|2008-09-02 16:10:30||facundobatista||set||assignee: facundobatista|
messages: + msg72350
|2008-09-02 14:37:24||ncoghlan||set||priority: high|
messages: + msg72342
versions: + Python 3.1, - Python 3.0
|2008-05-04 14:37:50||facundobatista||set||messages: + msg66211|
title: Consider using bytes type instead of str to store Decimal coefficients -> Decimal slowdown in 3.0 due to str/unicode changes
messages: + msg66155
|2008-03-26 02:30:01||ncoghlan||set||messages: + msg64538|
keywords: + patch
messages: + msg64531