Opened 18 months ago

Closed 8 months ago

#14711 closed defect (fixed)

Weak references in the coercion graph

Reported by: jpflori Owned by: davidloeffler
Priority: critical Milestone: sage-6.2
Component: number fields Keywords: memleak, number field, QuadraticField
Cc: SimonKing, nbruin, nthiery, aschilling, zabrocki Merged in:
Authors: Simon King, Travis Scrimshaw, Jean-Pierre Flori Reviewers: Nils Bruin, Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: 00b3e2f (Commits) Commit: 00b3e2f3cf90b5e7a339367f8ad4e08e1f0fb3d7
Dependencies: Stopgaps:

Description (last modified by SimonKing)

The following quickly eats up memory:

sage: for D in xrange(2,2**32):
....:     QuadraticField(-D);
....:

(This is with 5.10.rc0)

Problem analysis

The quadratic field is created with a coerce embedding into CLF. At the same
time, this coerce embedding is stored in CLF._coerce_from_hash:

sage: phi = CLF.coerce_map_from(Q)
sage: phi is Q.coerce_embedding()
True
sage: Q in CLF._introspect_coerce()['_coerce_from_hash']
True

The "coerce_from_hash" is a MonoDict, hence, has only a weak reference to the key
(Q, in this case). However, there still is a strong reference from
CLF to the coerce map phi. And phi has a strong reference to its
domain, thus, to Q. Hence, the existence of CLF prevents garbage collection of
Q.

And there is a second chain of strong references from CLF to Q: From CLF to
phi to the parent of phi (i.e., a homset) to the domain Q of this homset.

Suggested solution

We can not turn the reference from CLF to phi into a weak reference, because
then even a strong reference to Q would not prevent phi from garbage
collection. Hence, we need to break the above mentioned reference chains in
two points. In the attached branch, maps generally keep a strong reference to
the codomain (this is important in composite maps and actions), but those used
in the coercion system (and only there!!) will only have a weak
reference to the domain, and they set the cdef ._parent attribute to None
(hence, we also override .parent(), so that it reconstructs the homset if
the weak reference to the domain is still valid).

To preserve the domain()/codomain() interface, I have removed the method
domain() and have replaced it by a cdef public attribute that will either
hold a weak reference (which returns the domain when called, hence, the
interface does not change) or a ConstantFunction (which should actually be
faster to call than a method). Since accessing a cdef attribute is still
faster, the cdef attribute _codomain is kept (since this will always be a
strong reference), but _domain has been removed.

This "weakening of references" is done for the coercions found by
discover_coerce_map_from() stored into _coerce_from_hash. So, this mainly
happens for things done with _coerce_map_from_() and with composite
maps. Similarly for _convert_from_hash.

Weakening is not used on the maps that are explicitly registered by
.register_embedding() and .register_coercion(). This is in order to
preserve the connectivity of the coercion graph. The register_* methods
are only used on selected maps, that are of particular importance for the
backtrack search in discover_coerce_map_from(). These strong
registrations do not propagate: Compositions of strongly registered
coercions found by discover_coerce_map_from() will be weakened.

Since weakened maps should not be used outside of the coercion system, its
string representation shows a warning to replace them by a copy. The attached
branch implements copying of maps in some additional cases.

SchemeMorphism can not inherit from Morphism, because of a bug with
multiple inheritance of a Python class from Cython extension classes. But once
this bug is fixed, we surely want to make SchemeMorphism inherit from
Morphism. This transition is prepared here.

Weakened maps should only be used in the coercion system: A weakened map can become invalid by garbage collection, and the coercion system has the job to remove a map from the coercion cache as soon as it becomes invalid.

Maps outside of the coercion system should be safe against invalidation. Hence, when we take a coerce map, then we should better create a non-weakened copy. The branch also provides copying (and pickling) for all kinds of maps and morphisms (hopefully no map/morphism class went unnoticed).

In any case, the commit messages should give a concise description of what has
been done.

TODO in future tickets

  • Provide a documentation of the use of weak references in coercion, and of different ways of registering coercions, with their different impacts on garbage collecion.
  • Provide a version of .register_coercion() that weakens the coercion map. It would hence have the same effect as returning a map by ._coerce_map_from_(), but of course ._coerce_map_from() could not easily be changed in an interactive session.

Effects on the overall functioning of Sage

It is conceivable that some parts of Sage still suppose implicitly that stuff
cached with UniqueRepresentation is permanently cached, even though the
seemingly permanent cache was not more than a consequence of a memory leak in
the coercion system. With the attached branch, garbage collection of parent
structures will much more often become possible. Hence, code that relied on a
fake-permanent cache would now need to create the same parent repeatedly.

I (Simon) have tested how many additional parent creations occur with the
attached branch when running sage -t --all. The findings are summarised in
comment:107: The number of additional parent creations increased by not more
than 1% for all but two parent classes (both related with tableaux). I also
found that the time to run the tests did not significantly increase.

Jean-Pierre has occasionally stated that some of his computations have been
infeasible with the memory leak in the above example. I hope that his
computations will now succeed.

Attachments (1)

chain.png (45.2 KB) - added by SimonKing 14 months ago.
A reference chain that apparently keeps quadratic fields alive.

Download all attachments as: .zip

Change History (269)

comment:1 Changed 18 months ago by jpflori

In number_field.py:

Quadratic number fields are cached::

I guess they should be only weakly cached.

comment:2 Changed 18 months ago by SimonKing

I think at some point I tried to use UniqueRepresentation for the quadratic number fields (which would be enough to have a weak cache). However, this turned out to open a can of worms in all the number theory and elliptic curve code, if I recall correctly.

comment:3 Changed 18 months ago by jpflori

There is a cache option to the NumberField? constructor, maybe I can live with that, not sure it is a good default behavior though.

Last edited 18 months ago by jpflori (previous) (diff)

comment:4 Changed 18 months ago by jpflori

And trying

QuadraticField(-D, cache=False)

does not solve the problem anyway.

comment:5 Changed 18 months ago by jpflori

After a quick look (and apart from _nf_cache and _cyclo_cache in number_field.py), the culprit might be ComplexDoubleField? doing too much caching of embeddings.

comment:6 follow-up: Changed 18 months ago by jpflori

Indeed, there is a map created at initialization and stored in CDF/RDF's "_convert_from_list" which is a Python list so gives in the end a strong ref to the number field.

comment:7 in reply to: ↑ 6 Changed 18 months ago by SimonKing

Replying to jpflori:

Indeed, there is a map created at initialization and stored in CDF/RDF's "_convert_from_list" which is a Python list so gives in the end a strong ref to the number field.

Ah, yes, that's bad. If I recall correctly, default embeddings are (currently) stored by strong reference via an attribute of the codomain, and if this codomain is immortal, the domain will be immortal as well.

I am afraid that this week I will have no capacity to work on it or do reviews. There might be a chance during the upcoming Sage days in Orsay.

comment:8 Changed 18 months ago by jpflori

In the coercion model, a first step is to remove the addition of the newly created morphism to _convert_from_list, and only add it to _convert_from_hash (except in the register_conversion function).
(Note that this is the current behavior for "coerce" maps, they are only added to _coerce_from_hash, not _coerce_from_list, except within the register_coercion function).

Not sure if these two *_from_list lists have any real use?

But that's not enough anyway (although it removes one eternal strong reference), surely something like what you just posted.

I'll try to attend something like one to three half days of the Sage Days, first guess is Wednesday afternoon, surely another half day on Tuesday.
Hopefully we can tackle this together.

comment:9 Changed 18 months ago by jpflori

See http://trac.sagemath.org/sage_trac/ticket/8335#comment:69 for another incarnation of this problem but with finite fields.

comment:10 Changed 16 months ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:11 Changed 14 months ago by jpflori

Bumping Simon as requested.

comment:12 Changed 14 months ago by SimonKing

I really wonder why the quadratic number field is put into CDF._convert_from_list. Is it perhaps in Parent.convert_map_from()?

Namely, if a look-up in _convert_from_hash fails, then not only the _convert_from_hash gets updated, but also _convert_from_list:

        try:
            return self._convert_from_hash.get(S)
        except KeyError:
            mor = self.discover_convert_map_from(S)
            self._convert_from_list.append(mor)
            self._convert_from_hash.set(S, mor)
            return mor

But why would this be done? Note that _coerce_from_list is not updated when calling Parent.coerce_map_from()!!! So, this looks like an oversight to me. I hope it is, because then we would not need to mess around with yet another weak reference game.

comment:13 Changed 14 months ago by SimonKing

I always thought of _coerce_from_list as a way to store some coercions (namely those explicitly registered during __init__) permanently, but all other coercions should only be weakly cached, in _coerce_from_hash.

And I think _convert_from_list should have exactly the same rôle. I suggest to use _convert_from_list only in Parent.register_conversion() and nowhere else. This would be analogous to how we deal with _coerce_from_list.

comment:14 follow-up: Changed 14 months ago by SimonKing

Unfortunately, this easy change is not enough. I still get

sage: Q = QuadraticField(-3)
sage: import gc
sage: gc.collect()
524
sage: C = Q.__class__.__base__
sage: len([x for x in gc.get_objects() if isinstance(x, C)])
3
sage: del Q
sage: gc.collect()
0
sage: len([x for x in gc.get_objects() if isinstance(x, C)])
3
sage: Q = QuadraticField(-5)
sage: len([x for x in gc.get_objects() if isinstance(x, C)])
4
sage: del Q
sage: gc.collect()
398
sage: len([x for x in gc.get_objects() if isinstance(x, C)])
4

But if I recall correctly, there is further strong caching done for number fields.

comment:15 Changed 14 months ago by jpflori

Sure, there is.
See http://trac.sagemath.org/ticket/14711#comment:4, though I don't really remember if that was enough to disable all the number field caching stuff.

comment:16 in reply to: ↑ 14 ; follow-up: Changed 14 months ago by SimonKing

Replying to SimonKing:

But if I recall correctly, there is further strong caching done for number fields.

I stand corrected. There is sage.rings.number_field.number_field._nf_cache, which is a dictionary. But apparently it does use weak references to the values.

However, I don't see why one shouldn't use a WeakValueDictionary instead.

comment:17 in reply to: ↑ 16 ; follow-up: Changed 14 months ago by jpflori

Replying to SimonKing:

Replying to SimonKing:

But if I recall correctly, there is further strong caching done for number fields.

I stand corrected. There is sage.rings.number_field.number_field._nf_cache, which is a dictionary. But apparently it does use weak references to the values.

However, I don't see why one shouldn't use a WeakValueDictionary instead.

Me neither, unless someone has the habit to play frequently with the same number field but without keeping any of its elements alive between different uses, personally I don't and would not really see the point.

If we switch to a weak value dict, we could also get rid of the cache argument of the constructor then which won't be that useful/sensible anymore.

comment:18 Changed 14 months ago by SimonKing

Clearing this cache doesn't help anyway:

sage: Q = QuadraticField(-3)
sage: import weakref
sage: import gc
sage: gc.collect()
524
sage: C = Q.__class__.__base__
sage: len([x for x in gc.get_objects() if isinstance(x, C)])
3
sage: del Q
sage: gc.collect()
0
sage: len([x for x in gc.get_objects() if isinstance(x, C)])
3
sage: sage.rings.number_field.number_field._nf_cache.clear()
sage: gc.collect()
0
sage: len([x for x in gc.get_objects() if isinstance(x, C)])
3

Even worse, with the change proposed above, one actually has an empty _convert_from_list for CDF, but nevertheless the quadratic number field does not want to die:

sage: CDF._introspect_coerce()
{'_action_hash': <sage.structure.coerce_dict.TripleDict at 0x95264c4>,
 '_action_list': [],
 '_coerce_from_hash': <sage.structure.coerce_dict.MonoDict at 0x952656c>,
 '_coerce_from_list': [],
 '_convert_from_hash': <sage.structure.coerce_dict.MonoDict at 0x9526534>,
 '_convert_from_list': [],
 '_element_init_pass_parent': False,
 '_embedding': None,
 '_initial_action_list': [],
 '_initial_coerce_list': [],
 '_initial_convert_list': []}

Hence, there must be another strong reference somewhere.

comment:19 in reply to: ↑ 17 Changed 14 months ago by SimonKing

Replying to jpflori:

However, I don't see why one shouldn't use a WeakValueDictionary instead.

Me neither, unless someone has the habit to play frequently with the same number field but without keeping any of its elements alive between different uses, personally I don't and would not really see the point.

If we switch to a weak value dict, we could also get rid of the cache argument of the constructor then which won't be that useful/sensible anymore.

I think it isn't sensible anyway. But that's not the point. We first need to find out what keeps the fields alive, when using the branch that I am now about to push. Wait a minute...

comment:20 Changed 14 months ago by SimonKing

  • Branch set to u/SimonKing/ticket/14711
  • Created changed from 06/10/13 02:49:00 to 06/10/13 02:49:00
  • Modified changed from 09/28/13 15:00:48 to 09/28/13 15:00:48

comment:21 follow-up: Changed 14 months ago by SimonKing

Isn't there some tool that is able to show the reference graph? objgraph or so?

Changed 14 months ago by SimonKing

A reference chain that apparently keeps quadratic fields alive.

comment:22 in reply to: ↑ 21 ; follow-up: Changed 14 months ago by jpflori

Replying to SimonKing:

Isn't there some tool that is able to show the reference graph? objgraph or so?

Yes, see http://trac.sagemath.org/ticket/11521#comment:8

comment:23 follow-up: Changed 14 months ago by SimonKing

sage: objgraph.show_chain(objgraph.find_backref_chain(random.choice(objgraph.by_type('NumberField_quadratic_with_category')),inspect.ismodule), filename='chain.png')

shows me the file chain.png in the attachment (of course, subject to some random choice).

What is happening there? If I am not mistaken, objgraph only shows strong references. The quadratic field Q is used as key for the MonoDict which stores conversions into CDF. This monodict has a weak reference to the key Q, but a strong reference to the value, which is a morphism. The morphism of course points to both domain and codomain, and there is your problem.

So, how can we break this chain?

comment:24 in reply to: ↑ 22 Changed 14 months ago by SimonKing

Replying to jpflori:

Replying to SimonKing:

Isn't there some tool that is able to show the reference graph? objgraph or so?

Yes, see http://trac.sagemath.org/ticket/11521#comment:8

Thanks, but google was faster than you :-P

comment:25 in reply to: ↑ 23 ; follow-up: Changed 14 months ago by jpflori

Replying to SimonKing:

sage: objgraph.show_chain(objgraph.find_backref_chain(random.choice(objgraph.by_type('NumberField_quadratic_with_category')),inspect.ismodule), filename='chain.png')

shows me the file chain.png in the attachment (of course, subject to some random choice).

What is happening there? If I am not mistaken, objgraph only shows strong references. The quadratic field Q is used as key for the MonoDict which stores conversions into CDF. This monodict has a weak reference to the key Q, but a strong reference to the value, which is a morphism. The morphism of course points to both domain and codomain, and there is your problem.

So, how can we break this chain?

Weakcaching the domain?
In such a situation it would make sense as in the monodict this domain is already only weakcached, in contrast to the codomain which stays alive anyway.
Didn't we do something similar for Action?

Not sure about the other uses of morphism though, a morphism could then survive when its parent dies.
But whats the point of keeping a morphism alive if you don't use its parent?

comment:26 Changed 14 months ago by SimonKing

I had a similar problem (don't remember the ticket) with actions. I had to create a weak reference to the set that is being acted on. And spontaneously I only see one way to break the reference chain: Have a weak reference to the domain of maps.

And I doubt that this would be any reasonable. Normally, we do want to be able to access the domain when we have a map. So, how can we protect the domain?

comment:27 in reply to: ↑ 25 Changed 14 months ago by SimonKing

Replying to jpflori:

Not sure about the other uses of morphism though, a morphism could then survive when its parent dies.

Isn't the homset containing the morphism keeping a strong reference to domain and codomain, too? Or did I change this somewhere? So, would having a weak reference to the domain actually help?

But whats the point of keeping a morphism alive if you don't use its parent?

Well, imagine a method that returns a morphism. You have constructed the domain and the codomain inside of the method. It would be awkward to return domain, codomain, morphism instead of only one item, morphism. But if the morphism only keeps a weak reference to the domain, and if you only return the morphism, then the domain might be garbage collected during return, and this would make the morphism useless.

comment:28 follow-up: Changed 14 months ago by nbruin

Yes, we have run into these things repeatedly. We're storing maps as _coerce_from and _convert_from on the codomain because for those maps, the codomain needs the domain to exist anyway (a polynomial ring will be holding a reference to its coefficient ring, a quotient ring needs the ring it was quotiented from).

This goes very wrong when we have maps into LARGER rings that exist independently. Indeed, as soon as you're coercing/converting/embedding a number field into Qbar, into SR, or into CC, your ring has been damned with virtually eternal life (SR is one ring to forever in the darkness bind them...).

A nasty solution is to ALSO have _coerce_to and _convert_to, store each map in only one, and in the discovery process look on both the domain and the codomain. One can then choose whether the map should be cached on the domain or the codomain (depending on which one is expected to have the longer natural line). We'd end up mostly using the _*_from variants as we have now, but for things like QQbar etc. we'd choose the other one.

This might reduce the number of times where we'll get a leak this way, but I suspect that it'll be possible to get strong reference cycles via this process nonetheless.

comment:29 Changed 14 months ago by jpflori

Replying to SimonKing:

Replying to jpflori:

Not sure about the other uses of morphism though, a morphism could then survive when its parent dies.

Isn't the homset containing the morphism keeping a strong reference to domain and codomain, too? Or did I change this somewhere? So, would having a weak reference to the domain actually help?

Don't know, we'll have to check.

But whats the point of keeping a morphism alive if you don't use its parent?

Well, imagine a method that returns a morphism. You have constructed the domain and the codomain inside of the method. It would be awkward to return domain, codomain, morphism instead of only one item, morphism. But if the morphism only keeps a weak reference to the domain, and if you only return the morphism, then the domain might be garbage collected during return, and this would make the morphism useless.

Yeah I got that if you don't store an outside refernce to the domain, then it will get gc'ed.

But I don't really see what kind of method would return just such a morphism, internally constructing the domain without you providing it (or having other references ot it somehow), do you have actual examples in mind?

Anyway, another solution would be to add an option to Action/Morphism? and so on to only use weakref optionally.

comment:30 in reply to: ↑ 28 Changed 14 months ago by jpflori

Replying to nbruin:

Yes, we have run into these things repeatedly. We're storing maps as _coerce_from and _convert_from on the codomain because for those maps, the codomain needs the domain to exist anyway (a polynomial ring will be holding a reference to its coefficient ring, a quotient ring needs the ring it was quotiented from).

This goes very wrong when we have maps into LARGER rings that exist independently. Indeed, as soon as you're coercing/converting/embedding a number field into Qbar, into SR, or into CC, your ring has been damned with virtually eternal life (SR is one ring to forever in the darkness bind them...).

I think weak caching the domain should solve this problem (unless some homset as Simon mentioned comes into play).

comment:31 follow-up: Changed 14 months ago by SimonKing

Last idea, before I go to sleep:

We could

  • only have a weak reference to the values (here: a morphism, say, phi) of the MonoDict in _convert_from_hash (here: CDF._convert_from_hash),
  • keep a strong reference from the morphism to the domain (here: from Q to phi)
  • add a strong reference from the domain (Q) to the morphism (phi).

Would this save us?

We want that a strong reference [edit: I mean an external strong reference] to Q keeps phi alive. Well, it does, since we added a strong reference Q->phi.

We want that phi can be collected, if no external strong reference to Q [edit: or to phi] exists. Well, there only are weak references from the MonoDict to phi and to Q. Hence, the only strong reference to phi comes from Q, and the only strong reference to Q comes from phi. This is a circle, that Python's cyclic garbage collector can deal with. Both Q and phi would be collected, and removed from the MonoDict.

[edit:] And finally: An external strong reference to phi will keep Q alive, since we have a strong reference from phi to its domain Q.

I find this solution by far more appealing than introducing a weak reference to the domain of a map. Good night.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:32 in reply to: ↑ 31 ; follow-up: Changed 14 months ago by jpflori

Replying to SimonKing:

Last idea, before I go to sleep:

We could

  • only have a weak reference to the values (here: a morphism, say, phi) of the MonoDict in _convert_from_hash (here: CDF._convert_from_hash),
  • keep a strong reference from the morphism to the domain (here: from Q to phi)
  • add a strong reference from the domain (Q) to the morphism (phi).

Would this save us?

We want that a strong reference [edit: I mean an external strong reference] to Q keeps phi alive. Well, it does, since we added a strong reference Q->phi.

We want that phi can be collected, if no external strong reference to Q [edit: or to phi] exists. Well, there only are weak references from the MonoDict to phi and to Q. Hence, the only strong reference to phi comes from Q, and the only strong reference to Q comes from phi. This is a circle, that Python's cyclic garbage collector can deal with. Both Q and phi would be collected, and removed from the MonoDict.

[edit:] And finally: An external strong reference to phi will keep Q alive, since we have a strong reference from phi to its domain Q.

That would suit as well I guess and sounds kind of like the coerce_to solution nils suggested.
If we go this way, I guess we should do the same for actions.

comment:33 in reply to: ↑ 32 Changed 14 months ago by nbruin

Replying to jpflori:

That would suit as well I guess and sounds kind of like the coerce_to solution nils suggested.
If we go this way, I guess we should do the same for actions.

Yes, it strikes me as similar. In fact, because when you're trying to figure out a coercion or conversion you usually have both the domain and the codomain already, there's no need for weak references.

See also http://trac.sagemath.org/ticket/11521#comment:152

Note that a map and a homset really do need strong references to domain and codomain, because they need both to stay sane. If you want maps with weak references to one or the other, you'd have to make a special class specifically for use in the coercion system. Note that such maps would often essentially reference elements (at least in the codomain), so a strong reference to to codomain is probably unavoidable in almost all cases.

Once a coercion or a conversion is discovered, how do we decide where to cache it? Do domain and codomain need a ranking and store the map on the domain only if it's ranks strictly higher? We'd have
ZZ, QQ, SR of rank 0. Different float rings rank 1, polynomial rings of rank (base) + 1 etc. something like that? Perhaps the coercion "construction" hierarchy is of use for this?

comment:34 Changed 14 months ago by SimonKing

When we would do as I have suggested (strong reference from Q to phi, weak reference from CDF to phi) then we have of course the problem what happens if Q is immortal and we want to get rid of CDF, because then we have a strong reference from phi to the codomain CDF, keeping CDF alive.

So, in both approaches we are discussing here, sooner or later have to decide: Do we want that the domain of a coercion/conversion can be removed even if the codomain survives? Or do we want that the codomain of a coercion/conversion can be removed even if the domain survives?

Isn't there any way to achieve both at the same time?

comment:35 follow-up: Changed 14 months ago by SimonKing

PS: It might be doable to guess from the construction of an object whether it will be immortal or not, and then decide whether we store the coercion in the domain or in the codomain. But note that this may slow down the whole coercion system, because when searching a coercion it would always be needed to look both at the domain and the codomain: Two searches where we currently have only one.

And when the construction shall guide us what to do, then we always need to compute the construction first---and actually not all parents are currently provided with a construction.

comment:36 in reply to: ↑ 35 Changed 14 months ago by SimonKing

Replying to SimonKing:

Two searches where we currently have only one.

Hmm. This may be not the case, actually. We could continue to only do the search in codomain._coerce_from_hash, which would still be a MonoDict, hence, with weak references to the key (i.e., to the domain). So, the search would only happen there. But then, depending on the immortality of the domain resp. the codomain, what we find as value of codomain._coerce_from_hash will be a strong respectively a weak reference to a map, and then we would have no reference respectively a strong reference back from the domain to the map.

But still, I fear this will slow down things.

comment:37 Changed 14 months ago by SimonKing

How about that?

Let D, C be domain and codomain of a coerce map phi. Let us store strong references from MonoDicts domain._coerce_into_hash and codomain._coerce_from_hash. Let us create a method of phi._make_weak_references() that turns the default strong references from phi to its domain and codomain into weak references.

That's to say: We could still use the current backtracking algorithm to detect coercions (this is since we keep having codomain._coerce_from_hash). We would call phi._make_weak_references() only when registering the coercion. So, I guess the additional overhead would be small, and the default behaviour of maps would still be safe.

Would this solve our problem? I think so. Assume that there are no external strong references to C, but there are external strong references to D. Hence, there is a strong reference from D to phi, but phi (because we have called phi._make_weak_references() only has a weak reference to C. Hence, C can be deallocated, and this would trigger the callback for D._coerce_into_hash[C]=phi.

In other words, phi would be removed from the MonoDict assigned to D. As a result, C and phi can be collected, but D will survive (because of the external strong reference).

And you may note that this picture is completely symmetric. Hence, an external strong reference to C would not be enough to keep phi and D alive.

Isn't this exactly what we want?

comment:38 follow-up: Changed 14 months ago by SimonKing

I think we'd need to do more: phi has a strong reference to the homset phi.parent(), which also has strong references to both D and C.

Perhaps we could make it so that homsets always only keep weak references to domain and codomain, whereas maps (such as phi) by default keep strong references to domain and codomain, but have a method 'phi._make_references_weak()` that makes them have weak references to domain and codomain?

Rationale: I hope it is very unlikely that we have a homset, but don't created an element of it and don't keep references to domain or codomain. Hence, I hope it is acceptable that in such situation the domain and codomain of the homset may be garbage collected. But if we have a morphism, then this morphism will keep the domain and codomain alive, and thus weak references of the homset don't hurt. And the exception is: If this morphism is used for coercion, then we can call _make_references_weak() on it, so that domain and/or codomain need an external reference to prevent garbage collection.

Hmm. I guess it isn't very clear yet. Perhaps it is best to try and provide a proof of concept, sometimes in the next days.

comment:39 in reply to: ↑ 38 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

Hmm. I guess it isn't very clear yet. Perhaps it is best to try and provide a proof of concept, sometimes in the next days.

I'm pretty sure you'll find it to be incredibly painful. A homset and a homomorphism are only healthy if their domains and codomains exist. They should therefore have strong references to them. The protocols required to correctly handle homsets and homomorphisms without those strong references will be very painful. What's worse, those homomorphisms will often still work correctly if the proper protocol isn't followed, because domain and codomain will usually not be very quickly reclaimed by GC. So you'll very likely have very hard to find bugs.

Maps in the coercion system are a little different: We'd only be looking up the map if we HAVE domain and codomain (in fact, the lookup would be keyed on them). One way of dealing with this is not to have full-blown maps as mathematical objects, but just have a "premap" ... the minimal data to define the coercion map. I think it's a mistake to allow our full-blown maps to also stand in for such "premaps". Note that a premap will usually need strong references to the codomain anyway. Most of the time, a premap is just a sequence of images of the generators of the domain.

Certainly, "premaps" don't need to have a reference to a homset.

I think the easier solution is to devise a strategy to store coercions on either domain or codomain.
Any complication in lookup from these could be alleviated by having a global, fully weak, triple dict keyed on domain and codomain, containing the coercion map (weakly referenced). That way, it's not important whether the coercion is stored in _coerce_from or in _coerce_to. Those list would only be responsible for keeping a strong reference. The lookup could happen in a global, fully weak, associative lookup. I think you ended up with a similar structure around actions or homsets somewhere.

The main thing this gets us is flexibility in WHO is keeping the strong refs to our coercion maps (usually either domain or codomain; are there other possibilities?). I'm not sure it fully solves our problems. It does if we can make a "mortality hierarchy", and store the ref on the more mortal one (preferring the codomain in case of a draw).

comment:40 in reply to: ↑ 39 ; follow-up: Changed 14 months ago by SimonKing

Replying to nbruin:

Replying to SimonKing:

Hmm. I guess it isn't very clear yet. Perhaps it is best to try and provide a proof of concept, sometimes in the next days.

I'm pretty sure you'll find it to be incredibly painful.

Not at all. Admittedly I had no time yet to run all tests. But Sage starts and the memleak is fixed. I'll update the branch shortly.

A homset and a homomorphism are only healthy if their domains and codomains exist.

Correct.

They should therefore have strong references to them.

No. If there is no external strong reference to domain/codomain and no element of the homset exists that is stored outside of the coercion model, then I think there is no reason to keep the homset valid. The domain/codomain together with the coerce maps and together with the homset should be garbage collected.

The protocols required to correctly handle homsets and homomorphisms without those strong references will be very painful.

No idea what you are talking about here. "Protocol" in the sense of "interface"? Well, the interface will be the same. There is a callable attribute ".domain()" of homsets and of maps. Currently, these callable attributes are methods. With my patch, they are either ConstantFunction or weakref.ref. At least for maps, there will be methods _make_weak_references() and _make_strong_references() to choose between the two.

What's worse, those homomorphisms will often still work correctly if the proper protocol isn't followed, because domain and codomain will usually not be very quickly reclaimed by GC.

If you have a homomorphism outside of the coercion framework, then the domain and codomain will be kept alive, unless you call _make_weak_references() on the map (which the user shouldn't do---it is an underscore method after all).

Otherwise, if you have no external strong reference to, say, the domain of a coerce map, then there will be no supported way to access the coerce map (namely, for codomain.coerce_map_from(domain) you'd need a reference to the domain). So, I don't think there is a problem here.

Maps in the coercion system are a little different: We'd only be looking up the map if we HAVE domain and codomain

Exactly. And all other maps will keep the domain and codomain alive and will thus keep the homset valid.

Any complication in lookup from these could be alleviated by having a global, fully weak, triple dict keyed on domain and codomain, containing the coercion map (weakly referenced).

Problem: If this is a global object, then you will have a strong reference to it, hence, you will have a strong reference to all the coerce maps, and thus (at least when you have strong references to domain and codomain) all parents that are ever involved in a coercion or conversion either as domain or codomain will be immortal.

That way, it's not important whether the coercion is stored in _coerce_from or in _coerce_to.

By the way, in the branch that I am preparing there is still only _coerce_from. As it has turned out, a _coerce_to is not needed.

I am confident that my branch will have the following property: If a map from P1 to P2 is cached in the coercion model, and you don't keep a strong external reference to P1 (or P2), then P1 (or P2) can be garbage collected. But if you keep a strong external reference to both P1 and P2, then the map will stay in the cache.

comment:41 in reply to: ↑ 40 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

The protocols required to correctly handle homsets and homomorphisms without those strong references will be very painful.

No idea what you are talking about here. "Protocol" in the sense of "interface"?

Protocol as in "how to use the interface properly". In this case the protocol would include: keep strong references to domain and codomain for as long as you're keeping a reference to the the map.

If you have a homomorphism outside of the coercion framework, then the domain and codomain will be kept alive, unless you call _make_weak_references() on the map (which the user shouldn't do---it is an underscore method after all).

The problem is, homomorphisms constructed by the coercion framework might leak into user space:

sage: QQ.coerce_map_from(ZZ)
Natural morphism:
  From: Integer Ring
  To:   Rational Field

Are you always going to return a copy of the morphism held in the coercion framework with strong references to domain and codomain, and mandate that the only supported interface is accessing the coercion maps via that interface? You'd better check the current code base for compliance with that specification. Especially: do all maps know how to create a copy of themselves? Do map compositions know how to recurse into their components for making copies and ensure that domain/codomain references are made strong again?

Problem: If this is a global object, then you will have a strong reference to it, hence, you will have a strong reference to all the coerce maps, and thus (at least when you have strong references to domain and codomain) all parents that are ever involved in a coercion or conversion either as domain or codomain will be immortal.

No, I said "fully weak", i.e., also with weak values. You already have one of those global associative caches in the Homset constructor. (in fact, that's the only use and the reason why TripleDict grew a weakvalues=true parameter)

By the way, in the branch that I am preparing there is still only _coerce_from. As it has turned out, a _coerce_to is not needed.

Indeed, if you can make you idea work. But I think it needs some pretty invasive changes in how one can extract and use maps found by the coercion framework.

Your idea would mean we'd have multiple versions of maps around, some with weak references (which shouldn't leave the coercion framework) and some with strong references. Which should be equal? which should be identical?

Compare with now:

sage: a1=QQ.coerce_map_from(ZZ)
sage: a2=QQ.coerce_map_from(ZZ)
sage: b=sage.rings.rational.Z_to_Q()
sage: c=sage.rings.rational.Z_to_Q()
sage: [a1 is a2, a1 is b, b is c]
[True, False, False]
sage: [a1 == a2, a1 == b, b == c]
[True, False, False]

Your approach will have to break a1 is a2. How will you deal with equality?

I think getting some of these references weak within the coercion framework would be great. It should be a little more robust that a _coerce_to and _coerce_from solution (except for maps that internally end up keeping a strong reference to their domain; how do map compositions fare in this respect?).

comment:42 in reply to: ↑ 41 ; follow-up: Changed 14 months ago by SimonKing

Hi Nils,

Replying to nbruin:

Replying to SimonKing:

No idea what you are talking about here. "Protocol" in the sense of "interface"?

Protocol as in "how to use the interface properly". In this case the protocol would include: keep strong references to domain and codomain for as long as you're keeping a reference to the the map.

You mean: Of the homset. If you create a map, then it's fine.

Admittedly, I am not totally happy with letting Hom be with weak references from the very beginning. What I could imagine, though: Let it be strong in the beginning; but change Homset.__call__ so that it first replaces the strong by a weak reference in the homset. Namely, maps (i.e., the things returned by __call__!) will then have the burden to carry strong references to domain and codomain.

The problem is, homomorphisms constructed by the coercion framework might leak into user space:

sage: QQ.coerce_map_from(ZZ)
Natural morphism:
  From: Integer Ring
  To:   Rational Field

Correct.

What about renaming coerce_map_from() into _cm_coerce_map_from()? It would not be part of the official interface (since it is an underscore method) and hence is entitled to return something that only makes sense when used within the coercion model. We could then define

def coerce_map_from(self, P):
    phi = self._cm_coerce_map_from(P)
    if phi is None:
        return
    phi._make_strong_references()
    return phi

returning a map with strengthened references (note: I am not speaking about a copy). So, this would be the "official" way to get a "safe" map from an unsafe internally used coercion.

No, I said "fully weak", i.e., also with weak values. You already have one of those global associative caches in the Homset constructor.

I see. Hmmm. There is one important difference to Homsets: If you only store weak references to the coerce maps, then what would prevent them from being immediately garbage collected? In the case of Homsets, it is the elements that prevents them from being garbage collected. Hence, having a fully weak cache does make sense.

Indeed, if you can make you idea work. But I think it needs some pretty invasive changes in how one can extract and use maps found by the coercion framework.

I don't think so, if one separates the internally used methods from the interface.

Your idea would mean we'd have multiple versions of maps around, some with weak references (which shouldn't leave the coercion framework) and some with strong references. Which should be equal? which should be identical?

Again, I am not talking about "returning copies".

comment:43 in reply to: ↑ 42 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

Hi Nils,

Replying to nbruin:

Replying to SimonKing:

No idea what you are talking about here. "Protocol" in the sense of "interface"?

Protocol as in "how to use the interface properly". In this case the protocol would include: keep strong references to domain and codomain for as long as you're keeping a reference to the the map.

You mean: Of the homset. If you create a map, then it's fine.

No, also for the map, if I understand your proposal correctly. If I keep a reference to just a map, I'd expect it to keep the domain and codomain alive as well (i.e., the semantics of a map with _make_strong_references; the only type of map that should be allowed to escape into the wild).

Admittedly, I am not totally happy with letting Hom be with weak references from the very beginning. What I could imagine, though: Let it be strong in the beginning; but change Homset.__call__ so that it first replaces the strong by a weak reference in the homset. Namely, maps (i.e., the things returned by __call__!) will then have the burden to carry strong references to domain and codomain.

But that responsibility would fall back onto the homset once the last reference to a map has been lost. You wouldn't know when that would happen. Do the maps in the coercion framework really need a Homset? Perhaps you can just leave that blank if you have _use_weak_references.

What about renaming coerce_map_from() into _cm_coerce_map_from()? It would not be part of the official interface (since it is an underscore method) and hence is entitled to return something that only makes sense when used within the coercion model. We could then define

def coerce_map_from(self, P):
    phi = self._cm_coerce_map_from(P)
    if phi is None:
        return
    phi._make_strong_references()
    return phi

returning a map with strengthened references (note: I am not speaking about a copy). So, this would be the "official" way to get a "safe" map from an unsafe internally used coercion.

That leaves you with a memory leak again: After asking for a coerce_map, the map stored in the coercion framework now has strong references again, even after I discard my requested coerce_map.

No, I said "fully weak", i.e., also with weak values. You already have one of those global associative caches in the Homset constructor.

I see. Hmmm. There is one important difference to Homsets: If you only store weak references to the coerce maps, then what would prevent them from being immediately garbage collected? In the case of Homsets, it is the elements that prevents them from being garbage collected. Hence, having a fully weak cache does make sense.

Yes, that's why one still needs the strong references in _coerce_from or _coerce_to. It just unlinks the responsibility of keeping the map alive from the ability to find it, given domain and codomain. If you can make your idea work, you won't need it. But I'll keep my sceptical position for now (either justified or for the sake of constructive argument, we'll see).

Again, I am not talking about "returning copies".

And that's where you'll get big trouble from. If you're going to return strong versions of maps stored in the coercion system, you have to make those copies. Otherwise, there's nothing that tracks the lifetimes properly.

comment:44 in reply to: ↑ 43 Changed 14 months ago by SimonKing

Replying to nbruin:

But that responsibility would fall back onto the homset once the last reference to a map has been lost. You wouldn't know when that would happen. Do the maps in the coercion framework really need a Homset? Perhaps you can just leave that blank if you have _use_weak_references.

This could actually be a good idea that would allow to preserve the strong references of Homsets to domain and codomain. I originally hesitated to have Map._parent=None for maps that are in the coercion framework, because maps are elements and thus should have parents. But the parent could easily be reconstructed, provided that domain and codomain of the coerce map are still alive. And it will be alive if we access the map, because accessing it only works if we have the domain and codomain in our hands.

comment:45 follow-up: Changed 14 months ago by SimonKing

With the following done, Sage starts:

  • Having the usual strong references of homsets to domain and codomain.
  • Having maps by default as "usual" elements with strong references to domain and codomain.
  • self._parent=None for maps registered by the coercion model, overriding the self.parent() method by something that tries to reconstruct the parent from domain and codomain.

Moreover, it fixes the memleak:

sage: Q = QuadraticField(-5)
sage: C = Q.__class__.__base__
sage: import gc
sage: _ = gc.collect()
sage: numberQuadFields = len([x for x in gc.get_objects() if isinstance(x, C)])
sage: del Q
sage: _ = gc.collect()
sage: numberQuadFields == len([x for x in gc.get_objects() if isinstance(x, C)]) + 1
True

Granted, it is possible to get a map in an invalid state (at least with the not-yet-posted version of my branch):

sage: Q = QuadraticField(-5)
sage: phi = CDF.convert_map_from(Q)
sage: del Q
sage: _ = gc.collect()
sage: phi.parent()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-14-5708ddd58791> in <module>()
----> 1 phi.parent()

/home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/categories/map.so in sage.categories.map.Map.parent (sage/categories/map.c:3023)()

ValueError: This map is in an invalid state, domain or codomain have been garbage collected

But the question is: Is there any way to make Q garbage collectable in the first example but not collectable in the second example?

comment:46 in reply to: ↑ 45 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

sage: Q = QuadraticField(-5)
sage: phi = CDF.convert_map_from(Q)
sage: del Q
sage: _ = gc.collect()
sage: phi.parent()
ValueError: This map is in an invalid state, domain or codomain have been garbage collected

But the question is: Is there any way to make Q garbage collectable in the first example but not collectable in the second example?

Yes of course. CDF.convert_map_from(Q) should return a copy equivalent to phi with strong references to domain and codomain. If the original phi is a composition of "weak" (coercion generated) maps then all the components of the returned phi should also be strengthened copies.

Note that the full story should be

sage: Q = QuadraticField(-5)
sage: phi = CDF.convert_map_from(Q)
sage: del Q
sage: _ = gc.collect() #Q is kept alive due to phi
sage: phi.parent() is not None
True
sage: del phi
sage: _ = gc.collect() #now Q gets collected.

It means that getting safe maps out of the coercion framework is relatively expensive business, and it means that maps dwelling there must have some concept of how to make a copy of themselves. It can be fairly high level: we just need a container that can have fresh _domain,_codomain,_parent slots to reference strongly what's only reffed weakly (or not at all) on the maps internal to coercion.

I hope this can all happen without incurring too much performance loss: the weak reference checking and Homspace reconstruction could end up being slow(ish) in the coercion framework if those operations are done too often.

comment:47 Changed 14 months ago by jpflori

Just a random thought about the coerce_to construction using strong references: we really have to make sure to pay attention to things like coercions from ZZ to GF(p) which could make finite fields live forever (once again).

Last edited 14 months ago by jpflori (previous) (diff)

comment:48 Changed 14 months ago by SimonKing

Concerning a generic copy method for maps: It is of course possible to provide a generic method that takes care of all data in the __dict__ and all slots common to maps (namels: those of Element plus domain and codomain). Everything else should be done in the subclasses.

The code I am experimenting with results in some crashes, I am afraid. Hopefully I will be able to fix this.

comment:49 Changed 14 months ago by SimonKing

Example of a crash:

sage: s = ModularSymbols(11).2.modular_symbol_rep()[0][1]; s                                        
{-1/9, 0}
sage: loads(dumps(s)) == s
True
sage: s = ModularSymbols(11).2.modular_symbol_rep()[0][1]
<BOOOM>

comment:50 Changed 14 months ago by SimonKing

Ooops! That's odd:

sage: s = ModularSymbols(11).2.modular_symbol_rep()[0][1]
sage: f, (a,b,c), D = s.__reduce__()
sage: s = ModularSymbols(11).2.modular_symbol_rep()[0][1]
sage: D['_ModularSymbol__space']
Manin Symbol List of weight 2 for Gamma0(11)
sage: s = ModularSymbols(11).2.modular_symbol_rep()[0][1]
<BOOOM>

So, printing the "Manin Symbol List" is enough to trigger the crash. Very bad.

comment:51 Changed 14 months ago by SimonKing

Sorry, reduction is not to blame. Doing a garbage collection after the first line and then repeating the first line reproduces the crash. Hence, some parent is not correctly kept alive. Anyway, you can't see it, since I didn't post the code yet...

comment:52 in reply to: ↑ 46 ; follow-up: Changed 14 months ago by SimonKing

Replying to nbruin:

Yes of course. CDF.convert_map_from(Q) should return a copy equivalent to phi with strong references to domain and codomain. If the original phi is a composition of "weak" (coercion generated) maps then all the components of the returned phi should also be strengthened copies.

In other words, you do think that we should distinguish between underscore methods that are used internally in the coercion system and just return the maps, and an "official" interface that returns strong copies. Do I understand correctly?

Concerning compositions, I agree that the parent in the middle should be kept alive by the composed map (even if this map is in the coercion system, hence, domain and codomain are only weakly referenced): If the composed map is kept in memory, then we need to be able to apply the composition, and hence the "man in the middle" needs to be available.

comment:53 in reply to: ↑ 52 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

In other words, you do think that we should distinguish between underscore methods that are used internally in the coercion system and just return the maps, and an "official" interface that returns strong copies. Do I understand correctly?

Yes, with your approach the maps stored and used in the internals of the coercion systems are not able to stay healthy on their own. They can only survive within a controlled environment. So you cannot let those maps escape into the wild (the royal society for prevention of cruelty to maps would probably have you arrested). I don't see another solution than making a version that is better prepared for the outside world.

Concerning compositions, I agree that the parent in the middle should be kept alive by the composed map (even if this map is in the coercion system, hence, domain and codomain are only weakly referenced): If the composed map is kept in memory, then we need to be able to apply the composition, and hence the "man in the middle" needs to be available.

Yes, you are correct. You might want to check if compositions do tend to occur in the coercion system. They would be quite painful to work with. The natural way of constructing them would be to have a containing map type with _domain,_codomain,_parent set appropriately, together with a sequence of maps. Those maps would normally be normal, healthy maps with their own strong references to their domains and codomains: a composition would hence carry internally a strong reference to both its domain and codomain (due to the first and last map in the sequence).

The generic way of making a "weak" version of a map would still lead to a map that (internally) keeps strong references to domain and codomain. You'd have to make a custom way of weakening this map. Would you weaken the first and last map in the sequence? Then for a composition of two maps, you'd have to separately keep a reference to the middle (co)domain. Or would you have half-weakened maps as well, that only have a weaked domain or codomain?

That makes me realize a further complication: the copying probably has to happen both ways.
Before you prepare a map to become part of the coercion system, you'd have to make sure that the map you're holding is not referenced by anyone outside. Thus, you'd have to make sure that either the origin of the map is guaranteed (it's not a map that is referenced elsewhere--I think this will be impossible to verify in practice, since users can register arbitrary maps as coercions) or you have to make a copy before weakening it (if weakening is an in-place operation, as you proposed above), further upping the cost of coercion discovery. Otherwise, registering a coercion might have the side-effect of weakening a map that someone else is holding already.

(these are the kind of snowballing complications I was afraid of by making a separate type of map suitable for the coercion system)

comment:54 in reply to: ↑ 53 ; follow-ups: Changed 14 months ago by SimonKing

Replying to nbruin:

Concerning compositions, I agree that the parent in the middle should be kept alive by the composed map (even if this map is in the coercion system, hence, domain and codomain are only weakly referenced): If the composed map is kept in memory, then we need to be able to apply the composition, and hence the "man in the middle" needs to be available.

Yes, you are correct. You might want to check if compositions do tend to occur in the coercion system.

They do frequently occur, because coercions are found by some kind of backtracking algorithm. But, somehow surprisingly, I don't got the impression that the crashes I am observing come from this.

Anyway, I agree that one should have a strong reference in the middle.

The generic way of making a "weak" version of a map would still lead to a map that (internally) keeps strong references to domain and codomain.

No. You would have weak reference to the domain and codomain, but a strong reference to the middle. A FormalCompositeMap, by the way, stores two maps __first and __second, and in my current experimental code I simply make __first.codomain a constant function (if it isn't already).

It could in principle mean that the composite map gets deallocated, while __first stays somewhere else in the coercion system, and now keeps a parent (namely the middle one) alive that may be collectable. I'll worry about it later...

That makes me realize a further complication: the copying probably has to happen both ways.
Before you prepare a map to become part of the coercion system, you'd have to make sure that the map you're holding is not referenced by anyone outside. Thus, you'd have to make sure that either the origin of the map is guaranteed (it's not a map that is referenced elsewhere--I think this will be impossible to verify in practice, since users can register arbitrary maps as coercions)

I think the (unwritten, I am afraid) contract is that register_coercion() is only called in __init__. So, perhaps it should rather be _register_coercion(), to remove it from the user interface.

comment:55 in reply to: ↑ 54 Changed 14 months ago by nbruin

Replying to SimonKing:

I think the (unwritten, I am afraid) contract is that register_coercion() is only called in __init__. So, perhaps it should rather be _register_coercion(), to remove it from the user interface.

Absolutely not! I think it's a very important feature that coercions can be discovered "lazily", i.e., be registered after the fact. It also means (but this is just a fact of life) that, while parents are supposed to be immutable, their relations in the (global state)! coercion graph can evolve over time.
You could of course have a _register_coercion for internal use that mandates being passed a map with the promise no-one else will keep a reference to that map, but I'm pretty sure we have to keep an advertised register_coercion. You could ask sage-devel, of course.

At some point there was even an idea to have a context manager to temporarily modify the coercion graph:

K=QuadraticField(3)
with coercion(K.real_embeddings()[0]):
    print 1+K.0

leading to -0.732050807568877 (assuming the first embedding is the negative one).
For basic computations these things are not so essential, but by the time you're a couple levels deep, e.g., you want to compute the archimedean period matrices of some abelian variety defined over a number field, letting the coercion framework to the required conversions might be the only quick way to actually get your data in the right ring. I think we don't want to take away that possibility.

comment:56 in reply to: ↑ 54 Changed 14 months ago by nbruin

Replying to SimonKing:

It could in principle mean that the composite map gets deallocated, while __first stays somewhere else in the coercion system, and now keeps a parent (namely the middle one) alive that may be collectable. I'll worry about it later...

Hm. Any time you have different versions of the same map that may diverge in the strength with which they refer to one of their domain, codomain, parent, etc., you'll need to make a copy to accommodate the divergence in strength. So it probably makes sense to only have two levels: either domain,codomain, and parent are referenced strongly or domain and codomain are referenced weakly (and probably there's no reference to parent at all).

That means that "weak" map compositions in the coercion system need to have a strong reference to the middle domain. That shouldn't be too bad.

Apart from possible efficiency problems, I think this idea can be made to work. The main programming penalty is the added burden on writing new map classes: maps must be able to generate a copy of themselves. You could make this optional: maps unable to copy themselves would be just stored as-is in the coercion framework, with all the memory leak consequences this has. If it's cheap to figure out if maps are weak and/or are capable of generating a weak/strong version of themselves, we could just accommodate both: If a "weakened" map arrives into the coercion framework it can just be used as-is. If a normal map arrives, we see if it can be weakened. If so, we make a weakened copy and store that. Otherwise the map is used as-is.

If a map is about to be passed out of the coercion framework, we check if it's weakened. If not, we can just give out the map itself. Otherwise, we make a strengthened copy and give that. If making a strengthened copy is not possible, we'd have to raise an error.

Of course the main point whether this is acceptable is whether it can be done with little to no increase to overhead compared to now. Costs come at two points

  • map access: domain and codomain must always be accessed via the methods rather than the (lightning fast) cdeffed attributes _domain and _codomain, since they may be stored via weakref or not. Coercion lookup itself shouldn't really be affected, but coercion application might. If the parent of coercion maps is accessed in the process, we might see a slowdown due to that too.
  • coercion discovery and registration: This will likely involve copying maps now, so this might slow down considerably. This shouldn't really be an inner loop operation, but it may affect things: multimodular algorithms may create lots of, say, matrix rings over finite fields. The computation itself may be relatively cheap, so the construction of the parent and the registration of its coercions may be a significant part of the total cost.

I guess the only way to see whether this is worth it is by trying. At least the semantics are clear. I find it a little scary to weigh down the entire interface for "Maps" but if we can make it opt-in it's perhaps not too much of a burden. (We could just gradually upgrade map classes to be "weakenable" as we find them to be responsible for memory leaks)

comment:57 follow-up: Changed 14 months ago by SimonKing

I just found something crazy: Apparently the rational field got garbage collected in one of the crashing examples. Hard to believe. But it is in something using modular symbols, which is very old code, predating the unique parent paradigma. So, could be that it calls the constructor of the rational field, rather than a factory or whatever makes the rational field unique.

comment:58 in reply to: ↑ 57 Changed 14 months ago by SimonKing

Replying to SimonKing:

I just found something crazy: Apparently the rational field got garbage collected in one of the crashing examples. Hard to believe.

Fortunately I was mistaken: It is only the case that the __init__ method is called repeatedly on the same object QQ if you call RationalField() repeatedly. Namely, it is not using a classcall metaclass, but does the caching in __new__---but __init__ is always called after __new__, whether it is cached or not. That's one of the reasons for introducing classcall metaclass.

comment:59 follow-up: Changed 14 months ago by SimonKing

Perhaps it would be a good idea to change RationalField to use ClasscallMetaclass, but of course on a new ticket. Anyway, it is not related to the problem here.

comment:60 in reply to: ↑ 59 Changed 14 months ago by SimonKing

Replying to SimonKing:

Perhaps it would be a good idea to change RationalField to use ClasscallMetaclass, but of course on a new ticket.

I created #15247

comment:61 follow-up: Changed 14 months ago by nbruin

Too bad. The idea as suggested doesn't actually solve the memory leak; it just makes it less severe (by a constant factor). The problem is: The weakened maps don't prevent their domain from being GCed, but after than happens they linger (now defunct) in _coerce_from. You'll see that even with your patch in, the example in the ticket description will still eat memory--just a little less quickly. You'll find that CDF._coerce_from_hash will contain a LOT of entries.

If we were to use a mix of _coerce_from and _coerce_to (somehow choosing which one to use) you wouldn't see this problem.

If we really want/need to, we could probably salvage the "weakened map" solution:

  • we could install a callback on the weakrefs. Note that the callback would have to be delivered to the codomain, so we wouldn't really have "weakened maps" as objects on their own: the callback on the weakref would make them specific to the data structure in which they reside. There is also the usual problem that weakref callback if very critical and we'd have to be very careful what we do there.
  • defunct maps are easy to recognize: they have a dead weakref in their domain. We could just periodically scrub _coerce_from for defunct maps. One possible strategy would be to keep a "reference size" for _coerce_from and every time we add an entry we check if it is now double the reference size. If it is, we trigger gc, scrub, and reset the reference size. This would at least keep the list bounded in size and hopefully limit the number of expensive scrubs we have to do (treating the bounds exponentially should lead to small amortized costs)
Last edited 14 months ago by nbruin (previous) (diff)

comment:62 in reply to: ↑ 61 ; follow-up: Changed 14 months ago by SimonKing

I have pushed my branch. I wonder why this did not show up as a post on trac. Anyway, I checked that when clicking on "Commits" then everything is there.

I hesitated to push it before, because it is not ready for review. However, it would be better if we'd all agree what code we are talking about.

Replying to nbruin:

Too bad. The idea as suggested doesn't actually solve the memory leak; it just makes it less severe (by a constant factor).

I think this is not the case with the branch that I have just uploaded. I did

sage: for D in xrange(2,2**30):
....:    print get_memory_usage()
....:    Q = QuadraticField(-D)

First, the memory consumption very slowly raised from 213.60546875 to 214.10546875 and then remained steady for several minutes, until I interrupted. And I rather think that the increased consumption was just due to the increased size of D.

The problem is: The weakened maps don't prevent their domain from being GCed, but after than happens they linger (now defunct) in _coerce_from. You'll see that even with your patch in, the example in the ticket description will still eat memory--just a little less quickly. You'll find that CDF._coerce_from_hash will contain a LOT of entries.

This is clearly not the case with the current commit. After running thousands of cycles in the above "for" loop, I get

sage: CDF._introspect_coerce()
{'_action_hash': <sage.structure.coerce_dict.TripleDict at 0xa26b25c>,
 '_action_list': [],
 '_coerce_from_hash': <sage.structure.coerce_dict.MonoDict at 0xa26b3e4>,
 '_coerce_from_list': [],
 '_convert_from_hash': <sage.structure.coerce_dict.MonoDict at 0xa26b41c>,
 '_convert_from_list': [],
 '_element_init_pass_parent': False,
 '_embedding': None,
 '_initial_action_list': [],
 '_initial_coerce_list': [],
 '_initial_convert_list': []}
sage: gc.collect()
2213
sage: for k,v in CDF._introspect_coerce().iteritems():
    if v:
        print k, len(v)
....:         
_coerce_from_hash 4
_convert_from_hash 3

If we were to use a mix of _coerce_from and _coerce_to (somehow choosing which one to use) you wouldn't see this problem.

I don't see this problem anyway.

If we really want/need to, we could probably salvage the "weakened map" solution:

  • we could install a callback on the weakrefs.

What weakrefs are you talking about? Those to domain and codomain?

And what would the callback be supposed to do?

  • defunct maps are easy to recognize: they have a dead weakref in their domain. We could just periodically scrub _coerce_from for defunct maps.

Well, with the current commit, if a map becomes defunct by some garbage collection then it is removed from the _coerce_from_hash by the same garbage collection, hence, it will not linger around.

A different story is _coerce_from_list, which is a list. Here, we might need to take care of defunct maps. Perhaps the maps there shouldn't be weakened in the first place (_coerce_from_list is filled by register_coercion(), and perhaps it would make sense to keep these maps strong), but I am not sure if this wouldn't re-introduce the QuadraticField leak I have just fixed.

One possible strategy would be to keep a "reference size" for _coerce_from and every time we add an entry we check if it is now double the reference size. If it is, we trigger gc, scrub, and reset the reference size.

As I have stated above, I don't think there is a problem with _coerce_from_hash accumulating garbage. But _coerce_from_list may contain garbage, of limited size, because it is only added to by explicit calls to register_coercion().

I think a better strategy would be to make discover_coercion check whether it meets a defunct map when it performs the backtrack algorithm.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:63 Changed 14 months ago by SimonKing

Anyway, here is the problem I am currently having:

sage: E = ModularSymbols(11).2
sage: s = E.modular_symbol_rep()
sage: del E,s
sage: import gc
sage: gc.collect()
1309
sage: E = ModularSymbols(11).2
sage: v = E.manin_symbol_rep()
sage: c,x = v[0]
sage: y = x.modular_symbol_rep()
sage: y.parent()
Abelian Group of all Formal Finite Sums over Integer Ring
sage: A = y.parent().get_action(QQ, self_on_left=False, op=operator.mul)
sage: A.right_domain()
Abelian Group of all Formal Finite Sums over Integer Ring
sage: A.left_domain()
Rational Field
sage: A.codomain()
Traceback (most recent call last):
...
RuntimeError: This action acted on a set that became garbage collected

Hence, If I understand correctly, the "Formal Finite Sums over Rational Field" became garbage collected.

And that's where action differ from maps:

  • In the case of coercion maps, we have domain and codomain, which together are used as weak cache keys for the map. Hence, if either domain or codomain become garbage, then the map becomes invalid but is immediately removed from the cache and will thus not hurt.
  • In the case of actions, we have left domain and right domain, which together are used as weak cache keys for the action. However, in addition to the two domains, an action has a codomain, which currently is weak referenced (this was in order to fix some memory leak). If the codomain is distinct from both left and right domain and if the codomain becomes garbage, then the action becomes invalid, but it would NOT be removed from the cache, as long as domain and codomain are no garbage.

I am afraid that having a strong reference to the codomain of all actions will re-introduce a memory leak fixed elsewhere. But in the above analysis, you may notice that there only is a problem if the codomain is distinct from both left and right domain. Hence, we could be clever and have a strong reference to the codomain only in this case, and a weak reference otherwise.

I will try this now...

comment:64 Changed 14 months ago by SimonKing

I just learnt that the codomain of an action coincides with the set that is acted upon. But here, we have a sage.categories.action.PrecomposedAction. So, it composes maps phi from left and psi from right domain with an action alpha that knows about the codomains of phi and psi only. And thus perhaps we have again the problem of keeping "the middle parent" alive.

Namely, if the underlying set S of alpha is the codomain of psi, but psi is weak, then neither psi nor alpha will keep S alive. But S is sometimes not used as cache key for the precomposed action: Only the domains of psi and phi appear in the key. Hence, I think I just need to add a strong reference to the underlying set of alpha.

comment:65 Changed 14 months ago by SimonKing

The proposed change does in fact fix the problem mentioned in comment:63

comment:66 Changed 14 months ago by SimonKing

I have pushed the new commit. The example from comment:63 became a doctest.

I am now running make ptest. Let us see how many problems persist. Depending on the result, we may worry later whether or not we want to add a safe user interface to the coercion system.

comment:67 Changed 14 months ago by SimonKing

Note that I have retested

sage: for D in xrange(2,2**30):
....:    print get_memory_usage()
....:    Q = QuadraticField(-D)

with the current commit. The memory consumption stays level after a short while, and moreover the numbers returned by get_memory_usage() are now less than 190!

comment:68 Changed 14 months ago by SimonKing

Result of make ptest with the current commit:

sage -t src/sage/interfaces/maxima_abstract.py  # 1 doctest failed
sage -t src/sage/matrix/matrix2.pyx  # 1 doctest failed
sage -t src/sage/categories/group_algebras.py  # Killed due to segmentation fault
sage -t src/sage/combinat/symmetric_group_algebra.py  # Killed due to segmentation fault
sage -t src/sage/combinat/ncsf_qsym/ncsf.py  # Killed due to segmentation fault
sage -t src/sage/combinat/words/morphism.py  # 10 doctests failed
sage -t src/sage/schemes/toric/morphism.py  # 4 doctests failed
sage -t src/sage/matrix/matrix0.pyx  # 3 doctests failed
sage -t src/sage/categories/pushout.py  # Killed due to segmentation fault
sage -t src/sage/rings/polynomial/plural.pyx  # 11 doctests failed
sage -t src/sage/libs/singular/function.pyx  # 2 doctests failed
sage -t src/sage/structure/coerce.pyx  # 5 doctests failed
sage -t src/sage/libs/singular/groebner_strategy.pyx  # 2 doctests failed

So, there remains a lot of work to do.

comment:69 in reply to: ↑ 62 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

I think this is not the case with the branch that I have just uploaded. I did

Got it! Thanks. To have documented why we're OK here: _coerce_from_hash is a MonoDict, so it holds a strong reference to the map stored. This is what keeps the map alive. However, when the domain vanishes, then the MonoDict callback will remove the entry and hence the strong reference to the map. This makes it possible for the map to be GCed. So the required callback to clean up is already triggered via the key triple.

What weakrefs are you talking about? Those to domain and codomain?
And what would the callback be supposed to do?

Indeed, domain and codomain. So those callbacks are already taken care of by _coerce_from_hash being a MonoDict. The codomain is actually not relevant for this (and would be strongly referenced by the map anyway -- perhaps "weakened" maps should only have their domain reference weakened and parent (reference to the homset) cleared? If we just always keep codomain strongly referenced compositions would naturally keep things alive guaranteed anyway. Virtually all maps have a strong ref to the codomain (via generator images) internally anyway, so putting it explicitly on the outside shouldn't hurt much.

A different story is _coerce_from_list, which is a list. Here, we might need to take care of defunct maps. Perhaps the maps there shouldn't be weakened in the first place (_coerce_from_list is filled by register_coercion(), and perhaps it would make sense to keep these maps strong), but I am not sure if this wouldn't re-introduce the QuadraticField leak I have just fixed.

Do we really need _coerce_from_list? Have we identified what it does that cannot be accomplished with the data stored in _coerce_from_hash?

As I have stated above, I don't think there is a problem with _coerce_from_hash accumulating garbage. But _coerce_from_list may contain garbage, of limited size, because it is only added to by explicit calls to register_coercion().

I think a better strategy would be to make discover_coercion check whether it meets a defunct map when it performs the backtrack algorithm.

I doubt you could prove about such an incidental "bumping in" strategy that the number of defunct maps is bounded linearly in the number of active stuff (perhaps measured by active entries in _coerce_from?). That means you wouldn't be able to prove that you don't have a memory leak, and I suspect that with a little study, one could concoct an example that exhibits the leak as well. If discover_coercion would regularly visit all entries in _coerce_from_list then the process would be way too slow.

Given how delicate this code is, please do put ample documentation about assumptions and strategies in the code. Otherwise, the next person to work on this code will likely screw things up. Hopefully it'll be cought by doctests, but we've seen that this could easily not happen.

Last edited 14 months ago by nbruin (previous) (diff)

comment:70 Changed 14 months ago by nbruin

So one action point: Have you considered just leaving the codomain strongly referenced? Apart from the fact that _make_weak and _make_strong on map compositions still needs to recurse into components, it should make compositions easier to work with, because the first map will keep the middle (co)domain alive, as desired.

It also means _codomain can remain a fast slot.

I currently don't see a scenario where weakening the codomain reference buys us anything, especially because maps internally will usually reference the codomain.

Another action point: see if _coerce_from_list can simply be thrown away.

comment:71 in reply to: ↑ 69 Changed 14 months ago by SimonKing

Replying to nbruin:

Indeed, domain and codomain. So those callbacks are already taken care of by _coerce_from_hash being a MonoDict. The codomain is actually not relevant for this (and would be strongly referenced by the map anyway -- perhaps "weakened" maps should only have their domain reference weakened and parent (reference to the homset) cleared? If we just always keep codomain strongly referenced compositions would naturally keep things alive guaranteed anyway. Virtually all maps have a strong ref to the codomain (via generator images) internally anyway, so putting it explicitly on the outside shouldn't hurt much.

This might actually be a good idea. Note that some wise person decided to store coerce maps on the codomain. Hence, having a strong reference from the map back to the codomain will not hurt at all, with the additional advantage you just mentioned. It would also fix the problem with composed maps and with PrecomposedAction!

Do we really need _coerce_from_list? Have we identified what it does that cannot be accomplished with the data stored in _coerce_from_hash?

I don't know why it had originally been introduced. But when I added the weak versions of triple and mono dict, I actually thought of it as a way to make some coercions (namely those explicitly registered) permanent.

I doubt you could prove about such an incidental "bumping in" strategy that the number of defunct maps is bounded linearly in the number of active stuff (perhaps measured by active entries in _coerce_from?). That means you wouldn't be able to prove that you don't have a memory leak, and I suspect that with a little study, one could concoct an example that exhibits the leak as well.

Sure. But the more you have to struggle to construct a leak, the more happy I'll be... :-P

Given how delicate this code is, please do put ample documentation about assumptions and strategies in the code. Otherwise, the next person to work on this code will likely screw things up. Hopefully it'll be cought by doctests, but we've seen that this could easily not happen.

OK, I'll try to be explicit in either the comments in the code, or in the docs.

comment:72 Changed 14 months ago by SimonKing

I can confirm that with a strong reference to the codomain, the leak is still fixed. Now trying to see if it also prevents some of the crashes I've seen in the tests!

comment:73 follow-up: Changed 14 months ago by SimonKing

Outch. Sage started, but the first four tests I've run have segfaulted. Very bad. How can that be?

comment:74 in reply to: ↑ 73 ; follow-up: Changed 14 months ago by SimonKing

Replying to SimonKing:

Outch. Sage started, but the first four tests I've run have segfaulted. Very bad. How can that be?

This is really getting scary. I see in an interactive session that the leak is fixed, but according to the corresponding doctest it isn't fixed.

comment:75 in reply to: ↑ 74 ; follow-up: Changed 14 months ago by SimonKing

Replying to SimonKing:

This is really getting scary. I see in an interactive session that the leak is fixed, but according to the corresponding doctest it isn't fixed.

What a fun...

When counting the number of quadratic number fields tracked by gc, I did

numberQuadFields = len([x for x in gc.get_objects() if isinstance(x, C)])

And apparently,just by chance, x became a pointer to the number field that I wanted to delete. Hence, I had to add del x to make the tests pass.

comment:76 Changed 14 months ago by SimonKing

I am now back at trying to trace down the errors mentioned in comment:68. Frustratingly, with my current local branch (not yet posted), I can not reproduce all the errors, even though the code during comment:68 looked nearly the same.

comment:77 Changed 14 months ago by SimonKing

One rather puzzling error:

sage: import gc
sage: SG4 = SymmetricGroupAlgebra(ZZ,4)
sage: gc.collect()
1051
sage: SG4(1).is_central()
------------------------------------------------------------------------
./sage: Zeile 134: 14576 Speicherzugriffsfehler  "$SAGE_ROOT/src/bin/sage" "$@"

Why is this puzzling? Well, it does not occur when I make both domain and codomain weak references, for coerce maps. But it does occur when I only make the domain a weak reference.

So, is it the case that "the more weak references, the more crash safe"??

comment:78 in reply to: ↑ 75 Changed 14 months ago by nbruin

Replying to SimonKing:

numberQuadFields = len([x for x in gc.get_objects() if isinstance(x, C)])

Perhaps use

numberQuadFields = sum(1 for x in gc.get_objects() if isinstance(x, C))

instead, to prevent leaking x?

comment:79 Changed 14 months ago by SimonKing

It reduces to

sage: SG4 = SymmetricGroupAlgebra(ZZ,4)
sage: SG4._introspect_coerce()['_coerce_from_list']
[Generic morphism:
  From: Integer Ring
  To:   Symmetric group algebra of order 4 over Integer Ring,
 Generic morphism:
  From: Symmetric group algebra of order 3 over Integer Ring
  To:   Symmetric group algebra of order 4 over Integer Ring]
sage: phi, psi = _
sage: import gc
sage: gc.collect()
1062
sage: phi
Generic morphism:
  From: Integer Ring
  To:   Symmetric group algebra of order 4 over Integer Ring
sage: psi
Traceback (most recent call last):
...
ValueError: This map is in an invalid state, domain or codomain have been garbage collected

So, perhaps we need to keep stuff strong in the coerce_from_list after all.

comment:80 Changed 14 months ago by SimonKing

PS: But why does it not crash if the coerce maps' codomains get weakref'd too?

comment:81 Changed 14 months ago by SimonKing

For the record: When I do not weaken the maps on _coerce_from_list or _convert_from_list, the crash vanishes, but the memory leak is still fixed.

Also in my unpublished branch: Skip invalid maps in discover coercion (in the backtracking algorithm). But this is just an additional safety. I think we want that explicitly registered maps (i.e., those which are the fundamental path ways in the backtracking algorithm) will stay alive. Hence, it might even be worth while to keep an explicit reference to the domain of the map, so that the map will remain valid even if something weakens it.

I am now running tests again.

comment:82 follow-up: Changed 14 months ago by SimonKing

To summarise the requirements found in our discussion for a stable and memory
friendly coercion system:

  • Maps registered by P.register_coercion(mor) are the backbone of the discover_coercion algorithm. Hence, they need to be kept healthy as long as P lives.
  • If P has a coerce embedding then this embedding needs to be kept healthy as long as P lives.
  • If the coercion system finds a coercion from P to Q different from the two preceding cases (i.e., by transitive closure), then P must not prevent Q and the coercion map from garbage collection, and Q must not prevent P and the coercion map from garbage collection. But the coercion map needs to stay healthy as long as both P and Q are alive. In particular, take care of composed maps and actions.

To summarise how I think we can meet these requirements:

  • P.register_coercion(mor) keeps a strong reference to mor.domain() in a new attribute P._registered_domains (which is a list). All other maps in the coercion system will be weakened.
  • Homsets keep strong references to domain and codomain.
  • "Weakening a map" means to use a weak reference to the domain and a removed reference to the homset. But we will keep a strong reference to the codomain. Consequence: (1) In a composed map or action, the "middle parents" will always stay alive as long as the composed map lives. (2) Embeddings do what we required above: The embedding keeps the codomain alive.
  • We store the map phi found by P.discover_coercion(Q) in P._coerce_from_hash, which is a monodict. In particular, if Q will be garbage collected, then phi is immediately removed from the cache, and thus the strong reference of phi to the codomain P will not prevent P from garbage collection. And if P will be garbage collected, then the whole cache including phi is removed. However, if both P and Q live, then phi will stay in P._coerce_from_hash[Q], and it will stay healthy, because its domain Q is still alive (and hence the weak reference is still ok).

I think this model makes sense.

And concerning a safe user interface: Perhaps we can do without. Namely, we could make it so that the string representation of a weakened map will consist of a warning, suggesting to use a copy. In this way, it would be sufficiently likely that the user wouldn't have too many bad surprises.

comment:83 in reply to: ↑ 82 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

  • Maps registered by P.register_coercion(mor) are the backbone of the discover_coercion algorithm. Hence, they need to be kept healthy as long as P lives.

It's not clear to me this is the case. If mor is a map from S to P then P.register_coercion(mor) ensures the coercion system knows how to map an element from S into P. Why is it important to maintain this information for the lifetime of P? If S ceases to exist, then one would not need to map elements from S to P. Why do we need to ensure S keeps existing? Shouldn't P have a reference to S independent of the coercion system if P's health depends on the existence of S? I think the coercion system is there to keep track of relations between existing objects, not to keep objects in existence (although this might be a side-effect of keeping track of relations between other objects).

  • If P has a coerce embedding then this embedding needs to be kept healthy as long as P lives.

I presume this is the function of the _embedding coercion attribute? So it looks like we already have that. What if we want multiple embeddings?

  • P.register_coercion(mor) keeps a strong reference to mor.domain() in a new attribute P._registered_domains (which is a list). All other maps in the coercion system will be weakened.

So what means are there available to add a coercion without tying the lifespan of one to the other? Shouldn't it be possible to specify such things too?

  • We store the map phi found by P.discover_coercion(Q) in P._coerce_from_hash, which is a monodict. In particular, if Q will be garbage collected, then phi is immediately removed from the cache, and thus the strong reference of phi to the codomain P will not prevent P from garbage collection.

It never did prevent collection: The reference to phi is held by P, so the reference from phi to P would be recognized as a cycle, so the cyclic GC would find it (and parents usually are involved in cycles already, so cyclic GC is their only chance for being reclaimed anyway). Your statement is still true.

And concerning a safe user interface: Perhaps we can do without. Namely, we could make it so that the string representation of a weakened map will consist of a warning, suggesting to use a copy. In this way, it would be sufficiently likely that the user wouldn't have too many bad surprises.

Hm, we'll see.

comment:84 in reply to: ↑ 83 ; follow-ups: Changed 14 months ago by SimonKing

With my current not yet published code, I get errors only in one file, namely with scheme morphisms. And this actually isn't a surprise, since scheme morphisms almost completely ignore the existing methods they inherit from sage.categories.map.Map. They have a custom __init__ doing more or less the same what the old version of Map.__init__ used to do, and they even override domain() and codomain().

So, this should be fixable, and I suppose I will be able to post a commit so that all tests pass, later today.

Replying to nbruin:

Replying to SimonKing:

  • Maps registered by P.register_coercion(mor) are the backbone of the discover_coercion algorithm. Hence, they need to be kept healthy as long as P lives.

It's not clear to me this is the case. If mor is a map from S to P then P.register_coercion(mor) ensures the coercion system knows how to map an element from S into P. Why is it important to maintain this information for the lifetime of P? If S ceases to exist, then one would not need to map elements from S to P.

One does! Namely, suppose that you first do P.register_coercion(mor), then you allow S to become garbage collected, and then you create a new parent Q with an embedding into what looks like S (of course, it now is a replica of the original now garbage collected S).

You would want that Q coerces into P via S, by transitivity of coercions. But you collected mor.domain() and thus you will fail to find this coercion.

Another attempt to explain why I think the explicitly registered maps need to be kept:

Think of the coercions as a digraph.

  • The vertices correspond to parents.
  • The arrows (oriented edges) of the digraph correspond to those maps that are declared as coercions by .register_coercion(...).
  • In addition to the arrows created with register_coercion, the coercion system may find short-cuts by calling ._coerce_map_from_(...). For efficiency reasons, these short-cuts are stored in a cache.
  • The coercion system then tries to find directed paths between two given vertices, including short-cuts. For efficiency reasons, it stores the resulting composed maps in a cache.

How does the coercion system find "directed paths with short-cuts" from Q to P?

  • Of course, it would be impossible to just guess a parent S such that Q has a short-cut into S and S has a short-cut into P.
  • One could search through all paths alpha (paths without shortcuts, I mean) starting at Q and simultaneously through all paths beta ending at P, and then test whether there is a short-cut from the endpoint of alpha to the startpoint of beta. It would work, but I guess it would be very time consuming.
  • The current coercion system will therefore just search (by backtracking) through all shortcut-free paths beta ending at P, end then test whether there is a short-cut from Q to the startpoint of beta. In addition, the coerce embedding registered for Q will be considered in forward direction.

Remark

Perhaps in the long run, we could actually use a proper digraph (with a lightning fast backend) to keep track of coercions.

Now for garbage collection:

Why do we need to ensure S keeps existing? Shouldn't P have a reference to S independent of the coercion system if P's health depends on the existence of S? I think the coercion system is there to keep track of relations between existing objects, not to keep objects in existence (although this might be a side-effect of keeping track of relations between other objects).

I think that in many cases it would indeed be the case that P should reference S independent of coercions (say, if S is the base ring of P). However, it is conceivable (and I think I've met such cases in failing doctests) that P can remain perfectly healthy without S, but still we would like to find coercions from Q to P via S.

So, the coercion system will not care for the health of P, but it must care for the connectivity of the coercion graph. And in the current algorithm sketched above, it is of vital importance to keep arrows leading to P alive, since otherwise we have to live with shortcuts only.

  • If P has a coerce embedding then this embedding needs to be kept healthy as long as P lives.

I presume this is the function of the _embedding coercion attribute? So it looks like we already have that. What if we want multiple embeddings?

Then we look into the code and see that multiple embeddings are explicitly excluded. A parent has precisely one embedding that is taken into account by the coercion search in forward direction. You may of course register further embeddings as coercions, by emb.codomain().register_coercion(emb), but they would only be used for search in backward direction.

  • P.register_coercion(mor) keeps a strong reference to mor.domain() in a new attribute P._registered_domains (which is a list). All other maps in the coercion system will be weakened.

So what means are there available to add a coercion without tying the lifespan of one to the other?

Note that after P.register_coercion(mor), mor.domain() will live at least as long as P. But mor.domain() would not be enough to keep P alive.

And there surely is a means available to add a coercion that doesn't tie the lifespan of two parents too closely: Implement P._coerce_map_from_(Q), which can return a map or simply "True" (in the latter case, conversion is used to coerce Q into P). The result is cached in P._coerce_from_hash, but not in P._coerce_from_list.

Shouldn't it be possible to specify such things too?

Perhaps in the long run? I wouldn't like to do those things (such as: Rewrite the coercion system to use a proper digraph backend) here.

comment:85 in reply to: ↑ 84 Changed 14 months ago by SimonKing

Replying to SimonKing:

With my current not yet published code, I get errors only in one file, namely with scheme morphisms. And this actually isn't a surprise, since scheme morphisms almost completely ignore the existing methods they inherit from sage.categories.map.Map. They have a custom __init__ doing more or less the same what the old version of Map.__init__ used to do, and they even override domain() and codomain().

Arrgh, it is even worse: SchemeMorphism just inherits from Element, not from Map! Unbelievable.

comment:86 Changed 14 months ago by SimonKing

  • Authors set to Simon King
  • Work issues set to Provide copy of composed maps

I have pushed two more commits, and now all doctests should pass (to be verified).

I also think I have extensively explained the rationale behind the changes. Hence, I have already clicked "Needs review". But it was too soon (see below).

A potential "todo": We might want that a weakened map returned by P.coerce_map_from(Q) will print as

sage: QQ['x'].coerce_map_from(QQ)
This is a map used by the coercion system.
If you want to use it outside of the coercion system,
please use a copy of the map
sage: copy(_)
Polynomial base injection morphism:
  From: Rational Field
  To:   Univariate Polynomial Ring in x over Rational Field

In this case, we may want to have __copy__ methods everywhere. Even though the current branch improves copying, I just obtained the following crash that I want to fix first:

sage: QQ['x'].coerce_map_from(ZZ)
Composite map:
  From: Integer Ring
  To:   Univariate Polynomial Ring in x over Rational Field
  Defn:   Natural morphism:
          From: Integer Ring
          To:   Rational Field
        then
          Polynomial base injection morphism:
          From: Rational Field
          To:   Univariate Polynomial Ring in x over Rational Field
sage: phi = copy(_)
sage: phi(2)
<SEGFAULT>

comment:87 Changed 14 months ago by SimonKing

  • Status changed from new to needs_review

Done, and now I'd say it can be reviewed. With the latest commit, one can do

sage: phi = QQ['x'].coerce_map_from(ZZ)
sage: phi.domain
<weakref at 0xa225284; to 'sage.rings.integer_ring.IntegerRing_class' at 0x96ddd3c (EuclideanDomains.parent_class)>
sage: type(phi)
<type 'sage.categories.map.FormalCompositeMap'>
sage: psi = copy(phi)
sage: psi
Composite map:
  From: Integer Ring
  To:   Univariate Polynomial Ring in x over Rational Field
  Defn:   Natural morphism:
          From: Integer Ring
          To:   Rational Field
        then
          Polynomial base injection morphism:
          From: Rational Field
          To:   Univariate Polynomial Ring in x over Rational Field
sage: psi(3)
3
sage: psi.domain
The constant function (...) -> Integer Ring

which required implementing __copy__ for polynomial basering injections and formal composite maps.

If you want me to make weakened coercion maps print as a big warning, then I could of course do so, but will only do if you ask.

comment:88 Changed 14 months ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues changed from Provide copy of composed maps to Fix elliptic curves code

Too bad. Apparently the elliptic curve code does not like SchemeMorphism to be a Morphism...

comment:89 Changed 14 months ago by SimonKing

Namely:

sage: E=EllipticCurve('37a1')
sage: P=E(0,0)
sage: Q=5*P
<Booom>

apparently while trying to create an action.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:90 Changed 14 months ago by SimonKing

Aha.

sage: P.__class__.mro()
[sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_number_field,
 sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field,
 sage.schemes.projective.projective_point.SchemeMorphism_point_abelian_variety_field,
 sage.structure.element.AdditiveGroupElement,
 sage.structure.element.ModuleElement,
 sage.schemes.projective.projective_point.SchemeMorphism_point_projective_field,
 sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring,
 sage.schemes.generic.morphism.SchemeMorphism_point,
 sage.schemes.generic.morphism.SchemeMorphism,
 sage.categories.morphism.Morphism,
 sage.categories.map.Map,
 sage.structure.element.Element,
 sage.structure.sage_object.SageObject,
 object]

and

sage: P.domain
<bound method EllipticCurvePoint_number_field.domain of (0 : 0 : 1)>
sage: P.domain.__module__
'sage.schemes.elliptic_curves.ell_point'
sage: P.domain??
Type:       instancemethod
String Form:<bound method EllipticCurvePoint_number_field.domain of (0 : 0 : 1)>
File:       /home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_point.py
Definition: P.domain(self)
Source:
    def domain(self):
        """
        Return the domain of this point, which is `Spec(F)` where `F` is
        the field of definition.

        EXAMPLES::

            sage: E=EllipticCurve(QQ,[1,1])
            sage: P=E(0,1)
            sage: P.domain()
            Spectrum of Rational Field
            sage: K.<a>=NumberField(x^2-3,'a')
            sage: P=E.base_extend(K)(1,a)
            sage: P.domain()
            Spectrum of Number Field in a with defining polynomial x^2 - 3
       """
        return self.parent().domain()

So, not only was SchemeMorphism ignoring Morphism, but additionally its sub-class EllipticCurvePoint_fieldEllipticCurvePoint_field overrode what it inherited from SchemeMorphism by a verbosely identical copy.

The elliptic curve code is a mess.

comment:91 Changed 14 months ago by SimonKing

In sage.schemes.elliptic_curves.heegner, it also seems to me that GaloisAutomorphism should use Morphism. I don't know if I will change it here.

comment:92 Changed 14 months ago by SimonKing

Hmm. If we are in very bad luck, then the current commit triggers a bug in Cython concerning confusion of different cpdef slots when one provides two different base classes (ModuleElement and Morphism). Namely, it pretty much seems that

   (<ModuleElement>left)._add_(<ModuleElement>right)

does not return

   left._add_(right)

comment:93 Changed 14 months ago by SimonKing

  • Status changed from needs_work to needs_review

Hooray!

----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 3777.0 seconds
    cpu time: 5867.6 seconds
    cumulative wall time: 7256.6 seconds

I added a "todo" to the documentation of sage.schemes.generic.morphism, stating that SchemeMorphism should rather inherit from Morphism, but currently can not, because of a bug in Cython. I modified the code so that it now exactly imitates the new Morphism code. In this way, a future transition to a sub-class of Morphism should be easier.

Anyway, since the tests pass, I'd say it is "needs review" for now.

Plan: If you believe that the new approach makes sense, then I'll also add a longer section to the reference manual, explaining how the weakref business is supposed to work.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:94 follow-up: Changed 14 months ago by SimonKing

By the way, I was looking into my logs/ptest.log, and it seems that the total cpu time for the tests remained essentially the same. Hence, hopefully there is no bad slow-down. But we should probably take some old benchmarks used at, say, #11900, and see what my new commits do with them.

comment:95 Changed 14 months ago by SimonKing

Here are the tests from #11900.

In Commit:05fb569, I get

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 10.76 s, sys: 0.18 s, total: 10.93 s
Wall time: 10.95 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 3.12 s, sys: 0.00 s, total: 3.12 s
Wall time: 3.13 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 2.28 s, sys: 0.02 s, total: 2.29 s
Wall time: 2.30 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 4.80 s, sys: 0.04 s, total: 4.84 s
Wall time: 4.85 s
sage: def test(E):
....:     for p in prime_range(10000):
....:         if p != 389:
....:             G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 31.56 s, sys: 0.09 s, total: 31.65 s
Wall time: 31.70 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 21.96 s, sys: 0.06 s, total: 22.02 s
Wall time: 22.07 s

In public/sage-git/master, I get

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 10.72 s, sys: 0.17 s, total: 10.90 s
Wall time: 10.91 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 3.23 s, sys: 0.00 s, total: 3.23 s
Wall time: 3.24 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4, z]).echelon_form()
CPU times: user 2.21 s, sys: 0.02 s, total: 2.23 s
Wall time: 2.23 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 5.27 s, sys: 0.04 s, total: 5.32 s
Wall time: 5.32 s
sage: def test(E):
....:    for p in prime_range(10000):
....:        if p != 389:
....:            G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 32.06 s, sys: 0.11 s, total: 32.17 s
Wall time: 32.22 s
sage: %time for E in cremona_curves([11..100]): S = E.integral_points(both_signs=False)
CPU times: user 22.11 s, sys: 0.07 s, total: 22.17 s

These tests have been found sensitive against slowness in category and coercion framework. So, the fact that there is not the faintest regression in these tests gives some confidence.

comment:96 in reply to: ↑ 84 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

One does! Namely, suppose that you first do P.register_coercion(mor), then you allow S to become garbage collected, and then you create a new parent Q with an

embedding into what looks like S (of course, it now is a replica of the original now garbage collected S).

You would want that Q coerces into P via S, by transitivity of coercions. But you collected mor.domain() and thus you will fail to find this coercion.

I agree that there is a place for such strong connections, but I have severe reservations about declaring it's the only way or even the default way to inform the system
about coercions.

The following would leak memory with the model you propose:

M1=ZZ^1
M2=ZZ^2
for d in [2..100000]:
    N=ZZ^d
    m1=Hom(N,M1)([M.0 for i in range(d)])
    m2=Hom(N,M2)([M.(i % 2) for i in range(d)])
    M1.register_coercion(m1)
    M2.register_coercion(m2)

I have severe reservations about declaring that this code "will never be memory efficient" in sage. One way out is to use the (for this purpose) extremely inappropriately named

    N.register_embedding(m1)

instead, which in your model would mean M1 lives at least as long as N instead. In addition, we would not be able to do this for both M1 and M2.

I think there's room for a register_embedding with those semantics (although it should probably have a different name, because it doesn't have to be an embedding)
as well as for register_coercion_from_while_keeping_domain_alive with a catchier name, but the life-enhancing side effects are fundamentally separate from the fact
that there's a coercion in the first place, and I think it should be possible to register a non-life-enhancing coercion as well (the main reason is that
it's easily done and that I haven't seen a proof it's not necessary. We don't want to unnecessarily hamstring the system).

philosophical ramblings

The following observations are the result of trying to come up with a conceptual ideal/model that we could use to argue what our coercion framework SHOULD do. Up to
now it seems to me people have mainly been making ad-hoc, gut feeling decisions about how to put together coercion. I haven't found a better solution here, but I
think there are some examples may illustrate we might just have to be pragmatic about this.

Your suggestion makes sense if you want to model a "permanent, unchanging universe" in which all possible parents, with consistent coercions, already exist; we're
simply "discovering" this universe in a piecemeal fashion. It's a common model in modern algebra, but I think our computer algebra model is too far away from this
ideal to follow this model too far. Consider:

Qx.<x>=QQ[]
K.<a>=NumberField(x^4-2)
L.<b>=NumberField(x^2-2,embedding=a^2)

This fits perfectly in the "unchanging universe" model. Also note that the coercion system does not need to let L keep K alive, since the construction parameters,
which get kept alive for the life of L by CachedRepresentation or something analogous, refer to K already.

Now consider

M.<b>=NumberField(x^2-2)

In the "unchanging universe" (and in sage as well) we have that M is distinct from L. However, I think it's unrealistic to expect that all "embeddings" etc. can be
specified at construction time. So I think, even though it's not possible currently in sage, that one should allow for

m1=Hom(M,K)([a^2])
m2=Hom(M,K)([-a^2])
M.register_embedding(m1)

Note that the choice of m1 or m2 here leads to different relations between M and K and hence different universes.
In other words, our concept of "globally unique" is not powerful enough to capture the
full identity of objects, which would include the coercion relations with objects that haven't been "discovered" yet. In practice, we can usually work around that by
for instance changing the names of generators and hence create artificially differently labelled objects but that's already not a possibility for creating
different copies of ZZ^n, since there are no generator names to choose there.

I think one has to accept the reality here: what we have is a collection of objects whose relations do change in time.

Some particular responses (most of them direct corollaries from what is observed above).

Another attempt to explain why I think the explicitly registered maps need to be kept:

Think of the coercions as a digraph.

  • The vertices correspond to parents.
  • The arrows (oriented edges) of the digraph correspond to those maps that are declared as coercions by .register_coercion(...).
  • In addition to the arrows created with register_coercion, the coercion system may find short-cuts by calling ._coerce_map_from_(...). For efficiency reasons,

these short-cuts are stored in a cache.

  • The coercion system then tries to find directed paths between two given vertices, including short-cuts. For efficiency reasons, it stores the resulting composed

maps in a cache.

That's not the only thing coercion does. It may also find "common covering structures", which may lead to construction of new parents. Those definitely don't deserve
to get nailed into memory. Yet, the code that creates these parents will look (to the coercion system) as a "user", so it would be using these strong-referencing
coercion registration routines.

So, the coercion system will not care for the health of P, but it must care for the connectivity of the coercion graph. And in the current algorithm sketched above,
it is of vital importance to keep arrows leading to P alive, since otherwise we have to live with shortcuts only.

I think it may well be a feature, not a bug, that one at some point can just be left with the shortcuts and that the intermediates have fallen out. The natural way of
staying close to "discovering a permanent universe" is by never throwing away anything that has been discovered, and I think we agree that's a "memory leak". So
it's really a matter of only keeping things around that we still need. If we're too lax with considering what is "needed", we'll end up keeping too many things in
memory.

Then we look into the code and see that multiple embeddings are explicitly excluded. A parent has precisely one embedding that is taken into account by the coercion

search in forward direction. You may of course register further embeddings as coercions, by emb.codomain().register_coercion(emb), but they would only be used
for search in backward direction.

Not only that: you'd be tying different lifetime implications to that construction too.

And there surely is a means available to add a coercion that doesn't tie the lifespan of two parents too closely: Implement P._coerce_map_from_(Q), which can
return a map or simply "True" (in the latter case, conversion is used to coerce Q into P). The result is cached in P._coerce_from_hash, but not in
P._coerce_from_list.

You mean: implement P._install_coerce_map_from_(m), which does: _coerce_from_hash[Domain(m)]=m. I think it is quite important to be able to manipulate the
coercion graph without having to modify library code.

comment:97 in reply to: ↑ 94 Changed 14 months ago by nbruin

Congratulations on making such good headway! The main thing left is to determine how weakly referenced the coercion framework needs to be.

comment:98 Changed 14 months ago by SimonKing

  • Commit set to 05fb569cb132a8c89713021f1f4b25cd2dd7cb1c

New commits:

[changeset:05fb569]Change SchemeMorphism? back (to cope with a Cython bug), copying the new code from sage.categories.map.Map
[changeset:8fd09d5]Copying of PolynomialBaseringInjection? and FormalCompositeMap?
[changeset:be37145]Let SchemeMorphism? inherit from Morphism, not from Element
[changeset:0f38a2c]Keep strong reference to codomain of weakened coerce maps Keep strong reference to domains of *registered* coercions
[changeset:a53261d]Keep a strong reference to the codomain of PrecomposedAction?
[changeset:1ff6f3f]Add generic copy of maps. Fix copy of elements. Replace _(co)domain everywhere
[changeset:61d818c]Replace Map.(co)domain by constant functions, remove ._(co)domain
[changeset:ebe82df]Use a proper WeakValueDictionary? for number fields
[changeset:4685c73]convert_map_from() should only store weak references Similar to coerce_map_from, the detected morphism should be stored only in a weak dictionary, not in a list.

comment:99 in reply to: ↑ 96 Changed 14 months ago by SimonKing

Replying to nbruin:

I agree that there is a place for such strong connections, but I have severe reservations about declaring it [.register_coercion()] is the only way or even the default way to inform the system
about coercions.

Well, I have mentioned ._coerce_map_from_(...) in several previous posts, and if you look at my thematic tutorial on categories and coercion, you'll find that I consider this the default. And it only yields weak caching.

I have severe reservations about declaring that this code "will never be memory efficient" in sage.

I think that we want some particularly important coercions to be tied to the lifetime of the codomain, and thus we use .register_coercion(), and we want other coercions to be tied to the minimum of the lifetimes of domain and codomain, and thus we use ._coerce_map_from_(). I don't think we have a problem here.

Consider:

Qx.<x>=QQ[]
K.<a>=NumberField(x^4-2)
L.<b>=NumberField(x^2-2,embedding=a^2)

This fits perfectly in the "unchanging universe" model. Also note that the coercion system does not need to let L keep K alive, since the construction parameters,
which get kept alive for the life of L by CachedRepresentation or something analogous, refer to K already.

It isn't CachedRepresentation, but this doesn't matter.

Now consider

M.<b>=NumberField(x^2-2)

In the "unchanging universe" (and in sage as well) we have that M is distinct from L. However, I think it's unrealistic to expect that all "embeddings" etc. can be
specified at construction time.

Again, nobody has claimed that everything needs to be declared at construction
time. There are some particularly important coercions registered at
construction time, namely the coerce embedding (if it exists then it is
unique) and those installed by .register_coercion(). Everything else is
dynamical, based on _coerce_map_from_().

In my description from comment:84, note that the digraph is not totally
static. It has static parts (corresponding to coerce embeddings and coercions
fixed by .register_coercion()) and dynamic shortcuts (corresponding to _coerce_map_from_).

So I think, even though it's not possible currently in sage, that one should allow for

m1=Hom(M,K)([a^2])
m2=Hom(M,K)([-a^2])
M.register_embedding(m1)

I don't know if this is reasonable, but at least it is against what people
originally wanted with the coerce embedding. If you declare the coerce
embedding phi from a number field K to, say, CC, then you consider K as a
subfield of CC. If you provide another number field L, which is isomorphic
to K, with a different embedding psi into CC, then adding an element of
K to an element of L is done by embedding both into CC and then adding
complex numbers.

Since we think of K and L as different subfields of CC and not as abstract
fields, we must consider K and L as different objects, and so the different
embedding must play a role in the cache key for K and L. This is why they have
to be provided at construction time.

It would be a totally different way of thinking if you tried to do the same
with CC.register_coercion(phi/psi) or with
CC._coerce_map_from_(K/L). Namely, in both cases, you would not be able to
add elements of K and L, because neither K nor L would know about the
embedding. And in fact you would consider K and L as abstract fields, and you
would in fact want K is L (at least if you fancy unique parents, which I
do...). And then the axioms for coercion would strike: There can be at most
one coercion from K (i.e., L) to CC. Hence, you could not
simultaneously declare different embeddings of K into CC as coercions.

Since it pretty much seems to me that number theorists want to comfortable
compute with different isomorphic subfields of CC, it would thus simply not
feasible to restrict oneself to .register_coercion and _coerce_map_from_:
One needs coerce embeddings, and one needs that they are part of the
defining data of a number field.

Note that the choice of m1 or m2 here leads to different relations between M and K and hence different universes.
In other words, our concept of "globally unique" is not powerful enough to capture the
full identity of objects, which would include the coercion relations with
objects that haven't been "discovered" yet.

I would state it differently. In order to define K (a subfield of CC), there
is no way around providing the embedding during creation. "Discovering" a
coercion relation seems the wrong approach here.

And speaking about memory: The embedding of K into CC is stored as an
attribute of K, not of CC. Hence, K keeps CC alive, but CC does not prevent K
from garbage collection. So, I really don't understand where you see a problem.

In practice, we can usually work around that by
for instance changing the names of generators and hence create artificially differently labelled objects but that's already not a possibility for creating
different copies of ZZ^n, since there are no generator names to choose there.

Well, if one has obvious distinguishing data, such as an embedding, then there
is nothing artificial when using them.

I think one has to accept the reality here: what we have is a collection of objects whose relations do change in time.

No. I don't see anything dynamic in your "embedded numberfield" examples. A
subfield is a subfield is a subfield.

That's not the only thing coercion does. It may also find "common covering
structures", which may lead to construction of new parents. Those definitely
don't deserve to get nailed into memory. Yet, the code that creates these
parents will look (to the coercion system) as a "user", so it would be using
these strong-referencing coercion registration routines.

What you seem to mention here is the pushout construction. It mainly relies on
"construction functors". I don't even know if it takes the coerce embeddings
into account at all.

Anyway, the new parents created by pushouts indeed play the same role as parents
created by the user. Let's try to be more concrete. Let P and Q be
parents, you want to add an element p of P to an element q of Q, and the pushout
construction finds a parent R such that both P and Q coerce into R, allowing
to perform the addition in R, resulting in r=R(p)+R(q).

Now, it could be that R.register_coercion(P) and R.register_coercion(Q)
are both executed in R.__init__ (but see the remark below). In the current
code (also in my branch), this would imply a strong reference chain from R to
both P and Q. Hence, even if you did del p,q,P,Q, P and Q could not be
garbage collected.

But I don't think we should see this problematic, for several reasons:

  • Pushout constructions don't arise particularly often. Normally, either P coerces into Q or Q coerces into P, or both embed into the same parent anyway, and I have mentioned above: With a coerce embedding, the existance of R would not prevent P and Q from garbage collection (plus, it has nothing to do with pushout anyway...)
  • Is register_coercion really used so often? I think _coerce_map_from_ is more commonly used, and then the existence of R would not prevent P and Q from garbage collection.

I think it may well be a feature, not a bug, that one at some point can just
be left with the shortcuts and that the intermediates have fallen out.

How would you guarantee that you kept in mind enough shortcuts to not change
connectivity by throwing away intermediates?

The
natural way of staying close to "discovering a permanent universe" is by
never throwing away anything that has been discovered, and I think we agree
that's a "memory leak".

No, we disagree.

It is a memory leak if a connected component (not taking into account
shortcuts) of the coercion graph can not be garbage collected, even though
there is no external strong reference (which may be a coerce embedding) to any
vertex of the connected component.

Note that this was exactly the problem with the example from the ticket
description! As I have pointed out in comment:18, it was not the case that
the problem lay in _coerce_from_list_, because this was empty. In
particular, it was not the case that .register_coercion() was to
blame.

Instead, the memory leak came from short-cuts, i.e., from the stuff
stored in _coerce_from_hash, which can also be seen in
chain.png.

Hence, the quadratic field and CC did belong to different connected components
of the coercion graph, but the shortcut kept Q alive.

And there surely is a means available to add a coercion that doesn't tie the
lifespan of two parents too closely: Implement P._coerce_map_from_(Q),
which can return a map or simply "True" (in the latter case, conversion is
used to coerce Q into P). The result is cached in P._coerce_from_hash, but
not in P._coerce_from_list.

You mean: implement
P._install_coerce_map_from_(m), which does:
_coerce_from_hash[Domain(m)]=m. I think it is quite important to be able
to manipulate the coercion graph without having to modify library code.

This might be a good idea. So, we would have .register_coercion() for
permanent pathways, and _install_coerce_map_from() (with a similar
semantics, i.e., you can either just provide the parent or a whole morphism)
for impermanent shortcuts.

comment:100 follow-up: Changed 14 months ago by SimonKing

Let me try to summarise what is (or may be) left to do:

  • Add a section explaining the current weak coercion model, to facilitate maintanance,
  • I think I forgot to add some doc strings when I changed SchemeMorphism,
  • Add _install_coerce_map_from().
  • Perhaps: Let the string representation of a weakened map consist of a warning to not use this map outside of the coercion framework.
  • Perhaps: Re-introduce a cdef public attribute _codomain, since this would allow faster access than calling .codomain(), and since the codomain will be strongly referenced anyway.

Anything I forgot?

Last edited 14 months ago by SimonKing (previous) (diff)

comment:101 Changed 14 months ago by SimonKing

  • Work issues Fix elliptic curves code deleted

comment:102 Changed 14 months ago by SimonKing

And I think I should do a further test: I will modify Parent.__init__ so that it prints the type of self to a log file, and so I'll see how many parents are created with and without the patch. If we see a sudden change in the statistics for some types, then it might point us to code that implicitly relies on a permanent cache.

comment:103 in reply to: ↑ 100 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

Good, I think we at least are in sufficient agreement for the practical implications of what we need.

Let me try to summarise what is (or may be) left to do:

  • Add a section explaining the current weak coercion model, to facilitate maintenance,
  • Add _install_coerce_map_from().

To clarify this point (and it might be helpful to put something along these lines in the documentation), it seems to me there would be 4 ways to put coercions in place:

  • A programmatic way, by supplying code in _coerce_map_from_. Since it's programmatic, it seems it can be rediscovered easily when parents get garbage collected and recreated, so it seems appropriate maps stemming from here do not lead to lifetime implications.
  • A way to put a coercion in that ensures that the codomain keeps the domain alive (.register_coercion)
  • A way to put a coercion in that ensures that the domain keeps the codomain alive (register_embedding does that, but only can only accommodate one per domain)
  • A way to put a coercion in that does not imply any life support between domain and codomain. Someone who starts out should probably not use this, because garbage collection can lead to surprising results. It may be required to avoid memory problems.

I think the fourth point is desirable because the alternative, programmatic solutions via _coerce_map_from_, feel much more heavy-weight (subclassing a whole parent just to extend _coerce_map_from_ may be appropriate for someone who is concerned with developing sage, but seems inappropriate to me for someone who is thinking about using sage to do a complicated computation.

  • Perhaps: Let the string representation of a weakened map consist of a warning to not use this map outside of the coercion framework.

I think yes: Due to cyclic references, parents will usually survive until the next GC, which may be quite a while after the last reference is lost. So place where the map becomes liable to turn defunct may be quite distant from the place where the map if found to be defunct. People deserve a reminder about that.

comment:104 in reply to: ↑ 103 ; follow-up: Changed 14 months ago by SimonKing

Replying to nbruin:

Replying to SimonKing:

Let me try to summarise what is (or may be) left to do:

  • Add a section explaining the current weak coercion model, to facilitate maintenance,
  • Add _install_coerce_map_from().

To clarify this point (and it might be helpful to put something along these lines in the documentation), ...

But where?

I think the fourth point is desirable because the alternative, programmatic solutions via _coerce_map_from_, feel much more heavy-weight (subclassing a whole parent just to extend _coerce_map_from_ may be appropriate for someone who is concerned with developing sage, but seems inappropriate to me for someone who is thinking about using sage to do a complicated computation.

OK. But then, this method should be visible, hence, not starting with an underscore.

  • Perhaps: Let the string representation of a weakened map consist of a warning to not use this map outside of the coercion framework.

I think yes: Due to cyclic references, parents will usually survive until the next GC, which may be quite a while after the last reference is lost. So place where the map becomes liable to turn defunct may be quite distant from the place where the map if found to be defunct. People deserve a reminder about that.

OK. Perhaps: If the map is weak but the domain reference is still available, then show the map as

"""WARNING: This %s map from %s to %s
may become defunct after the next garbage collection.
For usage outside of the coercion system, try to create a copy,
or apply the method `_make_strong_references()`"""%(self._repr_type(), self.domain(),self.codomain()

and if the domain is unavailable, then show the map as

"Defunct %s map"%self._repr_type()"

comment:105 in reply to: ↑ 104 Changed 14 months ago by SimonKing

Replying to SimonKing:

To clarify this point (and it might be helpful to put something along these lines in the documentation), ...

But where?

The thematic tutorial coercion_and_categories would be a natural place, but would it be enough? Granted, the doc of register_embedding, register_coercion and install_coercion should refer to each other and elaborate on the different use cases and should also mention _coerce_map_from_.

comment:106 Changed 14 months ago by SimonKing

With vanilla public/sage-git/master, I find that sage -t --all results in 1083022 calls to Parent.__init__, while with the branch from here it is called 1129534 times.

Hence, there is an increase in the number of parents being created. No surprise, since this ticket is about making parents garbage collectable in some situations.

Nevertheless, it might make sense to see whether some types of parents show a particularly strong increase, so that we can then decide whether we should have some stronger cache for these types.

comment:107 follow-up: Changed 14 months ago by SimonKing

  • Cc nthiery added

I studied the differences in parent creation during sage -t --all in more detail.

Absolute differences

Here are the 10 classes that have the most additional creations in the ticket branch compared with the public/sage-git/master branch (the list shows the absolute number of additional creations and the name of the class):

(19873, 'sage.rings.homset.RingHomset_generic')
(16597, 'sage.categories.homset.Homset')
(2839, 'sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic')
(2270, 'sage.rings.homset.RingHomset_quo_ring')
(2137, 'sage.rings.finite_rings.homset.FiniteFieldHomset')
(1960, 'sage.rings.number_field.morphism.NumberFieldHomset')
(1279, 'sage.sets.positive_integers.PositiveIntegers')
(851, 'sage.combinat.tableau.Tableaux_all')
(831, 'sage.modules.free_module_homspace.FreeModuleHomspace')
(481, 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_p')

Here are the "bottom 10" classes. As you can see, there are parents for which we have considerably less creations with the ticket than without, which comes as a surprise to me:

(-57, 'sage.sets.family.LazyFamily')
(-134, 'sage.combinat.words.words.Words_all')
(-134, 'sage.combinat.permutation.StandardPermutations_all')
(-136, 'sage.combinat.permutation.Permutations_set')
(-142, 'sage.combinat.subset.Subsets_sk')
(-158, 'sage.sets.non_negative_integers.NonNegativeIntegers')
(-166, 'sage.combinat.cartesian_product.CartesianProduct_iters')
(-170, 'sage.combinat.integer_list.IntegerListsLex')
(-253, 'sage.combinat.skew_partition.SkewPartitions_rowlengths')
(-3838, 'sage.sets.set.Set_object_enumerated')

Relative differences

Here are the 10 classes that have the biggest relative increase in number of creations (ticket compared with master):

+14.67% sage.combinat.tableau.Tableaux_all
+3.79% sage.combinat.skew_tableau.SemistandardSkewTableaux_all
+1.00% sage.combinat.skew_tableau.SkewTableaux
+1.00% sage.combinat.partition_tuple.PartitionTuples_all
+0.91% sage.rings.homset.RingHomset_quo_ring
+0.75% sage.categories.examples.sets_cat.PrimeNumbers_Facade
+0.67% sage.combinat.crystals.affine.AffineCrystalFromClassicalAndPromotion
+0.66% sage.groups.matrix_gps.homset.MatrixGroupHomset
+0.64% sage.combinat.partition_tuple.PartitionTuples_level
+0.60% sage.structure.list_clone_demo.IncreasingIntArrays

Here are the 10 classes with the biggest relative decrease in the number of creations:

-0.25% sage.combinat.crystals.kirillov_reshetikhin.KR_type_A2_with_category
-0.25% sage.combinat.crystals.kirillov_reshetikhin.KR_type_A2
-0.25% sage.categories.examples.finite_monoids.IntegerModMonoid
-0.33% sage.sets.integer_range.IntegerRangeEmpty
-0.33% sage.combinat.affine_permutation.AffinePermutationGroupTypeG
-0.33% sage.combinat.affine_permutation.AffinePermutationGroupTypeC
-0.38% sage.combinat.crystals.infinity_crystals.InfinityCrystalOfTableauxTypeD
-0.39% sage.combinat.permutation.CyclicPermutations
-0.40% sage.combinat.vector_partition.VectorPartitions
-0.54% sage.combinat.composition_tableau.CompositionTableaux_all

Conclusion

Even though the absolute differences in the creation of various kinds of homsets seem to be dramatic, the relative differences suggest that there is no serious problem here. There are only four classes that show an increase of at least 1%. Three of them are related with tableaux, that's why I add Nicolas to the ticket: Perhaps we want to change the cache for tableaux?

comment:108 Changed 14 months ago by SimonKing

Concerning a new method install_coercion: Wouldn't it be easier to provide register_coercion with an optional argument permanent=True, so that using the method with permanent=False would do what you suggested for install_coercion? I guess having two methods install_coercion and register_coercion could confuse the user.

comment:109 Changed 14 months ago by SimonKing

Concerning documentation: I just found that the underscore methods of sage.structure.parent.Parent are documented in the reference manual. Hence it should be no problem to add documentation of _coerce_map_from_ directly in-place.

comment:110 follow-up: Changed 14 months ago by SimonKing

And I just notice that the documentation of the module sage.structure.parent starts with a "simple example of registering coercions", which I find rather obscure and which does things in a way that we would do differently today. E.g., it does not initialise the category, but overrides the method category(). And it calls self._populate_coercion_lists_(), which I have never seen in code created in the past few years.

Hence, I'll update this example.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:111 in reply to: ↑ 110 ; follow-up: Changed 14 months ago by SimonKing

Replying to SimonKing:

And I just notice that the documentation of the module sage.structure.parent starts with a "simple example of registering coercions", which I find rather obscure and which does things in a way that we would do differently today. E.g., it does not initialise the category, but overrides the method category(). And it calls self._populate_coercion_lists_(), which I have never seen in code created in the past few years.

Hence, I'll update this example.

Hm. I am undecided.

Perhaps it would be better to focus here on fixing the memory leak (which, I think succeeded), only documenting with examples that it has worked.

Hence, on this ticket, I would just

  • provide missing docs for SchemeMorphism
  • Let the string representation of a weakened map consist of a warning to not use this map outside of the coercion framework.
  • Perhaps: Re-introduce a cdef public attribute _codomain, since this would allow faster access than calling .codomain(), and since the codomain will be strongly referenced anyway.

Everything else should perhaps better be done on a follow-up ticket:

  • Add documentation explaining the current weak coercion model, to facilitate maintanance,
  • Add permanent=True option to register_coercion().

What do you think?

comment:112 Changed 14 months ago by git

  • Commit changed from 05fb569cb132a8c89713021f1f4b25cd2dd7cb1c to 452d21629d4531d8e117e869b65bac0ab350c1ee

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:452d216]Add docs to SchemeMorphism?

comment:113 Changed 14 months ago by SimonKing

I think there is a further technical thing I could do in the next commit: I have implemented __copy__ for some types of morphisms. But there already exist methods called _extra_slots() and _update_slots(), and I think in order to implement copying one should update these. This might (on a different ticket) also help to provide a default pickling for maps.

comment:114 Changed 14 months ago by git

  • Commit changed from 452d21629d4531d8e117e869b65bac0ab350c1ee to 5168cfd15d4cdbaa3ffdbd4be0f7d783f77257c7

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:5168cfd]Generic copy method for maps, using _update_slots Use a cdef _codomain, since the codomain is strongly refed anyway Add doctests

comment:115 in reply to: ↑ 111 Changed 14 months ago by SimonKing

Replying to SimonKing:

Perhaps it would be better to focus here on fixing the memory leak (which, I think succeeded), only documenting with examples that it has worked.

Hence, on this ticket, I would just

  • provide missing docs for SchemeMorphism

Done in the current commit.

  • Perhaps: Re-introduce a cdef public attribute _codomain, since this would allow faster access than calling .codomain(), and since the codomain will be strongly referenced anyway.

Done in the current commit.

In addition, I changed the new generic __copy__ method of maps so that it uses _update_slots and _extra_slots. This complies with how currently pickling is implemented by default. For several types of maps, I implemented copying accordingly.

  • Let the string representation of a weakened map consist of a warning to not use this map outside of the coercion framework.

Still todo.

Everything else should perhaps better be done on a follow-up ticket:

  • Add documentation explaining the current weak coercion model, to facilitate maintanance,
  • Add permanent=True option to register_coercion().

Do you agree that this shall be on a different ticket?

Last edited 14 months ago by SimonKing (previous) (diff)

comment:116 in reply to: ↑ 107 ; follow-up: Changed 14 months ago by nthiery

Replying to SimonKing:

Even though the absolute differences in the creation of various kinds of homsets seem to be dramatic, the relative differences suggest that there is no serious problem here. There are only four classes that show an increase of at least 1%. Three of them are related with tableaux, that's why I add Nicolas to the ticket: Perhaps we want to change the cache for tableaux?

Could you post a quick summary (say in the ticket description/title)
of what the current patch does?

Thanks!

comment:117 in reply to: ↑ 116 Changed 14 months ago by SimonKing

  • Description modified (diff)
  • Summary changed from Memleak when creating QuadraticField to Weak references in the coercion graph

Replying to nthiery:

Could you post a quick summary (say in the ticket description/title)
of what the current patch does?

Done. OK, the summary is actually not quick. Sorry.

comment:118 Changed 14 months ago by SimonKing

  • Description modified (diff)
  • Status changed from needs_review to needs_work
  • Work issues set to String repr. of weakened maps; copying/pickling of maps

I think changing the string representation of weakened maps should be done here. And then, in a couple of tests, one needs to copy the map in order to get the test pass.

Therefore, I suggest to implement copying for all maps here as well, not on a different ticket. After all, it is not difficult: One just looks at the list of cdef attributes, and implements _extra_slots and _update_slots taking exactly these attributes into account. The only difficulty is to really catch all kinds of maps.

Note that in most cases phi == loads(dumps(phi)) would return False, but this is since comparison of maps is often not implemented---and this is what I will certainly not attempt to implement here.

comment:119 follow-up: Changed 14 months ago by SimonKing

I wonder: Would it make sense to implement a generic comparison for maps, based on the dictionary returned by self._extra_slots({})? Namely, these data are used for pickling and copying of maps, and thus it seems reasonable to me that two maps are equal if and only if the pickling data coincide.

What do you think? Worth trying? Better be done on a different ticket?

comment:120 in reply to: ↑ 119 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

I wonder: Would it make sense to implement a generic comparison for maps, based on the dictionary returned by self._extra_slots({})? Namely, these data are used for pickling and copying of maps, and thus it seems reasonable to me that two maps are equal if and only if the pickling data coincide.

And the "weakened" copies of maps (with in the near future an easily distinguished string rep) would be equal to their counter parts? That may well be a desirable choice, but by no means uncontroversial. I don't think in coercion we ever depend on equality testing on maps do we? I think it's better done on a separate ticket.

Another suggestion about how to get the the strong references in for register_coercion. If the maps put in by register_coercion are used afterwards many times to derive other cached coercion maps from, it would perhaps be preferable to have them in a form that is readily usable for that, i.e., as "weakened" maps (it means the map can go straight into map compositions etc.). Otherwise we may well end up making copies repeatedly in the coercion framework.

We could get the strong connections in by, for instance, referencing the domains explicitly, say on an attribute _domains_with_registered_coercions_to_here. The coercion map itself could simply live in the normal cache, as a weakened map.

The same applies to _register_embedding, although perhaps the coercion discovery treats the store differently, and storing a strong reference to even a weakened map implies a strong reference to the codomain.

Other question, does _parent=None imply a weakened map? (I guess isinstance(_domain,weakref.ref) definintely does) or are there other reasons for the parent to be unset?

comment:121 in reply to: ↑ 120 ; follow-up: Changed 14 months ago by SimonKing

Replying to nbruin:

And the "weakened" copies of maps (with in the near future an easily distinguished string rep) would be equal to their counter parts?

Of course. Equality does (and should) not depend on weak references, I think

I don't think in coercion we ever depend on equality testing on maps do we?

We don't. Otherwise, people would have had comparison implemented already.

I think it's better done on a separate ticket.

Agreed.

Concerning "near future": I am already testing a new commit that provides

  • special string representation for weakened maps
  • copying for all maps and morphisms (at least those that I was able to find in the sources). It was very dull work: Look up the cdef slots, implement _extra_slots and _update_slots, add a test...
  • Use the copy functionality on most tests that expose coerce maps. Hence, I replace
    sage: R.coerce_map_from(P)
    ...
    
    by
    sage: copy(R.coerce_map_from(P))
    
    and also add a link to this ticket. Not everywhere, but in most places.

Another suggestion about how to get the the strong references in for register_coercion. If the maps put in by register_coercion are used afterwards many times to derive other cached coercion maps from, it would perhaps be preferable to have them in a form that is readily usable for that, i.e., as "weakened" maps (it means the map can go straight into map compositions etc.). Otherwise we may well end up making copies repeatedly in the coercion framework.

Why do you think they would/should be copied inside of the coercion model? I thought we already had agreed that copying is needed when exposing a coerce map to the user (this is why I suggested that the string repr contains a warning!). But certainly not internally. This would be by far too slow.

Suppose you have two non-weakened maps phi and psi, and then do chi = phi*psi (a composite map). When you then weaken chi, neither phi nor psi would be changed. So, why copying?

We could get the strong connections in by, for instance, referencing the domains explicitly, say on an attribute _domains_with_registered_coercions_to_here.

This is already done in my current branch, and it is called _registered_domains (simply a list).

The coercion map itself could simply live in the normal cache, as a weakened map.

No, because we need some container that only stores those maps that are considered in the backtracking algorithm. So, the current separate list _coerce_from_list must be preserved.

The same applies to _register_embedding, although perhaps the coercion discovery treats the store differently, and storing a strong reference to even a weakened map implies a strong reference to the codomain.

All weakened maps still have a strong reference to the codomain. Only the reference to the domain will be weak. And register_embedding is still simply assigning the embedding to an attribute _embedding of the domain.

Other question, does _parent=None imply a weakened map? (I guess isinstance(_domain,weakref.ref) definintely does) or are there other reasons for the parent to be unset?

I guess one could test self._parent is None, rather than typetest stuff. This should actually be faster.

Concerning "reasons": The parent is unset, because otherwise we have a chain of references from the map to the domain, namely via the parent (i.e., the homset). Hence, having a weak reference from the map to the domain would be futile if there is a reference from the map to its parent. Note that alternatively one could have a weak reference from the homset to the domain. But I think we have agreed above that we don't want this as a default.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:122 in reply to: ↑ 121 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

Suppose you have two non-weakened maps phi and psi, and then do chi = phi*psi (a composite map). When you then weaken chi, neither phi nor psi would be changed. So, why copying?

Well, if you'd do that then chi wouldn't really be a weakened map. Assuming maps act on the left, i.e. chi.domain()=psi.domain(), the resulting structure would have a strong reference to its domain, via psi.domain().

The converse, making a strong composite out of weakened maps, shouldn't be a problem at all (except that if people start looking at the components, they'd be able to get their hands on weakened maps).

I think the coercion system makes a lot of map compositions, and they usually would have to be weakened. That's why it might be worth ensuring that the maps stored internally are already weakened.

This is already done in my current branch, and it is called _registered_domains (simply a list).

And the maps inserted into _coerce_from_hash are weakened or not? Conceptually it would be a little easier if all of them are. Perhaps enforcing such a rule (or at least change most code to comply) is too costly, though.

No, because we need some container that only stores those maps that are considered in the backtracking algorithm. So, the current separate list _coerce_from_list must be preserved.

Ah. I didn't realize that. You say that _coerce_from_hash is not considered by backtracking. Indeed, that changes things. In that case, _coerce_from_list could be a "weak set" (e.g., a WeakValueDictionary with trivial keys), since the maps are kept alive by their entries in _coerce_from_hash, where the key is kept alive by the _registered_domains. This would get rid of the garbage collection problem, if we ever want to have maps that help coercion discovery but don't have lifetime implications.

(this should go on a different ticket)

Last edited 14 months ago by nbruin (previous) (diff)

comment:123 Changed 14 months ago by git

  • Commit changed from 5168cfd15d4cdbaa3ffdbd4be0f7d783f77257c7 to 364b9856b28d7060e3ea9825144de66c8f11ca2a

Branch pushed to git repo; I updated commit sha1. New commits:

[changeset:364b985]Add warning to string repr of weakened maps. Implement copying for *all* kinds of maps.

comment:124 in reply to: ↑ 122 Changed 14 months ago by SimonKing

Replying to nbruin:

Replying to SimonKing:

Suppose you have two non-weakened maps phi and psi, and then do chi = phi*psi (a composite map). When you then weaken chi, neither phi nor psi would be changed. So, why copying?

Well, if you'd do that then chi wouldn't really be a weakened map. Assuming maps act on the left, i.e. chi.domain()=psi.domain(), the resulting structure would have a strong reference to its domain, via psi.domain().

Correct. Would this be a problem? Let's see:

Let psi: A -> B and phi: B -> C be coerce maps, hence, chi=phi*psi: A -> C is a coerce map as well. Assume that we have done B.register_coercion(psi), so that B prevents A from garbage collection. Assume that phi is only stored in C._coerce_from_hash, i.e., C would not prevent B from garbage collection. In other words, we assume that phi is weakened but psi isn't.

Let us assume first that we did not discover chi as a coercion yet. If we have a strong reference to C but no external reference to B, then B and A could of course be garbage collected.

Now, let us assume that we did discover that chi is a coercion and put it into C._coerce_from_hash, in the attempt of weakening it. C would have a strong reference to chi, which has a strong reference to its first map, psi, which has a strong reference to both its domain A and codomain B. Hence, C would prevent both A and B from garbage collection.

I think this indeed qualifies as a memory leak, according to the definition I gave in some post above.

Difficult. Can this be solved, even with copying? I have to think about it.

This is already done in my current branch, and it is called _registered_domains (simply a list).

And the maps inserted into _coerce_from_hash are weakened or not?

In my current branch, it is not weakened. Perhaps it should be. It would indeed be conceptually easier if a map is in the coercion system if and only if it is weakened. One could do it, since _registered_domains would keep the domain alive, Note, however, that this would not suffice for fixing the memory leak described above. We would still have that chi refers to psi, which strongly refers to its codomain B (the codomain is always strong), and then B._registered_domains strongly refers to A.

In this situation,

  • we want to have a strong reference from B to A, since we used B.register_coercion(mor).
  • we must not have a strong reference from C to A, since chi was discovered but not registered.
  • we must not have a strong reference from C to B, since phi was not registered.
  • we could live with a strong reference from A to B, I guess.

If C is alive, then we want that it does not prevent A or B from garbage collection. But if both A and C are alive, then chi must remain a valid map, hence, B must be prevented from garbage collection. It follows that if C is alive then either A and B get collected together, or they both stay alive.

I should catch some sleep now, perhaps I'll find a solution to the puzzle tomorrow.

comment:125 Changed 14 months ago by SimonKing

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Work issues String repr. of weakened maps; copying/pickling of maps deleted

With the new commit I have pushed today, all doctest should pass.

comment:126 follow-up: Changed 14 months ago by SimonKing

Let me elaborate a bit more on the memory leak from comment:124.

First of all, this leak is not introduced by my branch. Hence, it would probably be better to attempt a fix on a different ticket, as the changes introduced in my branch already are big enough.

Now for a deeper analysis of what happens. I want to argue that there is
only one scenario in which this leak occurs. This scenario rarely occurs
and can easily be avoided.

Let phi: A -> B and psi: B -> C be maps (sorry for changing the names
compared with comment:124...), and define chi = psi*phi: A -> C. We assume that phi and psi are coerce maps, and thus chi is a coerce
map as well, but initially Sage is not aware of chi.

chi could be registered (i.e., C.register_coercion(chi)), it could be that
C._coerce_map_from_(A) provides a shortcut, or it could be that chi is
discovered by the backtracking algorithm of the coercion system.

Registering chi

Of course, if chi is explicitly registered as a coercion, then C will (with
the current code!!) keep A alive, and in order to not invalidate chi, B will
be kept alive as well. I don't consider this a memory leak, since it is an
explicit registration.

_coerce_map_from_

Typically, C._coerce_map_from_(A) just returns True, None or False, and not
a map. If it returns true, then a direct conversion chi' from A to C is
stored as coercion. Note that chi' is not a composite map. So, we would be
in a totally different situation. Since chi' has no reference to B, to phi
or to psi, there is no leak in this case.

Theoretically, C._coerce_map_from_(A) could return the composite map
chi. This would be possible, and it would create a memory leak. Hence, we
learn that _coerce_map_from_ should better not return a composite map. I
don't think we can automatically avoid a leak in this case.

Discovering chi by backtracking

We need to distinguish cases, since there are different ways of how the
coercion system became aware of phi and psi.

The punchline is: If chi is discovered by backtracking then psi is
stored in C._coerce_from_list.
Without psi being on this list,
backtracking won't find chi.

Hence, there has C.register_coercion(psi) been done. With the current code, it
means that C will keep B alive.

There remain only three cases:

  1. Assume that phi is a registered coercion. Hence, with the current code, B keeps A alive, and still C will keep B alive. Hence, C also keeps A alive. Adding chi to C._coerce_from_hash[A] won't change these lifetime dependencies. No leak.
  1. Assume that phi is a coerce embedding. Hence, A will keep B alive, and still C will keep B alive, but neither C nor B keep A alive. In particular, phi is weakened, so that there is no strong reference from phi to A. Adding chi to C._coerce_from_hash[A] will not change these lifetime dependencies, since the key A is only weakly referenced. No leak.
  1. Assume that phi has been discovered by backtracking or has been provided by B._coerce_map_from_(A) as a short-cut. In particular, it is weak and only has a weak reference to A. Then, still C keeps B alive, but B does not keep A alive, nor does A keep B alive, and C will also not keep A alive. If we put C._coerce_from_hash[A]=chi, then again C will not prevent A from garbage collection, since A is only weakly referenced in the MonoDict, and if there is no external reference to C, then a strong reference to A will not be enough to keep B alive. No leak.

Conclusion

A composite map can only arise in the coercion system, (1) if it is explicitly
registered, or (2) if the second map of the composition is explicitly
registered, or (3) if the composite map is returned by _coerce_map_from_.

I think case (1) does not constitute a leak. I have shown that there is no
memory leak in case (2). Case (3) is a leak, but this case can easily be
avoided by returning a "simple" map that is mathematically equivalent to the
composite map.

comment:127 Changed 14 months ago by SimonKing

PS: Since teaching will start next week for me, I will probably not be able to fix the leak from comment:124, even if you succeed to convince me that it really is a leak. So, I guess it is safe to start reviewing the attached branch, I think it will not change in the next few days...

comment:128 follow-up: Changed 14 months ago by SimonKing

PPS: I just found that Sage's coercion system is clever enough to find a composite map if phi is registered as coerce embedding and psi is a short-cut:

sage: A = Aclass()
sage: B = Bclass()
sage: C = Cclass()
sage: phi = sage.categories.map.Map(A,B)
sage: A.register_embedding(phi)
sage: psi = C.coerce_map_from(B)
sage: print psi
Generic map:
  From: <class '__main__.Bclass'>
  To:   <class '__main__.Cclass'>

        WARNING: This map has apparently been used internally
        in the coercion system. It may become defunct in the next
        garbage collection. Please use a copy.
sage: print phi
Generic map:
  From: <class '__main__.Aclass'>
  To:   <class '__main__.Bclass'>

        WARNING: This map has apparently been used internally
        in the coercion system. It may become defunct in the next
        garbage collection. Please use a copy.
sage: C.coerce_map_from(A)
Composite map:
  From: <class '__main__.Aclass'>
  To:   <class '__main__.Cclass'>

        WARNING: This map has apparently been used internally
        in the coercion system. It may become defunct in the next
        garbage collection. Please use a copy.

Here, before discovering and caching the composite map, A keeps B alive because of the embedding, and C neither keeps A nor B alive. After caching the composite map, A still keeps B alive, and C still does not keep A alive, because it only occurs as weak key in a MonoDict.

But we have

sage: del psi, B, A
sage: import gc
sage: _ = gc.collect()
sage: len([x for x in gc.get_objects() if isinstance(x,Aclass)])
0
sage: len([x for x in gc.get_objects() if isinstance(x,Bclass)])
1

So, why is B not garbage collected? To be investigated, I need to hurry now.

Last edited 14 months ago by SimonKing (previous) (diff)

comment:129 in reply to: ↑ 128 ; follow-up: Changed 14 months ago by SimonKing

Replying to SimonKing:

sage: del psi, B, A
sage: import gc
sage: _ = gc.collect()
sage: len([x for x in gc.get_objects() if isinstance(x,Aclass)])
0
sage: len([x for x in gc.get_objects() if isinstance(x,Bclass)])
1

So, why is B not garbage collected? To be investigated, I need to hurry now.

Argh. Because simply I forgot to delete phi...

Let's try again, this time without leaving a reference to the maps.

sage: import gc
sage: class Aclass(Parent): pass                  
sage: class Bclass(Parent): pass                  
sage: class Cclass(Parent):                       
....:    def _coerce_map_from_(self, P):
....:        if isinstance(P, Bclass):
....:            return sage.categories.map.Map(P,self)
....:         
sage: A = Aclass()
sage: B = Bclass()
sage: C = Cclass()
sage: A.register_embedding(sage.categories.map.Map(A,B))
sage: C.has_coerce_map_from(A)
True
sage: del A,B
sage: gc.collect()
862
sage: len([x for x in gc.get_objects() if isinstance(x,Aclass)])
0
sage: len([x for x in gc.get_objects() if isinstance(x,Bclass)])
0

So, no leak.

I think my analysis is now complete: A memory leak caused by composite coerce maps will only arise if C._coerce_map_from_(A) returns the composite map. I have also shown that there is no need to let C._coerce_map_from_(A) return a composite map.

Hence, I would argue that C._coerce_map_from_(A) returning a composite map is a misuse. Granted, it is far from obvious that it is a misuse. I feel tempted to investigate how often composite maps are actually returned by _coerce_map_from_.

comment:130 in reply to: ↑ 129 Changed 14 months ago by SimonKing

Replying to SimonKing:

Hence, I would argue that C._coerce_map_from_(A) returning a composite map is a misuse. Granted, it is far from obvious that it is a misuse. I feel tempted to investigate how often composite maps are actually returned by _coerce_map_from_.

For example, I found that during startup of Sage composite maps are returned by Q._coerce_map_from_(P) for the following values of P, Q:

Coercion Rational Field to Complex Field with 2 bits of precision
Coercion Rational Field to Complex Field with 53 bits of precision
Coercion <type 'int'> to Univariate Polynomial Ring in x over Integer Ring
Coercion Integer Ring to Complex Field with 2 bits of precision
Coercion <type 'int'> to Complex Field with 53 bits of precision
Coercion <type 'int'> to Real Interval Field with 53 bits of precision
Coercion <type 'int'> to Univariate Polynomial Ring in x over Rational Field
Coercion <type 'int'> to Real Interval Field with 64 bits of precision
Coercion Complex Lazy Field to Complex Double Field
Coercion <type 'int'> to Univariate Polynomial Ring in x over Algebraic Real Field

I guess in all of these cases the domain and the "middle parent" will be immortal anyway.

comment:131 in reply to: ↑ 126 ; follow-up: Changed 14 months ago by nbruin

Replying to SimonKing:

First of all, this leak is not introduced by my branch. Hence, it would probably be better to attempt a fix on a different ticket, as the changes introduced in my branch already are big enough.

Agreed.

Typically, C._coerce_map_from_(A) just returns True, None or False, and not
a map. If it returns true, then a direct conversion chi' from A to C is
stored as coercion.

Hm, I agree that the references are in that case out of reach of what we're considering here, but all this is saying is "it is okay to use conversion as a coercion from A to C". This conversion still has to be programmed/stored/discovered somewhere, so I'd expect that some conversion cache might be liable to hold a strong reference.

The punchline is: If chi is discovered by backtracking then psi is
stored in C._coerce_from_list.
Without psi being on this list,
backtracking won't find chi.

Hence, there has C.register_coercion(psi) been done. With the current code, it
means that C will keep B alive.

Right, I was already expecting something along these lines when you explained the function of coerce_from_list: The backbone of the coercion framework presently requires lifetime specifications to be explicit and it seems this is not just a by-product of the implementation, it seems to be part of the spec. That's fine by itself. Whether having such implications is sufficient for sage in the future remains to be seen, but changing that is a redesign problem that would need to be carefully considered (just as it might be desirable to allow multiple embeddings to be registered)

As a consequence, in the present model, register_coercion(...,strong=false) would not be advisable.

Case (3) is a leak, but this case can easily be
avoided by returning a "simple" map that is mathematically equivalent to the
composite map.

This would be a necessary step to avoid the leak, and all the coercion system can do, but if programmed in a generic way, the references causing the leak would likely still be present internally.

comment:132 in reply to: ↑ 131 ; follow-up: Changed 14 months ago by SimonKing

Replying to nbruin:

The punchline is: If chi is discovered by backtracking then psi is
stored in C._coerce_from_list.
Without psi being on this list,
backtracking won't find chi.

Modulo the oversight I have corrected in my previous posts:

If a composed map chi is discovered by backtracking, then either the second map is registered as a coercion (hence, C keeps B alive) or the first map is the coerce embedding of A (hence, A keeps B alive). But, as I have shown, storing the composed map as coercion from A to C (in C._coerce_from_hash[A]) does not cause a leak, at least not with the attached branch.

Right, I was already expecting something along these lines when you explained the function of coerce_from_list: The backbone of the coercion framework presently requires lifetime specifications to be explicit and it seems this is not just a by-product of the implementation, it seems to be part of the spec. That's fine by itself. Whether having such implications is sufficient for sage in the future remains to be seen, but changing that is a redesign problem that would need to be carefully considered

Agreed. Currently, the coercion system operates on a virtual digraph, and I could actually imagine that this digraph could become an actual object with a fast graph backend. This might give more flexibility for our coercion system. But this would require a major rewrite.

(just as it might be desirable to allow multiple embeddings to be registered)

Why? What should be done with these embeddings?

comment:133 in reply to: ↑ 132 Changed 14 months ago by nbruin

Replying to SimonKing:

Why? What should be done with these embeddings?

I don't have a direct application in mind (hence the might), but just for symmetry it seems appropriate.

One possible example would be someone working on some weak approximation problem, having a whole bunch of number fields K with specified embeddings in CC as well as Qp (for some p). In this application, Qp may well be just as immortal as CC is, so using register_coercion would not express the right life time implications: The K should get deleted while Qp remains, just as CC remains.

This would be accomplished by letting K have embeddings in both CC and Qp. I'm not claiming at this point that using coercion is the most appropriate tool to express the relations in this scenario.

There is one benefit one gets from having maps recognized as coercions: A lot of derived structures can now be automatically get built with the appropriate maps between them via pushout constructions. If you just have some maps lying around, constructing the corresponding derived maps will be a lot of work.

That's my reason to really care about an expressive coercion system. My experience with magma, which tends to have a much more restricted notion of coercion, has taught me that building these maps can be a *lot* of silly work. It would be great if one could "borrow" the coercion system for that every now and again (this is one of the reasons why I think some context manager that can put in "temporary" coercions would be great: inside the context manager one would request the derived map, store it, and then return the coercion system to its original state)

comment:134 follow-up: Changed 14 months ago by nbruin

I'm not so sure that the coercion system was designed with embeddings as an alternative to registered coercions: If you register a map only as an embedding (and not also as a coercion on the codomain) you can end up with the coercion system yielding non-transitive results:

class pA(Parent): pass
class pB(Parent): pass
class pC(Parent): pass

A=pA()
B=pB()
C=pC()

BtoA=Hom(B,A)(lambda x: A(x))
AtoC=Hom(A,C)(lambda x: C(x))
A.register_coercion(BtoA)
A.register_embedding(AtoC)

C.coerce_map_from(A) #finds the right map
A.coerce_map_from(B) #finds the right map
C.coerce_map_from(B) #returns none!

(other combinations of using register_coercion and register_embedding do lead to the appropriate discovery)

so, if we want to view the coercion framework as a digraph and valid coercions as paths in this digraph, then an arbitrary combination of register_embedding and register_coercion may lead to invalid manipulations of the graph (i.e., leading to a state where the system fails to provide consistent (transitive) results).

This wasn't such a problem before, but since we are now tying lifetime implications to how a coercion is registered, I think it now becomes apparent.

Last edited 14 months ago by nbruin (previous) (diff)

comment:135 in reply to: ↑ 134 ; follow-ups: Changed 14 months ago by SimonKing

Replying to nbruin:

{{{
A.register_coercion(BtoA)
A.register_embedding(AtoC)

C.coerce_map_from(A) #finds the right map
A.coerce_map_from(B) #finds the right map
C.coerce_map_from(B) #returns none!
}}}

IF this is a bug then it should be dealt with on a new ticket. Note, however, that C can not know about the embedding of A into C, and not even about the mere existence of A. So, how could it possibly be aware of a coercion from B to C via A? Hence, I am not sure if this qualifies as a bug or as a misuse.

This wasn't such a problem before, but since we are now tying lifetime implications to how a coercion is registered, I think it now becomes apparent.

I don't quite follow this argument. Anyway, I should now do some more project related work, namely #12630,

comment:136 in reply to: ↑ 135 Changed 14 months ago by nbruin

Replying to SimonKing:

IF this is a bug then it should be dealt with on a new ticket.

Agreed.

Note, however, that C can not know about the embedding of A into C, and not even about the mere existence of A.

Are you suggesting that C.coerce_map_from(A) already fails? If we follow the
digraph model for coercion, then whether there's a path from A to C is a
property of the graph, not something the vertices "know" about. Perhaps the
following more symmetrically formulated code (which does the same thing anyway)
is more convincing:

sage: G=get_coercion_model()
sage: G.discover_coercion(A,C)
(Generic morphism ..., None)
sage: G.discover_coercion(B,A) #currently unweakened with your patch!
(Generic morphism ..., None)
sage: sage: G.discover_coercion(B,C)
None

So, how could it possibly be aware of a coercion from B to C via A?
Hence, I am not sure if this qualifies as a bug or as a misuse.

Are you claiming that register_embedding is not supposed to add edges to the
same graph as register_coercion does? I don't see how that would lead to a
useful model.

This wasn't such a problem before, but since we are now tying lifetime
implications to how a coercion is registered, I think it now becomes apparent.

I don't quite follow this argument.

As the documentation of register_embedding shows, it was originally considered
to be a rather non-essential component; just some coercion map that gets
"blessed" as a particularly canonical one, but doesn't actually has a
very different effect (in fact, as we see, really a more limited effect), so
people would just have used register_coercion or (even more flexible)
_coerce_map_from_.

With less strong references, there is more reason to use register_embedding:
it expresses that the domain should keep the codomain alive rather than the
other way around; the kind of thing that wouldn't be expressed usefully before
anyway.

comment:137 in reply to: ↑ 135 Changed 14 months ago by nbruin

Replying to SimonKing:

Replying to nbruin:

A.register_coercion(BtoA)
A.register_embedding(AtoC)

C.coerce_map_from(A) #finds the right map
A.coerce_map_from(B) #finds the right map
C.coerce_map_from(B) #returns none!

IF this is a bug then it should be dealt with on a new ticket.

This is now #15303.

comment:138 follow-up: Changed 13 months ago by darij

Any info what exactly slowed down the tableaux classes?

comment:139 Changed 13 months ago by git

  • Commit changed from 364b9856b28d7060e3ea9825144de66c8f11ca2a to 23f18f23c38b104364ba499b4d4db8683480b895

Branch pushed to git repo; I updated commit sha1. New commits:

23f18f2Merge branch 'master' into ticket/14711

comment:140 in reply to: ↑ 138 Changed 13 months ago by SimonKing

FWIW, I have merged the current master branch into the branch from here. I had to resolve some merge conflicts. So, I hope I did right.

Replying to darij:

Any info what exactly slowed down the tableaux classes?

I did not state (in comment:107) that tableaux classes became slower. All what I stated was: If you run the complete doc tests of Sage, then you will find that more parent creations occur with the branch than with vanilla Sage---and the tableaux classes show the largest relative increase.

I don't even state that this is bad. Apparently there are doctests that would in vanilla Sage re-use tableaux that have been created in other doctests. This branch fixes a leak. Hence, some tableaux are garbage collected between doctests.

IF the tableaux developers believe that tablaux should be more strongly cached, then they should properly implement a stronger cache, rather than relying on the memory leak that is fixed in this ticket.

comment:141 Changed 13 months ago by darij

I'm not blaming your branch for slowing down tableaux! Actually, tableaux are probably doing a good job at slowing down themselves, and there's been a plan for quite a while now to rewrite their class hierarchy from scratch. But I want to know what exactly it is that causes these slowdowns in tableaux but nowhere else (kind of); that would probably an antipattern we should try to avoid.

Are there good ways of finding out

1) what causes the slowdown, and

2) how the branches compare on more realistic measurements rather than doctests (say, by dropping the cache between every doctest and the next one?)?

comment:142 Changed 12 months ago by jdemeyer

  • Milestone changed from sage-5.13 to sage-6.0

comment:143 follow-up: Changed 12 months ago by darij

Can't get this thing to compile:

darij@travis-virtualbox:~/gitsage/sage-5.13.beta1$ make build
cd build && \
	"../build/pipestatus" \
		"env SAGE_PARALLEL_SPKG_BUILD='' ./install all 2>&1" \
		"tee -a ../logs/install.log"

It seems to hang at this place...

comment:144 in reply to: ↑ 143 Changed 12 months ago by SimonKing

Replying to darij:

Can't get this thing to compile:

darij@travis-virtualbox:~/gitsage/sage-5.13.beta1$ make build
cd build && \
	"../build/pipestatus" \
		"env SAGE_PARALLEL_SPKG_BUILD='' ./install all 2>&1" \
		"tee -a ../logs/install.log"

It seems to hang at this place...

I have seen this a couple of times---not only here. Sometimes it even occurs when returning to vanilla sage. So, I believe it is not a problem of this branch, but a general problem. Of git? Of Sage's build system? No idea.

I had the impression that doing "pkill python" helps. Not sure though.

comment:145 Changed 12 months ago by SimonKing

  • Work issues set to Fix doctests errors after merging master

Some errors have emerged, at qsym.py, for example.

comment:146 Changed 12 months ago by git

  • Commit changed from 23f18f23c38b104364ba499b4d4db8683480b895 to d68c5df4618cc4fcf8ef215ee6b2f475be028209

Branch pushed to git repo; I updated commit sha1. New commits:

d68c5dfMinor fixes, that became needed since #14711 was not merged quickly enough
c42b539Merge branch 'master' into ticket/14711

comment:147 Changed 12 months ago by SimonKing

  • Status changed from needs_review to needs_work

The new commit fixes some trivial errors (some people were still using ._domain and were still not copying coerce maps when exposing them to the outside world).

However, this will be a tough one:

sage -t src/sage/schemes/projective/projective_morphism.py
**********************************************************************
File "src/sage/schemes/projective/projective_morphism.py", line 1326, in sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.canonical_height
Failed example:
    f.canonical_height(Q,badprimes=[2])
Expected:
    0.0013538030870311431824555314882
Got:
    verbose 0 (3533: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
    verbose 0 (3533: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
    0.0013538030870311431824555314882
**********************************************************************
1 item had failures:
   1 of  16 in sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.canonical_height
    [481 tests, 1 failure, 8.63 s]
----------------------------------------------------------------------
sage -t src/sage/schemes/projective/projective_morphism.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 8.9 seconds
    cpu time: 7.7 seconds
    cumulative wall time: 8.6 seconds

Somehow, the use of a weakened coerce map makes the Gröbner machinery use a slow toy implementation :-/

comment:148 Changed 12 months ago by SimonKing

I found how Gröbner basis computation comes into play: When calling a scheme morphism, a scheme is called, which involves for some map S to test S.codomain() == self. This comparison involves comparing ideals, and this means one needs to compute a Gröbner basis.

I only wonder why this comparison does not happen with strong maps. Also I need to study why the comparison is not by identity.

comment:149 Changed 12 months ago by SimonKing

Aha! It does not come from the weak maps, but it comes from the fact that my branch also changes the __call__ method of scheme morphisms (namely copying what happens in sage.categories.map`). So, this could be the problem.

comment:150 Changed 12 months ago by SimonKing

I will fix it, but this also means that conversion between different schemes will be more permissive. But I think this is consistent with the rest of Sage: Conversions are just supposed to somehow make sense of the input, whereas only coercions have to satisfy certain axioms.

comment:151 Changed 12 months ago by SimonKing

Too bad. We have to have check=True by default (that's convention in Sage). And since schemes are no unique parents, comparison of schemes will generally involve Gröbner basis computations.

I only hope that in this particular application we know that we are dealing with good input and thus can set check=False.

comment:152 Changed 12 months ago by git

  • Commit changed from d68c5df4618cc4fcf8ef215ee6b2f475be028209 to ee30c20b0adc9878a13c8286c96ee5e972e2b002

Branch pushed to git repo; I updated commit sha1. New commits:

ee30c20Address the "check" keyword of scheme morphisms by name, not position

comment:153 Changed 12 months ago by SimonKing

  • Status changed from needs_work to needs_review
  • Work issues Fix doctests errors after merging master deleted

With the new commit, all tests in sage.schemes pass. I guess this means "needs review" again!

comment:154 follow-up: Changed 12 months ago by nbruin

For (sub)scheme equality testing, should there be a fast path returning true for identical schemes? That would be a rather common case in the coercion system. There are of course other fast "true" cases: When ideals have the same generators then equality can be determined pretty quickly too. (it wouldn't surprise me if singular already had that optimization)

comment:155 in reply to: ↑ 154 ; follow-up: Changed 12 months ago by SimonKing

Replying to nbruin:

For (sub)scheme equality testing, should there be a fast path returning true for identical schemes?

Isn't this what happens when doing == in python?

There are of course other fast "true" cases: When ideals have the same generators then equality can be determined pretty quickly too. (it wouldn't surprise me if singular already had that optimization)

Indeed. But I think we already have a ticket for comparison of ideals---with the additional complication that the hash of ideals must involve a Gröbner basis computation as well.

comment:156 in reply to: ↑ 155 Changed 12 months ago by nbruin

Replying to SimonKing:

Isn't this what happens when doing == in python?

No it doesn't:

sage: class T(object):
....:     def __eq__(self,other):
....:         return False
....:     
sage: a=T()
sage: a == a
False

and in fact, there is a famous object in standard Python with this property:

sage: float(NaN)
nan
sage: nan=float(NaN)
sage: nan == nan
False

There is a documented optimization in dictionaries: Upon key lookup, identity is tested before equality is tried. This has odd consequences when NaN is used as a key in a dict: If you use the identical NaN, lookup will succeed, but not with any other NaN.

Indeed. But I think we already have a ticket for comparison of ideals---with the additional complication that the hash of ideals must involve a Gröbner basis computation as well.

Hm, that's not clear to me. In order to have a GOOD hash it seems something like a groebner basis needs to be involved. but for some applications using the same hash as the ring would also be a great hash. Of course, in many cases a groebner basis is going to be required anyway (are ideals with different monomial orders automatically non-equal?), so perhaps basing the hash on it isn't such a big deal.

It is an indication that ideals shouldn't be used as keys in dictionaries, where their hash would be required. In particular, it means schemes shouldn't be produced from an ideal (literally) but from a list of generators. Otherwise we're going to be in trouble if schemes ever were to become UniqueRepresentation?.

comment:157 Changed 12 months ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:158 follow-up: Changed 11 months ago by mmezzarobba

Hello everyone,

It looks like there has already been plenty of discussion about this branch, and stupid merge conflicts with develop accumulate while it is waiting for review. Could someone please clarify which parts of the changes still need review?

(Btw I just pushed u/mmezzarobba/ticket/14711 to resolve a trivial conflicts with the current develop branch. But it may be a better idea to wait until this branch is really ready to be merged and do a single merge.)

comment:159 Changed 11 months ago by SimonKing

The current master seems to merge cleanly (I didn't test develop, though). What is the policy (Volker?): Is it enough to review a ticket after merging with the current master branch? Or has the reviewer to take into account the develop branch, too?

comment:160 follow-up: Changed 11 months ago by SimonKing

All tests pass after merging master. But there is a conflict with #12217 (in the develop branch). I am now testing the merge I just did, and will push the resulting branch in case of success.

comment:161 in reply to: ↑ 160 ; follow-up: Changed 11 months ago by mmezzarobba

Replying to SimonKing:

All tests pass after merging master. But there is a conflict with #12217 (in the develop branch). I am now testing the merge I just did, and will push the resulting branch in case of success.

Is your merge different from mine? No need to run the tests if it is identical, I already did.

comment:162 Changed 11 months ago by git

  • Commit changed from ee30c20b0adc9878a13c8286c96ee5e972e2b002 to 37bf59eac24eda1ece89aff7dde4a1db5d0cbb5c

Branch pushed to git repo; I updated commit sha1. New commits:

37bf59eMerge branch 'develop' into ticket/14711, resolving conflicts with Trac 12217

comment:163 in reply to: ↑ 161 Changed 11 months ago by SimonKing

Replying to mmezzarobba:

Replying to SimonKing:

All tests pass after merging master. But there is a conflict with #12217 (in the develop branch). I am now testing the merge I just did, and will push the resulting branch in case of success.

Is your merge different from mine? No need to run the tests if it is identical, I already did.

No idea if they are identical, and no idea how one could even test whether they are identical.

Anyway, I pushed my version of the merge, since all tests in src/sage/rings/ passed and since the examples from the ticket description of #12217 and the description of this ticket are fixed.

comment:164 in reply to: ↑ 158 ; follow-up: Changed 11 months ago by SimonKing

Replying to mmezzarobba:

It looks like there has already been plenty of discussion about this branch, and stupid merge conflicts with develop accumulate while it is waiting for review. Could someone please clarify which parts of the changes still need review?

Actually I don't know. Nils?

comment:165 in reply to: ↑ 164 ; follow-up: Changed 11 months ago by nbruin

Replying to SimonKing:

Replying to mmezzarobba:

It looks like there has already been plenty of discussion about this branch, and stupid merge conflicts with develop accumulate while it is waiting for review. Could someone please clarify which parts of the changes still need review?

Actually I don't know. Nils?

I didn't look at code with the purpose of review, but to figure out if our solution was conceptually the right one.

In the current coercion framework, something along the lines of this patch is necessary to avoid lifetime problems as mentioned in the ticket, so I guess someone can just go ahead and carefully read if the code does what it supposed to do and doesn't add to the confusion the coercion framework is prone to. Ideally, the patch might fix some of the horrible name choices in the coercion framework.

The end result of our investigations was: The coercion framework is purposely messy. It wasn't clear at the time what model would work well, so the ball was kicked further down the road: The main tool is _coerce_map_from_ (note the underscores!) which is to be implemented by the author of a parent class and programmatically generates coercion maps. It is responsible for ensuring generating results that are consistent with the fact that path-connectedness is closed under composition.

In the light of that: The coercion system is not particularly designed to have any lifetime implications. Structures should keep related other structures alive by themselves (base rings etc.). So weakening lifetime implications as happens here should be OK.

comment:166 in reply to: ↑ 165 ; follow-up: Changed 11 months ago by SimonKing

Replying to nbruin:

In the current coercion framework, something along the lines of this patch is necessary to avoid lifetime problems as mentioned in the ticket, so I guess someone can just go ahead and carefully read if the code does what it supposed to do and doesn't add to the confusion the coercion framework is prone to.

Well, the history of this ticket certainly is confusing, as there has been some back and forth, and a mercurial patch would be a lot nicer.

Anyway, I guess in the end the patch can be summarised as follows:

The partially conflicting properties of Sage's coercion model are:

  • The coercion model uses a backtracking algorithm, relying on some maps that are explicitly provided during initialisation of the codomain, and it is also possible to provide a (single) embedding during initialisation of the domain. To keep the backtracking algorithm functional, it should not be allowed to garbage-collect these maps, as long as the codomain (resp. the domain of the embedding) is alive.
  • In addition to pure backtracking, the coercion model asks the codomain (via _coerce_map_from_) whether it knows a custom shortcut for coercion of the domain into the codomain.
  • For efficiency, the maps discovered by the "backtracking with shortcuts" model are cached. However, coerce maps cached in *this* way should not prevent any parent from garbage collection.

That's to say (@Nils): A coercion model (partially) relying on backtracking MUST have lifetime implications for the parents involved, simply to keep the backtracking algorithm functional. But ideally, all caching-for-efficiency and short-cutting done on top of backtracking algorithm should have no additional lifetime implications.

Currently, there are additional lifetime implications, and this ticket aims to remove some of them.

The approach is to "weaken" morphisms that are used in the coercion model.

  • Coerce maps discovered by backtracking-with-shortcuts are stored in a weak key dictionary that is an attribute of the codomain, keyed by the domain. Hence, if there is no chain of strong references to the domain, then the map can be collected. And also, if there is no chain of strong references to the codomain, then the codomain together with the weak key dictionary containing the maps can be collected.
  • The problem is that there could be two chains of strong references to the domain via the coerce map: One since the map has a strong reference to the domain, a second since the map has a strong reference to the homset it belongs to, which has a strong reference to the domain. So, the coerce map prevents itself from being collected in two ways.
  • But if the coerce map has only a weak reference to the domain and the homset, then this chains of strong references break, and hence nothing prevents the map from garbage collection, except of course there is a different chain of strong references to the domain.

So, this ticket introduces a method of maps for "weakening" the map: This
method is used when a map is put into the coerce cache, and it replaces the
strong reference to domain and homset by weak maps. A strong reference to the
codomain is kept, since (1) the map is stored in the codomain, so, a strong
reference from map to codomain is not more than a cyclic reference, and (2) it
is a way to keep composite maps alive (composite maps need to keep the "parent
in the middle" alive).

Of course, when a map only has a weak map to the domain, then it is possible
that the map becomes defunct: This is when you keep the map, then its domain
becomes collected, and afterwards you want to do something with the map. This
potential problem is addressed as follows:

  • If a weakened map stays inside of the coercion model, then it will always be collected, as soon as either domain or codomain are collected: If the domain is collected, then the corresponding item of the weak key dictionary is removed, and if the codomain is collected then the whole dictionary is removed.
  • Hence, we only have a problem if we take a map created by the coercion model and try to use it outside of the coercion model. With this ticket, this usage is declared to be a misuse. To make the user aware, a weakened map prints a big fat warning.
  • If one wants to use a map outside of the coercion model, one is supposed to use a copy of this map.

The last point is another benefit of this ticket: It is supposed to implement
copying (and thus, pickling!!) of all maps in Sage!

Ideally, the patch might fix some of the horrible name choices in the coercion framework.

That's not the purpose of this ticket.

The end result of our investigations was: The coercion framework is
purposely messy. It wasn't clear at the time what model would work well, so
the ball was kicked further down the road: The main tool is
_coerce_map_from_ (note the underscores!) which is to be implemented by the
author of a parent class and programmatically generates coercion maps.

That is only one tool. And if I am not mistaken about Sage's history,
_coerce_map_from_ was predated by a pure backtracking approach, that has
turned out to be not flexible enough.

It is responsible for ensuring generating results that are consistent with the fact that path-connectedness is closed under composition.

... which is dealt with on a different ticket. Please don't prevent this
ticket from review just because it only addresses one flaw of the current
coercion model.

In the light of that: The coercion system is not particularly designed to
have any lifetime implications.

I disagree. If you want something like backtracking (i.e., if you do not want
that _coerce_map_from_ is the only way to implement a coercion), then a
coercion model must have lifetime implications. But again, this ticket is
about removing some lifetime implication that is not a consequence of
backtracking, and I assume we both do agree that this implication should be avoided. Hence, the disagreement on a point that is not in the scope of this ticket should not prevent a review of this ticket.

comment:167 in reply to: ↑ 166 Changed 11 months ago by nbruin

Replying to SimonKing:

First of all, indeed someone SHOULD go ahead and review the ticket. I'm just not
comfortable with the sage coercion system (even after spending some time trying
to become familiar with it), so it's not me.

That's to say (@Nils): A coercion model (partially) relying on backtracking MUST have lifetime implications for the parents involved, simply to keep the backtracking algorithm functional. But ideally, all caching-for-efficiency and short-cutting done on top of backtracking algorithm should have no additional lifetime implications.

Apart from intermediate parents involved in composed maps: I don't think so. If
you're working with finitely generated structures then any homomorphism can be
given by images of generators, which in the end could be encoded as lists of
(lists of) integers. So the defining information of a homomorphism doesn't have
to hold explicit references to the (co)domain, and furthermore a composition of
homomorphisms doesn't have to refer to the homomorphisms it is composed of: one
just needs to store the images in the final codomain of the generators of the
initial domain. The homomorphism can then just store weak references to domain
and codomain to check that when it's used, the domain and codomain are still
available.

The last point is another benefit of this ticket: It is supposed to implement
copying (and thus, pickling!!) of all maps in Sage!

That's great.

Ideally, the patch might fix some of the horrible name choices in the coercion framework.

That's not the purpose of this ticket.

OK, I thought we had some steps in that direction somewhere; just not here then I guess.

[_coerce_map_from_] is only one tool. And if I am not mistaken about Sage's history,
_coerce_map_from_ was predated by a pure backtracking approach, that has
turned out to be not flexible enough.

Predated by a model that I think basically needed to be ripped out. If I'm not mistaken about a
conversation in 2007 with Robert, when he was working on the framework we have now, the idea was that
MOST parents would solve their coercions via this programmatic tool, because they would probably know
best to do it. The lists of maps used for automatic backtracking were supposed to be relatively short.

It is responsible for ensuring generating results that are consistent with the fact that path-connectedness is closed under composition.

... which is dealt with on a different ticket. Please don't prevent this
ticket from review just because it only addresses one flaw of the current
coercion model.

"It" being the parent that implements _coerce_map_from_, not this ticket. This remark was not meant to
state anything about the reviewability of this ticket.

comment:168 Changed 11 months ago by jpflori

I've had a look at the discussion here and the actual changes and am quite happy with them, at least with my current knowledge of the coercion framework.
I'll push in a few minutes some reviewer changes mostly for formatting issues, a dirty utf8 ö character and a failing doctest.
Apart from this, there is one piece of code I'm not completely sure to get:

             mor = self.discover_convert_map_from(S)
-            self._convert_from_list.append(mor)
+            # Before trac #14711, the morphism has been 
+            # put both into _convert_from_list and into
+            # _convert_from_hash. But there is no reason
+            # to have a double book-keeping, specifically
+            # if one of them is by strong references!
             self._convert_from_hash.set(S, mor)
+            # Moreover, again by #14711, the morphism should
+            # only keep weak references to domain and codomain,
+            # to allow them being garbage collected.
+            if mor is not None:
+                mor._make_weak_references()
             return mor

First, I feel the inlined comments may deserve to be moved into the docstring.

Second, is the weakening necessary? Isn't the map already "weak"? And if not, why weaken it after storing it in the MonoDict?? If I get that correctly, in the end, what is stored is weakened anyway as mor is just a pointer to some python object, it is just that doing it after storing a pointer to the object elsewhere feels akward to me.
(The same thing is done at some other places in the same file.)

comment:169 follow-up: Changed 11 months ago by jpflori

  • Branch changed from u/SimonKing/ticket/14711 to u/jpflori/ticket/14711
  • Commit changed from 37bf59eac24eda1ece89aff7dde4a1db5d0cbb5c to 0af59ea93689cb6abb9d3fae0f1cf11f2aee5cca
  • Reviewers set to Jean-Pierre Flori

A few other remarks:

  • has the Cython bug been reported upstream?
  • I think the first todo -- add a lot of doc -- is really critical :)
  • to correct the warning in combinat/ncsym/dual.py I filtered the warning stemming from the use of a weakened map with "...", as is done in combinat/sf/new_kschur.py (see commit 364b9856b) as from what I understood the combinat code tries to send something from one basis to another and to do so relies on the coercion framework so end up with a weakened map. Note that I don't feel it's really a satisfying long term solution; the combinat people surely won't like the output being polluted with warnings (which are not that helpful in these cases). But I don't want to dive into the combinat code to make a copy of the needed map at the right place now.

New commits:

0af59eaReviewer changes. Mostly formatting.

comment:170 Changed 11 months ago by jpflori

FYI, this passes all tests when merged against 6.1.beta2.

comment:171 follow-up: Changed 11 months ago by tscrim

My 2 cents. I don't think that coerce_map_from() should return the map which is used in the coercion system, but a copy of it. I believe this would be a better system since it's easily accessible to a user, so the user could mess with the map and the coercion system, and the result is used in error messages where the "copy" warning message has no purpose (for example the doctest in ncsym/dual.py). Subsequently I believe we should have a hidden function which returns the actual map, for those cases when one needs it.

Also couldn't we use (some form of) #8878 get around some of the backtracking issues?

comment:172 in reply to: ↑ 171 ; follow-up: Changed 11 months ago by nbruin

Replying to tscrim:

My 2 cents. I don't think that coerce_map_from() should return the map which is used in the coercion system, but a copy of it.

Presently, that routine gets used internally as well. The internal routine should of course NOT copy the map, so changing that would imply renaming the present routine to an underscore method and writing a new wrapper that does the copying ... and changing the internal code to use the new underscore method.

Also couldn't we use (some form of) #8878 get around some of the backtracking issues?

This is outside the scope of this ticket. We would need to seriously recalibrate the "coercion costs" to ensure that the "shortest path" would indeed be a reasonable thing. Furthermore, a large part of the graph is encoded programmatically, so not fully accessible for a backtracking search. We could of course just trust the programmatic bits to yield "shortest" paths, but those routines tend to do depth-first searches themselves

comment:173 in reply to: ↑ 169 Changed 11 months ago by SimonKing

Replying to jpflori:

A few other remarks:

  • has the Cython bug been reported upstream?

Yes, but I don't have a reference. Anyway, it was reported to cython-users mailing list, and some time ago on sage-devel Robert Bradshaw did recall that I had reported it.

  • I think the first todo -- add a lot of doc -- is really critical :)

What todo list are you referring to?

comment:174 in reply to: ↑ 172 ; follow-up: Changed 11 months ago by SimonKing

Replying to nbruin:

Replying to tscrim:

My 2 cents. I don't think that coerce_map_from() should return the map which is used in the coercion system, but a copy of it.

I somehow agree, but:

Presently, that routine gets used internally as well. The internal routine should of course NOT copy the map, so changing that would imply renaming the present routine to an underscore method and writing a new wrapper that does the copying ... and changing the internal code to use the new underscore method.

Would this really be so difficult?

Also couldn't we use (some form of) #8878 get around some of the backtracking issues?

This is outside the scope of this ticket.

Yes, but it is an interesting idea. Given the difficulties in #15303, it would actually be worth while to go beyond and create an actual digraph for dealing both with the search for coerce maps (and given an actual graph, it might be easier to instrument graph algorithms) and strong/weak references, caching of maps and so on.

comment:175 Changed 11 months ago by SimonKing

PS: The review commit looks ok to me. I only wonder: Should a doc string ending with a test also end with a blank line? I thought that the usual thing to do in Sage (but not official standard) is this

def f1(...):
    """
    This is some doc

    EXAMPLES::

        sage: ...
        ...

    The doc ends with normal text and hence without blank line
    """
    return None

but

def f2(...):
    """
    Some doc

    EXAMPLES::

        sage: ...

    There is a concluding example, and after the example is
    a blank line::

        sage: ...
        ,,,

    """
    return None

So, I wonder if it is needed that the review commit removes trailing blank lines. On the other hand, I don't mind if they'll be removed.

comment:176 Changed 11 months ago by jpflori

Sorry about the blank lines, I think I've been overzealous and played too much with vim.
I personally prefer not leaving superfluous blank lines and didn't get the impression it was an informal convention but I don't really care what ends up in the final branch.

I was thinking about the todo in the ticket description:

  • Provide a documentation of the use of weak references in coercion, and of different ways of registering coercions, with their different impacts on garbage collecion.

At the moment, I feel like the ticket could be merged.
There's Travis issue with perfectly make sense, but how harmful would it be to leave that for another ticket?
Would it really involve more work and rebasing than doing it here?

Nils idea would do the trick and doesn't look that hard at first but I feel it won't be that easy to ensure that each current incarnations of coerce_map_from have been correctly left as is when outside of the coercion framework but had an underscore added within the coercion framework (or we'll jsut end up with random memleaks again :().

comment:177 in reply to: ↑ 174 ; follow-ups: Changed 11 months ago by tscrim

Replying to SimonKing:

Replying to nbruin:

Presently, that routine gets used internally as well. The internal routine should of course NOT copy the map, so changing that would imply renaming the present routine to an underscore method and writing a new wrapper that does the copying ... and changing the internal code to use the new underscore method.

Would this really be so difficult?

Isn't all of the coercion model consolidated in coerce.pyx and parent.pyx? I can make a more detailed look and work on this tomorrow.

Also couldn't we use (some form of) #8878 get around some of the backtracking issues?

This is outside the scope of this ticket.

Yes, but it is an interesting idea. Given the difficulties in #15303, it would actually be worth while to go beyond and create an actual digraph for dealing both with the search for coerce maps (and given an actual graph, it might be easier to instrument graph algorithms) and strong/weak references, caching of maps and so on.

I was thinking it was outside of the scope of this ticket, but wasn't sure from the discussion if something like that was needed as a dependency. Although that's basically what we have currently (if I'm reading the code right). To do more of the graph algorithms, it might be worthwhile to also store the data in other formats (ex. a map of parents to an array of their "neighbors") depending on what is useful.

comment:178 in reply to: ↑ 177 Changed 11 months ago by nbruin

Replying to tscrim:

Would this really be so difficult?

I don't think it would be particularly difficult

I was thinking it was outside of the scope of this ticket, but wasn't sure from the discussion if something like that was needed as a dependency. Although that's basically what we have currently (if I'm reading the code right). To do more of the graph algorithms, it might be worthwhile to also store the data in other formats (ex. a map of parents to an array of their "neighbors") depending on what is useful.

Simon's tutorial example for how to write parents is a very good illustration of the problem: Localizations of Z at a finite set of primes S. A parent may have so many coercions into it that it's inefficient, impractical, or impossible to list them all (the localization at any subset T would coerce naturally). The one (almost superfluous) thing his example is forgetting is to test if the asked ring coerces into ZZ and via that into the localization (i.e. the depth-first search). This example convinced me that the hybrid we have now, ugly, confusing and complicated as it may be, might actually be the best we can do. With things like Qbar, SR, ComplexField? etc., I don't think it's possible to separate the programmatic and the recursible parts.

comment:179 in reply to: ↑ 177 Changed 11 months ago by SimonKing

Replying to tscrim:

Yes, but it is an interesting idea. Given the difficulties in #15303, it would actually be worth while to go beyond and create an actual digraph for dealing both with the search for coerce maps (and given an actual graph, it might be easier to instrument graph algorithms) and strong/weak references, caching of maps and so on.

I was thinking it was outside of the scope of this ticket, but wasn't sure from the discussion if something like that was needed as a dependency.

No, it is more the other way around: Here, we lay the ground for building a coercion framework without undue lifetime implications. At least this is my viewpoint on this ticket.

comment:180 follow-up: Changed 11 months ago by tscrim

Okay, I've done the initial stuff and called the new method _internal_coerce_map_from(). I've pushed it into the branch

public/ticket/14711-internal_test

However I get the following doctest failing in parent.pyx:

The following was fixed in :trac:`4740`::

    sage: F = GF(13)
    sage: F.coerce_map_from(F) is F.coerce_map_from(F)
    True

It's returning False which I think is okay, but I'd need someone more experienced in the finite fields code to verify that it's okay...well it might just need to be changed to the new internal method (see below).

I'm also getting a strange <BLANKLINE> in a doctest in coerce.pyx, which is causing a doctest failure. My guess is it's somehow coming from the warning message... Anyways, I'm running all doctests now.

Now here's the list of files in the new branch which use coerce_map_from:

categories/pushout.py
combinat/sf/new_kschur.py
combinat/root_system/weight_lattice_realizations.py
geometry/polyhedron/parent.py
rings/real_mpfr.pyx
rings/real_double.pyx
rings/finite_rings/finite_field_base.pyx
rings/finite_rings/integer_mod_ring.py
rings/finite_rings/finite_field_prime_modn.py
rings/number_field/number_field.py
rings/number_field/number_field_rel.py
rings/polynomial/polynomial_modn_dense_ntl.pyx
rings/polynomial/polynomial_ring.py
rings/polynomial/laurent_polynomial_ring.py
rings/complex_field.py
rings/complex_double.pyx
rings/rational_field.py
rings/residue_field.pyx

I've also started doing some of the swaps to the internal maps in:

src/sage/categories/homset.py
src/sage/categories/map.pyx
src/sage/combinat/free_module.py
src/sage/structure/parent_old.pyx
schemes/projective/projective_point.py
schemes/projective/projective_morphism.py
schemes/generic/morphism.py
structure/formal_sum.py

I'd like to know if we're okay just swapping the old coerce_map_from() to the _internal_coerce_map_from()? I think we'd want to do this anytime the user will not have access to the maps, and I think they are safe to do so, but could someone else double-check this for me? Thanks.

Last edited 11 months ago by tscrim (previous) (diff)

comment:181 in reply to: ↑ 180 ; follow-ups: Changed 11 months ago by SimonKing

Replying to tscrim:

However I get the following doctest failing in parent.pyx:

The following was fixed in :trac:`4740`::

    sage: F = GF(13)
    sage: F.coerce_map_from(F) is F.coerce_map_from(F)
    True

It's returning False which I think is okay, but I'd need someone more experienced in the finite fields code to verify that it's okay...

I suppose what we want to test here is in fact that internally coerce maps are cached, and thus identical objects are used when one internally asks for the coerce maps.

Hence, I think one should test F._internal_coerce_map_from(F) is F._internal_coerce_map_from(F), adding a comment that this is just a test and _internal_coerce_map_from() is, well, internal.

I'm also getting a strange <BLANKLINE> in a doctest in coerce.pyx, which is causing a doctest failure. My guess is it's somehow coming from the warning message...

Hmmm. This needs to be fixed.

I'd like to know if we're okay just swapping the old coerce_map_from() to the
_internal_coerce_map_from()? I think we'd want to do this anytime the user will not have access
to the maps, and I think they are safe to do so, but could someone else double-check this for me?

I think it is almost exactly what we want.

Perhaps with a little refinement:

  • In doctests, we should use coerce_map_from(), since we want to see proper maps there, except for educational purposes such as the test mentioned above.
  • In code, we will mostly want _internal_coerce_map_from().
  • Exception: If we have a "public" (non-underscore) method that returns a coerce map, then it should internally either explicitly create a copy or use coerce_map_from(). We may think of turning some of these methods into cached methods: If they are frequently called, copying the map each time is bad.

comment:182 in reply to: ↑ 181 Changed 11 months ago by tscrim

Replying to SimonKing:

I suppose what we want to test here is in fact that internally coerce maps are cached, and thus identical objects are used when one internally asks for the coerce maps.

Hence, I think one should test F._internal_coerce_map_from(F) is F._internal_coerce_map_from(F), adding a comment that this is just a test and _internal_coerce_map_from() is, well, internal.

Changed.

I'm also getting a strange <BLANKLINE> in a doctest in coerce.pyx, which is causing a doctest failure. My guess is it's somehow coming from the warning message...

Hmmm. This needs to be fixed.

I still don't know where this is coming from.

I think it is almost exactly what we want.

Perhaps with a little refinement:
...

That was exactly what I was thinking. Done and I've pushed the changes to the branch public/ticket/14711-internal_test.

However I am getting segfaults in running the tests in complex_number.pyx, number_field.py, and others, and I don't know what's causing it. (I've also merged in develop.)

I also don't quite understand why we need to copy the maps given in geometry/polyhedron/parent.py since it is being used in an internal _get_action_()?

comment:183 follow-up: Changed 11 months ago by jpflori

Please also remove the "..." which were added previously to filter the warnings.
I think of at least two of them in the combinat dir, maybe Simon remember more of them.

comment:184 in reply to: ↑ 183 Changed 11 months ago by tscrim

Replying to jpflori:

Please also remove the "..." which were added previously to filter the warnings.
I think of at least two of them in the combinat dir, maybe Simon remember more of them.

I got the ones in combinat, and I didn't come across any others (but I may have looked poorly).

Also, I hope I wasn't overzealous in removing some of the copy()'s and changing to the internal coerce map. We might also need to do something for the conversion maps as well... But first, I will need some help in figuring out the segfaults I'm getting.

comment:185 in reply to: ↑ 181 Changed 11 months ago by nbruin

Replying to SimonKing:

We may think of turning some of these methods into cached methods: If they are frequently called, copying the map each time is bad.

NO!! That very cache will then reintroduce the strong references we're trying to weaken!

comment:186 Changed 10 months ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:187 Changed 9 months ago by git

  • Commit changed from 0af59ea93689cb6abb9d3fae0f1cf11f2aee5cca to 6b233b52b8932cbe3a3f6ff9dabb0e5b5615b7e2

Branch pushed to git repo; I updated commit sha1. New commits:

6110bb9Now using _internal_coerce_map_from.
6f22299Initial attempt at _internal_coerce_map_from_() method.
3b6ac30Started transition.
147b4f5Removed unneeded copying of maps.
8c1ef83Merge branch 'develop' into public/ticket/14711
21aa9bcRemoved some more copy and some other formatting changes.
6b233b5Merge remote-tracking branch 'trac/develop' into ticket/14711

comment:188 Changed 9 months ago by jpflori

First step toward rebasing.
Lots of work still needed, especially for p-adic stuff (at the very least).

comment:189 Changed 9 months ago by git

  • Commit changed from 6b233b52b8932cbe3a3f6ff9dabb0e5b5615b7e2 to 7d7f7ae03d3fd16e630c69fa863f9ce8e1ac01e3

Branch pushed to git repo; I updated commit sha1. New commits:

7d7f7aeFixes for p-adic coercions.

comment:190 Changed 9 months ago by jpflori

Some maps created for p-adics seem to get automatically gc'ed and make some doctests fail.

comment:191 Changed 9 months ago by jpflori

There are still a huge of number of failures, a lot of them in the number field stuff.
I've double checked and these are not present in the old u/SimonKing/ticket/14711 branch.
So it must be that something about number field or coercion has changed in other tickets since the original development of this ticket.

The current trac/master seems (mostly) fine.
So it's between trac/master (6.1.1) and trac/develop (6.2.beta2).
Or not, as I've just tested every tag up to 6.2.beta2 on top of u/SimonKing/ticket/14711 without problems.
I've resolved conflicts in a slightly different way so it might be the reason behind the different behaviors.

comment:192 follow-up: Changed 9 months ago by tscrim

Is your branch based off the one I was working on?

comment:193 Changed 9 months ago by git

  • Commit changed from 7d7f7ae03d3fd16e630c69fa863f9ce8e1ac01e3 to d0c26b94039540688eb35e985ebd7b558cec62b1

Branch pushed to git repo; I updated commit sha1. New commits:

d0c26b9Fix wrong conflict resolution in number_field.py.

comment:194 Changed 9 months ago by jpflori

Ok, my bad, I wrongly resolved a commit in number_field.py the first time.

comment:195 in reply to: ↑ 192 Changed 9 months ago by jpflori

Replying to tscrim:

Is your branch based off the one I was working on?

Yes it is.

comment:196 follow-up: Changed 9 months ago by jpflori

It seems plausible that a bunch of errors and segaults are caused by the fact that some calls to copy were discarded in the construction of "conversion maps" or something in that spirit.

For sure something similar to what was done whit _internal_coerce... should be done for convert_map....

comment:197 Changed 9 months ago by jpflori

Disregard my last comment, it seems I've forgotten to rebuild some files while switching between different branches...

comment:198 Changed 9 months ago by jpflori

One of the "new" problems when testing number_field.py seems to be that

def _lift_cyclotomic_element(self, new_parent, bint check=True, int rel=0)

is called with rel of non-int type.
The call stems from number_field_morphism.py:

x._lift_cyclotomic_element(self.codomain(), False, self.ratio)

comment:199 Changed 9 months ago by jpflori

Minimal example:

sage: cf6 = CyclotomicField( 6 )
sage: cf12 = CyclotomicField( 12 )
sage: z6 = cf6.0
sage: g = cf12.coerce_map_from(cf6)
sage: g(z6)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-6-cc0ddcad408e> in <module>()
----> 1 g(z6)

/home/jpflori/sage.git/local/lib/python2.7/site-packages/sage/categories/map.so in sage.categories.map.Map.__call__ (sage/categories/map.c:4982)()

/home/jpflori/sage.git/local/lib/python2.7/site-packages/sage/rings/number_field/number_field_morphisms.so in sage.rings.number_field.number_field_morphisms.CyclotomicFieldEmbedding._call_ (sage/rings/number_field/number_field_morphisms.c:6049)()

/home/jpflori/sage.git/local/lib/python2.7/site-packages/sage/rings/number_field/number_field_element_quadratic.so in sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic._lift_cyclotomic_element (sage/rings/number_field/number_field_element_quadratic.cpp:5613)()

TypeError: an integer is required

comment:200 Changed 9 months ago by jpflori

Ok, it seems ratio is None.

comment:201 Changed 9 months ago by jpflori

I guess some update_slots magic has to be used to copy ratio for cyclotomic field morphims.

comment:202 Changed 9 months ago by jpflori

It might also be worth checking why this used to work and where these new (defunct) copies occur.

comment:203 Changed 9 months ago by git

  • Commit changed from d0c26b94039540688eb35e985ebd7b558cec62b1 to b21179f6631af835d01ed1f7f250bb2ac4c12f2b

Branch pushed to git repo; I updated commit sha1. New commits:

b21179fFix copying of some morphims.

comment:204 in reply to: ↑ 196 Changed 9 months ago by jpflori

Replying to jpflori:

For sure something similar to what was done whit _internal_coerce... should be done for convert_map....

This should still be done. See for example src/sage/rings/polynomial/polynomial_element.pyx.

comment:205 Changed 9 months ago by git

  • Commit changed from b21179f6631af835d01ed1f7f250bb2ac4c12f2b to 6b2b2e51ea475059605450d14fb657496e7f7c78

Branch pushed to git repo; I updated commit sha1. New commits:

6b2b2e5Fix test for weakened morphisms.

comment:206 Changed 9 months ago by git

  • Commit changed from 6b2b2e51ea475059605450d14fb657496e7f7c78 to 1cf51a4ce58fcc8620ac4158361567e73e7df9c5

Branch pushed to git repo; I updated commit sha1. New commits:

1cf51a4Introduce _internal_convert_map_from, use it and fix doctests.

comment:207 Changed 9 months ago by jpflori

  • Authors changed from Simon King to Simon King, Travis Scrimshaw, Jean-Pierre Flori
  • Reviewers changed from Jean-Pierre Flori to Nils Bruin, Jean-Pierre Flori
  • Status changed from needs_review to needs_work
  • Work issues set to blankline, gc

The remaining issues are:

  • some maps seem to get collected in padics/CR_template.pxi
  • <BLANKLINE> issue when the WARNING stuff is fed into an Exception/Error? text (it seems to be duplicated: once before the Traceback and once in the error string, maybe a doctesting framework limitation?)

comment:208 Changed 9 months ago by git

  • Commit changed from 1cf51a4ce58fcc8620ac4158361567e73e7df9c5 to f5827666b700d3b8d245b20d2346c7110bd0c21d

Branch pushed to git repo; I updated commit sha1. New commits:

f582766Fix doctests for copy of conversion from QQ to Zp.

comment:209 Changed 9 months ago by jpflori

  • Work issues changed from blankline, gc to blankline

The padic issue was caused by a wrong doctest.
Fixed now.

comment:210 Changed 9 months ago by git

  • Commit changed from f5827666b700d3b8d245b20d2346c7110bd0c21d to c9cd7a46c1338b7e452ea8f4e5e26d189f43ddb8

Branch pushed to git repo; I updated commit sha1. New commits:

c9cd7a4Fix doctests in combinat using coercion stuff.

comment:211 Changed 9 months ago by jpflori

I've set back the WARNING stuff in the combinat doctests which were failing.
I'm not really acuqinted to this code, so Travis could you confirm that the fact that internal coercion stuff is used is expected?
(I see you changed stuff from coerce_map_from to the internal version in sf/new_kschur and it seems the error is triggered when composing stuff internally, that is not when dealing with user visible stuff, so it seems ok)

There is still the strange blankline mentioned by Travis in structure/coerce.pyx.

comment:212 Changed 9 months ago by git

  • Commit changed from c9cd7a46c1338b7e452ea8f4e5e26d189f43ddb8 to 4e4bdbb4abe71fd77529bfef5dadb12c473453af

Branch pushed to git repo; I updated commit sha1. New commits:

4e4bdbbFix for failing doctest in coerce.pyx.

comment:213 Changed 9 months ago by jpflori

  • Status changed from needs_work to needs_review
  • Work issues blankline deleted

Ok, this was some strange output from the doctesting framework not liking the new lines and ... in the expected output.

I guess we could set this to positive review if Travis or Simon is ok with my latest changes (_internal_convert_map_from and the combinat doctests) and avoid further painful rebasing.

comment:214 Changed 9 months ago by tscrim

I'll try to take a look at it tonight, otherwise I will do so tomorrow unless Simon beats me too it.

comment:215 follow-up: Changed 9 months ago by tscrim

  • Branch changed from u/jpflori/ticket/14711 to public/ticket/14711
  • Commit changed from 4e4bdbb4abe71fd77529bfef5dadb12c473453af to ea58b22f0bf2652e7d04b3d55e6217dcb8732cdf

I've actually changed TriangularModuleMorphism to print out a copy of itself when raising an error because I didn't like the WARNING message being displayed. (FTR, they were being used as expected since they are suppose to be internal coercions.) And while that strange blankline is weird, it doesn't seem to be harmful, so I'm up for setting this to positive review. Simon, Nils, any objections?


New commits:

ea58b22Made triangular module morphism return a copy of self in error messages.

comment:216 Changed 9 months ago by SimonKing

Is it normally the case that the error being raised by TriangularModuleMorphism will not be caught? Otherwise, copying the morphism just for getting its print representation would be a waste of time.

Currently I do not have the capacity to check details, and for about one week I won't be able to review the recent changes.

comment:217 Changed 9 months ago by tscrim

I don't think so. It's for when trying to incorrectly use the (natural) inverse map, and as such, it shouldn't be caught much (if at all). At least I can't think of a case where it is...

comment:218 Changed 9 months ago by tscrim

How about we add an optional argument suppress_warning to the _repr_ for times like this but when the error is expected to be caught?

comment:219 in reply to: ↑ 215 ; follow-up: Changed 9 months ago by nthiery

Hi!

Replying to tscrim:

I've actually changed TriangularModuleMorphism to print out a copy of itself when raising an error because I didn't like the WARNING message being displayed. (FTR, they were being used as expected since they are suppose to be internal coercions.)

Sorry, I haven't been following the details. Having to change the
code of existing morphisms when the usage is as expected feels like a
smell (one more thing to think about when using/implementing
morphisms). If I understand properly, in certain circumstances, one
has to make copies of morphisms. Is it described somewhere in the documentation what those
circumstances are exactly? It would be best if the warning would point
to this documentation, as I would not guess, at first sight, why I'd
need to make a copy of an immutable object.

Cheers,

Nicolas

comment:220 in reply to: ↑ 219 ; follow-up: Changed 9 months ago by jpflori

Replying to nthiery:

Hi!

Replying to tscrim:

I've actually changed TriangularModuleMorphism to print out a copy of itself when raising an error because I didn't like the WARNING message being displayed. (FTR, they were being used as expected since they are suppose to be internal coercions.)

Sorry, I haven't been following the details. Having to change the
code of existing morphisms when the usage is as expected feels like a
smell (one more thing to think about when using/implementing
morphisms). If I understand properly, in certain circumstances, one
has to make copies of morphisms. Is it described somewhere in the documentation what those

Not with Travis last changes.
Now the coerce/convert_map_from methods return "safe" objects for which the copying was automatically done.
It's only the _internal_ prefixed methods which return weakened objects but might be faster as no copies are involved.

comment:221 in reply to: ↑ 220 Changed 9 months ago by nthiery

Replying to jpflori:

Replying to nthiery:

Replying to tscrim:

I've actually changed TriangularModuleMorphism to print out a copy of itself when raising an error because I didn't like the WARNING message being displayed. (FTR, they were being used as expected since they are suppose to be internal coercions.)

Sorry, I haven't been following the details. Having to change the
code of existing morphisms when the usage is as expected feels like a
smell (one more thing to think about when using/implementing
morphisms). If I understand properly, in certain circumstances, one
has to make copies of morphisms. Is it described somewhere in the documentation what those

Not with Travis last changes.
Now the coerce/convert_map_from methods return "safe" objects for which the copying was automatically done.
It's only the _internal_ prefixed methods which return weakened objects but might be faster as no copies are involved.

You mean that the change to TriangularModuleMorphism is not needed any more?

comment:222 follow-up: Changed 9 months ago by jpflori

I'd say the change is needed.
But that's because the code there uses an internal method to go faster rather than the publicized safe and slower method.

Normally one would use the public and slower method and won't have such problems.
If one wants to use internal stuff, then it does not sound so unnatural that one has to be careful.

comment:223 in reply to: ↑ 222 Changed 9 months ago by nthiery

Replying to jpflori:

I'd say the change is needed.
But that's because the code there uses an internal method to go faster rather than the publicized safe and slower method.

Sorry, I am confused; which internal method?

Last edited 9 months ago by nthiery (previous) (diff)

comment:224 Changed 9 months ago by jpflori

In fact, the code in Triangular... does not use the new _internal_coerce_map_from, but the code here:
http://git.sagemath.org/sage.git/diff/src/sage/combinat/sf/new_kschur.py?id=6110bb984403114b2ddb8410868472d1cfdc64df

comment:225 Changed 9 months ago by tscrim

IMO the TriangularModuleMorphism should be an internal coercion map in these cases, and so the issue is the error messages includes the map. Hence there is a big, scary, but completely unrelated warning printed with the error message. So to suppress the warning, either we copy self or do (something like) comment:218.

comment:226 follow-ups: Changed 9 months ago by nthiery

Ok, thanks for the explanations!

Hmm, this is not super convincing since this adds some complexity: when should one use _internal_coercion_map_from or coerce_map_from? when should one do a copy? I guess that will do for now, but if we end up having to worry about those every so often, we should find some better approach.

As for the current workaround, I prefer using copy to introducing another protocol as in comment:218.

Cheers,

Nicolas

comment:227 in reply to: ↑ 226 ; follow-up: Changed 9 months ago by SimonKing

Replying to nthiery:

Hmm, this is not super convincing since this adds some complexity: when should one use _internal_coercion_map_from or coerce_map_from? when should one do a copy?

If you can be sure that domain and codomain will remain strongly referenced, then you should be safe with _internal_coercion_map_from---but since the _repr_ method can not know whether a strong reference will remain, it will print the warning.

If it could be that the map itself is the only object holding references to domain and codomain, then you must copy it (or use coerce_map_from).

As for the current workaround, I prefer using copy to introducing another protocol as in comment:218.

I don't think the suggestion from comment:218 has a chance to work. Can _repr_ take an optional argument?

comment:228 Changed 9 months ago by SimonKing

PS: Why not use some kind of lazy string, that will copy the map only if the string representation is actually printed? Hence, if the error is caught somewhere, then the error message will not be expanded. But if the error appears on screen, then the lazy string will copy the map before printing it.

comment:229 in reply to: ↑ 226 Changed 9 months ago by jpflori

Replying to nthiery:

Ok, thanks for the explanations!

Hmm, this is not super convincing since this adds some complexity:

Sure but it's hard fixing bugs without modifying code :)

when should one use _internal_coercion_map_from or coerce_map_from? when should one do a copy? I guess that will do for now, but if we end up having to worry about those every so often, we should find some better approach.

I'd say the answer is simple: just use the non-internal method by default.

Of course this is "unless you know what you're doing"...

comment:230 in reply to: ↑ 227 ; follow-up: Changed 9 months ago by tscrim

Replying to SimonKing:

I don't think the suggestion from comment:218 has a chance to work. Can _repr_ take an optional argument?

Yes it can, as long as it has a default value. The plus-minus diagrams in combinat/crystals/kirillov_reshetikhin.py do it, and I think a few other places as well.

comment:231 in reply to: ↑ 230 ; follow-up: Changed 9 months ago by SimonKing

Is the suggestion to do something like this:

    raise TypeError("%s is totally doomed."%m)

(which is when an optional parameter to _repr_ can not make sense) or like this:

    raise TypeError("%s is totally doomed."%m._repr_(suppress_warning=False))

(which works but is is clumsy)?

comment:232 in reply to: ↑ 231 Changed 9 months ago by tscrim

Replying to SimonKing:

Is the suggestion to do something like this:

    raise TypeError("%s is totally doomed."%m)

(which is when an optional parameter to _repr_ can not make sense) or like this:

    raise TypeError("%s is totally doomed."%m._repr_(suppress_warning=False))

(which works but is is clumsy)?

The latter one (so we don't have to do the copy unnecessarily).

comment:233 follow-up: Changed 8 months ago by jpflori

Do you mean one would have to always pass the suppress_warning thing?

comment:234 in reply to: ↑ 233 ; follow-up: Changed 8 months ago by tscrim

Replying to jpflori:

Do you mean one would have to always pass the suppress_warning thing?

I'm not completely sure what you mean. I'm going to take a shot and say only if one wants to suppress the warning, not if they didn't care if it has a warning or not. For example,

sage: domain._get_coerce_map_internal(codomain)

will work because of the default value of True (and display the warning message as well).

@Simon, I don't think that will work because python should run the copy before passing to the lazy string, since I think the string's formatting is the only thing being lazily done.

comment:235 in reply to: ↑ 234 Changed 8 months ago by SimonKing

Replying to tscrim:

@Simon, I don't think that will work because python should run the copy before passing to the lazy string, since I think the string's formatting is the only thing being lazily done.

That's why I said "Why not use some kind of lazy string" in comment:228. It would of course be a new class, along the lines of

class CopyOnPrint:
    def __init__(self, x):
        self.x = x
    def __repr__(self):
        return repr(self.x.__copy__())

comment:236 follow-up: Changed 8 months ago by jpflori

I'm also lost now.

My problem is I don't feel we need to copy that map just to print it.
And I don't get the meaning of Simon point in comment:231.

What I understood is that Travis suggested to add an optional suppress_warning option to the _repr_ method of Morphism set to False by default.
In the piece of code currently printing the boring warning, one would use %m._repr_(suppress_warning) as we don't really care to print that the map was using weak references.
@Simon is it this construction that you find clumsy?

comment:237 Changed 8 months ago by SimonKing

PS: This "CopyOnPrint" would only provide the string representation of the map. The whole error message would then be a lazy format string, such that the copy would really only happen when printing the error message.

Proof of concept:

sage: class CopyOnPrint:
....:     def __init__(self, x):
....:         self.x = x
....:     def __repr__(self):
....:         print "Now a copy is taken"
....:         return repr(x.__copy__())
....:     
sage: O = CopyOnPrint(x)
sage: O
Now a copy is taken
x
sage: msg = "The map %s is doomed"%O
Now a copy is taken

The last line shows that the copy happens even though the message is not printed. However, when combined with a lazy format string, the behaviour is as intended:

sage: from sage.misc.lazy_format import LazyFormat
sage: lazy_msg = LazyFormat("The map %s is doomed")%O

So, the message is created without copying, but copying happens when printing the message:

sage: lazy_msg
Now a copy is taken
The map x is doomed

comment:238 follow-up: Changed 8 months ago by tscrim

Ah, sorry about that Simon. However do you think we find this useful enough to not do the evils of copying or adding an optional arg to _repr_? Because having the lazy format and copy string seems to specific to our case.

Actually...what it we have a lazy string that takes an arbitrary function and prints the result? This might be useful for errors which want to do some (non-trivial) transformation to an object before adding it to the error.

comment:239 in reply to: ↑ 236 Changed 8 months ago by SimonKing

Replying to jpflori:

My problem is I don't feel we need to copy that map just to print it.

I understand that we want all our weakened maps to print a big fat warning, since they are only safe to use when a reference to domain and codomain is being kept. This should be guaranteed as long as the weakened maps live in the safe environment of the coercion framework, but can not be guaranteed if the user pulls them out of their natural environment.

Normally, the coercion framework will not print maps, hence, one will see the big fat warning *only* if one deals with a weakened map that lives outside of the coercion framework.

Now, back to your question: If we accept that a weakened map must provide a big fat warning then we have to do something special when we want that a weakened map prints as a normal map.

Options:

  • Make it strong in-place. That's bad, because it may create a memory leak on the fly.
  • Use a copy. That's what the big fat warning currently suggests.
  • Find a way to tell _repr_ whether the warning shall be given or not. I.e.: Introduce an optional parameter to _repr_

And I don't get the meaning of Simon point in comment:231.

All I wanted to say is: the optional argument to _repr_ will not save us any effort.

What I understood is that Travis suggested to add an optional suppress_warning option to the _repr_ method of Morphism set to False by default.

Which I find odd.

In the piece of code currently printing the boring warning, one would use %m._repr_(suppress_warning) as we don't really care to print that the map was using weak references.
@Simon is it this construction that you find clumsy?

Yes.

comment:240 in reply to: ↑ 238 ; follow-up: Changed 8 months ago by SimonKing

Replying to tscrim:

Actually...what it we have a lazy string that takes an arbitrary function and prints the result?

That's lazy_string, which is different from LazyFormat.

comment:241 in reply to: ↑ 240 ; follow-up: Changed 8 months ago by tscrim

Replying to SimonKing:

Replying to tscrim:

Actually...what it we have a lazy string that takes an arbitrary function and prints the result?

That's lazy_string, which is different from LazyFormat.

Why can't we just use that with copy as the function? Something like:

sage: from sage.misc.lazy_string import lazy_string
sage: LazyFormat('%s')%lazy_string(copy, 5)
5

comment:242 in reply to: ↑ 241 ; follow-up: Changed 8 months ago by SimonKing

Replying to tscrim:

Why can't we just use that with copy as the function? Something like:

sage: from sage.misc.lazy_string import lazy_string
sage: LazyFormat('%s')%lazy_string(copy, 5)
5

Makes sense to me.

comment:243 in reply to: ↑ 242 ; follow-up: Changed 8 months ago by nbruin

Replying to SimonKing:

Replying to tscrim:

Why can't we just use that with copy as the function? Something like:

sage: from sage.misc.lazy_string import lazy_string
sage: LazyFormat('%s')%lazy_string(copy, 5)
5

Makes sense to me.

This may mean that by the time the string gets expanded, the domain of the weak map has already been garbage collected and that the copy may fail; now leading to a failure in error message production (which is even worse than an awkward error message). Can't we just live with a slightly more awkward error message; possibly combined with a slightly less awkward warning?

comment:244 in reply to: ↑ 243 ; follow-up: Changed 8 months ago by tscrim

Replying to nbruin:

This may mean that by the time the string gets expanded, the domain of the weak map has already been garbage collected and that the copy may fail; now leading to a failure in error message production (which is even worse than an awkward error message). Can't we just live with a slightly more awkward error message; possibly combined with a slightly less awkward warning?

Eeek, you're right. However I believe we should not print the warning message when we're not exposing an object to the public.

Another option would be to print the warning message via _repr_help that Volker proposed in #15036 comment 20 for the internal maps. How do you feel about this?

comment:245 in reply to: ↑ 244 ; follow-ups: Changed 8 months ago by nbruin

Replying to tscrim:

Eeek, you're right. However I believe we should not print the warning message when we're not exposing an object to the public.

Then you should probably just chop off the warning from the string, since that seems by far the cheapest option (other than coming up with an entirely new protocol):

sage: def fn(S):
    i=S.find('\n\n        WARNING')
    return S[:i] if i >=0 else S
sage: phi=QQ._internal_coerce_map_from(ZZ)
sage: timeit("str(phi)")
625 loops, best of 3: 15.7 µs per loop
sage: timeit('str(phi).split("\\n\\n        WARNING")[0]')
625 loops, best of 3: 16 µs per loop
sage: timeit("fn(str(phi))")
625 loops, best of 3: 16.9 µs per loop
sage: timeit("str(copy(phi))")
625 loops, best of 3: 23.6 µs per loop

And to check the penalty on a normal, strong, map:

sage: psi=copy(phi)
sage: timeit("str(psi)")
625 loops, best of 3: 9.97 µs per loop
sage: timeit("fn(str(psi))")
625 loops, best of 3: 11.4 µs per loop
sage: timeit('str(psi).split("\\n\\n        WARNING")[0]')
625 loops, best of 3: 11.1 µs per loop

Whether you do it lazily or upon creation of the error message is another matter, but I think this example shows that just stripping the "WARNING" from the string when that is absolutely required is cheap enough compared to producing the string in the first place. I do think it will be a source for confusion if we start printing objects in error messages differently from how they are normally represented.

Would the following string rep perhaps be more acceptable?

sage: phi
(internal coercion system map--copy before use) Natural morphism:
  From: Integer Ring
  To:   Rational Field

Another option would be to print the warning message via _repr_help that Volker proposed in #15036 comment 20 for the internal maps. How do you feel about this?

I think that's bad, because Volker's proposal serves a completely different purpose. This has nothing to do with something being printed at top-level or not, but with the context in which it is printed.

Last edited 8 months ago by nbruin (previous) (diff)

comment:246 in reply to: ↑ 245 Changed 8 months ago by tscrim

Replying to nbruin:

Then you should probably just chop off the warning from the string, since that seems by far the cheapest option (other than coming up with an entirely new protocol):

I'm happy with doing it this way. Simon, Nicolas, Jean-Pierre, any objections?

comment:247 in reply to: ↑ 245 Changed 8 months ago by SimonKing

Replying to nbruin:

I do think it will be a source for confusion if we start printing objects in error messages differently from how they are normally represented.

Would the following string rep perhaps be more acceptable?

sage: phi
(internal coercion system map--copy before use) Natural morphism:
  From: Integer Ring
  To:   Rational Field

I think it is better than my "big fat warning", and I prefer this solution over "chopping off the warning".

comment:248 Changed 8 months ago by git

  • Commit changed from ea58b22f0bf2652e7d04b3d55e6217dcb8732cdf to f68550d17989e50adecc9c1d6634109095174003

Branch pushed to git repo; I updated commit sha1. New commits:

c7d070fMerge branch 'public/ticket/14711' of trac.sagemath.org:sage into public/ticket/14711
f68550dFixed bad doctests from merge.

comment:249 follow-up: Changed 8 months ago by tscrim

Rebased on 6.2.beta5.

I'm not in favor of having any warning message displayed as part of an error message. Here's another option then (a variant on the optional arg):

Define _repr_no_warning() which does the main bulk of the string construction and then _repr_ just adds the warning. Then for things which want to include the a possible internal map, they just call _repr_no_warning().

Variant on the above: instead of _repr_no_warning(), we override __str__() and have TriangularModuleMorphism call str(self).

One more option: we change the warning message in TriangularModuleMorphism to not call repr(self) and instead spell some things out.


At some point we will have to do something (one of us) considers evil. If people en masse think leaving an error message in there is the best course of action, I'll accept it.

Thoughts?

comment:250 in reply to: ↑ 249 Changed 8 months ago by jpflori

Replying to tscrim:

Define _repr_no_warning() which does the main bulk of the string construction and then _repr_ just adds the warning. Then for things which want to include the a possible internal map, they just call _repr_no_warning().

I would be ok with that one.

And we should definitely merge this ticket, so some compromise has to be reached.

comment:251 Changed 8 months ago by nbruin

My $0.02:

  • Don't overengineer this special case (i.e., don't add new API)
  • my preference would be to change the error messages to not include the maps. Those errors look ugly even without the warning in there and maps tend to print in a rather uninformative way anyway.
  • toning down the warning to just an informative prefix (map internal to coercion system--copy before use) would be fine with me
  • string chopping seems a reasonable alternative
  • it doesn't look like TriangleModuleMorphism is very time critical anyway, so a copy of the map would be OK too. If it becomes a bottleneck, it can be revisited.

comment:252 Changed 8 months ago by git

  • Commit changed from f68550d17989e50adecc9c1d6634109095174003 to 8e5fe42b226442ef1dc181de0838803f00b29638

Branch pushed to git repo; I updated commit sha1. New commits:

d91bfabMerge branch 'develop' into public/ticket/14711
8e5fe42Changed warning message to leaner version.

comment:253 Changed 8 months ago by tscrim

Okay, I've cut down the size of the warning and removed the printing of the map from the error message for TriangularModuleMorphism (which is more inline with python's error messages).

comment:254 Changed 8 months ago by SimonKing

These changes look good to me.

comment:255 Changed 8 months ago by tscrim

Jean-Pierre, any objections? Because I believe if you don't have any, we can set this to positive review and get this merged in.

comment:256 Changed 8 months ago by jpflori

  • Status changed from needs_review to positive_review

Not any objection, I want this merged asap.

comment:257 Changed 8 months ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long src/sage/structure/coerce.pyx
**********************************************************************
File "src/sage/structure/coerce.pyx", line 1180, in sage.structure.coerce.CoercionModel_cache_maps.discover_coercion
Failed example:
    cm.discover_coercion(RR, QQ)
Expected:
    (None,
     Generic map:
      From: Rational Field
      To:   Real Field with 53 bits of precision...)
Got:
    (None, (map internal to coercion system -- copy before use)
    Generic map:
      From: Rational Field
      To:   Real Field with 53 bits of precision)
**********************************************************************

comment:258 Changed 8 months ago by vbraun

Also:

sage -t --long src/sage/tests/book_schilling_zabrocki_kschur_primer.py
**********************************************************************
File "src/sage/tests/book_schilling_zabrocki_kschur_primer.py", line 619, in sage.tests.book_schilling_zabrocki_kschur_primer
Failed example:
    ks3([3,2]).omega()
Expected:
    Traceback (most recent call last):
    ...
    ValueError: t^2*s[1, 1, 1, 1, 1] + t*s[2, 1, 1, 1] + s[2, 2, 1] is not
    in the image of Generic morphism:
    From: 3-bounded Symmetric Functions over Fraction Field of Univariate
    Polynomial Ring in t over Rational Field in the 3-Schur basis
    To:   Symmetric Functions over Fraction Field of Univariate Polynomial Ring
    in t over Rational Field in the Schur basis
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.tests.book_schilling_zabrocki_kschur_primer[214]>", line 1, in <module>
        ks3([Integer(3),Integer(2)]).omega()
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/combinat/sf/new_kschur.py", line 715, in omega
        return self.parent()(self.lift().omega())
      File "parent.pyx", line 1070, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8858)
      File "morphism.pyx", line 431, in sage.categories.morphism.SetMorphism._call_ (sage/categories/morphism.c:6519)
      File "/home/release/Sage/local/lib/python2.7/site-packages/sage/categories/modules_with_basis.py", line 1830, in preimage
        raise ValueError("{} is not in the image".format(f))
    ValueError: t^2*s[1, 1, 1, 1, 1] + t*s[2, 1, 1, 1] + s[2, 2, 1] is not in the image
**********************************************************************

comment:259 follow-up: Changed 8 months ago by tscrim

??? I tested coerce.pyx so many times I lost track. Anyways, I've fixed the doctests, but waiting on my sage to recompile to do a final check.

Last edited 8 months ago by tscrim (previous) (diff)

comment:260 follow-up: Changed 8 months ago by tscrim

  • Cc aschilling zabrocki added

Anne, Mike - More changes to the k-schur book...

comment:261 in reply to: ↑ 259 Changed 8 months ago by SimonKing

Replying to tscrim:

??? I tested coerce.pyx so many times I lost track. I've fixed the doctests, but waiting on my sage to recompile to do a final check.

Keep cool, these failures look totally trivial. While we are at it: Thank you very much for finishing these patches. I could currently not work on it myself.

comment:262 follow-up: Changed 8 months ago by tscrim

I really need to figure out how to get ccache to work, so as to avoid those long recompiles (I think I'm about 50/238 files in :/).

comment:263 Changed 8 months ago by git

  • Commit changed from 8e5fe42b226442ef1dc181de0838803f00b29638 to 00b3e2f3cf90b5e7a339367f8ad4e08e1f0fb3d7

Branch pushed to git repo; I updated commit sha1. New commits:

00b3e2fFixed doctests.

comment:264 Changed 8 months ago by tscrim

  • Status changed from needs_work to positive_review

Fixed. Took 51 minutes for my Sage to recompile itself. Now to have it recompile again!

comment:265 in reply to: ↑ 262 Changed 8 months ago by SimonKing

Replying to tscrim:

I really need to figure out how to get ccache to work

sage -i ccache doesn't work for you?

comment:266 in reply to: ↑ 260 Changed 8 months ago by aschilling

Replying to tscrim:

Anne, Mike - More changes to the k-schur book...

Do you really think that it is a good idea to remove valuable information? Now

    sage: Sym = SymmetricFunctions(FractionField(QQ["t"]))
    sage: ks3 = Sym.kschur(3)
    sage: ks3([3,2]).omega()
    Traceback (most recent call last):
    ...
    ValueError: t^2*s[1, 1, 1, 1, 1] + t*s[2, 1, 1, 1] + s[2, 2, 1] is not 
    in the image

Before

    sage: Sym = SymmetricFunctions(FractionField(QQ["t"]))
    sage: ks3 = Sym.kschur(3)
    sage: ks3([3,2]).omega()
    Traceback (most recent call last):
    ...
    ValueError: t^2*s[1, 1, 1, 1, 1] + t*s[2, 1, 1, 1] + s[2, 2, 1] is not 
    in the image of Generic morphism"
    From: 3-bounded Symmetric Functions over Fraction Field of Univariate 
    Polynomial Ring in t over Rational Field in the 3-Schur basis
    To:   Symmetric Functions over Fraction Field of Univariate Polynomial Ring
    in t over Rational Field in the Schur basis

comment:267 Changed 8 months ago by tscrim

I don't think the information about a generic statement of a map is useful. I think if you come across this error message you either:

  • know the morphism you're trying explicitly (such as the coercion in the example) and are feeding it bad data, or
  • it's buried deep or implicitly in your code and you have a bug somewhere (to which you can use some print statements or pdb to figure out what map it is).

IMO, it really is the error message (and the traceback) that carries the pertinent information, not saying what domain <-> codomain is actually raising the error message.

comment:268 Changed 8 months ago by vbraun

  • Branch changed from public/ticket/14711 to 00b3e2f3cf90b5e7a339367f8ad4e08e1f0fb3d7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.