> The above change is very sensible, since we know that outP is on
> self.__E2, so should directly create a point on E2 and not check again
> that our point is really on E2 (which is very expensive).
I agree that we should make the change:
else:
outP = self.__E2(outP)
to
else:
outP = self.__E2.point(outP,check=False)
When I originally wrote the code I did not know that this problem
existed. I just wanted to map a pair of elements on a field to the
elliptic curve point object associated to those coordinates.
I created the ticket:
http://trac.sagemath.org/sage_trac/ticket/6672
and will fix this when I get home tonight (I'm at work right now.)
The fix is very easy, if someone else wants to grab it for now, that
is fine. But just be sure to set check = false in the other point
coercion call as well (in the if block associated with this else
block.)
Thanks,
Dan
On Mon, Aug 3, 2009 at 7:00 PM, William Stein<wst...@gmail.com> wrote:
> On Mon, Aug 3, 2009 at 6:10 PM, VictorMiller<victorsmil...@gmail.com> wrote:
>>
>> Sorry, here's the definition of Q:
>>
>> Q = E.random_element()
>>
>> Victor
>>
>> On Aug 3, 8:45 pm, Simon King <simon.k...@nuigalway.ie> wrote:
>>> Hi!
>>>
>>> On 4 Aug., 02:31, VictorMiller <victorsmil...@gmail.com> wrote:
>>>
>>> > Here are the commands I used:
>>>
>>> > qq = [z for z in primes(100000,100000+100) if (z%12) == 11]
>>> > E = EllipticCurve(j=GF(qq[0])(1728))
>>> > # E has qq[0]+1 points over GF(qq[0])
>>> > factor(qq[0]+1)
>>> > P = ((qq[0]+1)//3)*E.random_element()
>>> > K = [E(0),P,-P]
>>> > phi = E.isogeny(K)
>
> There appears to be a memory leak -- or some sort of caching (!) -- in
> the code to evaluate phi. This is likely impacting the complexity of
> the some code that is run during the computation of phi(P). The log
> below shows that memory usage increases upon evaluation of phi(P):
>
> sage: get_memory_usage()
> 210.109375
> sage: timeit('phi(P)')
> 125 loops, best of 3: 7.13 ms per loop
> sage: get_memory_usage()
> 210.609375
> sage: timeit('phi(P)')
> 125 loops, best of 3: 7.3 ms per loop
> sage: get_memory_usage()
> 211.109375
> sage: timeit('phi(P)')
> 125 loops, best of 3: 7.49 ms per loop
> sage: get_memory_usage()
> 211.609375
> sage: timeit('phi(P)')
> 125 loops, best of 3: 7.69 ms per loop
> sage: get_memory_usage()
> 212.109375
>
> Now I looked at the source code for the function phi(P) =
> phi.__call__(P) and bisected by putting early returns in. If you
> change
>
> else:
> outP = self.__E2(outP)
>
> to
>
> else:
> return outP
> outP = self.__E2(outP)
>
> in that function in ell_curve_isogeny.py (around line 875), then the
> leak and slowdown vanishes.
>
> Thus the real problem is in the "trivial" line "self.__E2(outP)",
> which by the way takes even in good cases like 10 times as long as the
> rest of the whole function put together. Indeed, coercing a point
> into a curve is a horrendous disaster (this is the real problem,
> forget the isogeny stuff):
>
> sage: get_memory_usage()
> 195.81640625
> sage: timeit('E(P)')
> 625 loops, best of 3: 4.24 ms per loop
> sage: get_memory_usage()
> 201.31640625
>
> In fact, the function E.point is to blame, evidently:
>
> sage: timeit('E.point(P)')
> 125 loops, best of 3: 4.13 ms per loop
> sage: get_memory_usage()
> 202.08984375
> sage: timeit('E.point(P)')
> 125 loops, best of 3: 4.4 ms per loop
> sage: get_memory_usage()
> 203.08984375
>
> ... but *ONLY* with check=True (the default):
>
> sage: timeit('E.point(P,check=False)')
> 625 loops, best of 3: 8.26 µs per loop
> sage: get_memory_usage()
> 203.08984375
> sage: timeit('E.point(P,check=False)')
> 625 loops, best of 3: 7.29 µs per loop
> sage: get_memory_usage()
> 203.08984375
>
> I.e., we get a speedup of a factor of nearly 1000 by using
> check=False, plus the leak goes away. So in the check -- which
> involves arithmetic -- maybe the coercion model is surely being
> invoked at some point (I guess), and that is perhaps caching
> information, thus memory usage goes up and performance goes down. I
> don't know, I'm not looking further.
>
> Going back to your original problem, if I change in ell_curve_isogeny.py
>
> else:
> outP = self.__E2(outP)
>
> to
>
> else:
> outP = self.__E2.point(outP,check=False)
>
> then we have the following, which is exactly what you would hope for
> (things are fast, no slowdown).
>
> sage: qq = [z for z in primes(100000,100000+100) if (z%12) == 11]
> sage: E = EllipticCurve(j=GF(qq[0])(1728))
> sage: # E has qq[0]+1 points over GF(qq[0])
> sage: factor(qq[0]+1)
> 2^2 * 3 * 5 * 1667
> sage: P = ((qq[0]+1)//3)*E.random_element()
> sage: K = [E(0),P,-P]
> sage: phi = E.isogeny(K)
> sage: get_memory_usage()
> 190.56640625
> sage: timeit('phi(P)')
> 625 loops, best of 3: 69.8 µs per loop
> sage: for i in xrange(20): timeit('phi(P)')
>
> ....:
> 625 loops, best of 3: 69.3 µs per loop
> 625 loops, best of 3: 69.3 µs per loop
> 625 loops, best of 3: 69.6 µs per loop
> 625 loops, best of 3: 69.9 µs per loop
> 625 loops, best of 3: 69.8 µs per loop
> 625 loops, best of 3: 70 µs per loop
> 625 loops, best of 3: 71.2 µs per loop
> 625 loops, best of 3: 69.3 µs per loop
> 625 loops, best of 3: 70.8 µs per loop
> 625 loops, best of 3: 69.2 µs per loop
> 625 loops, best of 3: 70.2 µs per loop
> 625 loops, best of 3: 70.7 µs per loop
> 625 loops, best of 3: 70 µs per loop
> 625 loops, best of 3: 71 µs per loop
> 625 loops, best of 3: 70 µs per loop
> 625 loops, best of 3: 70.2 µs per loop
> 625 loops, best of 3: 70.1 µs per loop
> 625 loops, best of 3: 70 µs per loop
> 625 loops, best of 3: 70.1 µs per loop
> 625 loops, best of 3: 70.1 µs per loop
>
> The above change is very sensible, since we know that outP is on
> self.__E2, so should directly create a point on E2 and not check again
> that our point is really on E2 (which is very expensive).
>
> I hope the above is helpful and that somebody opens a trac ticket and
> submits a patch. I have to get back to what I was doing... I also
> hope the above email provides some ideas as to how to quickly get to
> the bottom of questions like this. Note that I did all this in < 10
> minutes by using ?? to see where relevant source code is, putting in
> some return statements (often better than print statements), and
> knowing that P(...) means P.__call__.
>
> -- William
>
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support-unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
