Opened 10 years ago
Closed 9 years ago
#13378 closed defect (fixed)
Do not cache the non-existence of coerce/convert map too often, and do not pretend that there is a conversion where it doesn't make sense at all
Reported by: | SimonKing | Owned by: | robertwb |
---|---|---|---|
Priority: | major | Milestone: | sage-5.7 |
Component: | coercion | Keywords: | coercion conversion object cache |
Cc: | nbruin, jpflori | Merged in: | sage-5.7.beta0 |
Authors: | Simon King | Reviewers: | Nils Bruin |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Sorry for the long ticket title.
About the first part of the title:
sage: P.<x,y> = QQ[] sage: P.is_coercion_cached(x) False sage: P.coerce_map_from(x) sage: P.is_coercion_cached(x) True
Hence, there is a reference to x in the coercion cache for P. OK, by #715 and friends, the reference is weak --- unless x does not allow weak references, in which case the reference will be strong, and x would not be collectable. Hence, a potential memory leak.
About the second part:
sage: ZZ.convert_map_from(1) Conversion map: From: Set of Python objects of To: Integer Ring
or
sage: P.convert_map_from(x) Traceback (most recent call last): ... TypeError: Cannot convert sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular to sage.structure.parent.Parent
I think it is not good that the error occurs. The answer of ZZ.convert_map_from(1)
seems strange, but apparently those things actually occur, namely conversions from the category of sequences.
Attachments (1)
Change History (27)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 follow-ups: ↓ 3 ↓ 4 Changed 10 years ago by
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 5 Changed 10 years ago by
Replying to nbruin:
Are you sure
ZZ.convert_map_from(10)should not raise an error?
No, I am not sure.
Shouldn't the argument be a parent?
Or a type, because we want a coercion (not just a conversion) between Python ints and Sage integers.
This has the potential for getting hairy if you want this to work:
sage: A=AdditiveGroups() sage: A(ZZ) Free commutative group on generators [1]
That's totally separate. AdditiveGroups()
, which doesn't exist yet, is a category and not a parent. It would be desirable, though, to have
sage: ZZ.category() # current behaviour Category of euclidean domains sage: AdditiveGroups()(ZZ).category() # not implemented Category of additive groups
because then
parent(ZZ)
ZZ has no parent, it is a parent. Elements have a parent, but parents have a category.
It actually makes me wonder if parent(ZZ) should even work.
parent(X) currently returns the type of X, if X has no method X.parent()
. This is in order to make int(1)+1
work. I don't think one should slow it down by distinguishing cases like "if X is a parent then parent(X) should raise an error, but if X is anything else then either return X.parent() or type(X)".
Anyway. I tried to introduce a shortcut for Parent.coerce_map_from
, such that None
is returned (without caching) if the argument is neither a CategoryObject
nor a type. Similarly, I introduced a shortcut for Parent.convert_map_from
, but had to be more relaxed, because apparently convert maps also need to exist from sequences (which are SageObject
, but not CategoryObject
).
Result: It nearly worked. There was one segfault in sage.rings.polynomial.infinite_polynomial_element (which I wrote) and one doctest error.
comment:4 in reply to: ↑ 2 Changed 10 years ago by
Replying to nbruin:
I know this all flies in the face of duck typing, but so does the whole category framework.
One could say that the category framework is the opposite of duck typing: In duck typing, you'd test whether certain methods are available for X, and conclude that X belongs to the category of ducks. In the category framework, you would at some point initialise X as an object of the category of ducks, and the category then provides X with methods like "quack()", "swim()", "fly()" --- or, if the category framework can not provide generic methods, it does require that these methods are implemented.
But I actually think that's a strength of the category framework. And note that after category initialisation of X, it would to some extent be possible to determine X.category()
from the methods X provides.
comment:5 in reply to: ↑ 3 Changed 10 years ago by
ZZ has no parent, it is a parent. Elements have a parent, but parents have a category.
Ah yes, keeping that distinction strict is probably a good idea, even if it's not always desirable from a strictly mathematical point of view:
sage: I=ZZ.ideal(3) sage: I(6) TypeError: 'Ideal_pid' object is not callable sage: parent(I) Monoid of ideals of Integer Ring sage: category(I) Category of ring ideals in Integer Ring
so an ideal is an element and not a parent (although mathematically it's also a
a non-unitary ring and at the very least a ZZ-module). What's that category
doing on I
though? Do elements have a parent as well as a category?
sage: V=FreeModule(ZZ,1) sage: W=V.span([3*V.0]) sage: parent(W) <class 'sage.modules.free_module.FreeModule_submodule_pid_with_category'> sage: category(W) Category of modules with basis over Integer Ring
And here we're not getting a parent "... of submodules of V", whatever the ... should be.
Along these lines, by the way:
sage: NumberField(x^2+1,name='i').ideal(3) Fractional ideal (3) sage: QQ.ideal(3) Principal ideal (1) of Rational Field
illustrating the usual schism between algebraists and number theorists.
I don't think I'm really trying to make any point here. I'm just checking to what degree Sage agrees with my mathematical intuition.
comment:6 Changed 10 years ago by
- Status changed from new to needs_review
I am not totally sure if the patch has dependencies, but let's test. With the patch, it is tested whether the input is valid as the domain of a conversion map or a coercion map. There is a difference between the two cases! Namely, Sequences are OK for a conversion map, but not for a coercion map.
If the input S is invalid, P.coerce_map_from(S)
returns None, which is the expected answer if there is no coercion (hence, no error is raised). Because the short-cut is quick enough and in order to not pollute the cache, the answer is not cached.
comment:7 Changed 10 years ago by
- Cc jpflori added
comment:8 follow-up: ↓ 9 Changed 9 years ago by
Could you clarify under what circumstances not having this code pollutes the cache? In particular, it seems that [coerce|convert]_map_from is always called with parent(x) which should always return a Parent or type? Perhaps what I'm asking is what object violate this in their parent() method.
comment:9 in reply to: ↑ 8 Changed 9 years ago by
Replying to robertwb:
Could you clarify under what circumstances not having this code pollutes the cache?
Unfortunately, I did not write in the ticket description what use case made me create this ticket. But probably it was some experimental code on the computation of Ext algebras of basic algebras (i.e., finite-dimensional path algebra quotients).
Anyway. The problem is that in the coercion code one quite typically has
if self.has_coerce_map_from(P): ...
without checking whether P really is a parent or type. And that means trouble, if P happens to be, say, an element (Yes, that did occur! But I don't know where I had originally found it). See the ticket description for an example.
Of course, if P is neither a parent nor a type, then there is no coercion map from P to self. And as you know, the coercion framework would not only cache a coercion map from P to self, but it would also cache the non-existence of a coercion map from P to self.
So, the trouble starts if P runs over many elements that are not weakreffable. For each element P, the coercion framework would store the value None
in self's coercion dictionary. And since the element is not weakreffable, the entry will stay in cache forever, and I think this may even prevent self from being garbage collected.
comment:10 Changed 9 years ago by
PS: If P is not a category object nor a type, it is impossible that there is a coercion map from P to self. Therefore the patch introduces a short cut: self.coerce_map_from(P)
immediately returns None, and does not try to find a coercion map by a costly backtrack algorithm.
comment:11 Changed 9 years ago by
Didn't it happen with integer ? (I think python ints.)
comment:12 Changed 9 years ago by
Some info here http://trac.sagemath.org/sage_trac/ticket/13400#comment:31 but this ticket was opened before so...
comment:13 Changed 9 years ago by
Thank you, Jean-Pierre! Yes, it seems ZZ.ideal(5)
is a real-world-example in which the coercion framework caches the trivial fact that there is no coercion map whose domain is the number 5. In addition, 5 is not weakreffable, and finally the Sage integer 5 is not unique -- but the coercion cache compares its keys by uniqueness and not by equality.
So, doing ZZ.ideal(5)
repeatedly will fill up the coercion cache (post #715, at least) with trivialities.
comment:14 Changed 9 years ago by
Too bad/good, I just tested it with sage-5.6.beta1:
sage: %timeit a = ZZ.ideal(5) 625 loops, best of 3: 147 µs per loop sage: %timeit a = ZZ.ideal(5) 625 loops, best of 3: 144 µs per loop sage: %timeit a = ZZ.ideal(5) 625 loops, best of 3: 147 µs per loop sage: %timeit a = ZZ.ideal(5) 625 loops, best of 3: 148 µs per loop sage: %timeit a = ZZ.ideal(5) 625 loops, best of 3: 146 µs per loop sage: %timeit a = ZZ.ideal(5) 625 loops, best of 3: 147 µs per loop sage: %timeit a = ZZ.ideal(5) 625 loops, best of 3: 148 µs per loop sage: %timeit a = ZZ.has_coerce_map_from(5) 625 loops, best of 3: 82.1 µs per loop sage: %timeit a = ZZ.has_coerce_map_from(5) 625 loops, best of 3: 81.4 µs per loop sage: %timeit a = ZZ.has_coerce_map_from(5) 625 loops, best of 3: 81.3 µs per loop
So, the problem mentioned at #13400 does currently not exist.
We should investigate why it is not a problem.
comment:15 follow-ups: ↓ 16 ↓ 17 Changed 9 years ago by
comment:16 in reply to: ↑ 15 Changed 9 years ago by
comment:17 in reply to: ↑ 15 Changed 9 years ago by
comment:18 Changed 9 years ago by
Straightforward patch that applies (with slight whitespace fuzz for me) and doctests succeed. Plus it solves a real regression. At this pace, Sage 5.7 will have a negative memory footprint! yay.
Positive review.
comment:19 Changed 9 years ago by
- Milestone changed from sage-5.6 to sage-5.7
- Reviewers set to Nils Bruin
- Status changed from needs_review to positive_review
comment:20 follow-up: ↓ 21 Changed 9 years ago by
- Dependencies set to #12313, #12215
comment:21 in reply to: ↑ 20 Changed 9 years ago by
Please don't add dependencies that aren't required for the patches to apply. The fix here can be applied independently of other tickets and makes sense too. It might solve a problem that doesn't become quite as apparent without those other tickets, but that has little to do with its applicability.
We've had problems before where tickets were unnecessarily dequeued due to superfluous dependencies on tickets that turned out to need further work. Also, #12313 already states it's dependent on #12215, so there's no need to repeat that dependence here.
comment:22 follow-up: ↓ 23 Changed 9 years ago by
comment:23 in reply to: ↑ 22 Changed 9 years ago by
comment:24 Changed 9 years ago by
I guess it's a matter of definitions. I consider "merge with" as an equivalence relation (symmetric and transitive). Given that #12313 is to be merged with #13378 and #12215 is to be merged with #12313, the logical conclusion is that these 3 tickets need to be merged together. I didn't use the phrase "merge with" here, only to make the order of merging more clear (first #12215, then #12313, then #13378).
no need to repeat that dependence here.
I find it easier to have the full set of dependencies written down. Consider tickets A, B and C where A and B have positive review, C needs review, A depends on B and B depends on C. If the implicit dependency of A on C is not written down, then it's not obvious to the release manager that A cannot currently be merged.
comment:25 Changed 9 years ago by
- Dependencies #12313, #12215 deleted
comment:26 Changed 9 years ago by
- Merged in set to sage-5.7.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
Are you sure
should not raise an error? Shouldn't the argument be a parent? Something like:
This has the potential for getting hairy if you want this to work:
because then
parent(ZZ)
should be a Parent and it's not. However, this doesn't seem to be the way categories work anyway and it's probably wise to keep a strict separation between sets (parents) and categories. It actually makes me wonder if parent(ZZ) should even work.I know this all flies in the face of duck typing, but so does the whole category framework. I'm afraid that a fully duck typed computer algebra system would about as bad as an untyped one.