Opened 5 years ago

Closed 5 years ago

#17578 closed defect (fixed)

Use Parent/Element for Manin symbols

Reported by: pbruin Owned by:
Priority: major Milestone: sage-6.5
Component: modular forms Keywords: Manin symbol
Cc: jdemeyer, jpflori, was Merged in:
Authors: Peter Bruin, Travis Scrimshaw Reviewers: Travis Scrimshaw, Peter Bruin
Report Upstream: N/A Work issues:
Branch: 286e475 (Commits) Commit: 286e4756e2bb1e5657611d505ec5d7d6f99f3c36
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (19)

comment:1 Changed 5 years ago by pbruin

  • Branch set to u/pbruin/17578-ManinSymbol_Parent_Element
  • Commit set to a9da0487574bd6c9e31743929de1a9ae1b476cdb
  • Status changed from new to needs_review

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.

comment:2 follow-up: Changed 5 years ago by tscrim

  • Branch changed from u/pbruin/17578-ManinSymbol_Parent_Element to u/tscrim/manin_symbol_parent-17578
  • Commit changed from a9da0487574bd6c9e31743929de1a9ae1b476cdb to 9cf191b8faf45f97855e5612ed81d7a3988c5cb4
  • Reviewers set to Travis Scrimshaw

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:

c070145Merge branch 'u/pbruin/17578-ManinSymbol_Parent_Element' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578
9cf191bMore changes towards a proper parent class.

comment:3 in reply to: ↑ 2 Changed 5 years ago by 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.)

comment:4 Changed 5 years ago by jdemeyer

  • Dependencies set to #15015

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

comment:5 Changed 5 years ago by jdemeyer

  • Dependencies changed from #15015 to #17579

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

comment:8 Changed 5 years ago by git

  • Commit changed from 9cf191b8faf45f97855e5612ed81d7a3988c5cb4 to 57a425901538723e212815ab1e84908ff992cf40

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

7725122Cosmetic changes
6957f17Merge remote-tracking branch 'origin/develop' into ticket/15015
aca71cbUpgrade to mpir-2.7.0-alpha12
67babebFix doctests due to changed xgcd results
8c7fbbdRe-enable "not tested" test from #4357
aefe0ebUpgrade to MPIR 2.7.0-alpha12
3d583afMerge remote-tracking branch 'origin/develop' into ticket/15015
d97c066Rename source directory
d647df8Trac 17579: move ManinSymbol class
57a4259Merge branch 'u/jdemeyer/ticket/17579' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578

comment:9 Changed 5 years ago by tscrim

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

comment:10 Changed 5 years ago by pbruin

  • Branch changed from u/tscrim/manin_symbol_parent-17578 to u/pbruin/17578-ManinSymbol_Parent_Element
  • Commit changed from 57a425901538723e212815ab1e84908ff992cf40 to e59b940b36c40cca506f7740a480c47369920309

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.

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

comment:12 Changed 5 years ago by tscrim

  • Branch changed from u/pbruin/17578-ManinSymbol_Parent_Element to u/tscrim/manin_symbol_parent-17578
  • Cc was added
  • Commit changed from e59b940b36c40cca506f7740a480c47369920309 to 57a425901538723e212815ab1e84908ff992cf40

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:

6494bcdTrac 17578: move ManinSymbol class (1)
dcf9d35Trac 17578: move ManinSymbol class (2)
a9da048Trac 17578: use Parent/Element for Manin symbols
c070145Merge branch 'u/pbruin/17578-ManinSymbol_Parent_Element' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578
9cf191bMore changes towards a proper parent class.
57a4259Merge branch 'u/jdemeyer/ticket/17579' of trac.sagemath.org:sage into u/tscrim/manin_symbol_parent-17578

comment:13 follow-up: Changed 5 years ago by 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.

comment:14 in reply to: ↑ 13 Changed 5 years ago by 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?

comment:15 Changed 5 years ago by pbruin

  • Authors changed from Peter Bruin to Peter Bruin, Travis Scrimshaw
  • Branch changed from u/tscrim/manin_symbol_parent-17578 to u/pbruin/17578-ManinSymbol_Parent_Element
  • Commit changed from 57a425901538723e212815ab1e84908ff992cf40 to 286e4756e2bb1e5657611d505ec5d7d6f99f3c36
  • Dependencies #17579 deleted
  • Description modified (diff)

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

comment:16 follow-up: Changed 5 years ago by tscrim

  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Peter Bruin

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.

comment:17 in reply to: ↑ 16 Changed 5 years ago by pbruin

  • Status changed from needs_review to positive_review

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.

comment:18 Changed 5 years ago by tscrim

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

comment:19 Changed 5 years ago by vbraun

  • Branch changed from u/pbruin/17578-ManinSymbol_Parent_Element to 286e4756e2bb1e5657611d505ec5d7d6f99f3c36
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.