#715: Parents probably not reclaimed due to too much caching
------------------------+---------------------------------------------------
Reporter: robertwb | Owner: somebody
Type: defect | Status: needs_review
Priority: major | Milestone: sage-4.8
Component: coercion | Keywords: weak cache coercion
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #9138, #11900
------------------------+---------------------------------------------------
Changes (by SimonKing):
* status: needs_info => needs_review
* work_issues: Should we rename `TripleDictById` into `TripleDict`, or
do we want a "weak triple dictionary
with comparison by equality"? =>
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.
>
> Apply [attachment:trac715_tripledict_combined.patch]
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.
Apply [attachment:trac715_one_tripledict.patch]
--
Comment:
To answer my own question: I believe that comparison by equality does not
make sense (yet), since it isn't used in the coercion model.
Therefore, I have produced a new patch. Idea: The `TripleDict` stores the
addresses of the keys. In addition, there is a dictionary of weak
references with callback function. The ''only'' purpose of these
references is that their callback functions are erasing invalid dictionary
items.
__"Raw" speed__
Patched:
{{{
sage: from sage.structure.coerce_dict import TripleDict
sage: D = TripleDict(113)
sage: L = []
sage: for p in prime_range(10^3):
....: K = GF(p)
....: P = K['x','y']
....: L.append((K,P))
....:
sage: for i,(K,P) in enumerate(L):
....: D[K,P,True] = i
....:
sage: cython("""
....: from sage.structure.coerce_dict cimport TripleDict
....: def testTriple(TripleDict D, list L):
....: for K,P in L:
....: n = D[K,P,True]
....: def testTripleGet(TripleDict D, list L):
....: for K,P in L:
....: n = D.get(K,P,True)
....: def testTripleSet(list L):
....: cdef TripleDict D = TripleDict(113)
....: for i,(K,P) in enumerate(L):
....: D.set(K,P,True, i)
....: """)
sage: %timeit testTriple(D,L)
625 loops, best of 3: 42.4 µs per loop
sage: %timeit testTripleGet(D,L)
625 loops, best of 3: 28.3 µs per loop
sage: %timeit testTripleSet(L)
125 loops, best of 3: 2.66 ms per loop
}}}
Unpatched:
{{{
sage: %timeit testTriple(D,L)
625 loops, best of 3: 31.2 µs per loop
sage: %timeit testTripleGet(D,L)
625 loops, best of 3: 17.5 µs per loop
sage: %timeit testTripleSet(L)
625 loops, best of 3: 79.2 µs per loop
}}}
__Doctest speed__
Patched
{{{
sage -t "devel/sage-main/sage/modules/free_module.py"
[11.4 s]
sage -t "devel/sage-main/sage/modules/free_module.py"
[11.7 s]
}}}
Unpatched
{{{
sage -t "devel/sage-main/sage/modules/free_module.py"
[11.7 s]
sage -t "devel/sage-main/sage/modules/free_module.py"
[11.5 s]
}}}
__Conclusion__
Using weak references, things become a bit slower, but it is a lot better
than with the previous patches. According to the timing of the doc tests,
the regression doesn't matter in applications.
I guess there is no free lunch, and thus the regression is small enough,
given that the memory leak is fixed (which is checked in a new test).
I have not run the full test suite yet, but I think it can be reviewed.
Apply trac715_one_triple_dict.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/715#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 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.
