pari slowness

[David Harvey]

Hi,

This is on an 8-core 2GHz xeon running debian. (Tom Boothby's machine.)

In a clean build of sage-3.0.2:

sage: time x = bernoulli(40000)
CPU times: user 4.19 s, sys: 0.01 s, total: 4.20 s
Wall time: 4.20 s
sage: time x = bernoulli(40000)
CPU times: user 3.18 s, sys: 0.01 s, total: 3.18 s
Wall time: 3.19 s
sage: time x = bernoulli(40000)
CPU times: user 3.18 s, sys: 0.00 s, total: 3.19 s
Wall time: 3.19 s
sage: time x = bernoulli(40000)
CPU times: user 3.18 s, sys: 0.00 s, total: 3.19 s
Wall time: 3.19 s

Then I tried building my own PARI/GP. I first built gmp 4.2.1 with
jason martin's core 2 patches. Then I built pari/gp. I get:

? #
timer = 1 (on)
? x = bernfrac(40000);
time = 1,972 ms.
? x = bernfrac(40000);
time = 1,317 ms.
? x = bernfrac(40000);
time = 1,316 ms.
? x = bernfrac(40000);
time = 1,316 ms.

Why is the sage version three times slower than the gp version?

david

[mabshoff]

On Jun 9, 10:05 am, David Harvey <dmhar...@math.harvard.edu> wrote:
> Hi,

Hi David,

No clue. Can you actually compare the gp binary from Sage directly
with the timings from your self builid binary to eliminate the problem
that libPari is involved here? If the gp binary in Sage is slower by a
factor of three compared to the one you build this sounds like a bug
to me. But it could also be conversation overhead for example.

> david

Cheers,

Michael

[boo...@u.washington.edu]

FYI, when I computed bernoulli(10^7+4), I did so from sage -gp -- not from the sage interface to gp.

[David Harvey]

With sage -gp, I get something *in between*:

? x = bernfrac(40000);
time = 3,272 ms.
? x = bernfrac(40000);
time = 2,260 ms.
? x = bernfrac(40000);
time = 2,260 ms.

The banner printout is exactly the same for both gp builds:

GP/PARI CALCULATOR Version 2.3.3 (released)
amd64 running linux (x86-64/GMP-4.2.1 kernel) 64-
bit version
compiled: Jun 9 2008, gcc-4.1.2 20061115 (prerelease)
(Debian 4.1.1-21)
(readline v5.2 enabled, extended help available)

except that my standalone build says "readline not compiled in".

david

[Jonathan Bober]

On Mon, 2008-06-09 at 10:19 -0700, mabshoff wrote:
>
> [...]

> No clue. Can you actually compare the gp binary from Sage directly
> with the timings from your self builid binary to eliminate the problem
> that libPari is involved here? If the gp binary in Sage is slower by a
> factor of three compared to the one you build this sounds like a bug
> to me. But it could also be conversation overhead for example.

Definitely could be conversion overhead. On my machine (warning: I'm
still running the "ridiculously old" Sage 2.10.2) I get

sage: time y = pari(40000).bernfrac()
CPU times: user 4.14 s, sys: 0.00 s, total: 4.14 s
Wall time: 4.15
sage: type(y)
<type 'sage.libs.pari.gen.gen'>
sage: time x = Rational(y)
CPU times: user 1.50 s, sys: 0.00 s, total: 1.50 s
Wall time: 1.50

It looks like the conversion from sage.lib.pari.gen.gen to
sage.rings.rational.Rational just converts y to a string and then parses
the resulting string, which is why this takes so long.

[David Harvey]

That's true, that definitely accounts for part of it.

But there's still quite a big gap between the times from sage -gp and
from my standalone GP build (see my followup email earlier on this
thread).

I wonder if we are just building GMP incorrectly. That bernfrac()
routine should depend mainly on the speed of long integer
multiplication and division. I am not a GP expert --- how does one
generate large random integers in GP? I could try multiplying them to
see how long that takes.

david

[Michael Abshoff]

 
Yep.

But there's still quite a big gap between the times from sage -gp and
from my standalone GP build (see my followup email earlier on this
thread).

Yes.
 

I wonder if we are just building GMP incorrectly. That bernfrac()
routine should depend mainly on the speed of long integer
multiplication and division. I am not a GP expert --- how does one
generate large random integers in GP? I could try multiplying them to
see how long that takes.

Well, I believe that out spkg-install for GMP is potentially broken since we updated to gmp 4.2.2. There are also some potential issues with pre-3.0.3 gmp.spkgs, so I am adding some explicite messages that lets you know that Jason's GMP patch was actually applied.
 

david

Cheers,

Michael
 

[David Harvey]

On Jun 9, 2008, at 5:35 PM, Michael Abshoff wrote:

I wonder if we are just building GMP incorrectly. That bernfrac()

routine should depend mainly on the speed of long integer
multiplication and division. I am not a GP expert --- how does one
generate large random integers in GP? I could try multiplying them to
see how long that takes.

Well, I believe that out spkg-install for GMP is potentially broken since we updated to gmp 4.2.2. There are also some potential issues with pre-3.0.3 gmp.spkgs, so I am adding some explicite messages that lets you know that Jason's GMP patch was actually applied.

In which version of sage did we switch to gmp 4.2.2? I will try building the previous version on this machine and compare results.

david

[William Stein]

The last version, so that we could build on cygwin, and also it was needed
for OS X 10.5 64-bit. We will switch to mpir soon, as soon as there is a
release :-)

-- William

[Bill Hart]

Doesn't gmp 4.2.1 build on cygwin? Do you happen to recall what the
issues were, as it'll be a problem for mpir too (though I did manage
one build on cygwin already).

Bill.

On 9 Jun, 22:58, "William Stein" <wst...@gmail.com> wrote:

[mabshoff]

Hi Bill,

On Jun 9, 3:07 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
> Doesn't gmp 4.2.1 build on cygwin? Do you happen to recall what the
> issues were, as it'll be a problem for mpir too (though I did manage
> one build on cygwin already).
>
> Bill.

At some point after a recent Cygwin update gmp 4.2.1 ceased to build
with some sort of assembly error. Cygwin itself updated to gmp 4.2.2,
so I do not know if it is a bug they just missed. I also noticed that
even with vanilla gmp 4.2.2 on OSX "ABI=64" is not supported which
really confused me since I got gmp to compile to compile in 64 bit
mode on OSX before. But it seems like config.guess misidentifies some
recent Core2 Quad CPUs, i.e.

http://groups.google.com/group/sage-support/t/3371db245e33a79c

from today and also some mention about that with that recent Japanese
Core2 patch for gmp discussed on mpir-devel this week.

Cheers,

Michael

[David Harvey]

On Jun 9, 2008, at 5:17 PM, Jonathan Bober wrote:

This is now

http://trac.sagemath.org/sage_trac/ticket/3387

(this ticket does not include the discrepancy in GP timings)

david

[mabshoff]

Good.

> (this ticket does not include the discrepancy in GP timings)
>
> david

Craig Citro did *a lot* of work on pari<->Sage conversation a while
back and there are still some cases open. So once Craig sees this he
might have some explanation what needs to get done since he knows the
code well and might already have something that was never submitted
since it needs cleanup.

Cheers,

Michael

[William Stein]

Patch up. Please review.

William

[David Harvey]

Okay, I can confirm that with sage 3.0.1, sage -gp has the same speed
as my standalone GP build. So mostly likely the change to GMP 4.2.2
introduced a speed regression (probably the core 2 patches not being
applied properly).

david

[mabshoff]

On Jun 9, 7:01 pm, David Harvey <dmhar...@math.harvard.edu> wrote:
> On Jun 9, 2008, at 5:58 PM, William Stein wrote:

<SNIP>

> > The last version, so that we could build on cygwin, and also it was  
> > needed
> > for OS X 10.5 64-bit.   We will switch to mpir soon, as soon as  
> > there is a
> > release :-)
>
> Okay, I can confirm that with sage 3.0.1, sage -gp has the same speed  
> as my standalone GP build. So mostly likely the change to GMP 4.2.2  
> introduced a speed regression (probably the core 2 patches not being  
> applied properly).

Ok, I will investigate and made this a blocker for 3.0.3: #3388

As is the gmp.spkg with the Core2 patches and all that fun stuff is a
giant mess including the OSX fixes made by William :)

Let's hope MPIR is here sooner than later ....

> david

Cheers,

Michael

[David Harvey]

On Jun 9, 2008, at 10:36 PM, mabshoff wrote:
>> Okay, I can confirm that with sage 3.0.1, sage -gp has the same speed
>> as my standalone GP build. So mostly likely the change to GMP 4.2.2
>> introduced a speed regression (probably the core 2 patches not being
>> applied properly).
>
> Ok, I will investigate and made this a blocker for 3.0.3: #3388
>
> As is the gmp.spkg with the Core2 patches and all that fun stuff is a
> giant mess including the OSX fixes made by William :)
>
> Let's hope MPIR is here sooner than later ....

I just noticed that the slowness happens on amd64 as well, so
probably Gaudry's patches are not being applied properly either.

This is on alhambra (2.6GHz opteron):

----------------------------------------------------------------------
| SAGE Version 3.0.1, Release Date: 2008-05-05 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------

sage: x = ZZ.random_element(2^10000000)
sage: y = ZZ.random_element(2^10000000)
sage: time z = x * y
CPU times: user 0.19 s, sys: 0.02 s, total: 0.21 s
Wall time: 0.21
sage: time z = x * y
CPU times: user 0.19 s, sys: 0.01 s, total: 0.20 s
Wall time: 0.20
sage: time z = x * y
CPU times: user 0.20 s, sys: 0.00 s, total: 0.20 s
Wall time: 0.20

----------------------------------------------------------------------
| SAGE Version 3.0.2, Release Date: 2008-05-24 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------

sage: x = ZZ.random_element(2^10000000)
sage: y = ZZ.random_element(2^10000000)
sage: time z = x * y
CPU times: user 0.41 s, sys: 0.00 s, total: 0.41 s
Wall time: 0.42 s
sage: time z = x * y
CPU times: user 0.41 s, sys: 0.00 s, total: 0.41 s
Wall time: 0.41 s
sage: time z = x * y
CPU times: user 0.41 s, sys: 0.00 s, total: 0.41 s
Wall time: 0.41 s

david

[David Harvey]

On Jul 22, 2008, at 12:35 PM, David Harvey wrote:

Okay, I can confirm that with sage 3.0.1, sage -gp has the same speed

as my standalone GP build. So mostly likely the change to GMP 4.2.2

introduced a speed regression (probably the core 2 patches not being

applied properly).

Ok, I will investigate and made this a blocker for 3.0.3: #3388

As is the gmp.spkg with the Core2 patches and all that fun stuff is a

giant mess including the OSX fixes made by William :)

Let's hope MPIR is here sooner than later ....

I just noticed that the slowness happens on amd64 as well, so  

probably Gaudry's patches are not being applied properly either.

This seems to have been fixed already in 3.0.5. Sorry for the noise.

david

[mabshoff]

On Jul 22, 11:48 am, David Harvey <dmhar...@math.harvard.edu> wrote:
> On Jul 22, 2008, at 12:35 PM, David Harvey wrote:

<SNIP>

> This seems to have been fixed already in 3.0.5. Sorry for the noise.
>
> david

Hi David,

we reverted to the old gmp 4.2.1 spkg in 3.0.5 since the only reason
to upgrade was to better support Cygwin and OSX 64 bit. Since both of
those platforms are not ready for prime time we decided it would be
the more prudent way to go. Obviously we want eMPIRe in Sage ASAP and
I need to do my share to make this happen, so please remind me
often :)

Cheers,

Michael