#17435: Cythonise path algebra elements
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: algebra | Resolution:
Keywords: path algebra | Merged in:
elements, days64.5, days65 | Reviewers:
Authors: Simon King | Work issues:
Report Upstream: N/A | Commit:
Branch: | 8d5d84687d0b60db3890a1f00b6b8acac3fc2c67
public/17435/cythonise_path_algebra_elements| Stopgaps:
Dependencies: #16453 #17526 |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Replying to [comment:123 jdemeyer]:
> In short, I would prefer to revert all changes to bitset/biseq.
I didn't revert all changes, but most of them. Also I changed the signal
handling according to your advices.
These changes did hardly change the timings for the few examples that I
did. As mentioned in comment:136, profiling indicated that I should use
more care for deallocation resp. for the freelist. I did as follows:
1. The freelist (which serves for lazy allocation/deallocation of terms)
now is not a linked list of terms, but a static array. That allowed to
simplify term_free and term_create_... functions.
2. I increased the size of the freelist from 1000 to 5000. Hopefully
acceptable.
3. Examples show that it is unlikely that the freelist is empty, it is
unlikely that we are dealing with paths of length zero, and it is likely
that monomials have more than one reference. I used Cython's likely(...)
and unlikely(...) accordingly, which seemed to have an effect.
__Results__
- Doctests pass.
- It still seems that functions are interruptible.
- I tested that
{{{
sage: P =
DiGraph({Integer(1):{Integer(1):['x','y','z']}}).path_semigroup().algebra(GF(Integer(25),'t'))
sage: P.inject_variables()
Defining e_1, x, y, z
sage: while 1:
....: p = x^4+x*y*x*z+2*z^2*x*y
....: q = p^7
....: print get_memory_usage()
}}}
does not leak memory.
- Timing now is as follows:
{{{
sage: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 4.13 times longer than the fastest. This could mean
that an intermediate result is being cached
100000 loops, best of 3: 17.9 µs per loop
sage: p = x^4+x*y*x*z+2*z^2*x*y
sage: %timeit q = p^7
1000 loops, best of 3: 954 µs per loop
}}}
That is no change in the "small" example and a visible improvement in
the second example.
- Profiling yields
{{{
sage: %crun for n in xrange(1000): q = (x^4+x*y*x*z+2*z^2*x*y)^7
PROFILE: interrupts/evictions/bytes = 103/1/28248
Using local file /home/king/Sage/git/sage/local/bin/python.
Using local file /home/king/.sage/temp/linux-
va3e.site/14199/tmp_FhpNzY.perf.
Total: 103 samples
0 0.0% 0.0% 91 88.3% PyEval_EvalCode
1 1.0% 1.0% 91 88.3% PyEval_EvalCodeEx
1 1.0% 1.9% 91 88.3% PyEval_EvalFrameEx
0 0.0% 1.9% 91 88.3% PyObject_Call
0 0.0% 1.9% 91 88.3% PyRun_FileExFlags
0 0.0% 1.9% 91 88.3% PyRun_SimpleFileExFlags
0 0.0% 1.9% 91 88.3% PyRun_StringFlags
0 0.0% 1.9% 91 88.3% Py_Main
0 0.0% 1.9% 91 88.3% __libc_start_main
0 0.0% 1.9% 91 88.3% _start
0 0.0% 1.9% 91 88.3% call_function (inline)
0 0.0% 1.9% 91 88.3% exec_statement (inline)
0 0.0% 1.9% 91 88.3% ext_do_call (inline)
0 0.0% 1.9% 91 88.3% fast_function (inline)
0 0.0% 1.9% 91 88.3% function_call
0 0.0% 1.9% 91 88.3% run_mod (inline)
0 0.0% 1.9% 81 78.6% PyNumber_Multiply
0 0.0% 1.9% 81 78.6% PyNumber_Power
0 0.0% 1.9% 81 78.6%
__pyx_f_4sage_9structure_7element_generic_power_c
0 0.0% 1.9% 81 78.6%
__pyx_pf_4sage_9structure_7element_11RingElement_10__mul__ (inline)
0 0.0% 1.9% 81 78.6%
__pyx_pf_4sage_9structure_7element_11RingElement_16__pow__ (inline)
0 0.0% 1.9% 81 78.6%
__pyx_pw_4sage_9structure_7element_11RingElement_11__mul__
0 0.0% 1.9% 81 78.6%
__pyx_pw_4sage_9structure_7element_11RingElement_17__pow__
0 0.0% 1.9% 81 78.6% binary_op1 (inline)
0 0.0% 1.9% 81 78.6% ternary_op (inline)
0 0.0% 1.9% 80 77.7%
__pyx_f_4sage_7quivers_16algebra_elements_18PathAlgebraElement__mul_
2 1.9% 3.9% 79 76.7%
__pyx_f_4sage_7quivers_16algebra_elements_poly_iadd_lmul.isra.60.constprop.73
2 1.9% 5.8% 36 35.0%
__pyx_f_4sage_7quivers_16algebra_elements_mon_mul_path
2 1.9% 7.8% 27 26.2%
__pyx_f_4sage_7quivers_16algebra_elements_term_create_keep_mon (inline)
2 1.9% 9.7% 24 23.3%
__pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_init_concat
1 1.0% 10.7% 24 23.3%
__pyx_f_4sage_7quivers_16algebra_elements_mon_free (inline)
1 1.0% 11.7% 23 22.3%
__pyx_f_4sage_7quivers_16algebra_elements_mon_free.part.15
20 19.4% 31.1% 20 19.4% _int_free
3 2.9% 34.0% 16 15.5%
__pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_init
10 9.7% 43.7% 12 11.7% __calloc
0 0.0% 43.7% 12 11.7%
__pyx_f_4sage_15data_structures_25bounded_integer_sequences_bitset_init
(inline)
0 0.0% 43.7% 12 11.7%
__pyx_f_4sage_3ext_6memory_check_calloc (inline)
0 0.0% 43.7% 12 11.7% sage_calloc (inline)
0 0.0% 43.7% 11 10.7%
__pyx_f_4sage_3ext_6memory_check_malloc (inline)
0 0.0% 43.7% 11 10.7% sage_malloc (inline)
10 9.7% 53.4% 10 9.7% _int_malloc
2 1.9% 55.3% 9 8.7% __GI___libc_malloc
0 0.0% 55.3% 8 7.8% PyDict_SetItem
0 0.0% 55.3% 8 7.8%
__pyx_f_4sage_7quivers_16algebra_elements_homog_poly_free
0 0.0% 55.3% 8 7.8%
__pyx_f_4sage_7quivers_16algebra_elements_poly_dealloc (inline)
0 0.0% 55.3% 8 7.8%
__pyx_f_4sage_7quivers_16algebra_elements_poly_free (inline)
8 7.8% 63.1% 8 7.8%
__pyx_f_4sage_7quivers_16algebra_elements_term_free (inline)
0 0.0% 63.1% 8 7.8%
__pyx_pf_4sage_7quivers_16algebra_elements_18PathAlgebraElement_2__dealloc__
(inline)
0 0.0% 63.1% 8 7.8%
__pyx_pw_4sage_7quivers_16algebra_elements_18PathAlgebraElement_3__dealloc__
(inline)
0 0.0% 63.1% 8 7.8%
__pyx_tp_dealloc_4sage_7quivers_16algebra_elements_PathAlgebraElement
0 0.0% 63.1% 8 7.8% dict_set_item_by_hash_or_entry
(inline)
0 0.0% 63.1% 8 7.8% insertdict (inline)
0 0.0% 63.1% 8 7.8% insertdict_by_entry
1 1.0% 64.1% 5 4.9% PyObject_IsTrue
0 0.0% 64.1% 5 4.9% __Pyx_PyObject_IsTrue (inline)
2 1.9% 66.0% 5 4.9%
__pyx_f_4sage_7quivers_16algebra_elements_negdegrevlex
4 3.9% 69.9% 4 3.9%
__pyx_pf_4sage_5rings_12finite_rings_14element_givaro_25FiniteField_givaroElement_8__nonzero__
(inline)
0 0.0% 69.9% 4 3.9%
__pyx_pw_4sage_5rings_12finite_rings_14element_givaro_25FiniteField_givaroElement_9__nonzero__
3 2.9% 72.8% 3 2.9% __GI___sigsetjmp
3 2.9% 75.7% 3 2.9%
__pyx_f_4sage_9structure_7element_have_same_parent_c
3 2.9% 78.6% 3 2.9% _init@4f78
3 2.9% 81.6% 3 2.9% _sig_on_prejmp (inline)
2 1.9% 83.5% 3 2.9% sig_block (inline)
0 0.0% 83.5% 2 1.9% __Pyx_GetException
1 1.0% 84.5% 2 1.9%
__pyx_f_4sage_5rings_12finite_rings_14element_givaro_25FiniteField_givaroElement__mul_
2 1.9% 86.4% 2 1.9% mpn_ior_n
0 0.0% 86.4% 1 1.0% 0x0000000004ac78f7
0 0.0% 86.4% 1 1.0% 0x0000000004b0b55f
0 0.0% 86.4% 1 1.0% 0x00007f5bb6e0988f
0 0.0% 86.4% 1 1.0% 0x00007f5bb6e09ebf
1 1.0% 87.4% 1 1.0% PyObject_GC_UnTrack
0 0.0% 87.4% 1 1.0% PyObject_RichCompare
0 0.0% 87.4% 1 1.0% _PyObject_GC_Track
1 1.0% 88.3% 1 1.0% __GI___libc_free
0 0.0% 88.3% 1 1.0%
__Pyx_Generator_CheckRunning.isra.10.part.11
0 0.0% 88.3% 1 1.0% __Pyx_PyObject_Call (inline)
0 0.0% 88.3% 1 1.0%
__Pyx_mul_mp_bitcnt_t_checking_overflow (inline)
1 1.0% 89.3% 1 1.0%
__Pyx_mul_unsigned_long_checking_overflow (inline)
1 1.0% 90.3% 1 1.0% __gmpn_cmp (inline)
1 1.0% 91.3% 1 1.0% __gmpn_lshift
0 0.0% 91.3% 1 1.0%
__pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_init_slice
1 1.0% 92.2% 1 1.0%
__pyx_f_4sage_15data_structures_25bounded_integer_sequences_bitset_lshift
(inline)
1 1.0% 93.2% 1 1.0%
__pyx_f_4sage_5rings_12finite_rings_14element_givaro_make_FiniteField_givaroElement
1 1.0% 94.2% 1 1.0%
__pyx_f_4sage_7quivers_16algebra_elements_18PathAlgebraElement__cmp_
1 1.0% 95.1% 1 1.0%
__pyx_f_4sage_7quivers_16algebra_elements_18PathAlgebraElement__new_
0 0.0% 95.1% 1 1.0%
__pyx_f_4sage_9structure_11coerce_maps_24DefaultConvertMap_unique__call_
0 0.0% 95.1% 1 1.0%
__pyx_f_4sage_9structure_14coerce_actions_16LeftModuleAction__call_
0 0.0% 95.1% 1 1.0%
__pyx_f_4sage_9structure_6coerce_24CoercionModel_cache_maps_bin_op
0 0.0% 95.1% 1 1.0%
__pyx_f_4sage_9structure_7element_7Element__richcmp
0 0.0% 95.1% 1 1.0%
__pyx_f_4sage_9structure_7element_7Element__richcmp_
0 0.0% 95.1% 1 1.0%
__pyx_pf_4sage_9structure_7element_7Element_62__richcmp__ (inline)
0 0.0% 95.1% 1 1.0%
__pyx_pw_4sage_9structure_7element_7Element_63__richcmp__
0 0.0% 95.1% 1 1.0%
__pyx_tp_dealloc_4sage_7quivers_16algebra_elements___pyx_scope_struct____iter__
0 0.0% 95.1% 1 1.0% __setfpucw
1 1.0% 96.1% 1 1.0% _init@4ab8
1 1.0% 97.1% 1 1.0% _sig_on_postjmp
1 1.0% 98.1% 1 1.0% _sig_on_postjmp (inline)
0 0.0% 98.1% 1 1.0% free_check
0 0.0% 98.1% 1 1.0% ln1
1 1.0% 99.0% 1 1.0% sig_unblock
1 1.0% 100.0% 1 1.0% sig_unblock (inline)
}}}
The difference in the profiling between biseq_init_concat and mon_mul_path
indicates how much time is spent for memory allocation of `path_mon_t*`.
It makes me think if I should perhaps replace the usage of `path_mon_t*`
by arrays of length one.
That would be similar to what is done for biseq_t and seemed to yield an
improvement. I couldn't do the same trick for terms, because I have linked
lists of terms. But for monomials it would perhaps make sense.
If someone likes to finish reviewing: Go ahead! If changing the monomials
has a good effect, then I can still open a new ticket, or post it here if
the review isn't finished yet.
--
Ticket URL: <http://trac.sagemath.org/ticket/17435#comment:138>
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.
