Weak references in the coercion graph

jpflori commented 11 years ago

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.

CC: @simon-king-jena @nbruin @nthiery @anneschilling @zabrocki

Component: number fields

Keywords: QuadraticField

Author: Simon King, Travis Scrimshaw, Jean-Pierre Flori

Branch: 00b3e2f

Reviewer: Nils Bruin, Jean-Pierre Flori

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

jpflori commented 11 years ago

comment:1

In number_field.py:

Quadratic number fields are cached::

I guess they should be only weakly cached.

simon-king-jena commented 11 years ago

comment:2

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.

jpflori commented 11 years ago

comment:3

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

jpflori commented 11 years ago

comment:4

And trying

QuadraticField(-D, cache=False)

does not solve the problem anyway.

jpflori commented 11 years ago

comment:5

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.

jpflori commented 11 years ago

comment:6

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.

simon-king-jena commented 11 years ago

comment:7

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.

jpflori commented 11 years ago

comment:8

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.

jpflori commented 11 years ago

comment:9

See #8335 comment:69 for another incarnation of this problem but with finite fields.

jpflori commented 10 years ago

comment:11

Bumping Simon as requested.

simon-king-jena commented 10 years ago

comment:12

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.

simon-king-jena commented 10 years ago

comment:13

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.

simon-king-jena commented 10 years ago

comment:14

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.

jpflori commented 10 years ago

comment:15

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

simon-king-jena commented 10 years ago

comment:16

Replying to @simon-king-jena:

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.

jpflori commented 10 years ago

comment:17

Replying to @simon-king-jena:

Replying to @simon-king-jena:

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.

simon-king-jena commented 10 years ago

comment:18

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.

simon-king-jena commented 10 years ago

comment:19

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

simon-king-jena commented 10 years ago

Branch: u/SimonKing/ticket/14711

simon-king-jena commented 10 years ago

comment:21

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

simon-king-jena commented 10 years ago

Attachment: chain.png

A reference chain that apparently keeps quadratic fields alive.

jpflori commented 10 years ago

comment:22

Replying to @simon-king-jena:

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

Yes, see #11521 comment:8

simon-king-jena commented 10 years ago

comment:23

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?

simon-king-jena commented 10 years ago

comment:24

Replying to @jpflori:

Replying to @simon-king-jena:

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

Yes, see #11521 comment:8

Thanks, but google was faster than you :-P

jpflori commented 10 years ago

comment:25

Replying to @simon-king-jena:

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?

simon-king-jena commented 10 years ago

comment:26

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?

simon-king-jena commented 10 years ago

comment:27

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.

nbruin commented 10 years ago

comment:28

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 _convertto, 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.

jpflori commented 10 years ago

comment:29

Replying to @simon-king-jena:

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.

jpflori commented 10 years ago

comment:30

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).

simon-king-jena commented 10 years ago

comment:31

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.

jpflori commented 10 years ago

comment:32

Replying to @simon-king-jena:

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.

nbruin commented 10 years ago

comment:33

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 [#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?

simon-king-jena commented 10 years ago

comment:34

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?

simon-king-jena commented 10 years ago

comment:35

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.

simon-king-jena commented 10 years ago

comment:36

Replying to @simon-king-jena:

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.

simon-king-jena commented 10 years ago

comment:37

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?

simon-king-jena commented 10 years ago

comment:38

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.

nbruin commented 10 years ago

comment:39

Replying to @simon-king-jena:

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).

simon-king-jena commented 10 years ago

comment:40

Replying to @nbruin:

Replying to @simon-king-jena:

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.

nbruin commented 10 years ago

comment:41

Replying to @simon-king-jena:

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?).

simon-king-jena commented 10 years ago

comment:42

Hi Nils,

Replying to @nbruin:

Replying to @simon-king-jena:

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".

nbruin commented 10 years ago

comment:43

Replying to @simon-king-jena:

Hi Nils,

Replying to @nbruin:

Replying to @simon-king-jena:

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.

simon-king-jena commented 10 years ago

comment:44

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.

simon-king-jena commented 10 years ago

comment:45

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?

nbruin commented 10 years ago

comment:46

Replying to @simon-king-jena:

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.

jpflori commented 10 years ago

comment:47

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).

simon-king-jena commented 10 years ago

comment:48

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.

simon-king-jena commented 10 years ago

comment:49

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>

simon-king-jena commented 10 years ago

comment:50

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.

sagemath / sage

Weak references in the coercion graph #14711