Ticket #467 (closed enhancement: fixed)

Opened 1 year ago

Last modified 1 year ago

[with patch] asymptotically slow pari integer conversions

Reported by: dmharvey Assigned to: craigcitro
Priority: minor Milestone: sage-2.8.7
Component: basic arithmetic Keywords:
Cc:

Description

The conversion function from PARI integers to python longs is asymptotically slow (apparantly quadratic time). This shows up when doing something like int(some_pari_object). Similarly from SAGE integers to PARI integers.

There are also inconsistencies like (on my machine at home): 

sage: x = 10^100000

sage: time y = pari(x)
CPU times: user 1.18 s, sys: 0.01 s, total: 1.19 s
Wall time: 1.26

sage: time z = Integer(y)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.02

sage: time u = int(y)
CPU times: user 1.94 s, sys: 1.33 s, total: 3.27 s
Wall time: 3.58

sage: time u = int(Integer(y))
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.03

now see the quadratic time: 

sage: x = 10^1000000

sage: time y = pari(x)
CPU times: user 105.12 s, sys: 1.26 s, total: 106.38 s
Wall time: 121.86

sage: time z = Integer(y)
CPU times: user 0.03 s, sys: 0.02 s, total: 0.05 s
Wall time: 0.09

sage: time u = int(y)
CPU times: user 188.17 s, sys: 145.12 s, total: 333.28 s
Wall time: 364.80

sage: time u = int(Integer(y))
CPU times: user 0.04 s, sys: 0.02 s, total: 0.06 s
Wall time: 0.07

Attachments

convert.hg (3.4 kB) - added by craigcitro on 10/12/2007 12:49:47 PM.

Change History

09/10/2007 07:41:41 PM changed by mabshoff

  • milestone set to sage-feature.

09/13/2007 07:56:54 PM changed by was

  • type changed from defect to enhancement.

10/10/2007 04:56:22 PM changed by craigcitro

  • owner changed from somebody to craigcitro.

10/10/2007 04:56:27 PM changed by craigcitro

  • status changed from new to assigned.

10/12/2007 12:49:24 PM changed by craigcitro

  • summary changed from asymptotically slow pari integer conversions to [with-patch] asymptotically slow pari integer conversions.
  • milestone changed from sage-feature to sage-2.8.7.

So I've fixed half of the above problems, namely the Pari <--> SAGE issues. I'm going to make a patch for the Pari <--> int issues, but since 2.8.7 is imminent, I thought it would be worth getting this posted first. Here's the state of affairs after the first patch: 

sage: x = 10^100000

sage: time y = pari(x)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00

sage: time z = Integer(y)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00

sage: time u = int(y)
CPU times: user 1.64 s, sys: 1.09 s, total: 2.73 s
Wall time: 2.79

sage: time u = int(Integer(y))
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00

sage: x = 10^1000000

sage: time y = pari(x)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01

sage: time z = Integer(y)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00

sage: time u = int(y)
CPU times: user 220.90 s, sys: 137.34 s, total: 358.24 s
Wall time: 408.11

sage: time u = int(Integer(y))
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01

There is a small (20%) improvement on pari --> sage with this patch, and a much larger (at least 5X, up to 7-8X depending on the length of the number) improvement on sage --> pari with this patch. Running y._pari_() with y an element of ZZ is the fastest way to get the corresponding pari element, as pari(y) has just a bit more overhead (it ultimately calls y._pari_() after a few typechecks and whatnot).

The other ticket (with the pari <--> python long issue) is #864.

10/12/2007 12:49:47 PM changed by craigcitro

  • attachment convert.hg added.

10/12/2007 03:18:00 PM changed by craigcitro

  • summary changed from [with-patch] asymptotically slow pari integer conversions to [with patch] asymptotically slow pari integer conversions.

10/12/2007 11:29:31 PM changed by was

This has a serious problem: 

22:42 < cwitty_> I was looking at #467, and I just crashed SAGE with a PARI stack overflow.
22:43 < cwitty_> I thought the stack was supposed to resize automatically, or something?  (Or at least
                 not crash SAGE.)
22:44 < cwitty_> sage: n = 10^10000000
22:44 < cwitty_> sage: %time _ = pari(n)
22:44 < cwitty_>   ***   the PARI stack overflows !
22:44 < cwitty_>   current stack size: 8000000 (7.629 Mbytes)
22:44 < cwitty_>   [hint] you can increase GP stack with allocatemem()
22:44 < cwitty_> /home/cwitty/sage/local/bin/sage-sage: line 205: 25703 Aborted
                 sage-ipython -c "$SAGE_STARTUP_COMMAND;" "$@"
22:44 < cwitty_> (This is after I applied the patch from #467.)
22:45 < williamstein> weird.
22:45 < williamstein> it should automatically double *if* the author correctly uses _sig_on/_sig_off
22:47 < cwitty_> This is the ZZ->Pari fast coercion patch, and I'm pretty sure (from skimming the patch)
                 that he never touches _sig_on/_sig_off.  So that's probably it.

See trac #

10/12/2007 11:40:11 PM changed by was

  • status changed from assigned to closed.
  • resolution set to fixed.