Opened 6 years ago

Closed 5 years ago

#15247 closed enhancement (fixed)

Introduce a baseclass for singletons

Reported by: SimonKing Owned by:
Priority: major Milestone: sage-6.4
Component: performance Keywords:
Cc: nthiery, nbruin, novoselt Merged in:
Authors: Simon King Reviewers: Marc Mezzarobba, Travis Scrimshaw, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: aa9821e (Commits) Commit: aa9821ecb389908ce84b69735ead32bf871bdd4f
Dependencies: Stopgaps:

Description

Since some while, we have sage.categories.category_singleton.Category_singleton. A singleton is a class that allows the creation of exactly one instance (of any subclass). The technical implementa tion of Category_singleton is roughly like this: In some static __classcall__, test that the given class is a direct subclass of Category_singleton; then create a (the) instance of the class; then set the override the classcall of this class and of the class of the instance (which might be a subclass) by a constant function returning the instance.

I suggest to provide this construction scheme generally, in sage.misc.fast_methods.SingletonClass. The idea is: If one write a class inheriting from SingletonClass then one does not need to think about caching the unique instance or writing a fast hash or writing fast comparison, since this will all be inherited from SingletonClass.

I suggest to use it at least on the rational field, which currently has a custom cache, and its hash method is written in Python.

With the branch that I am going to add, I get

sage: %timeit RationalField()
1000000 loops, best of 3: 269 ns per loop
sage: %timeit hash(QQ)
10000000 loops, best of 3: 134 ns per loop
sage: %timeit QQ==ZZ
10000000 loops, best of 3: 144 ns per loop

With vanilla sage-5.12.b5, it is a lot slower:

sage: %timeit RationalField()
10000 loops, best of 3: 82.4 us per loop
sage: %timeit hash(QQ)
1000000 loops, best of 3: 496 ns per loop
sage: %timeit QQ==ZZ
1000000 loops, best of 3: 878 ns per loop

Change History (45)

comment:1 Changed 6 years ago by SimonKing

  • Branch set to u/SimonKing/ticket/15247
  • Created changed from 10/01/13 22:42:26 to 10/01/13 22:42:26
  • Modified changed from 10/01/13 22:42:26 to 10/01/13 22:42:26

comment:2 Changed 6 years ago by SimonKing

It is not "needs review" yet, but I guess it only needs test coverage for the new class.

comment:3 Changed 6 years ago by git

  • Commit set to add22e67c8eddafc7097aee8ee1b6883596a8a89

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

[changeset:add22e6]Add tests for SingletonClass?

comment:4 Changed 6 years ago by SimonKing

  • Authors set to Simon King
  • Status changed from new to needs_review

I did not run make ptest yet, but I have added tests for the new SingletonClass and hence change the ticket into "needs review".

comment:5 Changed 6 years ago by SimonKing

It will be needed to change the expected output of several hash functions in the tests, as the hash of QQ is changed object.__hash__(QQ) with my branch.

comment:6 follow-up: Changed 6 years ago by SimonKing

Oops, and much worse: It seems that I forgot to think about unpickling old pickles of QQ!

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

Replying to SimonKing:

Oops, and much worse: It seems that I forgot to think about unpickling old pickles of QQ!

I stand corrected: THIS seems to work. But the pickle jar broke.

comment:8 follow-up: Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work

I have now clue what is going wrong here.

I tested saving a rational number in vanilla sage, and I could read the pickle after rebuilding Sage with my branch. However, it seems that some old pickles in the pickle jar manage to create a version of the integer ring without calling its __init__. This could be accomplished by directly calling __new__. But is this really done somewhere?

comment:9 follow-up: Changed 6 years ago by nthiery

I won't have time to review this ticket, but I am all +1 on progress on this direction. Just one thing: the priority is not as high than #10963, and the two patches are likely to conflict with each other, so I'd recommend basing this one on top of #10963.

Cheers,

Nicolas

comment:10 in reply to: ↑ 9 ; follow-up: Changed 6 years ago by SimonKing

Replying to nthiery:

I won't have time to review this ticket, but I am all +1 on progress on this direction. Just one thing: the priority is not as high than #10963, and the two patches are likely to conflict with each other,

Why? My branch touches sage.misc.fast_methods and sage.rings.rational_field and nothing else. I do not aim (yet!) at changing Category_singleton, although it would make sense in the long run (i.e., after #10963.

comment:11 in reply to: ↑ 10 Changed 6 years ago by nthiery

Replying to SimonKing:

Why? My branch touches sage.misc.fast_methods and sage.rings.rational_field and nothing else. I do not aim (yet!) at changing Category_singleton, although it would make sense in the long run (i.e., after #10963.

Ah, ok, perfect! Double +1 on this ticket then. Well, as long as it does not eat up review time from you on #10963 :-)

comment:12 Changed 6 years ago by git

  • Commit changed from add22e67c8eddafc7097aee8ee1b6883596a8a89 to 44de39272977327c5a6b248dc2bc0f54a36db382

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

[changeset:44de392]Add Rational.new, to make ancient pickles readable

comment:13 Changed 6 years ago by SimonKing

  • Status changed from needs_work to needs_review

I did not run make ptest yet, but at least the new commit makes unpickle_all() work.

comment:14 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to update hash values in tests

Oops, I forgot: Some hash values are to be updated as well.

comment:15 Changed 6 years ago by SimonKing

Nice finding: One of the hash tests was in fact wrong, because it was a test for the hash of a different class!

I am about to fix this now, by testing against the definition of the respective hash functions. So, I am not testing against the result on 64bit and 32 bit machines, since such tests don't seem meaningful to me.

comment:16 Changed 6 years ago by git

  • Commit changed from 44de39272977327c5a6b248dc2bc0f54a36db382 to 86d2b6417e5e4814b2a61cb510edef32a5a3b08c

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

[changeset:86d2b64]Fix the hash value doctests of Heegner points

comment:17 Changed 6 years ago by SimonKing

  • Status changed from needs_work to needs_review
  • Work issues update hash values in tests deleted

Now I am confident that the tests will work, and that the branch is ready for review.

comment:18 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to fixs more hash values

comment:19 Changed 6 years ago by SimonKing

There are even more tests that test against the hash value of an instance of the wrong class!

comment:20 Changed 6 years ago by git

  • Commit changed from 86d2b6417e5e4814b2a61cb510edef32a5a3b08c to 26132d9f30e881fc75a3bae60c8e526a6e4fef9f

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

[changeset:26132d9]Fix several more hash tests

comment:21 follow-up: Changed 6 years ago by SimonKing

  • Status changed from needs_work to needs_review
  • Work issues fixs more hash values deleted

There were several hash tests to fix. In all cases, I stopped comparing against a particular number, because

  1. the number depends on the architecture (32- versus 64-bit)
  2. the number does not show how the hash function works
  3. one should test the result of hash against the hash function of the class being tested---otherwise (and this happened in at least three examples) one might test an instance of the wrong class.

The tests should work now.

comment:22 Changed 6 years ago by git

  • Commit changed from 26132d9f30e881fc75a3bae60c8e526a6e4fef9f to 848952746e60990b25a0cf013081f5fad4ffe6e3

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

[changeset:8489527]Use "sorted" in one test on sets

comment:23 in reply to: ↑ 21 Changed 6 years ago by SimonKing

Replying to SimonKing:

The tests should work now.

All but one test worked. The failing test was testing against the order of elements of a set. The obvious solution was to use "sorted" in the example. Hence, with the branch that I updated a minute ago, all tests pass for me.

comment:24 in reply to: ↑ 8 Changed 6 years ago by mmezzarobba

Replying to SimonKing:

However, it seems that some old pickles in the pickle jar manage to create a version of the integer ring without calling its __init__. This could be accomplished by directly calling __new__. But is this really done somewhere?

I'm not sure I understand what you mean: isn't that (calling __new__ but not __init__) how unpickling works in general?

comment:25 follow-up: Changed 6 years ago by mmezzarobba

  • Branch changed from u/SimonKing/ticket/15247 to u/mmezzarobba/15247-singleton_class
  • Commit changed from 848952746e60990b25a0cf013081f5fad4ffe6e3 to 207f6b72c0dc4601732c5ca0ee722c4c43c95709
  • Reviewers set to Marc Mezzarobba
  • I am a little bit skeptical about tying the singleton behaviour to comparison by identity if SingletonClass is meant to be the way to implement singleton classes. Indeed, this makes it virtually unusable for Elements as long as sage keeps abusing == to implement semantic (as opposed to syntaxic) equality. And singleton classes descending from Element have at leat one natural use case, namely well-known constants (infinities, pi...). Could you please comment on this choice?
  • I don't like having the same explanations and/or tests repeated in several docstrings. I tried to remove redundancies in c5acb88a and 949b7b2aa. But feel free to revert these commits if you disagree!
  • The same goes for 207f6b72, where I applied SingletonClass to other parents (initially to check how usable it was in practice, but since it's done...).
  • Finally, I made a few minor changes in d9ca799c. Could you please check that none of the things I "fixed" was intentional?

New commits:

d9ca799SingletonClass: cosmetic changes.
c5acb88SingletonClass: Less redundant docstrings
949b7b2QQ/SingletonClass: Delete redundant doctest
4123a50Merge in '6.1.rc0' to prevent whitespace conflicts
207f6b7Make QQbar, AA, and PariRing 'SingletonClass'es

comment:26 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:27 Changed 5 years ago by mmezzarobba

  • Branch changed from u/mmezzarobba/15247-singleton_class to u/mmezzarobba/15247-singleton_class-rebased
  • Commit changed from 207f6b72c0dc4601732c5ca0ee722c4c43c95709 to a431dadc789f4f519468c3c678937d4fde30e3af

comment:28 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:29 Changed 5 years ago by rws

  • Status changed from needs_review to needs_work
  • Work issues set to rebase

comment:30 Changed 5 years ago by git

  • Commit changed from a431dadc789f4f519468c3c678937d4fde30e3af to dfbb8bba4a90b1bc30cd33199c9eee9655d8fc95

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

0f900b9Use WithEqualityById on SingletonClass, replace QQ.__hash__
159daaaAdd tests for SingletonClass
a9d0e5aAdd Rational.__new__, to make ancient pickles readable
61ab8c8Fix the hash value doctests of Heegner points
5c1d17bFix several more hash tests
4969e24Use "sorted" in one test on sets
a2f369dSingletonClass: cosmetic changes.
59aea3cSingletonClass: Less redundant docstrings
765b281QQ/SingletonClass: Delete redundant doctest
dfbb8bbMake QQbar, AA, and PariRing 'SingletonClass'es

comment:31 Changed 5 years ago by mmezzarobba

  • Status changed from needs_work to needs_review
  • Work issues rebase deleted

rebased (not fully tested yet, but seems to work)


Last 10 new commits:

0f900b9Use WithEqualityById on SingletonClass, replace QQ.__hash__
159daaaAdd tests for SingletonClass
a9d0e5aAdd Rational.__new__, to make ancient pickles readable
61ab8c8Fix the hash value doctests of Heegner points
5c1d17bFix several more hash tests
4969e24Use "sorted" in one test on sets
a2f369dSingletonClass: cosmetic changes.
59aea3cSingletonClass: Less redundant docstrings
765b281QQ/SingletonClass: Delete redundant doctest
dfbb8bbMake QQbar, AA, and PariRing 'SingletonClass'es

comment:32 in reply to: ↑ 25 ; follow-up: Changed 5 years ago by tscrim

  • Branch changed from u/mmezzarobba/15247-singleton_class-rebased to public/singleton_class-15247
  • Commit changed from dfbb8bba4a90b1bc30cd33199c9eee9655d8fc95 to 0d78737de4a8f364903da0998f02fc9e803c2b0f
  • Reviewers changed from Marc Mezzarobba to Marc Mezzarobba, Travis Scrimshaw

Perhaps Simon can comment at some point, but here are my thoughts.

Replying to mmezzarobba:

  • I am a little bit skeptical about tying the singleton behaviour to comparison by identity if SingletonClass is meant to be the way to implement singleton classes. Indeed, this makes it virtually unusable for Elements as long as sage keeps abusing == to implement semantic (as opposed to syntaxic) equality. And singleton classes descending from Element have at leat one natural use case, namely well-known constants (infinities, pi...). Could you please comment on this choice?

I would say this is okay as you can always override __eq__ as necessary, and python's default is to do equality check by id.

  • I don't like having the same explanations and/or tests repeated in several docstrings. I tried to remove redundancies in c5acb88a and 949b7b2aa. But feel free to revert these commits if you disagree!

I moved the pickling test to the class-level doc in order to make it more visible.

  • The same goes for 207f6b72, where I applied SingletonClass to other parents (initially to check how usable it was in practice, but since it's done...).
  • Finally, I made a few minor changes in d9ca799c. Could you please check that none of the things I "fixed" was intentional?

I think they were typos.

I've also made some other misc review changes. However I have a question, should this be in sage/misc or in sage/structure since it feels more like a structural piece of Sage? Otherwise I'm happy with the current state of things (and found similar speedups).


New commits:

4ad8e71Merge branch 'u/mmezzarobba/15247-singleton_class-rebased' of trac.sagemath.org:sage into public/structure/singleton_class-15247
0d78737Some review changes for #15247.

comment:33 in reply to: ↑ 32 ; follow-up: Changed 5 years ago by SimonKing

Replying to tscrim:

Perhaps Simon can comment at some point, but here are my thoughts.

Well, at some point I should perhaps look at the code/doc again...

I've also made some other misc review changes. However I have a question, should this be in sage/misc or in sage/structure since it feels more like a structural piece of Sage?

At #15820 we had a similar discussion, and Nicolas has convinced me with the following: If the structure being implemented is Sage-specific (examples: elements, parents) then it goes into sage.structure. If the structure being implemented would make sense outside of Sage, then it goes into sage.misc (examples: classcall metaclass, sequences of bounded integers as in #15820).

And I'd say that a singleton baseclass makes sense outside of Sage, hence, should go into sage.misc.

comment:34 Changed 5 years ago by git

  • Commit changed from 0d78737de4a8f364903da0998f02fc9e803c2b0f to 391421e37fd4391227aab94b00c447c1a6945bb2

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

391421eMerge branch 'public/singleton_class-15247' of trac.sagemath.org:sage into public/singleton_class-15247

comment:35 in reply to: ↑ 33 Changed 5 years ago by tscrim

Replying to SimonKing:

At #15820 we had a similar discussion, and Nicolas has convinced me with the following: If the structure being implemented is Sage-specific (examples: elements, parents) then it goes into sage.structure. If the structure being implemented would make sense outside of Sage, then it goes into sage.misc (examples: classcall metaclass, sequences of bounded integers as in #15820).

Thanks for reminding me of that (and sorry, I let this ticket slip of my radar); Nicolas told me at one time but I couldn't remember which when where.

And I'd say that a singleton baseclass makes sense outside of Sage, hence, should go into sage.misc.

I agree.


Rebased and we just need a little bit more review.

comment:36 Changed 5 years ago by git

  • Commit changed from 391421e37fd4391227aab94b00c447c1a6945bb2 to 3e9e736a9fbe164d07a2ce1d58efdc3e5b2a49ab

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

3e9e736Fix merge error

comment:37 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:38 Changed 5 years ago by tscrim

ping

Could someone just review my change 0d78737? I've given a positive review to everything else.

comment:39 Changed 5 years ago by nthiery

I just had a look at 0d78737, and it looks good to me.

I would have two semi-unrelated suggestions though:

  • Maybe rename the class to Singleton rather than SingletonClass: then the name of the class will describe, as is usual, what its instances are, rather than the class itself.
  • For the test that is modified in 0d78737: make the inheritance explicit by creating a subclasss rather than trigerring such an inheritance through a call to _refine_category.

Thanks!

Cheers,

Nicolas

comment:40 Changed 5 years ago by git

  • Commit changed from 3e9e736a9fbe164d07a2ce1d58efdc3e5b2a49ab to 3bd5ae067804742cc7e2f47b4e5575699a2f69d1

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

3bd5ae0Merge branch 'public/singleton_class-15247' of trac.sagemath.org:sage into public/singleton_class-15247

comment:41 Changed 5 years ago by tscrim

Done and done.

comment:42 Changed 5 years ago by git

  • Commit changed from 3bd5ae067804742cc7e2f47b4e5575699a2f69d1 to aa9821ecb389908ce84b69735ead32bf871bdd4f

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

aa9821eChanges from Nicolas' suggestions.

comment:43 Changed 5 years ago by nthiery

  • Reviewers changed from Marc Mezzarobba, Travis Scrimshaw to Marc Mezzarobba, Travis Scrimshaw, Nicolas M. Thiéry
  • Status changed from needs_review to positive_review

Thank you Travis! I double checked your changes, hence positive review.

comment:44 Changed 5 years ago by tscrim

Thank you Nicolas. Also thank you Simon and Marc for your work on this.

comment:45 Changed 5 years ago by vbraun

  • Branch changed from public/singleton_class-15247 to aa9821ecb389908ce84b69735ead32bf871bdd4f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.