Opened 3 years ago

Closed 3 years ago

#15654 closed defect (fixed)

PARI discriminant speed depends on stack size

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-6.2
Component: performance Keywords:
Cc: pbruin Merged in:
Authors: Jeroen Demeyer Reviewers: David Roe
Report Upstream: Reported upstream. Developers deny it's a bug. Work issues:
Branch: u/jdemeyer/ticket/15654 (Commits) Commit: a955e45e17cdbd40d24a103ef7903c5f970b24a3
Dependencies: #15653 Stopgaps:

Description (last modified by jdemeyer)

This is weird and bad:

sage: x = polygen(ZpFM(3,10))
sage: p = ((x-1)^50 + x)._pari_init_()
sage: %time pari(p).poldisc()
CPU times: user 52.73 s, sys: 0.00 s, total: 52.73 s
Wall time: 52.82 s
2*3 + 3^4 + 2*3^6 + 3^7 + 2*3^8 + 2*3^9 + O(3^10)
sage: pari.allocatemem(2<<20)
PARI stack size set to 2097152 bytes
sage: %time pari(p).poldisc()
CPU times: user 0.08 s, sys: 0.00 s, total: 0.08 s
Wall time: 0.08 s
2*3 + 3^4 + 2*3^6 + 3^7 + 2*3^8 + 2*3^9 + O(3^10)

Upstream: http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1507

Change History (18)

comment:1 Changed 3 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 3 years ago by jdemeyer

  • Description modified (diff)
  • Summary changed from Extremely slow PARI discriminants to PARI discriminant speed depends on stack size

comment:3 Changed 3 years ago by jdemeyer

  • Description modified (diff)
  • Report Upstream changed from N/A to Reported upstream. No feedback yet.

comment:4 Changed 3 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Dependencies set to #15653

comment:5 Changed 3 years ago by jdemeyer

  • Report Upstream changed from Reported upstream. No feedback yet. to Reported upstream. Developers deny it's a bug.

comment:6 Changed 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/15654
  • Created changed from 01/09/14 14:03:17 to 01/09/14 14:03:17
  • Modified changed from 01/09/14 16:04:16 to 01/09/14 16:04:16

comment:7 Changed 3 years ago by jdemeyer

  • Commit set to a955e45e17cdbd40d24a103ef7903c5f970b24a3
  • Status changed from new to needs_review

New commits:

7537427Fix conversion of zero p-adics to PARI
a955e45Speed up PARI determinants when stacksize is small

comment:8 Changed 3 years ago by jdemeyer

This solution works well for Sage, maybe not for PARI/GP upstream.

comment:9 follow-ups: Changed 3 years ago by roed

I'm fine with this change. I'm not yet familiar with reviewing SPKG changes using the new directory layout. Why is SPKG.txt deleted in this commit?

More generally, are there other places in Sage where we should be more aggressive about increasing the Pari stack size? If someone is using Pari nontrivially, our current stack size seems too small. Should we increase the stack whenever a user does certain operations signaling that they're going to be using Pari extensively (e.g. create a number field of degree larger than 4, take the discriminant of a polynomial of large degree...)?

comment:10 in reply to: ↑ 9 Changed 3 years ago by jdemeyer

Replying to roed:

I'm fine with this change. I'm not yet familiar with reviewing SPKG changes using the new directory layout. Why is SPKG.txt deleted in this commit?

Not all of SPKG.txt, just the changelog.

comment:11 in reply to: ↑ 9 Changed 3 years ago by jdemeyer

Replying to roed:

More generally, are there other places in Sage where we should be more aggressive about increasing the Pari stack size? If someone is using Pari nontrivially, our current stack size seems too small. Should we increase the stack whenever a user does certain operations signaling that they're going to be using Pari extensively (e.g. create a number field of degree larger than 4, take the discriminant of a polynomial of large degree...)?

We could detect the problem by adding some code to gerepile...() to count the number of garbage collections. We could for example give a warning if more than N happen per second (for a suitable value of N).

comment:12 Changed 3 years ago by jdemeyer

See #15659.

comment:13 in reply to: ↑ 9 Changed 3 years ago by jdemeyer

Replying to roed:

More generally, are there other places in Sage where we should be more aggressive about increasing the Pari stack size?

Yes, see #15660.

comment:14 Changed 3 years ago by roed

Cool. I'm doctesting this ticket and will then give it a positive review.

comment:15 Changed 3 years ago by roed

  • Reviewers set to David Roe
  • Status changed from needs_review to positive_review

Looks good.

comment:16 Changed 3 years ago by vbraun

  • Priority changed from critical to major

Ok, this is not "critical"

comment:17 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:18 Changed 3 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.