#14711: Memleak when creating QuadraticField
-------------------------------------+-------------------------------------
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: Fix elliptic curves
Report Upstream: N/A | code
Branch: | Commit:
u/SimonKing/ticket/14711 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by nbruin):
Replying to [comment:84 SimonKing]:
> One does! Namely, suppose that you first do `P.register_coercion(mor)`,
then you allow `S` to become garbage collected, and then you create a new
parent `Q` with an
embedding into what looks like `S` (of course, it now is a replica of the
original now garbage collected `S`).
> You would want that `Q` coerces into `P` via `S`, by transitivity of
coercions. But you collected `mor.domain()` and thus you will fail to find
this coercion.
I agree that there is a place for such strong connections, but I have
severe reservations about declaring it's the only way or even the default
way to inform the system
about coercions.
The following would leak memory with the model you propose:
{{{
M1=ZZ^1
M2=ZZ^2
for d in [2..100000]:
N=ZZ^d
m1=Hom(N,M1)([M.0 for i in range(d)])
m2=Hom(N,M2)([M.(i % 2) for i in range(d)])
M1.register_coercion(m1)
M2.register_coercion(m2)
}}}
I have severe reservations about declaring that this code "will never be
memory efficient" in sage. One way out is to use the (for this purpose)
extremely inappropriately named
{{{
N.register_embedding(m1)
}}}
instead, which in your model would mean M1 lives at least as long as N
instead. In addition, we would not be able to do this for both `M1` and
`M2`.
I think there's room for a `register_embedding` with those semantics
(although it should probably have a different name, because it doesn't
have to be an embedding)
as well as for `register_coercion_from_while_keeping_domain_alive` with a
catchier name, but the life-enhancing side effects are fundamentally
separate from the fact
that there's a coercion in the first place, and I think it should be
possible to register a non-life-enhancing coercion as well (the main
reason is that
it's easily done and that I haven't seen a proof it's not necessary. We
don't want to unnecessarily hamstring the system).
'''philosophical ramblings'''
The following observations are the result of trying to come up with a
conceptual ideal/model that we could use to argue what our coercion
framework SHOULD do. Up to
now it seems to me people have mainly been making ad-hoc, gut feeling
decisions about how to put together coercion. I haven't found a better
solution here, but I
think there are some examples may illustrate we might just have to be
pragmatic about this.
Your suggestion makes sense if you want to model a "permanent, unchanging
universe" in which all possible parents, with consistent coercions,
already exist; we're
simply "discovering" this universe in a piecemeal fashion. It's a common
model in modern algebra, but I think our computer algebra model is too far
away from this
ideal to follow this model too far. Consider:
{{{
Qx.<x>=QQ[]
K.<a>=NumberField(x^4-2)
L.<b>=NumberField(x^2-2,embedding=a^2)
}}}
This fits perfectly in the "unchanging universe" model. Also note that the
coercion system does not need to let L keep K alive, since the
construction parameters,
which get kept alive for the life of L by `CachedRepresentation` or
something analogous, refer to K already.
Now consider
{{{
M.<b>=NumberField(x^2-2)
}}}
In the "unchanging universe" (and in sage as well) we have that M is
distinct from L. However, I think it's unrealistic to expect that all
"embeddings" etc. can be
specified at construction time. So I think, even though it's not possible
currently in sage, that one should allow for
{{{
m1=Hom(M,K)([a^2])
m2=Hom(M,K)([-a^2])
M.register_embedding(m1)
}}}
Note that the choice of `m1` or `m2` here leads to different relations
between `M` and `K` and hence different universes.
In other words, our concept of "globally unique" is not powerful enough to
capture the
full identity of objects, which would include the coercion relations with
objects that haven't been "discovered" yet. In practice, we can usually
work around that by
for instance changing the names of generators and hence create
artificially differently labelled objects but that's already not a
possibility for creating
different copies of `ZZ^n`, since there are no generator names to choose
there.
I think one has to accept the reality here: what we have is a collection
of objects whose relations do change in time.
'''Some particular responses''' (most of them direct corollaries from what
is observed above).
> Another attempt to explain why I think the explicitly registered maps
need to be kept:
>
> Think of the coercions as a digraph.
> - The vertices correspond to parents.
> - The arrows (oriented edges) of the digraph correspond to those maps
that are declared as coercions by `.register_coercion(...)`.
> - In addition to the arrows created with `register_coercion`, the
coercion system may find short-cuts by calling `._coerce_map_from_(...)`.
For efficiency reasons,
> these short-cuts are stored in a cache.
> - The coercion system then tries to find directed paths between two
given vertices, including short-cuts. For efficiency reasons, it stores
the resulting composed
> maps in a cache.
That's not the only thing coercion does. It may also find "common covering
structures", which may lead to construction of new parents. Those
definitely don't deserve
to get nailed into memory. Yet, the code that creates these parents will
look (to the coercion system) as a "user", so it would be using these
strong-referencing
coercion registration routines.
> So, the coercion system will not care for the health of P, but it must
care for the connectivity of the coercion graph. And in the current
algorithm sketched above,
> it is of vital importance to keep arrows leading to P alive, since
otherwise we have to live with shortcuts only.
I think it may well be a feature, not a bug, that one at some point can
just be left with the shortcuts and that the intermediates have fallen
out. The natural way of
staying close to "discovering a permanent universe" is by never throwing
away anything that has been discovered, and I think we agree that's a
"memory leak". So
it's really a matter of only keeping things around that we still need. If
we're too lax with considering what is "needed", we'll end up keeping too
many things in
memory.
> Then we look into the code and see that multiple embeddings are
explicitly excluded. A parent has precisely one embedding that is taken
into account by the coercion
search ''in forward direction''. You may of course register further
embeddings as coercions, by `emb.codomain().register_coercion(emb)`, but
they would only be used
for search in backward direction.
Not only that: you'd be tying different lifetime implications to that
construction too.
> And there surely is a means available to add a coercion that doesn't tie
the lifespan of two parents too closely: Implement
`P._coerce_map_from_(Q)`, which can
> return a map or simply "True" (in the latter case, conversion is used to
coerce Q into P). The result is cached in `P._coerce_from_hash`, but not
in
> `P._coerce_from_list`.
You mean: implement `P._install_coerce_map_from_(m)`, which does:
`_coerce_from_hash[Domain(m)]=m`. I think it is quite important to be able
to manipulate the
coercion graph without having to modify library code.
--
Ticket URL: <http://trac.sagemath.org/ticket/14711#comment:96>
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.
