Weak references in the coercion graph

[jpflori]

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]

comment:1

In number_field.py:

Quadratic number fields are cached::

I guess they should be only weakly cached.

[simon-king-jena]

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]

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]

comment:4

And trying

QuadraticField(-D, cache=False)

does not solve the problem anyway.

[jpflori]

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]

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]

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]

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]

comment:9

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

[jpflori]

comment:11

Bumping Simon as requested.

[simon-king-jena]

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]

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]

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]

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]

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]

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]

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]

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]

Branch: u/SimonKing/ticket/14711

[simon-king-jena]

comment:21

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

[simon-king-jena]

Attachment: chain.png

A reference chain that apparently keeps quadratic fields alive.

[tscrim]

comment:255

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.

[jpflori]

comment:256

Not any objection, I want this merged asap.

[vbraun]

comment:257

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

[vbraun]

comment:258

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

[tscrim]

comment:259

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

[tscrim]

comment:260

Anne, Mike - More changes to the k-schur book...

[simon-king-jena]

comment:261

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.

[tscrim]

comment:262

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

[sagetrac-git]

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

00b3e2f

Fixed doctests.

[sagetrac-git]

Changed commit from 8e5fe42 to 00b3e2f

[tscrim]

comment:264

Fixed. Took 51 minutes for my Sage to recompile itself. Now to have it recompile again!

[simon-king-jena]

comment:265

Replying to @tscrim:

I really need to figure out how to get ccache to work

sage -i ccache doesn't work for you?

[anneschilling]

comment:266

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

[tscrim]

comment:267

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.

[vbraun]

Changed branch from public/ticket/14711 to 00b3e2f

[jdemeyer]

Changed commit from 00b3e2f to none

[jdemeyer]

Replying to @jpflori:

SchemeMorphism can not inherit from Morphism, because of a bug with
multiple inheritance of a Python class from Cython extension classes.

Does anybody have a reference to this bug? I see only comments about "a bug in Cython" without any specifics.

[tscrim]

comment:270

There is comment:92 for a bit more specifics. It might also be some shadow of cython/cython#1732 or have worked itself out in Cython upgrades. IDK, I could not explicitly reproduce any failures. (Although this was done before I was looking at this ticket.)

[jdemeyer]

comment:271

Replying to @tscrim:

It might also be some shadow of cython/cython#1732

I doubt it because that is specifically about overriding cdef methods with cpdef methods. I don't think that Sage did that before my relatively recent changes to the coercion model.