Sage: Ticket #467: [with patch] asymptotically slow pari integer conversions
https://trac.sagemath.org/ticket/467
<p>
The conversion function from PARI integers to python longs is asymptotically slow (apparantly quadratic time). This shows up when doing something like <code>int(some_pari_object)</code>. Similarly from SAGE integers to PARI integers.
</p>
<p>
There are also inconsistencies like (on my machine at home):
</p>
<pre class="wiki">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
</pre><p>
now see the quadratic time:
</p>
<pre class="wiki">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
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/467
Trac 1.1.6mabshoffTue, 11 Sep 2007 02:41:41 GMTmilestone set
https://trac.sagemath.org/ticket/467#comment:1
https://trac.sagemath.org/ticket/467#comment:1
<ul>
<li><strong>milestone</strong>
set to <em>sage-feature</em>
</li>
</ul>
TicketwasFri, 14 Sep 2007 02:56:54 GMTtype changed
https://trac.sagemath.org/ticket/467#comment:2
https://trac.sagemath.org/ticket/467#comment:2
<ul>
<li><strong>type</strong>
changed from <em>defect</em> to <em>enhancement</em>
</li>
</ul>
TicketcraigcitroWed, 10 Oct 2007 23:56:22 GMTowner changed
https://trac.sagemath.org/ticket/467#comment:3
https://trac.sagemath.org/ticket/467#comment:3
<ul>
<li><strong>owner</strong>
changed from <em>somebody</em> to <em>craigcitro</em>
</li>
</ul>
TicketcraigcitroWed, 10 Oct 2007 23:56:27 GMTstatus changed
https://trac.sagemath.org/ticket/467#comment:4
https://trac.sagemath.org/ticket/467#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>assigned</em>
</li>
</ul>
TicketcraigcitroFri, 12 Oct 2007 19:49:24 GMTmilestone, summary changed
https://trac.sagemath.org/ticket/467#comment:5
https://trac.sagemath.org/ticket/467#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-feature</em> to <em>sage-2.8.7</em>
</li>
<li><strong>summary</strong>
changed from <em>asymptotically slow pari integer conversions</em> to <em>[with-patch] asymptotically slow pari integer conversions</em>
</li>
</ul>
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
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).
</p>
<p>
The other ticket (with the pari <--> python long issue) is <a class="closed ticket" href="https://trac.sagemath.org/ticket/864" title="enhancement: Asymptotically slow PARI --> Python long conversions (closed: fixed)">#864</a>.
</p>
TicketcraigcitroFri, 12 Oct 2007 19:49:47 GMTattachment set
https://trac.sagemath.org/ticket/467
https://trac.sagemath.org/ticket/467
<ul>
<li><strong>attachment</strong>
set to <em>convert.hg</em>
</li>
</ul>
TicketcraigcitroFri, 12 Oct 2007 22:18:00 GMTsummary changed
https://trac.sagemath.org/ticket/467#comment:6
https://trac.sagemath.org/ticket/467#comment:6
<ul>
<li><strong>summary</strong>
changed from <em>[with-patch] asymptotically slow pari integer conversions</em> to <em>[with patch] asymptotically slow pari integer conversions</em>
</li>
</ul>
TicketwasSat, 13 Oct 2007 06:29:31 GMT
https://trac.sagemath.org/ticket/467#comment:7
https://trac.sagemath.org/ticket/467#comment:7
<p>
This has a serious problem:
</p>
<pre class="wiki">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.
</pre><p>
See trac #
</p>
TicketwasSat, 13 Oct 2007 06:40:11 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/467#comment:8
https://trac.sagemath.org/ticket/467#comment:8
<ul>
<li><strong>status</strong>
changed from <em>assigned</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
Ticket