#715: Parents probably not reclaimed due to too much caching
-------------------------------------------------------------------+--------
Reporter: robertwb |
Owner: somebody
Type: defect |
Status: needs_review
Priority: major |
Milestone: sage-pending
Component: coercion |
Resolution:
Keywords: weak cache coercion Cernay2012 | Work
issues:
Report Upstream: N/A |
Reviewers: Jean-Pierre Flori, Simon King
Authors: Simon King, Jean-Pierre Flori | Merged
in:
Dependencies: #9138, #11900, #11599, to be merged with #11521 |
Stopgaps:
-------------------------------------------------------------------+--------
Changes (by SimonKing):
* status: needs_work => needs_review
Old description:
> Here is a small example illustrating the issue.
>
> The memory footprint of the following piece of code grows indefinitely.
>
> {{{
> sage: K = GF(1<<55,'t')
> sage: a = K.random_element()
> sage: while 1:
> ....: E = EllipticCurve(j=a); P = E.random_point(); 2*P; del E, P;
>
> }}}
> E and P get deleted, but when 2*P is computed, the action of integers on
> A, the abelian group of rational points of the ellitpic curve, gets
> cached in the corecion model.
>
> A key-value pair is left in coercion_model._action_maps dict:
>
> (ZZ,A,*) : IntegerMulAction
>
> Moreover there is at least also references to A in the IntegerMulAction
> and one in ZZ._action_hash.
>
> So weak refs should be used in all these places if it does not slow
> things too much.
>
> '''To be merged with #11521'''. Apply:
>
> * [attachment:trac_715_combined.patch]
>
> and '''then''' the tickets from #11521.
New description:
Here is a small example illustrating the issue.
The memory footprint of the following piece of code grows indefinitely.
{{{
sage: K = GF(1<<55,'t')
sage: a = K.random_element()
sage: while 1:
....: E = EllipticCurve(j=a); P = E.random_point(); 2*P; del E, P;
}}}
E and P get deleted, but when 2*P is computed, the action of integers on
A, the abelian group of rational points of the ellitpic curve, gets cached
in the corecion model.
A key-value pair is left in coercion_model._action_maps dict:
(ZZ,A,*) : IntegerMulAction
Moreover there is at least also references to A in the IntegerMulAction
and one in ZZ._action_hash.
So weak refs should be used in all these places if it does not slow things
too much.
'''To be merged with #11521'''. Apply:
* [attachment:trac_715_combined.patch]
* [attachment:trac_715_local_refcache.patch]
and '''then''' the tickets from #11521.
--
Comment:
I have attached a new patch, that changes the way how references are being
kept track of.
First of all, as I have explained in my long post today, it is important
for speed that the buckets of `TripleDict` only know the location of the
keys in dictionary. Hence, references (weak or strong, depending on the
type of keys) need to be stored somewhere else.
Previously, there was a global dictionary, that was shared by all
`TripleDicts`. That probably was a bad idea, for the reasons you pointed
out. Now, the references are stored in a dictionary that is an attribute
of each `TripleDict`.
That has several advantages: In a single `TripleDict`, each key triple
only occurs once. Hence, we don't need to store the references in a list
addressed by a triple of memory locations, that are popped off the list
when being garbage collected.
Instead, each triple of memory locations points to exactly one triple of
references. The triple of references is popped off the dictionary as soon
as any weak-refed member of the key triple was garbage collected. Note
that the `if len(L)==0:` bit is not needed.
Another advantage: If the `TripleDicct` is deallocated, then the strong
references associated with the `TripleDict` will vanish as well, which
wouldn't have been the case with the old code.
Currently, there is only one bad situation I can think of: Let P be an
object that can not be weak-refed, has a `TripleDict` T as an attribute,
is used as a key in T, and has a `__del__` method. Then the reference
cycle P->T->T._refcache->P will keep P alive. However, if any of the four
assumptions does not hold, then P can be garbage collected. I think we can
take that chance.
Is there any question of yours that I forgot to address?
I didn't do timings, but I've successfully run the doc tests.
Apply trac_715_combined.patch trac_715_local_refcache.patch #11521
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/715#comment:204>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
