#11900: Serious regression caused by #9138
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: tbd
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.7.3
Component: performance | Keywords: categories regression
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #9138 #11911
---------------------------+------------------------------------------------
Comment(by SimonKing):
Here are some timings. I compare
(1) sage-4.7.2.alpha2,
(2) sage-4.7.2.alpha3-prerelease and
(3) sage-4.7.2.alpha3 with the patches from here.
I am restarting before each new test, so that caches created in one test
won't influence the other tests.
__Creation of matrix spaces__
(1)
{{{
sage: def test():
....: for i in xrange(5000):
....: MS = MatrixSpace(QQ,i)
....:
sage: %time test()
CPU times: user 0.38 s, sys: 0.00 s, total: 0.38 s
Wall time: 0.38 s
}}}
(2) The coercion from the base ring is initialised during matrix space
initialisation. That involves a lot of category computations and is slow:
{{{
sage: def test():
....: for i in xrange(5000):
....: MS = MatrixSpace(QQ,i)
....:
sage: %time test()
CPU times: user 1.85 s, sys: 0.03 s, total: 1.88 s
Wall time: 1.88 s
}}}
(3) Since matrix spaces are often considered mere containers, not rings or
modules, the first patch does no initialisation of the category during
initialisation of the matrix space. There is a method that can do the full
category initialisation ''after'' matrix space initialisation.
{{{
sage: def test():
....: for i in xrange(5000):
....: MS = MatrixSpace(QQ,i)
....:
sage: %time test()
CPU times: user 0.26 s, sys: 0.00 s, total: 0.27 s
Wall time: 0.27 s
}}}
__Creation of finite fields__
(1)
{{{
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.61 s
}}}
(2) It is slower by a factor of more than 10. %prun reveals that most time
is spent in `Category.join`.
{{{
sage: def test():
....: for p in prime_range(10000):
....: P = GF(p)
....:
sage: %time test()
CPU times: user 6.59 s, sys: 0.00 s, total: 6.60 s
Wall time: 6.62 s
}}}
(3) The drastic slow-down observed in (2) has not totally vanished, but I
hope this is good enough for now:
{{{
sage: def test():
....: for p in prime_range(10000):
....: P = GF(p)
....:
sage: %time test()
CPU times: user 0.82 s, sys: 0.01 s, total: 0.83 s
Wall time: 0.83 s
}}}
__Creation of polynomial rings__
(1)
{{{
sage: def test():
....: for p in prime_range(10000):
....: P = GF(p)['x']
....: P = GF(p)['x','y']
....:
sage: %time test()
CPU times: user 2.41 s, sys: 0.05 s, total: 2.46 s
Wall time: 2.53 s
}}}
(2) Since I am creating polynomial rings over finite fields, part of the
overhead comes from what we have seen in the previous example. However,
there must be an additional slowness, since the creation of finite fields
apparently only contributes 6 seconds.
{{{
sage: def test():
....: for p in prime_range(10000):
....: P = GF(p)['x']
....: P = GF(p)['x','y']
....:
sage: %time test()
CPU times: user 13.15 s, sys: 0.05 s, total: 13.20 s
Wall time: 13.27 s
}}}
(3) Here, it seems that additional improvements are needed: It is still
much slower than without #9138.
{{{
sage: def test():
....: for p in prime_range(10000):
....: P = GF(p)['x']
....: P = GF(p)['x','y']
....:
sage: %time test()
CPU times: user 6.54 s, sys: 0.08 s, total: 6.62 s
Wall time: 6.68 s
}}}
__is_subcategory using base__
(1) and (2)
{{{
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.95 s, sys: 0.00 s, total: 0.96 s
Wall time: 0.96 s
}}}
(3) I think an early abort strategy taking into account the base rings of
categories makes sense.
{{{
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.04 s, sys: 0.02 s, total: 0.06 s
Wall time: 0.06 s
}}}
'''__The Elliptic Curve Tests__'''
Recall that only two of them remained critical: `L =
EllipticCurve('960d1').prove_BSD()` and the
`change_ring(...).abelian_group()` test.
__prove_BSD()__
(1)
{{{
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.74 s, sys: 0.11 s, total: 3.85 s
Wall time: 5.05 s
}}}
(2) Given the timings above, this should be almost entirely due to finite
field and polynomial ring creation.
{{{
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 9.37 s, sys: 0.16 s, total: 9.53 s
Wall time: 10.89 s
}}}
(3) I am not totally happy, yet:
{{{
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 5.63 s, sys: 0.10 s, total: 5.72 s
Wall time: 5.87 s
}}}
__abelian_group()__
(1)
{{{
sage: def test():
....: E = EllipticCurve('389a')
....: for p in prime_range(10000):
....: if p != 389:
....: G = E.change_ring(GF(p)).abelian_group()
....:
sage: %time test()
CPU times: user 16.57 s, sys: 0.08 s, total: 16.65 s
Wall time: 16.77 s
}}}
(2)
{{{
sage: def test():
....: E = EllipticCurve('389a')
....: for p in prime_range(10000):
....: if p != 389:
....: G = E.change_ring(GF(p)).abelian_group()
....:
sage: %time test()
CPU times: user 26.87 s, sys: 0.10 s, total: 26.97 s
Wall time: 27.16 s
}}}
(3)
{{{
sage: def test():
....: E = EllipticCurve('389a')
....: for p in prime_range(10000):
....: if p != 389:
....: G = E.change_ring(GF(p)).abelian_group()
....:
sage: %time test()
CPU times: user 19.29 s, sys: 0.08 s, total: 19.37 s
Wall time: 19.54 s
}}}
I am not totally happy with the performance, yet. But I think it makes
sense that someone has a look at the current snap shot of patches.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11900#comment:64>
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.
