Opened 10 years ago
Closed 9 years ago
#9138 closed defect (fixed)
Categories for all rings
Reported by: | jbandlow | Owned by: | nthiery |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | categories | Keywords: | introspection, categories for rings |
Cc: | sage-combinat, robertwb | Merged in: | sage-5.0.beta0 |
Authors: | Simon King | Reviewers: | Volker Braun |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | To be merged with #11900 | Stopgaps: |
Description (last modified by )
Introspection is failing on polynomial rings:
sage: R.<x> = QQ[] sage: R.su<tab> R.sum R.summation R.summation_from_element_class_add sage: R.sum? Object `R.sum` not found. sage: R.sum() --------------------------------------------------------------------------- AttributeError Traceback (most recent call last)
This is because polynomial rings do not yet set their category properly:
sage: QQ[x]._test_category() ------------------------------------------------------------ Traceback (most recent call last): ... AssertionError: category of self improperly initialized
See http://groups.google.com/group/sage-devel/browse_thread/thread/4780192a11a8b591 for more discussion.
Many other rings are not properly initialised as well. The aim of this ticket is to change that.
Apply 9138_flat.patch (rebased on top of #9958, but will still apply with fuzz 2 otherwise).
See #11900 for a follow-up fixing some speed regressions.
Attachments (5)
Change History (131)
comment:1 Changed 10 years ago by
- Cc sage-combinat added
- Description modified (diff)
- Keywords categories added
- Summary changed from Introspection is failing on polynomial rings to Categories for polynomial rings
comment:2 follow-up: ↓ 3 Changed 10 years ago by
comment:3 in reply to: ↑ 2 Changed 10 years ago by
Replying to mmezzarobba:
This ticket seems to be a duplicate of #8613.
Indeed. This should have ringed a bell to me!
Since I have already recycled this ticket to "Categories for polynomial ring", I leave the two tickets as is. Once this ticket will be closed, it should be possible to close #8613 as well.
comment:4 follow-up: ↓ 5 Changed 10 years ago by
This ticket is just about a single kind of parent classes. Rather than going through a long list of parent classes one by one and inserting the missing pieces: Wouldn't it be a more thorough approach to provide a default implementation for the attributes needed in the category framework, in cases where it makes sense?
Here is an example:
sage: R.<x,y> = QQ[] sage: 'element_class' in dir(R) True sage: hasattr(R,'element_class') False
If I am not mistaken, "element_class" should be implemented by providing the attribute "Element".
But is there a reason why element_class is a dynamic meta-class and not a regular method? Since any parent class has a "an_element" method, it seems to me that the following default implementation makes sense (and it solves the problem in my example above):
def element_class(self): try: return self.Element except AttributeError: return self.an_element().__class__
It seems to me that providing reasonable default implementations would, on the long run, be easier than going through any single parent class. But certainly other people know more about the "how-to" of categories.
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 10 years ago by
Replying to SimonKing:
But is there a reason why element_class is a dynamic meta-class and not a regular method?
Sorry, I just noticed that "element_class" is not a method at all: I assumed that it should be used like R.element_class()
, but sadly it is R.element_class
without calling the attribute. So, one attribute (element_class) is implemented by providing another attribute (Element).
Anyway, if there shall be a default implementation for element_class then unfortunately it must be in __getattr__
.
comment:6 in reply to: ↑ 5 Changed 10 years ago by
Replying to SimonKing:
Replying to SimonKing:
But is there a reason why element_class is a dynamic meta-class and not a regular method?
Sorry, I just noticed that "element_class" is not a method at all...
Again wrong. I found in sage.structure.parent that there is indeed a method element_class -- with a lazy_attribute decorator. I am still confused by that programming style, so, better I shut up.
Anyway, changing the element_class method so that an_element is used (rather than raising an AttributeError
) did not help. Can you explain why this does not work?
comment:7 Changed 10 years ago by
Question: Is it OK to broaden the scope of this ticket, namely to use the category framework for everything that comes from sage/rings/ring.pyx? Or shall it be restricted to polynomial rings.
comment:8 follow-up: ↓ 9 Changed 10 years ago by
- Status changed from new to needs_review
Since #9944 almost has a positive review but does not entirely fix the bug reported here, I'm posting my patch here, building on top of that.
Examples:
With the patches from #9944:
sage: QQ['x'].category() # why not additionally an algebra? Category of euclidean domains sage: QQ['x','y'].category() # why not an algebra? Category of commutative rings sage: SteenrodAlgebra(2)['x'].category() # this is wrong Category of commutative rings sage: QQ['x','y'].sum([1,1]) Traceback (most recent call last): ... AttributeError: 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular' object has no attribute 'sum'
Adding my (not yet submitted) patch, I get:
sage: QQ['x'].category() Join of Category of euclidean domains and Category of commutative algebras over Rational Field sage: QQ['x','y'].category() Category of commutative algebras over Rational Field sage: SteenrodAlgebra(2)['x'].category() Category of algebras over mod 2 Steenrod algebra sage: QQ['x','y'].sum([1,1]) 2
So, I think the bug reported here is fixed. For me, all doctests pass.
Depends on #9944
comment:9 in reply to: ↑ 8 Changed 10 years ago by
Replying to SimonKing:
Adding my (not yet submitted) patch, ...
Oops, I meant: That's with the patch that I have submitted...
comment:10 follow-up: ↓ 11 Changed 10 years ago by
- Status changed from needs_review to needs_info
Hi Simon,
I haven't been following all the details of this, but thanks for the patch! One question I have is whether there is a performance penalty for this, and if so, to what degree is that acceptable. On my machine, I noticed about a 10% slow-down for
sage: R.<x> = QQ['x'] sage: timeit('f = x^2 + 1')
after applying the patches at #9944 and here. I did not do any rigorous testing so this may be spurious, but I'm not sure this should be given a positive review unless this issue has at least been considered.
If this has already happened and I missed the discussion, then I apologize. Just point me to it and I'll shut up and go away. :)
comment:11 in reply to: ↑ 10 Changed 10 years ago by
Hi Jason,
Replying to jbandlow:
I did not do any rigorous testing so this may be spurious, but I'm not sure this should be given a positive review unless this issue has at least been considered.
You are right, things like this should be considered. However, I wonder where a slow-down might come from.
If this has already happened and I missed the discussion, then I apologize. Just point me to it and I'll shut up and go away. :)
No, I wasn't testing the performance. Aparently I work in cycles: Recently I had several patches that considerably increased performance, and perhaps I am now in a slow mood again...
Anyway, I'll do some tests now.
comment:12 Changed 10 years ago by
Here are the test results:
Without all patches:
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 22.5 Âµs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 24.5 Âµs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 87.7 Âµs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 114 Âµs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 21.9 Âµs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 40 Âµs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 26.3 Âµs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 239 Âµs per loop
With the patches from #9944:
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 25.6 Âµs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 26.7 Âµs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 109 Âµs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 121 Âµs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 31.4 Âµs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 40 Âµs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 26.8 Âµs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 250 Âµs per loop
With the patches from #9944 and the patch from here:
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 25.7 Âµs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 28.3 Âµs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 115 Âµs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 125 Âµs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 31 Âµs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 17.5 Âµs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 25.1 Âµs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 256 Âµs per loop
Note, however, that the numbers arent't very stable
sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 20.9 Âµs per loop sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 20.8 Âµs per loop sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 22.6 Âµs per loop sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 37.9 Âµs per loop sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 15.4 Âµs per loop
But there is a tendency: Things tend to be slower, both with #9944 and with my patch.
So, it should be worth while to analyse the arithmetic with prun.
comment:13 Changed 10 years ago by
By the way, I think we should add doctests of the type
sage: TestSuite(QQ['x']).run() sage: TestSuite(QQ['x','y']).run() sage: TestSuite(QQ['x','y']['t']).run() sage: TestSuite(GF(3)['t']).run() sage: TestSuite(ZZ['t']).run()
If I understand the ticket description, this used to fail.
comment:14 Changed 10 years ago by
Idea: Could it be that the length of the method resolution order is responsible for the slow-down?
With all patches:
sage: len(type(QQ['x']).mro()) 47 sage: len(type(QQ['x','y']).mro()) 11 sage: len(type(GF(3)['x','y']).mro()) 11 sage: len(type(GF(3)['x']).mro()) 49 sage: len(type(ZZ['x']).mro()) 41 sage: len(type(ZZ['x']['t']).mro()) 41 sage: len(type(QQ['x'].gen()).mro()) 9 sage: len(type(QQ['x','y'].gen()).mro()) 8 sage: len(type(GF(3)['x','y'].gen()).mro()) 8 sage: len(type(GF(3)['x'].gen()).mro()) 10 sage: len(type(ZZ['x'].gen()).mro()) 9 sage: len(type(ZZ['x']['t'].gen()).mro()) 9
With only the patches from #9944:
sage: len(type(QQ['x']).mro()) 39 sage: len(type(QQ['x','y']).mro()) 11 sage: len(type(GF(3)['x','y']).mro()) 11 sage: len(type(GF(3)['x']).mro()) 41 sage: len(type(ZZ['x']).mro()) 34 sage: len(type(ZZ['x']['t']).mro()) 34 sage: len(type(QQ['x'].gen()).mro()) 9 sage: len(type(QQ['x','y'].gen()).mro()) 8 sage: len(type(GF(3)['x','y'].gen()).mro()) 8 sage: len(type(GF(3)['x'].gen()).mro()) 10 sage: len(type(ZZ['x'].gen()).mro()) 9 sage: len(type(ZZ['x']['t'].gen()).mro()) 9
Without these patches:
sage: len(type(QQ['x']).mro()) 18 sage: len(type(QQ['x','y']).mro()) 11 sage: len(type(GF(3)['x','y']).mro()) 11 sage: len(type(GF(3)['x']).mro()) 20 sage: len(type(ZZ['x']).mro()) 15 sage: len(type(ZZ['x']['t']).mro()) 15 sage: len(type(QQ['x'].gen()).mro()) 9 sage: len(type(QQ['x','y'].gen()).mro()) 8 sage: len(type(GF(3)['x','y'].gen()).mro()) 8 sage: len(type(GF(3)['x'].gen()).mro()) 10 sage: len(type(ZZ['x'].gen()).mro()) 9 sage: len(type(ZZ['x']['t'].gen()).mro()) 9
So, the mro of the rings becomes much longer. Could it be that, as a consequence, it takes longer to find common and frequently used methods such as R.parent()
and R.base_ring()
?
comment:15 Changed 10 years ago by
Here are times for basic methods (i.e., methods that require to walk up much of the mro):
Without patches
sage: R.<x> = ZZ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 253 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 447 ns per loop sage: R.<x> = QQ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 249 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 508 ns per loop sage: R.<x> = GF(3)[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 262 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 555 ns per loop sage: R.<x> = QQ['t'][] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 249 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 446 ns per loop sage: R.<x,y> = ZZ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 240 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 286 ns per loop sage: R.<x,y> = QQ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 240 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 282 ns per loop sage: R.<x,y> = GF(3)[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 245 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 284 ns per loop sage: R.<x,y> = QQ['t'][] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 266 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 413 ns per loop
With all patches
sage: R.<x> = ZZ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 539 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 476 ns per loop sage: R.<x> = QQ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 247 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 652 ns per loop sage: R.<x> = GF(3)[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 670 ns per loop sage: timeit('R.base_ring()',number=10^5) sage: R.<x> = QQ['t'][] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 254 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 496 ns per loop sage: R.<x,y> = ZZ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 583 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 297 ns per loop sage: R.<x,y> = QQ[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 237 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 307 ns per loop sage: R.<x,y> = GF(3)[] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 237 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 294 ns per loop sage: R.<x,y> = QQ['t'][] sage: timeit('x.parent()',number=10^5) 100000 loops, best of 3: 277 ns per loop sage: timeit('R.base_ring()',number=10^5) 100000 loops, best of 3: 477 ns per loop
So, there seems to be some slow-down in accessing basic methods.
comment:16 Changed 10 years ago by
But apparently one can work around the mro:
sage: timeit('R.base_ring()',number=10^6) 1000000 loops, best of 3: 470 ns per loop sage: timeit('Parent.base_ring(R)',number=10^6) 1000000 loops, best of 3: 352 ns per loop
So, if speed matters, it might be worth while to use the idiom above to speed things up. I'll ask on sage-devel whether there is a more elegant/pythonic way to cope with a long mro.
comment:17 Changed 10 years ago by
I had to rebase my patch since it
Depends on #9944
comment:18 Changed 10 years ago by
- Status changed from needs_info to needs_review
With the latest patches, I obtain the following timings:
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 25.8 µs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 27.8 µs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 112 µs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 124 µs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 12.7 µs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 15.7 µs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 10.3 µs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 148 µs per loop
Without these patches:
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 22.7 µs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 24.2 µs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 87 µs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 113 µs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 13 µs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 16.3 µs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 10.5 µs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 237 µs per loop
In other words, there is a mild deceleration in the univariate case and a mild (and in one case considerable) acceleration in the multivariate case.
I don't understand why. But perhaps a reviewer has an idea, and can also state his or her opinion how bad the deceleration is compared with the acceleration?
comment:19 Changed 10 years ago by
The patch is rebased again.
Note that meanwhile #9944 does not mean a slow down but a speed up! The patch from here, unfortunately, makes things slightly slower, again. But compared with unpatched Sage, it is not significantly slower in any case, but still much faster in some cases (and in two cases even faster than with #9944 alone).
Here are the latest timings.
Unpatched:
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 23.4 µs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 24.6 µs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 87.9 µs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 113 µs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 13 µs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 16.6 µs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 10.8 µs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 238 µs per loop sage: R.<x,y> = Qp(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 511 µs per loop sage: R.<x> = Qp(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 1.06 ms per loop
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 8.95 µs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 8.33 µs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 76.7 µs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 82.7 µs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 13.2 µs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 16.4 µs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 11 µs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 106 µs per loop sage: R.<x,y> = Qp(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 421 µs per loop sage: R.<x> = Qp(3)[] sage: timeit('(2*x-1)^2+5', number=10^4) 10000 loops, best of 3: 1.1 ms per loop
So, I hope it can be reviewed.
For the patch bot:
Depends on #9944
comment:20 follow-up: ↓ 22 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to Fix conversion maps that return None
Not good. Many doctests fail. First analysis: When I implemented the improved base ring conversion for polynomial rings, I noticed that _lmul_
for p-adics returns None (quite a bug). I thought that I had worked around that bug, as the doc tests pass with the patches from #9944.
But apparently it hit me here...
comment:21 Changed 10 years ago by
- Description modified (diff)
- Keywords for rings added
- Status changed from needs_work to needs_review
- Work issues Fix conversion maps that return None deleted
I think now we are ready for review.
Long tests passed for me.
By the way, the long tests made me fix another bug. Namely, in the __setstate__
method of CategoryObject
, the existing category was overridden by the value found in the pickle. If you do so for the ration field, than afterwards its category is not the category of quotient fields but of rings. Result: The pickle jar broke.
Solution: If the category in the pickle is None, then self._category
will be preserved. Otherwise, it will be the join of self._category
(if not None) with the category found in the pickle.
I don't know whether you agree with the second part of that solution. But I think the first part should be clear.
Also, I added some TestSuite
tests for various flavours of polynomial rings.
For the patch bot:
Depends on #9944
comment:22 in reply to: ↑ 20 ; follow-up: ↓ 23 Changed 10 years ago by
Replying to SimonKing:
Not good. Many doctests fail. First analysis: When I implemented the improved base ring conversion for polynomial rings, I noticed that
_lmul_
for p-adics returns None (quite a bug).
For the record: this *might* be intentional. The coercion protocle does specify that the arithmetic operation may return None under certain circumstances to state that, after all, they can't handle that operation, and some other approach should be tried.
Cheers,
Nicolas
comment:23 in reply to: ↑ 22 Changed 10 years ago by
Replying to nthiery:
Replying to SimonKing:
Not good. Many doctests fail. First analysis: When I implemented the improved base ring conversion for polynomial rings, I noticed that
_lmul_
for p-adics returns None (quite a bug).For the record: this *might* be intentional.
OK, but really just for the record -- because I did not change it. Instead, I test what _lmul_
does, and if it returns None then it will not be used in the base ring conversion.
comment:24 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to Doctest errors
Sorry, apparently I had not applied the patch when I was running the long doc tests. There were a couple of errors. So, needs work...
comment:25 Changed 10 years ago by
- Status changed from needs_work to needs_review
I think I just fixed it, and it can be reviewed.
Depends on #9944
comment:26 Changed 10 years ago by
FWIW, long tests pass for me.
comment:27 Changed 10 years ago by
But there is one point that I don't like:
With the patches from #9944), I get
sage -t "devel/sage-main/sage/schemes/elliptic_curves/sha_tate.py" [26.9 s]
which is about the same as without these patches. So, there is no speed loss.
But when I also apply the patch from here, I get
sage -t "devel/sage-main/sage/schemes/elliptic_curves/sha_tate.py" [30.3 s]
A similar slow down is visible for the tests from heegner.py.
What could be the reason? What arithmetic operations are dominant?
My original impression was that it is operations in large integer quotient rings. But that isn't the problem according to these tests:
sage: R = Integers(3814697265625) sage: a = R(1021573325796) sage: b = R(2884990864521) sage: timeit('a+b',number=10^6) 1000000 loops, best of 3: 297 ns per loop sage: timeit('a*b',number=10^6) 1000000 loops, best of 3: 397 ns per loop sage: timeit('a+2',number=10^6) 1000000 loops, best of 3: 1.24 µs per loop sage: timeit('a*2',number=10^6) 1000000 loops, best of 3: 1.4 µs per loop sage: timeit('a.sqrt()') 625 loops, best of 3: 146 µs per loop
I get more or less the same timings with or without the patch.
Any idea?
comment:28 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues changed from Doctest errors to Improve Monsky-Washnitzer
I see that there is a lot of slow-down in the Monsky-Washnitzer code, namely arithmetic in SpecialCubicQuotientRing
:
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: x, T = R.gens() sage: x (0) + (1)*x + (0)*x^2 sage: T (T) + (0)*x + (0)*x^2
In vanilla sage-4.6.2, I get sage: timeit('x*T') 625 loops, best of 3: 491 µs per loop }}} With the patches, I get
sage: timeit('x*T') 625 loops, best of 3: 612 µs per loop
So, there is your problem!
comment:29 Changed 10 years ago by
Closing in...
With patches
sage: %prun L=[x*T for _ in xrange(1000)] 392002 function calls in 0.766 CPU seconds Ordered by: internal time ncalls tottime percall cumtime percall filename:lineno(function) 384000 0.371 0.000 0.371 0.000 polynomial_ring.py:1836(modulus) 1000 0.367 0.000 0.724 0.001 monsky_washnitzer.py:553(_mul_) 1 0.017 0.017 0.766 0.766 <string>:1(<module>) 2000 0.006 0.000 0.006 0.000 integer_mod_ring.py:726(_repr_) 1000 0.003 0.000 0.004 0.000 monsky_washnitzer.py:325(__init__) 2000 0.001 0.000 0.001 0.000 {isinstance} 2000 0.000 0.000 0.000 0.000 {method 'parent' of 'sage.structure.element.Element' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
Without patches:
sage: %prun L=[x*T for _ in xrange(1000)] 404602 function calls in 0.684 CPU seconds Ordered by: internal time ncalls tottime percall cumtime percall filename:lineno(function) 1000 0.366 0.000 0.651 0.001 monsky_washnitzer.py:553(_mul_) 384600 0.234 0.000 0.234 0.000 polynomial_ring.py:1797(modulus) 2000 0.047 0.000 0.061 0.000 polynomial_ring.py:212(_element_constructor_) 1 0.018 0.018 0.684 0.684 <string>:1(<module>) 2000 0.007 0.000 0.007 0.000 integer_mod_ring.py:726(_repr_) 2000 0.005 0.000 0.006 0.000 integer_mod_ring.py:911(__cmp__) 1000 0.003 0.000 0.004 0.000 monsky_washnitzer.py:325(__init__) 4000 0.003 0.000 0.003 0.000 {isinstance} 4000 0.001 0.000 0.001 0.000 {method 'parent' of 'sage.structure.element.Element' objects} 2000 0.001 0.000 0.001 0.000 {cmp} 2000 0.000 0.000 0.000 0.000 {method 'base_ring' of 'sage.structure.category_object.CategoryObject' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
In other words: The biggest loss is the call to modulus()
. That should be possible to fix.
comment:30 Changed 10 years ago by
Possible reason:
sage: P = R.poly_ring() sage: len(P.__class__.mro()) 14 # without patch 35 # with patch
Apparently that makes attribute access slower.
comment:31 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
- Summary changed from Categories for polynomial rings to Categories for all rings
- Work issues Improve Monsky-Washnitzer deleted
I just found that the problem with modulus
is an excellent use case for the improved cached methods provided by #11115!
Namely, instead of caching the modulus in a Python attribute __modulus
and have self.modulus()
return self.__modulus
, I define self.modulus()
as a cached method -- and that is a lot faster:
With the patches:
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: P = R.poly_ring() sage: timeit('P.modulus()',number=10^6) 1000000 loops, best of 3: 226 ns per loop sage: x, T = R.gens() sage: timeit('x*T') 625 loops, best of 3: 234 Âµs per loop
Without the patches (and without the quick cached methods):
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: P = R.poly_ring() sage: timeit('P.modulus()',number=10^6) 1000000 loops, best of 3: 647 ns per loop sage: x, T = R.gens() sage: timeit('x*T') 625 loops, best of 3: 495 Âµs per loop
So, the slow-down turned into a speed-up. I don't know if the doc tests will all pass, but I put it as "needs review".
comment:32 Changed 10 years ago by
Note, however, that sage -t "devel/sage-main/sage/schemes/elliptic_curves/sha_tate.py"
is not up to speed, yet, but not as slow as with the old patch.
comment:33 Changed 10 years ago by
It could actually be that I there is no regression in Monsky-Washnitzer at all.
I just took the tests from sage/schemes/elliptic_curves/monsky_washnitzer.py and timed each test individually (using timeit). In all cases, the tests went faster with my patches - even though "sage -t" took 50% longer than without the patches.
My next guess was that there is a problem with the startup time. Indeed, starting sage without the patches feels "snappier".
Using "sage -startuptime", I found with the patches:
== Slowest (including children) == 1.623 sage.all (None) 0.356 sage.schemes.all (sage.all) 0.225 elliptic_curves.all (sage.schemes.all) 0.222 ell_rational_field (elliptic_curves.all) 0.216 sage.rings.all (sage.all) 0.214 sage.misc.all (sage.all) 0.173 sage.algebras.all (sage.all) 0.153 ell_number_field (ell_rational_field)
Without patch:
== Slowest (including children) == 1.196 sage.all (None) 0.312 sage.schemes.all (sage.all) 0.190 twisted.persisted.styles (sage.all) 0.176 elliptic_curves.all (sage.schemes.all) 0.172 ell_rational_field (elliptic_curves.all) 0.172 sage.misc.all (sage.all) 0.151 ell_number_field (ell_rational_field) 0.150 ell_field (ell_number_field) ... 0.087 sage.rings.all (sage.all) ... 0.035 sage.algebras.all (sage.all)
comment:34 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to startup time
comment:35 follow-up: ↓ 36 Changed 10 years ago by
It turns out that the measuring of the startup time is by far too flaky. Without the patches, the startup time varies from "1.008 sage.all (None)" to "1.518 sage.all (None)". There seems to be a regression, though.
comment:36 in reply to: ↑ 35 Changed 10 years ago by
Replying to SimonKing:
It turns out that the measuring of the startup time is by far too flaky. Without the patches, the startup time varies from "1.008 sage.all (None)" to "1.518 sage.all (None)". There seems to be a regression, though.
I have to correct myself.
It turned out that both the slow-down in the startup time and the slow-down in the Monsky-Washnitzer code are caused by #11115. So, I suggest that I prepare a new patch that is not based on #11115.
comment:37 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
- Work issues startup time deleted
comment:38 Changed 10 years ago by
For the record: Both sage -startuptime
and the Monsky-Washnitzer example do not report a significant slow-down. It is not a speed-up either, but I think that speeding things up shall be the job of #11115, eventually.
comment:39 Changed 10 years ago by
comment:40 follow-up: ↓ 41 Changed 10 years ago by
To be on the safe side, I repeated timings with the latest patch from here, applied only on top of #9944:
$ ./sage -startuptime ... == Slowest (including children) == 1.396 sage.all (None) 0.398 sage.misc.all (sage.all) 0.285 functional (sage.misc.all) 0.282 sage.schemes.all (sage.all) 0.271 sage.rings.complex_double (functional) ...
and
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: P = R.poly_ring() sage: x, T = R.gens() sage: timeit('x*T') 625 loops, best of 3: 869 µs per loop
Without all these patches, I get
$ ./sage -startuptime ... == Slowest (including children) == 1.282 sage.all (None) 0.284 sage.schemes.all (sage.all) 0.241 sage.misc.all (sage.all) 0.184 twisted.persisted.styles (sage.all) 0.165 elliptic_curves.all (sage.schemes.all) ...
and
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: P = R.poly_ring() sage: x, T = R.gens() sage: timeit('x*T') 625 loops, best of 3: 501 µs per loop
I think the timing of the startup time is within the error margin. But there is a slow-down of the Monsky-Washnitzer code. I have shown how to solve the latter problem, based on #11115.
I leave the decision to the reviewer whether or not #11115, together with a patch that puts a cached_method decorator in front of the modulus method, should be a dependency for this ticket.
comment:41 in reply to: ↑ 40 Changed 10 years ago by
Replying to SimonKing:
I leave the decision to the reviewer whether or not #11115, together with a patch that puts a cached_method decorator in front of the modulus method, should be a dependency for this ticket.
Apparently there is no reviewer :(
Anyway. I modified the patch so that now modulus()
becomes a cached method. This provides a speed-up even without #11115. And once #11115 is merged as well, the speed-up will increase.
Without #11115, but with the patches from #9944 and from here:
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: P = R.poly_ring() sage: x, T = R.gens() # Without patches, the following was 495 Âµs per loop sage: timeit('x*T') 625 loops, best of 3: 472 µs per loop sage: %prun L=[x*T for _ in xrange(1000)] 392002 function calls in 0.590 CPU seconds Ordered by: internal time ncalls tottime percall cumtime percall filename:lineno(function) 1000 0.385 0.000 0.560 0.001 monsky_washnitzer.py:553(_mul_) 384000 0.177 0.000 0.177 0.000 cachefunc.py:505(__call__) 1 0.019 0.019 0.590 0.590 <string>:1(<module>) 2000 0.006 0.000 0.006 0.000 integer_mod_ring.py:726(_repr_) 1000 0.003 0.000 0.004 0.000 monsky_washnitzer.py:325(__init__) 2000 0.001 0.000 0.001 0.000 {isinstance} 2000 0.000 0.000 0.000 0.000 {method 'parent' of 'sage.structure.element.Element' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
That's better than with an unpatched Sage and thus good enough.
comment:42 follow-up: ↓ 43 Changed 10 years ago by
- Status changed from needs_review to needs_work
- Work issues set to Categories for more rings...
While working on #11115, I found that there are still some rings that do neither use the new coercion framework nor properly initialize their category. That includes quotient rings and free algebras. The problem is that, even though they inherit from sage.rings.ring.Ring, they do not call the appropriate __init__
.
I was wondering whether that should be done here or on #11115, but after all I think it should better be here.
comment:43 in reply to: ↑ 42 Changed 10 years ago by
Replying to SimonKing:
While working on #11115, I found that there are still some rings that do neither use the new coercion framework nor properly initialize their category. That includes quotient rings and free algebras. The problem is that, even though they inherit from sage.rings.ring.Ring, they do not call the appropriate
__init__
.I was wondering whether that should be done here or on #11115, but after all I think it should better be here.
Both routes look fine. Please pick up whichever is more practical to you.
comment:44 Changed 10 years ago by
It is rather frustrating. I try to fit BooleanPolynomialRing
into the new coercion model, defining _element_constructor_ and _coerce_map_from_ -- and now, suddenly Sage is complaining that it is still using the old coercion model! I found that the reason for the complaint is the existence of _element_constructor. But that should be the new model, shouldn't it??
Time to call it a day...
comment:45 Changed 10 years ago by
It turned out that the notion of "coercion" was not used in the proper way, in sage.rings.polynomial.pbori. Namely, _coerce_
was used to convert a boolean set into a boolean polynomial. That can not be called a coercion, since boolean sets have no parent (at least no parent that would allow for a coercion map). The old coercion model did not mind, but the new coercion model complains about those things.
Moreover, there was a custom call method that first tried to call self._coerce_(x)
. When one renames that call method to _element_contructor_
(for the new coercion model) then one obtains an infinite recursion, because you need to evaluate the element constructor for constructing the _coerce_
method.
In other words, one needs to replace P._coerce_(...)
and P.coerce(...)
by either P(...)
or by a direct call to P._coerce_c_impl(...)
. This is what I'm trying now.
comment:46 Changed 10 years ago by
Good news: I managed to implement pickling for boolean monomial monoids and boolean monomials, to fit everything into the new coercion model and to make TestSuite(...).run()
work on boolean polynomial rings and boolean monomial monoids.
I am not updating my patch yet, though, since there are further issues to fix.
comment:47 Changed 10 years ago by
I just found a problem with the category of quotients:
sage: EuclideanDomains().Quotients() Join of Category of euclidean domains and Category of subquotients of monoids and Category of quotients of semigroups
That's plain wrong. Think of the ring of integers mod 16, which is certainly not a euclidean domain (not even integral domain), but should belong to the category of quotients of euclidean domains.
I'll try to analyse the problem. I noticed it when I tried to provide Integers(n)
with an appropriate category.
comment:48 Changed 10 years ago by
Wow!! I found that the wrong result is actually doctested in sage.categores.quotients!
That has to change.
comment:49 follow-up: ↓ 50 Changed 10 years ago by
From the doc:
Given a concrete category ``As()`` (i.e. a subcategory of ``Sets()``), ``As().Quotients()`` returns the category of objects of ``As()`` endowed with a distinguished description as quotient of some other object of ``As()``.
IntMod16 is *not* a quotient of ZZ by a morphism of *euclidean domains*. So it is not in EuclideanDomains?().Quotients().
comment:50 in reply to: ↑ 49 ; follow-up: ↓ 51 Changed 10 years ago by
Replying to nthiery:
From the doc:
Given a concrete category ``As()`` (i.e. a subcategory of ``Sets()``), ``As().Quotients()`` returns the category of objects of ``As()`` endowed with a distinguished description as quotient of some other object of ``As()``.IntMod16 is *not* a quotient of ZZ by a morphism of *euclidean domains*. So it is not in EuclideanDomains?().Quotients().
I see. So, I can not provide QuotientRing
with the category of quotients of the category of the ambient ring.
comment:51 in reply to: ↑ 50 Changed 10 years ago by
Replying to SimonKing:
I see. So, I can not provide
QuotientRing
with the category of quotients of the category of the ambient ring.
Yup. E.g. the quotient of an algebra A by a vector space I is just a vector space. But if I is an ideal, more can be said. So the logic to determine this piece of mathematical information is non trivial, and often one is better off just specifying it explicitly.
comment:52 follow-up: ↓ 53 Changed 9 years ago by
- Status changed from needs_work to needs_review
- Work issues Categories for more rings... deleted
The first patch did not cover all rings - it turned out that many classes derived from sage.rings.ring.Ring do in fact not call the __init__
method of rings. Hence, in these cases, the category stuff was not present.
The second patch takes care of some of these cases - I think I shouldn't vouch for completeness, though. Moreover, I implemented the new coercion model for some more classes of rings, such as free algebras, quotient rings, and boolean polynomial rings.
Concerning quotient rings: I hope that the category of this quotient ring is correctly chosen:
sage: P.<x,y> = QQ[] sage: Q = P.quo(P*[x^2+y^2]) sage: Q.category() Join of Category of commutative rings and Category of subquotients of monoids and Category of quotients of semigroups
What do you think: Should it perhaps better be "join of Category of commutative algebras over Rational Field and Category of subquotients ..."? After all, P belongs to the category of commutative algebras over the rational field.
But apart from that, it seems ready for review now.
comment:53 in reply to: ↑ 52 ; follow-up: ↓ 54 Changed 9 years ago by
Replying to SimonKing:
The first patch did not cover all rings - it turned out that many classes derived from sage.rings.ring.Ring do in fact not call the
__init__
method of rings. Hence, in these cases, the category stuff was not present.The second patch takes care of some of these cases - I think I shouldn't vouch for completeness, though. Moreover, I implemented the new coercion model for some more classes of rings, such as free algebras, quotient rings, and boolean polynomial rings.
Cool!
Concerning quotient rings: I hope that the category of this quotient ring is correctly chosen:
sage: P.<x,y> = QQ[] sage: Q = P.quo(P*[x^2+y^2]) sage: Q.category() Join of Category of commutative rings and Category of subquotients of monoids and Category of quotients of semigroupsWhat do you think: Should it perhaps better be "join of Category of commutative algebras over Rational Field and Category of subquotients ..."? After all, P belongs to the category of commutative algebras over the rational field.
If multiplication by elements of QQ are implemented (and I assume they are), then yes I definitely would go for commutative algebras.
But apart from that, it seems ready for review now.
Nice! I'll work on that in the coming weeks, but can't promise when with the upcoming Sage days. Please anyone beat me to it!
Cheers,
Nicolas
comment:54 in reply to: ↑ 53 Changed 9 years ago by
I just noticed:
The patch not only depends on #9944 but is based on sage-4.7.alpha5. I don't know which other patches are responsible for that, but the part of the patch that concerns the polybori code fails to apply with sage-4.6.
Replying to nthiery:
What do you think: Should it perhaps better be "join of Category of commutative algebras over Rational Field and Category of subquotients ..."? After all, P belongs to the category of commutative algebras over the rational field.
If multiplication by elements of QQ are implemented (and I assume they are), then yes I definitely would go for commutative algebras.
I looked at the code, and it seems that at least operation of the base ring exists. But I think one should also implement an _rmul_
and _lmul_
for quotient ring elements - it is missing, so far.
Best regards, Simon
comment:55 Changed 9 years ago by
comment:56 Changed 9 years ago by
comment:57 Changed 9 years ago by
The patchbot keeps complaining. I don't know why. Anyway, applied on top of sage-4.7.alpha5, it works for me.
comment:58 Changed 9 years ago by
- Dependencies set to #9944
comment:59 Changed 9 years ago by
- Status changed from needs_review to needs_work
Apparently the patches need to be rebased: I just tried to apply it on top of my patch queue (including some other relevant tickets), and 8 hunks did not apply for the first of the two patches. Needs work.
comment:60 Changed 9 years ago by
- Dependencies changed from #9944 to sage-4.7, #11268, #11139, #9976, #9944, #11269
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:61 Changed 9 years ago by
FWIW, all (short) tests pass for me.
comment:62 Changed 9 years ago by
The dependencies of this patch are stated in the corresponding form field. For the following timings, I additionally have #11298, #11267 and, in particular, #11115.
In some cases, there is quite an improvement, compared with the timings that are stated in previous comments! Note that the times per loop change, depending on whether one lets timeit run 10^4
loops (as in #9944) or one simply does timeit
without any specification.
First series of timings: I guess most of the speedup is due to #9944
sage: R.<x> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 20.9 µs per loop # unpatched 625 loops, best of 3: 22.5 Âµs per loop sage: R.<x> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 21.3 µs per loop # unpatched 625 loops, best of 3: 24.5 Âµs per loop sage: R.<x> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 19.2 µs per loop # unpatched 625 loops, best of 3: 87.7 Âµs per loop sage: R.<x> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 75.4 µs per loop # unpatched 625 loops, best of 3: 114 Âµs per loop sage: R.<x,y> = ZZ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 19.7 µs per loop # unpatched 625 loops, best of 3: 21.9 Âµs per loop sage: R.<x,y> = QQ[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 18.2 µs per loop # unpatched 625 loops, best of 3: 40 Âµs per loop sage: R.<x,y> = GF(3)[] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 15.8 µs per loop # unpatched 625 loops, best of 3: 26.3 Âµs per loop sage: R.<x,y> = QQ['t'][] sage: timeit('(2*x-1)^2+5') 625 loops, best of 3: 162 µs per loop # unpatched 625 loops, best of 3: 239 Âµs per loop
Timings for some "schemes" tests.
sage -t "devel/sage-main/sage/schemes/elliptic_curves/sha_tate.py" [29.5 s]
I have not the faintest idea where that slow-down might come from. Namely, the underlying arithmetic has drastically improved:
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: x, T = R.gens() sage: timeit('x*T') 625 loops, best of 3: 179 µs per loop # unpatched: 625 loops, best of 3: 612 µs per loop
and
sage: B.<t> = PolynomialRing(Integers(125)) sage: R = monsky_washnitzer.SpecialCubicQuotientRing(t^3 - t + B(1/4)) sage: P = R.poly_ring() sage: timeit('P.modulus()',number=10^6) 1000000 loops, best of 3: 161 ns per loop # unpatched: 1000000 loops, best of 3: 647 ns per loop sage: x, T = R.gens() sage: timeit('x*T') 625 loops, best of 3: 177 µs per loop # unpatched: 625 loops, best of 3: 495 Âµs per loop
And the startup time (which is also relevant for doctests:
1.326 sage.all (None) 0.324 sage.schemes.all (sage.all) 0.184 sage.misc.all (sage.all) 0.160 hyperelliptic_curves.all (sage.schemes.all)
I'd appreciate if someone could explain why the doctest time in sage.schemes increased, while the underlying arithmetics became faster.
Overall, I think that the performance is quite good, and of course the main point of this ticket (namely to implement the category framework for rings) was successfully addressed.
Review, anyone?
comment:63 Changed 9 years ago by
- Description modified (diff)
comment:64 Changed 9 years ago by
Thank you, Burcin!
For the patchbot:
Apply trac9138-categories_for_rings.patch, trac9138_categories_for_more_rings.rebase4.7.1.a1.patch
comment:65 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to Steenrod algebras
It seems that there is a problem with doctests for the Steenrod algebra. When I apply the patch on top of sage-4.7.1.rc1, I obtain
sage: SteenrodAlgebra(2)['x'].category() Exception raised: Traceback (most recent call last): File "/mnt/local/king/SAGE/sage-4.7.1.rc1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/mnt/local/king/SAGE/sage-4.7.1.rc1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/mnt/local/king/SAGE/sage-4.7.1.rc1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_1[12]>", line 1, in <module> SteenrodAlgebra(Integer(2))['x'].category()###line 114: sage: SteenrodAlgebra(2)['x'].category() File "/mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python/site-packages/sage/algebras/steenrod/steenrod_algebra.py", line 1037, in homogeneous_component basis = self._basis_fcn(n) File "cachefunc.pyx", line 531, in sage.misc.cachefunc.CachedFunction.__call__ (sage/misc/cachefunc.c:2227) File "/mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python/site-packages/sage/algebras/steenrod/steenrod_algebra_bases.py", line 368, in steenrod_algebra_basis_ if n < 0 or int(n) != n: ValueError: invalid literal for int() with base 10: 'x'
So, back to the drawing board...
comment:66 follow-up: ↓ 67 Changed 9 years ago by
I wonder if the Steenrod algebra problem is due to #10052, which was merged in 4.7.1.alpha3.
comment:67 in reply to: ↑ 66 ; follow-up: ↓ 68 Changed 9 years ago by
Replying to jhpalmieri:
I wonder if the Steenrod algebra problem is due to #10052, which was merged in 4.7.1.alpha3.
I wouldn't say "due to", since the critical tests (perhaps introduced by #10052) pass with sage-4.7.1.rc1. In fact, I already found out that trac9138-categories_for_rings.patch is to blame. But I don't know yet what went wrong.
comment:68 in reply to: ↑ 67 Changed 9 years ago by
comment:69 follow-up: ↓ 70 Changed 9 years ago by
In my first patch, I had introduced the test
sage: SteenrodAlgebra(2)['x'].category() Category of algebras over mod 2 Steenrod algebra
It was supposed to be a test for a polynomial ring over a non-commutative ring. But by your patch from #10052, the __getitem__
method of a Steenrod algebra got a different meaning.
I think the easiest solution (and probably the best solution as well would be to replace that test by a polynomial ring over a different non-commutative algebra, perhaps a matrix algebra.
comment:70 in reply to: ↑ 69 Changed 9 years ago by
Replying to SimonKing:
I think the easiest solution (and probably the best solution as well would be to replace that test by a polynomial ring over a different non-commutative algebra, perhaps a matrix algebra.
Helàs.
Matrix spaces have their custom __getitem__
as well. But it would be possible to construct the polynomial ring by using the polynomial ring constructor:
sage: PolynomialRing(MatrixSpace(QQ,2),'x').category() Category of algebras over Full MatrixSpace of 2 by 2 dense matrices over Rational Field sage: PolynomialRing(SteenrodAlgebra(2),'x').category() Category of algebras over mod 2 Steenrod algebra, milnor basis
The other problem is in sage/algebras/steenrod/steenrod_algebra.py.: With the patch from here,
sage: A1 = SteenrodAlgebra(profile=[2,1]) sage: A1(3) # map integer into A1
returns 3 and not 1!
That behaviour boils down to
sage: A1._from_dict({():3}) 3
Here, one should have
sage: A1._from_dict({():3},coerce=True) 1
I don't know, though, how my patch has changed the question whether there is a conversion or not: The word coerce
occurs precisely twice in my first patch, but that is certainly unrelated with "coerce=True" versus "coerce=False". Strange.
comment:71 follow-up: ↓ 72 Changed 9 years ago by
It seems that the problem is deeper. With the first patch, I obtain
sage: A1 = SteenrodAlgebra(profile=[2,1]) sage: A1.coerce_map_from(ZZ) Conversion map: From: Integer Ring To: sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [2, 1]
Without the patch, I obtain
sage: A1 = SteenrodAlgebra(profile=[2,1]) sage: A1.coerce_map_from(ZZ) Composite map: From: Integer Ring To: sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [2, 1] Defn: Natural morphism: From: Integer Ring To: Finite Field of size 2 then Generic morphism: From: Finite Field of size 2 To: sub-Hopf algebra of mod 2 Steenrod algebra, milnor basis, profile function [2, 1]
By consequence, when doing A1(3)
with my patch, a direct conversion is attempted from ZZ
to A1
, but the auxiliary methods involved in the conversion assume that the argument 3 has already been converted into the base ring, GF(2)
.
Perhaps a "register_coercion" during initialisation could help.
comment:72 in reply to: ↑ 71 Changed 9 years ago by
Replying to SimonKing:
Perhaps a "register_coercion" during initialisation could help.
Actually, that registration should take place in the __init_extra__
method that is defined in sage.categories.algebras
. Without my patch, the rather generic coercion from the base ring is registered no matter what, which means that it could result in a very slow coerce map from the base ring.
Therefore, my patch modifies __init_extra__
so that the generic coercion is only registered if no "better" coercion has been registered before. It could be that that is a problem for Steenrod algebras.
comment:73 Changed 9 years ago by
By inserting print statements into my new init_extra method, I found out that when it is called, the "one" of the Steenrod algebra is not available, yet. Therefore, the generic method ("multiply the given element of the base ring with the multiplicative unit of the algebra") is not available at that time.
Without my patch, a different method is used for coercion, namely
SetMorphism(function = self.from_base_ring, parent = Hom(self.base_ring(), self, Rings()))
The reason for changing it was the fact that normally self.one()._lmul_(r)
is a pretty fast way to convert a base ring element r into self. But I guess that the old from_base_ring
should be used if the unit is not available during initialisation.
comment:74 Changed 9 years ago by
That said: The generic from_base_ring does exactly the same as my new approach -- but it constructs the unit again and again and again. Therefore, if the unit is available during initialisation, then my approach is faster.
comment:75 Changed 9 years ago by
I am now fighting against some doc test failures, that are apparently due to the fact that many tests in sage.rings.polynomial.multi_polynomial_ring
do not use the cache of polynomial rings, in order to demonstrate features of ring classes that would otherwise hardly be used.
Problem: If there is a ring in the cache, together with a coerce map from its base ring, then the coerce map is cached as well. Later, if one constructs an isomorphic ring that is not in the cache of rings, then the ring will evaluate equal to the previously constructed ring, and thus looking up the coerce map yields a map with the wrong codomain.
Difficult.
comment:76 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
- Work issues Steenrod algebras deleted
The problem was that some doc tests in sage/rings violate the unique parent assumption on purpose. But homsets will try to be unique even if domain and codomain are not unique. That's bad.
Therefore, I made the following change for my first patch: If Hom(X,Y,category)
is able to find a hom set H for the given data in cache, then it is first tested that H.domain() is X
and H.codomain() is Y
. If it isn't, then a new hom set is constructed, and put into the cache.
Hence, we have (as a new doctest):
By trac ticket #9138, we abandon the uniqueness of hom sets, if the domain or codomain break uniqueness:: sage: from sage.rings.polynomial.multi_polynomial_ring import MPolynomialRing_polydict_domain sage: P.<x,y,z>=MPolynomialRing_polydict_domain(QQ, 3, order='degrevlex') sage: Q.<x,y,z>=MPolynomialRing_polydict_domain(QQ, 3, order='degrevlex') sage: P == Q True sage: P is Q False Hence, P and Q are not unique parents. By consequence, the following homsets aren't either:: sage: H1 = Hom(QQ,P) sage: H2 = Hom(QQ,Q) sage: H1 == H2 True sage: H1 is H2 False It is always the most recently constructed hom set that remains in the cache:: sage: H2 is Hom(QQ,Q) True
The second patch still applies on top of the first. I did the doc tests in sage/rings and sage/categories with the first patch, but full doc tests should be run with both patches, of course.
Apply trac9138-categories_for_rings.patch trac9138_categories_for_more_rings.rebase4.7.1.a1.patch
comment:77 follow-up: ↓ 78 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to doc test errors in sage/doc
Too bad. There are numerous errors for the tests in sage/doc.
comment:78 in reply to: ↑ 77 Changed 9 years ago by
Replying to SimonKing:
Too bad. There are numerous errors for the tests in sage/doc.
To be precise: The errors seem to come from elliptic curves. Not for the first time...
comment:79 Changed 9 years ago by
For example, I get
sage: L = EllipticCurve('11a').padic_lseries(5) --------------------------------------------------------------------------- RuntimeError Traceback (most recent call last) /home/king/<ipython console> in <module>() /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/padics.pyc in padic_lseries(self, p, normalize, use_eclib) 157 if self.ap(p) % p != 0: 158 Lp = plseries.pAdicLseriesOrdinary(self, p, --> 159 normalize = normalize, use_eclib=use_eclib) 160 else: 161 Lp = plseries.pAdicLseriesSupersingular(self, p, /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/padic_lseries.pyc in __init__(self, E, p, use_eclib, normalize) 197 print "Warning : Curve outside Cremona's table. Computations of modular symbol space might take very long !" 198 --> 199 self._modular_symbol = E.modular_symbol(sign=+1, use_eclib = use_eclib, normalize=normalize) 200 201 def __add_negative_space(self): /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_rational_field.pyc in modular_symbol(self, sign, use_eclib, normalize) 1241 M = ell_modular_symbols.ModularSymbolECLIB(self, sign, normalize=normalize) 1242 else : -> 1243 M = ell_modular_symbols.ModularSymbolSage(self, sign, normalize=normalize) 1244 self.__modular_symbol[typ] = M 1245 return M /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_modular_symbols.pyc in __init__(self, E, sign, normalize) 621 self._use_eclib = False 622 self._normalize = normalize --> 623 self._modsym = E.modular_symbol_space(sign=self._sign) 624 self._base_ring = self._modsym.base_ring() 625 self._ambient_modsym = self._modsym.ambient_module() /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_rational_field.pyc in modular_symbol_space(self, sign, base_ring, bound) 1111 except KeyError: 1112 pass -> 1113 M = ell_modular_symbols.modular_symbol_space(self, sign, base_ring, bound=bound) 1114 self.__modular_symbol_space[typ] = M 1115 return M /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_modular_symbols.pyc in modular_symbol_space(E, sign, base_ring, bound) 110 t = V.T(p) 111 ap = E.ap(p) --> 112 V = (t - ap).kernel() 113 p = next_prime(p) 114 /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__sub__ (sage/structure/element.c:12234)() /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6463)() /mnt/local/king/SAGE/sage-4.7.1.rc1/local/lib/python2.6/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.canonical_coercion (sage/structure/coerce.c:7862)() RuntimeError: BUG in map, returned None -2 <type 'sage.categories.map.FormalCompositeMap'> Composite map: From: Integer Ring To: Full Hecke algebra acting on Modular Symbols space of dimension 2 for Gamma_0(11) of weight 2 with sign 1 over Rational Field Defn: Natural morphism: From: Integer Ring To: Rational Field then Generic morphism: From: Rational Field To: Full Hecke algebra acting on Modular Symbols space of dimension 2 for Gamma_0(11) of weight 2 with sign 1 over Rational Field
with the latest patches.
comment:80 Changed 9 years ago by
- Status changed from needs_work to needs_review
- Work issues doc test errors in sage/doc deleted
At last it seems to work! With the new first patch together with the second patch, all doc tests (both sage/ and doc/) pass (at least for me)!
Here is the problem and its solution.
First Problem
Hecke algebras: _lmul_ for its elements returns None. The previous patch version would thus register from_base_ring
for coercion. However, in that case, a default implementation of from_base_ring
would be used, which fails if _lmul_ returns None. Hence, it must not be registered as coercion.
Solution: Use from_base_ring if it is a custom implementation , i.e., if self.from_base_ring
is not obtained from self.category().parent_class.from_base_ring
. If it is clear that the default implementation won't work, then do not register from_base_ring as coercion.
Additional advantage: If the user provides a fast custom from_base_ring
then it will be picked up.
Second problem
SpecialCubicQuotientRing
: Here, self.one() had not been available during initialisation
of coercion from the base ring. Hence, in the previous patch version, from_base_ring
had been registered.
However, _lmul_ is returning None, again. Additional complication:
The initialisation of a SpecialCubicQuotientRing
as a commutative algebra happened
too early, namely before its hash was available. Hence, the attempt to construct
a hom set containing the coercion from the base ring had failed.
Solution: Move CommutativeAlgebra.__init__
nearer to the end of SpecialCubicQuotientRing.__init__
,
namely to a point where both self.one() and the hash are available.
Conclusion
Ready for Review!
Apply trac9138-categories_for_rings.patch trac9138_categories_for_more_rings.rebase4.7.1.a1.patch
comment:81 Changed 9 years ago by
PS: It seems that the patch bot has a problem, because it doesn't understand that one of the patches of #9976 is for the devel/sagenb repository, not for devel/sage. Too bad...
comment:82 Changed 9 years ago by
- Status changed from needs_review to needs_work
I am currently getting doctest failures with my patches, when I start with sage-4.7.1.rc2 and some other patches.
I seems likely that the errors come from trac9138-categories_for_rings.patch, but it needs further investigation. For the moment, it needs work.
comment:83 Changed 9 years ago by
- Dependencies changed from sage-4.7, #11268, #11139, #9976, #9944, #11269 to sage-4.7, #11268, #11139, #9976, #9944, #11269, #11316
I added another dependency, namely #11316 (weighted degree term orders), that already has a positive review. But it still needs work, and because of the new dependency the first patch will require to be rebased.
comment:84 Changed 9 years ago by
- Work issues set to Fix doctest errors created by the second patch
The first patch needs to be rebased because of #11316, but it does not yield doctest errors.
However, the second patch introduces errors in devel/sage-main/sage/crypto/boolean_function.pyx and devel/sage-main/sage/rings/polynomial/pbori.pyx; in each case, 14 tests fail.
So, back to the drawing board...
comment:85 follow-up: ↓ 86 Changed 9 years ago by
Snap diagnose: #11316 changed when the term order is created, and I changed the order of things as well. In consequence, variable names are assigned twice, which yields an error. Example:
sage: from polybori import * sage: declare_ring([Block('x',2),Block('y',3)],globals()) Traceback (most recent call last) ... ValueError: variable names cannot be changed after object creation.
comment:86 in reply to: ↑ 85 Changed 9 years ago by
Replying to SimonKing:
Snap diagnose: #11316 changed when the term order is created, and I changed the order of things as well. In consequence, variable names are assigned twice, which yields an error.
I don't know what other ticket was creating the conflict (it has not been #11316, sorry for that). Anyway, the problem is that MPolynomialRing_generic.__init__
was calling ParentWithGens.__init__
first, and then Ring.__init__
. By consequence, name assignment is tried twice - which is not allowed.
I am currently running the doc tests (the two tests that previously failed are now fine), and if it succeeds then I'll update both patches.
comment:87 Changed 9 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
Both patches are updated: The first since it is rebased against #11316, the second since a rogue initialisation of a ParentWithGens
occured.
For me, all tests pass, with sage-4.7.1.rc2 plus #11316 plus both patches from here. Thus, needs review again.
Apply trac9138-categories_for_rings.patch trac9138_categories_for_more_rings.patch
comment:88 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues changed from Fix doctest errors created by the second patch to fix doctests errors in pbory
I tested against sage-4.7.2.alpha1 . I didn't add any dependancys because their descriptions all say they are merged in that version already. Almost all test pass except some tests in pbori.pyx .
mderickx@sage:/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha1/devel/sage$ ../../sage -t --long sage/rings/polynomial/pbori.pyx sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" ********************************************************************** File "/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha1/devel/sage-main/sage/rings/polynomial/pbori.pyx", line 843: sage: P(p) Exception raised: Traceback (most recent call last): File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_10[23]>", line 1, in <module> P(p)###line 843: sage: P(p) File "parent.pyx", line 945, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:7108) File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3256) File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3159) File "pbori.pyx", line 896, in sage.rings.polynomial.pbori.BooleanPolynomialRing._element_constructor_ (sage/rings/polynomial/pbori.cpp:8488) IndexError: list index out of range ********************************************************************** File "/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha1/devel/sage-main/sage/rings/polynomial/pbori.pyx", line 563: sage: ZZ['a'].gen() + c Exception raised: Traceback (most recent call last): File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_8[16]>", line 1, in <module> ZZ['a'].gen() + c###line 563: sage: ZZ['a'].gen() + c File "element.pyx", line 1309, in sage.structure.element.RingElement.__add__ (sage/structure/element.c:11532) File "coerce.pyx", line 713, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6420) File "coerce.pyx", line 827, in sage.structure.coerce.CoercionModel_cache_maps.canonical_coercion (sage/structure/coerce.c:7682) File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3256) File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3159) File "pbori.pyx", line 896, in sage.rings.polynomial.pbori.BooleanPolynomialRing._element_constructor_ (sage/rings/polynomial/pbori.cpp:8488) IndexError: list index out of range ********************************************************************** 2 items had failures: 1 of 25 in __main__.example_10 1 of 18 in __main__.example_8 ***Test Failed*** 2 failures. For whitespace errors, see the file /home/mderickx/.sage//tmp/.doctest_pbori.py [6.1 s] ---------------------------------------------------------------------- The following tests failed: sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" Total time for all tests: 6.1 seconds
A little sanity check that #11316 was really merged in 4.7.2.alpha1
mderickx@sage:/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha1/devel/sage$ ../../sage -hg log sage/rings/polynomial/pbori.pyx |head -n 20 changeset: 15995:f3369d315c96 tag: qtip tag: tip tag: trac9138_categories_for_more_rings.patch user: Simon King <simon.king@uni-jena.de> date: Sun Apr 24 15:28:28 2011 +0200 summary: #9138: Provide the category framework for quotient rings and free algebras. changeset: 15990:cf06a8bb75f4 user: Kwankyu Lee <ekwankyu@gmail.com> date: Tue May 10 16:58:20 2011 +0900 summary: Trac #11316: #11316: added weighted degree term orders
comment:89 Changed 9 years ago by
Strange. With sage-4.7.2.alpha2, I do not get that error.
$ ../../sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" [4.8 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 4.8 seconds
But I installed an updated version of polybori, perhaps that is the reason. So, I should try with vanilla sage-4.7.2.alpha1 and try to replicate the error you get.
comment:90 Changed 9 years ago by
- Status changed from needs_work to needs_review
I can definitely not confirm the error that you got.
I built sage-4.7.2.alpha2 (not alpha1, if that should make a difference). Then I qimported the two patches:
$ hg qapplied trac9138-categories_for_rings.patch trac9138_categories_for_more_rings.patch
followed by sage -b
.
And still I have
$ ../../sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" [7.7 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 7.8 seconds
comment:91 Changed 9 years ago by
- Status changed from needs_review to needs_work
Very very strange. Ok what I did is on sage.math.washington.edu:
I downloaded: http://boxen.math.washington.edu/home/release/sage-4.7.2.alpha2/sage-4.7.2.alpha2.tar Extracted the file and did make build using environment variables MAKE=make -j20 and SAGE_SPKG_PARALLEL_BUILD=yes. After having made this clean build (located in /mnt/usb1/scratch/mderickx/sage-4.7.2.alpha2) I got:
mderickx@sage:/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha2$ ./sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" [7.0 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 7.0 seconds
Then I qimported and applied your two patches and did
mderickx@sage:/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha2/devel/sage$ ../../sage -bt --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" ---------------------------------------------------------- sage: Building and installing modified Sage library files. ...whole load of buiding output sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" ********************************************************************** File "/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha2/devel/sage-main/sage/rings/polynomial/pbori.pyx", line 843: sage: P(p) Exception raised: Traceback (most recent call last): File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_10[23]>", line 1, in <module> P(p)###line 843: sage: P(p) File "parent.pyx", line 945, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:7108) File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3256) File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3159) File "pbori.pyx", line 896, in sage.rings.polynomial.pbori.BooleanPolynomialRing._element_constructor_ (sage/rings/polynomial/pbori.cpp:8488) IndexError: list index out of range ********************************************************************** File "/mnt/usb1/scratch/mderickx/sage-4.7.2.alpha2/devel/sage-main/sage/rings/polynomial/pbori.pyx", line 563: sage: ZZ['a'].gen() + c Exception raised: Traceback (most recent call last): File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/mderickx/.sage/tmp/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_8[16]>", line 1, in <module> ZZ['a'].gen() + c###line 563: sage: ZZ['a'].gen() + c File "element.pyx", line 1309, in sage.structure.element.RingElement.__add__ (sage/structure/element.c:11532) File "coerce.pyx", line 742, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6577) File "coerce.pyx", line 856, in sage.structure.coerce.CoercionModel_cache_maps.canonical_coercion (sage/structure/coerce.c:7818) File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3256) File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3159) File "pbori.pyx", line 896, in sage.rings.polynomial.pbori.BooleanPolynomialRing._element_constructor_ (sage/rings/polynomial/pbori.cpp:8488) IndexError: list index out of range ********************************************************************** 2 items had failures: 1 of 25 in __main__.example_10 1 of 18 in __main__.example_8 ***Test Failed*** 2 failures. For whitespace errors, see the file /home/mderickx/.sage//tmp/.doctest_pbori.py [6.1 s] ---------------------------------------------------------------------- The following tests failed: sage -t --long "devel/sage-main/sage/rings/polynomial/pbori.pyx" Total time for all tests: 6.1 seconds
So I seem to not be able to reproduce your passing the doctest. Did you also use sage.math. I can give you acces to the created folder on sage.math so you can fiddle around with it.
comment:92 follow-up: ↓ 93 Changed 9 years ago by
Is the update of pbory also on another ticket? Maybe we should list it as a dependancy?
comment:93 in reply to: ↑ 92 Changed 9 years ago by
Replying to mderickx:
Is the update of pbory also on another ticket? Maybe we should list it as a dependancy?
No. I did not install the new pbory spkg. Also I didn't try yet to install my patches on sage.math. So, probably that's the next step.
comment:94 Changed 9 years ago by
What I now did was as follows:
- Copy and open the pre-built sage-4.7.2.alpha2.tar.gz for sage.math (saves a lot of time...)
- qimport and apply the first patch, do
sage -b
and find that pbori.pyx still passes the tests. - qimport and apply the second patch, do
sage -b
and confirm the error that you observed.
At least, now there is a chance for me to debug it...
comment:95 Changed 9 years ago by
- Status changed from needs_work to needs_review
- Work issues fix doctests errors in pbory deleted
I got it!!
The problem was a misprint. I use the letter j where it should be the number zero. Apparently, on my machine, j became initialised as zero, so, things worked. But (as I found by printing its value) on sage.math it became initialised as one, hence, resulting in an index error.
I updated the patch, and with it, I find
SimonKing@sage:~/SAGE/sage-4.7.2.alpha2-sage.math.washington.edu-x86_64-Linux$ ./sage -t devel/sage/sage/rings/polynomial/pbori.pyx sage -t "devel/sage/sage/rings/polynomial/pbori.pyx" [6.0 s] ---------------------------------------------------------------------- All tests passed! Total time for all tests: 6.0 seconds
So, that was easy... Back to "needs review"!
comment:96 Changed 9 years ago by
comment:97 Changed 9 years ago by
I see you are the author of both so I guess it depends on wich ticket you want to get merged first. You should rebase one of the two tickets to apply cleanly after the other and add the corresponding dependency in the dependencies field. And maybe also add a note in the description for possible reviewers that it is wiser to first review the ticket on wich it depends.
Personally I would want this ticket to be merged before the other. The main reason is that this ticket really cleans up a lot of rings stuff, and the other ticket just makes things faster. And in general I prefer to do things right first and then make them fast ;). The other reason is that I expect that this ticket will cause more conflicts with other tickets. I would try to get this one in as fast as possible so there are less patches merged depending on doing things the old "wrong" way.
Or an even smarter thing to do would be to make both tickets apply cleanly on their own and passing all doctest in such a way that the can also be applied at the same time (but maybe not passing all doctests) . Then create a third patch wich is fixes the conflict between these tickets. This patch can then be added on wathever ticket gets reviewed/merged last. In this way none of the two tickets can delay the merging of the other.
comment:98 follow-up: ↓ 99 Changed 9 years ago by
- Cc robertwb added
- Dependencies changed from sage-4.7, #11268, #11139, #9976, #9944, #11269, #11316 to sage-4.7, #11268, #11139, #9976, #9944, #11269, #11316, #11342
I've reviewed #11342 before reading Maarten's comment, so how about we can merge #11342 first and #9138 afterwards.
In pbori.pyx
, can you clean up the comparison? E.g. remove __richcmp__
completely and fix the _cmp_
docstring.
In sage/structure/element.pyx
, the following is stated:
# For a derived Cython class, you **must** put the following in # your subclasses, in order for it to take advantage of the # above generic comparison code. You must also define # either _cmp_c_impl (if your subclass is totally ordered), # _richcmp_c_impl (if your subclass is partially ordered), or both # (if your class has both a total order and a partial order; # then the total order will be available with cmp(), and the partial # order will be available with the relation operators; in this case # you must also define __cmp__ in your subclass).
Now this info might be outdated, and I admit that I don't have a good understanding of how comparison is supposed to be implemented in the new coercion model, but your _cmp_
method does not follow that comment.
comment:99 in reply to: ↑ 98 Changed 9 years ago by
Replying to vbraun:
I've reviewed #11342 before reading Maarten's comment, so how about we can merge #11342 first and #9138 afterwards.
Makes sense now...
So, I'll attach a new patch here. The old patch does apply, it is just that one must change the expected output (namely the name of a class) in one test.
In
pbori.pyx
, can you clean up the comparison? E.g. remove__richcmp__
completely and fix the_cmp_
docstring.
OK. Sometimes I like to keep the old code in a comment, so that one can see how and why things have changed. Fixing the _cmp_
docstring is certainly needed.
In
sage/structure/element.pyx
, the following is stated:# For a derived Cython class, you **must** put the following in # your subclasses, in order for it to take advantage of the # above generic comparison code. ... Now this info might be outdated, and I admit that I don't have a good understanding of how comparison is supposed to be implemented in the new coercion model, but your `_cmp_` method does not follow that comment.
What you cite is for elements (and not outdated), but my code is for parents. I am afraid I have no reference. But I think I remember that for parents written in Cython one should provide a (single underscore) _cmp_
method. I might ask on sage-devel, though.
comment:100 Changed 9 years ago by
- Status changed from needs_review to needs_work
- Work issues set to comparison of BooleanPolynomialRings; one doctest fix
Actually the comparison code should be completely removed: Boolean polynomial rings are unique parents, and thus they are equal if and only if they are identical.
So, I will submit a new patch, that removes both _cmp_ and __richcmp__
completely (but perhaps moving the old tests to a new place) and fixes the doc test error that occurs in combination with #11342.
Changed 9 years ago by
Category framework for quotient rings and free algebras; new coercion framework for boolean polynomial rings; conversion from univariate polynomial rings to boolean polynomial rings
comment:101 follow-up: ↓ 102 Changed 9 years ago by
- Status changed from needs_work to needs_review
I have updated the second patch. Since the ticket now depends on #11342, I added a fix for pari ring doctest. Also, I completely removed the __richcmp__
and _cmp_
code from the boolean polynomial rings, since the code is actually not needed anymore (they are unique parents, and thus R==S
is the same as R is S
.
For me, the long tests pass. I hope they do for you as well?
comment:102 in reply to: ↑ 101 Changed 9 years ago by
Replying to SimonKing:
... Also, I completely removed the
__richcmp__
and_cmp_
code...
... but I moved the old doc tests from __richcmp__
to a different place, so that the old tests are preserved.
comment:103 Changed 9 years ago by
The doctests pass for me, too.
When I see commented-out methods lying around then I usually assume that they should be IN but for some reason we can't add the code yet, or that there is a bug in them that ought to be fixed. But right now there are various places where its just old stuff that we should actually get rid of. I would very much appreciate if you could clean that up and remove instead of just commenting out code that is not relevant any more. Realistically, if we don't remove that stuff while refactoring for newer frameworks then it'll forever clutter the source files. For those interested in the history there is always mercurial...
Some comments on the first patch:
- There is also a commented-out
__cmp__
insage/rings/polynomial/infinite_polynomial_ring.py
, I take it that should be removed as well? sage/rings/ring.pyx
l. 356-360 some commented out stuff after return? Same file, there are twocategory()
methods that are just commented out.
Second patch:
sage/algebras/free_algebra_quotient.py
the_coerce_impl
and__contains__
methods are also old stuff that should be snipped now that its no longer used.- The
_mul_(self,y)
method insage/monoids/free_monoid_element.py
guaranteesy
to be aFreeModuleElement
so the commented-out isinstance check should be removed. sage/monoids/monoid.py
again superfluouscategory()
method already commented out.- The commented-out
__reduce__
method insage/rings/polynomial/pbori.pyx
should go away, right? - The added comments in
sage/rings/quotient_ring.py
l. 153-162 aren't very helpful IMHO.
comment:104 Changed 9 years ago by
- Description modified (diff)
- Work issues comparison of BooleanPolynomialRings; one doctest fix deleted
I provided a third patch that (hopefully) addresses Volker's remarks on commented out old code that better ought to be removed. Tests still pass for me, but that's no surprise, since the new patch does not change the code nor the documentation.
Apply trac9138-categories_for_rings.patch trac9138_categories_for_more_rings.patch trac9138_remove_unused_code.patch
comment:105 Changed 9 years ago by
- Reviewers set to Volker Braun
- Status changed from needs_review to positive_review
Thanks for the effort of cleaning up the rings! Positive review.
comment:106 Changed 9 years ago by
- Dependencies changed from sage-4.7, #11268, #11139, #9976, #9944, #11269, #11316, #11342 to #11268 #11139 #9976 #9944 #11269 #11316 #11342
comment:107 Changed 9 years ago by
- Merged in set to sage-4.7.2.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
comment:108 Changed 9 years ago by
- Description modified (diff)
comment:109 Changed 9 years ago by
- Dependencies changed from #11268 #11139 #9976 #9944 #11269 #11316 #11342 to #11316 #11342
- Description modified (diff)
comment:110 follow-up: ↓ 111 Changed 9 years ago by
Simon, concercing #9138 and #11900: I am planning to unmerge #9138 in the sage-4.7.2 release series with the goal of merging them both in sage-4.7.3.alpha0. This is because I feel that, apart from this, the sage-4.7.2 release is essentially finished. Postponing to sage-4.7.3 will give us some more time for testing. What do you think?
comment:111 in reply to: ↑ 110 ; follow-up: ↓ 112 Changed 9 years ago by
Replying to jdemeyer:
Simon, concercing #9138 and #11900: I am planning to unmerge #9138 in the sage-4.7.2 release series with the goal of merging them both in sage-4.7.3.alpha0. This is because I feel that, apart from this, the sage-4.7.2 release is essentially finished. Postponing to sage-4.7.3 will give us some more time for testing. What do you think?
It also depends on the time. The patch from #11900 is invasive, since it makes libsingular polynomial rings use the new coercion model. I think that I'll need until Tuesday or Wednesday to get my patch ready. And then we need to find a reviewer. When is the release supposed to happen?
comment:112 in reply to: ↑ 111 Changed 9 years ago by
- Merged in sage-4.7.2.alpha3 deleted
- Milestone changed from sage-4.7.2 to sage-4.7.3
- Resolution fixed deleted
- Status changed from closed to new
Replying to SimonKing:
When is the release supposed to happen?
Well, I think sage-4.7.2.alpha4 could be finished today or tomorrow and I would rather not merge #11900 after that, especially if the patch is invasive. This is probably not a patch which I want to quickly squeeze in an rc0.
Note that the actual release of sage-4.7.2 could easily be some weeks from now, because we need some time for testing on various platforms, fixing things in an rc, testing again,...
comment:113 Changed 9 years ago by
- Status changed from new to needs_review
comment:114 Changed 9 years ago by
- Status changed from needs_review to positive_review
Still positive review, of course modulo #11900.
comment:115 Changed 9 years ago by
Since the patch bot does not know which patch to apply (hence, complains on all tickets that depend on this one):
Apply 9138_flat.patch
comment:117 follow-up: ↓ 118 Changed 9 years ago by
- Milestone set to sage-4.8
comment:118 in reply to: ↑ 117 Changed 9 years ago by
Replying to AlexanderDreyer:
Since I have two ticket in sage-pending (#11575 and #4539) because of the de-merge: Will this be in 4.8.0?
Depends on #11900. In any case, #9138 and #11900 will be merged together. If #11900 gets a positive review in a reasonable time, then they will be merged. William Stein already mentioned he might review #11900, which would be a very good thing.
comment:119 Changed 9 years ago by
- Dependencies changed from #11316 #11342 to To be merged with #11900
- Milestone changed from sage-4.8 to sage-pending
comment:120 follow-up: ↓ 121 Changed 9 years ago by
- Dependencies changed from To be merged with #11900 to #11761. To be merged with #11900
- Description modified (diff)
Since #11761 is already merged, I was rebasing the patch relative to it. The change is trivial, though: #11761 adds the line
msg = None
into sage/rings/polyomial/pbori.pyx, so that one of my hunks did not apply anymore. I did test that afterwards sage -t sage/rings/polynomial/pbori.pyx
still passes.
I hope that the rebase is trivial enough, so that I can preserve the positive review.
Apply 9138_flat_new_cython.patch
comment:121 in reply to: ↑ 120 Changed 9 years ago by
- Description modified (diff)
Replying to SimonKing:
Since #11761 is already merged, I was rebasing the patch relative to it. The change is trivial, though: #11761 adds the line
msg = Noneinto sage/rings/polyomial/pbori.pyx
My mistake: The first patch from #11761 adds that line, but the reviewer patch removes it. I forgot to apply the reviewer patch.
In other words: Rebasing was not needed! Return to the old patch.
Apply 9138_flat.patch
comment:122 Changed 9 years ago by
- Dependencies changed from #11761. To be merged with #11900 to To be merged with #11900
comment:123 Changed 9 years ago by
A note to the release manager: #11900 just got a positive review by Nicolas Thiéry.
comment:124 Changed 9 years ago by
- Milestone changed from sage-pending to sage-5.0
comment:125 Changed 9 years ago by
- Description modified (diff)
comment:126 Changed 9 years ago by
- Merged in set to sage-5.0.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
This ticket seems to be a duplicate of #8613.