Opened 5 years ago

Last modified 4 years ago

#16040 new defect

libsingular mpolynomial from dict is slow

Reported by: vbraun Owned by:
Priority: major Milestone: sage-6.4
Component: algebra Keywords:
Cc: malb, burcin, jkeitel, SimonKing Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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)

Change History (5)

comment:1 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:2 Changed 5 years ago by SimonKing

  • Cc SimonKing added

comment:3 Changed 5 years ago by malb

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™.

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 4 years ago by SimonKing

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?

Note: See TracTickets for help on using tickets.