Opened 16 months ago

Closed 14 months ago

Last modified 12 months ago

#22632 closed enhancement (fixed)

Cythonize CombinatorialFreeModuleElement

Reported by: tscrim Owned by:
Priority: major Milestone: sage-8.0
Component: performance Keywords: days85
Cc: sage-combinat, nthiery, jdemeyer, chapoton Merged in:
Authors: Travis Scrimshaw Reviewers: Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: 20cd0da (Commits) Commit:
Dependencies: Stopgaps:

Description

We move CombintorialFreeModuleElement to its own class IndexedFreeModuleElement and cythonize it for (future) speed gains.

Change History (78)

comment:1 Changed 16 months ago by tscrim

  • Branch set to public/combinat/cythonize_CFM_element-22632
  • Commit set to e9186745d5df8cf7092e17103dee9c12b6b33ebf
  • Status changed from new to needs_review

New commits:

e918674Moving CombinatorialFreeModuleElement to own (Cython) file.

comment:2 Changed 16 months ago by tscrim

  • Cc jdemeyer added

comment:3 Changed 16 months ago by hivert

I Travis,

I'm curious, is there any performance gain. I had the impression that storing everything in python dict simply kills all possibilities of optimization ?

We discussed during past sage days, to re-implement combinatorial free modules, using arrays with a global dict for all object used only during input and output and not during linear algebra.

Florent

comment:4 Changed 16 months ago by git

  • Commit changed from e9186745d5df8cf7092e17103dee9c12b6b33ebf to 6b9d88b14b162c5d7ea88c3339896c3adc6e79da

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

6b9d88bDoing some additional tweaks.

comment:5 Changed 16 months ago by tscrim

There seems to be a little bit with doing basic operations:

sage: C = CombinatorialFreeModule(QQ, [1,2,3])
sage: x = sum(C.basis())
sage: %timeit [x + x for _ in range(1000)]
100 loops, best of 3: 2.57 ms per loop

vs old:

sage: C = CombinatorialFreeModule(QQ, [1,2,3])
sage: x = sum(C.basis())
sage: %timeit [x + x for _ in range(1000)]
100 loops, best of 3: 2.94 ms per loop

While it's not much, it is something like a 10-15% speedup, but it is something likely to be called a significant number of times. It's even more so for scalar multiplication:

sage: s = SymmetricFunctions(ZZ).s()
sage: x = s.an_element()
sage: %timeit [4*x for _ in range(1000)]
100 loops, best of 3: 2.49 ms per loop

vs old:

sage: %timeit [4*x for _ in range(1000)]
100 loops, best of 3: 3.42 ms per loop

I might even be able to get some more speed if I am smarter in how we create the results of, e.g., _add_.

Last edited 16 months ago by tscrim (previous) (diff)

comment:6 Changed 16 months ago by git

  • Commit changed from 6b9d88b14b162c5d7ea88c3339896c3adc6e79da to f1fcdd97670b9450f31e1230250dba8cde53c790

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

f1fcdd9Do not go through _from_dict but directly create an element.

comment:7 Changed 16 months ago by tscrim

That gives a very nice speed boost:

sage: C = CombinatorialFreeModule(QQ, [1,2,3])
....: x = sum(C.basis())
....: %timeit [x + x for _ in range(1000)]
....: 
1000 loops, best of 3: 1.84 ms per loop
sage: s = SymmetricFunctions(ZZ).s()
sage: x = s.an_element()
sage: %timeit [4*x for _ in range(1000)]
100 loops, best of 3: 2.05 ms per loop

Now those Python calls become relatively expensive, so we should avoid them.

comment:8 Changed 16 months ago by tscrim

  • Cc chapoton added

Frédéric, I'm cc-ing you because you might want to note that I am taking care of the __cmp__ issue here as well.

comment:9 Changed 16 months ago by chapoton

  • Status changed from needs_review to needs_work

many broken doctests..

comment:10 Changed 16 months ago by git

  • Commit changed from f1fcdd97670b9450f31e1230250dba8cde53c790 to 4ee3313767ce3b3be2f7b5a8f5938d0d6c3e0edc

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

1d4aa1cFixing unpickling issues.
4ee3313Fixing Cython not inheriting _rmul_ and _lmul_ from different signatures.

comment:11 Changed 16 months ago by tscrim

  • Status changed from needs_work to needs_review

Fixed the pickling issues and the other failures (incompatible signatures for _lmul_ and _rmul_).

comment:12 Changed 16 months ago by git

  • Commit changed from 4ee3313767ce3b3be2f7b5a8f5938d0d6c3e0edc to d87735db11bdeab38d4932ca3b46abba8d4ba185

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

d87735dFixed trivial doctest failure.

comment:13 Changed 15 months ago by tscrim

Patchbot is green (essentially, doctest failure is independent).

comment:14 Changed 14 months ago by tscrim

ping

comment:15 Changed 14 months ago by nthiery

diff --git a/src/doc/en/thematic_tutorials/tutorial-objects-and-classes.rst b/src/doc/en/thematic_tutorials/tutorial-objects-and-classes.rst
index 3f964bf..749ab5f 100644
--- a/src/doc/en/thematic_tutorials/tutorial-objects-and-classes.rst
+++ b/src/doc/en/thematic_tutorials/tutorial-objects-and-classes.rst
@@ -285,8 +285,7 @@ Some particular actions modify the data structure of ``el``::
        sage: el.__class__
         <class 'sage.combinat.free_module.CombinatorialFreeModule_with_category.element_class'>
        sage: el.__dict__
-       {'__custom_name': 'foo',
-        '_monomial_coefficients': {[1, 2, 3]: 1, [1, 3, 2]: 3}}
+       {'__custom_name': 'foo'}

Plausibly the explanation around that change needs to be updated a bit: there remains no "normal" attribute in this example. Maybe el.foo=1 could be issued before, and a comment added after that _monomial_coefficients is a Cython attribute?

In general, this seems to be calling for changing the running example for this tutorial. The current one is a bit complicated. But that's for a later ticket.

comment:16 Changed 14 months ago by nthiery

@@ -242,7 +238,8 @@ class FreeAlgebraElement(AlgebraElement, CombinatorialFreeModuleElement):
             if self_on_left:
                 return Factorization([(self, 1)]) * scalar
             return scalar * Factorization([(self, 1)])
-        return super(FreeAlgebraElement, self)._acted_upon_(scalar, self_on_left)
+        ret = super(FreeAlgebraElement, self)._acted_upon_(scalar, self_on_left)
+        return ret
 

What's the point?

comment:17 Changed 14 months ago by nthiery

As you notice, I am going through the changes. Up to those details, it looks good :-)

comment:18 Changed 14 months ago by nthiery

About _divide_if_possible_: since we are moving it anyway, shall we use the occasion to put it somewhere meaningful? Maybe as a method in EuclideanDomains?, as x._divide_if_possible(r), next to quo_rem which it depends on?

comment:19 Changed 14 months ago by nthiery

I would move the comment about handling old pickles in the doc of CombinatorialFreeModule.Element.__setstate__, with a trac ref. Please also add a brief comment and trac ref for the unpickle_override at the end of the file.

comment:20 Changed 14 months ago by nthiery

Could you elaborate a bit why we need CombinatorialFreeModule.Element to be a subclass of IndexedFreeModuleElement? In particular, can you provide a minimal non-working example?

comment:21 Changed 14 months ago by nthiery

# TODO: move the content of this class to CombinatorialFreeModule.Element and ModulesWithBasis.Element
cdef class IndexedFreeModuleElement(Element):

The TODO could be updated :-)

comment:22 Changed 14 months ago by nthiery

I am wondering whether the printing methods (_sorted_items_for_printing, latex, repr, asciiart, ...) should be moved to Modules.WithBasis.ElementMethods. We are moving them anyway, and I believe they would be a reasonable default implementation. That would require providing a default value for parent._print_options though, and deciding for a generic idiom to run through the items.

What do you think?

We could also keep that for a later ticket.

comment:23 Changed 14 months ago by nthiery

Instead of sage.modules.with_basis.indexed_free_module_element, we could use the shorter sage.modules.with_basis.element. That would be consistent with the nearby morphism module. I don't foresee other element classes in this module that would not be element classes for IndexedFreeModule.

comment:24 Changed 14 months ago by nthiery

Users will have code importing CombinatorialFreeModuleElement. We should support them with a deprecation alias "Please use CombinatorialFreeModule.Element or IndexedFreeModuleElement."

If we wan't to be even kinder to our users, helping them prepare for the next step, we could have sage.modules.with_basis.indexed_free_module.IndexedFreeModule (or just .free_module.?) be an alias for CombinatorialFreeModuleElement. Then the above message warning would suggest IndexedFreeModule.Element.

comment:25 Changed 14 months ago by git

  • Commit changed from d87735db11bdeab38d4932ca3b46abba8d4ba185 to f66cb0d2a72a70fb65d22bc115d75d4e85614899

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

fbefa66Merge branch 'public/combinat/cythonize_CFM_element-22632' of git://trac.sagemath.org/sage into public/combinat/cythonize_CFM_element-22632
68cdf67Fixing things from testing.
99c99bfMoving _divide_if_possible to EuclideanDomains.
cafb215Remove map_coefficients call in __truediv__.
a8eeca6Remove comment and deprecate CombinatorialFreeModuleElement.
6b96942Rename indexed_free_module_element to indexed_element.
f66cb0dUpdating tutorial.

comment:26 Changed 14 months ago by git

  • Commit changed from f66cb0d2a72a70fb65d22bc115d75d4e85614899 to e0553bef39dbcee0dbaf72e6e38f9ad93f87d1c3

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

e0553beAdding comments about pickles.

comment:27 follow-up: Changed 14 months ago by tscrim

  • comment:15 I added a comment. Feel free to change. I also agree that a tutorial update should be done on a separate ticket.
  • comment:16 I had separated that in order to track down a bug (4ee3313).
  • comment:18 Good point. Done
  • comment:19 I feel these are basically useless to repeating what the code makes (more) clear, but added.
  • comment:20 This doesn't work with any subclasses where you need a _mul_ from the category. Change it and try to multiply two symmetric group algebra elements for example:
    sage: SymmetricGroupAlgebra(QQ, 3)
    Symmetric group algebra of order 3 over Rational Field
    sage: prod(_.algebra_generators())
    ...
    TypeError: 'NotImplementedType' object is not callable
    
    There were also pickling issues.
  • comment:21 Done.
  • comment:22 -1 as that is a little too close to enforcing elements being printed as sums, which is not what we want.
  • comment:23 I changed the file name to indexed_element as element is too generic for my tastes, but I left the class name the same.
  • comment:24 Done, but I slightly disagree with needing a deprecation because it was never imported into the global namespace. However, it was in the (public) doc, so it is good to have it. At this point, I think we should reference both and let the user decide.

comment:28 Changed 14 months ago by git

  • Commit changed from e0553bef39dbcee0dbaf72e6e38f9ad93f87d1c3 to b21fb167ab9562160ba5650e03ffd44a68be2c37

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

b21fb1622632: just a touch of polishing on the thematic tutorial change

comment:29 Changed 14 months ago by git

  • Commit changed from b21fb167ab9562160ba5650e03ffd44a68be2c37 to b13a870be54a27bfa1f2f71230256defc5b0d3a9

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

b13a87022632: use trac role instead of full url in doc

comment:30 in reply to: ↑ 27 Changed 14 months ago by nthiery

Replying to tscrim:

  • comment:15 I added a comment. Feel free to change.

Thanks; I did a second pass on it. Good to go.

  • comment:22 -1 as that is a little too close to enforcing elements being printed as sums, which is not what we want.

I see it as merely providing a sane default which works generically but can be overridden at will. Anyway, that's admittedly out of scope for this ticket; we can decide later on.

  • comment:23 I changed the file name to indexed_element as element is too generic for my tastes, but I left the class name the same.

Sounds good.

it was never imported into the global namespace. However, it was in the (public) doc, so it is good to have it.

Yup, exactly.

At this point, I think we should reference both and let the user decide.

Ok!

Out of curiosity, I am now going to have a quick look at the inheritance thing of comment:20. Other than that, it's good to go; thanks for all the hard work!

comment:31 Changed 14 months ago by git

  • Commit changed from b13a870be54a27bfa1f2f71230256defc5b0d3a9 to dec9bd65d49e91af6c662b658e838b1476306ec5

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

dec9bd622632: make CombinatorialFreeModule.Element an alias (and not subclass) of IndexedFreeModuleElement

comment:32 Changed 14 months ago by nthiery

Advantage of the above commit:

  • A bit simpler: no distinction anymore between CFF.Element and IndexedFreeModuleElement. In particular there is no risk to have someone use directly IndexedFreeModule? without inheriting from it.
  • Avoids a double inheritance, with CFF.element_class deriving from CFF.Element itself deriving from IndexedFreeModuleElement

Inconvenient:

  • requires to override element_class

I believe it's worth it. What do you think?

comment:33 Changed 14 months ago by nthiery

Running tests here ...

comment:34 follow-up: Changed 14 months ago by tscrim

I am not so convinced as it hides a fault in a non-trivial way; it something that we should not need to do. I do agree it is more simple. Nevertheless, one should typically use a subclass of the CFM.Element when subclassing CFM and needing a new element class if they want to use the same data structures. Although I don't think there is too much difference between our two hacks.

Also, in some ways it almost looks like you are moving the unpickling to a completely unrelated class since

register_unpickle_override("sage.combinat.free_module",
                           "CombinatorialFreeModuleElement",
                           CombinatorialFreeModule.Element)

If you want the __setstate__ in IndexedFreeModuleElement, then this register_unpickle_override should redirect to that.

comment:35 Changed 14 months ago by git

  • Commit changed from dec9bd65d49e91af6c662b658e838b1476306ec5 to 6665822c21ba3765553f3df12e640c5042958d0d

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

666582222632: revert b13a870be: the trac link is in an error message!

comment:36 Changed 14 months ago by git

  • Commit changed from 6665822c21ba3765553f3df12e640c5042958d0d to 4a77584f43adbbc36b279591929a7a4370292ad3

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

076d7cb22632: revert b13a870be: the trac link is in an error message!
4a7758422632: let register_pickle_override refer to IndexedFreeModuleElement and move it close by

comment:37 in reply to: ↑ 34 Changed 14 months ago by nthiery

Replying to tscrim:

I am not so convinced as it hides a fault in a non-trivial way; it something that we should not need to do. I do agree it is more simple. Nevertheless, one should typically use a subclass of the CFM.Element when subclassing CFM and needing a new element class if they want to use the same data structures. Although I don't think there is too much difference between our two hacks.

Ok. I agree, it's minor anyway.

Also, in some ways it almost looks like you are moving the unpickling to a completely unrelated class since

register_unpickle_override("sage.combinat.free_module",
                           "CombinatorialFreeModuleElement",
                           CombinatorialFreeModule.Element)

If you want the __setstate__ in IndexedFreeModuleElement, then this register_unpickle_override should redirect to that.

Good point. Fixed. This prompted me to move the register_unpickle_overide next to IndexedFreeModuleElement.

Sorry for the forced-push; I had screwed up my commit just before.

Altogether, I believe this is good to go!

comment:38 Changed 14 months ago by nthiery

  • Reviewers set to Nicolas M. Thiéry
  • Status changed from needs_review to positive_review

comment:39 Changed 14 months ago by nthiery

Oh, I forgot about cafb215ba2b808e: what's the rationale for replacing .map_coefficients by what looks like hand written equivalent?

comment:40 Changed 14 months ago by nthiery

  • Status changed from positive_review to needs_work

Oops, failing tests. Probably a triviality. Investigating.

comment:41 Changed 14 months ago by git

  • Commit changed from 4a77584f43adbbc36b279591929a7a4370292ad3 to 06a299e1c6d6734ec4930dc4f720dca5a4ead6ad

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

06a299e22632: fix typo in attribute name

comment:42 Changed 14 months ago by nthiery

It comes from the same commit :-) Just a typo in _monomial_cofficients. Fixed.


New commits:

06a299e22632: fix typo in attribute name

comment:43 Changed 14 months ago by nthiery

  • Status changed from needs_work to needs_review

comment:44 Changed 14 months ago by nthiery

sage -t src/sage/homology/simplicial_complex.py  # 1 doctest failed
sage -t src/sage/algebras/iwahori_hecke_algebra.py  # 18 doctests failed
sage -t src/sage/calculus/calculus.py  # 1 doctest failed
sage -t src/sage/categories/sets_cat.py  # 1 doctest failed
sage -t src/sage/categories/hopf_algebras_with_basis.py  # 1 doctest failed
sage -t src/sage/categories/algebras_with_basis.py  # 1 doctest failed
sage -t src/sage/combinat/free_module.py  # 1 doctest failed

Two types of failures:

...
        return type(self)(F, {k: c._divide_if_possible(x)
      File "sage/structure/element.pyx", line 459, in sage.structure.element.Element.__getattr__ (/opt/sage/src/build/cythonized/sage/structure/element.c:4256)
        return self.getattr_from_category(name)
      File "sage/structure/element.pyx", line 472, in sage.structure.element.Element.getattr_from_category (/opt/sage/src/build/cythonized/sage/structure/element.c:4365)
        return getattr_from_other_class(self, cls, name)
      File "sage/structure/misc.pyx", line 300, in sage.structure.misc.getattr_from_other_class (/opt/sage/src/build/cythonized/sage/structure/misc.c:1933)
        raise dummy_attribute_error
    AttributeError: 'sage.rings.polynomial.laurent_polynomial.LaurentPolynomial_univariate' object has no attribute '_divide_if_possible'

and trivial one about the element_class name. Working on the latter.

comment:45 follow-up: Changed 14 months ago by nthiery

The former probably comes from a parent whose categories are not initialized.

comment:46 in reply to: ↑ 45 Changed 14 months ago by tscrim

Replying to nthiery:

The former probably comes from a parent whose categories are not initialized.

The problem comes from the fact that Laurent polynomials are not in Euclidean domains. There are also a number of natural rings that are not Euclidean domains, but have a quo_rem that we could at least try this with (e.g., Z[x]). So I'm thinking of demoting it back down from the category.

comment:47 follow-up: Changed 14 months ago by nthiery

I just found out the same :-) Yeah, either demoting it back down, or lifting it up to Rings(). After all, it's a private method. So if it fails because it requires another method which is not implemented, that's ok. At least it will be easier to discover than if it's hidden in some random Python module. It's consistent with FreeModule?'s requirement of taking a ring as input.

comment:48 follow-up: Changed 14 months ago by nthiery

For the other failure: it stems from the fact that the created element class's name is set to reflect that it's the element class of a given parent:

sage: A = Algebras(QQ).WithBasis().example()
sage: A.element_class
<class 'sage.combinat.free_module.FreeAlgebra_with_category.element_class'>

However the work is half baked, since the module is not set accordingly: there is no class sage.combinat.free_module.FreeAlgebra; the module part comes from CombinatorialFreeModuleElement.__module__ (I am running this example without the ticket). With the ...Element being moved, the module part gets changed to sage.modules.with_basis.indexed_element.

Two options:

  • Not care and just update the doctests
  • Improve the output of the element class by setting the module of the parent as module.

I just implemented the latter to check that it worked. The end result is more consistent for the user; here we get:

<class 'sage.categories.examples.algebras_with_basis.FreeAlgebra_with_category.element_class'>

However changing __module__ might possibly break some introspection stuff (I checked A.element_class??, and that was fine). It will also require updating other doctests.

What do you think?

comment:49 Changed 14 months ago by git

  • Commit changed from 06a299e1c6d6734ec4930dc4f720dca5a4ead6ad to c889c4e9d791e692bec161f7c5bcc6afea8f4615

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

c889c4e22632: Fix the module part in dynamically created element classes, for consistency

comment:50 Changed 14 months ago by git

  • Commit changed from c889c4e9d791e692bec161f7c5bcc6afea8f4615 to 5a34041b0ab06dfbe1089698d50075c0525e066c

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

23f28c0Moving _divide_if_possible to Rings.
5a34041Merge branch 'public/combinat/cythonize_CFM_element-22632' of git://trac.sagemath.org/sage into public/combinat/cythonize_CFM_element-22632

comment:51 in reply to: ↑ 47 Changed 14 months ago by tscrim

Replying to nthiery:

I just found out the same :-) Yeah, either demoting it back down, or lifting it up to Rings(). After all, it's a private method. So if it fails because it requires another method which is not implemented, that's ok. At least it will be easier to discover than if it's hidden in some random Python module. It's consistent with FreeModule?'s requirement of taking a ring as input.

I think lifting it up to the category of Rings works for now.

comment:52 in reply to: ↑ 48 Changed 14 months ago by tscrim

Replying to nthiery:

For the other failure: it stems from the fact that the created element class's name is set to reflect that it's the element class of a given ... Two options:

  • Not care and just update the doctests
  • Improve the output of the element class by setting the module of the parent as module.

What do you think?

This seems to be a can of worms. :/ Although I would rather have the latter as well since it is a more proper fix. Since you've done it, we might as well keep it.

comment:53 Changed 14 months ago by nthiery

Ok; tests running here. Let's keep it only if there are just trivial doctests updates.

comment:54 Changed 14 months ago by git

  • Commit changed from 5a34041b0ab06dfbe1089698d50075c0525e066c to 4c63230f181aebf2b24ea6bd14d9868cce3dbef8

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

7cd9c4c22632: trivial doctest updates (element_class names)
4c63230Merge branch 'public/combinat/cythonize_CFM_element-22632' of trac.sagemath.org:sage into t/22632/public/combinat/cythonize_CFM_element-22632

comment:55 Changed 14 months ago by git

  • Commit changed from 4c63230f181aebf2b24ea6bd14d9868cce3dbef8 to b11d26e6fbd0fa2668b242e13c006fe57510ebb2

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

b11d26e22632: trivial indentation fix

comment:56 Changed 14 months ago by nthiery

All doctests updates were trivial. Being tired, I may have missed a few. Please rerun the tests, and if all goes well, or there just are some more trivial doctest updates, you can set a positive review on my behalf.

Cheers

comment:57 Changed 14 months ago by tscrim

  • Status changed from needs_review to positive_review

Tests pass for me too.

comment:58 Changed 14 months ago by tscrim

Thank you for the review.

comment:59 Changed 14 months ago by nthiery

My pleasure! I am glad this is done.

comment:60 Changed 14 months ago by vbraun

  • Status changed from positive_review to needs_work

PDF docs dont build

comment:61 Changed 14 months ago by nthiery

Compiling the doc here ...

comment:62 Changed 14 months ago by git

  • Commit changed from b11d26e6fbd0fa2668b242e13c006fe57510ebb2 to 20cd0dafdc07517145c3d8a20cbf8baa08e334dc

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

20cd0da22632: fixed ReST typo preventing the pdf doc compilation

comment:63 Changed 14 months ago by nthiery

Arg, the exact same _mul_ mistake has appeared a couple days ago in some other ticket.

I'll set back a positive review when the pdf doc compilation will be finished, in case there wouldbe something else.

Thanks Volker for reporting ...

comment:64 Changed 14 months ago by nthiery

The only other error I get is:

[docpdf] l.42 \addto
[docpdf]            \extrasmagyar{\def\pageautorefname{page}}

And I assume this is related to an outdate latex install on my machine:

[docpdf] Package sphinx Warning: 
[docpdf] ******** ERROR !! PLEASE UPDATE titlesec.sty !!********
[docpdf] ******** THIS VERSION SWALLOWS SECTION NUMBERS.********.

So, putting this back to positive review. Travis, can you double check things compile on your machine?

comment:65 Changed 14 months ago by nthiery

  • Status changed from needs_work to positive_review

comment:66 Changed 14 months ago by tscrim

pdf doc built for me too.

comment:67 Changed 14 months ago by vbraun

  • Branch changed from public/combinat/cythonize_CFM_element-22632 to 20cd0dafdc07517145c3d8a20cbf8baa08e334dc
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:68 Changed 12 months ago by jdemeyer

  • Commit 20cd0dafdc07517145c3d8a20cbf8baa08e334dc deleted

Question: what exactly is the purpose of the condition involving is_extension_type() in __make_element_class__?

I am trying to understand how/why is_extension_type is used in Sage. In other places in parent.pyx, it is to determine whether __class__ can be assigned to. But in __make_element_class__, it's not so clear to me.

(I know it's not directly related to this ticket, but git blame brought me here since this ticket made changes to __make_element_class__)

comment:69 follow-up: Changed 12 months ago by nthiery

Hi Jeroen!

In make_element_class, we need to decide how elements shall inherit from categories: either by subclassing P.Element (or the relevant class), or by using the getattr trick. The current rule is to subclass if P.Element is a Python class, and use getattr if P.Element is an extension type. is_extension_type is used to do the test.

comment:70 in reply to: ↑ 69 ; follow-up: Changed 12 months ago by jdemeyer

Thanks. That answers the factual question ("how is it done?") but not really the reason.

There are many differences between Python and Cython classes and I'm trying to understand which property matters here. I am asking because I tried to always use the dynamic class (using inherit=True in __make_element_class__ even for Cython element classes) and there is not much that breaks.

These are the main differences between Python and Cython classes that I can think of:

  1. The fact that __class__ can be assigned to for Python classes (I don't think this is the reason here)
  1. The fact that Python classes have a __dict__ (this is no longer true: Python classes with __slots__ don't have a __dict__ by default and Cython classes do support __dict__ if you declare it as attribute)
  1. The fact that Python classes always support multiple inheritance, which may or may not work for Cython classes
  1. Pickling (although Cython 0.26 does support pickling of Cython classes)
  1. Various performance differences
  1. ...

comment:71 in reply to: ↑ 70 Changed 12 months ago by jdemeyer

Replying to jdemeyer:

I am asking because I tried to always use the dynamic class (using inherit=True in __make_element_class__ even for Cython element classes) and there is not much that breaks.

To elaborate on this: after making this change

  • src/sage/structure/parent.pyx

    diff --git a/src/sage/structure/parent.pyx b/src/sage/structure/parent.pyx
    index a387136..ea7c60c 100644
    a b cdef class Parent(sage.structure.category_object.CategoryObject): 
    571571        # By default, don't fiddle with extension types yet; inheritance from
    572572        # categories will probably be achieved in a different way
    573573        if inherit is None:
    574             inherit = not is_extension_type(cls)
     574            inherit = True
    575575        if inherit:
    576576            if name is None:
    577577                name = "%s_with_category"%cls.__name__

I ran all doctests in rings, categories and structure and the only non-trivial doctest failures were involving enumerated sets (src/sage/categories/examples/infinite_enumerated_sets.py, src/sage/categories/sets_cat.py, src/sage/categories/enumerated_sets.py)

comment:72 Changed 12 months ago by nthiery

Hi Jeroen,

Thanks for running this interesting experiment!

I indeed would have been expecting things not too break too much. Systematically using dynamic classes would certainly simplify Sage's infrastructure. The only potential reason for not doing it is performance (speed and memory footprint). At the time we set this up, there was some consensual claim that systematically using a dynamic class would induce a performance loss for low granularity objects (e.g. finite field elements). Hence the above rule of thumb I implemented for deciding when to do what.

However I don't remember anyone doing some serious benchmarking to actually assess the validity of that claim. That would be very welcome! And this hints again at having some speed-regression test infrastructure for Sage.

Cheers,

Nicolas

PS: I could imagine code breaking in situations like:

cdef class MyElement:
    ....

cdef foo(MyElement x):
    x.bar()

where foo would be called on an instance of a dynamic subclass of MyElement, and foo be provided by some category.

Apparently we have no instance of that idiom in Sage :-)

comment:73 Changed 12 months ago by jdemeyer

Comments on this actual ticket: contrary to most element classes which are implemented in Cython, it seems that CombinatorialFreeModule_with_category.element_class actually does do the inheritance from the category in the "normal" way, using dynamic_class(), just like Python classes. So this is a good testcase for #23435.

comment:74 Changed 12 months ago by jdemeyer

In the light of #23435, is it important that CombinatorialFreeModule_with_category.element_class has a __dict__? In other words, is it important to support the following (example taken from src/doc/en/thematic_tutorials/tutorial-objects-and-classes.rst):

Some particular actions modify the data structure of ``el``::

    sage: el.rename("bla")
    sage: el
    bla

.. note::

    The class is stored in a particular attribute called ``__class__``,
    and the normal attributes are stored in a dictionary called ``__dict__``::

        sage: F = CombinatorialFreeModule(QQ, Permutations())
        sage: el = 3*F([1,3,2])+ F([1,2,3])
        sage: el.rename("foo")
        sage: el.blah = 42
        sage: el.__class__
        <class 'sage.combinat.free_module.CombinatorialFreeModule_with_category.element_class'>
        sage: el.__dict__
        {'__custom_name': 'foo',
         'blah': 42}

comment:75 follow-up: Changed 12 months ago by jdemeyer

Another question about this ticket: why are the arithmetic methods of IndexedFreeModuleElement implemented as cdef instead of cpdef?

    cdef _add_(self, other):

Every other class (except for IndexedFreeModuleElement and LieAlgebraElement) implements those as cpdef _add_.

This is confusing because

sage: F = CombinatorialFreeModule(QQ, Permutations())
sage: el = 3*F([1,3,2])+ F([1,2,3])
sage: el._add_(el)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-31-91def7298b70> in <module>()
----> 1 el._add_(el)

TypeError: 'NotImplementedType' object is not callable

It also prevents a Python class inheriting from IndexedFreeModuleElement to override this _add_.

comment:76 in reply to: ↑ 75 ; follow-up: Changed 12 months ago by tscrim

Replying to jdemeyer:

Another question about this ticket: why are the arithmetic methods of IndexedFreeModuleElement implemented as cdef instead of cpdef?

    cdef _add_(self, other):

Every other class (except for IndexedFreeModuleElement and LieAlgebraElement) implements those as cpdef _add_.

That is not quite true. They are cdef in Element, and so I followed suit. I see now in the doc for Element, that it says it should be cpdef. Is it because Element is special in that they are essentially acting as pure virtual methods that they aren't cpdef?

comment:77 Changed 12 months ago by jdemeyer

Follow-up: #23440

comment:78 in reply to: ↑ 76 Changed 12 months ago by jdemeyer

Replying to tscrim:

That is not quite true. They are cdef in Element, and so I followed suit. I see now in the doc for Element, that it says it should be cpdef. Is it because Element is special in that they are essentially acting as pure virtual methods that they aren't cpdef?

Yes, the Element base class is special. The arithmetic methods of Element do indeed act as "pure virtual" methods. I implemented them that way to allow fast calling in the Cython world while at the same time not existing in the Python world.

Note: See TracTickets for help on using tickets.