optimize elliptic curve arithmetic: 2*P much slower than P+P

[was]

William, my student noticed some slow performance with elliptic curves group law. I think there was a huge overhead in duplication: sage: E = EllipticCurve?([GF(101)(1),3]) sage: P = E([-1,1,1]) sage: timeit 2*P 100 loops, best of 3: 3.81 ms per loop sage: timeit P+P 1000 loops, best of 3: 1.81 ms per loop Basically n*P was passing through all sorts of high-level layers for group schemes, abelian groups, and the like. I've started teaching two courses here, and at the latest, will have to adapt to becoming a Dad next Tuesday (my wife Martine is overdue). But I may be able to add some code in the next three weeks.

[was]

This was from David Kohel. Here's a better formated version:

William, my student noticed some slow performance with elliptic curves group law. I think there was a huge overhead in duplication:

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
100 loops, best of 3: 3.81 ms per loop
sage: timeit P+P
1000 loops, best of 3: 1.81 ms per loop

Basically n*P was passing through all sorts of high-level layers for group schemes, abelian groups, and the like.

[mabshoff]

I guess this has been fixed. With Sage 2.8.2 I get:

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
1000 loops, best of 3: 317 µs per loop
sage: timeit P+P
10000 loops, best of 3: 92.7 µs per loop

Cheers,

Michael

[was]

Fixed by Robert bradshaw.

[mabshoff]

Ok, reopened.

For details see ​http://groups.google.com/group/sage-devel/t/e884bb605728649a

To quote David Kohel:

I think the problem needs to be profiled.  The problem is likely NOT
in elliptic curves, but some
horrendous chain of calls to module operations before getting to the
(same) actual algorithms.
Note that P*2 is slightly faster since it calls directly the member
function of P rather than a
function on integers.

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
1000 loops, best of 3: 309 µs per loop
sage: timeit P+P
10000 loops, best of 3: 89.8 µs per loop
sage: timeit P*2
1000 loops, best of 3: 204 µs per loop

Yes, reopen it: these sorts of problems need to be looked at and
optimized.  The same problem
applies to points on Jacobians (compare 2*P, P*2, and P+P).

--David 

[was]

As of SAGE-2.8.3 (probably due to Tom Boothby's work), this is now resolved:

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: import timeit
sage: t = timeit.Timer('2*P', 'from sage.all import EllipticCurve, GF; E = EllipticCurve([GF(101)(1),3]); P = E([-1,1,1])')
sage: t.timeit(10000)
1.0524919033050537
sage: s = timeit.Timer('P+P', 'from sage.all import EllipticCurve, GF; E = EllipticCurve([GF(101)(1),3]); P = E([-1,1,1])')
sage: s.timeit(10000)
1.067209005355835