Opened 7 years ago
Closed 7 years ago
#17435 closed enhancement (fixed)
Cythonise path algebra elements
Reported by:  SimonKing  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  algebra  Keywords:  path algebra elements, days64.5, days65 
Cc:  nthiery, ncohen, egunawan  Merged in:  
Authors:  Simon King  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  5b4ed6e (Commits, GitHub, GitLab)  Commit:  5b4ed6e69229b0809a1ab4ab63938569fed30b44 
Dependencies:  #16453 #17526  Stopgaps: 
Description (last modified by )
#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 noncommutative F5 algorithm.
Change History (153)
comment:1 Changed 7 years ago by
 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
 Branch set to u/SimonKing/cythonise_path_algebra_elements
comment:3 Changed 7 years ago by
 Cc nthiery ncohen added
 Commit set to 431b7f9a770b9f5749ab094702b5cd275c13d0ab
comment:4 Changed 7 years ago by
 Status changed from new to needs_review
comment:5 Changed 7 years ago by
 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
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
 Status changed from needs_review to needs_work
comment:8 Changed 7 years ago by
 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
 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
PS: I wonder whether I should implement Karatsuba multiplication...
comment:11 Changed 7 years ago by
 Commit changed from 27b6ea96786c16b60489b46e7835c7af986c5584 to 6f07e2628edf7b21296a7ec020d8eca8d5139a8a
comment:12 Changed 7 years ago by
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 cprofiling, a small improvement was visible.
 In the multiplication of path algebra elements, I did far more term comparisons than needed. Actually (again by cprofiling) 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 gitrerere
enabled, the dependency merges cleanly into the branch. So, no merge commit this time...
comment:13 Changed 7 years ago by
 Commit changed from 6f07e2628edf7b21296a7ec020d8eca8d5139a8a to a961dfdfc400b165a05ba8f41a7efcf08c104c84
Branch pushed to git repo; I updated commit sha1. New commits:
a961dfd  Remove cprofiling

comment:14 followup: ↓ 15 Changed 7 years ago by
I forgot to remove some lines that enabled cprofiling (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
Replying to SimonKing:
I forgot to remove some lines that enabled cprofiling (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
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*yz+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
 Commit changed from a961dfdfc400b165a05ba8f41a7efcf08c104c84 to 3c8ae84ad88dfa8aab8b2c7a609aaa471a369fae
comment:18 Changed 7 years ago by
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
 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
According to Nathann's comment on sagedevel, 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 availablebut in fact this should be the next step. I plan to finish implementing a noncommutitive F5 algorithm, which can compute standard bases for one and twosided 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
 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 followup: ↓ 23 Changed 7 years ago by
Arrgh. I hate git's merge. And I hate the fact that I had to reinstall gitrerere on my laptop, since I had to reinstall my OS.
comment:23 in reply to: ↑ 22 Changed 7 years ago by
Replying to SimonKing:
And I hate the fact that I had to reinstall gitrerere on my laptop, since I had to reinstall 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
comment:25 Changed 7 years ago by
 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 followup: ↓ 27 Changed 7 years ago by
Argh. The merge has failed.
comment:27 in reply to: ↑ 26 Changed 7 years ago by
comment:28 Changed 7 years ago by
 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
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
It could be that I will rewrite everything from scratch. Reason: Volker gave some good arguments on sagedevel 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
 Branch changed from u/SimonKing/cythonise_path_algebra_elements to public/17435/cythonise_path_algebra_elements
comment:32 Changed 7 years ago by
 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

comment:33 Changed 7 years ago by
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
 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
 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
 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
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
 Status changed from needs_work to needs_review
 Work issues Fix segfaults deleted
comment:39 Changed 7 years ago by
 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
 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
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
 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
There was a conflict, hence, I think I had to push a merge commit...
comment:44 Changed 7 years ago by
 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
 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
 Status changed from needs_work to needs_review
 Work issues Resolve yet another merge conflict deleted
Conflict resolved, tests pass. Needs review.
comment:47 Changed 7 years ago by
 Keywords SageDays64.5 added
comment:48 Changed 7 years ago by
Remark: The failing test on some patchbot is in pexpect, hence, unrelated to this ticket.
comment:49 Changed 7 years ago by
 Keywords days64.5 days65 added; SageDays64.5 removed
comment:50 Changed 7 years ago by
 Cc egunawan added
 Milestone changed from sage6.5 to sage6.8
comment:51 Changed 7 years ago by
 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
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
 Status changed from needs_review to needs_work
 Work issues set to Yet another merge conflict
comment:54 Changed 7 years ago by
Are you kidding?? There really is another merge conflict? Unbelievable!
comment:55 Changed 7 years ago by
The conflict appears to be with #16064.
comment:56 Changed 7 years ago by
 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
 Status changed from needs_work to needs_review
 Work issues Yet another merge conflict deleted
Should be good now.
comment:58 followup: ↓ 59 Changed 7 years ago by
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
 Status changed from needs_review to needs_work
 Work issues set to Remove Py_NEW, prepare Schreyer orderings
Replying to SimonKing:
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 ith generator of a twosided 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
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
 Commit changed from 0e094053ea05d59197de9152b9206caa09c40cb8 to 10c8167050b2565b6b8d1678ed17eb927a1d4d1a
comment:62 Changed 7 years ago by
 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 followup: ↓ 65 Changed 7 years ago by
Is the change to module_list.py really needed ?
comment:64 Changed 7 years ago by
 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
comment:66 followups: ↓ 68 ↓ 74 Changed 7 years ago by
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
 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
Replying to chapoton:
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 nontechnical review is enough?
comment:69 followup: ↓ 70 Changed 7 years ago by
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
Replying to 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 1of "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 speedup a couple of things.
comment:71 Changed 7 years ago by
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
comment:72 Changed 7 years ago by
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)
complains about that.
comment:73 Changed 7 years ago by
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 multidigraph on 3 vertices over Integer Ring
comment:74 in reply to: ↑ 66 Changed 7 years ago by
Replying to chapoton:
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 followup: ↓ 79 Changed 7 years ago by
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 followup: ↓ 78 Changed 7 years ago by
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
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 ; followup: ↓ 80 Changed 7 years ago by
Replying to jdemeyer:
You seem to use
int
in a lot of places which usually bounds the value to2^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 ; followup: ↓ 81 Changed 7 years ago by
Replying to jdemeyer:
I do not see the need for
biseq_realloc_concat
, why not simply usebiseq_dealloc
followed bybiseq_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 killlist (should actually be called a freelist): 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 reuse the monomial. And reusing, I thought, means realloc...
comment:80 in reply to: ↑ 78 ; followup: ↓ 101 Changed 7 years ago by
Replying to SimonKing:
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.
OK, some general advice just from the top of my head:
 Most importantly, be consistent: try not to assign a
long
to anint
, make sure that loop counters and loop bounds have the same type.  In most cases,
long
is a good type to use.  Use
int
only if you know for theoretical reasons that the value must be small (say, at most2^31  1
). There is no theoretical reason why a reference counter cannot be2^32
, soint
is not the right type for that. Anint
is usually good for booleans or for enumerating several possibilities.  Use
Py_ssize_t
for lengths and sizes of Python objects.  Use
size_t
for lengths and sizes of nonPython objects and of memory chunks. Note that this is an unsigned type.
comment:81 in reply to: ↑ 79 ; followup: ↓ 83 Changed 7 years ago by
Replying to 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.
comment:82 Changed 7 years ago by
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 out.path.mask_item = Mon.mask_item
comment:83 in reply to: ↑ 81 Changed 7 years ago by
Replying to jdemeyer:
Replying to 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 sagedevel? The cumulated times do not seem to match.
comment:84 followup: ↓ 87 Changed 7 years ago by
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.
comment:85 Changed 7 years ago by
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
The __cmp__
and __richcmp__
boilerplate is no longer needed and can simply be removed (just move the doctests to the singleunderscore methods).
comment:87 in reply to: ↑ 84 Changed 7 years ago by
Replying to jdemeyer:
Just a question: do you expect the structs
path_mon_t
,path_term_t
andpath_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 followup: ↓ 92 Changed 7 years ago by
This is very very bad:
cmp(M2.path.lengthM2.s_len, M1.path.lengthM1.s_len)
This converts both arguments from a C integer to a Python int
and then calls the Python function cmp()
.
comment:89 followup: ↓ 105 Changed 7 years ago by
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
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 followup: ↓ 102 Changed 7 years ago by
And remember to test this ticket with #18927.
comment:92 in reply to: ↑ 88 Changed 7 years ago by
Replying to jdemeyer:
This is very very bad:
cmp(M2.path.lengthM2.s_len, M1.path.lengthM1.s_len)This converts both arguments from a C integer to a Python
int
and then calls the Python functioncmp()
.
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 followup: ↓ 98 Changed 7 years ago by
When writing Cython code, you should use signal handling in the appropriate places to enable CTRLC. 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 lowlevel loops.
comment:94 followup: ↓ 99 Changed 7 years ago by
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
In general, I would avoid predec()
in Cython code unless it's needed for C++ classes (which isn't the case here).
comment:96 followup: ↓ 100 Changed 7 years ago by
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
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
Replying to jdemeyer:
When writing Cython code, you should use signal handling in the appropriate places to enable CTRLC. The easiest is simply to put a
sig_check()
inside loops which can take a long time, i.e. replacewhile ... ...by
while ... sig_check() ...in the lowlevel 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 Cfunctions.
comment:99 in reply to: ↑ 94 Changed 7 years ago by
Replying to jdemeyer:
This
predec(kill_list.nterms)is just an obscure way of writing
kill_list.nterms = 1so 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 overgeneralising.
comment:100 in reply to: ↑ 96 Changed 7 years ago by
Replying to 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 youinline
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 withinline
. 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
Replying to jdemeyer:
OK, some general advice just from the top of my head:
 Most importantly, be consistent: try not to assign a
long
to anint
, 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 twosided 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 nonnegative 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
comment:103 Changed 7 years ago by
 Commit changed from 63f08e1a962acbe620147135c4581ed52f86db2f to 35b167ef06d9862c00593b22dc0c06a7629396a6
comment:104 Changed 7 years ago by
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
Replying to jdemeyer:
Can you document the C structures in the
.pxd
file a bit more? What I'm missing is basic "what does thisstruct
do" documentation.
I forgot to address this one. On my todo list...
comment:106 Changed 7 years ago by
 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
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
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 followup: ↓ 111 Changed 7 years ago by
Just some quick comments, I don't have much time.
it was said to put sig_on/_off around potentially expensive calls to Cfunctions.
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
 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
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.
Replying to jdemeyer:
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 todo list.
For
sig_check
, you just have to ensure thatsig_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 callingsig_check
. So, as a rule of thumb: putsig_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
Sigh.
king@linuxva3e:~/Sage/git/sage> git trac pull 18927 remote branch: b6e57c46b714b1eb811a3a62fccfc37b6b5ff2ff Traceback (most recent call last): File "/home/king/bin/gittrac", line 18, in <module> cmdline.launch() File "/home/king/Sage/git/gittraccommand/git_trac/cmdline.py", line 213, in launch app.pull(args.ticket_or_branch) File "/home/king/Sage/git/gittraccommand/git_trac/app.py", line 90, in pull self.repo.pull(remote) File "/home/king/Sage/git/gittraccommand/git_trac/git_repository.py", line 176, in pull self.git.echo.fetch('trac', remote_branch) File "/home/king/Sage/git/gittraccommand/git_trac/git_interface.py", line 341, in meth return self.execute(git_cmd, *args, **kwds) File "/home/king/Sage/git/gittraccommand/git_trac/git_interface.py", line 98, in execute popen_stderr=subprocess.PIPE) File "/home/king/Sage/git/gittraccommand/git_trac/git_interface.py", line 263, in _run raise GitError(result) git_trac.git_error.GitError: git returned with nonzero exit code (128) when executing "git fetch trac b6e57c46b714b1eb811a3a62fccfc37b6b5ff2ff" STDERR: error: no such remote ref b6e57c46b714b1eb811a3a62fccfc37b6b5ff2ff
So, how to test with #18972?
comment:113 followup: ↓ 114 Changed 7 years ago by
Try
git pull origin u/vbraun/upgrade_cython_to_0_23
comment:114 in reply to: ↑ 113 Changed 7 years ago by
Replying to tscrim:
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/sitepackages/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/sitepackages/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/sitepackages/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
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
Good, with the obvious change I get
king@linuxva3e:~/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
Here is how I address Frédéric's comments.
 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
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) <ipythoninput556d3ca179acf> in <module>() > 1 X.homogeneous_component(Integer(0)) /home/king/Sage/git/sage/local/lib/python2.7/sitepackages/sage/categories/graded_modules_with_basis.py in homogeneous_component(self, n) 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/sitepackages/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/sitepackages/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 /home/king/Sage/git/sage/src/sage/combinat/dict_addition.pyx in sage.combinat.dict_addition.dict_addition (build/cythonized/sage/combinat/dict_addition.c:1190)() 19 from cpython cimport PyDict_Copy 20 > 21 cpdef dict_addition(dict_iter): 22 r""" 23 Returns the pointwise addition of dictionaries with coefficients. /home/king/Sage/git/sage/src/sage/combinat/dict_addition.pyx in sage.combinat.dict_addition.dict_addition (build/cythonized/sage/combinat/dict_addition.c:879)() 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/sitepackages/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 methodbut not a private (i.e. underscore) attribute!
I am not going to fix that bug in CombinatorialFreeModulethat's not really my world, as I prefer the "classical" way of implementing algebraic structures.
As a workaround, I may override the .sum() method.
comment:119 Changed 7 years ago by
Hilarious.
CombinatorialFreeModule.sum overrides GradedAlgebrasWithBasis.parent_class.sum, and PathAlgebra.sum ought to override CombinatorialFreeModule.sum by GradedAlgebrasWithBasis.parent_class.sum...
comment:120 Changed 7 years ago by
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 sagedevel and sagecombinat about it. Apparently CombinatorialFreeModule makes specific assumptions on the implementation details of its element class.
comment:121 Changed 7 years ago by
 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
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 followups: ↓ 126 ↓ 127 ↓ 138 Changed 7 years ago by
Well, I didn't really mean that you should change the bitset/biseq functions. I think those are sufficiently lowlevel 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 followup: ↓ 125 Changed 7 years ago by
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 ; followup: ↓ 130 Changed 7 years ago by
Replying to jdemeyer:
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 ; followup: ↓ 128 Changed 7 years ago by
Replying to jdemeyer:
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 ; followup: ↓ 129 Changed 7 years ago by
Replying to jdemeyer:
Well, I didn't really mean that you should change the bitset/biseq functions. I think those are sufficiently lowlevel 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 CtrlC?
Also, there is no reason to replace
sig_on()
/sig_off()
withsig_check()
in the biseq functions. Thesig_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
comment:129 in reply to: ↑ 127 ; followup: ↓ 131 Changed 7 years ago by
Replying to SimonKing:
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 notimplemented 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
Replying to SimonKing:
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 highlevel function might choose to use sig_on()
/sig_off()
instead of sig_check()
.
comment:131 in reply to: ↑ 129 ; followup: ↓ 132 Changed 7 years ago by
Replying to jdemeyer:
But a more philosophical reason to prefer
sig_on()
/sig_off()
for the bitset/biseq functions is that those loops really act like notimplementedmpn_
functions. Where we can use anmpn_
function, we do that usingsig_on()
/sig_off()
. Where we cannot use anmpn_
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 ; followup: ↓ 134 Changed 7 years ago by
Replying to SimonKing:
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
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 Ccode generated by Cython. For example, I removed the "inline" from bitset_init, because I expected that the error handling bloats the Ccode, and because I thought that bitset_init is called less often than bitset manipulation functions. The Ccode 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 ; followup: ↓ 135 Changed 7 years ago by
Replying to jdemeyer:
More importantly, when using
mpn_
functions, there simply is no loop where we can putsig_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
Replying to SimonKing:
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
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
 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
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/linuxva3e.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
 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 followup: ↓ 141 Changed 7 years ago by
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/linuxva3e.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 monomialrelated functions...
comment:141 in reply to: ↑ 140 Changed 7 years ago by
Replying to SimonKing:
I think I am done now! At least unless I find that after all these changes I find a benefit in inlining some monomialrelated 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
 Milestone changed from sage6.8 to sage6.9
I would like to have a patchbot's green light on the latest version..
comment:143 Changed 7 years ago by
 Status changed from needs_review to needs_work
There are two failing doctests, see patchbot report.
comment:144 followup: ↓ 145 Changed 7 years ago by
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 ; followup: ↓ 146 Changed 7 years ago by
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 forcepush? 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 ; followup: ↓ 147 Changed 7 years ago by
Replying to SimonKing:
Question: How should I change it? By rebasing and forcepush? 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 ; followup: ↓ 150 Changed 7 years ago by
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.
comment:148 Changed 7 years ago by
 Commit changed from 6ea8fa28882c544be8a368a7a9de89e60e3abc85 to 5b4ed6e69229b0809a1ab4ab63938569fed30b44
comment:149 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:150 in reply to: ↑ 147 Changed 7 years ago by
... 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
 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
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
 Branch changed from public/17435/cythonise_path_algebra_elements to 5b4ed6e69229b0809a1ab4ab63938569fed30b44
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
Cythoned path algebra elements
Implement mul, cmp, hash; fix add
Faster hash; fixed multiplication; temporary: sanity checks
Path algebra elements now feature complete; minor changes to path algebras
Use PathAlgebraElement for path algebras. Still missing: Pickling
Pickling of path algebra elements
Fix conversion of path algebra elements
Verify during printing of a polynomial that the terms are ordered. Only allow degree orders. More docs.
Conversion dict>path algebra element. Full doctest coverage.
Merge branch 't/17435/cythonise_path_algebra_elements' into cythonize_path_algebra_element