At sage-devel, Jeroen reported a massive regression in elliptic curve computations. The regression was introduced in the transition from sage-4.7.2.alpha2 to sage-4.7.2.alpha3.

It seems that #9138 is responsible, at least for a big part of the regression. With unpatched sage-4.7.2.alpha2, we find

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 5.54 s, sys: 0.15 s, total: 5.69 s
Wall time: 5.81 s

Adding #9138 and its dependency, we obtain

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 8.72 s, sys: 0.18 s, total: 8.89 s
Wall time: 8.92 s

It turns out that much time is wasted for calls to sage.categories.Category.join and to sage.categories.Category.hom_category.

When caching these two methods, one can reduce the speed difference to something like that (sage-4.7.2.alpha3 plus #11115 plus an experimental patch for the caching):

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 6.82 s, sys: 0.16 s, total: 6.98 s
Wall time: 7.40 s

However, that's still far from good. After caching join and hom_category, there is still too much time spent (according to %prun) for the initialisation of matrix spaces.

Apply

• attachment: trac11900_category_speedup_combined.patch
• attachment: trac11900_only_fix_singleton_hash.patch
• attachment: trac11900_doctest.patch

Depends on #11319
Depends on #9138
Depends on #11911
Depends on #9562

CC: @jdemeyer @nthiery @malb

Component: performance

Keywords: categories regression

Author: Simon King

Reviewer: Jeroen Demeyer, Nicolas M. Thiéry, Simon King, Jason Grout

Merged: sage-5.0.beta0

Issue created by migration from https://trac.sagemath.org/ticket/11900