Use Parent/Element for Manin symbols

[pbruin]

The classes ManinSymbolList and ManinSymbol (in sage.modular.modsym.manin_symbols) do not inherit from Parent and Element. We fix this and make ManinSymbolList a parent in the category FiniteEnumeratedSets.

To prevent a measurable slowdown, the class ManinSymbol is converted to Cython.

This is a dependency of #10513.

[pbruin]

The only real changes are in commit a9da048; the first two move the class ManinSymbol up in the file to allow Element = ManinSymbol in ManinSymbolList.

[tscrim]

I've made some more substantial changes making ManinSymbolList a proper parent in FiniteEnumeratedSets. In particular, there is a backwards incompatible change in that m[i] returns a ManinSymbol instance (of m) rather than a tuple. Also I changed the _list attribute to _symbol_list since FiniteEnumeratedSets uses _list internally. Lastly I've added a method symbol_list to get the explicit list of symbols (the indexing tuples).

I'm thinking we should post something to sage-devel stating this (proposed) change. Sound good?

---

New commits:

​c070145	Merge branch 'u/pbruin/17578-ManinSymbol_Parent_Element' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578
​9cf191b	More changes towards a proper parent class.

[pbruin]

Replying to tscrim:

I've made some more substantial changes making ManinSymbolList a proper parent in FiniteEnumeratedSets. In particular, there is a backwards incompatible change in that m[i] returns a ManinSymbol instance (of m) rather than a tuple. Also I changed the _list attribute to _symbol_list since FiniteEnumeratedSets uses _list internally. Lastly I've added a method symbol_list to get the explicit list of symbols (the indexing tuples).

I'm thinking we should post something to sage-devel stating this (proposed) change. Sound good?

I don't mind too much, but given that this ticket is a dependency of #10513, which already has positive review, wouldn't it make sense to do this on a different ticket? (I currently don't have enough time to review your changes.)

[jdemeyer]

This will almost certainly conflict with the already-merged #15015.

[jdemeyer]

I moved the "moving" part to #17579 (merging #15015). I'll let you decide which commits from here to cherry-pick on top of #17579.

[tscrim]

sage-devel: ​http://groups.google.com/forum/#!topic/sage-devel/JlPnmjA1PCg

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​7725122	Cosmetic changes
​6957f17	Merge remote-tracking branch 'origin/develop' into ticket/15015
​aca71cb	Upgrade to mpir-2.7.0-alpha12
​67babeb	Fix doctests due to changed xgcd results
​8c7fbbd	Re-enable "not tested" test from #4357
​aefe0eb	Upgrade to MPIR 2.7.0-alpha12
​3d583af	Merge remote-tracking branch 'origin/develop' into ticket/15015
​d97c066	Rename source directory
​d647df8	Trac 17579: move ManinSymbol class
​57a4259	Merge branch 'u/jdemeyer/ticket/17579' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578

[tscrim]

I merged in #17579, but kept the version from here.

[pbruin]

In the meantime I already rebased the branch (I think this is a better solution than merging in this case) and reverted the more substantial changes from Travis's commit, so that this ticket can be merged as soon as possible in view of #10513.

[tscrim]

I strongly disagree with doing this (IMO) dirty hack of parents just to merge it quickly. It creates parents without a category and elements not created from the parent, both of which are abuses of Parent.

Also from my understanding, since this branch was published and I based my branch on it, it was not good to rebase the branch. Merge commits don't hurt anyone.

[tscrim]

I'm creating the following for the test:

sage: from sage.modular.modsym.manin_symbols import ManinSymbolList_gamma0
sage: m = ManinSymbolList_gamma0(5,8)

Previously we have:

sage: %time L = m.manin_symbol_list()
CPU times: user 560 µs, sys: 84 µs, total: 644 µs
Wall time: 494 µs
sage: %time L = m.manin_symbol_list()
CPU times: user 48 µs, sys: 4 µs, total: 52 µs
Wall time: 68.9 µs

With my branch:

sage: %time L = m.manin_symbol_list()
CPU times: user 644 µs, sys: 90 µs, total: 734 µs
Wall time: 747 µs
sage: %time L = m.manin_symbol_list()
CPU times: user 56 µs, sys: 7 µs, total: 63 µs
Wall time: 64.8 µs

With Peter's branch:

sage: %time L = m.manin_symbol_list()
CPU times: user 792 µs, sys: 99 µs, total: 891 µs
Wall time: 828 µs
sage: %time L = m.manin_symbol_list()
CPU times: user 49 µs, sys: 6 µs, total: 55 µs
Wall time: 66 µs

So there is a slowdown with creating the instances of ManinSymbol that comes from the new branch and Peters by creating instances of Element. Hence this is a slowdown we might just have to deal with (assuming one is actually wanting the ManinSymbol, not the indexing tuple which can be grabbed by symbol_list).

---

New commits:

​6494bcd	Trac 17578: move ManinSymbol class (1)
​dcf9d35	Trac 17578: move ManinSymbol class (2)
​a9da048	Trac 17578: use Parent/Element for Manin symbols
​c070145	Merge branch 'u/pbruin/17578-ManinSymbol_Parent_Element' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578
​9cf191b	More changes towards a proper parent class.
​57a4259	Merge branch 'u/jdemeyer/ticket/17579' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578

[was]

If I'm reading your test, that's not just "a slowdown...we might just have to deal with", it's an epic slowdown, by a full factor of 10. Am I reading that right? If so, then this is definitely seriously worrisome.

[tscrim]

Replying to was:

If I'm reading your test, that's not just "a slowdown...we might just have to deal with", it's an epic slowdown, by a full factor of 10. Am I reading that right? If so, then this is definitely seriously worrisome.

The first line is the actual creation, the second is when the caching comes into effect. However the slowdown is by ~1.4x due to the overhead. Thus if we want to fix the probthese without the overhead from the category, we need an entirely different approach. Do you think you could run a timing in a more realistic computation or post such a computation?

[pbruin]

Here is a new branch incorporating my original fix, Travis's improvements, and a restructuring of the module sage.modular.modsym.manin_symbols into two new modules sage.modular.modsym.manin_symbol (Cython) and sage.modular.modsym.manin_symbol (Python).

The creation of the list in Travis's example goes down from 191 µs to 150 µs on the system on which I tested this.

(I have decided to rebase my branch; it has been inactive for months and I wanted to start with a clean slate. In particular, I found the duplicate commits in the Git history extremely annoying.)

[tscrim]

Overall I'm happy with the changes (especially the speedup, which was the sticking point for getting this in). Quick question, could any of those methods for the ManinSymbol class be declared cpdef and get a speed boost? If not (or you don't think it's necessary to do now), you can set this to a positive review.

[pbruin]

Replying to tscrim:

Overall I'm happy with the changes (especially the speedup, which was the sticking point for getting this in).

Thanks!

Quick question, could any of those methods for the ManinSymbol class be declared cpdef and get a speed boost? If not (or you don't think it's necessary to do now), you can set this to a positive review.

I prefer to do this later if and when it becomes necessary.

[tscrim]

Alright. Thanks for your work on this (and on improving the modules!!!).