#16040: libsingular mpolynomial from dict is slow
-----------------------+----------------------------
Reporter: vbraun | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.2
Component: algebra | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------+----------------------------
Creating multivariate polynomials from dictionaries is slow and grinds to
a halt around 100k terms. In particular, it seems to grow worse than
`O(N^2)`. Unpickling falls precisely into this trap.
With my C function profiler from #16038 we see that the problem is in
`p_Add_q`, which presumably also does some sorting:
{{{
sage: R = PolynomialRing(QQ, 16, 'a')
sage: # p = polynomial with 26492 terms
sage: p_dict = p.dict()
sage: %crun R(p_dict)
PROFILE: interrupts/evictions/bytes = 196/5/9880
Using local file /home/vbraun/Code/sage.git/local/bin/python.
Using local file /home/vbraun/.sage/temp/desktop/12236/tmp_wU2dXk.perf.
Removing pthread_getattr_np from all stack traces.
Total: 196 samples
174 88.8% 88.8% 174 88.8%
p_Add_q__FieldQ_LengthSix_OrdPosNomogPos
5 2.6% 91.3% 19 9.7%
__pyx_pf_4sage_5rings_10polynomial_8polydict_6ETuple_10__getitem__
(inline)
5 2.6% 93.9% 5 2.6% convert_3way_to_object (inline)
3 1.5% 95.4% 3 1.5% PyInt_FromLong
3 1.5% 96.9% 11 5.6% PyObject_RichCompare
2 1.0% 98.0% 2 1.0% _IO_vfwscanf
2 1.0% 99.0% 2 1.0% int_compare
1 0.5% 99.5% 1 0.5% adjust_tp_compare
1 0.5% 100.0% 1 0.5% omAllocBinPage
0 0.0% 100.0% 1 0.5% DefRingParlp
0 0.0% 100.0% 22 11.2% PyEval_EvalCode
0 0.0% 100.0% 22 11.2% PyEval_EvalCodeEx
0 0.0% 100.0% 22 11.2% PyEval_EvalFrameEx
0 0.0% 100.0% 22 11.2% PyObject_Call
0 0.0% 100.0% 22 11.2% PyRun_FileExFlags
0 0.0% 100.0% 22 11.2% PyRun_SimpleFileExFlags
0 0.0% 100.0% 22 11.2% PyRun_StringFlags
0 0.0% 100.0% 22 11.2% Py_Main
0 0.0% 100.0% 3 1.5% __Pyx_PyInt_From_int (inline)
0 0.0% 100.0% 22 11.2% __Pyx_PyObject_Call (inline)
0 0.0% 100.0% 1 0.5% __gmpz_init
0 0.0% 100.0% 1 0.5% __gmpz_init_set
0 0.0% 100.0% 22 11.2% __libc_start_main
0 0.0% 100.0% 22 11.2%
__pyx_f_4sage_9structure_11coerce_maps_24DefaultConvertMap_unique__call_
0 0.0% 100.0% 22 11.2%
__pyx_pf_4sage_5rings_10polynomial_28multi_polynomial_libsingular_27MPolynomialRing_libsingular_12_element_constructor_
(inline)
0 0.0% 100.0% 22 11.2%
__pyx_pf_4sage_9structure_6parent_6Parent_34__call__ (inline)
0 0.0% 100.0% 22 11.2%
__pyx_pw_4sage_5rings_10polynomial_28multi_polynomial_libsingular_27MPolynomialRing_libsingular_13_element_constructor_
0 0.0% 100.0% 19 9.7%
__pyx_pw_4sage_5rings_10polynomial_8polydict_6ETuple_11__getitem__
0 0.0% 100.0% 22 11.2%
__pyx_pw_4sage_9structure_6parent_6Parent_35__call__
0 0.0% 100.0% 1 0.5% _omAllocBin (inline)
0 0.0% 100.0% 22 11.2% _start
0 0.0% 100.0% 22 11.2% call_function (inline)
0 0.0% 100.0% 22 11.2% do_call (inline)
0 0.0% 100.0% 1 0.5% do_richcmp (inline)
0 0.0% 100.0% 22 11.2% exec_statement (inline)
0 0.0% 100.0% 22 11.2% ext_do_call (inline)
0 0.0% 100.0% 22 11.2% fast_function (inline)
0 0.0% 100.0% 22 11.2% function_call
0 0.0% 100.0% 3 1.5% nlInit2gmp
0 0.0% 100.0% 1 0.5% nlNormalize (inline)
0 0.0% 100.0% 1 0.5% omAllocBinFromFullPage
0 0.0% 100.0% 1 0.5% omAllocNewBinPage (inline)
0 0.0% 100.0% 22 11.2% run_mod (inline)
0 0.0% 100.0% 2 1.0% sage_gmp_malloc
0 0.0% 100.0% 2 1.0% sage_malloc
0 0.0% 100.0% 1 0.5% try_3way_to_rich_compare (inline)
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/16040>
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.
