Elliptic curve speed regression?

[Jeroen Demeyer]

Hello,

I have some indication that certain elliptic curve functions became
slower in recent Sage versions (comparing sage-4.7.1 to
sage-4.7.2.alpha3 for example). However, since disk speed and system
load might be factors, it would be nice if we could collect some data
points to see whether this is really the case.

I have prepared two small Sage scripts at:
http://boxen.math.washington.edu/home/jdemeyer/elltest1.sage
http://boxen.math.washington.edu/home/jdemeyer/elltest2.sage

For those who have installed sage-4.7.2.alpha3 and still have an older
version, please do
$ time ./sage elltest1.sage
$ time ./sage elltest2.sage
with both these versions.

[John Cremona]

Regarding integral points, #10973 fixes a bug. The buggy version was
faster but missed points. But that patch is not in 4.7.2.alpha3.

Regarding the first test, I am pretty sure that nothing changed in the
elliptic curve code itself, this must be a side-effect of something
else with arithmetic mod p. But I vaguely remember that William did
something with the abelian_group code, so perhaps he can comment.

John

> --
> You received this message because you are subscribed to the Google Groups "sage-nt" group.
> To post to this group, send an email to sag...@googlegroups.com.
> To unsubscribe from this group, send email to sage-nt+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sage-nt?hl=en-GB.
>
>

[Jeroen Demeyer]

As a first data point, on my laptop I get

elltest1.sage:
* sage-4.7.1 vanilla: 32s
* sage-4.7.2.alpha2 + new PARI + many patches: 27s
* sage-4.7.2.alpha3 + new Singular: 41s

elltest2.sage:
* sage-4.7.1 vanilla: 24s
* sage-4.7.2.alpha2 + new PARI + many patches: 22s
* sage-4.7.2.alpha3 + new Singular: 80s

So certainly something slowed down in sage-4.7.2.alpha3!

[daveloeffler]

Hi Jeroen,

I get the following:

elltest1.sage:
* sage-4.7.1 vanilla: 30.8s
* sage-4.7.2.alpha3: 40.8s

elltest2.sage:
* sage-4.7.1 vanilla: 22.7s
* sage-4.7.2.alpha3: 1m15s

(This is using one of the 2.2Ghz Opteron cores of
"fermat.warwick.ac.uk" -- just to save any of my Warwick colleagues
wasting time by running the exact same test.)

David

[daveloeffler]

On the same machine as above, I ran

sage: %prun EllipticCurve("196a").integral_points()

and compared the output. In 4.7.2.alpha3 it calls "category.join" 2900
times and "category.hom_category" 3918 times. Under 4.7.1 the same
methods get called only 347 and 462 times respectively. Also, the new
alpha calls "posix.stat" 2800 times, while the old one doesn't seem to
use that method at all. These three methods account for the bulk of
the 50% speed regression in this example.

David

[John Cremona]

I don't know if Simon King reads this list, but it would be
interesting to get his view. As I suspected, this is being caused by
some lower level stuff and not anything in
sage/schemes/elliptic_curves itself.

John

[Jeroen Demeyer]

On 2011-10-05 12:59, John Cremona wrote:
> I don't know if Simon King reads this list, but it would be
> interesting to get his view. As I suspected, this is being caused by
> some lower level stuff and not anything in
> sage/schemes/elliptic_curves itself.

I am currently building sage-4.7.2.alpha2 and sage-4.7.2.alpha3 on
sage.math.washington.edu to compare these two versions. Once we have
these data, we should probably post to sage-devel with our findings.

[Jeroen Demeyer]

On sage.math.washington.edu:

elltest1.sage:
* sage-4.7.2.alpha2: 23s
* sage-4.7.2.alpha3: 35s

elltest2.sage:
* sage-4.7.2.alpha2: 17s
* sage-4.7.2.alpha3: 62s

[Simon King]

Hi all!

That regression is awful, and for those not reading sage-devel: The
regression comes from #9138 (sorry for that), and the ticket for
fixing it is #11900.

On 5 Okt., 12:57, daveloeffler <dave.loeff...@gmail.com> wrote:
> On the same machine as above, I ran
>
> sage: %prun EllipticCurve("196a").integral_points()
>
> and compared the output. In 4.7.2.alpha3 it calls "category.join" 2900
> times and "category.hom_category" 3918 times. Under 4.7.1 the same
> methods get called only 347 and 462 times respectively. Also, the new
> alpha calls "posix.stat" 2800 times, while the old one doesn't seem to
> use that method at all.

The reason is that the elliptic curve code constructs many different
matrix spaces. Actually, since weak references are used, some of the
matrix spaces are garbage collected and constructed repeatedly.

#9138 made matrix spaces use the category framework to full extent.
That involves the construction of hom spaces and thus of hom
categories for the coercion of the base ring into the matrix space -
and hom categories use the join() method. That explains your
observation. It helps to improve the cache access for both methods.

In addition, it helps to be more lazy: Rather then constructing it
during initialisation, a coerce map from the base ring should only be
created when needed. Frequently, coercion from the base ring will not
be used at all, hence, there is no need to construct a hom space/hom
category for the coerce map.

Also, there are frequent calls to the list() method of dense vectors
over the rationals and integers. They currently use a generic
implementation. I found that a custom list() will be faster -- that
improvement is independent of categories, for a change.

But I think for avoiding the regression, it may be necessary to exempt
matrix spaces from the full use of categories. After all, the elliptic
curve code seems to use matrix spaces as simple containers, not as
modules or algebras.

Best regards,
Simon

[John Cremona]

On Thu, Oct 6, 2011 at 7:46 AM, Simon King <simon...@uni-jena.de> wrote:
> Hi all!
>
> That regression is awful, and for those not reading sage-devel: The
> regression comes from #9138 (sorry for that), and the ticket for
> fixing it is #11900.
>
> On 5 Okt., 12:57, daveloeffler <dave.loeff...@gmail.com> wrote:
>> On the same machine as above, I ran
>>
>> sage: %prun EllipticCurve("196a").integral_points()
>>

I am mystified about this. The only use integral_points() makes of
matrices is that it does some LLL-reduction on real matrices.

In a loop there are the lines

M = matrix.MatrixSpace(Z,n)
m = copy(M.identity_matrix())

where Z is the Integer ring, and n is constant (not changing in
different passes through the loop). The entries of m are then set
individually before m.LLL() is called. there is probably a better way
of doing this! At present matrix.MatrixSpace(Z,n) will be called
several times with the same parameters, and that line should certainly
be moved outside the loop.

In any case the vast majority of the time taken in integral_points()
is in computing the gens which is done by an external call to mwrank
(about 70s). Then the integral point computation only takes a
fraction of a second, on my machine.

But there must be more to this regression than that!

John

[Simon King]

Hi John!

On 6 Okt., 10:38, John Cremona <john.crem...@gmail.com> wrote:

> On Thu, Oct 6, 2011 at 7:46 AM, Simon King <simon.k...@uni-jena.de> wrote:
> >> sage: %prun EllipticCurve("196a").integral_points()
>
> I am mystified about this.  The only use integral_points() makes of
> matrices is that it does some LLL-reduction on real matrices.
>
> In a loop there are the lines
>
>             M = matrix.MatrixSpace(Z,n)
>             m = copy(M.identity_matrix())
>
> where Z is the Integer ring, and n is constant (not changing in
> different passes through the loop).

Why is M not simply defined outside of the loop?

My patch at #11900 fixes most of the elliptic curve speed regressions
caused by my patches from #9138. I have not tested that particular
example yet, but I hope that I'll be able to fix the remaining
regression as well.

Cheers,
Simon

[John Cremona]

On Thu, Oct 6, 2011 at 12:16 PM, Simon King <simon...@uni-jena.de> wrote:
> Hi John!
>
> On 6 Okt., 10:38, John Cremona <john.crem...@gmail.com> wrote:
>> On Thu, Oct 6, 2011 at 7:46 AM, Simon King <simon.k...@uni-jena.de> wrote:
>> >> sage: %prun EllipticCurve("196a").integral_points()
>>
>> I am mystified about this.  The only use integral_points() makes of
>> matrices is that it does some LLL-reduction on real matrices.
>>
>> In a loop there are the lines
>>
>>             M = matrix.MatrixSpace(Z,n)
>>             m = copy(M.identity_matrix())
>>
>> where Z is the Integer ring, and n is constant (not changing in
>> different passes through the loop).
>
> Why is M not simply defined outside of the loop?

No reason at all. My excuse is that this code was written by two
inexperienced masters students and I rewrote some but not all of it.
That line should be moved out of the loop right away.

John

>
> My patch at #11900 fixes most of the elliptic curve speed regressions
> caused by my patches from #9138. I have not tested that particular
> example yet, but I hope that I'll be able to fix the remaining
> regression as well.
>
> Cheers,
> Simon
>

[Simon King]

Hi John,

On 6 Okt., 14:07, John Cremona <john.crem...@gmail.com> wrote:
> That line should be moved out of the loop right away.

I'll do it, but even with the current version of my patch, %prun
EllipticCurve("196a").integral_points() shows very little overhead.

Cheers,
Simon

[Jeroen Demeyer]

The cause for the slowdown in elltest2.sage is NOT #9138, see my
sage-devel post. It must be some different patch merged in
sage-4.7.2.alpha3. This is the test:

for E in cremona_curves([11..100]):
S = E.integral_points(both_signs=False)

[daveloeffler]

I know what's going on here. The problem is in "E.gens()", which is
called by "E.integral_points()". Note that the slowdown for this
method is even more extreme:

time _=[E.gens() for E in cremona_curves([11..100])]

takes 9s in 4.7.1 and 58s in 4.7.2.alpha3. That is clearly what's
causing the slowdown in Jeroen's elltest2.sage.

The profiler makes it clear what's happened. There are 306 curves in
that list; but for most of them, we know E.gens() is trivial, because
the rank is in the default small version of John's database. So we
only need to do a 2-descent for 22 out of the 306 curves, the ones
whose rank is > 0. Under sage 4.7.1, the profiler confirms that
"sage.libs.mwrank.mwrank._two_descent.do_descent" is indeed only
getting called 22 times. On the other hand, for sage 4.7.2.alpha3,
that method gets called 306 times -- so a 2-descent is being done for
every curve, including the massive number of cases where it's
completely unnecessary because we already know the rank is 0!

John: any idea how this has happened?

David

[daveloeffler]

PS. I've found the culprit: this is a side-effect of #11587. If you
look at "trac_11587.patch", then it removes a couple of lines of code
at lines 710-712 of sage/databases/cremona.py which sets the
generators to [] if the gens aren't explicitly in the database but the
rank is known to be 0. The new version doesn't perform this little
check and so we waste loads of time doing pointless 2-descents.

That's enough sage for one day -- I'm off to have some dinner. :-)

David

[Simon King]

Dear Number Theorists,

for your information: It seems to me that my attempts to fix the
regression was succesful.

With sage-4.7.2.alpha2 (hence, without #9138), the tests in sage/
schemes take 663.5 seconds on my machine. With sage-4.7.2.alpha3
(hence with #9138) plus my fixes from #11900, they only take 597.0
seconds.

The patches from #11900 are less invasive than I originally thought.
In particular, "new coercion for polynomial rings" and "make parent
classes of categories as independent from the base ring as possible"
is not part of the patches.

Best regards,
Simon

[John Cremona]

Well done and thank you. Unfortunately the problem caused by #11587
has not been fixed (though diagnosed, thanks to David Loeffler), which
is a real pity since the aim of that ticket -- apart from extending
the database -- was to make accessing the database faster.
I myself have had no time to do anything Sage-related since term
started two weeks ago, so that's a regret but not a complaint!

John

[daveloeffler]

On Oct 16, 4:09 pm, John Cremona <john.crem...@gmail.com> wrote:
> Well done and thank you.  Unfortunately the problem caused by #11587
> has not been fixed (though diagnosed, thanks to David Loeffler), which
> is a real pity

Patch now up on trac. It's just 3 lines but brings the time for
"_=[E.gens() for E in cremona_curves([11..100])]" back down to 9.2 s
(exactly the same as in 4.7.1).

Regards, David

[Simon King]

Hi all,

a further improvement is provided by #11935. The patch is smaller than
#11900, but is in a way more invasive: It makes parent/element classes
of a category independent of the base ring of the category, unless
absolutely necessary. For example, one still has
Algebras(ZZ).parent_class!=Algebras(QQ).parent_class, but
Algebras(QQ).parent_class==Algebras(GF(5)).parent_class.

Since polynomial rings over very many finite fields F are created in
some elliptic curves computations and since the polynomial rings give
rise to the creation of Algebras(F).parent_class for each F (by
#9138), it is very efficient to unify these parent classes (it is 15%
of running time in some of the critical examples).

Taking two of Jeroen's examples from sage-devel:
"time ./sage ellbsd.sage"
5.5 seconds with sage-4.6.2
4.7 seconds with sage-4.7.2.alpha3+#11900+#11935.
"time ./sage elltest1.sage"
17.5 seconds with sage-4.6.2
16.9 seconds with sage-4.7.2.alpha3+#11900+#11935.

Cheers,
Simon

[Simon King]

Hi all!

Recall that #9138 makes all rings use the category framework. This is,
for example, necessary in order to get ideals in non-commutative rings
into Sage (#11068) and wrap Singular's non-commutative parts (#4539).
So, at least for my own work, it is absolutely essential to have
#9138.

But sadly, it would create a massive regression in some elliptic curve
computations.

At #11900, I got rid of that regression, and in some cases I even
obtain a speed-up compared with pre-#9138. There also is a follow-up
ticket #11943, that cleans up part of the code and would be nice to
have as well. But the speed comes from #11900, and this is what will
hopefully save #9138.

#11900 needs review. Since it is motivated by elliptic curves, I
thought I look here for a potential reviewer. William apparently made
a move towards reviewing it, but there was some misunderstanding that
made him think that the patches won't apply.

The patches should apply (with dependencies, of course) to sage-4.7.2.
But if you work with Jeroen's experimental sage-4.7.3.alpha1, then
please do *not* apply the patches: The experimental alpha1 already
contains both #9138 and #11900.

Best regards,
Simon

[Simon King]

Again hi!

Meanwhile #11935 needs review as well. It is a shorter patch than
#11900, but a bit more involved category-wise.

Why do I mention another category-ticket here? Because it makes some
elliptic curve computations 20% faster. The example is
sage: %time L = EllipticCurve('960d1').prove_BSD()

The following timings are of course on the same machine; the numbers
are copied from the tickets:

sage-4.7.2.alpha2:
CPU times: user 3.73 s, sys: 0.04 s, total: 3.78 s
Wall time: 4.01 s

sage-4.7.2.alpha2 + #9138 (not good indeed):
CPU times: user 10.10 s, sys: 0.07 s, total: 10.17 s
Wall time: 10.55 s

Jeroen's experimental sage-4.7.3.alpha1 (which contains #9138 and
#11900):
CPU times: user 4.32 s, sys: 0.10 s, total: 4.42 s
Wall time: 4.57 s

sage-4.7.3.alpha1 + #11943 + #11935:
CPU times: user 2.95 s, sys: 0.08 s, total: 3.03 s
Wall time: 3.20 s

Comparing the cpu-times of sage-4.7.2.alpha2 with
sage-4.7.3.alpha1+#11943+#11935:
sage: (3.73-2.95)/3.73
0.209115281501340

That's the 20% I promised.

Cheers,
Simon