Serious regression caused by #9138

[SimonKing]

At ​sage-devel, Jeroen reported a massive regression in elliptic curve computations. The regression was introduced in the transition from sage-4.7.2.alpha2 to sage-4.7.2.alpha3.

It seems that #9138 is responsible, at least for a big part of the regression. With unpatched sage-4.7.2.alpha2, we find

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 5.54 s, sys: 0.15 s, total: 5.69 s
Wall time: 5.81 s

Adding #9138 and its dependency, we obtain

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 8.72 s, sys: 0.18 s, total: 8.89 s
Wall time: 8.92 s

It turns out that much time is wasted for calls to sage.categories.Category.join and to sage.categories.Category.hom_category.

When caching these two methods, one can reduce the speed difference to something like that (sage-4.7.2.alpha3 plus #11115 plus an experimental patch for the caching):

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 6.82 s, sys: 0.16 s, total: 6.98 s
Wall time: 7.40 s

However, that's still far from good. After caching join and hom_category, there is still too much time spent (according to %prun) for the initialisation of matrix spaces.

Apply

• trac11900_category_speedup_combined.patch​
• trac11900_only_fix_singleton_hash.patch​
• trac11900_doctest.patch​

[SimonKing]

It seems that some time is spent for creating a homset, when creating a matrix space.

In fact, during initialisation, a special map from the basering is created for coercion. That has been introduced in #9138 because otherwise coercion from the base ring to the matrix space is too slow.

However, it might be better to not create the coerce map during initialisation. After all, it is a waste of time to create it when eventually it is not used. Perhaps that is what is happening here?

[SimonKing]

When avoiding initialisation of coercion from the base ring into a matrix space,(in addition to caching hom_category and join), I get

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 6.83 s, sys: 0.22 s, total: 7.05 s
Wall time: 7.07 s

[SimonKing]

The next problematic call seems to be __get__ of some lazy attribute. But I don't know yet which it is.

[SimonKing]

Next finding: It could be that the cache for matrix spaces is broken. I inserted a print statement into the initialisation of MatrixSpace_generic that shows base_ring,nrows,ncols and the sparsity.

By the cache implemented in the MatrixSpace constructor, no quadrupel should occur twice, but in fact the space of dense 8 by 8 matrices over GF(46337) and other instances occurs several times. Could it be that the matrix space is directly constructed, i.e., breaking the cache?

[SimonKing]

Replying to SimonKing:

By the cache implemented in the MatrixSpace constructor, no quadrupel should occur twice, but in fact the space of dense 8 by 8 matrices over GF(46337) and other instances occurs several times. Could it be that the matrix space is directly constructed, i.e., breaking the cache?

No, it is differently: The cache uses weak references. In fact, garbage collection is to blame for the double construction of matrix spaces.

[SimonKing]

When I use strong references for caching matrix spaces (in addition to the previous changes), I get

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 6.15 s, sys: 0.16 s, total: 6.31 s
Wall time: 6.33 s

Of course, one wouldn't like to have all the matrix spaces hanging around. But perhaps it is an option to temporarily turn garbage collection off.

However, the computation of E.gens() actually requires the construction of many different matrix spaces. So, making matrix space creation faster certainly is the best option.

[SimonKing]

Another time seems to be uselessly spent on a generic method of free module elements: list().

Such a small method ought to be as fast as possible and should thus be overridden in sub-classes. But sage.modules.vector_integer_dense.Vector_integer_dense does not override the list() method.

[SimonKing]

Replying to SimonKing:

Such a small method ought to be as fast as possible and should thus be overridden in sub-classes. But sage.modules.vector_integer_dense.Vector_integer_dense does not override the list() method.

Neither do sage.modules.vector_rational_dense.Vector_rational_dense.

[SimonKing]

If the initialisation of matrix spaces is changed such that Parent.__init__ (and thus the full category framework) is not called, then I'm down to

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 5.65 s, sys: 0.16 s, total: 5.82 s
Wall time: 5.83 s

As a consequence, the TestSuite of matrix spaces would not fully work, but perhaps it would be worth it. I'll ask sage-devel.

[SimonKing]

The next surprise is that (even if one avoids category initialisation of matrix spaces) many covariant constructions (quotients and subquotients) are called - that is another reason why Category.join() is called so often.

Part of the problem may be that sage.categories.CovariantConstructionCategory.category_of has been defined as @class_method in #8881, not as @cached_function (one can see in the code that cached_function has been considered, but was commented out). So, perhaps it is worth while to try that change?

But first I need to find out where the quotients and subquotients actually arise.

[SimonKing]

Yes!!

When I use a cache for category_of, we have

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens() 
CPU times: user 5.54 s, sys: 0.19 s, total: 5.74 s
Wall time: 5.75 s

and at least this instance of a regression has gone! I don't know how much of it is due to the fact that I also have #11115 applied, but let me first finish the patch and then we'll see.

[SimonKing]

I have attached a preliminary patch, if someone already wants to have a look. I need to do more tests (and run doctests), but up to now it seems that it fixes the regression.

Changes for Matrix Spaces

Matrix spaces will not make use of the category framework by default. But I introduced a new method that makes them use the category framework after initialisation:

            sage: MS = MatrixSpace(QQ,8)
            sage: TestSuite(MS).run()
            Failure in _test_category:
            Traceback (most recent call last):
            ...
            AssertionError: category of self improperly initialized
            ------------------------------------------------------------
            The following tests failed: _test_category
            sage: type(MS)
            <class 'sage.matrix.matrix_space.MatrixSpace_generic'>
            sage: MS.full_category_initialisation()
            sage: TestSuite(MS).run()
            sage: type(MS)
            <class 'sage.matrix.matrix_space.MatrixSpace_generic_with_category'>

Minor change: I made __matrix_class a lazy attribute.

Changes for categories

I turn hom_category in a cached method - the result is cached anyway, and thus it makes sense to cache as early as possible, in order to reduce the overhead, and in order to benefit from #11115.

I also cache the class method category_of in sage.categories.covariant_functorial_construction. According to a commented-out line, caching has been attempted anyway, but since it needs to be a class method, caching has not been possible by simply using a decorator.

Vectors

I added custom list() methods for both integral and rational dense vectors. Here is the speed difference (the timing is with patch attached):

sage: v = vector(ZZ,range(100))
sage: %timeit L = v.list()
625 loops, best of 3: 11 µs per loop
# was 17 µs per loop in sage-4.7.2.alpha2
sage: v = vector(QQ,range(100))
sage: %timeit L = v.list()
625 loops, best of 3: 24 µs per loop
# was 27.7 µs per loop in sage-4.7.2.alpha2

The difference is small, but one should benefit from it.

Doc formatting

I corrected some wrong formatting in the documentation of dense integral and rational vectors.

[SimonKing]

The crucial question: Does it fix the speed regression?

Here are Jeroen's examples from sage-devel.

sage-4.7.2.alpha2

sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 5.60 s, sys: 0.21 s, total: 5.81 s
Wall time: 5.83 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 7.08 s, sys: 0.03 s, total: 7.11 s
Wall time: 7.75 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 3.29 s, sys: 0.03 s, total: 3.32 s
Wall time: 3.38 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.73 s, sys: 0.04 s, total: 3.78 s
Wall time: 4.01 s
sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 16.47 s, sys: 0.04 s, total: 16.50 s
Wall time: 16.73 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 13.88 s, sys: 0.06 s, total: 13.94 s
Wall time: 14.01 s

sage-4.7.2.alpha2 plus #9138 and its dependency

sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 8.80 s, sys: 0.15 s, total: 8.95 s
Wall time: 8.98 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 7.11 s, sys: 0.03 s, total: 7.14 s
Wall time: 7.48 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 6.07 s, sys: 0.02 s, total: 6.09 s
Wall time: 6.13 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 10.10 s, sys: 0.07 s, total: 10.17 s
Wall time: 10.55 s
sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 23.03 s, sys: 0.05 s, total: 23.08 s
Wall time: 23.18 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 16.29 s, sys: 0.05 s, total: 16.34 s
Wall time: 16.48 s

sage-4.7.2.alpha2 plus #9138 and its dependency plus the patch from here

sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 6.02 s, sys: 0.20 s, total: 6.22 s
Wall time: 6.23 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 7.11 s, sys: 0.01 s, total: 7.12 s
Wall time: 7.39 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 3.81 s, sys: 0.04 s, total: 3.84 s
Wall time: 3.85 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 6.11 s, sys: 0.07 s, total: 6.18 s
Wall time: 6.20 s
sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 18.11 s, sys: 0.07 s, total: 18.17 s
Wall time: 18.23 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 13.13 s, sys: 0.05 s, total: 13.18 s
Wall time: 13.22 s

Conclusion

#9138 is indeed responsible for all but one regression. The only exception is the test suite for CrytalOfTableaux; it has already been argued on sage-devel that it is actually not a regression, since the test suite became much longer by #11183.

The patch from here fixes most regressions. Problematic remain the EllipticCurve('960d1').prove_BSD() and the E.change_ring(GF(p)).abelian_group() tests.

[SimonKing]

The patch is updated.

I did not run the doc tests yet, and also I think one should try to fix the remaining regression, but I turn it into "needs review".

[jdemeyer]

Doing some timing...

I am afraid I will not be able to review your patch because I am too unfamiliar with the matter that the patch deals with.

Note that your patch applies with "fuzz 2" against a vanilla sage-4.7.2.alpha3, you probably should make a clean version.

[SimonKing]

With sage-4.7.2.alpha2 plus #9138 plus #11734 (which is a blocker for 4.7.2 merged in alpha3) and the latest patch, I get

sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 5.52 s, sys: 0.19 s, total: 5.72 s
Wall time: 5.74 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 7.05 s, sys: 0.02 s, total: 7.06 s
Wall time: 7.28 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 3.70 s, sys: 0.01 s, total: 3.71 s
Wall time: 3.73 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 6.26 s, sys: 0.04 s, total: 6.30 s
Wall time: 6.31 s
sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 18.45 s, sys: 0.06 s, total: 18.51 s
Wall time: 18.56 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 12.54 s, sys: 0.02 s, total: 12.56 s
Wall time: 12.63 s

[SimonKing]

Replying to jdemeyer:

Note that your patch applies with "fuzz 2" against a vanilla sage-4.7.2.alpha3, you probably should make a clean version.

Really? Did you test the latest patch?

Anyway. For me, the priority is to first get it working.

[jdemeyer]

Replying to SimonKing:

Really? Did you test the latest patch?

I think so.

Anyway. For me, the priority is to first get it working.

I agree, but I thougt you should know...

[SimonKing]

Indeed, there is some fuzz. I'll take care of that in the next patch version.

[SimonKing]

So far, I did not cache join (only hom_category). That should be done next.

[jdemeyer]

(this also posted to sage-devel)

Some updated timings below, all times are best-out-of-3 wall times, in seconds. Patch #11900 is in progress so the timing is with the current patch. "baseline" means sage-4.7.2.alpha3 without #9138. Clearly, the slowdown of elltest2.sage is not due to #9138. Also Singular does not cause a slowdown.

cyclomat.sage:
sage-4.7.2.alpha2:           6.9
baseline:                    7.3
baseline + #9138 + #11900:   7.4
baseline + #11339 + #10903:  6.8

ellbsd.sage:
sage-4.7.2.alpha2:           7.5
baseline:                    7.3
baseline + #9138 + #11900:  12.4
baseline + #11339 + #10903:  7.4

elltest1.sage:
sage-4.7.2.alpha2:          27.0
baseline:                   24.4
baseline + #9138 + #11900:  31.7
baseline + #11339 + #10903: 24.7

elltest2.sage:
sage-4.7.2.alpha2:          19.6
baseline:                   63.8
baseline + #9138 + #11900:  62.3
baseline + #11339 + #10903: 62.9

J0_46_disc.sage
sage-4.7.2.alpha2:           8.9
baseline:                    8.2
baseline + #9138 + #11900:   8.8
baseline + #11339 + #10903:  8.4

[SimonKing]

OK, the timings indicate that I should now focus on

L = EllipticCurve('960d1').prove_BSD()

and

E = EllipticCurve('389a')
for p in prime_range(10000):
	if p != 389:
		G = E.change_ring(GF(p)).abelian_group()

[SimonKing]

The remaining slowness seems to be related with the initialisation of multivariate polynomial rings (implemented in libsingular). As for matrices, it seems to be a problem that #9138 constructs the coercion from the base ring during initialisation, and not when it is first requested.

The difference between matrix spaces and libsingular polynomial rings is that the latter does not use the new coercion model yet. I'll try to fix that, and hope that it will reduce the regression.

[SimonKing]

Implementing the new coercion for libsingular will not be easy, but it seems that it will pay off: It seems to me that some tests in _coerce_c_impl are done each time an element is coerced, rather than once, just for the parent of that element.

[SimonKing]

I managed to implement the new coercion model for libsingular rings, therefore cc to Martin.

One trick to make that work: One should acknowledge that polynomial rings are unique parents (unless one destroys uniqueness on purpose), thus, the hash can be id(self) and __cmp__ can be identity of objects.

What has hash and cmp to do with the new coercion model? There was a custom __richcmp__ in the code. It somehow managed to trigger a test for the old coercion model. And unfortunately, if replaces __cmp__ by _element_constructor_ then the test for the old coercion model raises an exception, even though _element_constructor_ is supposed to be a tool of the new model.

I think that in a different ticket, one can build on top of that and replace the current (and always repeated!) coercion tests on elements by tests that are done once for the parent of these elements. That would improve the performance.

Perhaps that was not a very clear explanation. Anyway.

With the new coercion, it becomes possible to avoid the construction of a coercion from the base ring during initialisation.

In addition, I am working on a simplification of the choice of category during PolynomialRing_generic.__init__. It uses sage.rings.categories.Category.join, but could actually directly construct a JoinCategory, since all the additional work in sage.rings.categories.Category.join is not needed. Since join() eats a lot of time in the benchmarks, I am confident that we will see an improvement.

That's the plan, now I have to do tests...

[SimonKing]

New coercion for libsingular; faster category choice for polynomial rings.

[SimonKing]

I have attached a second patch, in which I implemented the ideas sketched above. Doc tests need work (I guess some old tests will need to be rewritten).

There is some improvement in the timings, With sage-4.7.2.alpha3 and both patches applied, I get:

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 5.01 s, sys: 0.06 s, total: 5.07 s
Wall time: 5.22 s

Sage-4.7.2.alpha2 took 4.01 s on that example. Thus, with the second patch, we "only" have half of the regression that we had after the first patch, and only one fifth of the regression without both patches.

The other critical example became:

sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 15.93 s, sys: 0.04 s, total: 15.97 s
Wall time: 16.03 s

Sage-4.7.2.alpha2 took 16.73 s. Hence, here we actually have a slight improvement, where we previously had a drastic regression.

I need more tests, but I think that I can now hope to "rescue" #9138.

[SimonKing]

Running the L = EllipticCurve('960d1').prove_BSD() example with %prun, I find that a considerable amount of time is spent for calling cached functions. That is not the case with sage-4.7.2.alpha2 plus #11342. I guess that comes from the caching for the join() method in my first patch.

I see two ways to proceed: Test whether #11115 turns the increased use of cached function into an advantage. Or try to find out what cached function is actually called, and from where, and reduce it.

[SimonKing]

For the record: #11115 makes the cached function disappear from %prun (but that's no surprise, since %prun can not see through Cython). So, I have to try the second alternative.

[SimonKing]

Replying to SimonKing:

For the record: #11115 makes the cached function disappear from %prun (but that's no surprise, since %prun can not see through Cython)...

I forgot to continue the phrase: ..., but the timing did not improve. That is why I have to try the second alternative.

[SimonKing]

Still, there is too much time spent on the initialisation of polynomial rings. And the reason seems to be the construction of the parent class of the categories.

A polynomial ring over a finite prime field F belongs to the category of Commutative Algebras of F (by #9138). In order to provide the ring with the correct class (PolynomialRing_dense_mod_p_with_category in this case), one needs to have the parent class of CommutativeAlgebras(F). But this involves to know the parent classes of F algebras, F vector spaces, F bimodules, F left modules, F right modules, and rings.

During the elliptic curve computation, F varies. Hence, all the base classes need to be computed over and over again.

I wonder whether it is possible to make the parent class of a category independent of the base (here: F) of the category. Then, one could avoid the creation of about 5000 dynamic classes during the elliptic curve computation. I guess that's a question to sage-combinat-devel.

How might this work? Perhaps make the parent class of a category a class attribute: Algebras(F).parent_class depends on F, but Algebras(F).__class__.parent_class would be independent of F. Or perhaps one should better introduce a central cache for the parent and element classes, so that Algebras(F).parent_class is just a pointer to parent_class_cache[sage.categories.algebras.Algebras].

[nthiery]

Replying to SimonKing:

Still, there is too much time spent on the initialisation of polynomial rings. And the reason seems to be the construction of the parent class of the categories.

A polynomial ring over a finite prime field F belongs to the category of Commutative Algebras of F (by #9138). In order to provide the ring with the correct class (PolynomialRing_dense_mod_p_with_category in this case), one needs to have the parent class of CommutativeAlgebras(F). But this involves to know the parent classes of F algebras, F vector spaces, F bimodules, F left modules, F right modules, and rings.

During the elliptic curve computation, F varies. Hence, all the base classes need to be computed over and over again.

I wonder whether it is possible to make the parent class of a category independent of the base (here: F) of the category. Then, one could avoid the creation of about 5000 dynamic classes during the elliptic curve computation. I guess that's a question to sage-combinat-devel.

How might this work? Perhaps make the parent class of a category a class attribute: Algebras(F).parent_class depends on F, but Algebras(F).__class__.parent_class would be independent of F. Or perhaps one should better introduce a central cache for the parent and element classes, so that Algebras(F).parent_class is just a pointer to parent_class_cache[sage.categories.algebras.Algebras].

Actually that was the original intent; see the discussion around line 240 of category.py: two categories sharing the same inheritance diagram for their parent class would actually share that parent class. The implementation was simple: there was a cache on the dynamic class creation. There are two issues though:

• How to pickle such a class: the only solution I found was to pickle it as Algebras(F).parent_class; but this requires to store "Algebras(F)" as part of the parent class, which prevents sharing. Better solutions welcome!

• Even if the above is changed, this would still require the creation of the categories Algebras(F) (and super categories) for all F, which could take some time.

• I had had similar issues with the coercion system with MuPAD (the factoring code was creating zillions of fields, which crowded the coercion graph). So I already thought about modeling simultaneously a bunch of parents/categories having the exact same properties as a single template object (say in the coercion graph). But I did not come up with great solutions yet.

• One needs to be a bit carefull, as the inheritance diagram may depend on F. For example, Algebras(F).parent_class derives from VectorSpaces?(F).parent_class iff F is a field.

Once again, I am glad you are working on those category optimizations!

Altogether your proposals look very good. I am just unsure about short circuiting "Category.join", but I would need to look more in detail. Maybe we would need to add an abstraction layer in between. Anyway go ahead with whatever works for fixing #11900, and if we find something better, we can do it in a later patch.

[SimonKing]

Replying to nthiery:

Altogether your proposals look very good. I am just unsure about short circuiting "Category.join", but I would need to look more in detail.

Which of the two work-arounds do you mean? The caching (so that the cache already happens when calling Category.join(L), not only when creating the JoinCategory)? Or the attempt to directly create the JoinCategory during creation of a polynomial ring?

I think the latter is justified by having only few cases: It can be UniqueFactorisationDomain, IntegralDomain or EuclideanDomain, and it can be commutative or not. So, one can directly write down the result, rather than calling the Category.join(...) mechanism. Of course, one needs to verify that I wrote it down correctly.

[nthiery]

Replying to SimonKing:

Replying to nthiery: Which of the two work-arounds do you mean?

Actually both :-)

The caching (so that the cache already happens when calling Category.join(L), not only when creating the JoinCategory)? Or the attempt to directly create the JoinCategory during creation of a polynomial ring?

This might induce some quite big caching, since a given join may be created in many different ways (order of arguments, ...). That being said, maybe that's not so bad. Also, I need to check how this evolves with the upcoming "more category constructions" patch. Anyway, I guess we can wait until we actually meet the issue with that cache, if we do, before removing it again.

I think the latter is justified by having only few cases: It can be UniqueFactorisationDomain, IntegralDomain or EuclideanDomain, and it can be commutative or not. So, one can directly write down the result, rather than calling the Category.join(...) mechanism. Of course, one needs to verify that I wrote it down correctly.

The only potential issue is about the order of the categories in the join. Having everything go through Category.join makes it easier to maintain consistency, and make it evolve if needed. But if this remains a it is a well documented and well motivated exception, that could be ok. It's not worst than the order appearing in all the super_categories methods.

Cheers,

Nicolas

[SimonKing]

Before I sleep, just a brief report.

It seems to be perfectly alright if one lets parent and element classes rely on the default pickling of dynamic classes. This alone suffices to have

  sage: Algebras(GF(3)).parent_class is Algebras(GF(5)).parent_class
  True
  sage: loads(dumps(Algebras(GF(3)).parent_class)) is Algebras(GF(5)).parent_class
  True
  sage: Algebras(GF(3)).parent_class is Algebras(ZZ).parent_class
  False
  sage: Coalgebras(QQ).parent_class is Coalgebras(FractionField(QQ[x])).parent_class
  True 

The latter was mentioned as "todo" in category.py

And:

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.85 s, sys: 0.08 s, total: 3.93 s
Wall time: 4.08 s

In other words, the regression for prove_BSD disappears!

I certainly need to add some doc tests for the new feature, and also it will probably be needed to fix old tests. But I am confident that I can post a new patch tomorrow, that may be enough to fix the regression completely.

[SimonKing]

Replying to nthiery:

The caching (so that the cache already happens when calling Category.join(L), not only when creating the JoinCategory)? Or the attempt to directly create the JoinCategory during creation of a polynomial ring?

This might induce some quite big caching, since a given join may be created in many different ways (order of arguments, ...).

I thought that the join does depend on the order of the input categories. If it doesn't, one could always use frozen sets as key, rather than tuples.

I think the latter is justified by having only few cases: It can be UniqueFactorisationDomain, IntegralDomain or EuclideanDomain, and it can be commutative or not. So, one can directly write down the result, rather than calling the Category.join(...) mechanism. Of course, one needs to verify that I wrote it down correctly.

The only potential issue is about the order of the categories in the join. Having everything go through Category.join makes it easier to maintain consistency, and make it evolve if needed.

OK. If join changes the order of arguments in future versions of Sage, then we should change the five or six hard-coded categories that my patch uses in the initialisation of polynomial rings.

I suggest to add doc tests of the form

sage: P.<x> = ZZ[]
sage: P.category() is Category.join([CommutativeAlgebras(ZZ), UniqueFactorizationDomains()])
True

(that should be the answer, but with the current patch it is only the join of Algebras(ZZ) with UniqueFactorizationDomains(). So, that needs to bee fixed as well.

Having such tests would detect incompatible changes in the order of base categories in the join.

[SimonKing]

Concerning "Choice of categories for polynomial rings", I suggest to add a function somewhere (perhaps in sage/rings/polynomial/multi_polynomial_ring.py) that takes the category of the base ring and the number of generators as arguments, and returns the appropriate category of the polynomial ring.

That would certainly be better (and easier to maintain and also easier to cache and thus more efficient) than to choose the category in the different __init__ methods of different kinds of polynomial rings.

[SimonKing]

In order to keep patches small, my plan is to provide two patches. The first will be an update of the "polynomial categories and coercion" patch. The second shall deal with parent/element classes of categories, which is a separate issue.

Concerning the "polynomial categories and coercion":

Choice of category

Replying to SimonKing:

I suggest to add a function somewhere (perhaps in sage/rings/polynomial/multi_polynomial_ring.py) that takes the category of the base ring and the number of generators as arguments, and returns the appropriate category of the polynomial ring.

That seems to work fine. Since I directly construct a JoinCategory rather than calling Category.join, it is a little faster, and it is certainly easier to maintain than the current approach.

Easier detection of ring structures

Currently, if one wants to test whether a parent is a Euclidean domain, one has to do P in EuclideanDomains(), which boils down to P.category().is_subcategory(EuclideanDomains()). That implies the construction of all super-categories of P.category() and is thus rather slow.

I guess it would be much faster to add parent methods that tell whether the ring has a certain structure, and to simply ask P.is_euclidean_domain().

Similar parent methods should exist for Fields(), Rings(), CommutativeRings() and IntegralDomains().

[SimonKing]

Question to the release manager: How shall we proceed with re-mergin #9138? Shall that be done on #9138 (so that we have two separate tickets)? Or shall both merging and fixing #9138 be done here?

[jdemeyer]

Replying to SimonKing:

Question to the release manager: How shall we proceed with re-mergin #9138? Shall that be done on #9138 (so that we have two separate tickets)? Or shall both merging and fixing #9138 be done here?

I don't really understand your question but let me answer something anyway: I would leave #9138 as it is and put all fixes on #11900. When #11900 is finished, I will merge #9138 and #11900 at the same time.

Something else: Singular (#10903) will likely be merged in sage-4.7.2.alpha4. This will require some of these patches to be rebased. You may want to have a look at ​http://boxen.math.washington.edu/home/release/sage-4.7.2.alpha4/

[SimonKing]

In the doc of sage.categories.category.Category.all_super_categories, there is stated:

        FIXME:

        - make sure that this is compatible with the python algorithm
          for method resolution and make it O(n+m)

I think that would be an excellent idea, because the category hierarchy (determined by all_super_categories) and the method resolution order of the parent classes should be the same.

I doubt whether Python's mro is O(n+m), though. I know Python's mro algorithm and could implement it, but certainly it could be imported from somewhere, so that my programming effort is not needed here.

[SimonKing]

Replying to jdemeyer:

I don't really understand your question but let me answer something anyway: I would leave #9138 as it is and put all fixes on #11900. When #11900 is finished, I will merge #9138 and #11900 at the same time.

I asked because there was another case where a patch was unmerged, and the release manager insisted on having a separate ticket for merging it again - so, he did not simply re-opened the old ticket for that purpose.

Something else: Singular (#10903) will likely be merged in sage-4.7.2.alpha4. This will require some of these patches to be rebased. You may want to have a look at ​http://boxen.math.washington.edu/home/release/sage-4.7.2.alpha4/

OK. Is alpha4 "official", or is it currently an alpha-prerelease only?

[jdemeyer]

Replying to SimonKing:

Is alpha4 "official", or is it currently an alpha-prerelease only?

It is currently in testing. So if no unexpected issues arise, it should be released as it is now.

[SimonKing]

Replying to SimonKing:

In the doc of sage.categories.category.Category.all_super_categories, there is stated:

        FIXME:

        - make sure that this is compatible with the python algorithm
          for method resolution and make it O(n+m)

I think that would be an excellent idea, because the category hierarchy (determined by all_super_categories) and the method resolution order of the parent classes should be the same.

However, I think that it should be dealt with on a different ticket, since I don't see how it would help here.

I still see much time spent in all_super_categories. I just found that self.all_super_categores() does not start with C.all_super_categories() for C in self.super_categories(). That is certainly not very efficient, because it is effectively computing C.all_supercategories() repeatedly.

[SimonKing]

Replying to SimonKing:

I still see much time spent in all_super_categories. I just found that self.all_super_categores() does not start with C.all_super_categories() for C in self.super_categories(). That is certainly not very efficient, because it is effectively computing C.all_supercategories() repeatedly.

Indeed, it can be improved. And then, the benchmark finally becomes

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.60 s, sys: 0.11 s, total: 3.71 s
Wall time: 4.02 s

Conclusion

I will not change the order of all_super_categories, and I will not unify the parent classes of different categories - that shall be on a separate ticket.

However, I will

• make libsingular polynomial rings use the new coercion framework,
• avoid the construction of a coercion from the base ring at initialisation of matrix spaces and polynomial rings,
• create an external function for choosing the category of a polynomial ring, avoiding the overhead of the join() method,
• add parent methods that provide a faster way of determining algebraic structures than the classical P in CommutativeRings()
• improve the performance of all_super_categories().

[SimonKing]

I found a pickling bug for libsingular polynomia rings.

First session:

sage: P.<foo,bar> = PolynomialRing(QQ)
sage: save(P,'tmp')

Second session:

sage: Q = load('tmp.sobj')
sage: P.<foo,bar> = PolynomialRing(QQ)
sage: Q is P
False
sage: Q2 = load('tmp.sobj')
sage: Q2 is P
True
sage: Q2 is Q
False

Since I am fixing coercion of libsingular polynomial rings anyway, I'll fix the bug here.

[SimonKing]

Replying to SimonKing:

Since I am fixing coercion of libsingular polynomial rings anyway, I'll fix the bug here.

On the other hand, I was occasionally told to produce smaller patches. So, I created #11911 (which should be easy to review) and make it a dependency.

[SimonKing]

Too bad, the coercion for libsingular seems broken. That will be more work than I thought.

[SimonKing]

The broken coercion was relatively easy to fix. I am now returning to some further tuning of the timings. For example, I found that during initialisation of one multivariate polynomial ring, it is tested ten times (!) whether base_ring in Rings() or base_ring in Fields().

hat seems like a waste of time (should be done less often), and also it is faster to do base_ring.is_ring() if is_ring is a parent method.

[SimonKing]

PS: I did another benchmark.

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['t','x','z']
....:         
sage: %time test()
CPU times: user 1.14 s, sys: 0.02 s, total: 1.17 s
Wall time: 1.17 s

with sage-4.6.2. I becomes more than two seconds with #9138.

[nthiery]

Hi Simon,

Replying to SimonKing:

and also it is faster to do base_ring.is_ring() if is_ring is a parent method.

I thought that you had optimized the in containment to make it as fast as a method call? Besides, as far as I remember from previous discussions, we had agreed on the following:

• X in Fields() would return whether X is already known to be a field.

• X.is_field() would return whether X *is* a field, possibly launching a costly computation if needed, and possibly updating the category afterward

Finally, to do dispatching in category code, the preferred idiom would be X in Fields(). Roughly speaking, operations on an element depend on its declared parent, operations on a parent depend on its declared category.

Cheers,

Nicolas

[SimonKing]

Hi Nicolas,

Replying to nthiery:

Replying to SimonKing:

and also it is faster to do base_ring.is_ring() if is_ring is a parent method.

I thought that you had optimized the in containment to make it as fast as a method call?

That's #10667 and needs much more work than this. My aim here is to try and find a sufficiently good solution, so that #9138 can be rescued.

It could very well be that some of the changes (e.g. the use of is_ring) will be reverted by #10667, and replaced with a better solution. But I simply wouldn't like to wait another couple of months for #10667 to be finished - it would be a shame to postpone #9138 (which happens to be a dependency for #10667) such a long time.

• X in Fields() would return whether X is already known to be a field.

• X.is_field() would return whether X *is* a field, possibly launching a costly computation if needed, and possibly updating the category afterward

You are mistaken. Please look at the __contains__ method of Fields(). It dispatches to sage.rings.fields.is_Field, which dispatches to P.is_field().

Besides, in cases where this is a problem, there is a proof=False option for is_field. I would accept to argue that P in Fields() should be preserved, because of the difficulty of testing field-ness, and because it is not tested so often.

But P in Rings() is tested often and is too slow. X in Rings() takes an awful lot of time and is one of the four main causes for the regression. Bear in mind what X in Rings()` involves:

• Calling Rings(), which will be faster by #11115 (cached methods), but currently is not cheap. Thus, defining _Rings = Rings() once in a module and then testing X in _Rings is already an improvement.
• Calling C=X.category() - that's relatively cheap.
• Calling C.is_subcategory(_Rings), which is cached. However, in the elliptic curves code, C takes around 1000 different values, thus, caching really doesn't help here.
• is_subcategory involves constructing C.all_super_categories(). Again, 1000 times in the elliptic curves code. Note that this is because of #9138: Before, C would constantly be CommutativeRings(), but with #9138, it is CommutativeAlgebras(F) for different fields F.

Note that all_super_categories alone already takes 2 seconds in the %time L = EllipticCurve('960d1').prove_BSD() example! That's a third of the total computation time! The P in C idiom is to blame for a part of it, and Category.join is to blame for the rest.

It is much faster to define and use a parent method is_ring in the category of rings. Moreover, the base class sage.rings.ring.Ring also has a method is_ring, which is even faster than a method inherited from the category. Here is an example:

sage: R = Rings()
sage: MS = MatrixSpace(QQ,3)
sage: %timeit MS in R
625 loops, best of 3: 10.2 µs per loop
sage: %timeit MS.is_ring() # inherited from the category
625 loops, best of 3: 4.3 µs per loop
sage: P.<x,y> = PolynomialRing(GF(127))
sage: %timeit P.is_ring() # inherited from the base class
625 loops, best of 3: 392 ns per loop

On the long run, I would prefer to have fast containers (see #10667), so that one can do

O = Rings().objects()
for P in {many different parents with different categories]:
    if P in O:
        ...

But for now, I'd prefer a fast work-around.

Summary

The four main causes for the regression from #9138 are:

• P in Rings() is too slow (because it calls is_subcategory). #10667 will make it fast, on the long run, but for now it is easier and faster to add a parent method is_ring that returns True for rings.
• Category.join also involves calling is_subcategory too often. Fortunately, in many cases, the categories to be joined are known up to the base ring. Thus, it is possible to write down JoinCategory directly.
• C.is_subcategory(C2) is too slow, since C.all_super_categories() is too slow. I provide a faster (but equivalent) algorithm here.
• C.parent_class is too slow. In my not-yet-posted patch, I make it a little faster by calling dynamic_class_internal.f directly, thus, completely avoiding the cached_function overhead. C.parent_class should only depend on the base ring when absolutely necessary, but that will be dealt with on a different ticket.

[nthiery]

Replying to SimonKing:

I thought that you had optimized the in containment to make it as fast as a method call?

That's #10667 and needs much more work than this. My aim here is to try and find a sufficiently good solution, so that #9138 can be rescued.

It could very well be that some of the changes (e.g. the use of is_ring) will be reverted by #10667, and replaced with a better solution. But I simply wouldn't like to wait another couple of months for #10667 to be finished - it would be a shame to postpone #9138 (which happens to be a dependency for #10667) such a long time.

Ok, yes, I am perfectly fine with using is_ring as a temporary measure in critical and documented spots.

In general, +1 on getting #11900 in quickly even if it is not perfect, and thanks for all your work on that!

For the long run, I still would strongly argue for aiming at the "X in Fields()" idiom, if it can be made fast enough. It is more conceptual and versatile. But let's not waste time on that now, and postpone the discussion to your visit in Orsay.

• X in Fields() would return whether X is already known to be a field.

• X.is_field() would return whether X *is* a field, possibly launching a costly computation if needed, and possibly updating the category afterward

You are mistaken. Please look at the __contains__ method of Fields(). It dispatches to sage.rings.fields.is_Field, which dispatches to P.is_field().

I know: I wrote this backward compatibility hack :-)

What I described was the would-be clean plan for the future.

Cheers,

Nicolas

[SimonKing]

Not good. I got numerous doctest errors.

While it seems that postponing coercion from the base ring was good idea for matrix spaces (see first patch), it seems that the new coercion model for libsingular rings has no effect on the performance. So, I tend to leave that for a different ticket and try to simplify my patches.

[SimonKing]

One question: Would you agree that a category with a base ring (such that modules over the integers, having the integers as base ring) can never be a super-category of a category without a base (such as the category of commutative rings)?

If your answer is "yes" then one can get an "early abort" (hence, a speed-up) in is_subcategory. It would require to add a self.base() method to tensor categories and Cartesian product categories, in both cases returning self.base_category().base().

[nthiery]

Replying to SimonKing:

One question: Would you agree that a category with a base ring (such that modules over the integers, having the integers as base ring) can never be a super-category of a category without a base (such as the category of commutative rings)?

Roughly speaking yes; in any cases, that's currently true AFAIK. However, we might want to someday model the fact that any ring is a ZZ-module (or maybe not).

[SimonKing]

Replying to nthiery:

Replying to SimonKing: Roughly speaking yes; in any cases, that's currently true AFAIK.

No it isn't. That's why I asked:

sage: M = ModulesWithBasis(QQ)
sage: M.base()
Rational Field
sage: P = M.CartesianProducts()
sage: hasattr(P,'base')
False
sage: P.is_subcategory(M)
True

Thus, P has no base, but is a sub-category of a category with base.

However, we might want to someday model the fact that any ring is a ZZ-module (or maybe not).

That would probably just mean that the category of rings gets a base as well, namely ZZ.

[SimonKing]

Replying to SimonKing:

sage: M = ModulesWithBasis?(QQ) sage: M.base() Rational Field sage: P = M.CartesianProducts?() sage: hasattr(P,'base') False

And with my not-yet-submitted patch, P.base() would return QQ. It's the same with my patch for #10667, by the way.

[SimonKing]

Hooray! When I reverted libsingular rings using the old coercion model and confined the changes to matrices and categories, I only get few doctest errors:

sage -t  devel/sage-main/sage/matrix/matrix2.pyx # 5 doctests failed
sage -t  devel/sage-main/sage/rings/finite_rings/integer_mod_ring.py # 3 doctests failed
sage -t  devel/sage-main/sage/rings/ring.pyx # 2 doctests failed
sage -t  devel/sage-main/sage/rings/morphism.pyx # 4 doctests failed
sage -t  devel/sage-main/sage/categories/cartesian_product.py # 1 doctests failed
sage -t  devel/sage-main/sage/categories/modules_with_basis.py # 1 doctests failed

That seems manageable.

[SimonKing]

The doctest failures will be sufficiently easy to fix.

It will hardly be possible to have #9138 without any regression: After all, the initialisation of a good category takes its time. Therefore, I am trying to improve various frequently used category operations (is_subcategory, all_super_categories, testing ring-ness and field-ness, parent class construction) so that in the end the regression is tolerable.

In addition, I am now trying to look at the concrete examples. I still see that in the prove_BSD example the same polynomial rings are constructed repeatedly. So far, I am mystified: Looking at the code, garbage collection of the polynomial ring should simply not happen.

[SimonKing]

Oops, I was mistaken: I thought that every univariate polynomial ring was constructed twice. But in fact, it is only stored in cache twice, namely under different keys (see sage.rings.polynomial.polynomial_ring_constructor._single_variate). So, there is no starting point for an improvement here.

[SimonKing]

Postpone category initialisation for matrix spaces

[SimonKing]

Improve performance of various category operations. Introduce base() to more categories.

[SimonKing]

I think "new coercion model for libsingular" does not really fit to this ticket. Hence, I am not doing it in my new patch anymore.

It fixes many slownesses of the category framework that became unbearable with #9138. I am convinced that further tweaks are possible. For example, base ring independence of parent and element classes would have a significant impact on efficiency. But again, I believe that that should be on a different ticket.

All doc tests pass and thus it is "needs review". I'm now trying to collect some evidence supporting my patches.

Apply trac11900_no_categories_for_matrices.patch trac11900_category_speedup.patch

[SimonKing]

Here are some timings. I compare

(1) sage-4.7.2.alpha2, (2) sage-4.7.2.alpha3-prerelease and (3) sage-4.7.2.alpha3 with the patches from here.

I am restarting before each new test, so that caches created in one test won't influence the other tests.

Creation of matrix spaces

(1)

sage: def test():
....:     for i in xrange(5000):
....:         MS = MatrixSpace(QQ,i)
....:         
sage: %time test()
CPU times: user 0.38 s, sys: 0.00 s, total: 0.38 s
Wall time: 0.38 s

(2) The coercion from the base ring is initialised during matrix space initialisation. That involves a lot of category computations and is slow:

sage: def test():
....:     for i in xrange(5000):
....:         MS = MatrixSpace(QQ,i)
....:         
sage: %time test()
CPU times: user 1.85 s, sys: 0.03 s, total: 1.88 s
Wall time: 1.88 s

(3) Since matrix spaces are often considered mere containers, not rings or modules, the first patch does no initialisation of the category during initialisation of the matrix space. There is a method that can do the full category initialisation after matrix space initialisation.

sage: def test():
....:     for i in xrange(5000):
....:         MS = MatrixSpace(QQ,i)
....:         
sage: %time test()
CPU times: user 0.26 s, sys: 0.00 s, total: 0.27 s
Wall time: 0.27 s

Creation of finite fields

(1)

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)
....:         
sage: %time test()
CPU times: user 0.60 s, sys: 0.00 s, total: 0.60 s
Wall time: 0.61 s

(2) It is slower by a factor of more than 10. %prun reveals that most time is spent in Category.join.

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)
....:         
sage: %time test()
CPU times: user 6.59 s, sys: 0.00 s, total: 6.60 s
Wall time: 6.62 s

(3) The drastic slow-down observed in (2) has not totally vanished, but I hope this is good enough for now:

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)
....:         
sage: %time test()
CPU times: user 0.82 s, sys: 0.01 s, total: 0.83 s
Wall time: 0.83 s

Creation of polynomial rings

(1)

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['x']
....:         P = GF(p)['x','y']
....:         
sage: %time test()
CPU times: user 2.41 s, sys: 0.05 s, total: 2.46 s
Wall time: 2.53 s

(2) Since I am creating polynomial rings over finite fields, part of the overhead comes from what we have seen in the previous example. However, there must be an additional slowness, since the creation of finite fields apparently only contributes 6 seconds.

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['x']
....:         P = GF(p)['x','y']
....:         
sage: %time test()
CPU times: user 13.15 s, sys: 0.05 s, total: 13.20 s
Wall time: 13.27 s

(3) Here, it seems that additional improvements are needed: It is still much slower than without #9138.

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['x']
....:         P = GF(p)['x','y']
....:         
sage: %time test()
CPU times: user 6.54 s, sys: 0.08 s, total: 6.62 s
Wall time: 6.68 s

is_subcategory using base

(1) and (2)

sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(10000)]
sage: A = Algebras(GF(5))
sage: %time _ = [B.is_subcategory(A) for B in L]
CPU times: user 0.95 s, sys: 0.00 s, total: 0.96 s
Wall time: 0.96 s

(3) I think an early abort strategy taking into account the base rings of categories makes sense.

sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(10000)]
sage: A = Algebras(GF(5))
sage: %time _ = [B.is_subcategory(A) for B in L]
CPU times: user 0.04 s, sys: 0.02 s, total: 0.06 s
Wall time: 0.06 s

The Elliptic Curve Tests

Recall that only two of them remained critical: L = EllipticCurve('960d1').prove_BSD() and the change_ring(...).abelian_group() test.

prove_BSD() (1)

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.74 s, sys: 0.11 s, total: 3.85 s
Wall time: 5.05 s

(2) Given the timings above, this should be almost entirely due to finite field and polynomial ring creation.

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 9.37 s, sys: 0.16 s, total: 9.53 s
Wall time: 10.89 s

(3) I am not totally happy, yet:

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 5.63 s, sys: 0.10 s, total: 5.72 s
Wall time: 5.87 s

abelian_group()

(1)

sage: def test():
....:     E = EllipticCurve('389a')
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: %time test()
CPU times: user 16.57 s, sys: 0.08 s, total: 16.65 s
Wall time: 16.77 s

(2)

sage: def test():
....:     E = EllipticCurve('389a')
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: %time test()
CPU times: user 26.87 s, sys: 0.10 s, total: 26.97 s
Wall time: 27.16 s

(3)

sage: def test():
....:     E = EllipticCurve('389a')
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: %time test()
CPU times: user 19.29 s, sys: 0.08 s, total: 19.37 s
Wall time: 19.54 s

I am not totally happy with the performance, yet. But I think it makes sense that someone has a look at the current snap shot of patches.

[SimonKing]

Here is %prun test(L) for the following test of univariate polynomial ring creation:

sage: L = [GF(p) for p in prime_range(10000)]
sage: def test(L):
....:     for K in L:
....:         P = K['x']
....:         

(1)

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     3686    0.215    0.000    0.412    0.000 homset.py:248(__init__)
     1229    0.193    0.000    1.047    0.001 polynomial_ring.py:235(__init__)
7372/3686    0.094    0.000    0.126    0.000 lazy_attribute.py:493(__get__)
     3686    0.070    0.000    0.629    0.000 homset.py:40(Hom)
     1229    0.054    0.000    0.054    0.000 {method '_unset_coercions_used' of 'sage.structure.parent.Parent' objects}
    25803    0.040    0.000    0.113    0.000 {hasattr}
    23346    0.039    0.000    0.039    0.000 {method 'fix_to_pos' of 'sage.misc.function_mangling.ArgumentFixer' objects}
     1229    0.039    0.000    0.226    0.000 {method '_populate_coercion_lists_' of 'sage.structure.parent.Parent' objects}
    14745    0.036    0.000    0.098    0.000 classcall_metaclass.py:131(__call__)
     1228    0.035    0.000    0.314    0.000 finite_field_prime_modn.py:128(_coerce_map_from_)
    17203    0.032    0.000    0.064    0.000 cachefunc.py:147(__call__)
     1229    0.031    0.000    1.103    0.001 polynomial_ring.py:1954(__init__)
     3687    0.025    0.000    0.030    0.000 polynomial_ring.py:673(__hash__)
    17200    0.023    0.000    0.023    0.000 finite_field_prime_modn.py:223(order)
     1229    0.020    0.000    1.169    0.001 polynomial_ring_constructor.py:443(_single_variate)
6144/6143    0.018    0.000    0.038    0.000 cachefunc.py:505(__call__)
     1229    0.014    0.000    0.016    0.000 {method 'is_prime' of 'sage.rings.integer.Integer' objects}
     1229    0.013    0.000    1.065    0.001 polynomial_ring.py:1874(__init__)
        1    0.013    0.013    1.201    1.201 <ipython console>:1(test)
     6143    0.011    0.000    0.067    0.000 category.py:974(hom_category)
     1229    0.011    0.000    0.153    0.000 {method '_Hom_' of 'sage.rings.finite_rings.finite_field_base.FiniteField' objects}
     1229    0.011    0.000    1.189    0.001 polynomial_ring_constructor.py:48(PolynomialRing)
     3688    0.010    0.000    0.041    0.000 {method 'has_key' of 'dict' objects}
    14748    0.009    0.000    0.009    0.000 {isinstance}
     1229    0.008    0.000    0.142    0.000 homset.py:29(__init__)
     1229    0.007    0.000    0.009    0.000 polynomial_ring_constructor.py:427(_get_from_cache)
     1229    0.007    0.000    0.009    0.000 {sage.structure.parent_gens.normalize_names}
    14744    0.007    0.000    0.010    0.000 unique_representation.py:514(__hash__)
     7372    0.007    0.000    0.007    0.000 {getattr}
     1228    0.007    0.000    0.007    0.000 {sage.rings.finite_rings.integer_mod.IntegerMod}
     2458    0.006    0.000    0.014    0.000 dynamic_class.py:122(dynamic_class)

(2) As you can see, an awful lot of the time is spent for creation of the parent classes and for is_subcategory() tests:

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    11055    0.877    0.000    0.879    0.000 dynamic_class.py:258(dynamic_class_internal)
320769/3687    0.510    0.000    1.812    0.000 category.py:588(add_successors)
9826/1229    0.421    0.000    1.457    0.001 category.py:628(parent_class)
374826/34402    0.398    0.000    2.701    0.000 cachefunc.py:505(__call__)
72485/61432    0.381    0.000    2.185    0.000 cachefunc.py:147(__call__)
     9826    0.269    0.000    0.765    0.000 unique_representation.py:435(__classcall__)
     3687    0.232    0.000    2.245    0.001 category.py:554(all_super_categories)
   121627    0.219    0.000    0.219    0.000 {method 'fix_to_pos' of 'sage.misc.function_mangling.ArgumentFixer' objects}00    6.292    0.005 polynomial_ring.py:237(__init__)
     6144    0.217    0.000    0.555    0.000 homset.py:287(__init__)
22114/7373    0.179    0.000    1.670    0.000 lazy_attribute.py:493(__get__)
58971/45462    0.164    0.000    1.228    0.000 classcall_metaclass.py:131(__call__)
     9826    0.157    0.000    0.211    0.000 category.py:323(__init__)
   486657    0.145    0.000    0.189    0.000 unique_representation.py:514(__hash__)
     9832    0.114    0.000    2.485    0.000 category.py:679(is_subcategory)
4916/2458    0.104    0.000    0.613    0.000 {method 'coerce_map_from' of 'sage.structure.parent.Parent' objects}7    0.000    0.208    0.000 {hasattr}
    56514    0.081    0.000    0.081    0.000 finite_field_prime_modn.py:224(order)
     6144    0.078    0.000    1.513    0.000 homset.py:39(Hom)
     3687    0.068    0.000    2.231    0.001 category.py:868(join)
     7369    0.060    0.000    0.350    0.000 category_types.py:262(__init__)
     1229    0.058    0.000    0.058    0.000 {method '_unset_coercions_used' of 'sage.structure.parent.Parent' objects}.000    0.170    0.000 cachefunc.py:804(__get__)
    79885    0.051    0.000    0.079    0.000 {method 'add' of 'set' objects}
   396967    0.050    0.000    0.050    0.000 {method 'append' of 'list' objects}
2458/1229    0.047    0.000    0.628    0.001 polynomial_ring.py:470(_coerce_map_from_)
    14742    0.046    0.000    1.190    0.000 dynamic_class.py:122(dynamic_class)

(3) To my surprise, with my patches, the picture remains the same. I'll try to fix it.

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    11061    1.211    0.000    1.213    0.000 dynamic_class.py:258(dynamic_class_internal)
67595/6145    0.660    0.000    2.958    0.000 category.py:702(is_subcategory)
191717/34406    0.636    0.000    3.132    0.000 cachefunc.py:505(__call__)
   172054    0.501    0.000    0.501    0.000 {method 'fix_to_pos' of 'sage.misc.function_mangling.ArgumentFixer' objects}/22121    0.251    0.000    4.792    0.000 cachefunc.py:147(__call__)
     1229    0.233    0.000    5.394    0.004 polynomial_ring.py:246(__init__)
146251/14748    0.163    0.000    2.788    0.000 category.py:757(<genexpr>)
     9831    0.159    0.000    0.213    0.000 category.py:350(__init__)
77426/7373    0.098    0.000    2.973    0.000 cachefunc.py:733(_instance_call)
   130272    0.097    0.000    0.097    0.000 {getattr}
   121667    0.096    0.000    0.514    0.000 cachefunc.py:559(get_key)
36868/23350    0.095    0.000    0.810    0.000 classcall_metaclass.py:131(__call__)
   167141    0.087    0.000    0.087    0.000 {isinstance}
   226131    0.086    0.000    0.112    0.000 unique_representation.py:514(__hash__)
9832/1229    0.069    0.000    1.315    0.001 category.py:651(parent_class)
     3687    0.065    0.000    3.283    0.001 category.py:62(_join)
     7373    0.059    0.000    0.332    0.000 category_types.py:262(__init__)
76198/13519    0.055    0.000    2.885    0.000 {any}
    18434    0.055    0.000    0.175    0.000 cachefunc.py:804(__get__)
    35633    0.054    0.000    0.054    0.000 finite_field_prime_modn.py:224(order)
12288/2457    0.051    0.000    1.361    0.001 lazy_attribute.py:493(__get__)
     9831    0.046    0.000    0.509    0.000 unique_representation.py:435(__classcall__)
    18434    0.038    0.000    0.080    0.000 cachefunc.py:457(__init__)
     1228    0.037    0.000    0.202    0.000 finite_field_prime_modn.py:129(_coerce_map_from_)
     1228    0.036    0.000    0.088    0.000 homset.py:287(__init__)
    11061    0.036    0.000    1.384    0.000 dynamic_class.py:122(dynamic_class)

[SimonKing]

ARRGH, I am so unbelievably stupid!! I forgot to apply my second patch! All the timings for (3) above were only with the first patch!!!

On the bright side, it shows that my first patch isn't bad at all.

But I think it still makes sense to add the second as well. Here are the timings with both patches.

Creation of finite fields

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)
....:         
sage: %time test()
CPU times: user 0.68 s, sys: 0.02 s, total: 0.70 s
Wall time: 0.71 s

Creation of polynomial rings

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['x']
....:         P = GF(p)['x','y']
....:         
sage: %time test()
CPU times: user 4.32 s, sys: 0.07 s, total: 4.39 s
Wall time: 4.40 s

The Elliptic Curve Tests

prove_BSD()

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 4.20 s, sys: 0.07 s, total: 4.27 s
Wall time: 4.46 s

abelian_group()

sage: def test():
....:     E = EllipticCurve('389a')
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: %time test()
CPU times: user 18.02 s, sys: 0.09 s, total: 18.11 s
Wall time: 18.16 s

In conclusion, the original problem has almost vanished.

[SimonKing]

Note that with both patches applied, the creation of multivariate polynomial rings is faster than the creation of univariate rings:

sage: L = [GF(p) for p in prime_range(10000)]
sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['x']
....:         
sage: def test2():
....:     for p in prime_range(10000):
....:         P = GF(p)['x','y']
....:         
sage: %time test()
CPU times: user 2.56 s, sys: 0.04 s, total: 2.60 s
Wall time: 2.61 s
sage: %time test2()
CPU times: user 1.22 s, sys: 0.02 s, total: 1.24 s
Wall time: 1.24 s

The computation time with sage-4.6.2 has only been 1.25 s for test() and 0.67 s for test2(). I doubt that a regression in the polynomial ring creation can be avoided, when we really want category support for polynomial rings. However, I'll do my best to improve it.

[SimonKing]

Here is another innocent-looking detail that could have some impact: When many categories are created, it is essential that they are quickly initialised. By default, their name is determined from the type name at initialisation time - and that is costly.

The name should only be computed when needed - that calls for a lazy attribute. If a name is given explicitly, the name can still be overridden.

[nthiery]

Replying to SimonKing:

Here is another innocent-looking detail that could have some impact: When many categories are created, it is essential that they are quickly initialised. By default, their name is determined from the type name at initialisation time - and that is costly.

The name should only be computed when needed - that calls for a lazy attribute. If a name is given explicitly, the name can still be overridden.

+1

[jdemeyer]

Hi Simon, thanks for all this work! I will certainly do tests of these patches, to see whether they don't break anything and also timing tests. However, I will not review the patches themselves, I am not at all familiar with coercion.

[SimonKing]

Replying to jdemeyer:

Hi Simon, thanks for all this work! I will certainly do tests of these patches, to see whether they don't break anything and also timing tests.

Before you start: I just added another patch. The patch is not tested yet. It fixes some more doc string formatting, and it provides some smaller improvements. For example, it removes import statements from __init__ methods. It also introduces a cached function that computes the category used for a homset - the same computation used to happen repeatedly during homset creation. Also, the string representation is now only computed when needed - not during initialisation.

The effect of these improvements is certainly not as evident as what is done in the first patch. Nevertheless, since elliptic curve computations involve the creation of thousands of polynomial rings over finite fields, it is noticeable.

Apply trac11900_no_categories_for_matrices.patch trac11900_category_speedup.patch trac11900_further_tweaks.patch

[jdemeyer]

In a preliminary testing version of sage-4.7.3.alpha0, I get two doctest failures:

sage -t  "devel/sage/sage/categories/finite_enumerated_sets.py"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/devel/sage/sage/categories/finite_enumerated_sets.py", line 58:
    sage: FiniteEnumeratedSets()(GF(3))
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_3[2]>", line 1, in <module>
        FiniteEnumeratedSets()(GF(Integer(3)))###line 58:
    sage: FiniteEnumeratedSets()(GF(3))
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/local/lib/python/site-packages/sage/categories/category.py", line 485, in
__call__
        return self._call_(x, *args, **opts)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/local/lib/python/site-packages/sage/categories/finite_enumerated_sets.py",
 line 75, in _call_
        return EnumeratedSets()._call_(X)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/local/lib/python/site-packages/sage/categories/enumerated_sets.py", line 1
27, in _call_
        raise NotImplementedError
    NotImplementedError
**********************************************************************

and

sage -t  "devel/sage/sage/rings/residue_field.pyx"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.3.alpha0/devel/sage/sage/rings/residue_field.pyx", line 422:
    sage: F.category()
Expected:
    Category of finite fields
Got:
    Category of fields
**********************************************************************

[SimonKing]

Replying to jdemeyer:

sage: FiniteEnumeratedSets?()(GF(3))

Exception raised:

Yep. As I said, the last patch wasn't tested, yet.

[SimonKing]

Actually, I believe that FiniteEnumeratedSets()._call_(X) is flawed anyway: It returns return EnumeratedSets()._call_(X), thus, does not relate with finiteness. On the other hand, EnumeratedSets()._call_ returns a finite enumerated set, or raises an error.

The problem actually comes from the fact that the last patch accidentally changed the category of GF(3) from FiniteFields() to Fields(). So, that's a bug.

[SimonKing]

I wonder: What is the correct category for a finite field? Category of finite fields? Or Join of Category of subquotients of monoids and Category of quotients of semigroups and Category of finite fields? The latter would come out of the initialisation as a quotient ring, that is part of the initialisation of a finite field.

[SimonKing]

PS: I would argue as follows.

• Currently, the category of a finite field is FiniteFields(), without quotient ring stuff. So, let's be conservative and keep it.
• Currently, FiniteField_prime_modn is both initialised as a FiniteField and as a QuotientRing. With my patch, for saving time, it is just initialised as a Parent with the category of finite fields, and then as a quotient ring, which overrides that category.
• That sounds like a vaste of time. Therefore, QuotientRing.__init__ should only try to determine a "category with quotient stuff in it" when the category has not been initialised before.

Doing so yields the following timing (which is even a little better then pre-#9138):

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)
....:
sage: %time test()
CPU times: user 0.49 s, sys: 0.01 s, total: 0.50 s
Wall time: 0.51 s

I'll update my patch in a few minutes.

[SimonKing]

Some further improvements of field/ring/homset creation

[SimonKing]

I have updated the "further tweaks" patch. The two failing tests that Jeroen mentioned pass with the new patch version, and the timing for the creation of a finite field slightly improved.

[SimonKing]

A very pleasant result:

I was running the doc tests in sage/schemes (which seem to be the most critical). With sage-4.7.2.alpha2 (hence, without #9138), I obtain:

All tests passed!
Total time for all tests: 663.5 seconds

With sage-4.7.2.alpha3 (hence, with #9138) and the patches from #11911 and here, I obtain

All tests passed!
Total time for all tests: 597.0 seconds

In other words: The regression from #9138 apparently turned into a speed-up!

At Jeroen: You mentioned that you would not review it, because you are not so familiar with coercion. However, my own impression is that coercion plays almost no role in my patches (note that "new coercion for polynomial rings" is not part of the patches - it will be moved to a different ticket).

[jdemeyer]

Replying to SimonKing:

In other words: The regression from #9138 apparently turned into a speed-up!

That would be highly impressive it this is true!

We'll see about the reviewing. As said, first I want to test that it works and do some timings myself.

[nthiery]

Replying to jdemeyer:

Replying to SimonKing:

In other words: The regression from #9138 apparently turned into a speed-up!

That would be highly impressive it this is true!

I am impressed, but not really surprised! The category code (and related) had not been fine tuned, and Simon is getting ever more an expert at that :-)

We'll see about the reviewing. As said, first I want to test that it works and do some timings myself.

I should mention that I won't have time to do a detailed review. But I am following closely Simon's comments, and any lack of comment from me means I am +1 on his detailed proposed changes.

[nthiery]

Replying to SimonKing:

• Currently, the category of a finite field is FiniteFields(), without quotient ring stuff. So, let's be conservative and keep it.

+1, in particular since the upcoming #10963 is touching quite some the Finite* categories, and I'd like to reduce risks of conflicts.

Cheers,

Nicolas

[SimonKing]

I repeated the sage -t sage/schemes test. The improvement is smaller than in the first run, but I still see an improvement:

• 648.1 s with unpatched sage-4.7.2.alpha2
• 664.9 s with unpatched sage-4.7.2.alpha3
• 599.6 s with sage-4.7.2.alpha3 plus the patches.

However, it has only been 583.3 s in unpatched sage-4.6.2. Has the number of tests in sage/schemes increased since 4.6.2?

[jdemeyer]

Passes make ptestlong on sage.math.washington.edu.

[jdemeyer]

New timings using the same test files as before. Timings are best-out-of-3 wall times. "baseline" is actually sage-4.7.2.alpha3 minus various patches (#11587, #9138). "sage-4.7.3.alpha0" is a preliminary version of sage-4.7.3.alpha0, including the new PARI (#11130) and MPIR (#8664).

*** cyclomat.sage ***
sage-4.7.2.alpha2:      6.4s
baseline:               5.7s
baseline+#9138+#11900:  5.7s
sage-4.7.3.alpha0:      6.6s

*** ellbsd.sage ***
sage-4.7.2.alpha2:      6.8s
baseline:               5.9s
baseline+#9138+#11900:  7.7s
sage-4.7.3.alpha0:      6.4s

*** elltest1.sage ***
sage-4.7.2.alpha2:     23.5s
baseline:              22.4s
baseline+#9138+#11900: 25.9s
sage-4.7.3.alpha0:     23.4s

*** elltest2.sage ***
sage-4.7.2.alpha2:     18.5s
baseline:              18.0s
baseline+#9138+#11900: 16.5s
sage-4.7.3.alpha0:     17.7s

*** J0_46_disc.sage ***
sage-4.7.2.alpha2:      8.3s
baseline:               7.7s
baseline+#9138+#11900:  8.0s
sage-4.7.3.alpha0:      9.6s

This is some slowdown noticable in some tests, but it's not clear whether it is real, as there is quite some variation of runtime with some of these tests.

[SimonKing]

Hi Jeroen,

I understand your results that cyclomat.sage, elltest2.sage and J0_46_disc.sage are fine, while ellbsd.sage and elltest1.sage remain problematic.

I did five runs for each of the problematic tests, with sage-4.7.2.alpha2 and sage-4.7.2.alpha3+patches.

ellbsd.sage

4.7.2.alpha2

king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage ellbsd.sage

real    0m6.344s
user    0m5.180s
sys     0m0.380s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage ellbsd.sage

real    0m5.331s
user    0m4.932s
sys     0m0.308s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage ellbsd.sage

real    0m5.260s
user    0m4.812s
sys     0m0.356s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage ellbsd.sage

real    0m5.270s
user    0m4.848s
sys     0m0.336s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage ellbsd.sage

real    0m5.215s
user    0m4.836s
sys     0m0.288s

patched 4.7.2.alpha3

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage

real    0m6.392s
user    0m5.756s
sys     0m0.496s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage

real    0m5.928s
user    0m5.448s
sys     0m0.384s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage

real    0m5.654s
user    0m5.236s
sys     0m0.368s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage

real    0m5.576s
user    0m5.204s
sys     0m0.340s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage

real    0m5.599s
user    0m5.156s
sys     0m0.364s

elltest1.sage

4.7.2.alpha2

king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage elltest1.sage

real    0m19.189s
user    0m18.669s
sys     0m0.352s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage elltest1.sage

real    0m18.909s
user    0m18.417s
sys     0m0.380s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage elltest1.sage

real    0m19.463s
user    0m19.085s
sys     0m0.260s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage elltest1.sage

real    0m19.607s
user    0m19.205s
sys     0m0.276s
king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2$ time ./sage elltest1.sage

real    0m18.897s
user    0m18.445s
sys     0m0.328s

4.7.2.alpha3+patches

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage

real    0m18.420s
user    0m17.989s
sys     0m0.308s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage

real    0m18.273s
user    0m17.833s
sys     0m0.372s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage

real    0m18.461s
user    0m17.997s
sys     0m0.380s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage

real    0m18.416s
user    0m18.005s
sys     0m0.348s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage

real    0m19.687s
user    0m18.997s
sys     0m0.588s

Conclusion

I see a rather small slow-down in the first test, when comparing sage-4.7.2.alpha2 with "baseline+#9138+#11900"; it is smaller than the regression that you observe.

I can not confirm the slow-down that you observe in the second test: Here, I actually find a slight speed-up.

My setting is different, as I replace "baseline+#9138+#11900" with "sage-4.7.2.alpha3+#11900". Just to be on the safe side, here you see what I was working with:

king@mpc622:/mnt/local/king/SAGE/debug/sage-4.7.2.alpha2/devel/sage$ hg qtop
Keine Patches angewendet

versus

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3/devel/sage$ hg qapplied
trac11911_libsingular_pickling.patch
trac11900_no_categories_for_matrices.patch
trac11900_category_speedup.patch
trac11900_further_tweaks.patch

[SimonKing]

This ticket is related with #11935. There, the time for creation of parent and element classes of categories over different base rings is avoided. With the patches from here and the second of the two patches from #11935 applied to sage-4.7.2.alpha3, I find:

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage 

real	0m4.873s
user	0m4.408s
sys	0m0.364s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage 

real	0m4.957s
user	0m4.528s
sys	0m0.388s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage 

real	0m4.620s
user	0m4.288s
sys	0m0.280s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage 

real	0m4.615s
user	0m4.256s
sys	0m0.308s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage ellbsd.sage 

real	0m4.721s
user	0m4.344s
sys	0m0.344s

and

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage 

real	0m16.435s
user	0m16.025s
sys	0m0.292s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage 

real	0m16.981s
user	0m16.565s
sys	0m0.304s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage 

real	0m16.626s
user	0m16.173s
sys	0m0.396s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage 

real	0m16.950s
user	0m16.493s
sys	0m0.384s
king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.7.2.alpha3$ time ./sage elltest1.sage 

real	0m16.946s
user	0m16.461s
sys	0m0.412s

The result with the first patch from #11935 (one has to pick one of the two patches) is similar. That shows how much speed up is still possible with a clever usage of categories. But the methods used there go beyond what I am doing here - that's why I opened a separate ticket.

[jdemeyer]

With the second patch of #11935 added, all the testcases above are indeed faster than sage-4.7.2.alpha3-baseline (without #9138).

[SimonKing]

The patch bot starts with sage-4.7.1 and is unable to apply certain patches. Bad luck. But they should apply cleanly against sage-4.7.2.alpha4.

[SimonKing]

FWIW: Here is an example that should show that the regression is fixed.

I tested ./sage -t devel/sage/sage/schemes/. I obtain the following total running times:

• With sage-4.7.3.alpha0: 621.9 seconds
• plus #9138: 665.2 seconds
• plus #11900: 595.4 seconds

sage: (621.9-595.4)/621.9
0.0426113523074449
sage: (621.9-665.2)/621.9
-0.0696253416948063

So, the 7% regression from #9138 has been turned into a 4% speed-up.

[jdemeyer]

I hope you can find a reviewer to look at the code, I sent a message to sage-devel.

[was]

Jeroen's message is:

Simon King has a big patch at #11900 to speed-up categories.  There were
some regressions at #9138, this patch fixes all of these and moreover,
even speeds up some things.  This patch is quite important, there are
various tickets depending on it.

I have already checked that the patch works and that it fixes all
obvious regressions from #9138. Somebody with some understanding of
categories really needs to look at the code and review it.

[jdemeyer]

Milestone sage-4.7.3 deleted

[SimonKing]

The purpose of this ticket is explicit: Speed. I must admit that the code by which I obtain speed is sometimes a bit messy, specifically in is_subcategory, where I introduce additional special cases in a method that should be fairly generic.

There is a follow-up ticket #11943 that is concerned with consistency of the category graph. Question: Is it ok to keep the messy code from here and leave cleaning of is_subcategory to #11943?

[nthiery]

Replying to SimonKing:

The purpose of this ticket is explicit: Speed. I must admit that the code by which I obtain speed is sometimes a bit messy, specifically in is_subcategory, where I introduce additional special cases in a method that should be fairly generic.

There is a follow-up ticket #11943 that is concerned with consistency of the category graph. Question: Is it ok to keep the messy code from here and leave cleaning of is_subcategory to #11943?

If that makes your life easier, I say go for it. Anyway, it's likely that the second patch will go in very soon after, if not in the same release.

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

There is a follow-up ticket #11943 that is concerned with consistency of the category graph. Question: Is it ok to keep the messy code from here and leave cleaning of is_subcategory to #11943?

If that makes your life easier, I say go for it.

Thank you! Yes, it would make life easier for me, because otherwise I'd need to take part of my changes from #11943, use it to change the patch from here, and then also update the patch from #11943.

[nthiery]

We discussed this patch quite some with Simon. One of the issue that came up is whether it was ok to replace the nice idiom X in Fields() (or friends) with X.is_field() when time is critical. I consider that those two idioms have different semantic: X in Fields() means: do we already know that X is a ring (that is, X.category() is a subcategory of has Fields()), whereas X.is_field() may launch an expensive computation to detect whether X is actually a field or not.

The change was motivated by the fact that, in may important cases, X.is_field() is much faster than X in Fields():

    sage: R = QQ['x']
    sage: %timeit R.is_field()
    625 loops, best of 3: 442 ns per loop
    sage: %timeit R in Fields()
    625 loops, best of 3: 18 µs per loop

However, after experimenting together, we found out that the difference can most likely be made not so significant. The patch I just attached is a good step in that direction. Simon is currently experimenting with an implementation of Cython methods within Python classes.

Hopefully, with that patch or some variant thereof, the changes X in Fields() -> X.is_field() in trac11900_category_speedup.patch can be reverted while still solving the original regression.

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

The change was motivated by the fact that, in may important cases, X.is_field() is much faster than X in Fields(): ... Hopefully, with that patch or some variant thereof, the changes X in Fields() -> X.is_field() in trac11900_category_speedup.patch can be reverted while still solving the original regression.

I hope so! I think that the following makes sense: We change here the __contains__ method for Rings(), because that is what is needed most. The change shall be: Instead of creating the list of all super categories and then searching Rings() in that list, one should test whether the parent class of is a subclass of the parent class of Rings(). In particular, this can be put into Cython, where IIRC subclass checks are much faster than in Python.

On the long run, we could think of making subclass check of parent_class the default way of testing is_subcategory (this is one of the things we had discusses). Of course, when sharing parent classes (as in #11935), this has to be weakened.

[SimonKing]

Hi Nicolas, it seems that your "singleton" patch does not contain the pyx file.

By the way, since is_subcategory is used by __contains__, I would somehow prefer to not cythonise __contains__ but cythonise is_subcategory instead.

Anyway. Since the change concerns "speedup for category framework", the new stuff shall remain on this ticket. Do we agree on that?

Of course, after cythonising is_subcategory, I need to change my patches from #11943 and #11935 as well. In particular #11935 will be tricky, because the idea of "testing subcategories via subclasses of the parent class" will not work if parent classes are shared. But that problem shall be dealt with there and not here.

[nthiery]

An experimental implementation of optimized base class for singleton categories

[nthiery]

Replying to SimonKing:

Hi Nicolas, it seems that your "singleton" patch does not contain the pyx file.

Oops! Fixed!

By the way, since is_subcategory is used by __contains__, I would somehow prefer to not cythonise __contains__ but cythonise is_subcategory instead.

I see your point.

However, one would need to use the subcategory_hook: in `x in Rings()`, the is_subcategory that is called is that of the category of x, not of Rings(). So altogether it might be not as fast as when cythonizing contains. Also, since the optimized code for contains is small, I can live with the tiny code duplication due to the "manual inlining of is_subcategory" in contains.

Anyway. Since the change concerns "speedup for category framework", the new stuff shall remain on this ticket. Do we agree on that?

Definitely.

Of course, after cythonising is_subcategory, I need to change my patches from #11943 and #11935 as well. In particular #11935 will be tricky, because the idea of "testing subcategories via subclasses of the parent class" will not work if parent classes are shared. But that problem shall be dealt with there and not here.

Ah, I see, you are thinking of cythonizing is_subcategories via parent_class for *all* categories. Hmm, I haven't yet made up my mind about this. Unless it brings a clear general improvement (and not only for the specific regression this patch is about), shalle we not postpone that to later, and stick to a more local change (only about Rings and friends)?

Cheers,

Nicolas

[SimonKing]

@lazy_class_attribute? I didn't know about that!

Apparently there are further changes that the patch does not provide: Shouldn't there also be a change telling that Rings and Fields is a Category_singleton? So, replace "class Rings(Category)" by "class Rings(Category_singleton)"?

[SimonKing]

Replying to nthiery:

Ah, I see, you are thinking of cythonizing is_subcategories via parent_class for *all* categories.

Yes! Currently it would work, even for join categories. On the other hand, this could be a rather big change (so, better on a different ticket.

Hmm, I haven't yet made up my mind about this. Unless it brings a clear general improvement (and not only for the specific regression this patch is about), shalle we not postpone that to later, and stick to a more local change (only about Rings and friends)?

OK.

I don't know if we can do the change for Fields, though. Fields has a special __contains__ method, and I don't know if #9138 has really been strong enough to make it possible to use the default __contains__ instead.

Design question:

Apparently you suggest to implement a subclass of Category, so that Rings and Fields and so on inherit form this class rather than from Category. The other approach we discussed was to define cython functions and plug these functions into methods of python classes. I suggest that we do a couple of benchmarks, to see what's fastest. Doing that now...

[SimonKing]

You write that the Category_singleton uses an optimized class call. It is indeed slightly faster than the usual classcall, as it seems:

sage: from sage.categories.category_singleton import Category_singleton 
sage: class MyRingsSingleton(Category_singleton): 
....:     super_categories = Rings.__dict__['super_categories'] 
....:     
sage: MR = MyRingsSingleton()
sage: MR
Category of my rings singleton
sage: %timeit MyRingsSingleton()
625 loops, best of 3: 5.28 µs per loop
sage: %timeit Rings()
625 loops, best of 3: 6.92 µs per loop
sage: %timeit MyRingsSingleton()
625 loops, best of 3: 3.39 µs per loop
sage: %timeit Rings()
625 loops, best of 3: 6.92 µs per loop
sage: %timeit MyRingsSingleton()
625 loops, best of 3: 3.38 µs per loop
sage: %timeit Rings()
625 loops, best of 3: 7.02 µs per loop

I don't know why the first "timeit" for MyRingsSingleton is so match slower than the other two runs.

[SimonKing]

Replying to SimonKing:

You write that the Category_singleton uses an optimized class call. It is indeed slightly faster

"slightly" is ironical, as it is a factor of nearly two.

[SimonKing]

OMG, just for fun I made the same "benchmark" for the creation of the rational field, and look what I found:

sage: %timeit RationalField()
625 loops, best of 3: 75.4 µs per loop

That's bad!

[nthiery]

Replying to SimonKing:

Apparently there are further changes that the patch does not provide: Shouldn't there also be a change telling that Rings and Fields is a Category_singleton? So, replace "class Rings(Category)" by "class Rings(Category_singleton)"?

Yes, that's definitely the intention if we decide to go for this approach. At this point, it's just an experiment, so I did not bother implementing it.

[nthiery]

Replying to SimonKing:

Replying to SimonKing:

You write that the Category_singleton uses an optimized class call. It is indeed slightly faster

"slightly" is ironical, as it is a factor of nearly two.

:-)

One can expect more progress by:

• cythonizing ConstantFunction?
• cythonizing ClassCallMetaclass?.classcall

This probably should eventually be generalized to a Singleton subclass of UniqueRepresentation?.

[SimonKing]

I changed Rings(Category) into Rings(Category_singleton) (but then had to remove the rings_contains function in the pyx file, by cyclic import).

First, because of your optimisation of the classcall, one has

sage: %timeit Rings()
625 loops, best of 3: 3.42 µs per loop

Second, one has

sage: R = Rings()
sage: P.<x,y,z> = QQ[]
sage: P in R
True
sage: %timeit P in R
625 loops, best of 3: 1.38 µs per loop

Using PyType_IsSubtype from sage/ext/python_type.pxi, one comes down to 1.08 µs.

You use a lazy class attribute not only for the classcall, but also for the containment test. If one writes the containment test directly as a method (recall: We are here in a cython file!), one has 1.53 µs. So, to my surprise, the lazy class attribute trick works well also for performance!

Using a similar approach for computing the hash works as well. Namely, for a singleton class, it should be fine if the hash of the (single) instance is not id of the instance but id of the class. With the following code

cdef class hash_c(object):
    cdef long n
    def __init__(self, cls):
        self.n = id(cls)
    def __call__(self):
        return self.n

class Category_singleton(Category):
    ...
    @lazy_class_attribute
    def __hash__(cls):
        return hash_c(cls)

I obtain

sage: %timeit {R:1}
625 loops, best of 3: 695 ns per loop

Without that trick, it is 1.46 µs.

[SimonKing]

And the very good news is:

sage: R = Rings()
sage: MS = MatrixSpace(QQ,2)
sage: MS.is_ring.__module__
'sage.categories.rings'
sage: %timeit MS.is_ring()
625 loops, best of 3: 3.94 µs per loop
sage: %timeit MS in R
625 loops, best of 3: 1.41 µs per loop

So, the parent method is_ring that I introduced for speed reasons is now not the fastest thing to do. However, we still have

sage: P.<x,y,z> = QQ[]
sage: %timeit P.is_ring()   # that's a cython method defined for sage.rings.ring.Ring
625 loops, best of 3: 400 ns per loop

and

sage: %timeit MS in Rings()  # Adding the time needed to call Rings()
625 loops, best of 3: 5.09 µs per loop

[SimonKing]

Another improvement: It is very easy to cythonise ConstantFunction. Doing so improves the time for calling Rings(), for example:

sage: P.<x,y,z> = QQ[]
sage: %timeit Rings()
625 loops, best of 3: 2.05 µs per loop
sage: P in Rings()
True
sage: %timeit P in Rings()
625 loops, best of 3: 3.24 µs per loop

[SimonKing]

I have attached a new patch, which is your patch but with the modifications I explained above.

[nthiery]

Replying to SimonKing:

I have attached a new patch, which is your patch but with the modifications I explained above.

That all sounds good! Do you mind folding the different ideas we agreed upon in a single overview patch (unless you insist on keeping some of the changes cleanly separated). Then I'll do a final review and it will be good to go!

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

Replying to SimonKing:

I have attached a new patch, which is your patch but with the modifications I explained above.

That all sounds good! Do you mind folding the different ideas we agreed upon in a single overview patch

Do you mean "combine the four patches into one"? Or are there ideas concerning singleton that we discussed (for this ticket; I know that we had further ideas for other tickets) and are not included in the singleton patch yet?

I succeeded to save yet another bit of time: Use the fact that the argument of __contains__ should be a CategoryObject, or it is no object in a category.

Moreover, I found that it is both easier and slightly faster to use ConstantFunction for the __hash__.

And finally, I tried to get rid of the custom __contains__ method of Fields(). It should all use categories by now.

Current timings are:

sage: MS = MatrixSpace(QQ,2)
sage: P.<x,y,z> = QQ[]
sage: RC = Rings()
sage: FC = Fields()
sage: F3 = GF(3)
sage: %timeit Rings()
625 loops, best of 3: 2.04 µs per loop
sage: %timeit Fields()
625 loops, best of 3: 2.08 µs per loop
sage: %timeit MS in RC
625 loops, best of 3: 726 ns per loop
sage: %timeit MS in FC
625 loops, best of 3: 793 ns per loop
sage: %timeit F3 in RC
625 loops, best of 3: 667 ns per loop
sage: %timeit F3 in FC
625 loops, best of 3: 671 ns per loop
sage: %timeit {FC:1,RC:2}
625 loops, best of 3: 1.37 µs per loop
sage: %timeit hash(FC)
625 loops, best of 3: 352 ns per loop

The patch still needs work: Documentation needs to be written, and tests need to pass (I didn't try yet). But of course you can already see whether you might like the result.

Apply trac11900_no_categories_for_matrices.patch trac11900_category_speedup.patch trac11900_further_tweaks.patch trac_11900-category_singleton-sk.patch

[SimonKing]

Ah yes! One of the things that should be done in the finalisation of the patch is: Revert the use of is_ring, as P in Rings() is now competitive. But is there more to do than that and the documentation?

[SimonKing]

For the record: With the latest patches, one gets some doctest errors, but they seem managable:

        sage -t  devel/sage-main/sage/rings/polynomial/polynomial_quotient_ring.py # 6 doctests failed
        sage -t  devel/sage-main/sage/categories/pushout.py # 1 doctests failed
        sage -t  devel/sage-main/sage/rings/polynomial/polynomial_quotient_ring_element.py # 6 doctests failed
        sage -t  devel/sage-main/sage/combinat/debruijn_sequence.pyx # 21 doctests failed
        sage -t  devel/sage-main/sage/misc/constant_function.pyx # 2 doctests failed
        sage -t  devel/sage-main/sage/categories/category_singleton.pyx # 1 doctests failed

Concerning timings, I find with sage-4.7.2+#9138+the stuff from here the following results for the benchmarks that I posted five weeks ago. By "vanilla sage", I mean sage-4.7.2.alpha2 unpatched (copying the timings from above):

Creation of Matrix spaces

It is as with the previous patch versions, hence, faster than vanilla sage sage (0.38 s cpu):

sage: def test():
....:     for i in xrange(5000):
....:         MS = MatrixSpace(QQ,i)
....:
sage: %time test()
CPU times: user 0.25 s, sys: 0.01 s, total: 0.26 s
Wall time: 0.26 s

Creation of finite fields

It is faster than with the previous patches. Even better, it is now faster than vanilla sage (0.60 s cpu), which has not been the case with the previous patches:

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)
....:
sage: %time test()
CPU times: user 0.53 s, sys: 0.00 s, total: 0.53 s
Wall time: 0.53 s

Creation of polynomial rings

It is slower than vanilla sage (2.41 s cpu), but a bit faster than what I had with the patches 5 weeks ago (4.32 s CPU):

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['x']
....:         P = GF(p)['x','y']
....:
sage: %time test()
CPU times: user 3.92 s, sys: 0.05 s, total: 3.97 s
Wall time: 3.98 s

The two critical elliptic curve tests

Recall that the following two were most critical and were the reason for creating this ticket:

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.96 s, sys: 0.08 s, total: 4.04 s
Wall time: 4.25 s

That's about as fast as vanilla sage (CPU time went up a bit, wall time went down a bit)

sage: def test():
....:     E = EllipticCurve('389a')
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:
sage: %time test()
CPU times: user 16.53 s, sys: 0.14 s, total: 16.67 s
Wall time: 16.72 s

Again, that can very well compete with vanilla sage (16.57 s cpu, 16.77 s wall).

TODO

Instead of P.is_ring(), define _Rings = Rings() and test P in _Rings. Nicolas, please tell whether I forgot further things todo on this ticket.

[nthiery]

Replying to SimonKing:

Ah yes! One of the things that should be done in the finalisation of the patch is: Revert the use of is_ring, as P in Rings() is now competitive. But is there more to do than that and the documentation?

As far as I remember, this is it indeed.

And yes, I meant to combine all four patches for this ticket into one (it makes it easier to get an overview). Thanks!

Cheers,

Nicolas

[SimonKing]

Some of the errors are due to the fact that still some fields are not initialised as fields. For example: Laurent series rings.

sage: P = QQ[['x']]
sage: F = Frac(P)
sage: F.is_field()
True
sage: F.category()
Category of rings

So, here is yet another case of a parent whose category should better be properly initialised.

[SimonKing]

Most doctest errors are easy to fix. So, let us discuss the errors for polynomial quotient rings.

I guess polynomial quotient rings are the reason why is_field and the custom implementation of sage.categories.fields.Fields.__contains__ (which does call is_field) have originally been introduced: It is often a waste of time to test during initialisation whether a polyonomial quotient ring is a field or not.

By the way, is_field is currently not cached, but of course should be.

So, what shall we do? Perhaps this is one of the cases where we don't want to fully initialise the category during __init__?

I would argue as follows:

• If we do Q in Fields() for a polynomial quotient ring Q, then currently (that's to say: before my patch) Q.is_field() is called. In other words: Currently, Q in Fields() does trigger a potentially expensive computation, but that computation is not done during initialisation.
• Our aim is to get rid of the custom Fields.__contains__. Since Q in Fields() currently triggers a potentially expensive test, it should be OK if this is also done in future.
• When using the default Category_singleton.__contains__ for Fields(), then Q in Fields() involves calling Q.category().parent_class. Hence, Q.category() could be the right spot for triggering the field test.

Suggestion

During __init__, a polynomial quotient ring should be initialised as an object in the category of commutative algebras (not rings, as it is now). Moreover, polynomial quotient rings should have a custom category() method, different from the one inherited from CategoryObject.

If Q.category() is called, then it shall be tested whether Q is a field. If it is, then the category initialisation is repeated with the correct category.

Implementation

For that purpose I'd implement a new method (perhaps called _refine_category(self, category)) for category objects: P._refine_category(C) will change the original category into its join with C.

After using this method, the custom Q.category() method would override itself by the usual one. In other words, I imagine something like the following for polynomial quotient rings:

import types
def category(self):
    if self.is_field():
        self._refine_category(Fields())
    cat = CategoryObject.category(self)
    self.category = types.MethodType(CategoryObject.category, self, CategoryObject)
    return cat

[SimonKing]

Hmm. This will be more difficult than I thought: There are lots of is_field methods in Sage. Apparently some of them are not cached. It would probably not be feasible to have a custom category() method in all cases.

What could one do instead?

I see the following options:

1. We could remove the custom __contains__ method and restrict ourselves to fixing the case of PolynomialQuotientRing in the way I indicated. After all, this is the only case of failing doctests.
2. We could remove the custom __contains__ method and the category stuff for all parents with an is_field() method.
3. We could preserve the custom __contains__ method of Fields(), but ensure that the potentially time-consuming additional tests are cached. Instead of caching all is_field() methods (there are quite many), I suggest to use a cache on the function sage.rings.field.is_Field. Namely, this is what is really called in the custom __contains__ method.

I think the first solution is not really a solution. The second is too much for this ticket. The third seems fine to me, though. What do you think?

In more detail: We introduce the _refine_category() method to CategoryObject. We impose a cache on sage.rings.field.is_Field. In sage.rings.field.is_Field, we use _refine_category() on those rings that were found to be a field.

Since is_Field is cached, the _refine_category() method will be called at most once, and sage.categories.fields.Fields.__contains__ will also be faster because of the cache.

[SimonKing]

One slight complication: The current implementation of Fields.__contains__ starts with calling super(Fields,self).__contains__. But the latter is a lazy class attribute - and thus overrides Fields.__contains__.

Probably it is needed to avoid the call to super.

[SimonKing]

What I now did: Fields.__contains__ uses a helper that compares parent classes (the same that is used by Category_singleton). If that fails, then is_field() is called. If it turns out to be a field then the category is updated.

Without the singleton patch:

sage: P.<x> = QQ[]
sage: Q = P.quotient(x^2+2)
sage: Q in Fields()
True
sage: _Fields = Fields()
sage: %timeit Q in _Fields
625 loops, best of 3: 21.1 µs per loop
sage: isinstance(Q, Fields().parent_class)
False

It is so slow, because Q.category() gives the wrong answer, thus is_Field must be called, hence, Q.is_field() is called, and it is not cached.

With my experimental (not yet published) patch, we would get

sage: P.<x> = QQ[]
sage: Q = P.quotient(x^2+2)
sage: isinstance(Q, Fields().parent_class)
False
sage: Q in Fields()
True
sage: isinstance(Q, Fields().parent_class)
True
sage: _Fields = Fields()
sage: %timeit Q in _Fields
625 loops, best of 3: 662 ns per loop

In other words: In the first place, Q is not initialised as a field. But if Q in Fields() returns true (which is because of calling is_Field) then the category of Q is refined. Hence, the next time of calling Q in Fields() the shortcut of Category_singleton can be used.

What do you think?

[SimonKing]

There is something wrong with Category_singleton: It cant' be subclassed.

sage: class Test(Rings):
....:     pass
....:
sage: T = Test()
sage: T
Category of rings

In other words, making __classcall__ a lazy class attribute won't work, since subclasses need a different __classcall__.

Or do you see a mechanism that allows for subclassing?

The problem occurs if one makes EnumeratedSets inherit from Category_singleton, since DeBruijnSequences subclass enumerated sets.

[nthiery]

Replying to SimonKing:

There is something wrong with Category_singleton: It cant' be subclassed.

sage: class Test(Rings):
....:     pass
....:
sage: T = Test()
sage: T
Category of rings

In other words, making __classcall__ a lazy class attribute won't work, since subclasses need a different __classcall__.

Or do you see a mechanism that allows for subclassing?

The problem occurs if one makes EnumeratedSets inherit from Category_singleton, since DeBruijnSequences subclass enumerated sets.

I still need to thing about the rest. For that issue, maybe Category_singleton should define classcall_private instead of classcall (see ClasscallMetaclass? for the difference)? Hmm, no, that probably won't work since we want to subclass Category_singleton. I assume the wrong thing is that DeBruijnSequences? subclasses EnumeratedSets?, where the intention probably was to be a subcategory.

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

I assume the wrong thing is that DeBruijnSequences? subclasses EnumeratedSets?, where the intention probably was to be a subcategory.

Probably.

Another possibility: Category_singleton.__classcall__ should be a usual class method, but store the unique instance in an attribute (say, _inst) of the class - or, to be precise, in the dictionary of the class. Then, we could do something like

class Category_singleton(Category):
    @staticmethod
    def __classcall__(object cls):
        try:
            return (<dict>cls.__dict__)['_inst']
        except KeyError:
            inst = Category.__classcall__(cls)
            cls._inst = inst
            return inst

Then, I get

sage: from sage.categories.category_singleton import Category_singleton
sage: %timeit S=Category_singleton()
625 loops, best of 3: 2.13 µs per loop
sage: %timeit S=Singleton()
625 loops, best of 3: 2.07 µs per loop

So, the timing seems ok, and it is subclassable:

sage: class Test(Singleton): pass
....:
sage: Singleton()
Category of singleton
sage: Test()
Category of test

[SimonKing]

Probably my suggestion on __classcall__ is insufficient, since __contains__ is implemented as a lazy class attribute as well.

So, first option: Work around the lazy class attributes, by dispatching similar to what I indicated above.

Second option: Don't allow subclassing of singletons. In that case, DeBruijnSequence needs to copy the _call_ method from enumerated sets, and of course declare enumerated sets as a super category.

Or perhaps there is a way around: We could use a classcall similar to what I did in my previous post and add two lines that override the values of __contains__ and __hash__ obtained from super-classes.

Well, I need to experiment a bit...

[SimonKing]

I think I can make subclassing work. I get

sage: class Test(Rings): pass
....:
sage: Test()
Category of test
sage: Rings()
Category of rings
sage: ZZ in Rings()
True
sage: ZZ in Test()
False
sage: hash(Rings())
15828944
sage: hash(Test())
76231760
sage: %timeit Rings()
625 loops, best of 3: 2.44 µs per loop
sage: %timeit Test()
625 loops, best of 3: 2.58 µs per loop

However, De Bruijn sequences would still not work as they are written now: They are no singletons.

So, questions to you:

• Do we want to allow for subclasses? If we don't, shall the attempt to create a subclass of a subclass of Category_singleton result in an error?
• Should the attempt to do Category_singleton() result in an error? Namely, this would destroy all attempts to create a new singleton category in that session.
• Do we want that EnumeratedSets is a singleton? Then de Bruijn sequences have to change.

[SimonKing]

I'd of course appreciate your answer to my questions, but here is how I would answer:

Replying to SimonKing:

• Do we want to allow for subclasses?

We don't. Subclassing a singleton means that it is not a singleton.

If we don't, shall the attempt to create a subclass of a subclass of Category_singleton result in an error?

I think a big fat warning in the docs should be enough.

• Should the attempt to do Category_singleton() result in an error? Namely, this would destroy all attempts to create a new singleton category in that session.

It might be reasonable.

• Do we want that EnumeratedSets is a singleton? Then de Bruijn sequences have to change.

I think we do want that enumerated sets form a singleton. I really don't see why de Bruijn sequences are not simply copying the _call_ method from the enumerated sets.

[nthiery]

Replying to SimonKing:

I'd of course appreciate your answer to my questions, but here is how I would answer:

Replying to SimonKing:

• Do we want to allow for subclasses?

We don't. Subclassing a singleton means that it is not a singleton.

+1 (just to be pedantic: Subclassing a concrete singleton class means that ...)

If we don't, shall the attempt to create a subclass of a subclass of Category_singleton result in an error?

I think a big fat warning in the docs should be enough.

+1. The above should be just explained.

• Should the attempt to do Category_singleton() result in an error? Namely, this would destroy all attempts to create a new singleton category in that session.

It might be reasonable.

Category_singleton() won't pass the TestSuite? since it contains abstract methods. I think this is enough.

• Do we want that EnumeratedSets is a singleton? Then de Bruijn sequences have to change.

I think we do want that enumerated sets form a singleton.

+1. But we don't necessarily have to do it in this patch if this is inconvenient.

I really don't see why de Bruijn sequences are not simply copying the _call_ method from the enumerated sets.

Especially since the copy can easily be done with something like:

class DeBruijnSequences
    ...

    _call_ = EnumeratedSets.__dict__['_call_']

Feel free to postpone that (making EnumeratedSets? a singleton+fixing de BruijnSequences?) to a later patch. Though.

I need to check what exactly is the use case for their _call_ method. Maybe a candidate for CategoryMethods? in the long run.

[SimonKing]

Replying to nthiery:

Replying to SimonKing:

If we don't, shall the attempt to create a subclass of a subclass of Category_singleton result in an error?

I think a big fat warning in the docs should be enough.

+1. The above should be just explained.

Meanwhile I think raising an error would not hurt. Namely, __classcall__ can easily test whether the given class is anything that is not a direct subclass of Category_singleton. Hence, subclassing Rings will be illegal, and calling Category_singleton() will also be illegal. And moreover, this test would only happen once, namely before creating the unique instance of the singleton. So, if will have no performance penalty for %timeit Rings().

I think we do want that enumerated sets form a singleton.

+1. But we don't necessarily have to do it in this patch if this is inconvenient.

OK. I am now testing a patch version where EnumeratedSets is the only singleton that is not implemented using Category_singleton.

Especially since the copy can easily be done with something like:

class DeBruijnSequences
    ...

    _call_ = EnumeratedSets.__dict__['_call_']

Can it use a method of one class for another class that is not a subclass?

You are right that it should be a use case of category methods (IIRC these are methods that are inherited by subcategories).

[nthiery]

Replying to SimonKing:

Meanwhile I think raising an error would not hurt. Namely, __classcall__ can easily test whether the given class is anything that is not a direct subclass of Category_singleton. Hence, subclassing Rings will be illegal, and calling Category_singleton() will also be illegal. And moreover, this test would only happen once, namely before creating the unique instance of the singleton. So, if will have no performance penalty for %timeit Rings().

OK. I am now testing a patch version where EnumeratedSets is the only singleton that is not implemented using Category_singleton.

+1 on both.

Especially since the copy can easily be done with something like:

class DeBruijnSequences
    ...

    _call_ = EnumeratedSets.__dict__['_call_']

Can it use a method of one class for another class that is not a subclass?

Yup: unlike EnumeratedSets?._call_, EnumeratedSets?.dict_call_? is the original Python *function*, before it was transformed into a method of EnumeratedSets?. Not the nicest idiom on earth, but the trick works ...

Cheers,

Nicolas

[SimonKing]

I really don't know. Do we want to properly initialise the category of a polynomial quotient ring? If we do, then we also need to provide it with implementations of lift, ambient and retract.

So, I see two options:

• Provide a polynomial quotient ring just with the category of commutative algebras over its base field, so that the test suites pass for now. Deal with a proper initialisation (adding lift, ambient, retract) as Algebras(base_ring).Quotients() on a different ticket.
• Bloat this ticket up even more.

I prefer the first approach. I want to get this ticket finally off my plate. I really need #9138, and the longer it has to wait, the worse.

[SimonKing]

ARGL!!

The attempt to fix the category framework for polynomial quotient rings would end in a mess. I won't do it, at least not on this ticket.

[SimonKing]

And here is why it is a mess.

PolynomialQuotientRingElement has, of course, a _mul_ method. But when one defines the element class of a polnyomial quotient ring, then this _mul_ method is OVERRIDDEN by the category stuff, namely by _mul_parent. That must not happen.

[SimonKing]

The culprit is __init_extra__ in sage.categories.magmas, which does:

        def __init_extra__(self):
            """
                sage: S = Semigroups().example("free")
                sage: S('a') * S('b') # indirect doctest
                'ab'
                sage: S('a').__class__._mul_ == S('a').__class__._mul_parent
                True
            """
            # This should instead register the multiplication to the coercion model
            # But this is not yet implemented in the coercion model
            if (self.product != self.product_from_element_class_mul) and hasattr(self, "element_class") and hasattr(self.element_class, "_mul_parent"):
                self.element_class._mul_ = self.element_class._mul_parent

In other words, an EXISTING AND PROBABLY OPTIMIZED _mul_ is overridden by some generic slow stuff. So, I have to find out why this line is executed (it shouldn't).

[SimonKing]

Aha! It is an actual bug!

Namely, there are different parent methods called product defined in sage.categories.magmas: For Magmas, for Cartesian products of magmas, and for subquotients of magmas. Only in the first case is defined product_from_element_class_mul = product. So, if we have a quotient of a magma, then ALWAYS we will have self.product!=self.product_from_element_class_mul, and thus ALWAYS will the custom _mul_ of elements be overridden by the generic stuff.

I'm fixing that, and then I can also have the category framework with a proper quotient category for polynomial quotient rings.

[SimonKing]

Implement Category_singleton, cythonise ConstantFunction, and use both for most categories. Use categories for polynomial quotient rings

[SimonKing]

I have updated my last patch. I added some documentation, including a big fat warning concerning subclasses of subclasses of Category_singleton. In addition, I make sure that using Category_singleton directly does not destroy the cache of its subclasses. And I make polynomial quotient rings use categories.

However, it is not "needs review" yet, because I still have to remove the use of is_ring and is_field, and also I will eventually produce a combined patch.

[SimonKing]

I attached a file that combines the previous patches.

In addition, it uses ... in _Rings with _Rings=Rings() in many cases. However, I am now running doctests, and I get at least one error because of that. Apparently some ring is initialised as ring, but should better be a commutative ring.

Also I didn't check that all changes are documented.

So, still "needs work". But perhaps you like to have a look already...

Apply trac11900_category_speedup_combined.patch

[SimonKing]

It is frustrating. I thought it should all be fine by now, but no: Several errors.

It used to work fine before I replaced the use of "is_...". So, now I am wondering: Should one perhaps use a general mechanism for singletons similar to what I do for fields?

That's to say, if one has a category "Category of <name>s", then it should on the one hand provide a method "is_<name>" that constantly returns true, and on the other hand the __contains__ method should try whether some "is_<name>" method exists for the parent, and act accordingly (thus, refine the category of the parent if the parent turns out to be commutative).

Just some random thoughts before leaving the office.. :(

[SimonKing]

I think the ideas stated in my previous post are too radical.

But it seems that many of the errors can be fixed by using base classes as one should. For example, both Laurent polynomial and Laurent series rings inherit from CommutativeRing, but they only call the __init__ method of ParentWithBase.

I'll see how far this works...

[SimonKing]

The Weyl groups example is problematic. Reason seems to be that the logic behind "overriding the custom _mul_ method with generic stuff" doesn't apply to that example.

[SimonKing]

I fixed the "when to override _mul_" logic.

Also, I fixed some instances of a very bad phenomenon: There are many parents that inherit from classes such as sage.rings.ring.Field or sage.rings.ring.CommutativeRing -- but then they only call ParentWithGens.__init__!

For example, consider CFF.__init__. Before #9138, we used to have a custom Field.category() method, but I think there are only very rare cases in which CategoryObject.category() needs to be overridden. Moreover, #9138 made Field.__init__ initialise the category. But that won't help if we have subclasses of Field that are not calling Field.__init__. That is so annoying!

According to search_src('ParentWithGens\.__init__'), in order to really fix all issues, we'd still have to look at

tensor/differential_forms.py:110:        ParentWithGens.__init__(self, SR, \
groups/group.pyx:55:        sage.structure.parent_gens.ParentWithGens.__init__(self,
rings/real_mpfi.pyx:451:        ParentWithGens.__init__(self, self, tuple([]), False, category = Fields())
rings/multi_power_series_ring.py:305:        ParentWithGens.__init__(self, base_ring, name_list)
rings/complex_field.py:185:        ParentWithGens.__init__(self, self._real_field(), ('I',), False, category = Fields())
rings/integer_ring.pyx:236:        ParentWithGens.__init__(self, self, ('x',), normalize=False, category = EuclideanDomains())
rings/complex_mpc.pyx:297:        ParentWithGens.__init__(self, self._real_field(), ('I',), False)
rings/complex_double.pyx:158:        ParentWithGens.__init__(self, self, ('I',), normalize=False, category = Fields())
rings/complex_interval_field.py:144:        ParentWithGens.__init__(self, self._real_field(), ('I',), False, category = Fields())
rings/infinity.py:472:        ParentWithGens.__init__(self, self, names=('oo',), normalize=False)
rings/infinity.py:783:        ParentWithGens.__init__(self, self, names=('oo',), normalize=False)
rings/real_mpfr.pyx:308:        ParentWithGens.__init__(self, self, tuple([]), False, category = Fields())
rings/rational_field.py:213:        ParentWithGens.__init__(self, self, category = QuotientFields())
rings/number_field/number_field.py:1005:        ParentWithGens.__init__(self, QQ, name, category=category)
coding/linear_code.py:706:        ParentWithGens.__init__(self, base_ring)

This should go on a different ticket, that I am opening in a minute. Here, I'll just fix enough of these cases so that doc tests pass.

[SimonKing]

The follow-up ticket will be #12071.

[jdemeyer]

In your combined patch, it seems you wanted to rename (hg rename) constant_function.py to constant_function.pyx but instead you simply deleted constant_function.py.

Note that renaming is better than deleting the old file and adding the new file, since renaming is tracked by hg.

[SimonKing]

Replying to jdemeyer:

In your combined patch, it seems you wanted to rename (hg rename) constant_function.py to constant_function.pyx but instead you simply deleted constant_function.py.

I didn't. Mercurial did. In fact I had hg added the pyx file. But later, it somehow disappeared from the patch. Thank you for pointing that out.

Note that renaming is better than deleting the old file and adding the new file, since renaming is tracked by hg.

How can I rename it now? I already did delete the old and add the new file. So, how can I tell mercurial that it should instead rename the old file and incorporate the changes that I also did?

[SimonKing]

Replying to SimonKing:

Replying to jdemeyer:

In your combined patch, it seems you wanted to rename (hg rename) constant_function.py to constant_function.pyx but instead you simply deleted constant_function.py.

I didn't. Mercurial did. In fact I had hg added the pyx file. But later, it somehow disappeared from the patch. Thank you for pointing that out.

PS: I remember that I had a similar issue in the past. Then someone told me that I had to put things into my .hgrc file that ensure that new files will be part of the patch. Since then it worked - until today.

[nthiery]

Replying to SimonKing:

How can I rename it now? I already did delete the old and add the new file. So, how can I tell mercurial that it should instead rename the old file and incorporate the changes that I also did?

Brute force, but this should do the job:

    hg qpop
    # edit the patch, and remove all hunks about constant_function.*
    hg qpush
    hg mv constant_function.py constant_function.pyx

[SimonKing]

Replying to nthiery:

Replying to SimonKing: Brute force, but this should do the job:

Yep. Meanwhile I managed to fix it as well, with brute force. Submitting a hopefully final patch version in a few minutes.

[SimonKing]

Sorry, it takes a bit longer. I had forgotten to add some doc tests.

Nicolas, there is one change we talked about in Paris: The new _category_for_hom (which factors out the algorithm used inside the Hom function) is not using _meet_, but could use it. IIRC, you made such change, right? So, I should do as well.

[nthiery]

Simplification and refactorization of the logic in hom + typos

[nthiery]

Replying to SimonKing:

Nicolas, there is one change we talked about in Paris: The new _category_for_hom (which factors out the algorithm used inside the Hom function) is not using _meet_, but could use it. IIRC, you made such change, right? So, I should do as well.

Indeed; sorry, I should have posted the patch here since we did not get to work with the Sage-Combinat queue. Please merge it in your patch as you feel appropriate.

[SimonKing]

Replying to nthiery:

Indeed; sorry, I should have posted the patch here since we did not get to work with the Sage-Combinat queue. Please merge it in your patch as you feel appropriate.

Meanwhile I wonder whether that change shouldn't better be put on a different ticket. Namely, using the meet instead of the current algorithm (recall: The algorithm used in _category_for_hom was used before, I merely factored it out) actually would change things.

Namely, the meet may return a join category. But the current algorithm for determining the category for a homset will not return a join category, unless the categories of both parents coincide.

Example:

sage: Algebras(QQ)._meet_(Category.join([Fields(), ModulesWithBasis(QQ)]))
Join of Category of rings and Category of vector spaces over Rational Field
sage: PA = Parent(category=Algebras(QQ))
sage: PJ = Parent(category=Category.join([Fields(), ModulesWithBasis(QQ)]))
sage: H = Hom(PA,PJ); H
Set of Homomorphisms from <type 'sage.structure.parent.Parent'> to <type 'sage.structure.parent.Parent'>
sage: H.category()
Category of hom sets in Category of rings
sage: H.category().base_category
Category of rings

Using the meet would be a non-trivial change that probably has little to do with a speedup. So, better move it to another ticket, isn't it?

[nthiery]

Replying to SimonKing:

Using the meet would be a non-trivial change that probably has little to do with a speedup. So, better move it to another ticket, isn't it?

It's indeed a bug fix; so feel free to postpone it. Maybe in that case your factoring out could be postponned as well to that same ticket, to keep related changes together?

[SimonKing]

Replying to nthiery:

Replying to SimonKing: It's indeed a bug fix; so feel free to postpone it. Maybe in that case your factoring out could be postponned as well to that same ticket, to keep related changes together?

I am not so sure. If I remember correctly, factoring out and using cached method on it does provide a speed-up, and so does contribute to the purpose of this ticket.

I'll test after lunch whether I can show the speed-up in a more or less realistic example.

[SimonKing]

I tried to construct an example, but to my surprise I found no benefit, except of course that factoring the code out should be considered a clearer code.

I am now trying whether using the meet (and caching the meet) helps.

[SimonKing]

Replying to SimonKing:

I am now trying whether using the meet (and caching the meet) helps.

It seems that it doesn't make things faster.

Anyway. I am now running doctests for the version that uses the meet. If there are non-trivial errors then I'll postpone it. Otherwise, I'll include it in the patch here.

[SimonKing]

Replying to nthiery:

Indeed; sorry, I should have posted the patch here since we did not get to work with the Sage-Combinat queue. Please merge it in your patch as you feel appropriate.

Too bad. I did not realise that you had actually posted a patch. I made some of your changes myself, and now I have a hard time to merge your patch into mine.

[SimonKing]

Report on merging your reviewer patch:

• Using your changes in category.py, in particular caching of _meet_ and using a short patch in the case that the self.is_subcategory(other).
• If we use the _meet_ in sage/categories/homset.py then technically the algorithm already is factored out. So, I won't have a new function _category_for_homset anymore.
• I am using your changes in finite_field_prime_modn.py.

I will post a combined patch in a few minutes.

[SimonKing]

Finally I have posted a combined patch that also includes the recent ideas on _meet_, adds several doctests and fixes some of the missing calls to __init__ of base classes I was mentioning.

It also comprises Nicolas' review patch, with the only exception that I am now not using a separate function for computing the category of a homset.

If I see that correctly, all new stuff is backed up by doc tests. I did a complete test without using the review patch. I'm testing the latest patch version now, but I think it is "needs review"!

I think Nicolas is an author as well: He provided the original implementation of Category_singleton.

Apply trac11900_category_speedup_combined.patch

[SimonKing]

sage -testall -long has almost been successful: I got one rather trivial error.

File "/mnt/local/king/SAGE/stable/sage-4.7.2/devel/sage/sage/rings/residue_field
.pyx", line 422:
    sage: F.category()
Expected:
    Category of finite fields
Got:
    Join of Category of subquotients of monoids and Category of quotients of semigroups and Category of finite fields

Could this perhaps be taken care of in a reviewer patch? Or perhaps I'll fix it tomorrow morning

[SimonKing]

Replying to SimonKing:

sage -testall -long has almost been successful: I got one rather trivial error.

And even better: That test defines two residue fields F and k. For both, it skips two tests from the TestSuite ("_test_elements" and "_test_pickling"). But actually the whole test suite is fine now!

[SimonKing]

I have updated the patch. It now includes the doctest fixes for the residue fields, and in particular it runs the full test suite for residue fields now.

One question, though: The residue field example comprises two different kind of residue fields. The category of the first (called k in the example) is just Fields(). The category of the other is the more complicated one, with quotients etc. It could be a good idea to see why that happens. But not here...

Apply trac11900_category_speedup_combined.patch

[nthiery]

Replying to SimonKing:

I have updated the patch. It now includes the doctest fixes for the residue fields, and in particular it runs the full test suite for residue fields now.

One question, though: The residue field example comprises two different kind of residue fields. The category of the first (called k in the example) is just Fields(). The category of the other is the more complicated one, with quotients etc. It could be a good idea to see why that happens. But not here...

Apply trac11900_category_speedup_combined.patch

Thanks for all your work! It sounds good from your description. I'll try to review the patch by the end of this week.

Ah sorry, one more thing I should have though about earlier: all the Finite* categories will be refactored in the upcoming 10963, where will inherit from something else. To avoid a lot of trivial rebasing, do you mind if we postpone their singletonification to that later ticket?

If you agree, let me know if you prefer to strip those hunks out of the patch yourself, or let me do it.

Cheers,

Nicolas

[nthiery]

Replying to SimonKing:

I think Nicolas is an author as well: He provided the original implementation of Category_singleton.

Well, you really did 95% of the work and I would like you to be credited accordingly. If that was a research paper, I would be at best in the acknowledgement section. I suggest instead to:

• Add myself as an author in Category_singleton.pyx (so that I take the blames for what's broken in there) in my reviewer patch.
• Remove myself from the author list for this ticket.

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

• Add myself as an author in Category_singleton.pyx

Indeed. There, my only contribution was to add some documentation and raise an error that makes Category_singleton safer to use.

OK. But I thinkt this should really be a reviewer patch. Please make sure that you start with the most recent version of my patch -- the version that already includes most of what you did in the "review-nt" patch.

And I wouldn't mind to have the "FiniteBla" stuff be usual categories for now, even though eventually they shall be singletons as well.

I am looking forward to your reviewer patch and will now focus on rebasing #11943 and #11935.

[nthiery]

I have been through the patch, and have a *preliminary* reviewer patch which I am about to upload. There are still a couple things I'd like to do before posting my final reviewer patch:

• Avoid introducing new EXAMPLE instead of EXAMPLES

• use check=True/False? instead of category_checked=False/True?, for consistency with other similar use cases in Sage

(please argue if you prefer check_category rather than just check)

• Look again at is_Field, and in particular document the behaviour

• Finish removing some duplication in the init method of Ring/...

• Revert the changes to the FiniteCategories? (if that's alright with you, this will be done by stripping the combined patch, rather than undoing the changes in the reviewer patch)

• I forgot what we had discussed about CartesianProducts?.base: whether we should drop this method for the time being, or keep it.

By the way: I am not keen on calling one() in the initialization, as calculating one() may be very costly. In general, in our former experience with MuPAD-Combinat and Sage, creating elements (with an_element, ...) early in the initialization has been a repeated source of problems. When it is about sanity check, this can be postponed to the TestSuite?.

However, this ticket contains a lot of urgent and good stuff, and get soon into Sage, so this comment is for a later ticket.

I created another followup ticket: #12099

[SimonKing]

Hi Nicolas,

Do I understand correctly that you plan to do these things in your final reviewer patch? Or do you ask me to do the changes?

Best regards, Simon

[nthiery]

Replying to SimonKing:

Do I understand correctly that you plan to do these things in your final reviewer patch?

Indeed!

[nthiery]

Hi!

I am almost done (updated patch attached; please look at what I did for the init in IntegralDomain? and subclasses). However, I have a problem: with sage 4.8.alpha2 on Ubuntu Oneiric, with the two patches:

9138_flat.patch
trac11900_category_speedup_combined.patch

I am getting a lot of segmentation faults that I don't get without those patches. See the attached log (not: it is actually the log with my patch on top, but I am getting at least the same segfault in sage.structure.element without my patch; I'll post an updated log tomorrow morning).

Any clues?

[SimonKing]

The segmentation faults seem indeed related with the patches from here: Category_singleton is mentioned in the errors. Since I don't get the errors with sage-4.7.2 and IIRC also not with sage-4.8.alpha0, I a afraid I have to install yet another alpha version...

[SimonKing]

We need a rebase anyway: One hunk in matrix_space.py fails with sage-4.8.alpha3 (I guess this is because of a blocker for sage-4.8 that has recently been merged).

[SimonKing]

No, it wasn't the blocker, it is the M4RIE ticket #9562.

[nthiery]

Test failures with 4.8 alpha2 with the combined patch (but not my reviewer's patch) and dependency

[SimonKing]

Nicolas, could you try again with sage-4.8.alpha3?

Namely, I get

$ ../../sage -t sage/structure/element.pyx                                                    sage -t  "devel/sage-main/sage/structure/element.pyx"
         [5.4 s]

----------------------------------------------------------------------
All tests passed!
Total time for all tests: 5.5 seconds

with

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.8.alpha3/devel/sage$ hg qapplied
9138_flat.patch
trac11900_category_speedup_combined.patch

[SimonKing]

Also when having applied your patch as well, at least one of the tests in which you have observed a segfault works fine:

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.8.alpha3/devel/sage$ ../../sage -t sage/structure/element.pyx
sage -t  "devel/sage-main/sage/structure/element.pyx"
         [3.5 s]

----------------------------------------------------------------------
All tests passed!
Total time for all tests: 3.5 seconds

Actually note that with your patch it is only 3.5 seconds, while with my patch it is only 5.5 seconds.

I am now running all long tests. I have read your patch, and it looks very reasonable. I'd appreciate if you could re-run the tests with sage-4.8.alpha3.

[nthiery]

Ok, I'll download and compile alpha3 now. Answer late tonight ...

For information, I ran the test with -verbose on my machine, and the segfault can be triggered with

    sage: vector([])

[SimonKing]

Replying to nthiery:

For information, I ran the test with -verbose on my machine, and the segfault can be triggered with

sage: vector([])

Then it's fixed with alpha3:

king@mpc622:/mnt/local/king/SAGE/rebase/sage-4.8.alpha3$ ./sage
----------------------------------------------------------------------
| Sage Version 4.8.alpha3, Release Date: 2011-12-02                  |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
**********************************************************************
*                                                                    *
* Warning: this is a prerelease version, and it may be unstable.     *
*                                                                    *
**********************************************************************
sage: vector([])
()

with #9138 and the two patches from here applied.

I guess one should try to find out what ticket has changed the relevant bits in the vector creation, and list it as dependency.

[SimonKing]

With the setting described in my previous post, I get

$ ./sage -testall -long
...
The following tests failed:


        sage -t  -long -force_lib "devel/sage/sage/misc/constant_function.pyx"
        sage -t  -long -force_lib "devel/sage/sage/categories/vector_spaces.py"
Total time for all tests: 7980.3 seconds

That seems doable. I will try to solve it, update my patch probably tomorrow (needs to be rebased anyway), and then it will hopefully be solved.

[SimonKing]

Both our patches need to be change. Namely, I need to rebase mine because of #9562 and you need to modify yours, because it introduces the two errors that I indicated in the previous post.

First error: By my patch, _value is a cdef attribute of constant functions, thus, one can not access it in a doc test. Therefore, I had changed the corresponding doctest. But your patch re-introduces that test.

So, please remove the hunk

diff --git a/sage/misc/constant_function.pyx b/sage/misc/constant_function.pyx
--- a/sage/misc/constant_function.pyx
+++ b/sage/misc/constant_function.pyx
@@ -64,7 +64,7 @@ cdef class ConstantFunction(SageObject):
         """
         EXAMPLES::

-            sage: ConstantFunction(1)()
+            sage: ConstantFunction(1)._value
             1
         """
         self._value = value

from your patch.

Second error: There is one error message saying "base ring must be a field." But your reviewer patch changes one example, so that the same error message is expected without the dot in the end.

I am talking about the hunk

diff --git a/sage/categories/vector_spaces.py b/sage/categories/vector_spaces.py
--- a/sage/categories/vector_spaces.py
+++ b/sage/categories/vector_spaces.py
@@ -32,36 +32,33 @@ class VectorSpaces(Category_module):
...
...
             sage: VectorSpaces(ZZ)
             Traceback (most recent call last):
             ...
-            AssertionError: The base ring must be a field.
+            AssertionError: The base ring must be a field

+        With ``check=False``, the check is disabled, possibly enabling
+        incorrect inputs::
+
+            sage: VectorSpaces(ZZ, check=False)
+            Category of vector spaces over Integer Ring

[SimonKing]

It could be that I found the ticket that is responsible for making vector([]) work: #10595, which was merged in sage-4.8.alpha3. I have updated the list of dependencies accordingly.

[SimonKing]

No, sorry, I did not read carefully enough: #10595 was merged in sage-4.7.alpha3, not 4.8.alpha3. So, it was probably something else.

[SimonKing]

I have updated my patch, rebased against the M4RIE ticket.

[nthiery]

Replying to SimonKing:

First error: By my patch, _value is a cdef attribute of constant functions, thus, one can not access it in a doc test. Therefore, I had changed the corresponding doctest. But your patch re-introduces that test.

Ah, I see, that was the rationale! Sorry; I'll redo my undo :-)

Second error: There is one error message saying "base ring must be a field." But your reviewer patch changes one example, so that the same error message is expected without the dot in the end.

Ok, will do when the upgrade/compilation will be over (but that will be tomorrow)

Cheers,

Nicolas

[nthiery]

Replying to nthiery:

Ok, will do when the upgrade/compilation will be over (but that will be tomorrow)

Argl, I don't manage to compile alpha3 on my laptop. I sent a mail on sage-release, but I have no idea how much time this could be. Sorry, but I am stuck now.

In case you have a bit of spare time, the quickest would be for you to take over. What needs to be done:

• remove the chunk about ConstantFunctions? in my reviewer patch
• fold in my reviewer patch in yours
• fix the trivial doctest failure mentionned above
• remove all chunks in the resulting patch about Finite*
• CartesianProducts?.base: did not we decide to remove it? I don't remember; do as you feel appropriate
• EXAMPLE:: -> EXAMPLES::
• There might be a couple base_checked options left after my patch; change those to the standard check=
• Check that all tests pass

And then a last quick check from met, and that will be good to go!

Cheers!

Nicolas

[SimonKing]

Replying to nthiery:

• remove all chunks in the resulting patch about Finite*

I don't understand this one. Do you mean, I shall remove doctest stuff such as

+        sage: Category.join((Modules(ZZ), FiniteFields()), as_list=True)
+        [Category of modules over Integer Ring, Category of finite fields]

+        sage: sage.categories.algebra_functor.AlgebrasCategory.category_of(FiniteMonoids(), QQ)
+        Category of monoid algebras over Rational Field

or also this:

-class FiniteCoxeterGroups(Category):
+class FiniteCoxeterGroups(Category_singleton):

and

-class FiniteCrystals(Category):
+class FiniteCrystals(Category_singleton):

?

• CartesianProducts?.base: did not we decide to remove it? I don't remember; do as you feel appropriate

I think we said that it should be fine for base_ring at least. But I think we also said that this ticket should work stand-alone, and resulting messy code will be taken care of in #11943 and #11935.

Let's see what breaks when I remove that method.

• EXAMPLE:: -> EXAMPLES::

Sorry, I produced rather many EXAMPLE::s.

[SimonKing]

The doc tests aren't finished, but I observed several errors that are due to not having the base() method for Cartesian products.

So, I'd prefer to keep base() in, so that it works, and then take care of the problem in a nicer way in #11943 or #11935.

And please, tell me what the problem is with the "Finite*" stuff, and to what extent I have to change things: Only new doctests that use "Finite*", or should I also not use Category_singleton on "Finite*"?

Best regards,

Simon

[nthiery]

Replying to SimonKing:

The doc tests aren't finished, but I observed several errors that are due to not having the base() method for Cartesian products.

So, I'd prefer to keep base() in, so that it works, and then take care of the problem in a nicer way in #11943 or #11935.

Ok, keep it!

And please, tell me what the problem is with the "Finite*" stuff, and to what extent I have to change things: Only new doctests that use "Finite*", or should I also not use Category_singleton on "Finite*"?

It is *only* about not using Category_singleton for Finite* stuff, since those will be refactored soon anyway, so we might as well not create a conflict for nothing.

Thanks!

Nicolas

[SimonKing]

Replying to nthiery:

It is *only* about not using Category_singleton for Finite* stuff, since those will be refactored soon anyway, so we might as well not create a conflict for nothing.

I see. I'll change it accordingly and will then test whether there is a regression. Currently (that's to say when we keep the base() method) all doc tests pass.

[nthiery]

Replying to SimonKing:

I see. I'll change it accordingly and will then test whether there is a regression. Currently (that's to say when we keep the base() method) all doc tests pass.

Excellent. Thanks!

[SimonKing]

General speedup for the category framework, using Category_singleton for Finite*

[SimonKing]

I have attached two patches. Both of them combine the ideas of Nicolas and myself. The base() method is left in; this shall be taken care of at #11943 (I'll mark it as "todo" there, if it hasn't already been done).

With each patch (plus #9138), all doctests pass when starting with sage-4.8.alpha3. I was of course reading Nicolas' patches before including them, and I give his contribution a positive review.

For the record, I repeated all benchmarks that were discussed here. The main data are obtained with not using Category_singleton for Finite*. The timings with using Category_singleton and the timings with sage 4.6.2 are also given, namely in the comments.

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 5.61 s, sys: 0.19 s, total: 5.80 s
Wall time: 5.95 s  # 5.61 s
# 4.6.2: 6.35 s

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 4.23 s, sys: 0.09 s, total: 4.32 s
Wall time: 4.66 s  # 4.84 s
# 4.6.2: 4.69 s

sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:             
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 17.42 s, sys: 0.12 s, total: 17.54 s
Wall time: 17.60 s   # 17.59 s
# 4.6.2: 15.97 s

sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 12.46 s, sys: 0.08 s, total: 12.55 s
Wall time: 12.66 s   # 12.86 s
# 4.6.2: 14.05 s

sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 5.10 s, sys: 0.22 s, total: 5.32 s
Wall time: 5.33 s    # 5.74 s
# 4.6.2: 6.20 s

sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 3.87 s, sys: 0.06 s, total: 3.92 s
Wall time: 3.94 s    # 3.37 s
# 4.6.2: 3.46 s

sage: R = Rings()
sage: MS = MatrixSpace(QQ,3)
sage: %timeit MS in R
625 loops, best of 3: 765 ns per loop  # 774 ns
# 4.6.2: 10.1 µs
sage: %timeit MS.is_ring()
625 loops, best of 3: 4.18 µs per loop # 3.88 µs
# 4.6.2: BOOM

sage: def test():
....:     for i in xrange(5000):
....:         MS = MatrixSpace(QQ,i)
....:         
sage: %time test()
CPU times: user 0.25 s, sys: 0.00 s, total: 0.25 s
Wall time: 0.25 s   # 0.30 s
# 4.6.2: 0.37 s

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)
....:         
sage: %time test()
CPU times: user 0.60 s, sys: 0.00 s, total: 0.60 s
Wall time: 0.60 s   # 0.66 s
# 4.6.2: 0.57 s

sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(10000)]
sage: A = Algebras(GF(5))
sage: %time _ = [B.is_subcategory(A) for B in L]
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.07 s   # 0.06 s
# 4.6.2: 0.97 s

sage: v = vector(ZZ,range(100))
sage: %timeit L = v.list()
625 loops, best of 3: 11.7 µs per loop  # 12.1 µs
# 4.6.2: 16.4 µs
sage: v = vector(QQ,range(100))
sage: %timeit L = v.list()
625 loops, best of 3: 23.5 µs per loop  # 23.8 µs
# 4.6.2: 24.5 µs

The following is still not good, but I think #11935 will solve that problem:

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['t','x','z']
....:         
sage: %time test()
CPU times: user 2.84 s, sys: 0.05 s, total: 2.89 s
Wall time: 2.90 s    # 2.97 s
# 4.6.2: 1.22 s

Left to do

The final reviewer (i.e., Nicolas, I presume) should decide whether we want to have trac11900_category_speedup_combined_Finitesingleton.patch​ or trac11900_category_speedup_combined.patch​.

[nthiery]

Replying to SimonKing:

I have attached two patches. Both of them combine the ideas of Nicolas and myself. The base() method is left in; this shall be taken care of at #11943 (I'll mark it as "todo" there, if it hasn't already been done).

The final reviewer (i.e., Nicolas, I presume) should decide whether we want to have trac11900_category_speedup_combined_Finitesingleton.patch​ or trac11900_category_speedup_combined.patch​.

Since the timing are not decisive in one direction or the other, I vote for trac11900_category_speedup_combined.patch​ which reduces the risks of conflicts with #10963. I have just been through all of it, and it is good enough to go.

Positive review! Thanks for all your hard work!

PS for the release manager: I haven't run myself the tests since alpha3 segfaults on my Ubuntu 11.10 box.

PS for Simon: Just a remark for next time: in a patch which is likely to conflict with other patches lying around on the same topics, please refrain from doing syntactical improvements (like EXAMPLE -> EXAMPLES) in chunks where nothing else is changed otherwise. Also, the workaround for super(Fields).contains in Fields is a code smell. We should instead find a way to make our Cython contains behave properly with inheritance. In a future patch!

[jdemeyer]

I posted a comment at #11943: should I wait until #11943 also gets a positive review in order to merge #9138, #11900 and #11943 together?

[nthiery]

Replying to jdemeyer:

I posted a comment at #11943: should I wait until #11943 also gets a positive review in order to merge #9138, #11900 and #11943 together?

No, please go ahead! I might not get the time to review #11943 instantly, and the earlier #11900 and friends are in, the better!

Thanks :-)

[jdemeyer]

Replying to nthiery:

Replying to jdemeyer:

I posted a comment at #11943: should I wait until #11943 also gets a positive review in order to merge #9138, #11900 and #11943 together?

No, please go ahead! I might not get the time to review #11943 instantly, and the earlier #11900 and friends are in, the better!

Thanks :-)

In any case, I was planning to postpone these tickets to sage-5.0 (which is scheduled to come after sage-4.8). The sage-4.8 release is getting close to being finished and I prefer not to merge the big tickets #9138 and #11900 at this point. They change a lot of core functionality of Sage, so there could be some unexpected consequences.

[nthiery]

Replying to jdemeyer:

In any case, I was planning to postpone these tickets to sage-5.0 (which is scheduled to come after sage-4.8). The sage-4.8 release is getting close to being finished and I prefer not to merge the big tickets #9138 and #11900 at this point. They change a lot of core functionality of Sage, so there could be some unexpected consequences.

Hmm, it would have been really helpful to have a clean base to work on for the bunch of followup patches. That especially since #9138 requires recompiling most of the Sage library, which makes it very inconvenient to handle in a patch queue.

Cheers,

Nicolas

[jdemeyer]

Replying to nthiery:

Hmm, it would have been really helpful to have a clean base to work on for the bunch of followup patches. That especially since #9138 requires recompiling most of the Sage library, which makes it very inconvenient to handle in a patch queue.

Well, you could simply leave #9138 at the bottom of the queue, so you would need to recompile only once. Or truly import the patch (not qimport, but import).

If this is really an obstruction to you, I could easily make available a sage-5.0 pre-prerelease with the few patches related to #9138.

[nthiery]

Replying to jdemeyer:

Well, you could simply leave #9138 at the bottom of the queue, so you would need to recompile only once. Or truly import the patch (not qimport, but import).

I forgot to mention one piece of information: we would need to integrate this in the Sage-Combinat queue, which is used by people of varying technical strength. So most of them use the Sage-Combinat script which is not clever enough to not unapply those patches that haven't changed.

If this is really an obstruction to you, I could easily make available a sage-5.0 pre-prerelease with the few patches related to #9138.

That probably would work. Or just call it an alpha0 to not change the usual workflow. Simon?

[SimonKing]

Replying to nthiery:

Replying to jdemeyer:

If this is really an obstruction to you, I could easily make available a sage-5.0 pre-prerelease with the few patches related to #9138.

That probably would work. Or just call it an alpha0 to not change the usual workflow. Simon?

It doesn't really matter for the project I'm doing for a living: I can always use these "few" patches (namely #9138, #11900, #11115, #11068, #4539, #7797) privately, even if they are not part of the official distribution.

So having it in sage-5.0.alpha0 or .prerelease seems fine to me.

[jdemeyer]

Replying to nthiery:

That probably would work. Or just call it an alpha0 to not change the usual workflow. Simon?

I will go for sage-5.0.prealpha0 (to indicate that it has more of an unofficial status).

[SimonKing]

I am afraid this needs work

sage: None in Rings()

results in a segfault, with the patch. I'll fix it after the status reports of the Sage-Flint days are over.

[SimonKing]

I have updated my patch. It is tested whether the argument is None.

If it is not None, then the argument is tried to be assigned to a cdef'ed variable of type CategoryObject. While it is possible to assign None to it (which is the reason for the segfault), every non-None object that is not of the right type will produce a type error, which is then caught.

In other words, my fix should be correct. I added a test for the fix. Needs review!

[nthiery]

I just had a look at the in Rings() code. Maybe Cython should be complaining when trying to assign None to a variable of a given type. In any cases, testing for None sounds good for the time being. On the other hand, I am now puzzled by the code just below (sorry if I missed it before):

    except TypeError: # this is for objects that aren't CategoryObjects 
        try: 
	    return PyType_IsSubtype(<type>(x.category().parent_class), self._parent_class_of_category) 
 	except AttributeError: 
 	    return False 

If x is not a category object, does it make sense to call x.category()? Shouldn't this just always return False? Otherwise, there should be an example in the doctests illustrating this.

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

I just had a look at the in Rings() code. Maybe Cython should be complaining when trying to assign None to a variable of a given type.

I'm not sure. I think the idea is the same as having a point (in C) point to NULL.

If x is not a category object, does it make sense to call x.category()? Shouldn't this just always return False? Otherwise, there should be an example in the doctests illustrating this.

I guess that is the same problem that hit me in #11521: There are objects that aren't CategoryObject instances. Any integer is an example.

I don't remember if actually doc tests would fail if we simplify the code. But I guess I wrote that for a reason. Well, let's simply try...

[SimonKing]

Indeed, when simply returning False, one gets an error:

sage -t  devel/sage-main/sage/categories/fields.py
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/categories/fields.py", line 87:
    sage: GR in Fields()
Expected:
    True
Got:
    False

Here, GR = gap('Rationals'), equipped with a callable attribute GR.category() that returns Fields().

[zimmerma]

I tried to apply the patch to 4.7.2 but it failed:

sage: hg_sage.import_patch("/tmp/trac11900_category_speedup_combined.patch")
cd "/usr/local/sage-4.7.2/sage/devel/sage" && hg import   "/tmp/trac11900_category_speedup_combined.patch"
applying /tmp/trac11900_category_speedup_combined.patch
patching file sage/categories/algebras.py
Hunk #2 FAILED at 116
Hunk #3 FAILED at 127
2 out of 3 hunks FAILED -- saving rejects to file sage/categories/algebras.py.rej
...
Hunk #1 FAILED at 82
1 out of 2 hunks FAILED -- saving rejects to file sage/structure/category_object.pyx.rej
abort: patch failed to apply

Paul

[SimonKing]

Replying to zimmerma:

I tried to apply the patch to 4.7.2 but it failed:

sage: hg_sage.import_patch("/tmp/trac11900_category_speedup_combined.patch")

Did you also apply all three dependencies?

[zimmerma]

Replying to SimonKing:

Did you also apply all three dependencies?

no, sorry, but since #9562 itself requires to apply other patches, this is too complex for me. I will wait until 4.8 is out, or maybe until 4.8.alpha5 finishes compiling on my Ubuntu 11.10 system.

Paul

[nthiery]

Replying to SimonKing:

Indeed, when simply returning False, one gets an error:

sage -t  devel/sage-main/sage/categories/fields.py
**********************************************************************
File "/home/simon/SAGE/sage-4.8.alpha3/devel/sage-main/sage/categories/fields.py", line 87:
    sage: GR in Fields()
Expected:
    True
Got:
    False

Here, GR = gap('Rationals'), equipped with a callable attribute GR.category() that returns Fields().

Ok. Then please add this as a doctest of "in Rings()" containment, and then you can put a positive review on my behalf.

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

Ok. Then please add this as a doctest of "in Rings()" containment, ...

What do you mean by that? Shall I have a GR.category() be defined, and then test GR in Rings()?

[nthiery]

Replying to SimonKing:

Replying to nthiery:

Ok. Then please add this as a doctest of "in Rings()" containment, ...

What do you mean by that? Shall I have a GR.category() be defined, and then test GR in Rings()?

Ah, I see; I had not noticed that GR was equiped with a category method specifically in that example (which I probably wrote ...). Then, I would add this to the documentation in Rings():

Currently, an object is considered *in* a category as soon as it has a
category method returning an appropriate value::

    sage: class A:
    ....:     def category(self): return Fields()
    ....:         
    sage: 
    sage: A() in Rings()
    True

This feature will most likely be deprecated in favor of having the
class ``A`` derive from :class:`CategoryObject`.

Maybe even is rather than will most likely be.

Cheers,

Nicolas

[jdemeyer]

I get one test failure (including also #9958):

sage -t  -force_lib devel/sage/sage/categories/category_singleton.pyx
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-5.0.prealpha0/devel/sage-main/sage/categories/category_singleton.pyx", line 266:
    sage: hash(Rings()) == hash(Rings)     # indirect doctest
Expected:
    True
Got:
    False
**********************************************************************

[SimonKing]

How can this possibly be? The code of Category_singleton explicitly says that the hash of the unique instance is the same as the hash of the class. I'll try to google whether the hash behaviour has changed between Python 2.6 and 2.7.

[SimonKing]

Is the 5.0 prealpha available somewhere? #9958 looks rather complicated, and I wouldn't like to apply it all by myself.

And google did not tell me whether the hash implementation has significantly changed between 2.6 and 2.7.

[jdemeyer]

Replying to SimonKing:

Is the 5.0 prealpha available somewhere? #9958 looks rather complicated, and I wouldn't like to apply it all by myself.

I am working on it, it should be done by tomorrow.

And google did not tell me whether the hash implementation has significantly changed between 2.6 and 2.7.

The hash for integers certainly changed, see #11986.

[jdemeyer]

I can confirm the problem with category_singleton.pyx is really caused by #9958+#11986.

[SimonKing]

By "something changed with the hash between 2.6 and 2.7", I did not mean that the value of the hash changed. What I meant was: Has the way of calling the provided __hash__ method changed?

In the patch, we turn the hash of a Category_singleton into a lazy class attribute:

    @lazy_class_attribute 
    def __hash__(cls): 
        return ConstantFunction(id(cls)) 

Is there any change between python2.6 and python2.7 that would affect this code?

[SimonKing]

I am now trying a different approach: I introduce a cdef class FastHashable_class. It has a cdef int attribute _hash, and __hash__ simply returns self._hash. I make Category_singleton inherit from this class and from Category. In the __classcall__ method, I assign the value of _hash appropriately.

First tests show that the hash method will be even faster than with the current patch, and since it uses a straight forward __hash__ method (not a lazy class attribute) it is likely to work in Python 2.7.

Preparing a patch now...

[SimonKing]

The following timings are on a different machine than the timings above, but I think they show that the new hash method is pretty good:

sage: timeit("Rings()",number=10000)
10000 loops, best of 3: 981 ns per loop
sage: R = Rings()
sage: timeit("hash(R)",number=10000)
10000 loops, best of 3: 107 ns per loop

The tests at least in sage/categories pass, so, I put it back to "needs review"

Apply trac11900_category_speedup_combined.patch

[SimonKing]

PS:

According to Nicolas' request, I've added some documentation, but in fact I did it into sage/categories/category.py.

[jdemeyer]

Now works with Python 2.7.

[jdemeyer]

Please rebase this to #11319, otherwise the patch applies with fuzz 2.

[SimonKing]

General speedup for the category framework.

[SimonKing]

Done!

[SimonKing]

AFAIU, the current version of the patch is in sage-5.0.prealpha0. I hope this will make it more easy to finish reviewing the patch!

[nthiery]

Replying to SimonKing:

AFAIU, the current version of the patch is in sage-5.0.prealpha0. I hope this will make it more easy to finish reviewing the patch!

I have been through the patch, and it looks good to me. Thanks so much Simon for your hard work on this! It goes far beyond the extra mile.

I am running the tests on my machine. I'll set a positive review when it's done. In case I forget to: if in three hours you have not heard from me, you can set a positive review on my behalf.

Just one note: I hope nobody had a pile of patches on top of the matrix/vector space code, since the many little doc improvements there (like EXAMPLES: -> EXAMPLES::) will force quite some rebasing. Please make this in a separate ticket next time, or just leave it to whoever is working on those files.

Cheers,

Nicolas

[nthiery]

All tests passed on Ubuntu 11.10 (after replacing readline with the latest version from #11970). To be precise:

• sage/schemes/elliptic_curves/lseries_ell.py first timed out, but that probably was because I suspended my laptop in the mean time. The test passed when I launched them individually

• sage/misc/preparser.py failed (see attached log). It did not fail when I relauched it individually.

[nthiery]

For the record: a non reproducible failure in devel/sage/sage/misc/preparser.py

[jdemeyer]

Bad news: this breaks on OS X 10.6. With sage-4.8.alpha5 + #9138 + #11900, sage fails to start up:

bsd:sage-4.8.alpha5 jdemeyer$ ./sage
----------------------------------------------------------------------
| Sage Version 4.8.alpha5, Release Date: 2011-12-20                  |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
**********************************************************************
*                                                                    *
* Warning: this is a prerelease version, and it may be unstable.     *
*                                                                    *
**********************************************************************
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/IPython/ipmaker.pyc in force_import(modname, force_reload)
     61         reload(sys.modules[modname])
     62     else:
---> 63         __import__(modname)
     64
     65

/Users/jdemeyer/sage-4.8.alpha5/local/bin/ipy_profile_sage.py in <module>()
      5     preparser(True)
      6
----> 7     import sage.all_cmdline
      8     sage.all_cmdline._init_cmdline(globals())
      9

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/all_cmdline.py in <module>()
     12 try:
     13
---> 14     from sage.all import *
     15     from sage.calculus.predefined import x
     16     preparser(on=True)

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/all.py in <module>()
     66 from time                import sleep
     67
---> 68 from sage.misc.all       import *         # takes a while
     69
     70 from sage.misc.sh import sh

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/misc/all.py in <module>()
     79 from func_persist import func_persist
     80
---> 81 from functional import (additive_order,
     82                         sqrt as numerical_sqrt,
     83                         arg,

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/misc/functional.py in <module>()
     34
     35
---> 36 from sage.rings.complex_double import CDF
     37 from sage.rings.real_double import RDF, RealDoubleElement
     38

/Users/jdemeyer/sage-4.8.alpha5/local/bin/complex_double.pyx in init sage.rings.complex_double (sage/rings/complex_double.c:15152)()
     90
     91
---> 92
     93
     94

Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/rings/complex_field.pyc in ComplexField(prec, names)
     85         if not C is None:
     86             return C
---> 87     C = ComplexField_class(prec)
     88     cache[prec] = weakref.ref(C)
     89     return C

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/rings/complex_field.pyc in __init__(self, prec)
    185         ParentWithGens.__init__(self, self._real_field(), ('I',), False, category = Fields())
    186 #        self._populate_coercion_lists_()
--> 187         self._populate_coercion_lists_(coerce_list=[complex_number.RRtoCC(self._real_field(), self)])
    188
    189     def __reduce__(self):

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/rings/complex_number.so in sage.rings.complex_number.RRtoCC.__init__ (sage/rings/complex_number.c:14411)()
   2261
   2262
-> 2263
   2264
   2265

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/categories/map.so in sage.categories.map.Map.__init__ (sage/categories/map.c:2234)()
    121
    122
--> 123
    124
    125

Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/categories/homset.pyc in Hom(X, Y, category)
    199     # For the moment, this is the category, for compatibility with the current implementations
    200     # of Homset in rings, schemes, ...
--> 201     H = category.hom_category().parent_class(X, Y, category = category)
    202
    203     ##_cache[key] = weakref.ref(H)

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/categories/homset.pyc in __init__(self, X, Y, category, base, check)
    339             #    raise TypeError, "Y (=%s) must be in category (=%s)"%(Y, category)
    340
--> 341         Parent.__init__(self, base = base, category = category.hom_category())
    342
    343     def _repr_(self):

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__init__ (sage/structure/parent.c:4197)()
    515
    516
--> 517
    518
    519

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/structure/parent.so in sage.structure.parent.Parent._init_category_ (sage/structure/parent.c:4711)()
    564
    565
--> 566
    567
    568

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/structure/dynamic_class.pyc in dynamic_class(name, bases, cls, reduction, doccls)
    254     assert(type(name) is str)
    255     #    assert(cls is None or issubtype(type(cls), type) or type(cls) is classobj)
--> 256     return dynamic_class_internal(name, bases, cls, reduction, doccls)
    257
    258 @cached_function

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/misc/cachefunc.pyc in __call__(self, *args, **kwds)
    176             return self.cache[k]
    177         except KeyError:
--> 178             w = self.f(*args, **kwds)
    179             self.cache[k] = w
    180             return w

/Users/jdemeyer/sage-4.8.alpha5/local/lib/python2.6/site-packages/sage/structure/dynamic_class.pyc in dynamic_class_internal(name, bases, cls, reduction, doccls)
    341         if type(base) is ClasscallMetaclass:
    342             metaclass = DynamicClasscallMetaclass
--> 343     return metaclass(name, bases, methods)
    344
    345 class DynamicMetaclass(type):

TypeError: duplicate base class Sets.HomCategory.parent_class
Error importing ipy_profile_sage - perhaps you should run %upgrade?
WARNING: Loading of ipy_profile_sage failed.

sage:

With only #9138 applied, it works.

[SimonKing]

Strange.

How could the operating system have an influence on whether two parent classes coincide or not?

Since #11943 deals with the consistency of method resolution order of parent classes: Could you try whether the problem disappears when you also apply #11943?

[jdemeyer]

Replying to SimonKing:

Since #11943 deals with the consistency of method resolution order of parent classes: Could you try whether the problem disappears when you also apply #11943?

No, it remains the same.

[SimonKing]

Replying to jdemeyer:

Replying to SimonKing:

Since #11943 deals with the consistency of method resolution order of parent classes: Could you try whether the problem disappears when you also apply #11943?

No, it remains the same.

I don't understand how the operating system could possibly matter here. I hope that someone on sage-devel can grant me with access to some OS X 10.6 computer.

[SimonKing]

It turns out that, for whatever reason, the category of sets is not a unique object on OS X, even though it should be cached as the unique instance of a category singleton.

After starting sage on bsd.math, ignore the error and do

sage: from sage.categories.sets_cat import Sets
sage: S is Sets()
False

Again, I don't see how OS X could be able to break the cache, but it does.

[SimonKing]

Sorry, I meant

sage: Sets() is Sets()
False

[SimonKing]

Aha! That's how an influence of the operating system is possible:

sage: Sets.__classcall__
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)

/scratch/sking/sage-5.0.prealpha1/local/bin/<ipython console> in <module>()

/scratch/sking/sage-5.0.prealpha1/local/lib/python2.7/site-packages/sage/misc/lazy_attribute.pyc in __get__(self, _, cls)
    647             1
    648         """
--> 649         result = self.f(cls)
    650         if result is NotImplemented:
    651             return getattr(super(cls, cls),self.f.__name__)

/scratch/sking/sage-5.0.prealpha1/local/lib/python2.7/site-packages/sage/categories/category_singleton.so in sage.categories.category_singleton.Category_singleton.__classcall__ (sage/categories/category_singleton.c:1453)()

OverflowError: value too large to convert to int

In other words, lazy class attribute does not work on OS X!

Jeroen, you said that sage works on OS X with #9138. Do you mean that all tests pass? Including tests for lazy_class_attribute (I hope there are some tests)?

[SimonKing]

Got it!

CategorySingleton inherits from FastHashableClass, which stores its hash in a cdef attribute. By mistake, I made it cdef int _hash. It should better be cdef Py_ssize_t _hash or so.

[jdemeyer]

Replying to SimonKing:

Jeroen, you said that sage works on OS X with #9138. Do you mean that all tests pass?

I don't think I tested that, just that it started up.

[SimonKing]

Fixed and ready for review! The problem has not been in lazy_class_attribute but in the classcall method of Category_singleton in combination with a too short type used in FastHashable_class.

Apply trac11900_category_speedup_combined.patch trac11900_fix_singleton_hash.patch

[nthiery]

Replying to SimonKing:

Fixed and ready for review! The problem has not been in lazy_class_attribute but in the classcall method of Category_singleton in combination with a too short type used in FastHashable_class.

Apply trac11900_category_speedup_combined.patch trac11900_fix_singleton_hash.patch

Good catch Simon!

Given that this issue was non trivial to pinpoint, do you see a way to add a doctest to FastHashClass?? Say with a small class returning a large hash that would cause the same overflow on OS X?

With that, and assuming that all test pass, I am happy to put back the positive review.

Cheers,

Nicolas

[SimonKing]

Replying to nthiery:

Given that this issue was non trivial to pinpoint, do you see a way to add a doctest to FastHashClass?? Say with a small class returning a large hash that would cause the same overflow on OS X?

FastHashable_class._hash must be explicitly assigned - i.e., one could try to create an example that would crash on machines where the biggest Py_ssize_t does not fit into an int, by explicitly assigning such value. CategorySingleton assigns id(cls) to the attribute _hash of the unique instance of cls - and Sets happens to have an address that doesn't fit into an int.

Cheers, Simon

[SimonKing]

Too bad. In order to create an example, it would be needed to write a little cython example, which cimports FastHashable_class. But in order to do so, it would be needed to add a pxd header file. Is it worth it?

[SimonKing]

Sorry, there *is* a header file. And I think it is OK to include FastHashable_class in the existing header.

[SimonKing]

Fix FastHashable_class._hash

[SimonKing]

I have added a test and updated my patch accordingly. The new test does work on OS X, but the full test suite isn't finished yet.

Apply trac11900_category_speedup_combined.patch trac11900_fix_singleton_hash.patch

[SimonKing]

Hooray, make ptest works on bsd.math, and now I am starting make ptestlong! However, I think the reviewer should run the test suite as well, just to be on the safe side.

[SimonKing]

FWIW, make ptestlong works for me.

[jason]

This new patch fixes the startup problem for me! Hooray! Thanks!

[jdemeyer]

I moved the doctest to a new file sage/tests/cython.pyx. This way, we don't require cython at test-time, only at build time.

[jason]

Sage also starts up with jdemeyer's change, and the sage/tests/cython.pyx file passes (OSX 10.6.8). From Simon's comments, apparently this is only part of the necessary review. Hopefully someone with a faster machine can run testlong.

[jdemeyer]

Replying to jason:

Sage also starts up with jdemeyer's change, and the sage/tests/cython.pyx file passes (OSX 10.6.8). From Simon's comments, apparently this is only part of the necessary review.

Yes, the first big patch trac11900_category_speedup_combined.patch​ already got positive_review.

I can run make ptestlong but don't wait for that to review this patch.

[jason]

If starting up is all that is necessary, then positive review. Simon's explanation also makes sense to me, but I haven't been keeping up on this ticket enough to understand it well enough to check the explanation very deeply.

[jdemeyer]

I'm seeing this error on bsd.math but that's unrelated to this ticket:

sage -t  --long -force_lib devel/sage/sage/schemes/generic/toric_divisor.py
**********************************************************************
File "/Users/jdemeyer/sage-4.8.alpha5/devel/sage-main/sage/schemes/generic/toric_divisor.py", line 1590:
    sage: supp.Vrepresentation()
Expected:
    [A vertex at (-1, 1), A vertex at (0, 2), A vertex at (0, -1), A vertex at (3, -1)]
Got:
    [A vertex at (-1, 1), A vertex at (0, 2), A vertex at (3, -1), A vertex at (0, -1)]
**********************************************************************

[jdemeyer]

Apart from that, everything is fine on bsd.math (sage-4.8.alpha5 + #9138 + #11900).

[SimonKing]

Hi Jeroen,

Is it really a problem to have cython(...) in doctests? I have used cython(...) in the past, for example when testing introspection (namely, cython creates a temporary file, so that introspection is easy).

Aha, is it because some people do not have gcc but install a Sage-binary?

[was]

Replying to SimonKing:

Aha, is it because some people do not have gcc but install a Sage-binary?

Standard (non-optional) tests are allowed to depend on gcc. I don't know if this is written in stone anywhere, but there have been many such standard tests in the past. They aren't a problem for buildbots, since they always have GCC installed.

If nothing else, it is very important to test that calling the compiler from Sage does work.

[jdemeyer]

Replying to was:

Replying to SimonKing:

Aha, is it because some people do not have gcc but install a Sage-binary?

Standard (non-optional) tests are allowed to depend on gcc.

Really? I thought the opposite is true.

I know there are some doctests marked

# optional -- gcc

For example in sage/misc/cython.py

[zimmerma]

thank you very much Simon for your work on this ticket (and on #715). Only a few people have the necessary knowledge to work on speed regressions and memory leaks, but solving such issues is crucial so that Sage is really usable in research.

Paul Zimmermann

[jdemeyer]

Small question: is there are particular reason for writing

self.__dict__.__delitem__('element_class')

instead of

del self.__dict__['element_class']

The latter is faster because it bypasses the lookup of the __delitem__ attribute. I'm changing this in #24270.

[SimonKing]

Replying to jdemeyer:

Small question: is there are particular reason for writing

self.__dict__.__delitem__('element_class')

instead of

del self.__dict__['element_class']

The latter is faster because it bypasses the lookup of the __delitem__ attribute. I'm changing this in #24270.

When I wrote that line, I was ignorant of the difference in performance. Actually I even thought that del self.__dict__['element_class'] was slower, since I expected that the Python interpreter first needs to translate that statement into an attribute lookup that it subsequently has to do anyway.

Meanwhile I know better and wouldn't write it again in that way.

Once again: I HATE THE TRAC WEB INTERFACE!!! While I write these lines, every few seconds the browser window becomes blank and (when I start scrolling and continue writing) reappears in a totally different place. It is a VERY SERIOUS pain in the neck!