libsingular mpolynomial from dict is slow

[vbraun]

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)

CC: @malb @burcin @sagetrac-jkeitel @simon-king-jena

Component: algebra

Issue created by migration from https://trac.sagemath.org/ticket/16040

[malb]

comment:3

It's doing things naively, i.e. it adds terms up instead of building the list manually. Doing the list building ourselves would require reading a bit of Singular code to make sure we're doing it right™.

[simon-king-jena]

comment:5

Well, could the right thing to do be anything else but (1) sorting the dictionary items according to the term ordering, or (2) sorting the dictionary items according to the inverse term ordering, before feeding them to p_Add_q?