#17120: Extreme speed regression in ramification_breaks() doctest
---------------------------------+------------------------
Reporter: jdemeyer | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+------------------------
Description changed by jdemeyer:
Old description:
> In sage-5.12, the following takes a bit over a second:
> {{{
> sage: K.<b> = NumberField(x^8 - 20*x^6 + 104*x^4 - 40*x^2 + 1156)
> sage: %time K.galois_group().ramification_breaks(K.primes_above(2)[0])
> CPU times: user 0.57 s, sys: 0.18 s, total: 0.75 s
> Wall time: 1.32 s
> {1, 3, 5}
> }}}
>
> In sage-6.3, it takes about 50s:
> {{{
> sage: K.<b> = NumberField(x^8 - 20*x^6 + 104*x^4 - 40*x^2 + 1156)
> sage: %time K.galois_group().ramification_breaks(K.primes_above(2)[0])
> CPU times: user 50.1 s, sys: 440 ms, total: 50.5 s
> Wall time: 51 s
> {1, 3, 5}
> }}}
New description:
In sage-5.12, the following takes a bit over a second:
{{{
sage: K.<b> = NumberField(x^8 - 20*x^6 + 104*x^4 - 40*x^2 + 1156)
sage: %time K.galois_group().ramification_breaks(K.primes_above(2)[0])
CPU times: user 0.57 s, sys: 0.18 s, total: 0.75 s
Wall time: 1.32 s
{1, 3, 5}
}}}
In sage-6.3, it takes about 50s:
{{{
sage: K.<b> = NumberField(x^8 - 20*x^6 + 104*x^4 - 40*x^2 + 1156)
sage: %time K.galois_group().ramification_breaks(K.primes_above(2)[0])
CPU times: user 50.1 s, sys: 440 ms, total: 50.5 s
Wall time: 51 s
{1, 3, 5}
}}}
`%prun` shows:
{{{
124043 function calls (123309 primitive calls) in 52.496 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
5/4 50.869 10.174 50.929 12.732 {method 'echelon_form' of
'sage.matrix.matrix_integer_dense.Matrix_integer_dense' objects}
104 0.439 0.004 0.439 0.004 {select.select}
1166 0.067 0.000 0.277 0.000
number_field.py:1350(_element_constructor_)
3 0.050 0.017 0.238 0.079 __init__.py:1(<module>)
1 0.046 0.046 0.046 0.046 {posix.fork}
23333 0.045 0.000 0.045 0.000 {isinstance}
1 0.036 0.036 0.036 0.036 {posix.forkpty}
663 0.031 0.000 0.057 0.000
number_field.py:2548(__cmp__)
794 0.022 0.000 0.053 0.000
polynomial_ring_constructor.py:56(PolynomialRing)
334 0.022 0.000 0.485 0.001 pexpect.py:918(expect_list)
1288 0.020 0.000 0.033 0.000 free_module.py:900(__call__)
518 0.018 0.000 0.039 0.000
number_field.py:6348(_coerce_non_number_field_element_in)
829 0.018 0.000 0.020 0.000
polynomial_ring.py:318(_element_constructor_)
133 0.018 0.000 0.038 0.000 matrix_space.py:1185(matrix)
1 0.017 0.017 0.251 0.251 __init__.py:106(<module>)
794 0.017 0.000 0.082 0.000 rings.py:707(__getitem__)
6/3 0.016 0.003 0.023 0.008 monomials.py:2(_monomials)
32 0.015 0.000 0.094 0.003
galois_group.py:652(__call__)
105 0.015 0.000 0.015 0.000
dynamic_class.py:324(dynamic_class_internal)
1 0.015 0.015 0.023 0.023 numeric.py:1(<module>)
1 0.015 0.015 0.021 0.021 {method 'galois_group' of
'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'
objects}
6933 0.014 0.000 0.014 0.000 {method 'search' of
'_sre.SRE_Pattern' objects}
1 0.014 0.014 0.014 0.014 linalg.py:10(<module>)
1 0.014 0.014 0.015 0.015 __init__.py:7(<module>)
4 0.012 0.003 51.021 12.755
free_module.py:5248(_echelonized_basis)
11 0.012 0.001 0.263 0.024
free_module.py:6693(element_class)
5 0.012 0.002 51.056 10.211
free_module.py:5116(__init__)
8 0.012 0.001 51.384 6.423
order.py:571(ring_generators)
6518/6379 0.011 0.000 0.026 0.000 {len}
273 0.010 0.000 0.015 0.000
function_base.py:2945(add_newdoc)
1288 0.010 0.000 0.045 0.000
free_module.py:5042(__call__)
627 0.009 0.000 0.043 0.000 maps.py:223(_call_)
744 0.008 0.000 0.008 0.000 {method 'extend' of 'list'
objects}
1 0.008 0.008 0.010 0.010 polynomial.py:55(<module>)
6 0.008 0.001 0.014 0.002
matrix_space.py:533(get_action_impl)
627 0.007 0.000 0.007 0.000 {method '_coefficients' of
'sage.rings.number_field.number_field_element.NumberFieldElement' objects}
794 0.007 0.000 0.016 0.000
polynomial_ring_constructor.py:502(_single_variate)
1325 0.007 0.000 0.011 0.000 copy.py:66(copy)
[...]
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17120#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 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.
For more options, visit https://groups.google.com/d/optout.
