#13991: Mitigate speed regressions in symmetric function related code due to
#12313
----------------------------------+-----------------------------------------
Reporter: nbruin | Owner: sage-combinat
Type: task | Status: new
Priority: major | Milestone: sage-5.8
Component: combinatorics | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #13605, #14225 | Stopgaps:
----------------------------------+-----------------------------------------
Comment (by tscrim):
Hey Simon,
I have a patch which does the caching. Here's the message I was going to
post (right) before the server crash:
With some further digging, there is exactly one meaningful call to
`Core.to_grassmannian()` which is a `k`-core method which converts back to
a `k`-bounded partition and then calls
`Partition.from_kbounded_to_grassmannian()` which calls
`Partition.from_kbounded_to_reduced_word()`. I've made a change which
caches the Weyl group to the basis object and then made it directly call
`from_kbounded_to_reduce_word()` (which also avoids going to a `k`-core
and back). This doesn't significantly decreases the test suite time for
me.
Here are my top function calls.
Before changes:
{{{
2399942 function calls (2360396 primitive calls) in 31.765
seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
350412 1.685 0.000 1.685 0.000 {isinstance}
7830 1.391 0.000 4.542 0.001 weyl_group.py:937(action)
42983 1.269 0.000 2.375 0.000
free_module.py:2142(_from_dict)
24207 1.185 0.000 2.246 0.000 partition.py:651(__init__)
12128/85 1.094 0.000 31.100 0.366
{sage.combinat.dict_addition.dict_linear_combination}
155841 1.052 0.000 1.052 0.000 combinat.py:866(__hash__)
22548/19595 0.678 0.000 3.589 0.000
partition.py:4043(_element_constructor_)
127648/127051 0.581 0.000 0.658 0.000 {len}
7880 0.517 0.000 0.982 0.000 free_module.py:660(_vector_)
15325 0.493 0.000 2.820 0.000
partition.py:597(__classcall_private__)
2949 0.491 0.000 1.211 0.000
polynomial_ring.py:298(_element_constructor_)
50979 0.474 0.000 0.613 0.000 weakref.py:55(__getitem__)
42983 0.445 0.000 0.445 0.000 free_module.py:34(__init__)
24635 0.435 0.000 1.075 0.000
integer_list.py:1013(__cmp__)
49602 0.420 0.000 0.532 0.000 {repr}
1848 0.415 0.000 2.560 0.001
{sage.libs.symmetrica.symmetrica.t_SCHUR_HOMSYM_symmetrica}
22657 0.379 0.000 1.191 0.000
partition.py:3929(__classcall_private__)
7766 0.362 0.000 0.715 0.000 free_module.py:562(support)
}}}
After:
{{{
2296313 function calls (2256847 primitive calls) in 30.238
seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
330017 1.550 0.000 1.550 0.000 {isinstance}
7848 1.381 0.000 4.508 0.001 weyl_group.py:937(action)
43052 1.276 0.000 2.410 0.000
free_module.py:2142(_from_dict)
12175/85 1.103 0.000 29.582 0.348
{sage.combinat.dict_addition.dict_linear_combination}
21796 1.081 0.000 2.074 0.000 partition.py:651(__init__)
155841 1.023 0.000 1.023 0.000 combinat.py:866(__hash__)
20133/17182 0.613 0.000 3.299 0.000
partition.py:4043(_element_constructor_)
111781/110905 0.501 0.000 0.580 0.000 {len}
7873 0.500 0.000 0.754 0.000 free_module.py:660(_vector_)
2949 0.498 0.000 1.202 0.000
polynomial_ring.py:298(_element_constructor_)
43052 0.466 0.000 0.466 0.000 free_module.py:34(__init__)
47386 0.448 0.000 0.585 0.000 weakref.py:55(__getitem__)
24635 0.425 0.000 1.065 0.000
integer_list.py:1013(__cmp__)
49654 0.420 0.000 0.531 0.000 {repr}
1848 0.403 0.000 2.521 0.001
{sage.libs.symmetrica.symmetrica.t_SCHUR_HOMSYM_symmetrica}
11256 0.382 0.000 2.309 0.000
partition.py:597(__classcall_private__)
7766 0.356 0.000 0.709 0.000 free_module.py:562(support)
1324 0.353 0.000 6.382 0.005
modules_with_basis.py:1690(preimage)
}}}
Doing some digging through all the data, the longest tests seems to be:
{{{
1 0.000 0.000 16.398 16.398 monoids.py:150(_test_prod)
1 0.000 0.000 10.306 10.306
semigroups.py:90(_test_associativity)
}}}
Which basically comes from doing `x = F.an_element()` and `x*x*x`. Here
are my timings:
Before:
{{{
589843 function calls (579632 primitive calls) in 8.102 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
86470 0.439 0.000 0.439 0.000 {isinstance}
1888 0.338 0.000 1.115 0.001 weyl_group.py:937(action)
7839 0.235 0.000 0.451 0.000
free_module.py:2142(_from_dict)
4510 0.220 0.000 0.426 0.000 partition.py:651(__init__)
2146/9 0.187 0.000 7.944 0.883
{sage.combinat.dict_addition.dict_linear_combination}
25751 0.171 0.000 0.171 0.000 combinat.py:866(__hash__)
31144/30547 0.141 0.000 0.185 0.000 {len}
4271/3838 0.128 0.000 0.680 0.000
partition.py:4043(_element_constructor_)
1938 0.126 0.000 0.421 0.000 free_module.py:660(_vector_)
13883 0.125 0.000 0.166 0.000 weakref.py:55(__getitem__)
3101 0.105 0.000 0.624 0.000
partition.py:597(__classcall_private__)
1246/671 0.103 0.000 0.343 0.001 {method
'has_coerce_map_from' of 'sage.structure.parent.Parent' objects}
12195 0.101 0.000 0.150 0.000
unique_representation.py:531(__hash__)
3 0.086 0.029 0.086 0.029 {posix.waitpid}
9170 0.085 0.000 0.120 0.000 {repr}
7839 0.084 0.000 0.084 0.000 free_module.py:34(__init__)
5173 0.083 0.000 0.241 0.000
partition.py:3929(__classcall_private__)
1888 0.082 0.000 1.604 0.001
weyl_group.py:970(has_descent)
}}}
With changes:
{{{
555235 function calls (545766 primitive calls) in 7.224 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
82808 0.390 0.000 0.390 0.000 {isinstance}
1870 0.329 0.000 1.078 0.001 weyl_group.py:937(action)
7616 0.235 0.000 0.435 0.000
free_module.py:2142(_from_dict)
4254 0.212 0.000 0.401 0.000 partition.py:651(__init__)
1997/9 0.186 0.000 7.050 0.783
{sage.combinat.dict_addition.dict_linear_combination}
25751 0.167 0.000 0.167 0.000 combinat.py:866(__hash__)
28064/27772 0.123 0.000 0.147 0.000 {len}
13289 0.122 0.000 0.165 0.000 weakref.py:55(__getitem__)
1895 0.122 0.000 0.185 0.000 free_module.py:660(_vector_)
4015/3580 0.112 0.000 0.625 0.000
partition.py:4043(_element_constructor_)
12002 0.112 0.000 0.158 0.000
unique_representation.py:531(__hash__)
2658 0.100 0.000 0.564 0.000
partition.py:597(__classcall_private__)
1240/665 0.099 0.000 0.341 0.001 {method
'has_coerce_map_from' of 'sage.structure.parent.Parent' objects}
8986 0.086 0.000 0.116 0.000 {repr}
1870 0.081 0.000 1.566 0.001
weyl_group.py:970(has_descent)
7616 0.080 0.000 0.080 0.000 free_module.py:34(__init__)
1870 0.078 0.000 0.111 0.000
free_module.py:634(coefficients)
1935 0.077 0.000 0.136 0.000
infinity.py:889(_element_constructor_)
}}}
I can post my patch in the new ticket you create (I gather that it the
appropriate thing to do for tasks). Sorry for the message bomb.
Best,[[BR]]
Travis
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13991#comment:53>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
