Opened 9 years ago

Closed 9 years ago

#12853 closed defect (fixed)

Severe slow-down in elliptic_curve integral_points()

Reported by: jdemeyer Owned by: tbd
Priority: blocker Milestone: sage-5.0
Component: performance Keywords:
Cc: vbaun, SimonKing Merged in: sage-5.0.beta14
Authors: Andrey Novoseltsev Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

Consider the file

E = EllipticCurve([-879984,319138704])
P1 = E.point((540,1188))
P2 = E.point((576,1836))
P3 = E.point((468,3132))
P4 = E.point((612,3132))
P5 = E.point((432,4428))
t = cputime()
pts = E.integral_points([P1,P2,P3,P4,P5])
print "Time:", cputime(t)

With sage-4.8, this takes about 35 seconds. With sage-5.0.beta10, the same test takes about 50 seconds.

This is caused by #11599.

Attachments (1)

trac_12853.patch (3.8 KB) - added by jdemeyer 9 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 follow-up: Changed 9 years ago by novoselt

As a reviewer of #11599: it was a major clean up of the generic scheme code which made it readable and conforming to current Sage framework, please don't unmerge it...

comment:2 Changed 9 years ago by jdemeyer

  • Description modified (diff)

I can confirm that this is caused by #11599. When applying #11599 to sage-5.0.beta3, I get the same slowdown.

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

Replying to novoselt:

As a reviewer of #11599: it was a major clean up of the generic scheme code which made it readable and conforming to current Sage framework, please don't unmerge it...

Well, if the slow-down cannot be fixed, I have not much choice... I don't want to release sage-5.0 with such a massive speed regression.

comment:4 Changed 9 years ago by novoselt

With this patch on Sage-5.0.beta12 the example from the description drops on my machine from 37 to 12 seconds, which seems to be a severe speed-up compared to pre-#11599 state.

Given that this is achieved by a one-liner taking repeated computations out of the loop, perhaps nobody was really bothered by the speed of this code and as long as it works it is fine...

comment:5 Changed 9 years ago by novoselt

For the record: profiler shows drop from 24 to 9 millions of primitive calls.

comment:6 Changed 9 years ago by jdemeyer

  • Authors set to Andrey Novoseltsev
  • Reviewers set to Jeroen Demeyer
  • Status changed from new to needs_review

Positive review provided:

  1. You put a proper commit message in your patch
  2. This actually passes doctests (which I'm checking right now)

Changed 9 years ago by jdemeyer

comment:7 Changed 9 years ago by jdemeyer

I added a commit message and changed some timings. If you agree with my changes, you can set positive_review.

comment:8 Changed 9 years ago by novoselt

  • Status changed from needs_review to positive_review

comment:9 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.0.beta14
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.