Opened 7 years ago

Closed 7 years ago

#17435 closed enhancement (fixed)

Cythonise path algebra elements

Reported by: SimonKing Owned by:
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by SimonKing)

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

Change History (153)

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

  • Cc nthiery ncohen added
  • Commit set to 431b7f9a770b9f5749ab094702b5cd275c13d0ab

Last 10 new commits:

c48b312Cythoned path algebra elements
e85f3aaImplement mul, cmp, hash; fix add
61c283aFaster hash; fixed multiplication; temporary: sanity checks
1fda709Path algebra elements now feature complete; minor changes to path algebras
15ed81dUse PathAlgebraElement for path algebras. Still missing: Pickling
2b16f3aPickling of path algebra elements
6daa985Fix conversion of path algebra elements
269a607Verify during printing of a polynomial that the terms are ordered. Only allow degree orders. More docs.
b32b034Conversion dict->path algebra element. Full doctest coverage.
431b7f9Merge 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:

99da336Fixing 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:

27b6ea9Fix 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:

fab190eKill list for path algebra elements
6f07e26Avoid 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:

a961dfdRemove c-profiling

comment:14 follow-up: 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

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

880801fMake doctests of path algebra elements work on 64 bit
3c8ae84Fix 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:

b080629Elaborate 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: 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

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

cd77a17Merge branch 't/15820/ticket/15820' into t/17435/cythonise_path_algebra_elements

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

Argh. The merge has failed.

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

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

7564770Merge branch 'develop' into t/15820/ticket/15820
962c674Merge branch 'u/jdemeyer/ticket/15820' of git://trac.sagemath.org/sage into t/15820/ticket/15820
63d2693More descriptive function name for bounded integer sequences
af690caMerge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths
126ee26Merge branch 't/15820/ticket/15820' into t/16453/cythonize_quiver_paths
6a6d913Do less imports in path's pxd file; signal handling in one function
73b6539revert a change to pickling of bounded integer sequences
73ac689Allow to choose two alternative encodings of paths
0432297Remove alternative implementation of paths, because of benchmark results
7d9d492Merge 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:

f2a69abMore useful functions for biseq_t
fd3fd82Better hash function for biseq_t. Document the new functions.
b10c172Cython implementation of quiver paths
9d56888Use Cython implementation of paths in path algebras/representations
3b26941Cythoned path algebra elements
6118f0aKill list for path algebra elements
0433d0cAvoid needless term comparisons during multiplication
ba2ed8dElaborate 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:

0a72b46Add a doctest for _nb_arrows
70503e3Clarify the documentation of _cmp_c_impl
8984ea7Merge branch 'public/ticket/16453' of git://trac.sagemath.org/sage into t/17435/cythonise_path_algebra_elements_6.7.beta
5a5e35dMerge 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:

35eb6c2Remove 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:

c89be23Fix 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:

3e94fefMerge with 6.7.beta4, cope with the change of _cmp_c_impl -> _cmp_
93f5310Address reviewer's comments
cbde0c3Elaborate on the meaning of gcd for paths
e8d802eMerge branch 't/17435/cythonise_path_algebra_elements_6.7.beta' into t/17435/cythonise_path_algebra_elements_6.7.beta4
f30e7f7Change _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:

9168ed3Some Cython tweaks for quiver paths
3f0adeeUse cached_method on PathSemigroup.reverese, for efficiency
028c85dStore edge tuple as attribute of path semigroups; length zero path evaluate to false; fix some typos
2dd3206Fix path slicing with step -1, and add test
ecf87e1Merge 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:

330baebMerge 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:47 Changed 7 years ago by SimonKing

  • Keywords SageDays64.5 added

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

  • Cc egunawan added
  • 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:

21da25aAdd 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:

0e09405Resolve 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: 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

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

45ac933Merge branch 'develop' into t/17435/cythonise_path_algebra_elements
10c8167Prepare 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: 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:

e2a27ccRevert unnecessary change to module_list.py

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

Replying to chapoton:

Is the change to module_list.py really needed ?

You are right, it isn't.

comment:66 follow-ups: 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:

63f08e1Add a stronger test to the _latex_ method

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

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 non-technical review is enough?

comment:69 follow-up: 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

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

complains about that.

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

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 follow-up: 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: 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: Changed 7 years ago by SimonKing

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

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: Changed 7 years ago by SimonKing

Replying to jdemeyer:

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: Changed 7 years ago by jdemeyer

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:

  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: Changed 7 years ago by 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.

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
out.path.mask_item = Mon.mask_item

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

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 sage-devel? The cumulated times do not seem to match.

comment:84 follow-up: 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

Replying to 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?

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: Changed 7 years ago by jdemeyer

This is very very bad:

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

Replying to jdemeyer:

This is very very bad:

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

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

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

Replying to jdemeyer:

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

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

Replying to jdemeyer:

OK, some general advice just from the top of my head:

  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

Replying to jdemeyer:

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:

ffb5e0dDo not mix unsigned int with mp_size_t
f823fe8Some speed-ups
35b167eChange 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

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

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:

203d4deElaborate 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: 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:

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

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

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

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

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/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/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 

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

comment:119 Changed 7 years ago by SimonKing

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

0b9ecbcFix _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: 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: 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: Changed 7 years ago by SimonKing

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 ; follow-up: Changed 7 years ago by SimonKing

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 ; follow-up: Changed 7 years ago by SimonKing

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

Replying to SimonKing:

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?

IIRC, is is

git checkout <commit> <file>

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

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

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 high-level function might choose to use sig_on()/sig_off() instead of sig_check().

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

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 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: Changed 7 years ago by jdemeyer

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 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: Changed 7 years ago by SimonKing

Replying to jdemeyer:

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

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

8d5d846Change inlining and signal handling; use freelist more efficiently

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

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:

  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:

6ea8fa2Move monomials from heap to stack

comment:140 follow-up: 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

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 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: 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: Changed 7 years ago by SimonKing

Replying to jdemeyer:

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

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

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

Do you think the little changes in bitset can stay?

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

Replying to SimonKing:

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: Changed 7 years ago by SimonKing

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 git

  • Commit changed from 6ea8fa28882c544be8a368a7a9de89e60e3abc85 to 5b4ed6e69229b0809a1ab4ab63938569fed30b44

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

cfb56ceMerge branch 'develop' into t/17435/cythonise_path_algebra_elements
5b4ed6eRevert 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.