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

[simon-king-jena]

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.

CC: @nbruin @jpflori

Component: coercion

Keywords: coercion conversion object cache

Author: Simon King

Reviewer: Nils Bruin

Merged: sage-5.7.beta0

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

[nbruin]

comment:2

Are you sure

ZZ.convert_map_from(10)

should not raise an error? Shouldn't the argument be a parent? Something like:

    if not(isinstance(S,type) or isinstance(type(S),sage.structure.parent.Parent):
        raise TypeError('convert maps only exist from parents')

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]

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.

[simon-king-jena]

comment:3

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.

[simon-king-jena]

comment:4

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.

[nbruin]

comment:5

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.

[simon-king-jena]

Attachment: trac_13378-convert_map_shortcut.patch.gz

Test validity of input before a (failing) construction of coercion

[simon-king-jena]

Author: Simon King

[simon-king-jena]

comment:6

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.

[robertwb]

comment:8

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.

[simon-king-jena]

comment:9

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 category object 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 category object 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.

[simon-king-jena]

comment:10

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.

[jpflori]

comment:11

Didn't it happen with integer ? (I think python ints.)

[jpflori]

comment:12

Some info here #13400 comment:31 but this ticket was opened before so...

[simon-king-jena]

comment:13

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.

[simon-king-jena]

comment:14

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.

[jpflori]

comment:15

Did you apply #12313?
It seems after a really quick read that #13400 is a follow up to #12313 to mitigate a speed regression.

[simon-king-jena]

comment:16

Replying to @jpflori:

Did you apply #12313?

Nope.

It seems after a really quick read that #13400 is a follow up to #12313 to mitigate a speed regression.

OK, what would explain it. Sorry, I will only be able to resume work tomorrow.

[simon-king-jena]

comment:17

Replying to @jpflori:

Did you apply #12313?
It seems after a really quick read that #13400 is a follow up to #12313 to mitigate a speed regression.

OK, I confirm that the problem with ZZ.ideal(5) becoming incrementally slower really exists with #12313. hence, this here is needed.

[nbruin]

comment:18

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.

[nbruin]

Reviewer: Nils Bruin

[jdemeyer]

Dependencies: #12313, #12215

[nbruin]

comment:21

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.

[simon-king-jena]

comment:22

Yes, neither #12313 nor #12215 are dependencies for my patch. They should be merged together, because #13378 avoids a regression that #12313 would introduce, but #13378 makes perfectly sense without #12313.

[jdemeyer]

comment:24

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.

[jdemeyer]

Changed dependencies from #12313, #12215 to none

[jdemeyer]

Merged: sage-5.7.beta0