msg73624  (view) 
Author: Pernici Mario (pernici) 
Date: 20080923 10:25 
In this patch x_mul(a, b) uses fewer bit operations for a != b,
asymptotically half of them.
On the three computers I tried the speedup is around 5% for size=4
and it increases up to 4560% just below the Karatsuba cutoff,
then it decreases a bit after this cutoff (on one computer the speedup
is only 16% after KARATSUBA_CUTOFF=70, but raising the cutoff to 140,
for which with the current code the multiplication is also faster,
the speedup is 45%).

msg73694  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20080924 09:19 
Just to be clear: this patch halves the number of shifts and masks,
asymptotically; it doesn't affect the number of adds and multiplies
(except for saving a few additions to zero by setting the initial carry
intelligently). Is that correct? It's quite surprising that the bit
operations have such a large effect on the running time.
Perhaps this is an argument for considering changing PyLong_SHIFT to 16
(or better, 32, since surely almost every compiler provides uint64_t or
equivalent these days)? Though that would be quite an involved task.
While I believe the idea is sound, the patch isn't quite correctit's
got some assertions that won't always hold. For example, with the
patch, in a debug build of Python, I get:
>>> a = b = 2**301
[36413 refs]
>>> a*b
Assertion failed: (carry <= PyLong_MASK), function x_mul, file
Objects/longobject.c, line 2228.
Abort trap
I'm fairly sure that the assert(carry <= PyLong_MASK) doesn't matter,
and that the assertion at the end of the main outer loop (assert(carry
>> PyLong_SHIFT) == 0)) should still hold. But some more comments and
analysis in the code would be good. For example, if carry >=
PyLong_MASK the the comment that 2*MASK + 2*MASK*MASK is contained in a
twodigit isn't so useful. How big can carry get?

msg73722  (view) 
Author: Pernici Mario (pernici) 
Date: 20080924 15:57 
Yes, I think that the speedup is due to reducing the number of
shifts and masks.
Changing PyLong_SHIFT to 16 would be complicated; for instance in
v_iadd() carry could not be a digit of 16 bits anymore; writing code
specific for 64 bit machines would surely improve performance;
maybe with PyLong_SHIFT=30 few changes to the code would be needed?
I did not modify the case a = b.
I changed the documentation, which was wrong,
adding detailed bounds on carry
in the various steps to check that it does not overflow.
I corrected the wrong assertion (carry <= PyLong_MASK).

msg73773  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20080925 08:44 
Thanks for the updated patch! Looks good, on a quick scan.
(One comment typo I noticed: there's a line
BASE  3 = 2*MASK  1
presumably this should be 2*BASE  3 on the LHS.)
Just out of interest, is it possible to go further, and combine 4
partial multiplications at once instead of 2? Or does the extra
bookkeeping involved make it not worth it?
I think it's important to make sure that any changes to longobject.c
don't slow down operations on small integers (where "small" means "less
than 2**32") noticeably.
Re: possible changes to PyLong_SHIFT
Yes, changing PyLong_SHIFT to 16 (or 32) would be complicated, and would
involve almost a complete rewrite of longobject.c, together with much
else... It wasn't really a serious suggestion, but it probably would
provide a speedup. The code in GMP gives some idea how things might work.
Changing PyLong_SHIFT to 30 doesn't seem like a totally ridiculous idea,
though. One problem is that there's no 64bit integer type (for
twodigits) in *standard* C89; so since Python is only allowed to assume
C89 there would have to be some fallback code for those (very few,
surely) platforms that didn't have a 64bit integer type available.
On 64bit machines one could presumably go further, and have
PyLong_SHIFT be 60 (or 62, or 63  but those break the assumption
in long_pow that the PyLong_SHIFT is a multiple of 5). This would
depend on the compiler providing a 128bit type for twodigits (like
__uint128_t on gcc/x8664). Probably not worth it, especially if it
ends up slowing down operations on everyday small integers.
Any of these changes is also going to affect a good few other parts of
the codebase (e.g. marshal, pickle?, struct?, floatobject.c, ...). It
shouldn't be difficult to find most of the files affected (just look to
see which files include longintrepr.h), but I have a suspicion there are
a couple of other places that just assume PyLong_SHIFT is 15).

msg74028  (view) 
Author: Pernici Mario (pernici) 
Date: 20080929 14:15 
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%

msg74029  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20080929 14:36 
Nice work! Seems like we're going to be able to look forward to faster
integer arithmetic in Python 2.7 / 3.1. I'll try to find time to review
your patch properly sometime soon.
Regarding the HAVE_INT64, there's a standard autoconf macro
AC_TYPE_INT64_T (and its unsigned counterpart AC_TYPE_UINT64_T) that
automatically sets int64_t (or uint64_t) to a 64bit (unsigned) integer
type whenever it exists. So don't worry about the preprocessor stuff for
the moment, so long as it's working on your machine; we can fix it in
Python's configure script instead sometime.

msg74035  (view) 
Author: Christian Heimes (christian.heimes) * 
Date: 20080929 17:36 
Nice work :)
I'm changing the target versions to 2.7 and 3.1. The proposed changes
are too large for a maintenance release.

msg74430  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20081007 09:15 
It looks as though changing PyLong_SHIFT to 30 everywhere is much simpler
than I feared. Here's a short patch that does exactly that. It:
 changes the definitions in longintrepr.h
 changes marshal.c to write digits as longs, not shorts
 adds some casts to longobject.c (most of which should really
have been there alreadyclearly Python's never encountered
a machine where ints are only 2 bytes long, even though the
standard seems to permit it).
With this patch, all tests pass on my machine with the exception of
the getsizeof tests in test_sys; and sys.getsizeof is working fineit's
the tests that need to be changed.
Still to do:
 use uint64 and uint32 instead of unsigned long long and unsigned long,
when available; this avoids wasting lots of space on platforms
where a long is 64 bits.
 provide fallback definitions for platforms that don't have any 64bit
type available
 (?)expose the value of PyLong_SHIFT to Python somewhere (in sys?); then
the getsizeof tests could use this value to determine whether a digit
is expected to take 2 bytes or 4 (or ...)

msg75495  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20081104 15:37 
I've opened a separate issue (issue 4258) for the idea of using 30bit
long digits instead of 15bit ones. I'll remove the patch from this
issue.
Pernici Mario's idea applies even better to base 2**30 longs: one can
clump together 16 (!) of the multiplications at once, essentially
eliminating the overhead of shifts almost completely.

msg75750  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20081111 17:12 
See issue 4258 for a patch that combines 30bit digits with
this multiplication optimization. The code is quite different
from the patch posted here, but the basic idea is the same.

msg83964  (view) 
Author: Pernici Mario (pernici) 
Date: 20090322 09:53 
This patch comes from 30bit_longdigit13+optimizations1.patch in issue4258
with modification for the case of multiplication by 0; it passes
test_long.py and pidigits is a bit faster.

msg84069  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20090324 09:36 
Thanks! Unfortunately, it looks like I messed this up yesterday by
removing mul1 (after the division patch went in, mul1 wasn't used any
more). I'll fix this.

msg84072  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20090324 10:07 
Updated version of longobject_diff1:
 add mul1 back in
 rename MAX_PARTIALS to the more descriptive BLOCK_MUL_SIZE
 rewrite digits_multiply so that the call to digits_multiply_add
always has b_size=BLOCK_MUL_SIZE, then hardcode this and get
rid of the b_size argument. This should give the compiler some
opportunities for loopunrolling in digits_multiply_add.

msg95792  (view) 
Author: Mark Dickinson (mark.dickinson) * 
Date: 20091128 16:01 
I'm going to close this: it's a really nice idea, but after the 30bit
long digits were implemented, the speedup doesn't seem to be worth the
extra code complication.
The only situation I've found where this optimization really does make a
big difference is when using 60bit digits, but allowing those in Python
would take a bit more work (essentially because it requires using some
inline assembler to get at the CPU widening multiply and 128bitby64bit
division instructions).
