#15303: Coercion discovery fails to be transitive
----------------------------+-------------------------
Reporter: nbruin | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.13
Component: coercion | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
----------------------------+-------------------------
Comment (by nbruin):
Replying to [comment:2 SimonKing]:
> 3. Provided that we fixed the problem of transitivity, we would now find
a coercion from B to C via A.
There would be an additional effect, by the way: If the coercion that does
get discovered is stored as a composition (on C) then there is now a
reference from C._coerce_from_hash to A. This reference lives in a
MonoDict keyed by B, so this reference remains as long as B is alive. So
we see that as long as B and C are alive, then A will be kept alive as
well (thus, with monodicts we can have objects whose lifetime depends on
two objects BOTH being alive)
Note that if the composition gets computed in a smarter way (for instance,
a composition of homomorphisms between finitely generated rings could be
explicitly computed by computing the images of the generators and
constructing a straight homomorphism from B to C out of that) then the
resulting coercion map might not refer to A anymore.
I am not saying that this is avoidable nor that we should consider this a
memory leak: we're keeping A in memory for a good reason, even if the
reason is not directly supplied by the user.
> However, one additional complication arises with the current
implementation: The ''absence'' of a coercion is cached. Hence, if we
asked for a coercion in 1., then in 3. you would still not get a coerce
map, because the absence of a coercion has been cached in 1.
There are milder ways of invalidating caches: We could mark cached non-
existence with a "coercion graph version number". When a non-existence is
retrieved, one could check the current "coercion graph version number" and
if the current graph is newer, we'd have to reinvestigate the "None".
Frankly, I don't believe that would give acceptable performance either,
but we could at least be much more lazy about invalidating "no coercion
exists" findings. The reason why I think this would still not be good
enough is because I expect that coercion graph mutations occur fairly
frequently (basically with any parent creation) and I don't see a way to
localize coercion graph versions, so any mutation would invalidate ALL
non-existence caches.
> For example `B._coerce_embeddings_from[A] = phi`, ''in addition'' to
`A._coerce_embedding = phi`. Since it is a `MonoDict` and thus has weak
references to the keys, B would not prevent A from being garbage collected
(but of course A would still keep B alive, because we registered the
coerce embedding).
Yes, something along those lines. In fact, since `_coerce_embeddings_from`
and `_coerce_from_list` would serve the same purpose from the perspective
of coercion discoveries, I think the entries in `_coerce_from_list` should
also be added to `_coerce_embeddings_from`, because it would simplify the
code. By then it would make more sense to call the attribute
`_coerce_from_to_be_used_in_backtracking` and the list that is now
`_coerce_from_hash` could be `_coerce_from_cached_results`.
By then we should probably be storing ALL maps there in weakened form.
The only function of `_coerce_from_list` now is to keep domains alive, so
it would be more economical to replace that by a list
`_domains_to_keep_alive` where we can store strong references to the
domains of the corresponding weakened maps that are now in
`_coerce_from_to_be_used_in_backtracking`
So we would end up with (names up for choice):
- `P._coercion_cache`: !MonoDict containing discovered (weakened) maps
into P.
- `P._coercion_maps`: !MonoDict containing (weakened) maps into P that
get used by backtracking
- `P._domains_to_keep_alive`: List of domains that should be kept alive
as long as P lives.
- `P._codomains_to_keep_alive`: List of codomains that should be kept
alive as long as P lives. Normally, such codomains Q would have an entry
in `Q._coercion_maps[P]`. Just storing a map in P._coerce_embedding would
also have this effect.
In the present naming system, it wasn't immediately clear to me what
purposes `_coerce_from_hash` and `_coerce_from_list` served, so changing
those names could be beneficial.
> If nobody has a better suggestion, then I think we should restrict
ourselves to just fix the transitivity problem; the cache problem (it
seems to me) is not solvable without creating a drastic slow-down.
Yes, I don't have any suggestions that I seriously believe would lead to
acceptable performance.
--
Ticket URL: <http://trac.sagemath.org/ticket/15303#comment:3>
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.
