Cythonise path algebra elements #17435

simon-king-jena · 2014-12-02T23:39:52Z

#16453 provides a Cython version of quiver paths. The purpose of this ticket is to introduce a Cython implementation of path algebra elements.

Note that the arithmetic appears to be faster than the current default implementation of free associative algebras. So, it might make sense to use (the more general) path algebras to become the default for free associative algebras.

The next step shall be to implement computation of Gröbner bases. minimal generating sets and minimal projective resolutions for modules over path algebras, with a non-commutative F5 algorithm.

Depends on #16453
Depends on #17526

CC: @nthiery @nathanncohen @egunawan

Component: algebra

Keywords: path algebra elements, days64.5, days65

Author: Simon King

Branch/Commit: 5b4ed6e

Reviewer: Frédéric Chapoton

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

The text was updated successfully, but these errors were encountered:

simon-king-jena · 2014-12-03T00:01:33Z

Changed keywords from none to path algebra elements

simon-king-jena · 2014-12-03T00:01:33Z

Author: Simon King

simon-king-jena · 2014-12-03T00:01:33Z

Dependencies: #16453

simon-king-jena · 2014-12-03T00:02:45Z

Branch: u/SimonKing/cythonise_path_algebra_elements

simon-king-jena · 2014-12-03T00:04:10Z

Commit: 431b7f9

simon-king-jena · 2014-12-03T00:04:10Z

Last 10 new commits:

`c48b312`	`Cythoned path algebra elements`
`e85f3aa`	`Implement mul, cmp, hash; fix add`
`61c283a`	`Faster hash; fixed multiplication; temporary: sanity checks`
`1fda709`	`Path algebra elements now feature complete; minor changes to path algebras`
`15ed81d`	`Use PathAlgebraElement for path algebras. Still missing: Pickling`
`2b16f3a`	`Pickling of path algebra elements`
`6daa985`	`Fix conversion of path algebra elements`
`269a607`	`Verify during printing of a polynomial that the terms are ordered. Only allow degree orders. More docs.`
`b32b034`	`Conversion dict->path algebra element. Full doctest coverage.`
`431b7f9`	`Merge branch 't/17435/cythonise_path_algebra_elements' into cythonize_path_algebra_element`

sagetrac-git · 2014-12-03T06:51:46Z

Branch pushed to git repo; I updated commit sha1. New commits:

`99da336`	`Fixing some typos in the docs`

sagetrac-git · 2014-12-03T06:51:46Z

Changed commit from 431b7f9 to 99da336

simon-king-jena · 2014-12-03T11:17:45Z

comment:6

I just noticed a problem, most likely in _sub_:

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: P.inject_variables()
Defining e_1, x, y, z
sage: e_1 + 2*x*y*x*z*z*z*x*y - z*z*x*y*z*z*x*y   # gives wrong result
e_1 + 3*x*y*x*z*z*z*x*y + 4*z*z*x*y*z*z*x*y
sage: e_1 - z*z*x*y*z*z*x*y + 2*x*y*x*z*z*z*x*y   # gives correct result
e_1 + 2*x*y*x*z*z*z*x*y + 4*z*z*x*y*z*z*x*y

sagetrac-git · 2014-12-03T14:26:31Z

Branch pushed to git repo; I updated commit sha1. New commits:

`27b6ea9`	`Fix subtraction of path algebra elements`

sagetrac-git · 2014-12-03T14:26:31Z

Changed commit from 99da336 to 27b6ea9

simon-king-jena · 2014-12-03T14:29:48Z

comment:9

Fixed. The problem was that under certain circumstances, the computation c = a - b has put the negative of a term of a into c, where it should have put a copy of the term.

Now the tests work. I also included a comparison with the letterplace implementation of free associative algebras. Letterplace is faster, but it is restricted to homogeneous elements.

simon-king-jena · 2014-12-03T14:31:11Z

comment:10

PS: I wonder whether I should implement Karatsuba multiplication...

sagetrac-git · 2014-12-06T15:35:00Z

Branch pushed to git repo; I updated commit sha1. New commits:

`fab190e`	`Kill list for path algebra elements`
`6f07e26`	`Avoid needless term comparisons during multiplication`

sagetrac-git · 2014-12-06T15:35:00Z

Changed commit from 27b6ea9 to 6f07e26

simon-king-jena · 2014-12-06T15:41:22Z

comment:12

I did two changes:

I implemented a kill list for terms. It has not as much impact as I originally thought, so, maybe it makes sense to revert that change. However, when I did some c-profiling, a small improvement was visible.
In the multiplication of path algebra elements, I did far more term comparisons than needed. Actually (again by c-profiling) I found that half of the time was spent on the comparisons. In the latest commit, I avoid some comparisons by book keeping.

Now, at least according to few benchmarks, the arithmetic for path algebra elements is faster than the arithmetic for both available implementations of free associative algebra elements (one of them, letterplace, is available for homogeneous elements only). Hence, in the long run, it might be worth while to implement free associative algebras as quiver algebras!

At least with git-rerere enabled, the dependency merges cleanly into the branch. So, no merge commit this time...

sagetrac-git · 2014-12-10T12:00:05Z

Branch pushed to git repo; I updated commit sha1. New commits:

`a961dfd`	`Remove c-profiling`

sagetrac-git · 2014-12-10T12:00:05Z

Changed commit from 6f07e26 to a961dfd

simon-king-jena · 2014-12-10T12:01:44Z

comment:14

I forgot to remove some lines that enabled c-profiling (which was useful to get my implementation to better speed). Without it, it becomes a bit faster.

simon-king-jena · 2014-12-10T12:04:19Z

comment:15

Replying to @simon-king-jena:

I forgot to remove some lines that enabled c-profiling (which was useful to get my implementation to better speed). Without it, it becomes a bit faster.

... and thus I also updated the timings appearing in the docs.

simon-king-jena · 2015-08-27T14:54:20Z

comment:138

Replying to @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:

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.
I increased the size of the freelist from 1000 to 5000. Hopefully acceptable.
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.

sagetrac-git · 2015-08-27T16:30:58Z

Changed commit from 8d5d846 to 6ea8fa2

sagetrac-git · 2015-08-27T16:30:58Z

Branch pushed to git repo; I updated commit sha1. New commits:

`6ea8fa2`	`Move monomials from heap to stack`

simon-king-jena · 2015-08-27T16:42:12Z

comment:140

It was easy to move the monomials from heap to stack.

With the latest commit, it is still interruptible, arithmetic still runs without memory leak, and the timing becomes

sage: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 4.45 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 18 µs per loop
sage: %timeit q = p^7
1000 loops, best of 3: 740 µs per loop

So, the small example stays as it was, but the large example improved by as much as 22%!!

The profile:

sage: %crun for n in xrange(1000): q = (x^4+x*y*x*z+2*z^2*x*y)^7
PROFILE: interrupts/evictions/bytes = 77/5/26640
Using local file /home/king/Sage/git/sage/local/bin/python.
Using local file /home/king/.sage/temp/linux-va3e.site/15600/tmp_tOwJBh.perf.
Total: 77 samples
       0   0.0%   0.0%       71  92.2% PyEval_EvalCode
       0   0.0%   0.0%       71  92.2% PyEval_EvalCodeEx
       0   0.0%   0.0%       71  92.2% PyEval_EvalFrameEx
       0   0.0%   0.0%       71  92.2% PyObject_Call
       0   0.0%   0.0%       71  92.2% PyRun_FileExFlags
       0   0.0%   0.0%       71  92.2% PyRun_SimpleFileExFlags
       0   0.0%   0.0%       71  92.2% PyRun_StringFlags
       0   0.0%   0.0%       71  92.2% Py_Main
       0   0.0%   0.0%       71  92.2% __libc_start_main
       0   0.0%   0.0%       71  92.2% _start
       0   0.0%   0.0%       71  92.2% binary_op1 (inline)
       0   0.0%   0.0%       71  92.2% call_function (inline)
       0   0.0%   0.0%       71  92.2% exec_statement (inline)
       0   0.0%   0.0%       71  92.2% ext_do_call (inline)
       0   0.0%   0.0%       71  92.2% fast_function (inline)
       0   0.0%   0.0%       71  92.2% function_call
       0   0.0%   0.0%       71  92.2% run_mod (inline)
       1   1.3%   1.3%       70  90.9% PyNumber_Multiply
       0   0.0%   1.3%       70  90.9% __pyx_pf_4sage_9structure_7element_11RingElement_10__mul__ (inline)
       1   1.3%   2.6%       70  90.9% __pyx_pw_4sage_9structure_7element_11RingElement_11__mul__
       0   0.0%   2.6%       69  89.6% PyNumber_Power
       1   1.3%   3.9%       69  89.6% __pyx_f_4sage_7quivers_16algebra_elements_18PathAlgebraElement__mul_
       0   0.0%   3.9%       69  89.6% __pyx_f_4sage_9structure_7element_generic_power_c
       0   0.0%   3.9%       69  89.6% __pyx_pf_4sage_9structure_7element_11RingElement_16__pow__ (inline)
       0   0.0%   3.9%       69  89.6% __pyx_pw_4sage_9structure_7element_11RingElement_17__pow__
       0   0.0%   3.9%       69  89.6% ternary_op (inline)
       4   5.2%   9.1%       68  88.3% __pyx_f_4sage_7quivers_16algebra_elements_poly_iadd_lmul.isra.56.constprop.68
       2   2.6%  11.7%       27  35.1% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_init_concat
       0   0.0%  11.7%       27  35.1% __pyx_f_4sage_7quivers_16algebra_elements_mon_mul_path (inline)
       2   2.6%  14.3%       17  22.1% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_init
       0   0.0%  14.3%       16  20.8% __pyx_f_4sage_7quivers_16algebra_elements_mon_free (inline)
       1   1.3%  15.6%       16  20.8% __pyx_f_4sage_7quivers_16algebra_elements_term_create_blank (inline)
       0   0.0%  15.6%       15  19.5% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_dealloc
       0   0.0%  15.6%       15  19.5% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_bitset_free (inline)
       0   0.0%  15.6%       15  19.5% sage_free (inline)
      10  13.0%  28.6%       13  16.9% __calloc
       0   0.0%  28.6%       13  16.9% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_bitset_init (inline)
       0   0.0%  28.6%       13  16.9% __pyx_f_4sage_3ext_6memory_check_calloc (inline)
      13  16.9%  45.5%       13  16.9% _int_free
       0   0.0%  45.5%       13  16.9% sage_calloc (inline)
       3   3.9%  49.4%        9  11.7% __pyx_f_4sage_5rings_12finite_rings_14element_givaro_25FiniteField_givaroElement__mul_
       2   2.6%  51.9%        7   9.1% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_bitset_lshift (inline)
       5   6.5%  58.4%        7   9.1% __pyx_f_4sage_7quivers_16algebra_elements_negdegrevlex
       2   2.6%  61.0%        4   5.2% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_bitset_fix (inline)
       2   2.6%  63.6%        4   5.2% __pyx_f_4sage_5rings_12finite_rings_14element_givaro_make_FiniteField_givaroElement
       3   3.9%  67.5%        3   3.9% Givaro::GFqDom::mul (inline)
       3   3.9%  71.4%        3   3.9% PyObject_IsTrue
       0   0.0%  71.4%        3   3.9% __Pyx_PyObject_IsTrue (inline)
       0   0.0%  71.4%        3   3.9% __Pyx_mul_mp_bitcnt_t_checking_overflow (inline)
       3   3.9%  75.3%        3   3.9% __Pyx_mul_unsigned_long_checking_overflow (inline)
       3   3.9%  79.2%        3   3.9% _int_malloc
       2   2.6%  81.8%        2   2.6% __GI___sigsetjmp
       2   2.6%  84.4%        2   2.6% __Pyx_GetItemInt_Fast (inline)
       2   2.6%  87.0%        2   2.6% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_limb_lower_bits_up (inline)
       2   2.6%  89.6%        2   2.6% __sigjmp_save
       2   2.6%  92.2%        2   2.6% sig_block (inline)
       0   0.0%  92.2%        1   1.3% 0x00007fffb7051497
       1   1.3%  93.5%        1   1.3% PyErr_Fetch
       0   0.0%  93.5%        1   1.3% PyErr_Occurred
       0   0.0%  93.5%        1   1.3% PyNumber_Add
       0   0.0%  93.5%        1   1.3% __Pyx_PyObject_Call (inline)
       0   0.0%  93.5%        1   1.3% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_init_copy
       0   0.0%  93.5%        1   1.3% __pyx_f_4sage_15data_structures_25bounded_integer_sequences_biseq_init_copy (inline)
       1   1.3%  94.8%        1   1.3% __pyx_f_4sage_5rings_12finite_rings_14element_givaro_12Cache_givaro_element_from_data
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_7quivers_16algebra_elements_18PathAlgebraElement__add_
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_7quivers_16algebra_elements_mon_copy (inline)
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_7quivers_16algebra_elements_poly_add (inline)
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_7quivers_16algebra_elements_term_copy
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_7quivers_16algebra_elements_term_copy_recursive (inline)
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_9structure_11coerce_maps_24DefaultConvertMap_unique__call_
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_9structure_14coerce_actions_16LeftModuleAction__call_
       0   0.0%  94.8%        1   1.3% __pyx_f_4sage_9structure_6coerce_24CoercionModel_cache_maps_bin_op
       0   0.0%  94.8%        1   1.3% __pyx_pf_4sage_5rings_12finite_rings_14element_givaro_12Cache_givaro_14element_from_data (inline)
       0   0.0%  94.8%        1   1.3% __pyx_pf_4sage_9structure_7element_11RingElement_2__add__ (inline)
       0   0.0%  94.8%        1   1.3% __pyx_pw_4sage_5rings_12finite_rings_14element_givaro_12Cache_givaro_15element_from_data
       0   0.0%  94.8%        1   1.3% __pyx_pw_4sage_5rings_12finite_rings_14element_givaro_25FiniteField_givaroElement_33__richcmp__
       0   0.0%  94.8%        1   1.3% __pyx_pw_4sage_9structure_7element_11RingElement_3__add__
       0   0.0%  94.8%        1   1.3% __setfpucw
       1   1.3%  96.1%        1   1.3% _init
       1   1.3%  97.4%        1   1.3% _sig_on_prejmp (inline)
       1   1.3%  98.7%        1   1.3% mpn_ior_n
       0   0.0%  98.7%        1   1.3% sig_check (inline)
       1   1.3% 100.0%        1   1.3% sig_unblock (inline)
       0   0.0% 100.0%        1   1.3% top_check

The difference between biseq_init_concat and mon_mul_path has disappeared, which obviously is a consequence of using the stack (before, there was an expensive sage_calloc).

Also, tests still pass.

I think I am done now! At least unless I find that after all these changes I find a benefit in inlining some monomial-related functions...

simon-king-jena · 2015-08-27T16:46:43Z

comment:141

Replying to @simon-king-jena:

I think I am done now! At least unless I find that after all these changes I find a benefit in inlining some monomial-related functions...

I just noticed that all mon_... functions appearing in the profile in fact are inline, even though I did not suggest to the compiler that mon_mul_path should be inlined. Thus, the compiler was clever enough :-).

Therefore, I will abstain from playing with inline now. I will stop coding now, so, please continue reviewing!

fchapoton · 2015-09-11T08:40:46Z

comment:142

I would like to have a patchbot's green light on the latest version..

fchapoton · 2015-09-15T14:12:57Z

comment:143

There are two failing doctests, see patchbot report.

jdemeyer · 2015-09-16T09:31:07Z

comment:144

Why all the changes inside bounded_integer_sequences anyway? I don't think any of these changes is needed for this ticket. If you think they are needed, can they be moved to a new ticket?

simon-king-jena · 2015-09-23T08:21:41Z

comment:145

Replying to @jdemeyer:

Why all the changes inside bounded_integer_sequences anyway? I don't think any of these changes is needed for this ticket. If you think they are needed, can they be moved to a new ticket?

I'll have a look (after #12103, this here is the next I want to finally finish).

Question: How should I change it? By rebasing and force-push? Or by a commit that reverses the changes and is perhaps reversed again on another ticket?

Do you think the little changes in bitset can stay?

tscrim · 2015-09-23T13:04:20Z

comment:146

Replying to @simon-king-jena:

Question: How should I change it? By rebasing and force-push? Or by a commit that reverses the changes and is perhaps reversed again on another ticket?

Another commit; it's good to have history which shows things you did (because you might want to look at/use them later). Plus you would not be changing history.

simon-king-jena · 2015-09-23T13:07:15Z

comment:147

Replying to @tscrim:

Plus you would not be changing history.

... IF it there is some likelyhood that other people are already using the branch and thus needed to rebase their work if I rebase the branch. I asked because I am not sure if people do use the branch. I do, but I think I don't count here.

Anyway, let's do it with a new commit.

sagetrac-git · 2015-09-23T13:23:28Z

Branch pushed to git repo; I updated commit sha1. New commits:

`cfb56ce`	`Merge branch 'develop' into t/17435/cythonise_path_algebra_elements`
`5b4ed6e`	`Revert changes to bounded_integer_sequences`

sagetrac-git · 2015-09-23T13:23:28Z

Changed commit from 6ea8fa2 to 5b4ed6e

nathanncohen · 2015-09-23T13:51:25Z

comment:150

... IF it there is some likelyhood that other people are already using the branch and thus needed to rebase their work if I rebase the branch.

Not to mention that unless they also modify your code in their branch (and not just "use it") then their rebase would be totally trivial.

Nathann

fchapoton · 2015-09-24T11:13:15Z

comment:151

ok, my patchbot has given a green light, and I have no further comments on the code.

Any further enhancement could be done in another ticket.

So positive review.

fchapoton · 2015-09-24T11:13:15Z

Reviewer: Frédéric Chapoton

simon-king-jena · 2015-09-24T13:15:15Z

comment:152

It took a very long time to finish this ticket (I had the first version of the code on my laptop two years ago), but the comments of the referees have been very helpful and resulted in major improvements.

Jeroen, shouldn't your name be added to the list of reviewers as well?

Thank you very much!

vbraun · 2015-09-25T07:53:00Z

Changed branch from public/17435/cythonise_path_algebra_elements to 5b4ed6e

simon-king-jena added this to the sage-6.5 milestone Dec 2, 2014

simon-king-jena added the p: major / 3 label Dec 2, 2014

This comment has been minimized.

Sign in to view

simon-king-jena added t: enhancement labels Dec 3, 2014

simon-king-jena added the s: needs review label Dec 3, 2014

simon-king-jena added s: needs work and removed s: needs review labels Dec 3, 2014

simon-king-jena added s: needs review and removed s: needs work labels Dec 3, 2014

fchapoton modified the milestones: sage-6.8, sage-6.9 Sep 11, 2015

fchapoton added s: needs work and removed s: needs review labels Sep 15, 2015

simon-king-jena added s: needs review and removed s: needs work labels Sep 23, 2015

fchapoton added s: positive review and removed s: needs review labels Sep 24, 2015

vbraun removed the s: positive review label Sep 25, 2015

vbraun closed this as completed in fbcd898 Sep 25, 2015

This was referenced Dec 29, 2022

Memory leak for letterplace implementation of free algebras #17494

Open

Allow cyclic quivers in quiver representation #18632

Open

Cythonise path algebra elements #17435

Cythonise path algebra elements #17435

Comments

simon-king-jena commented Dec 2, 2014

simon-king-jena commented Dec 3, 2014

This comment has been minimized.

simon-king-jena commented Dec 3, 2014

simon-king-jena commented Dec 3, 2014

simon-king-jena commented Dec 3, 2014

simon-king-jena commented Dec 3, 2014

simon-king-jena commented Dec 3, 2014

sagetrac-git mannequin commented Dec 3, 2014

sagetrac-git mannequin commented Dec 3, 2014

simon-king-jena commented Dec 3, 2014

sagetrac-git mannequin commented Dec 3, 2014

sagetrac-git mannequin commented Dec 3, 2014

simon-king-jena commented Dec 3, 2014

simon-king-jena commented Dec 3, 2014

sagetrac-git mannequin commented Dec 6, 2014

sagetrac-git mannequin commented Dec 6, 2014

simon-king-jena commented Dec 6, 2014

sagetrac-git mannequin commented Dec 10, 2014

sagetrac-git mannequin commented Dec 10, 2014

simon-king-jena commented Dec 10, 2014

simon-king-jena commented Dec 10, 2014

simon-king-jena commented Aug 27, 2015

sagetrac-git mannequin commented Aug 27, 2015

sagetrac-git mannequin commented Aug 27, 2015

simon-king-jena commented Aug 27, 2015

simon-king-jena commented Aug 27, 2015

fchapoton commented Sep 11, 2015

fchapoton commented Sep 15, 2015

jdemeyer commented Sep 16, 2015

simon-king-jena commented Sep 23, 2015

tscrim commented Sep 23, 2015

simon-king-jena commented Sep 23, 2015

sagetrac-git mannequin commented Sep 23, 2015

sagetrac-git mannequin commented Sep 23, 2015

nathanncohen mannequin commented Sep 23, 2015

fchapoton commented Sep 24, 2015

fchapoton commented Sep 24, 2015

simon-king-jena commented Sep 24, 2015

vbraun commented Sep 25, 2015