Mutable integers?

[GoogleCodeExporter]

From http://www.aleax.it/gmpy.html, "Early tests have shown that supporting
Python 2's "in-place operation" functionality (by making MPZ, MPF and MPQ
Python objects mutable) would offer a substantial performance boost."

How much work would it be to add a mutable integer type? E.g. for mpmath,
this could potentially speed up series evaluation, using some strategy like
the following (note that this is fully backwards compatible):

try:
    MUTABLE = gmpy.mutable_mpz
except:
    MUTABLE = gmpy.mpz

def exp(x, prec):
    s = MUTABLE(1<<prec)
    t = MUTABLE(s)
    k = 1
    while t:
        t *= x
        t >>= prec
        t //= k
        s += t
        k += 1
    return gmpy.mpz(s)

(Not as fast as writing the same code in C with mutable GMP numbers, but if
it could speed up Python-implemented algorithms...)

Original issue reported on code.google.com by fredrik....@gmail.com on 24 Feb 2009 at 11:09

[GoogleCodeExporter]

I've done some comparisons between mutable and immutable GMP numbers using 
Cython.
There was a significant performance difference in the Cython but I didn't see
significant performance differences between mutable mpz (via Cython) and 
immutable
(via gmpy) mpz. It turns out that gmpy does a lot of caching which eliminates 
much of
the allocation overhead. If I disable gmpy's caching, then immutables are 
faster.

That comment may predate the inclusion of caching in gmpy.

Original comment by casevh on 4 May 2009 at 5:58

• Added labels: Priority-Low, Type-Enhancement
• Removed labels: Priority-Medium, Type-Defect

[GoogleCodeExporter]

I have done additional testing with mutable mpz. I added support for standard,
immutable inplace operations and a compile-time option to use mutable 
operations.
Using a naive factorial calculation "for i in xrange(10000000): fact*=i" as a
benchmark, I see a 4% improvement just by adding the immutable inplace 
operations. I
see a 30% improvement when using mutable operations. 

When I benchmark runtests.py with gmpy using the immutable inplace operations, 
I see
less than a 1% improvement. As expected, it fails with mutable inplace 
operations. 

I tested your example with 1000000 iterations of exp(1, 1000). Measurements are:
gmpy 1.10: 2.5 seconds
gmpy 1.11: 2.4 seconds (with immutable mpz)
gmpy 1.11: 2.1 seconds (with mutable mpz)

Is the benefit significant for you?

Original comment by casevh on 17 Nov 2009 at 8:20

[GoogleCodeExporter]

A 10-20% improvement is not worth it, IMO, even if it's slightly better than 
that at
lower precision. Better to just do the critical parts in C directly.

Original comment by fredrik....@gmail.com on 18 Nov 2009 at 11:36

[GoogleCodeExporter]

An update on an old issue....

The final version of GMPY 1.11 added caching of gmpy.mpz objects in addition to 
the caching of GMP mpz_t objects. This eliminated almost all the performance 
advantages of a mutable integer type. But I still had to try...

I renamed the gmpy development trunk to gmpy2 so I could be more aggressive in 
making changes. I added an mutable integer called xmpz. It inter-operates with 
the other integer types. When the result type is ambiguous (i.e. mpz + xmpz), 
the result type is controlled by gmpy2.set_prefer_mutable. If you work with 
xmpz and want to convert it to an mpz, use xmpz.make_mpz. It just swaps 
pointers around but has the side-effect of setting the original xmpz to 0. 
Unfortunately, even after all this work, it isn't faster for the exp(1,prec) 
test until the precision is around 10000,

I did add additional bit operations. I changed all the names to start with bit_ 
so scan0 is now bit_scan0. 

Both mpz and xmpz support the slice notation. As a side-effect, len(mpz) now 
returns the length in bits but considers 0 to have a length of 1.

Please let me know if any of the changes, especially the bit operations or 
direct access to bit positions are of benefit. 

Original comment by casevh on 29 Jul 2010 at 6:49

[GoogleCodeExporter]

Thanks!

I found both the mutable mpz and the bit access methods to be useful.

I just d/l'd GMPY (1.12) last night to solve a problem I was having with fast 
polynomial multiplication (I wanted to use GMP's FFT multiply). I needed to 
rapidly set up / read off the mpz types, so I back-ported the slice reading to 
1.12 last night and implemented a half-baked slice assignment in 
gmpy_mpz_mutate today, which seems to work well enough, but isn't especially 
robust.

I can upload the modified files if there is interest, and would welcome 
feedback (as this is my first GMP and python-C development project, but I don't 
know if there is any interest in continued development along the 1.12 branch 
(despite it being the featured download)

Original comment by keith.a....@gmail.com on 30 Jul 2010 at 11:33

[GoogleCodeExporter]

Are you reading continuous ranges of bits? If so, I may be able to optimize 
that particular operation, at least for a long enough range.

I'm trying not to add new features to 1.1x but I will be releasing 1.13 to fix 
a bug.

Even though it's not a featured download, can you use the latest SVN version?

Can you provide an example of your fast polynomial multiplication? I'd like to 
see how you're using GMPY and mutable integer.

Original comment by casevh on 2 Aug 2010 at 7:41

[GoogleCodeExporter]

Right now, I'm only using the mutability to construct the integer via slices, 
although I could probably use more of the methods as I optimize my code. I am 
reading (and setting) continuous ranges. I've pulled out the poly fft 
multiplication code, and my subscript assignment code as attachments.

I have just checked out the current version in svn, but haven't started working 
with it yet.

Original comment by keith.a....@gmail.com on 2 Aug 2010 at 11:10

Attachments:

• subscript_assign
• poly_fft

[GoogleCodeExporter]

A couple of suggestions. The SVN version has bit_mask() and bit_length()/len(). 
(bit_length(0) returns 0 but len(0) returns 1)

Are the coefficients always positive? 

How large are the coefficients?

Original comment by casevh on 3 Aug 2010 at 4:33

[GoogleCodeExporter]

In my case the coefficients are positive, and I've used multiplicand 
coefficients up to about 400 bits (with polynomials having about 10^5 terms). 
I'd like to get up to about 650 bits (~200 digits), but my surrounding code is 
still too inefficient overall.

Original comment by keith.a....@gmail.com on 3 Aug 2010 at 8:04

[GoogleCodeExporter]

I've created issue 42 to track this as a general purpose enhancement. It has 
been on my list for a while.

Original comment by casevh on 4 Aug 2010 at 1:01

[GoogleCodeExporter]

Added pack() and unpack() in issue 42. The following polynomial multiply code 
is approximately 3x to 5x faster:

def FftMultiply2(self, multiplicand):
    n = min(len(self), len(multiplicand))
    max_s = max(self)
    max_m = max(multiplicand)
    bit_size = gmpy2.bit_length(n) \
                + gmpy2.bit_length(max_s) + gmpy2.bit_length(max_m)
    m1 = gmpy2.pack(self, bit_size)
    m2 = gmpy2.pack(multiplicand, bit_size)
    return gmpy2.unpack(m1 * m2, bit_size)

Original comment by casevh on 12 Aug 2010 at 5:48

[GoogleCodeExporter]

Mutable integers are available in gmpy2.

Original comment by casevh on 11 Mar 2011 at 3:14

• Changed state: Fixed