Opened 7 years ago

Closed 7 years ago

# Cythonise path algebra elements

Reported by: Owned by: SimonKing major sage-6.9 algebra path algebra elements, days64.5, days65 nthiery, ncohen, egunawan Simon King Frédéric Chapoton N/A 5b4ed6e 5b4ed6e69229b0809a1ab4ab63938569fed30b44 #16453 #17526

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

### comment:1 Changed 7 years ago by SimonKing

• Authors set to Simon King
• Component changed from PLEASE CHANGE to algebra
• Dependencies set to #16453
• Description modified (diff)
• Keywords path algebra elements added
• Type changed from PLEASE CHANGE to enhancement

### comment:2 Changed 7 years ago by SimonKing

• Branch set to u/SimonKing/cythonise_path_algebra_elements

### comment:3 Changed 7 years ago by SimonKing

• Commit set to 431b7f9a770b9f5749ab094702b5cd275c13d0ab

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

### comment:4 Changed 7 years ago by SimonKing

• Status changed from new to needs_review

### comment:5 Changed 7 years ago by git

• Commit changed from 431b7f9a770b9f5749ab094702b5cd275c13d0ab to 99da3361014e5397d8bc24a0ec1e2db1df6014f8

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

 ​99da336 Fixing some typos in the docs

### comment:6 Changed 7 years ago by SimonKing

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


### comment:7 Changed 7 years ago by SimonKing

• Status changed from needs_review to needs_work

### comment:8 Changed 7 years ago by git

• Commit changed from 99da3361014e5397d8bc24a0ec1e2db1df6014f8 to 27b6ea96786c16b60489b46e7835c7af986c5584

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

 ​27b6ea9 Fix subtraction of path algebra elements

### comment:9 Changed 7 years ago by SimonKing

• Status changed from needs_work to needs_review

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.

### comment:10 Changed 7 years ago by SimonKing

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

### comment:11 Changed 7 years ago by git

• Commit changed from 27b6ea96786c16b60489b46e7835c7af986c5584 to 6f07e2628edf7b21296a7ec020d8eca8d5139a8a

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

### comment:12 Changed 7 years ago by SimonKing

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

### comment:13 Changed 7 years ago by git

• Commit changed from 6f07e2628edf7b21296a7ec020d8eca8d5139a8a to a961dfdfc400b165a05ba8f41a7efcf08c104c84

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

 ​a961dfd Remove c-profiling

### comment:14 follow-up: ↓ 15 Changed 7 years ago by SimonKing

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.

### comment:15 in reply to: ↑ 14 Changed 7 years ago by SimonKing

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.

### comment:16 Changed 7 years ago by SimonKing

I just noticed that the letterplace implementation leaks in the following example:

sage: L.<x,y,z> = FreeAlgebra(GF(25,'t'), implementation='letterplace')
sage: p = x^4+x*y*x*z+2*z^2*x*y
sage: while 1:
....:     print get_memory_usage()
....:     z = p^7


The corresponding example with path algebras does not leak (one only sees that the kill list fills up in the first few iterations):

sage: P = DiGraph({1:{1:['x','y','z']}}).path_semigroup().algebra(GF(25,'t'))
sage: p = sage_eval('x+y*z*x+2*y-z+1', P.gens_dict())
sage: while 1:
....:     print get_memory_usage()
....:     z = p^7


That might explain why letterplace is slower than path algebras. In any case, fixing the leak should be the purpose of another ticket.

### comment:17 Changed 7 years ago by git

• Commit changed from a961dfdfc400b165a05ba8f41a7efcf08c104c84 to 3c8ae84ad88dfa8aab8b2c7a609aaa471a369fae

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

 ​880801f Make doctests of path algebra elements work on 64 bit ​3c8ae84 Fix deallocation of kill list

### comment:18 Changed 7 years ago by SimonKing

I have changed my operating system from openSUSE 12.3 32bit to openSUSE 13.2 64bit. Doing so, I found that one doctest depended on the bits. So, I fixed that.

Also, I found one crash, and it is astounding that it did not occur before: When I put a term on the kill list, I dereference the coefficient. When I remove the kill list (which happens when Sage quits) then I dereferenced the coefficient *again*. That's of course wrong, and corrected in the second commit.

Something else: While the change from 32bit to 64bit did not make letterplace faster, the timings for my implementation improved by as much as 20%! So, I am looking forward to my applications :-).

Concerning timings: Is it ok to include timings into the docs? After all, they are on a particular machine etc. Is there a policy? If so, I could remove the corresponding parts from sage.quivers.algebra_elements.

### comment:19 Changed 7 years ago by git

• Commit changed from 3c8ae84ad88dfa8aab8b2c7a609aaa471a369fae to b080629d373feb384750218e99b9f77286fd79b9

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

 ​b080629 Elaborate on the role of different implementations of free algebras

### comment:20 Changed 7 years ago by SimonKing

According to Nathann's comment on sage-devel, including timings is ok, as long as the timings are consistent on different machines.

In this case, on openSUSE 32bit, arithmetic for path algebra elements is faster than arithmetic for letterplace free algebra elements, which is much faster than arithmetic for the default implementation of free algebra elements. On openSUSE 64bit, it is the same ranking; while letterplace is not faster in 64bit than in 32bit, the path algebra implementation becomes 20% faster in this example.

Of course, the purpose of the three implementations is different:

The letterplace implementation only allows to deal with homogeneous elements, but in contrast to the default implementation for free algebras it comes with standard basis computations, allowing to construct graded algebra quotients.

Path algebras are more general then free associative algebras, and homogeneity is not required. At the moment, standard bases are not available---but in fact this should be the next step. I plan to finish implementing a non-commutitive F5 algorithm, which can compute standard bases for one and two-sided ideals of modules over path algebra quotients (in particular, of ideals in path algebras, so that one can deal with algebra quotients), provided of course that the computation terminates in finite time. And moreover, it will be able to compute minimal generating sets of modules over basic algebras.

So, in the long run, it might make sense to replace the current default implementation of free algebra elements, modelling free associative algebras as a special case of path algebras. But that's for future. I hope that for now the comment on the relation of the three implementations is fine.

### comment:21 Changed 7 years ago by SimonKing

• Dependencies changed from #16453 to #16453 #17526
• Status changed from needs_review to needs_work
• Work issues set to Merge

Sigh. Develop doesn't merge cleanly. So, merge is needed. Moreover, it would be good to make #17526 a dependency, since that fixes a bug for bitsets that is relevant here.

### comment:22 follow-up: ↓ 23 Changed 7 years ago by SimonKing

Arrgh. I hate git's merge. And I hate the fact that I had to re-install git-rerere on my laptop, since I had to re-install my OS.

### comment:23 in reply to: ↑ 22 Changed 7 years ago by SimonKing

And I hate the fact that I had to re-install git-rerere on my laptop, since I had to re-install my OS.

Or not? Apparently git rerere is there. Nevertheless, I am asked to do merges that I have been done in the past (repeatedly).

### comment:24 Changed 7 years ago by SimonKing

What the heck is wrong with git?

I just tried to merge #17526 with the branch here. #17526 only changes bitset.pxi. But git merge asks me to resolve conflicts in bounded_integer_sequences.pyx. I am tired of these artificial conflicts that git is producing.

### comment:25 Changed 7 years ago by git

• Commit changed from b080629d373feb384750218e99b9f77286fd79b9 to cd77a17eacc60b56921f9695ffd3d8d2187cebfa

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

 ​cd77a17 Merge branch 't/15820/ticket/15820' into t/17435/cythonise_path_algebra_elements

### comment:26 follow-up: ↓ 27 Changed 7 years ago by SimonKing

Argh. The merge has failed.

### comment:27 in reply to: ↑ 26 Changed 7 years ago by SimonKing

Argh. The merge has failed.

In fact, git merge has reverted changes from #16453. Frankly, at the moment my impression is that git is very bad for productivity.

### comment:28 Changed 7 years ago by git

• Commit changed from cd77a17eacc60b56921f9695ffd3d8d2187cebfa to 7d9d492e0307bcf2e6c73e8c903131fcde7c178f

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

 ​7564770 Merge branch 'develop' into t/15820/ticket/15820 ​962c674 Merge branch 'u/jdemeyer/ticket/15820' of git://trac.sagemath.org/sage into t/15820/ticket/15820 ​63d2693 More descriptive function name for bounded integer sequences ​af690ca Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths ​126ee26 Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths ​6a6d913 Do less imports in path's pxd file; signal handling in one function ​73b6539 revert a change to pickling of bounded integer sequences ​73ac689 Allow to choose two alternative encodings of paths ​0432297 Remove alternative implementation of paths, because of benchmark results ​7d9d492 Merge branch 't/16453/cythonize_quiver_paths' into t/17435/cythonise_path_algebra_elements

### comment:29 Changed 7 years ago by SimonKing

As it turns out, the "32bit vs 64bit" problem should be fixed at #16453, not here. With mercurial, one could just move the patch from here to there. With git, I expect it will be a lot more difficult to cope with an erroneous commit. If I understood Volker's advice, I should not try to merge #16453 again (after fixing the error there, we will have a new merge conflict) as long as the branch here works. So, I just leave it.

### comment:30 Changed 7 years ago by SimonKing

It could be that I will rewrite everything from scratch. Reason: Volker gave some good arguments on sage-devel why I should not use C structs for the terms on PyObject* for the coefficients (even though it seems I got the reference counting right...), but should rely on Python objects. It could be that I'll end up implementing an element of a path algebra as a typed memoryview...

We will see.

### comment:31 Changed 7 years ago by SimonKing

• Branch changed from u/SimonKing/cythonise_path_algebra_elements to public/17435/cythonise_path_algebra_elements

### comment:32 Changed 7 years ago by SimonKing

• Commit changed from 7d9d492e0307bcf2e6c73e8c903131fcde7c178f to ba2ed8ddf6286a87ebb92b29b4912bd4b320df0e

Since supposedly nobody but me was using the old branch of this ticket, since nobody was attempting a full review, since the branch of one dependency has changed and since the commit history was a bit messy, I created a new branch by rebasing and attached it here.

The resulting code did not change. I still use linked lists. Actually I am not convinced that arrays could be better, since my impression is that arithmetic operations would involve copying the content of the arrays around, whereas with linked lists one has just to redirect pointers.

Anyway, I plan to do some tests with arrays, but I think the code is ready for review, and a change to arrays could be done on a different ticket, if useful.

New commits:

 ​f2a69ab More useful functions for biseq_t ​fd3fd82 Better hash function for biseq_t. Document the new functions. ​b10c172 Cython implementation of quiver paths ​9d56888 Use Cython implementation of paths in path algebras/representations ​3b26941 Cythoned path algebra elements ​6118f0a Kill list for path algebra elements ​0433d0c Avoid needless term comparisons during multiplication ​ba2ed8d Elaborate on the role of different implementations of free algebras
Last edited 7 years ago by SimonKing (previous) (diff)

### comment:33 Changed 7 years ago by SimonKing

The branch does not cleanly merge into develop. Hence, I have to resolve a conflict and push here.

### comment:34 Changed 7 years ago by git

• Commit changed from ba2ed8ddf6286a87ebb92b29b4912bd4b320df0e to 5a5e35de6b19c1453ec4b40f797d507117ff60bc

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

 ​0a72b46 Add a doctest for _nb_arrows ​70503e3 Clarify the documentation of _cmp_c_impl ​8984ea7 Merge branch 'public/ticket/16453' of git://trac.sagemath.org/sage into t/17435/cythonise_path_algebra_elements_6.7.beta ​5a5e35d Merge branch 'public/17435/cythonise_path_algebra_elements' of git://trac.sagemath.org/sage into t/17435/cythonise_path_algebra_elements_6.7.beta

### comment:35 Changed 7 years ago by SimonKing

• Work issues changed from Merge to Fix segfaults

The merge conflict is resolved. However, it is not ready for review yet: There are segfaults related with coercion. That's bad.

### comment:36 Changed 7 years ago by git

• Commit changed from 5a5e35de6b19c1453ec4b40f797d507117ff60bc to 35eb6c24469b4c44d892e2c2d49c6381f470dc7e

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

 ​35eb6c2 Remove arguments from __cinit__

### comment:37 Changed 7 years ago by SimonKing

Apparently it was needed to remove optional arguments from __cinit__. Dunno if the behaviour of __cinit__ or PY_NEW has changed recently.

### comment:38 Changed 7 years ago by SimonKing

• Status changed from needs_work to needs_review
• Work issues Fix segfaults deleted

### comment:39 Changed 7 years ago by git

• Commit changed from 35eb6c24469b4c44d892e2c2d49c6381f470dc7e to c89be23ef352198dc697a7940673e8fe222d04f2

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

 ​c89be23 Fix multiplication path*monomial*path

### comment:40 Changed 7 years ago by git

• Commit changed from c89be23ef352198dc697a7940673e8fe222d04f2 to f30e7f74d4a164b0269e14c39948e26cff84e505

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

 ​3e94fef Merge with 6.7.beta4, cope with the change of _cmp_c_impl -> _cmp_ ​93f5310 Address reviewer's comments ​cbde0c3 Elaborate on the meaning of gcd for paths ​e8d802e Merge branch 't/17435/cythonise_path_algebra_elements_6.7.beta' into t/17435/cythonise_path_algebra_elements_6.7.beta4 ​f30e7f7 Change _cmp_c_impl -> _cmp_ for path algebra elements

### comment:41 Changed 7 years ago by SimonKing

I had to resolve a merge conflict at #16453, and I had to cope with the recent change from _cmp_c_impl to _cmp_ for elements. All tests in sage.quivers pass.

### comment:42 Changed 7 years ago by git

• Commit changed from f30e7f74d4a164b0269e14c39948e26cff84e505 to ecf87e10308fe4ccb311bd5cda6f94681dedc794

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

 ​9168ed3 Some Cython tweaks for quiver paths ​3f0adee Use cached_method on PathSemigroup.reverese, for efficiency ​028c85d Store edge tuple as attribute of path semigroups; length zero path evaluate to false; fix some typos ​2dd3206 Fix path slicing with step -1, and add test ​ecf87e1 Merge branch 't/16453/cythonize_quiver_paths_6.7.beta4' into t/17435/cythonise_path_algebra_elements_6.7.beta4

### comment:43 Changed 7 years ago by SimonKing

There was a conflict, hence, I think I had to push a merge commit...

### comment:44 Changed 7 years ago by SimonKing

• Status changed from needs_review to needs_work
• Work issues set to Resolve yet another merge conflict

ANOTHER merge conflict???? It really sucks.

### comment:45 Changed 7 years ago by git

• Commit changed from ecf87e10308fe4ccb311bd5cda6f94681dedc794 to 330baeb7815351c0e813400a9473abcb3689f567

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

 ​330baeb Merge branch 'public/17435/cythonise_path_algebra_elements' of git://trac.sagemath.org/sage into t/17435/cythonise_path_algebra_elements_6.8.beta2

### comment:46 Changed 7 years ago by SimonKing

• Status changed from needs_work to needs_review
• Work issues Resolve yet another merge conflict deleted

Conflict resolved, tests pass. Needs review.

### comment:48 Changed 7 years ago by SimonKing

Remark: The failing test on some patchbot is in pexpect, hence, unrelated to this ticket.

### comment:49 Changed 7 years ago by SimonKing

• Keywords days64.5 days65 added; SageDays64.5 removed

### comment:50 Changed 7 years ago by egunawan

• Milestone changed from sage-6.5 to sage-6.8

### comment:51 Changed 7 years ago by git

• Commit changed from 330baeb7815351c0e813400a9473abcb3689f567 to 21da25a9d1057f21e8ef7afe4028171319f4c580

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

 ​21da25a Add a method to determine the complement of a subpath

### comment:52 Changed 7 years ago by SimonKing

The previous commit adds a method for paths, that should be useful in Gröbner basis computations and thus somehow belongs to a ticket on path algebras.

### comment:53 Changed 7 years ago by kdilks

• Status changed from needs_review to needs_work
• Work issues set to Yet another merge conflict

### comment:54 Changed 7 years ago by SimonKing

Are you kidding?? There really is another merge conflict? Unbelievable!

### comment:55 Changed 7 years ago by SimonKing

The conflict appears to be with #16064.

### comment:56 Changed 7 years ago by git

• Commit changed from 21da25a9d1057f21e8ef7afe4028171319f4c580 to 0e094053ea05d59197de9152b9206caa09c40cb8

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

 ​0e09405 Resolve merge conflict with trac #16064

### comment:57 Changed 7 years ago by SimonKing

• Status changed from needs_work to needs_review
• Work issues Yet another merge conflict deleted

Should be good now.

### comment:58 follow-up: ↓ 59 Changed 7 years ago by SimonKing

The failing test shown by the patchbot is in pexpect and clearly unrelated with this ticket. Can somebody try to review it, before it starts bitrotting again?

### comment:59 in reply to: ↑ 58 Changed 7 years ago by SimonKing

• Status changed from needs_review to needs_work
• Work issues set to Remove Py_NEW, prepare Schreyer orderings

Can somebody try to review it, before it starts bitrotting again?

I am afraid it happened again. This time, Py_NEW won't work any longer, since a cythoned class is now not a type any longer (if I understand correctly).

In addition to that, I'd like to change a couple of things that are related with my upcoming application (F5 algorithm for path algebras), namely a framework to use Schreyer orderings. They may be useful when computing Syzygies (as experience in the commutative case shows). Let I_i be the i-th generator of a two-sided free module, and a*I_i*b be a monomial (paths a, b). A Schreyer ordering is given by choosing, for each i, a path s_i, and then comparison of a*I_i*b and c*I_j*d involves a comparison of the paths a*s_i*b and c*s_j*d.

I believe such a change belongs here (even though the applications do not appear here).

### comment:60 Changed 7 years ago by SimonKing

PS: I see that I here use a "cutoff" for monomials (longer monomials are set to zero). I won't use that in my applications and thus remove that, too.

### comment:61 Changed 7 years ago by git

• Commit changed from 0e094053ea05d59197de9152b9206caa09c40cb8 to 10c8167050b2565b6b8d1678ed17eb927a1d4d1a

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

 ​45ac933 Merge branch 'develop' into t/17435/cythonise_path_algebra_elements ​10c8167 Prepare Schreyer orderings for later applications

### comment:62 Changed 7 years ago by SimonKing

• Status changed from needs_work to needs_review
• Work issues Remove Py_NEW, prepare Schreyer orderings deleted

Since Py_NEW only is a problem with the latest beta, I merged with develop. Then, I removed the "cutoff" thingy that has turned out (in my private work branch) to lead to nothing, and instead I provided some framework for Schreyer orderings (although they aren't used here). And then I improved clarity of some comments.

Note that basic arithmetic is still faster than with Letterplace (which could be because of a memory leak in Letterplace that meanwhile is fixed upstream):

sage: L.<x,y,z> = FreeAlgebra(GF(25,'t'), implementation='letterplace')
sage: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 12.06 times longer than the fastest. This could mean that an intermediate result is being cached
1000 loops, best of 3: 394 µs per loop
sage: %timeit p = x^4+x*y*x*z+2*z^2*x*y
1000 loops, best of 3: 395 µs per loop
sage: p = x^4+x*y*x*z+2*z^2*x*y
sage: %timeit q = p^7
The slowest run took 4.78 times longer than the fastest. This could mean that an intermediate result is being cached
100 loops, best of 3: 2.27 ms per loop
sage: %timeit q = p^7
100 loops, best of 3: 2.39 ms per loop


versus

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: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 24.51 times longer than the fastest. This could mean that an intermediate result is being cached
10000 loops, best of 3: 20.7 µs per loop
sage: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 4.05 times longer than the fastest. This could mean that an intermediate result is being cached
10000 loops, best of 3: 21.2 µ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: 1.69 ms per loop


Tests pass and it still needs review!

### comment:63 follow-up: ↓ 65 Changed 7 years ago by chapoton

Is the change to module_list.py really needed ?

### comment:64 Changed 7 years ago by git

• Commit changed from 10c8167050b2565b6b8d1678ed17eb927a1d4d1a to e2a27ccfe9f87667d9264e194414b3e75f8e4f93

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

 ​e2a27cc Revert unnecessary change to module_list.py

### comment:65 in reply to: ↑ 63 Changed 7 years ago by SimonKing

Is the change to module_list.py really needed ?

You are right, it isn't.

### comment:66 follow-ups: ↓ 68 ↓ 74 Changed 7 years ago by chapoton

Hello,

I am not able to do a serious technical review (cython..), but I am happy enough with what I understand, and the bot gives a green light. So I am ready to give a positive review, if you are satisfied with this rather superficial check.

One minor point: I would prefer to have a bigger example for the latex method, where \cdot appears.

### comment:67 Changed 7 years ago by git

• Commit changed from e2a27ccfe9f87667d9264e194414b3e75f8e4f93 to 63f08e1a962acbe620147135c4581ed52f86db2f

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

 ​63f08e1 Add a stronger test to the _latex_ method

### comment:68 in reply to: ↑ 66 Changed 7 years ago by SimonKing

One minor point: I would prefer to have a bigger example for the latex method, where \cdot appears.

Good idea. I think the additional test is better, and one can also check manually that the product is correctly computed.

Perhaps the release manager can decide if your non-technical review is enough?

### comment:69 follow-up: ↓ 70 Changed 7 years ago by chapoton

Some more comments, review in progress:

1) Why is there no "except -1" at the end of this line:

+    cpdef tuple complement(self, QuiverPath subpath)
cpdef bint has_subpath(self, QuiverPath subpath) except -1


of "src/sage/quivers/paths.pxd" ?

2) According to the new code in src/sage/quivers/algebra.py, it is now possible, if A is a path algebra, to call A(a dictionary here). Is this tested ?

### comment:70 in reply to: ↑ 69 Changed 7 years ago by SimonKing

Some more comments, review in progress:

1) Why is there no "except -1" at the end of this line:

+    cpdef tuple complement(self, QuiverPath subpath)
cpdef bint has_subpath(self, QuiverPath subpath) except -1


of "src/sage/quivers/paths.pxd" ?

Which line do you mean? cpdef tuple complement...? Here, the return type is a python object (tuple), which means that you can not set (and also do not need to set) an except value.

2) According to the new code in src/sage/quivers/algebra.py, it is now possible, if A is a path algebra, to call A(a dictionary here). Is this tested ?

I'll have a look. If it is possible, then it should be tested. Right now, I try to speed-up a couple of things.

### comment:71 Changed 7 years ago by chapoton

Ok.

3) Please remove the final dot in the title (first line) of algebra_elements.pyx

and 2) is indeed tested here:

sage: P(p.monomial_coefficients()) == p

Last edited 7 years ago by chapoton (previous) (diff)

### comment:72 Changed 7 years ago by chapoton

4) "degree_on_basis" has disappeared, and now

sage: A = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup().algebra(ZZ)
sage: A.inject_variables()
Defining e_0, e_1, e_2, a, b, c, d, e, f
sage: X = a+2*b+3*c+5*e_0+3*e_2
sage: X.homogeneous_component(0)


### comment:73 Changed 7 years ago by chapoton

5)

division does not change the base_ring if needed:

sage: X/4
5/4*e_0 + 1/4*a + 1/2*b + 3/4*c + 3/4*e_2
sage: (X/4).parent()
Path algebra of Looped multi-digraph on 3 vertices over Integer Ring


### comment:74 in reply to: ↑ 66 Changed 7 years ago by jdemeyer

Hello,

I am not able to do a serious technical review (cython..)

If needed, I might be able to do a pure technical review (cython..)

### comment:75 follow-up: ↓ 79 Changed 7 years ago by jdemeyer

I do not see the need for biseq_realloc_concat, why not simply use biseq_dealloc followed by biseq_init_concat?

A possible use case of biseq_realloc_concat might be if the result is one of the inputs, but that doesn't seem to be your use case.

### comment:76 follow-up: ↓ 78 Changed 7 years ago by jdemeyer

You seem to use int in a lot of places which usually bounds the value to 2^31 - 1. This can artificially put limits on what your objects are used for. For example, I would use a larger type for a reference counter.

I understand that you don't want to change all your code for this, so consider this more "general advice" rather than a needs_work issue.

### comment:77 Changed 7 years ago by jdemeyer

Code like this

cdef path_mon_t *out = <path_mon_t*>sage_malloc(sizeof(path_mon_t))
if out==NULL:
raise MemoryError("Out of memory while allocating a path term")


can be replaced by

cdef path_mon_t *out = <path_mon_t*>check_malloc(sizeof(path_mon_t))


### comment:78 in reply to: ↑ 76 ; follow-up: ↓ 80 Changed 7 years ago by SimonKing

You seem to use int in a lot of places which usually bounds the value to 2^31 - 1. This can artificially put limits on what your objects are used for. For example, I would use a larger type for a reference counter.

I understand that you don't want to change all your code for this, so consider this more "general advice" rather than a needs_work issue.

I don't think it would be difficult to change.

What is the general advice? What integer types should be used for what purpose? I still do not have a clear picture of int, long, size_t, mp_size_t, etc.

### comment:79 in reply to: ↑ 75 ; follow-up: ↓ 81 Changed 7 years ago by SimonKing

I do not see the need for biseq_realloc_concat, why not simply use biseq_dealloc followed by biseq_init_concat?

Premature optimisation is the root of all evil, I know... That's to say, I expected that realloc is faster than dealloc followed by alloc.

A possible use case of biseq_realloc_concat might be if the result is one of the inputs, but that doesn't seem to be your use case.

The only place where I use biseq_realloc_concat is in the kill-list (should actually be called a free-list): If I have a dead term in the pool that I want to revive, then its monomial is still allocated. If this monomial has a refcount > 1 then it is used in a second term, and thus I am not allowed to touch it, and need to allocate a totally new monomial. But otherwise, I can re-use the monomial. And re-using, I thought, means re-alloc...

### comment:80 in reply to: ↑ 78 ; follow-up: ↓ 101 Changed 7 years ago by jdemeyer

What is the general advice? What integer types should be used for what purpose? I still do not have a clear picture of int, long, size_t, mp_size_t, etc.

1. Most importantly, be consistent: try not to assign a long to an int, make sure that loop counters and loop bounds have the same type.
2. In most cases, long is a good type to use.
3. Use int only if you know for theoretical reasons that the value must be small (say, at most 2^31 - 1). There is no theoretical reason why a reference counter cannot be 2^32, so int is not the right type for that. An int is usually good for booleans or for enumerating several possibilities.
4. Use Py_ssize_t for lengths and sizes of Python objects.
5. Use size_t for lengths and sizes of non-Python objects and of memory chunks. Note that this is an unsigned type.

### comment:81 in reply to: ↑ 79 ; follow-up: ↓ 83 Changed 7 years ago by jdemeyer

That's to say, I expected that realloc is faster than dealloc followed by alloc.

I would actually expect the opposite. Realloc might need to copy data, a dealloc followed by an alloc not.

### comment:82 Changed 7 years ago by jdemeyer

Similarly, this should be biseq_dealloc + biseq_init_copy:

bitset_realloc(out.path.data, Mon.data.size)
bitset_copy(out.path.data, Mon.data)
out.path.length = Mon.length
out.path.itembitsize = Mon.itembitsize


### comment:83 in reply to: ↑ 81 Changed 7 years ago by SimonKing

That's to say, I expected that realloc is faster than dealloc followed by alloc.

I would actually expect the opposite. Realloc might need to copy data, a dealloc followed by an alloc not.

Ouch, you are right. OK, this needs to change.

By the way, do you have an idea how to explain the timings (with cProfile) that I posted today on sage-devel? The cumulated times do not seem to match.

### comment:84 follow-up: ↓ 87 Changed 7 years ago by jdemeyer

Just a question: do you expect the structs path_mon_t, path_term_t and path_poly_t to be used as basic building blocks for other classes?

I'm asking this because I am wondering why you don't simply make this into Cython extension types, especially given that you need manual reference counting using the ref member of path_mon_t and for PyObject *coef. With Cython/Python, you get both of these for free.

Last edited 7 years ago by jdemeyer (previous) (diff)

### comment:85 Changed 7 years ago by jdemeyer

This line fails the "be consistent" advice, since biseq_contains returns mp_size_t, which is a signed type:

cdef size_t i = biseq_contains(self._path, subpath._path, 0)


### comment:86 Changed 7 years ago by jdemeyer

The __cmp__ and __richcmp__ boilerplate is no longer needed and can simply be removed (just move the doctests to the single-underscore methods).

### comment:87 in reply to: ↑ 84 Changed 7 years ago by SimonKing

Just a question: do you expect the structs path_mon_t, path_term_t and path_poly_t to be used as basic building blocks for other classes?

There will also be geobuckets, for Gröbner basis computations.

At some point (long time ago, maybe 2 years) I did some tests with Cython classes. Actually in two versions: terms being instances of a Cython class and providing an attribute .nxt pointing to the next term (i.e., a linked list similar to what is done here), and alternatively terms a Cython class and polynomials having an attribute of type list, storing a polynomial not as a linked list but as a Python list of terms.

Both was slower than the code here. I don't recall how much, but probably it was rather significant. Otherwise, I would not have chosen the current boilerplate approach.

### comment:88 follow-up: ↓ 92 Changed 7 years ago by jdemeyer

cmp(M2.path.length-M2.s_len, M1.path.length-M1.s_len)


This converts both arguments from a C integer to a Python int and then calls the Python function cmp().

### comment:89 follow-up: ↓ 105 Changed 7 years ago by jdemeyer

Can you document the C structures in the .pxd file a bit more? What I'm missing is basic "what does this struct do" documentation.

### comment:90 Changed 7 years ago by jdemeyer

Replace

Py_DECREF(<object>(T.coef))


by

Py_XDECREF(T.coef)


and

Py_INCREF(<object>T.coef)


by

Py_XINCREF(T.coef)


The reason is that Cython already changes the refcount in the cast to <object>. The X versions do not need such a cast.

### comment:91 follow-up: ↓ 102 Changed 7 years ago by jdemeyer

And remember to test this ticket with #18927.

### comment:92 in reply to: ↑ 88 Changed 7 years ago by SimonKing

cmp(M2.path.length-M2.s_len, M1.path.length-M1.s_len)


This converts both arguments from a C integer to a Python int and then calls the Python function cmp().

Yep. This will be in a commit that I am currently preparing, but for which I need more insight about profiling (an explanation why the cumulative times do not add up).

### comment:93 follow-up: ↓ 98 Changed 7 years ago by jdemeyer

When writing Cython code, you should use signal handling in the appropriate places to enable CTRL-C. The easiest is simply to put a sig_check() inside loops which can take a long time, i.e. replace

while ...
...


by

while ...
sig_check()
...


in the low-level loops.

### comment:94 follow-up: ↓ 99 Changed 7 years ago by jdemeyer

This

predec(kill_list.nterms)


is just an obscure way of writing

kill_list.nterms -= 1


so why not use the latter?

### comment:95 Changed 7 years ago by jdemeyer

In general, I would avoid predec() in Cython code unless it's needed for C++ classes (which isn't the case here).

### comment:96 follow-up: ↓ 100 Changed 7 years ago by jdemeyer

This might be a matter of style, but I think you use inline really a lot. Remember that function calls are not that expensive but that moving bytes from RAM to CPU is expensive. So, if you inline too much such that the code of a function gets really large (in particular, if it no longer fits into the CPU cache), then you're certainly losing performance with inline. I'm not saying that this is the case here, but it's a pitfall to look out for.

### comment:97 Changed 7 years ago by jdemeyer

That's it for now. I didn't really read the code, just skimmed over it.

### comment:98 in reply to: ↑ 93 Changed 7 years ago by SimonKing

When writing Cython code, you should use signal handling in the appropriate places to enable CTRL-C. The easiest is simply to put a sig_check() inside loops which can take a long time, i.e. replace

while ...
...


by

while ...
sig_check()
...


in the low-level loops.

I did read what the reference manual said about sig_check versus sig_on/_off, but I admit that I did not fully understand it. On the one hand, I got the impression that sig_check is faster and can totally replace sig_on/_off, on the other hand it was said to put sig_on/_off around potentially expensive calls to C-functions.

### comment:99 in reply to: ↑ 94 Changed 7 years ago by SimonKing

This

predec(kill_list.nterms)


is just an obscure way of writing

kill_list.nterms -= 1


so why not use the latter?

I started using it in lines such as "some_function(preinc(n))", which I thought was slightly more efficient than doing "n+=1; some_function(n)". But perhaps I could be mistaken about the performance. And in any case, I guess you are right, I was over-generalising.

### comment:100 in reply to: ↑ 96 Changed 7 years ago by SimonKing

This might be a matter of style, but I think you use inline really a lot. Remember that function calls are not that expensive but that moving bytes from RAM to CPU is expensive. So, if you inline too much such that the code of a function gets really large (in particular, if it no longer fits into the CPU cache), then you're certainly losing performance with inline. I'm not saying that this is the case here, but it's a pitfall to look out for.

Probably that's another misconception that I have regarding of what is happening in a computer...

OK, I'll remove the "inline" from any function that is more than three lines. Do you think that's a reasonable rule of thumb?

### comment:101 in reply to: ↑ 80 Changed 7 years ago by SimonKing

1. Most importantly, be consistent: try not to assign a long to an int, make sure that loop counters and loop bounds have the same type.

In order to be consistent, I will change the types referring to the degree of a monomial to mp_size_t. Rationale: The degree of a monomial is the length of a path, and the length of a path currently IS mp_size_t.

Unfortunately, this rationale leads me to be inconsistent in another regards:

A monomial is of the form a*I*b, where I is a generator of a free two-sided module, a is the left cofactor, and b is the right cofactor (both cofactors are paths); OR ALTERNATIVELY, it is simply of the form a, making it an element of the path algebra and not of a module over the path algebra.

The current encoding is: If .mid==-1 then we have an element of the path algebra. Otherwise, .mid is equal to the length of the path a.

Hence, by the above rationale, .mid should be mp_size_t. But by the encoding, it must be able to assume the value -1.

Perhaps it would be better to change the encoding: .mid should be replaced by .l_length, which is mp_size_t and denotes the length of the left cofactor. Instead, I should either introduce a new component, say bint in_algebra, or I should change .pos to long, saying that if .pos is negative then the monomial belongs to a path algebra (not to a proper module over a path algebra), and if it is non-negative then .pos denotes the summand of a free module in which the monomial lives. The latter is the current meaning of .pos.

What do you think is better? I think using .pos makes sense: It tells us where the monomial lives, either in a summand of a free module, or in a path algebra.

Note that all the encoding only becomes relevant in the F5 algorithm for modules over path algebras that I am currently preparing.

### comment:102 in reply to: ↑ 91 Changed 7 years ago by SimonKing

And remember to test this ticket with #18927.

How to? I am using 6.9.beta3. Is #18927 in it? If it isn't, what to do? Do I need sage -ba?

### comment:103 Changed 7 years ago by git

• Commit changed from 63f08e1a962acbe620147135c4581ed52f86db2f to 35b167ef06d9862c00593b22dc0c06a7629396a6

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

 ​ffb5e0d Do not mix unsigned int with mp_size_t ​f823fe8 Some speed-ups ​35b167e Change Cython coding style according to reviewer's remarks

### comment:104 Changed 7 years ago by SimonKing

I think I have now addressed all remarks by Jeroen, with only exception the sig_check/on/off issue. Thanks a lot, Jeroen!

Actually the timings from comment:62 have now improved, in particular for multiplication, which involves a lot of allocation (and perhaps reallocation) and comparison of terms:

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: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 24.13 times longer than the fastest. This could mean that an intermediate result is being cached
10000 loops, best of 3: 20.2 µs per loop
## Was: 20.7 µs
sage: %timeit p = x^4+x*y*x*z+2*z^2*x*y
100000 loops, best of 3: 18.9 µs per loop
## Was: 21.2 µs
sage: p = x^4+x*y*x*z+2*z^2*x*y
sage: %timeit q = p^7
1000 loops, best of 3: 1.06 ms per loop
## Was: 1.69 ms


I'll take care of sig_check later, and also of Frédéric's advices.

### comment:105 in reply to: ↑ 89 Changed 7 years ago by SimonKing

Can you document the C structures in the .pxd file a bit more? What I'm missing is basic "what does this struct do" documentation.

I forgot to address this one. On my to-do list...

### comment:106 Changed 7 years ago by git

• Commit changed from 35b167ef06d9862c00593b22dc0c06a7629396a6 to 203d4dee99418489fadb56164eaec90e749b9f16

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

 ​203d4de Elaborate on the type definitions in the .pxd file. Remove some debugging code

### comment:107 Changed 7 years ago by SimonKing

I have yet another question about sig_on/off/check.

Assume that f is a cython function that calls another cython function g in a tight loop. First of all, is it correct that there is no point in using sig_... if there is no "except" value given for f and g?

Now assume that both f and g are declared with an except value (or return a Python object). Should one have

cdef int g(...) except -1:
<do something>
return ...
cdef int f(...) except -1:
while ...:
g(...)


or

cdef int g(...) except -1:
sig_check()
<do something>
return ...
cdef int f(...) except -1:
while ...:
g(...)


or

cdef int g(...) except -1:
<do something>
return ...
cdef int f(...) except -1:
while ...:
sig_check()
g(...)


or

cdef int g(...) except -1:
sig_check()
<do something>
return ...
cdef int f(...) except -1:
while ...:
sig_check()
g(...)


? What are the differences?

### comment:108 Changed 7 years ago by SimonKing

I have tested that the following code can be interrupted:

sage: cython("""
....: include "sage/ext/interrupt.pxi"
....: cdef int test1(int a) except -1:
....:     cdef int i
....:     for i in range(a):
....:         sig_check()
....:         x = a*a
....: cpdef int test2(int b) except -1:
....:     while 1:
....:         test1(b*b)
....: """)
sage: test2(5)
^C
Traceback (most recent call last):
...
KeyboardInterrupt:


So, I will put sig_check/on/off mainly into "small" functions (that of course need to declare an except value) that are frequently called, and will not put it into the caller functions (unless of course there is further code in the caller function that can't be interrupted).

### comment:109 follow-up: ↓ 111 Changed 7 years ago by jdemeyer

Just some quick comments, I don't have much time.

it was said to put sig_on/_off around potentially expensive calls to C-functions.

Here, I really meant C functions in an external library that you don't have control over, for pure Cython code, you usually don't need sig_on/sig_off. Does this clarify things?

OK, I'll remove the "inline" from any function that is more than three lines. Do you think that's a reasonable rule of thumb?

I think it's difficult to give a rule of thumb. It mostly depends on what the function does. I think a better rule of thumb is: functions which are simple and don't take much time. If you really want to be sure: profile!

Hence, by the above rationale, .mid should be mp_size_t. But by the encoding, it must be able to assume the value -1.

These conditions do not contradict each other (mp_size_t is signed), so there is no problem here.

Do I need sage -ba?

You should never need sage -ba. Anytime you do need it, that's a bug in the build system. Just use make.

To test with #18927, I'd make a new private branch where you merge the branch of this ticket and the branch of #18927.

For sig_check, you just have to ensure that sig_check is called often enough in every possible code path. I.e. it should not be possible that your code runs a whole second without ever calling sig_check. So, as a rule of thumb: put sig_check inside every loop, which corresponds to your third proposal.

### comment:110 Changed 7 years ago by git

• Commit changed from 203d4dee99418489fadb56164eaec90e749b9f16 to 3ca283e5cfec8fc94087eae2f579668071ae08dd

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

 ​3ca283e Make various boilerplate functions interruptible. Fix parent of divided path algebra elements

### comment:111 in reply to: ↑ 109 Changed 7 years ago by SimonKing

In the new commit, I have tried to address the sig_on/off/check issue. I took care to make many boilerplate functions (some of them in sage.data_structures) interruptible. Then, when using these functions in higher level functions, it is not needed to put sig_check again. However, to be on the safe side, often I put additional sig_checks at the beginning of loops.

I elaborate a lot more on what each boilerplate function does, by putting comments in front of each function.

I fixed the problem with the parent of "X/4" that Frédéric found in comment:73. Yet to be fixed is the problem with degree_on_basis.

I checked that the timings are still as good as they used to be (hence, all the signal checking did not make it slower).

I also checked 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: p = x^4+x*y*x*z+2*z^2*x*y
sage: while 1:
....:     p = p*p
....:


is interruptible. Also I could interrupt determining the string representation of a large element.

And of course I checked that all tests in sage.quivers and also in sage.data_structures pass.

OK, I'll remove the "inline" from any function that is more than three lines. Do you think that's a reasonable rule of thumb?

I think it's difficult to give a rule of thumb. It mostly depends on what the function does. I think a better rule of thumb is: functions which are simple and don't take much time. If you really want to be sure: profile!

Well, according to my small benchmark, multiplication became 30% faster after removing the excessive misuse of "inline". So, again thank you for that hint.

Hence, by the above rationale, .mid should be mp_size_t. But by the encoding, it must be able to assume the value -1.

These conditions do not contradict each other (mp_size_t is signed), so there is no problem here.

OK. But nonetheless, I believe the encoding should better be in .pos, not in .l_len (formerly .mid), since ultimately what we are encoding is the "position" of the monomial in a module/path algebra.

To test with #18927, I'd make a new private branch where you merge the branch of this ticket and the branch of #18927.

OK, next on my to-do list.

For sig_check, you just have to ensure that sig_check is called often enough in every possible code path. I.e. it should not be possible that your code runs a whole second without ever calling sig_check. So, as a rule of thumb: put sig_check inside every loop, which corresponds to your third proposal.

I think I have put sig_check in all code paths, because it is in all (or at least most) interruptible boilerplate functions, and additionally is used in loops of higher level functions.

### comment:112 Changed 7 years ago by SimonKing

Sigh.

king@linux-va3e:~/Sage/git/sage> git trac pull 18927
remote branch: b6e57c46b714b1eb811a3a62fccfc37b6b5ff2ff
Traceback (most recent call last):
File "/home/king/bin/git-trac", line 18, in <module>
cmdline.launch()
File "/home/king/Sage/git/git-trac-command/git_trac/cmdline.py", line 213, in launch
app.pull(args.ticket_or_branch)
File "/home/king/Sage/git/git-trac-command/git_trac/app.py", line 90, in pull
self.repo.pull(remote)
File "/home/king/Sage/git/git-trac-command/git_trac/git_repository.py", line 176, in pull
self.git.echo.fetch('trac', remote_branch)
File "/home/king/Sage/git/git-trac-command/git_trac/git_interface.py", line 341, in meth
return self.execute(git_cmd, *args, **kwds)
File "/home/king/Sage/git/git-trac-command/git_trac/git_interface.py", line 98, in execute
popen_stderr=subprocess.PIPE)
File "/home/king/Sage/git/git-trac-command/git_trac/git_interface.py", line 263, in _run
raise GitError(result)
git_trac.git_error.GitError: git returned with non-zero exit code (128) when executing "git fetch trac b6e57c46b714b1eb811a3a62fccfc37b6b5ff2ff"
STDERR: error: no such remote ref b6e57c46b714b1eb811a3a62fccfc37b6b5ff2ff


So, how to test with #18972?

### comment:113 follow-up: ↓ 114 Changed 7 years ago by tscrim

Try

git pull origin u/vbraun/upgrade_cython_to_0_23


### comment:114 in reply to: ↑ 113 Changed 7 years ago by SimonKing

Try

git pull origin u/vbraun/upgrade_cython_to_0_23


Thank you, that worked.

Or it didn't:

File "src/sage/quivers/algebra.py", line 462, in sage.quivers.algebra.PathAlgebra._latex_monomial
Failed example:
latex(X)  # indirect doctest
Exception raised:
Traceback (most recent call last):
File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
exec(compiled, globs)
File "<doctest sage.quivers.algebra.PathAlgebra._latex_monomial[2]>", line 1, in <module>
latex(X)  # indirect doctest
File "/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/misc/latex.py", line 920, in __call__
return LatexExpr(x._latex_())
File "sage/quivers/algebra_elements.pyx", line 294, in sage.quivers.algebra_elements.PathAlgebraElement._latex_ (build/cythonized/sage/quivers/algebra_elements.c:22337)
latex_scalar_mult = None,
TypeError: function() got multiple values for keyword argument 'latex_scalar_mult'


WTF? Did #18972 change more than just the Cython version??

### comment:115 Changed 7 years ago by SimonKing

Argh. Cython is absolutely right to complain about it:

    def _latey_(...):
return repr_lincomb(self._sorted_items_for_printing(),
scalar_mult       = self.parent()._print_options['scalar_mult'],
latex_scalar_mult = self.parent()._print_options['latex_scalar_mult'],
latex_scalar_mult = None,
repr_monomial = self._parent._latex_monomial,
is_latex=True, strip_one = True)


OK, to be fixed.

### comment:116 Changed 7 years ago by SimonKing

Good, with the obvious change I get

king@linux-va3e:~/Sage/git/sage> ./sage -t src/sage/quivers/
...
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 17.2 seconds
cpu time: 13.6 seconds
cumulative wall time: 16.0 seconds


and

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: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 62.64 times longer than the fastest. This could mean that an intermediate result is being cached
100000 loops, best of 3: 17.2 µs per loop
sage: %timeit p = x^4+x*y*x*z+2*z^2*x*y
The slowest run took 4.50 times longer than the fastest. This could mean that an intermediate result is being cached
100000 loops, best of 3: 17.3 µ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: 1.11 ms per loop
sage: %timeit q = p^7
1000 loops, best of 3: 1.09 ms per loop


which means that the timings didn't change much.

So, next I will fix the latex issue and address Frédéric's comments, and then it can hopefully be finished.

### comment:117 Changed 7 years ago by SimonKing

• comment:66: \cdot example is added
• comment:69: An except value can only be set on a cdef function that does NOT return a python object. Hence, it is for functions that returns a pointer, an int, a bint, and so on. As you have found yourself, calling a path algebra with a dictionary to create an element is indeed tested.
• comment:71: The dot is removed.
• comment:73: The quotient of a path algebra element with a scalar now has potentially a new parent, and this is tested.

Still missing:

• comment:72: Sigh. Why is there no default implementation of degree_on_basis that tries if the basis element has a degree method, and returns the result??? With such a default it would work. Fixing it in the next commit.

### comment:118 Changed 7 years ago by SimonKing

Now I am really upset.

I implemented a degree_on_basis() method returning the degree of the basis element in question. But then:

sage: X.homogeneous_component(0)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-5-56d3ca179acf> in <module>()
----> 1 X.homogeneous_component(Integer(0))

161             degree_on_basis = self.parent().degree_on_basis
162             return self.parent().sum_of_terms((i, c)
--> 163                                               for (i, c) in self
164                                               if degree_on_basis(i) == n)
165

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/free_module.py in sum_of_terms(self, terms, distinct)
2001         if distinct:
2002             return self._from_dict(dict(terms))
-> 2003         return self.sum(self.term(index, coeff) for (index, coeff) in terms)
2004
2005     def monomial_or_zero_if_none(self, i):

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/free_module.py in sum(self, iter_of_elements)
1841         """
1842
-> 1843         D = dict_addition( element._monomial_coefficients for element in iter_of_elements )
1844         return self._from_dict( D, remove_zeros=False )
1845

19 from cpython cimport PyDict_Copy
20
22     r"""
23     Returns the pointwise addition of dictionaries with coefficients.

44
45     D = {}
---> 46     for D_tmp in dict_iter:
47         if D == {}:
48             D = PyDict_Copy( D_tmp )

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/combinat/free_module.py in <genexpr>((element,))
1841         """
1842
-> 1843         D = dict_addition( element._monomial_coefficients for element in iter_of_elements )
1844         return self._from_dict( D, remove_zeros=False )
1845

/home/king/Sage/git/sage/src/sage/structure/element.pyx in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4680)()
416             dummy_error_message.name = name
417             raise dummy_attribute_error
--> 418         return getattr_from_other_class(self, P._abstract_element_class, name)
419
420     def __dir__(self):

/home/king/Sage/git/sage/src/sage/structure/misc.pyx in sage.structure.misc.getattr_from_other_class (build/cythonized/sage/structure/misc.c:1670)()
257         dummy_error_message.cls = type(self)
258         dummy_error_message.name = name
--> 259         raise dummy_attribute_error
260     if isinstance(attribute, methodwrapper):
261         dummy_error_message.cls = type(self)

AttributeError: 'sage.quivers.algebra_elements.PathAlgebraElement' object has no attribute '_monomial_coefficients'


Why does CombinatorialFreeModule expect that elements have a public attribute _monomial_coefficients? That's an implementation detail that a generic implementation must not rely on. It can certainly assume that there is X.monomial_coefficients() as a method---but not a private (i.e. underscore) attribute!

I am not going to fix that bug in CombinatorialFreeModule---that's not really my world, as I prefer the "classical" way of implementing algebraic structures.

As a work-around, I may override the .sum() method.

Hilarious.

### comment:120 Changed 7 years ago by SimonKing

That implementation detail is expected in further methods:

sage: from sage.misc.sageinspect import sage_getsource
sage: from inspect import ismethod
sage: def find_offenders(A):
....:     for a in dir(A):
....:         try:
....:             x = getattr(A,a)
....:         except AttributeError:
....:             print "Attribute",a,"is not an attribute"
....:         if not ismethod(x):
....:             continue
....:         try:
....:             s = sage_getsource(x)
....:         except:
....:             print "Source code of attribute",a,"not available"
....:         if "._monomial_coeff" in s:
....:             print "Attribute",a,"relies on an implementation detail"
....:
sage: A = DiGraph({0:{1:['a'], 2:['b']}, 1:{0:['c'], 1:['d']}, 2:{0:['e'],2:['f']}}).path_semigroup().algebra(ZZ)
sage: find_offenders(A)
Attribute _apply_module_endomorphism relies on an implementation detail
Attribute _apply_module_morphism relies on an implementation detail
Attribute _product_from_combinatorial_algebra_multiply relies on an implementation detail
Attribute linear_combination relies on an implementation detail


I think I'll ask sage-devel and sage-combinat about it. Apparently CombinatorialFreeModule makes specific assumptions on the implementation details of its element class.

### comment:121 Changed 7 years ago by git

• Commit changed from 3ca283e5cfec8fc94087eae2f579668071ae08dd to 0b9ecbc6c54d6a00f5d35cd9c2ce7ff00c9ab84c

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

 ​0b9ecbc Fix _latex_ method, override .sum() and implement .degree_on_basis()

### comment:122 Changed 7 years ago by SimonKing

Done.

I believe that the usage of Element._monmial_coefficients for methods of CombinatorialFreeModule should be replaced by Element.monomial_coefficients(), but that's of course not the job of this ticket.

I did not merge #18972 into the published branch, but I tested it in a private branch.

Anyway, I hope that now all objections of the reviewers are addressed...

### comment:123 follow-ups: ↓ 126 ↓ 127 ↓ 138 Changed 7 years ago by jdemeyer

Well, I didn't really mean that you should change the bitset/biseq functions. I think those are sufficiently low-level that the inline is probably justified where it was. I would also remove the signal handling from the bitset functions since they are very simple functions. For some functions, an additional overhead over just the sig_check() is that you're adding exception handling. Also, there is no reason to replace sig_on()/sig_off() with sig_check() in the biseq functions. The sig_on()/sig_off() are used correctly, so let them be.

In short, I would prefer to revert all changes to bitset/biseq.

### comment:124 follow-up: ↓ 125 Changed 7 years ago by jdemeyer

To clarify what I said about sig_check(), I prefer this style:

cdef int g(...) except -1:
<do something>
return ...
cdef int f(...) except -1:
while ...:
sig_check()
g(...)


I don't see the point of a function like

def foo():
sig_check()
...


In such a case, I would leave the signal handling to the caller of foo().

### comment:125 in reply to: ↑ 124 ; follow-up: ↓ 130 Changed 7 years ago by SimonKing

I don't see the point of a function like

def foo():
sig_check()
...


In such a case, I would leave the signal handling to the caller of foo().

The advantage (from my perspective) is that one only puts sig_check() into one function foo(), whereas you suggest to put it into all functions that call foo() (which is easy to forget).

### comment:126 in reply to: ↑ 123 ; follow-up: ↓ 128 Changed 7 years ago by SimonKing

In short, I would prefer to revert all changes to bitset/biseq.

A technical question: What git command can I use to change a single file by reverting a specific commit?

### comment:127 in reply to: ↑ 123 ; follow-up: ↓ 129 Changed 7 years ago by SimonKing

Well, I didn't really mean that you should change the bitset/biseq functions. I think those are sufficiently low-level that the inline is probably justified where it was.

I tried to remove it only for functions that seemed sufficiently complicated to me.

For some functions, an additional overhead over just the sig_check() is that you're adding exception handling.

Right, exception handling adds an overhead. Perhaps one could say that I should add exception handling and sig_check() in functions that are sufficiently complicated (and contain a loop), so that there is the possibility that they run long enough to catch a Ctrl-C?

Also, there is no reason to replace sig_on()/sig_off() with sig_check() in the biseq functions. The sig_on()/sig_off() are used correctly, so let them be.

Is it not the case that sig_check adds less overhead than sig_on/off? At least this is how I understood what's written in the developer guide. The developer guide seems to suggest to use them for different purposes.

### comment:128 in reply to: ↑ 126 Changed 7 years ago by tscrim

In short, I would prefer to revert all changes to bitset/biseq.

A technical question: What git command can I use to change a single file by reverting a specific commit?

IIRC, is is

git checkout <commit> <file>


### comment:129 in reply to: ↑ 127 ; follow-up: ↓ 131 Changed 7 years ago by jdemeyer

Is it not the case that sig_check adds less overhead than sig_on/off?

It depends. With sig_check() in a loop, the overhead is O(n) where n is the number of iterations. With sig_on()/sig_off(), the overhead is O(1). So, for few loop iterations, sig_check() is faster. For many loop iterations, sig_on()/sig_off() is faster.

But a more philosophical reason to prefer sig_on()/sig_off() for the bitset/biseq functions is that those loops really act like not-implemented mpn_ functions. Where we can use an mpn_ function, we do that using sig_on()/sig_off(). Where we cannot use an mpn_ function, we write a manual loop instead.

### comment:130 in reply to: ↑ 125 Changed 7 years ago by jdemeyer

The advantage (from my perspective) is that one only puts sig_check() into one function foo(), whereas you suggest to put it into all functions that call foo() (which is easy to forget).

The way I see it, you should put sig_check() where it is really needed. It is not needed in a simple function foo(), since that function is fast enough that we don't need to check for interrupts. It is the function calling foo() which might run a long time and needs to check for interrupts.

Also, imagine a situation like

def high_level_function(L):
for x in L:
foo(x)
bar(x)
baz(x)


Here, you would put just one sig_check() in every iteration. If you add interrupt checking to foo, bar and baz, you have 3 interrupt checks per iteration which is less efficient. Similarly, the high-level function might choose to use sig_on()/sig_off() instead of sig_check().

### comment:131 in reply to: ↑ 129 ; follow-up: ↓ 132 Changed 7 years ago by SimonKing

But a more philosophical reason to prefer sig_on()/sig_off() for the bitset/biseq functions is that those loops really act like not-implemented mpn_ functions. Where we can use an mpn_ function, we do that using sig_on()/sig_off(). Where we cannot use an mpn_ function, we write a manual loop instead.

And we used it for mpn_, because sig_on/off can catch more errors (RuntimeError etc) than only a KeyboardInterrupt, right?

### comment:132 in reply to: ↑ 131 ; follow-up: ↓ 134 Changed 7 years ago by jdemeyer

And we used it for mpn_, because sig_on/off can catch more errors (RuntimeError etc) than only a KeyboardInterrupt, right?

More importantly, when using mpn_ functions, there simply is no loop where we can put sig_check(). (Technically, there is a loop in the MPIR sources, but we don't want to change those)

### comment:133 Changed 7 years ago by SimonKing

Concerning "inline", I read in several sources that inline should be done on SMALL functions that are called OFTEN.

But I am not sure what is small. I guess what counts here is the size of the C-code generated by Cython. For example, I removed the "inline" from bitset_init, because I expected that the error handling bloats the C-code, and because I thought that bitset_init is called less often than bitset manipulation functions. The C-code is

static int __pyx_f_4sage_15data_structures_6bitset_bitset_init(struct __pyx_t_4sage_15data_structures_6bitset_bitset_s *__pyx_v_bits, mp_bitcnt_t __pyx_v_size) {
int __pyx_r;
__Pyx_RefNannyDeclarations
int __pyx_t_1;
PyObject *__pyx_t_2 = NULL;
int __pyx_lineno = 0;
const char *__pyx_filename = NULL;
int __pyx_clineno = 0;
__Pyx_RefNannySetupContext("bitset_init", 0);
__pyx_t_1 = ((__pyx_v_size <= 0) != 0);
if (__pyx_t_1) {
__pyx_t_2 = __Pyx_PyObject_Call(__pyx_builtin_ValueError, __pyx_tuple_, NULL); if (unlikely(!__pyx_t_2)) {__pyx_filename = __pyx_f[0]; __pyx_lineno = 79; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
__Pyx_GOTREF(__pyx_t_2);
__Pyx_Raise(__pyx_t_2, 0, 0, 0);
__Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;
{__pyx_filename = __pyx_f[0]; __pyx_lineno = 79; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}
__pyx_v_bits->size = __pyx_v_size;
__pyx_v_bits->limbs = (((__pyx_v_size - 1) / (8 * (sizeof(mp_limb_t)))) + 1);
__pyx_v_bits->bits = ((mp_limb_t *)sage_calloc(__pyx_v_bits->limbs, (sizeof(mp_limb_t))));
__pyx_t_1 = ((__pyx_v_bits->bits == NULL) != 0);
if (__pyx_t_1) {
PyErr_NoMemory(); {__pyx_filename = __pyx_f[0]; __pyx_lineno = 85; __pyx_clineno = __LINE__; goto __pyx_L1_error;}
}


Is that "long"? I think so. Thus, better not inline.

### comment:134 in reply to: ↑ 132 ; follow-up: ↓ 135 Changed 7 years ago by SimonKing

More importantly, when using mpn_ functions, there simply is no loop where we can put sig_check(). (Technically, there is a loop in the MPIR sources, but we don't want to change those)

Ouch, that's another thing I forgot. If an error occurs, it will happen at the next sig_check() that is executed. But I've typically put sig_check() BEFORE a statement that may be interrupted, which makes it useless.

### comment:135 in reply to: ↑ 134 Changed 7 years ago by jdemeyer

If an error occurs, it will happen at the next sig_check() that is executed. But I've typically put sig_check() BEFORE a statement that may be interrupted, which makes it useless.

Just to be clear, with "error" in the above sentence, you really mean "interrupt", right?

It's not useless to put sig_check() in the beginning of a function. I think it does not matter much, since the code will eventually call sig_check() (in a different function) which will catch the interrupt.

### comment:136 Changed 7 years ago by SimonKing

By profiling, I see that a lot of time for doing multiplication is spent with deallocation:

       0   0.0%   7.2%       23  33.3% __pyx_f_4sage_7quivers_16algebra_elements_homog_poly_free
0   0.0%   7.2%       23  33.3% __pyx_f_4sage_7quivers_16algebra_elements_poly_dealloc (inline)
0   0.0%   7.2%       23  33.3% __pyx_f_4sage_7quivers_16algebra_elements_poly_free (inline)
0   0.0%   7.2%       23  33.3% __pyx_f_4sage_7quivers_16algebra_elements_term_free (inline)
0   0.0%   7.2%       23  33.3% __pyx_pf_4sage_7quivers_16algebra_elements_18PathAlgebraElement_2__dealloc__ (inline)
0   0.0%   7.2%       23  33.3% __pyx_pw_4sage_7quivers_16algebra_elements_18PathAlgebraElement_3__dealloc__ (inline)


So, I try to optimize the free list a little further.

### comment:137 Changed 7 years ago by git

• Commit changed from 0b9ecbc6c54d6a00f5d35cd9c2ce7ff00c9ab84c to 8d5d84687d0b60db3890a1f00b6b8acac3fc2c67

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

 ​8d5d846 Change inlining and signal handling; use freelist more efficiently

### comment:138 in reply to: ↑ 123 Changed 7 years ago by SimonKing

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

### comment:139 Changed 7 years ago by git

• Commit changed from 8d5d84687d0b60db3890a1f00b6b8acac3fc2c67 to 6ea8fa28882c544be8a368a7a9de89e60e3abc85

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

 ​6ea8fa2 Move monomials from heap to stack

### comment:140 follow-up: ↓ 141 Changed 7 years ago by SimonKing

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

### comment:141 in reply to: ↑ 140 Changed 7 years ago by SimonKing

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!

### comment:142 Changed 7 years ago by chapoton

• Milestone changed from sage-6.8 to sage-6.9

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

### comment:143 Changed 7 years ago by chapoton

• Status changed from needs_review to needs_work

There are two failing doctests, see patchbot report.

### comment:144 follow-up: ↓ 145 Changed 7 years ago by 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?

### comment:145 in reply to: ↑ 144 ; follow-up: ↓ 146 Changed 7 years ago by SimonKing

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?

### comment:146 in reply to: ↑ 145 ; follow-up: ↓ 147 Changed 7 years ago by tscrim

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.

### comment:147 in reply to: ↑ 146 ; follow-up: ↓ 150 Changed 7 years ago by SimonKing

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.

### comment:148 Changed 7 years ago by git

• Commit changed from 6ea8fa28882c544be8a368a7a9de89e60e3abc85 to 5b4ed6e69229b0809a1ab4ab63938569fed30b44

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

### comment:149 Changed 7 years ago by SimonKing

• Status changed from needs_work to needs_review

### comment:150 in reply to: ↑ 147 Changed 7 years ago by ncohen

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

### comment:151 Changed 7 years ago by chapoton

• Reviewers set to Frédéric Chapoton
• Status changed from needs_review to positive_review

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.

### comment:152 Changed 7 years ago by SimonKing

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!

### comment:153 Changed 7 years ago by vbraun

• Branch changed from public/17435/cythonise_path_algebra_elements to 5b4ed6e69229b0809a1ab4ab63938569fed30b44
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.