#14711: Weak references in the coercion graph
-------------------------------------+-------------------------------------
Reporter: jpflori | Owner: davidloeffler
Type: defect | Status: needs_review
Priority: critical | Milestone: sage-5.13
Component: number fields | Resolution:
Keywords: memleak, number | Merged in:
field, QuadraticField | Reviewers:
Authors: Simon King | Work issues:
Report Upstream: N/A | Commit:
Branch: | 364b9856b28d7060e3ea9825144de66c8f11ca2a
u/SimonKing/ticket/14711 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (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.''
2. 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.''
3. 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/14711#comment:126>
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.
