#11900: Serious regression caused by #9138
-------------------------------------------------------------+--------------
Reporter: SimonKing | Owner:
tbd
Type: defect | Status:
needs_review
Priority: critical | Milestone:
sage-4.8
Component: performance | Keywords:
categories regression
Work_issues: Update reviewer patch | Upstream:
N/A
Reviewer: Jeroen Demeyer, Nicolas M. Thiéry, Simon King | Author:
Simon King, Nicolas M. Thiéry
Merged: | Dependencies:
#9138 #11911 #9562
-------------------------------------------------------------+--------------
Changes (by SimonKing):
* status: needs_work => needs_review
* reviewer: Jeroen Demeyer, Nicolas M. Thiéry => Jeroen Demeyer, Nicolas
M. Thiéry, Simon King
Old description:
> At [http://groups.google.com/group/sage-
> devel/browse_thread/thread/d885434ba9c22d66 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]
New description:
At [http://groups.google.com/group/sage-
devel/browse_thread/thread/d885434ba9c22d66 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]
or [attachment:trac11900_category_speedup_combined_Finitesingleton.patch]
at your choice.
--
Comment:
I have attached two patches. Both of them combine the ideas of Nicolas and
myself. The `base()` method is left in; this shall be taken care of at
#11943 (I'll mark it as "todo" there, if it hasn't already been done).
With each patch (plus #9138), all doctests pass when starting with
sage-4.8.alpha3. I was of course reading Nicolas' patches before including
them, and I give his contribution a positive review.
For the record, I repeated all benchmarks that were discussed here. The
main data are obtained with ''not'' using Category_singleton for Finite*.
The timings with using Category_singleton and the timings with sage 4.6.2
are also given, namely in the comments.
{{{
sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 5.61 s, sys: 0.19 s, total: 5.80 s
Wall time: 5.95 s # 5.61 s
# 4.6.2: 6.35 s
}}}
{{{
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 4.23 s, sys: 0.09 s, total: 4.32 s
Wall time: 4.66 s # 4.84 s
# 4.6.2: 4.69 s
}}}
{{{
sage: def test(E):
....: for p in prime_range(10000):
....: if p != 389:
....: G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 17.42 s, sys: 0.12 s, total: 17.54 s
Wall time: 17.60 s # 17.59 s
# 4.6.2: 15.97 s
}}}
{{{
sage: %time for E in cremona_curves([11..100]): S =
E.integral_points(both_signs=False)
CPU times: user 12.46 s, sys: 0.08 s, total: 12.55 s
Wall time: 12.66 s # 12.86 s
# 4.6.2: 14.05 s
}}}
{{{
sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 5.10 s, sys: 0.22 s, total: 5.32 s
Wall time: 5.33 s # 5.74 s
# 4.6.2: 6.20 s
}}}
{{{
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4,
z]).echelon_form()
CPU times: user 3.87 s, sys: 0.06 s, total: 3.92 s
Wall time: 3.94 s # 3.37 s
# 4.6.2: 3.46 s
}}}
{{{
sage: R = Rings()
sage: MS = MatrixSpace(QQ,3)
sage: %timeit MS in R
625 loops, best of 3: 765 ns per loop # 774 ns
# 4.6.2: 10.1 µs
sage: %timeit MS.is_ring()
625 loops, best of 3: 4.18 µs per loop # 3.88 µs
# 4.6.2: BOOM
}}}
{{{
sage: def test():
....: for i in xrange(5000):
....: MS = MatrixSpace(QQ,i)
....:
sage: %time test()
CPU times: user 0.25 s, sys: 0.00 s, total: 0.25 s
Wall time: 0.25 s # 0.30 s
# 4.6.2: 0.37 s
}}}
{{{
sage: def test():
....: for p in prime_range(10000):
....: P = GF(p)
....:
sage: %time test()
CPU times: user 0.60 s, sys: 0.00 s, total: 0.60 s
Wall time: 0.60 s # 0.66 s
# 4.6.2: 0.57 s
}}}
{{{
sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(10000)]
sage: A = Algebras(GF(5))
sage: %time _ = [B.is_subcategory(A) for B in L]
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.07 s # 0.06 s
# 4.6.2: 0.97 s
}}}
{{{
sage: v = vector(ZZ,range(100))
sage: %timeit L = v.list()
625 loops, best of 3: 11.7 µs per loop # 12.1 µs
# 4.6.2: 16.4 µs
sage: v = vector(QQ,range(100))
sage: %timeit L = v.list()
625 loops, best of 3: 23.5 µs per loop # 23.8 µs
# 4.6.2: 24.5 µs
}}}
The following is still not good, but I think #11935 will solve that
problem:
{{{
sage: def test():
....: for p in prime_range(10000):
....: P = GF(p)['t','x','z']
....:
sage: %time test()
CPU times: user 2.84 s, sys: 0.05 s, total: 2.89 s
Wall time: 2.90 s # 2.97 s
# 4.6.2: 1.22 s
}}}
'''__Left to do__'''
The final reviewer (i.e., Nicolas, I presume) should decide whether we
want to have
[attachment:trac11900_category_speedup_combined_Finitesingleton.patch] or
[attachment:trac11900_category_speedup_combined.patch].
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11900#comment:186>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
