[issue3944] faster long multiplication

[Pernici Mario]

Pernici Mario <pernici at users.sourceforge.net> added the comment:

Mark, following your suggestions about using bigger integer types,
I added code to convert Python numbers to arrays of twodigits,
when a 64 bit integer type is supported, and for numbers with size
larger than 20; otherwise the code of the previous patch is used.
This 64 bit integer is used only inside multiplication, so no
modifications need to be made in other parts of the Python code.
Now with numbers with 300 decimal digits or more the speedup is
2x on 32 bit machine, 3x on 64 bit machine (50% and 2x respectively
for squaring).

There is a macro HAVE_INT64 to control if there is a 64 bit type;
the preprocessor instructions should be OK with gcc, but other
compilers might have a 64 bit type and not long long, so HAVE_INT64
is wrongly not defined and one falls back to multiplying arrays of
16 bit digits; these preprocessor instructions need to be fixed.

The speed difference for small integers is small;
here is a summary of some benchmarks on
Pentium M 1.6GHz, Athlon XP 2600+,
Athlon 64 X2 Dual Core 3800+, all with Debian;
speedup of this patch with respect to the current revision
(+ means the patch is faster):
In pybench, SimpleIntegerArithmetic: from -0.5% to +0.5%
            SimpleLongArithmetic:  : from -1% to +7%
pystone                            : from +0.5% to +1.5%

Added file: http://bugs.python.org/file11653/longobject2.diff

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue3944>
_______________________________________