Re: [sage-devel] Re: devising a speed comparison test between different types

[William Stein]

On Sat, Dec 3, 2016 at 10:53 PM, Ralf Stephan <> wrote:

“Both ZZ and numpy use libgmp internally “

No, ZZ uses libgmp (actually really MPIR, which is a fork of GMP), and
numpy uses Python’s ints/longs. Python’s int/long type is arbitrary
precision, despite the confusing naming. It only implements relatively
naive algorithms – karatsuba, etc., – and not the asymptotically fast
Fourier transform methods that GMP (and MPIR) implement and highly
optimize. So Sage’s ZZ will start beating the pants off of Python (and
numpy) when the numbers get large.

Example – try this with various values of “digits” and you’ll see ZZ
being *arbitrarily
faster* than Python’s longs:

def bench(digits):print "digits =", digitsglobal n, m, n1, m1,
n2, m2  # timeit uses global namespacen =
ZZ.random_element(10^digits)m = ZZ.random_element(10^digits)
%timeit n*mn1 = int(n)m1 = int(m)%timeit n1*m1import
numpyn2 = numpy.int(n)m2 = numpy.int(m)%timeit n2*m2

bench(10)bench(100)bench(1000)bench(1)bench(10)bench(100)

digits = 10 625 loops, best of 3: 51.1 ns per loop 625 loops, best of 3:
126 ns per loop 625 loops, best of 3: 107 ns per loop digits = 100 625
loops, best of 3: 445 ns per loop 625 loops, best of 3: 315 ns per loop 625
loops, best of 3: 254 ns per loop digits = 1000 625 loops, best of 3: 2.16
µs per loop 625 loops, best of 3: 13.8 µs per loop 625 loops, best of 3:
13.5 µs per loop digits = 1 625 loops, best of 3: 64.9 µs per loop 625
loops, best of 3: 588 µs per loop 625 loops, best of 3: 618 µs per loop
digits = 10 625 loops, best of 3: 1.47 ms per loop 25 loops, best of 3:
20.9 ms per loop 25 loops, best of 3: 21.9 ms per loop digits = 100 25
loops, best of 3: 18.7 ms per loop 5 loops, best of 3: 870 ms per loop 5
loops, best of 3: 883 ms per loop

# At 1 million digits (on this test machine): ZZ is 46.5 times faster
than Python ints:870 / 18.7

46.5240641711230
See this worksheet. https://cloud.sagemath.com/projects/4a5f0542-5873-4eed-a85c-a18c706e8bcd/files/support/2016-12-04-ints.sagews>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: devising a speed comparison test between different types

[Volker Braun]

On Sunday, December 4, 2016 at 5:58:45 PM UTC+1, Pierre wrote:

> -- numpy.int32 or int.64: like "int" initially, but works mod 2^32 or 
> 2^64, and gives an overflow warning when it happens. No increase in 
> speed, for general reasons which I will just call "overhead" for lack 
> of a better understanding. (Still good for numpy functions, 
> obviously). 
>

Signed overflow is undefined in C/C++ and not necessarily mod 2^x. I'm 
pretty sure that numpy inherits this from C/C++. You must use unsigned 
integer types like numpy.uint64 if you rely on overflow behavior.

The overhead is of course the wrapping in a Python object. If that is 
limiting your computation then you'll have to work in C/Cython with the 
internal integer (machine int or gmp/mpir).

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: devising a speed comparison test between different types

[Pierre Guillot]

PPS come to think of it, my last PS explains it all. So in summary:

-- ZZ= always arbitrary precision.
-- int= a C int when the numbers stay < 2^64, so there is an increase
of speed -- but not nearly as much of an increase as I expected, which
is why I was confused at first, because I wasn't seeing this for what
it was. Also, computations start using "long" when the numbers are
big, so you don't see the overflow, and you don't always see the
increase in speed.
-- numpy.int32 or int.64: like "int" initially, but works mod 2^32 or
2^64, and gives an overflow warning when it happens. No increase in
speed, for general reasons which I will just call "overhead" for lack
of a better understanding. (Still good for numpy functions,
obviously).


2016-12-04 9:11 GMT-05:00 Pierre :
> PS actually, i am a little wrong with Python ints being arbitrary precision.
> In fact there is no such thing as just a python int, there is "int" and
> "long", but computations with ints can give you an answer which is "long";
> presumably this mostly means that everything is as slow as if everything was
> always a "long". Well, i don't really know, and I wish I did.
>
>
> On Sunday, December 4, 2016 at 8:47:12 AM UTC-5, Pierre wrote:
>>
>> Hi all,
>>
>> Thanks for your answers. There are a few things that I now understand, but
>> i'm still confused. One crucial mistake I made was, as I see now thanks to
>> Ralf's message, to believe that numpy.int meant "C int": no, it means python
>> int ! For C ints, use numpy.int32 (or 64). In fact :
>>
>> sage: numpy.int(2) ^ numpy.int(32)
>> 4294967296
>>
>> sage: numpy.int(2) ^ numpy.int(64)
>> 18446744073709551616L   #notice the L, typical of python ints
>>
>> sage: numpy.int32(2) ^ numpy.int32(32)
>> /Applications/SageMath/src/bin/sage-ipython:1: RuntimeWarning: overflow
>> encountered in int_scalars
>> #!/usr/bin/env python
>> 0
>>
>>
>> All as expected. And to answer Simon's interrogation, if I'm correct a
>> python int is actually arbitrary precision (and it prints with an L when
>> above 2^64), but it's slower than ZZ. It's not a C int.
>>
>> However, i've been playing with Simon's code for testing (nice idea!), and
>> i'm still puzzled:
>>
>> sage: %time testfunc(ZZ(1234123), ZZ(1234123), operator.add)
>> CPU times: user 69.3 ms, sys: 787 µs, total: 70.1 ms
>> Wall time: 70.8 ms
>>
>> sage: %time testfunc(int(1234123), int(1234123), operator.add)
>> CPU times: user 42.3 ms, sys: 631 µs, total: 42.9 ms
>> Wall time: 43.5 ms
>>
>> sage: %time testfunc(numpy.int(1234123), numpy.int(1234123), operator.add)
>> CPU times: user 44 ms, sys: 538 µs, total: 44.5 ms
>> Wall time: 45 ms
>>
>> sage: %time testfunc(numpy.int32(1234123), numpy.int32(1234123),
>> operator.add)
>> CPU times: user 74.2 ms, sys: 822 µs, total: 75 ms
>> Wall time: 77.7 ms
>>
>> So ZZ is slightly slower than python int = numpy.int, which is already
>> weird since the arbitrary precision integers of ZZ are meant to faster than
>> those of python.
>>
>> But even more bizarre is the fact that numpy.int32 gives the slowest
>> performance! i'm guessing that the operator.add includes overhead when
>> asking numpy to add its ints.
>>
>> Question: Is there a way of using very fast C integers within Sage,
>> without using Cython? (the latter because the answer is meant to be
>> understandable by beginners).
>>
>> If I figure this out, I guess the analogous question with floats will be
>> answered, too.
>>
>> Thanks !
>>
>> Pierre
>>
>>
>>
>>
>>
>>
>>
>
> --
> You received this message because you are subscribed to a topic in the
> Google Groups "sage-devel" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/sage-devel/HNX5rHzuBc8/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> sage-devel+unsubscr...@googlegroups.com.
> To post to this group, send email to sage-devel@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.



-- 
Pierre
06 06 40 72 28

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.