Make parent/element classes independent of base rings

[simon-king-jena]

At #11900 and sage-combinat-devel, as well as in some comments in sage/categories/category.py, the idea was discussed to make, for example, Algebras(GF(3)).parent_class==Algebras(GF(5)).parent_class - hence, make the parent/element classes as independent from the base of a category as possible.

This is implemented in this patch by introducing an abstract class
CategoryWithParameters which uses pickling by "weak construction" for
its element and parent classes. Now:

• For a join category, the parent/element class depend only on the
  parent/element class of its super categories.
• For a Category_over_base (e.g. Modules, Algebras, Schemes, ...), the
  parent/element class depend only on the category of the base.
• For a bimodule, the parent/element class depend only on the category
  of the left and right bases.

In the process, this patch also:

• Adds a method Category._make_named_class providing a unified way to
  create parent and element classes (and later on morphism classes)
• Extends the interface of dynamic_class to customize caching and pickling
• Rename the experimental class IdempotentSemigroups.ElementMethods
  and remove its super class, and discards unused code there.

Apply

• attachment: trac11935_weak_pickling_by_construction-nt.patch
• attachment: trac_11935-weak_pickling_by_construction-review-ts.patch

Depends on #9138
Depends on #11900
Depends on #11943
Depends on #12875
Depends on #12876
Depends on #12877

CC: @jdemeyer @sagetrac-sage-combinat

Component: categories

Keywords: parent class, element class

Author: Simon King

Reviewer: Nicolas M. Thiéry, Travis Scrimshaw

Merged: sage-5.11.beta1

Issue created by migration from https://trac.sagemath.org/ticket/11935

[simon-king-jena]

comment:1

Concerning uniqueness of the parent class: In at least one case (namely Algebras(R)), the super categories depend on whether the base ring is a field or not. We would like to have

sage: Algebras(ZZ).parent_class != Algebras(GF(3)).parent_class == Algebras(QQ).parent_class
True

The idea is that the parent and element classes should only depend on the super categories, but otherwise should be independent from the base ring. Working at #11900, I found that this would drastically improve the performance of some elliptic curve computation.

[simon-king-jena]

comment:2

A problem may be seen in pickling. Before explaining the problem, let me remark that I don't see a big concern for "pickling a parent class": What we actually want to pickle is a parent, not just a naked class. The serialisation data of a polynomial ring, for example, will comprise the base ring, the generator names and the term order, but certainly the class of the polynomial ring will not be part of the pickle.

However, if we do want to serialise a naked parent or element class, we have the following problems:

Currently, C.parent_class is pickled by getattr, (C,"parent_class"). The pickling data (hence, C) is part of the cache key of a dynamic class. With that, the parent class of different categories C1 and C2 can't be the same.

I see three approaches to get rid of it.

1. Remove the pickling data from the cache key of dynamic classes
2. Make pickling of C.parent_class just rely on the default way of pickling a dynamic class
3. Work around the cache of dynamic classes, but still use getattr,(C,"parent_class") for pickling.

I think 1. is not gonna happen. It would break a lot of code, I suppose.

I had tested 2. and 3. while working on #11900. Both would work, but there are different conerns concerning long-term stability.

2. means:

   The pickle of a parent class will only depend on the category graph as it was on the time of pickling. If the category graph changes between pickling and unpickling the parent class, you would get a different class.

3. would be a bit more stable.

   The idea is:

   (i) In the lazy attribute parent_class(), the dynamic class is first created without providing the reduction data (as in approach 2.).
   (ii) Before returning that dynamic class, it is tested whether the reduction data is still none. If it is, the getattr, (C,"parent_class") thingy is inserted.

   Consequence: Algebras(QQ).parent_class could, for example, be unpickled as Algebras(GF(2)).parent_class - which is not a big problem, since we want them to be the same. However, if in a distant future we want them to be different again, we'd be in trouble...

I suggest that I create patches for both 2. and 3., and then people can tell what they think about it. The method resolution will then be taken care of by another patch.

[nthiery]

comment:3

Replying to @simon-king-jena:

A problem may be seen in pickling. Before explaining the problem, let me remark that I don't see a big concern for "pickling a parent class":

True: all parents ought to be pickled "by construction" rather than by
"class + internal data", in order to encapsulate as much as possible
of the data structure. This probably ought to be true as well for
elements. I don't know how far we are from this.

A good thing to do at this point would be to search through the sage
pickle jar for how many parent_class's and element_class's are pickled
there. And why. I don't know how complicated it is to do this search
though.

Among the three propositions, I like 3 best. I have trouble evaluating
how big the risks are to get stuck in the future. It does not seem too
big.

Thanks Simon for investigating this!

[simon-king-jena]

comment:4

Replying to @simon-king-jena:

I suggest that I create patches for both 2. and 3., and then people can tell what they think about it. The method resolution will then be taken care of by another patch.

I just argued myself into splitting the ticket: This here will be for the base ring independent parent/element classes, and another one will be for method resolution order.

[simon-king-jena]

comment:5

Replying to @nthiery:

A good thing to do at this point would be to search through the sage
pickle jar for how many parent_class's and element_class's are pickled
there.

Old pickles will not break, I believe. Let P3 = Algebras(GF(3)).parent_class and PQ = Algebras(QQ).parent_class. Here are a few scenarios:

1. P3 and PQ have been created and pickled with an old version of Sage

In the old version of Sage, P3!=PQ. They are pickled by construction. Hence, after applying my yet-to-be-submitted patches, they are unpickled as Algebras(GF(3)).parent_class and Algebras(QQ).parent_class - which is the same class after applying the patch.

Conclusion: An old pickle will not break, with either approach 2. or 3. The worst what could happen is P3!=PQ before pickling and P3==PQ after unpickling. But the defining property P3==Algebras(GF(3)).parent_class and PQ==Algebras(QQ).parent_class is preserved.

2. P3 and PQ are created and pickled according to approach 2. from above

Of course, P3==PQ at the time of pickling. The pickle will only depend on the parent classes of the super categories of Algebras(GF(3)) and Algebras(QQ). If there was a change in the super categories between pickling and unpickling, we would have P3!=Algebras(GF(3)).parent_class after unpickling.

Conclusion: A new pickle of P3 and PQ can be unpickled after a change in the category graph, but a change in the category graph will destroy the defining property P3==Algebras(GF(3)).parent_class.

3. P3 and PQ are created and pickled according to approach 3. from above

Of course, P3==PQ at the time of pickling. PQ and P3 will both be pickled by construction. In particular, a change in the category graph would not matter, as long as the super categories of Algebras(QQ) and Algebras(GF(3)) still coincide (up to the base ring) after the change in the category graph.

A problem would arise if, in a distant future, the super categories of Algebras(QQ) and Algebras(GF(3)) would become essentially different. Say, some algebra person finds that vector spaces over fraction fields should have their own category, different from the usual category of vector spaces. Then, Algebras(QQ).parent_class!=Algebras(GF(3)).parent_class. In particular, after such change, unpickling P3 or PQ would result in either PQ!=Algebras(QQ).parent_class or P3!=Algebras(GF(3)).parent_class.

Conclusion: A new pickle of P3 and PQ can be unpickled after a change in the category graph. Most changes in the category graph will preserve the defining property P3==Algebras(GF(3)).parent_class and PQ==Algebras(QQ).parent_class after unpickling. However, if the super categories will depend on the base ring in a different way as it is now, then either P3 or PQ will lose the defining property after unpickling, while the other will keep the defining property - and we don't know which of the two will break.

---

It seems to me that approach 3. is less fragile than 2. But I believe that in applications (hence, for pickling parents) both should be fine. So, I'll prepare patches for both approaches.

[simon-king-jena]

Use default pickling for parent/element classes, making them base ring independent.

[simon-king-jena]

comment:6

Attachment: trac11935_use_default_pickling.patch.gz

The patch that I just attached implements approach 2., hence, it uses the default pickling of dynamic classes. By consequence, the parent class of a category C will only depend on C.ParentMethods and on the parent classes of the super categories of C, but it will only depend on the base ring of C if the base ring changes the super categories (which holds for algebras, e.g.).

Note the effect on the computation time for elliptic curves. With sage-4.7.2.alpha3 plus #11900, we have

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.97 s, sys: 0.07 s, total: 4.04 s
Wall time: 4.18 s

but with the new patch on top of it, we have

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.11 s, sys: 0.06 s, total: 3.17 s
Wall time: 3.31 s

[simon-king-jena]

Author: Simon King

[simon-king-jena]

Attachment: trac11935_weak_pickling_by_construction.patch.gz

Use a weak form of "pickling by construction" for parent and element classes of categories

[simon-king-jena]

comment:7

The second patch is posted as well. It implements approach 3. Hence, the parent_class lazy attribute works around the cache of dynamic classes (by not providing unpickling information when the class is created), inserting the unpickling information only when the class has not been found in cache.

By consequence, when first creating Algebras(QQ).parent_class, then its cache key as a dynamic class only comprises the parent classes of the super categories. Before returning it, the unpickling data (by construction) is added. When Algebras(GF(3)).parent_class is created later, it is found in the cache of dynamic classes and immediately returned. The class returned will thus be unpickled as Algebras(QQ).parent_class.

Similar to the first patch, it considerably speeds up the elliptic curve computations:

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.05 s, sys: 0.07 s, total: 3.12 s
Wall time: 3.27 s

Apply only one of the two patches, at your choice!

[nthiery]

comment:8

Replying to @simon-king-jena:

Replying to @nthiery:

A good thing to do at this point would be to search through the sage
pickle jar for how many parent_class's and element_class's are pickled
there.

Old pickles will not break, I believe.

This is my belief too! Sorry if I have been unclear, but that was not the point of my suggestion. What I wanted to know whether currently most parents and elements were pickled by construction or by "class + data". If they already are pickled by construction, then how C.parent_class and C.element_class are pickled is mostly irrelevant, now and in the future, since it is seldom used.

Thanks in any cases for you detailed analysis!

It seems to me that approach 3. is less fragile than 2.

+1

Let's see if someone else has some preference between the two implementations.

Cheers,
Nicolas

[simon-king-jena]

comment:9

Replying to @nthiery:

What I wanted to know whether currently most parents and elements were pickled by construction or by "class + data".

I see. If I am not mistaken, if it is pickled by "class+data", then copy_reg._reconstructor is called at unpickling. Perhaps it is possible to modify _reconstructor, so that it writes data to some log file. In that way, we could find out how often it is actually used.

[nthiery]

comment:10

Replying to @simon-king-jena:

Replying to @nthiery:

What I wanted to know whether currently most parents and elements were pickled by construction or by "class + data".

I see. If I am not mistaken, if it is pickled by "class+data", then copy_reg._reconstructor is called at unpickling. Perhaps it is possible to modify _reconstructor, so that it writes data to some log file. In that way, we could find out how often it is actually used.

Yup. Or run explain_pickle on all pickles, and grep for element_class / parent_class.

[simon-king-jena]

comment:11

Replying to @nthiery:

Yup. Or run explain_pickle on all pickles, and grep for element_class / parent_class.

I don't know about explain_pickle. Where can I find it?

I am now running sage -testall -long with the _reconstructor log. So far, only ZODB.fsIndex.fsIndex and matplotlib.font_manager.FontEntry use it, but we will see if there's more.

[simon-king-jena]

comment:12

sage -testall -long succeeded (with the second patch applied, but it would probably work with thee first one as well), and copy_reg._reconstructor was only used on <class 'matplotlib.font_manager.FontEntry'>, <class 'ZODB.fsIndex.fsIndex'> and <class 'sage.misc.explain_pickle.EmptyNewstyleClass'>.

Hence, it indicates that "pickling by class and data" does not occur for parents. But, to be on the safe side, one should inspect the pickle jar using explain_pickle.

[jdemeyer]

Changed dependencies from #11900 to #9138, #11900

[simon-king-jena]

comment:14

sage -testall -long passes for either patch. So, unless we will find bad surprises in the pickle jar, both approaches should be fine. I am slightly in favour of approah 3.

[simon-king-jena]

comment:15

I decided to make this ticket depend on #11943, for two reasons: Firstly, it is rather clear that #11943 is a good idea, while I am less sure here (it is good for speed, but may under very particular circumstances break new pickles). Secondly, #11943 seems less invasive than the patch here.

I think that the "potentially breaking new pickles in a distant future" aspect is less urgent with the "weak pickling by construction" approach. Hence, I have only updated the second patch, the first can now be disregarded.

Apply trac11935_weak_pickling_by_construction_rel11943.patch

[simon-king-jena]

Changed dependencies from #9138, #11900 to #9138 #11900 #11943

[simon-king-jena]

comment:112

But who can review it? I guess as the author, I am only entitled to tell whether I am fine with the changes made by Nicolas and Travis.

So, what else can I do? #12895, or is there something more urgent?

[simon-king-jena]

comment:113

For the record: I think Travis' patch is fine.

[nthiery]

comment:114

I already reviewed your things. So if you are happy with my changes, then it's good to go!

Yes, #12895 is next on the list!

Thanks!

[simon-king-jena]

comment:115

I think Nicolas' changes look fine, too. But let's wait for the tests to finish.

[tscrim]

Attachment: trac_11935-weak_pickling_by_construction-review-ts.patch.gz

[tscrim]

comment:116

All tests had passed. However I've uploaded a tweaked review patch which changes the doctest line continuations to the new format.

Apply: trac11935_weak_pickling_by_construction-nt.patch trac_11935-weak_pickling_by_construction-review-ts.patch

[nthiery]

comment:117

Ok. +1 on Travis's new patch.

[simon-king-jena]

comment:118

Travis' changes look good. So, a final make ptestlong, and then we'll hopefully get it over with.

[simon-king-jena]

comment:119

The patchbot finds that all tests pass. On my laptop, tests aren't finished yet, but nothing has failed so far.

The startup.modules script complains that now the inspect module is loaded. This is a bit surprising to me, because I thought that the inspect module is loaded during startup anyway (it is frequently used). But I think there is not much need to worry---and the startup-time plugin does not complain.

The doctest continuation plugin complains about the first patch, but I just verified that the second patch fixes it.

And given all the comments above, I hope I am no entitled to change the status to "positive_review"---complain if you disagree.

[nthiery]

comment:120

Yippee :-)

[nthiery]

comment:122

Hi Jeroen,

Replying to @jdemeyer:

Milestone changed from sage-5.10 to sage-5.11

Ah shoot, it would have been helpful to have a clean base including those patches for the work on the subsequent category patches.

I assume you are in the process of cutting a rc0? Do you have some approximate schedule for 5.11?

Thanks!
Nicolas

[jdemeyer]

comment:123

Replying to @nthiery:

Ah shoot, it would have been helpful to have a clean base including those patches for the work on the subsequent category patches.

Well, given that these kind of patches are notorious for breaking things, I don't want to merge this in an rc. This patch is scheduled for sage-5.11.beta1 (with #12876 in beta0).

Do you have some approximate schedule for 5.11?

What do you mean?

[nthiery]

comment:124

Replying to @jdemeyer:

Replying to @nthiery:

Ah shoot, it would have been helpful to have a clean base including those patches for the work on the subsequent category patches.

Well, given that these kind of patches are notorious for breaking things, I don't want to merge this in an rc.

Fair enough :-)

This patch is scheduled for sage-5.11.beta1 (with #12876 in beta0).

Good point; we only need to have them in a beta, not necessarily for a final release.

Do you have some approximate schedule for 5.11?

What do you mean?

Roughly speaking when do you foresee 5.11.beta1 to be out?

Thanks!

[jdemeyer]

comment:125

Replying to @nthiery:

Roughly speaking when do you foresee 5.11.beta1 to be out?

I have no idea. It mainly depends on #13245 and #14699.

[jdemeyer]

Merged: sage-5.11.beta1

[jdemeyer]

Changed reviewer from Nicolas Thiery, Travis Scrimshaw to Nicolas M. Thiéry, Travis Scrimshaw