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

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.

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.

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[3]
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.

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

I like this path, also.

Beyond Deccoeff, this module could hold in the future other functions
that are speed critical.

Great work, Mark!

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

Can not get into this now, but I'll be able to deal with this in some
weeks...

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.

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?

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

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

Just a quick note to say I am still working on this.  I'll post some new 
code soon.

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

Changing title and assignee.  (But all help is appreciated:  if anyone 
wants to commit changes to the sandbox directory, please go ahead!)

> (2) Bring proposals to add a decimal literal to C ...

That should be "to Python", not "to C", of course.

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

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

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.

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

If issue7652 finishes. There's no point in fixing this bug.

No, this should be closed.