#13400: Investigate ways to gain speed in basic constructions
-------------------------------+--------------------------------------------
Reporter: nbruin | Owner: robertwb
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: coercion | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
-------------------------------+--------------------------------------------
Comment (by nbruin):
This example seems fairly typical:
{{{
def test1(N,B,t):
for i in range(t):
m=matrix(QQ,N,N,srange(N*N)).echelon_form()
%prun test1(20,40,10^3)
}}}
In 5.3b2:
{{{
677732 function calls (645652 primitive calls) in 3.976 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1000 2.021 0.002 3.537 0.004 {method 'echelon_form' of
'sage.matrix.matrix_rational_dense.Matrix_rational_dense' objects}
5978 0.236 0.000 0.237 0.000
dynamic_class.py:259(dynamic_class_internal)
5000 0.178 0.000 0.834 0.000 matrix_space.py:1180(matrix)
16384 0.091 0.000 0.099 0.000 {method 'is_prime' of
'sage.rings.integer.Integer' objects}
1991 0.090 0.000 0.103 0.000 {method 'ideal' of
'sage.rings.ring.Ring' objects}
16937/4983 0.082 0.000 0.547 0.000
lazy_attribute.py:506(__get__)
1000 0.076 0.000 0.076 0.000 {method 'range' of
'sage.rings.integer_ring.IntegerRing_class' objects}
1991 0.062 0.000 0.124 0.000
quotient_ring.py:322(__init__)
14394 0.062 0.000 0.192 0.000 arith.py:401(is_prime)
1 0.060 0.060 3.978 3.978 <ipython console>:1(test1)
10000 0.052 0.000 0.235 0.000
matrix_space.py:154(__classcall__)
110854 0.049 0.000 0.049 0.000 {isinstance}
1992 0.049 0.000 0.122 0.000 {sage.rings.ring.is_Field}
2000 0.041 0.000 0.168 0.000
matrix_space.py:230(__init__)
1991 0.039 0.000 0.298 0.000
integer_mod_ring.py:191(__init__)
5977/996 0.038 0.000 0.477 0.000
category.py:1011(parent_class)
2000 0.031 0.000 0.049 0.000 sequence.py:86(Sequence)
2000 0.031 0.000 0.203 0.000
arith.py:1051(previous_prime)
2989 0.031 0.000 0.056 0.000
sageinspect.py:917(sage_getargspec)
5975 0.031 0.000 0.040 0.000
category_types.py:261(__init__)
12000 0.028 0.000 0.056 0.000 misc.py:179(cputime)
2 0.027 0.014 0.031 0.015 __init__.py:2(<module>)
999 0.027 0.000 0.117 0.000
matrix_space.py:1133(zero_matrix)
14394 0.025 0.000 0.030 0.000 all.py:1(arithmetic)
2000 0.020 0.000 0.036 0.000
matrix_space.py:904(_get_matrix_class)
12000 0.020 0.000 0.020 0.000 {resource.getrusage}
8972/6981 0.018 0.000 0.212 0.000
{sage.misc.classcall_metaclass.typecall}
1000 0.017 0.000 0.238 0.000 constructor.py:34(matrix)
1000 0.017 0.000 0.143 0.000 misc.py:1051(srange)
8972/6981 0.017 0.000 0.226 0.000
unique_representation.py:449(__classcall__)
3000 0.016 0.000 0.019 0.000 {method '__copy__' of
'sage.matrix.matrix_integer_dense.Matrix_integer_dense' objects}
997 0.016 0.000 0.049 0.000 homset.py:296(__init__)
1991 0.015 0.000 0.048 0.000
magmas.py:101(__init_extra__)
996 0.015 0.000 0.085 0.000
integer_mod_ring.py:960(_coerce_map_from_)
997 0.015 0.000 0.065 0.000 homset.py:40(Hom)
5972 0.014 0.000 0.019 0.000 category.py:1286(join)
...
}}}
In 5.3b2+tickets
{{{
2262393 function calls (1685916 primitive calls) in 5.520 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1000 2.137 0.002 5.110 0.005 {method 'echelon_form' of
'sage.matrix.matrix_rational_dense.Matrix_rational_dense' objects}
5000 0.263 0.000 0.627 0.000
matrix_space.py:230(__init__)
2224 0.262 0.000 0.351 0.000
quotient_ring.py:322(__init__)
6159 0.194 0.000 0.195 0.000
dynamic_class.py:259(dynamic_class_internal)
5000 0.189 0.000 1.045 0.000 matrix_space.py:1180(matrix)
146080/29216 0.185 0.000 0.497 0.000
covariant_functorial_construction.py:359(is_subcategory)
379808/87648 0.131 0.000 0.462 0.000
covariant_functorial_construction.py:365(<genexpr>)
2224 0.120 0.000 0.139 0.000 {method 'ideal' of
'sage.rings.ring.Ring' objects}
16316 0.093 0.000 0.101 0.000 {method 'is_prime' of
'sage.rings.integer.Integer' objects}
6432 0.091 0.000 0.759 0.000 category.py:112(_join)
1000 0.087 0.000 0.087 0.000 {method 'range' of
'sage.rings.integer_ring.IntegerRing_class' objects}
18217/6220 0.079 0.000 0.699 0.000
lazy_attribute.py:506(__get__)
156240 0.075 0.000 0.170 0.000
category.py:1102(is_subcategory)
1 0.071 0.071 5.522 5.522 <ipython console>:1(test1)
167120/33664 0.066 0.000 0.544 0.000 {any}
14332 0.065 0.000 0.196 0.000 arith.py:401(is_prime)
154016 0.062 0.000 0.095 0.000
category.py:622(_subcategory_hook_)
44296 0.059 0.000 0.074 0.000 weakref.py:55(__getitem__)
129031 0.058 0.000 0.058 0.000 {isinstance}
10000 0.055 0.000 0.751 0.000
matrix_space.py:154(__classcall__)
2983 0.052 0.000 0.467 0.000 {sage.rings.ring.is_Field}
2224 0.047 0.000 0.983 0.000
integer_mod_ring.py:191(__init__)
2000 0.046 0.000 0.222 0.000
arith.py:1051(previous_prime)
1999 0.043 0.000 0.157 0.000
matrix_space.py:1133(zero_matrix)
5000 0.037 0.000 0.064 0.000
matrix_space.py:904(_get_matrix_class)
7000 0.037 0.000 0.048 0.000
category_types.py:261(__init__)
6000/1000 0.037 0.000 0.613 0.001
category.py:1023(parent_class)
19591 0.036 0.000 0.080 0.000 weakref.py:79(__setitem__)
3983 0.035 0.000 0.068 0.000
sageinspect.py:917(sage_getargspec)
154016 0.033 0.000 0.033 0.000 {issubclass}
2000 0.032 0.000 0.052 0.000 sequence.py:86(Sequence)
...
}}}
You can see where a lot of that time is going: In category construction
stuff.
The reason is simple: It's trying some multimodular approach. So there are
all
kinds of matrix spaces over various finite fields involved. Previously,
these
structures remained in memory, cached and ready for reuse. Ideal here, but
given
the peculiar choices of primes, rarely all that useful in practice.
With the stricter collection, these spaces need to be created time and
again.
However, the number of times that covariant_functorial_construction gets
called
is ''insane''. That almost looks like something needs to be constructed
for
''every element''.
On the plus side, if we run instead
{{{
def test1(N,B,t):
for i in range(t):
m=matrix(QQ,N,N,srange(N*N)).echelon_form(algorithm="classical")
%prun test1(20,40,10^3)
}}}
we get with 5.3b2
{{{
95507 function calls (95450 primitive calls) in 0.744 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1000 0.323 0.000 0.333 0.000 {method 'echelon_form' of
'sage.matrix.matrix_rational_dense.Matrix_rational_dense' objects}
1000 0.192 0.000 0.195 0.000 matrix_space.py:1180(matrix)
1 0.046 0.046 0.745 0.745 <ipython console>:1(test1)
2000 0.029 0.000 0.045 0.000 sequence.py:86(Sequence)
1000 0.029 0.000 0.029 0.000 {method 'range' of
'sage.rings.integer_ring.IntegerRing_class' objects}
2 0.027 0.014 0.031 0.016 __init__.py:2(<module>)
1000 0.015 0.000 0.276 0.000 constructor.py:34(matrix)
1000 0.015 0.000 0.090 0.000 misc.py:1051(srange)
26770 0.011 0.000 0.011 0.000 {isinstance}
2000 0.006 0.000 0.006 0.000 sequence.py:463(__init__)
1000 0.005 0.000 0.005 0.000
matrix_space.py:154(__classcall__)
2000 0.005 0.000 0.009 0.000 misc.py:179(cputime)
243 0.004 0.000 0.005 0.000
function_base.py:3122(add_newdoc)
2000 0.003 0.000 0.003 0.000 {resource.getrusage}
1 0.002 0.002 0.003 0.003 polynomial.py:48(<module>)
2000 0.002 0.000 0.002 0.000
{sage.structure.element.canonical_coercion}
1 0.002 0.002 0.033 0.033 type_check.py:3(<module>)
1 0.002 0.002 0.002 0.002 chebyshev.py:77(<module>)
2000 0.001 0.000 0.010 0.000 misc.py:410(verbose)
18531/18518 0.001 0.000 0.001 0.000 {len}
...
}}}
and 5.3b2+tickets
{{{
96514 function calls (96457 primitive calls) in 0.682 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1000 0.316 0.000 0.326 0.000 {method 'echelon_form' of
'sage.matrix.matrix_rational_dense.Matrix_rational_dense' objects}
1000 0.136 0.000 0.139 0.000 matrix_space.py:1180(matrix)
1 0.050 0.050 0.683 0.683 <ipython console>:1(test1)
1000 0.043 0.000 0.043 0.000 {method 'range' of
'sage.rings.integer_ring.IntegerRing_class' objects}
2000 0.029 0.000 0.047 0.000 sequence.py:86(Sequence)
1000 0.017 0.000 0.108 0.000 misc.py:1051(srange)
1000 0.016 0.000 0.198 0.000 constructor.py:34(matrix)
26770 0.010 0.000 0.010 0.000 {isinstance}
2000 0.007 0.000 0.008 0.000 sequence.py:463(__init__)
2 0.006 0.003 0.011 0.006 __init__.py:2(<module>)
2000 0.004 0.000 0.008 0.000 misc.py:179(cputime)
1000 0.004 0.000 0.006 0.000
matrix_space.py:154(__classcall__)
2000 0.004 0.000 0.004 0.000
{sage.structure.element.canonical_coercion}
243 0.004 0.000 0.004 0.000
function_base.py:3122(add_newdoc)
2000 0.003 0.000 0.003 0.000 {resource.getrusage}
1 0.002 0.002 0.003 0.003 polynomial.py:48(<module>)
1 0.002 0.002 0.002 0.002 chebyshev.py:77(<module>)
18531/18518 0.002 0.000 0.002 0.000 {len}
1001 0.001 0.000 0.002 0.000 weakref.py:55(__getitem__)
...
}}}
so it's actually faster! (I've tried, these numbers seem representative).
I have no explanation for what is faster here. Perhaps just some
dictionary
lookups that happen faster now thanks to 'MonoDict' and 'TripleDict'.
So apart from `echelon_form` being really badly tuned for its choice of
algorithm, what do we do about this parent construction? Should sage keep
a
cache of useful finite fields and be a little more restrained in its
choice of
primes (promoting reuse of these finite fields)?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13400#comment:1>
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.
