#11900 closed defect (fixed)
Serious regression caused by #9138
Reported by: | SimonKing | Owned by: | tbd |
---|---|---|---|
Priority: | critical | Milestone: | sage-5.0 |
Component: | performance | Keywords: | categories regression |
Cc: | jdemeyer, nthiery, malb | Merged in: | sage-5.0.beta0 |
Authors: | Simon King | Reviewers: | Jeroen Demeyer, Nicolas M. Thiéry, Simon King, Jason Grout |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #11319, #9138, #11911, #9562 | Stopgaps: |
Description (last modified by )
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
Attachments (15)
Change History (269)
comment:1 Changed 9 years ago by
- Cc jdemeyer added
- Priority changed from critical to blocker
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
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
comment:4 Changed 9 years ago by
The next problematic call seems to be __get__
of some lazy attribute. But I don't know yet which it is.
comment:5 follow-up: ↓ 6 Changed 9 years ago by
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?
comment:6 in reply to: ↑ 5 Changed 9 years ago by
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 overGF(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.
comment:7 Changed 9 years ago by
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.
comment:8 follow-up: ↓ 9 Changed 9 years ago by
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.
comment:9 in reply to: ↑ 8 Changed 9 years ago by
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
.
comment:10 Changed 9 years ago by
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.
comment:11 Changed 9 years ago by
- Cc nthiery added
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.
comment:12 Changed 9 years ago by
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.
comment:13 Changed 9 years ago by
- Dependencies set to #9138
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.
comment:14 Changed 9 years ago by
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.
comment:15 Changed 9 years ago by
- Status changed from new to needs_review
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".
comment:16 follow-up: ↓ 18 Changed 9 years ago by
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.
comment:17 Changed 9 years ago by
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
comment:18 in reply to: ↑ 16 ; follow-up: ↓ 19 Changed 9 years ago by
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.
comment:19 in reply to: ↑ 18 Changed 9 years ago by
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...
comment:20 Changed 9 years ago by
Indeed, there is some fuzz. I'll take care of that in the next patch version.
comment:21 Changed 9 years ago by
- Status changed from needs_review to needs_work
So far, I did not cache join (only hom_category). That should be done next.
comment:22 Changed 9 years ago by
(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
comment:23 Changed 9 years ago by
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()
comment:24 Changed 9 years ago by
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.
comment:25 Changed 9 years ago by
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.
comment:26 Changed 9 years ago by
- Cc malb added
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...
comment:27 Changed 9 years ago by
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.
comment:28 Changed 9 years ago by
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.
comment:29 follow-up: ↓ 30 Changed 9 years ago by
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.
comment:30 in reply to: ↑ 29 Changed 9 years ago by
comment:31 follow-up: ↓ 32 Changed 9 years ago by
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]
.
comment:32 in reply to: ↑ 31 ; follow-up: ↓ 33 Changed 9 years ago by
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 ofCommutativeAlgebras(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 onF
, butAlgebras(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 thatAlgebras(F).parent_class
is just a pointer toparent_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.
comment:33 in reply to: ↑ 32 ; follow-up: ↓ 34 Changed 9 years ago by
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.
comment:34 in reply to: ↑ 33 ; follow-up: ↓ 36 Changed 9 years ago by
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 theJoinCategory
)? Or the attempt to directly create theJoinCategory
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
orEuclideanDomain
, and it can be commutative or not. So, one can directly write down the result, rather than calling theCategory.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
comment:35 Changed 9 years ago by
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.
comment:36 in reply to: ↑ 34 Changed 9 years ago by
- Work issues set to fiy doctests, fix categories for polynomial rings
Replying to nthiery:
The caching (so that the cache already happens when calling
Category.join(L)
, not only when creating theJoinCategory
)? Or the attempt to directly create theJoinCategory
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
orEuclideanDomain
, and it can be commutative or not. So, one can directly write down the result, rather than calling theCategory.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.
comment:37 follow-up: ↓ 39 Changed 9 years ago by
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.
comment:38 Changed 9 years ago by
- Milestone changed from sage-4.7.2 to sage-4.7.3
- Priority changed from blocker to major
comment:39 in reply to: ↑ 37 Changed 9 years ago by
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()
.
comment:40 follow-up: ↓ 41 Changed 9 years ago by
comment:41 in reply to: ↑ 40 ; follow-up: ↓ 43 Changed 9 years ago by
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/
comment:42 follow-up: ↓ 45 Changed 9 years ago by
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.
comment:43 in reply to: ↑ 41 ; follow-up: ↓ 44 Changed 9 years ago by
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?
comment:44 in reply to: ↑ 43 Changed 9 years ago by
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.
comment:45 in reply to: ↑ 42 ; follow-up: ↓ 46 Changed 9 years ago by
- Work issues changed from fiy doctests, fix categories for polynomial rings to fiy doctests, fix categories for polynomial rings, improve all_super_categories
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.
comment:46 in reply to: ↑ 45 Changed 9 years ago by
Replying to SimonKing:
I still see much time spent in
all_super_categories
. I just found thatself.all_super_categores()
does not start withC.all_super_categories()
for C inself.super_categories()
. That is certainly not very efficient, because it is effectively computingC.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()
.
comment:47 follow-up: ↓ 48 Changed 9 years ago by
- Work issues changed from fiy doctests, fix categories for polynomial rings, improve all_super_categories to fix doctests, fix libsingular pickling
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.
comment:48 in reply to: ↑ 47 Changed 9 years ago by
- Dependencies changed from #9138 to #9138 #11911
comment:49 Changed 9 years ago by
Too bad, the coercion for libsingular seems broken. That will be more work than I thought.
comment:50 follow-up: ↓ 52 Changed 9 years ago by
- Work issues changed from fix doctests, fix libsingular pickling to fix doctests
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.
comment:51 Changed 9 years ago by
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.
comment:52 in reply to: ↑ 50 ; follow-up: ↓ 53 Changed 9 years ago by
Hi Simon,
Replying to SimonKing:
and also it is faster to do
base_ring.is_ring()
ifis_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
comment:53 in reply to: ↑ 52 ; follow-up: ↓ 54 Changed 9 years ago by
Hi Nicolas,
Replying to nthiery:
Replying to SimonKing:
and also it is faster to do
base_ring.is_ring()
ifis_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 testingX 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 beCommutativeRings()
, but with #9138, it isCommutativeAlgebras(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 callsis_subcategory
). #10667 will make it fast, on the long run, but for now it is easier and faster to add a parent methodis_ring
that returns True for rings.Category.join
also involves callingis_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 downJoinCategory
directly.C.is_subcategory(C2)
is too slow, sinceC.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 callingdynamic_class_internal.f
directly, thus, completely avoiding thecached_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.
comment:54 in reply to: ↑ 53 Changed 9 years ago by
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 ofFields()
. It dispatches tosage.rings.fields.is_Field
, which dispatches toP.is_field()
.
I know: I wrote this backward compatibility hack :-)
What I described was the would-be clean plan for the future.
Cheers,
Nicolas
comment:55 Changed 9 years ago by
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.
comment:56 follow-up: ↓ 57 Changed 9 years ago by
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()
.
comment:57 in reply to: ↑ 56 ; follow-up: ↓ 58 Changed 9 years ago by
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).
comment:58 in reply to: ↑ 57 ; follow-up: ↓ 59 Changed 9 years ago by
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.
comment:59 in reply to: ↑ 58 Changed 9 years ago by
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.
comment:60 Changed 9 years ago by
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.
comment:61 Changed 9 years ago by
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.
comment:62 Changed 9 years ago by
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.
Changed 9 years ago by
Improve performance of various category operations. Introduce base() to more categories.
comment:63 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
- Work issues fix doctests deleted
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
comment:64 Changed 9 years ago by
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.
comment:65 Changed 9 years ago by
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)
comment:66 Changed 9 years ago by
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.
comment:67 Changed 9 years ago by
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.
comment:68 follow-up: ↓ 69 Changed 9 years ago by
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.
comment:69 in reply to: ↑ 68 Changed 9 years ago by
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
comment:70 follow-up: ↓ 71 Changed 9 years ago by
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.
comment:71 in reply to: ↑ 70 Changed 9 years ago by
- Description modified (diff)
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
comment:72 follow-up: ↓ 73 Changed 9 years ago by
- Status changed from needs_review to needs_work
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 **********************************************************************
comment:73 in reply to: ↑ 72 Changed 9 years ago by
Replying to jdemeyer:
sage: FiniteEnumeratedSets?()(GF(3))
Exception raised:
Yep. As I said, the last patch wasn't tested, yet.
comment:74 Changed 9 years ago by
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.
comment:75 Changed 9 years ago by
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.
comment:76 follow-up: ↓ 81 Changed 9 years ago by
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 aFiniteField
and as aQuotientRing
. With my patch, for saving time, it is just initialised as aParent
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.
comment:77 Changed 9 years ago by
- Status changed from needs_work to needs_review
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.
comment:78 follow-up: ↓ 79 Changed 9 years ago by
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).
comment:79 in reply to: ↑ 78 ; follow-up: ↓ 80 Changed 9 years ago by
comment:80 in reply to: ↑ 79 Changed 9 years ago by
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.
comment:81 in reply to: ↑ 76 Changed 9 years ago by
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
comment:82 Changed 9 years ago by
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?
comment:83 Changed 9 years ago by
Passes make ptestlong
on sage.math.washington.edu.
comment:84 follow-up: ↓ 85 Changed 9 years ago by
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.
comment:85 in reply to: ↑ 84 Changed 9 years ago by
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
comment:86 Changed 9 years ago by
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.
comment:87 Changed 9 years ago by
comment:88 Changed 9 years ago by
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.
comment:89 Changed 9 years ago by
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:
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.
comment:90 Changed 9 years ago by
- Priority changed from major to critical
- Reviewers set to Jeroen Demeyer
I hope you can find a reviewer to look at the code, I sent a message to sage-devel.
comment:91 Changed 9 years ago by
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.
comment:93 follow-up: ↓ 94 Changed 9 years ago by
- Milestone set to sage-4.8
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?
comment:94 in reply to: ↑ 93 ; follow-up: ↓ 95 Changed 9 years ago by
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
comment:95 in reply to: ↑ 94 Changed 9 years ago by
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.
comment:96 follow-up: ↓ 97 Changed 9 years ago by
- Status changed from needs_review to needs_work
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
comment:97 in reply to: ↑ 96 Changed 9 years ago by
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.
comment:98 follow-up: ↓ 99 Changed 9 years ago by
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.
Changed 9 years ago by
An experimental implementation of optimized base class for singleton categories
comment:99 in reply to: ↑ 98 ; follow-up: ↓ 101 Changed 9 years ago by
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 cythoniseis_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
comment:100 follow-up: ↓ 105 Changed 9 years ago by
@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)"?
comment:101 in reply to: ↑ 99 Changed 9 years ago by
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...
comment:102 follow-up: ↓ 103 Changed 9 years ago by
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.
comment:103 in reply to: ↑ 102 ; follow-up: ↓ 106 Changed 9 years ago by
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.
comment:104 Changed 9 years ago by
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!
comment:105 in reply to: ↑ 100 Changed 9 years ago by
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.
comment:106 in reply to: ↑ 103 Changed 9 years ago by
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?.
comment:107 Changed 9 years ago by
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.
comment:108 Changed 9 years ago by
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
comment:109 Changed 9 years ago by
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
comment:110 follow-up: ↓ 111 Changed 9 years ago by
I have attached a new patch, which is your patch but with the modifications I explained above.
comment:111 in reply to: ↑ 110 ; follow-up: ↓ 112 Changed 9 years ago by
- Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Nicolas M. Thiéry
- Work issues set to finalize the patch with the different ideas that have been explored
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
comment:112 in reply to: ↑ 111 Changed 9 years ago by
- Description modified (diff)
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
comment:113 follow-up: ↓ 115 Changed 9 years ago by
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?
comment:114 Changed 9 years ago by
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.
comment:115 in reply to: ↑ 113 Changed 9 years ago by
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
, asP 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
comment:116 Changed 9 years ago by
- Work issues changed from finalize the patch with the different ideas that have been explored to Laurent series rings are fields. Add docs. Don't use is_ring and friends
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.
comment:117 Changed 9 years ago by
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__
. SinceQ 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__
forFields()
, thenQ in Fields()
involves callingQ.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
comment:118 Changed 9 years ago by
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:
- We could remove the custom
__contains__
method and restrict ourselves to fixing the case ofPolynomialQuotientRing
in the way I indicated. After all, this is the only case of failing doctests. - We could remove the custom
__contains__
method and the category stuff for all parents with anis_field()
method. - We could preserve the custom
__contains__
method ofFields()
, but ensure that the potentially time-consuming additional tests are cached. Instead of caching allis_field()
methods (there are quite many), I suggest to use a cache on the functionsage.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.
comment:119 Changed 9 years ago by
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
.
comment:120 Changed 9 years ago by
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?
comment:121 follow-up: ↓ 122 Changed 9 years ago by
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.
comment:122 in reply to: ↑ 121 ; follow-up: ↓ 123 Changed 9 years ago by
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 ringsIn 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, sinceDeBruijnSequences
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
comment:123 in reply to: ↑ 122 Changed 9 years ago by
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
comment:124 Changed 9 years ago by
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...
comment:125 follow-up: ↓ 126 Changed 9 years ago by
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.
comment:126 in reply to: ↑ 125 ; follow-up: ↓ 127 Changed 9 years ago by
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.
comment:127 in reply to: ↑ 126 ; follow-up: ↓ 128 Changed 9 years ago by
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.
comment:128 in reply to: ↑ 127 ; follow-up: ↓ 129 Changed 9 years ago by
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).
comment:129 in reply to: ↑ 128 Changed 9 years ago by
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 usingCategory_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
comment:130 Changed 9 years ago by
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.
comment:131 Changed 9 years ago by
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.
comment:132 Changed 9 years ago by
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.
comment:133 Changed 9 years ago by
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).
comment:134 Changed 9 years ago by
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.
Changed 9 years ago by
Implement Category_singleton
, cythonise ConstantFunction
, and use both for most categories. Use categories for polynomial quotient rings
comment:135 Changed 9 years ago by
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.
comment:136 Changed 9 years ago by
- Description modified (diff)
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
comment:137 Changed 9 years ago by
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.. :(
comment:138 Changed 9 years ago by
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...
comment:139 Changed 9 years ago by
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.
comment:140 Changed 9 years ago by
- Work issues changed from Laurent series rings are fields. Add docs. Don't use is_ring and friends to Laurent series rings are fields. CFF is a field.
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.
comment:141 Changed 9 years ago by
The follow-up ticket will be #12071.
comment:142 follow-up: ↓ 143 Changed 9 years ago by
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.
comment:143 in reply to: ↑ 142 ; follow-ups: ↓ 144 ↓ 145 Changed 9 years ago by
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 deletedconstant_function.py
.
I didn't. Mercurial did. In fact I had hg add
ed 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?
comment:144 in reply to: ↑ 143 Changed 9 years ago by
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 deletedconstant_function.py
.I didn't. Mercurial did. In fact I had
hg add
ed 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.
comment:145 in reply to: ↑ 143 ; follow-up: ↓ 146 Changed 9 years ago by
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
comment:146 in reply to: ↑ 145 Changed 9 years ago by
comment:147 follow-up: ↓ 148 Changed 9 years ago by
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.
comment:148 in reply to: ↑ 147 ; follow-ups: ↓ 149 ↓ 154 Changed 9 years ago by
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 theHom
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.
comment:149 in reply to: ↑ 148 ; follow-up: ↓ 150 Changed 9 years ago by
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?
comment:150 in reply to: ↑ 149 ; follow-up: ↓ 151 Changed 9 years ago by
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?
comment:151 in reply to: ↑ 150 Changed 9 years ago by
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.
comment:152 follow-up: ↓ 153 Changed 9 years ago by
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.
comment:153 in reply to: ↑ 152 Changed 9 years ago by
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.
comment:154 in reply to: ↑ 148 Changed 9 years ago by
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.
comment:155 Changed 9 years ago by
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.
comment:156 follow-up: ↓ 161 Changed 9 years ago by
- Status changed from needs_work to needs_review
- Work issues Laurent series rings are fields. CFF is a field. deleted
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
comment:157 follow-up: ↓ 158 Changed 9 years ago by
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
comment:158 in reply to: ↑ 157 Changed 9 years ago by
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!
comment:159 follow-up: ↓ 160 Changed 9 years ago by
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
comment:160 in reply to: ↑ 159 Changed 9 years ago by
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
comment:161 in reply to: ↑ 156 ; follow-up: ↓ 162 Changed 9 years ago by
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
comment:162 in reply to: ↑ 161 Changed 9 years ago by
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.
comment:163 Changed 9 years ago by
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
comment:164 follow-up: ↓ 165 Changed 9 years ago by
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
comment:165 in reply to: ↑ 164 Changed 9 years ago by
Replying to SimonKing:
Do I understand correctly that you plan to do these things in your final reviewer patch?
Indeed!
comment:166 Changed 9 years ago by
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?
Changed 9 years ago by
comment:167 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to Segmentation faults
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...
comment:168 Changed 9 years ago by
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).
comment:169 Changed 9 years ago by
No, it wasn't the blocker, it is the M4RIE ticket #9562.
Changed 9 years ago by
Test failures with 4.8 alpha2 with the combined patch (but not my reviewer's patch) and dependency
comment:170 Changed 9 years ago by
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
comment:171 Changed 9 years ago by
- Status changed from needs_work to needs_review
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.
comment:172 follow-up: ↓ 173 Changed 9 years ago by
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([])
comment:173 in reply to: ↑ 172 Changed 9 years ago by
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.
comment:174 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues changed from Segmentation faults to Doctest errors, rebase rel #9562
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.
comment:175 follow-up: ↓ 179 Changed 9 years ago by
- Work issues changed from Doctest errors, rebase rel #9562 to Rebase first patch rel #9562; update reviewer patch
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
comment:176 Changed 9 years ago by
- Dependencies changed from #9138 #11911 to #9138 #11911 #10595 #9562
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.
comment:177 Changed 9 years ago by
- Dependencies changed from #9138 #11911 #10595 #9562 to #9138 #11911 #9562
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.
comment:178 Changed 9 years ago by
- Work issues changed from Rebase first patch rel #9562; update reviewer patch to Update reviewer patch
I have updated my patch, rebased against the M4RIE ticket.
comment:179 in reply to: ↑ 175 ; follow-up: ↓ 180 Changed 9 years ago by
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
comment:180 in reply to: ↑ 179 ; follow-up: ↓ 181 Changed 9 years ago by
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
comment:181 in reply to: ↑ 180 Changed 9 years ago by
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.
comment:182 follow-up: ↓ 183 Changed 9 years ago by
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
comment:183 in reply to: ↑ 182 ; follow-up: ↓ 184 Changed 9 years ago by
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
comment:184 in reply to: ↑ 183 ; follow-up: ↓ 185 Changed 9 years ago by
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.
comment:185 in reply to: ↑ 184 Changed 9 years ago by
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!
Changed 9 years ago by
General speedup for the category framework, using Category_singleton for Finite*
comment:186 follow-up: ↓ 187 Changed 9 years ago by
- Description modified (diff)
- Reviewers changed from Jeroen Demeyer, Nicolas M. Thiéry to Jeroen Demeyer, Nicolas M. Thiéry, Simon King
- Status changed from needs_work to needs_review
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.
comment:187 in reply to: ↑ 186 Changed 9 years ago by
- Status changed from needs_review to positive_review
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!
comment:188 follow-up: ↓ 189 Changed 9 years ago by
- Description modified (diff)
comment:189 in reply to: ↑ 188 ; follow-up: ↓ 190 Changed 9 years ago by
comment:190 in reply to: ↑ 189 ; follow-up: ↓ 191 Changed 9 years ago by
- Milestone changed from sage-4.8 to sage-5.0
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.
comment:191 in reply to: ↑ 190 ; follow-up: ↓ 192 Changed 9 years ago by
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
comment:192 in reply to: ↑ 191 ; follow-up: ↓ 193 Changed 9 years ago by
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.
comment:193 in reply to: ↑ 192 ; follow-ups: ↓ 194 ↓ 195 Changed 9 years ago by
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?
comment:194 in reply to: ↑ 193 Changed 9 years ago by
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.
comment:195 in reply to: ↑ 193 Changed 9 years ago by
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).
comment:196 Changed 9 years ago by
- Status changed from positive_review to needs_work
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.
comment:197 Changed 9 years ago by
- Status changed from needs_work to needs_review
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!
comment:198 follow-up: ↓ 199 Changed 9 years ago by
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
comment:199 in reply to: ↑ 198 Changed 9 years ago by
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...
comment:200 follow-up: ↓ 204 Changed 9 years ago by
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()
.
comment:201 follow-up: ↓ 202 Changed 9 years ago by
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
comment:202 in reply to: ↑ 201 ; follow-up: ↓ 203 Changed 9 years ago by
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?
comment:203 in reply to: ↑ 202 Changed 9 years ago by
comment:204 in reply to: ↑ 200 ; follow-up: ↓ 205 Changed 9 years ago by
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: FalseHere,
GR = gap('Rationals')
, equipped with a callable attributeGR.category()
that returnsFields()
.
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
comment:205 in reply to: ↑ 204 ; follow-up: ↓ 206 Changed 9 years ago by
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()
?
comment:206 in reply to: ↑ 205 Changed 9 years ago by
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 testGR 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
comment:207 Changed 9 years ago by
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 **********************************************************************
comment:208 Changed 9 years ago by
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.
comment:209 follow-up: ↓ 210 Changed 9 years ago by
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.
comment:210 in reply to: ↑ 209 Changed 9 years ago by
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.
comment:211 Changed 9 years ago by
comment:212 Changed 9 years ago by
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?
comment:213 Changed 9 years ago by
- Status changed from needs_review to needs_work
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...
comment:214 Changed 9 years ago by
- Status changed from needs_work to needs_review
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
comment:215 Changed 9 years ago by
PS:
According to Nicolas' request, I've added some documentation, but in fact I did it into sage/categories/category.py.
comment:216 Changed 9 years ago by
Now works with Python 2.7.
comment:217 Changed 9 years ago by
- Dependencies changed from #9138 #11911 #9562 to #11319, #9138, #11911, #9562
- Status changed from needs_review to needs_work
Please rebase this to #11319, otherwise the patch applies with fuzz 2.
comment:218 Changed 9 years ago by
- Status changed from needs_work to needs_review
- Work issues Update reviewer patch deleted
Done!
comment:219 follow-up: ↓ 220 Changed 9 years ago by
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!
comment:220 in reply to: ↑ 219 Changed 9 years ago by
- Status changed from needs_review to positive_review
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
comment:221 Changed 9 years ago by
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.
Changed 9 years ago by
For the record: a non reproducible failure in devel/sage/sage/misc/preparser.py
comment:222 Changed 9 years ago by
- Status changed from positive_review to needs_work
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.
comment:223 follow-up: ↓ 224 Changed 9 years ago by
comment:224 in reply to: ↑ 223 ; follow-up: ↓ 225 Changed 9 years ago by
comment:225 in reply to: ↑ 224 Changed 9 years ago by
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.
comment:226 Changed 9 years ago by
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.
comment:227 Changed 9 years ago by
Sorry, I meant
sage: Sets() is Sets() False
comment:228 follow-up: ↓ 230 Changed 9 years ago by
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)?
comment:229 Changed 9 years ago by
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.
comment:230 in reply to: ↑ 228 Changed 9 years ago by
comment:231 follow-up: ↓ 233 Changed 9 years ago by
- Description modified (diff)
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
comment:232 Changed 9 years ago by
- Status changed from needs_work to needs_review
comment:233 in reply to: ↑ 231 ; follow-up: ↓ 234 Changed 9 years ago by
Replying to SimonKing:
Fixed and ready for review! The problem has not been in
lazy_class_attribute
but in the classcall method ofCategory_singleton
in combination with a too short type used inFastHashable_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
comment:234 in reply to: ↑ 233 Changed 9 years ago by
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
comment:235 Changed 9 years ago by
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?
comment:236 Changed 9 years ago by
Sorry, there *is* a header file. And I think it is OK to include FastHashable_class
in the existing header.
comment:237 Changed 9 years ago by
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
comment:238 Changed 9 years ago by
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.
comment:239 Changed 9 years ago by
FWIW, make ptestlong
works for me.
comment:240 Changed 9 years ago by
This new patch fixes the startup problem for me! Hooray! Thanks!
Changed 9 years ago by
Changed 9 years ago by
comment:241 Changed 9 years ago by
- Description modified (diff)
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.
comment:242 follow-up: ↓ 243 Changed 9 years ago by
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.
comment:243 in reply to: ↑ 242 Changed 9 years ago by
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.
comment:244 Changed 9 years ago by
- Status changed from needs_review to positive_review
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.
comment:245 Changed 9 years ago by
- Reviewers changed from Jeroen Demeyer, Nicolas M. Thiéry, Simon King to Jeroen Demeyer, Nicolas M. Thiéry, Simon King, Jason Grout
comment:246 Changed 9 years ago by
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)] **********************************************************************
comment:247 Changed 9 years ago by
comment:248 follow-up: ↓ 249 Changed 9 years ago by
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?
comment:249 in reply to: ↑ 248 ; follow-up: ↓ 250 Changed 9 years ago by
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.
comment:250 in reply to: ↑ 249 Changed 9 years ago by
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
comment:251 Changed 9 years ago by
- Merged in set to sage-5.0.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:252 Changed 9 years ago by
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
comment:253 follow-up: ↓ 254 Changed 3 years ago by
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.
comment:254 in reply to: ↑ 253 Changed 3 years ago by
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!
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?