#14711: Weak references in the coercion graph
-------------------------------------+-------------------------------------
Reporter: jpflori | Owner: davidloeffler
Type: defect | Status: needs_review
Priority: critical | Milestone: sage-6.1
Component: number fields | Resolution:
Keywords: memleak, number | Merged in:
field, QuadraticField | Reviewers:
Authors: Simon King | Work issues:
Report Upstream: N/A | Commit:
Branch: | 37bf59eac24eda1ece89aff7dde4a1db5d0cbb5c
u/SimonKing/ticket/14711 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Replying to [comment:165 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/14711#comment:166>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
