Opened 7 years ago
Closed 7 years ago
#18897 closed defect (fixed)
Memory leak in sage.misc.binary_tree.BinareeTree
Reported by:  slabbe  Owned by:  

Priority:  critical  Milestone:  sage6.8 
Component:  memleak  Keywords:  
Cc:  SimonKing, jmantysalo  Merged in:  
Authors:  Simon King  Reviewers:  Sébastien Labbé, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  80ce876 (Commits, GitHub, GitLab)  Commit:  80ce8765811c7ac18b921467e113630169b6aaaf 
Dependencies:  Stopgaps: 
Description (last modified by )
This method, inspired from the code of Nils Bruin posted in the sagedevel post Memory leaks on matrix creation?, shows some leak in the eigenvalues method for integer matrices of order larger or equal to 4. Examples are below.
def test(L, dim): import gc from collections import Counter gc.collect() pre={id(c) for c in gc.get_objects()} for _ in range(100): matrix(dim, L).eigenvalues() gc.collect() post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre) return [(k,v) for (k,v) in post.iteritems() if v>10]
An example with no leak::
sage: L = [1,0,0,1,0,0,1,1,0,0,0,1,2,0,0,1,0,0,2,0,0,0,0,0,1] sage: test(L, 5) []
Five forgotten polynomials::
sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1] sage: test(L, 5) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)]
Twelve forgotten polynomials::
sage: L = [0,1,2,0,0,2,1,2,1,1,1,0,1,1,2,1,1,1,2,0,0,2,0,2,0] sage: test(L, 5) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1200)]
A 4 by 4 matrix with five forgotten polynomials::
sage: L = [0, 2, 0, 2, 2, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1] sage: test(L, 4) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)]
Random ones::
sage: test([randint(0,100) for _ in range(9)], 3) [] sage: test([randint(0,100) for _ in range(16)], 4) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)] sage: test([randint(0,2) for _ in range(25)], 5) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)] sage: test([randint(0,2) for _ in range(25)], 5) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1200)] sage: test([randint(0,2) for _ in range(25)], 5) [] sage: test([randint(0,100) for _ in range(36)], 6) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1400)]
Change History (37)
comment:1 Changed 7 years ago by
 Description modified (diff)
comment:2 Changed 7 years ago by
 Summary changed from Memory leak in eigenvalues method to Memory leak in polynomial_compiled.univar_pd
comment:3 Changed 7 years ago by
 Cc SimonKing added
comment:4 Changed 7 years ago by
comment:5 Changed 7 years ago by
Ok, so it seems to come from calling roots
on an element of the Univariate Polynomial Ring in x over Algebraic Field
:
def test(): import gc from collections import Counter gc.collect() pre={id(c) for c in gc.get_objects()} R.<x> = QQbar['x'] p = x^5  8*x^4 + 21*x^3  22*x^2 + 9*x  1 for _ in range(100): #p.factor() # which then calls: #QQbar._factor_univariate_polynomial(p) # which then calls: p.roots() gc.collect() post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre) return [(k,v) for (k,v) in post.iteritems() if v>10]
We get:
sage: test() [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 1000)]
comment:6 Changed 7 years ago by
Those univar_pd
are created in the class CompiledPolynomialFunction
which provides an easy way to create the problem:
def test(): from sage.rings.polynomial.polynomial_compiled import CompiledPolynomialFunction import gc from collections import Counter gc.collect() pre={id(c) for c in gc.get_objects()} L = [1, 9, 22, 21, 8, 1] for _ in range(100): CompiledPolynomialFunction(L) gc.collect() post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre) return [(k,v) for (k,v) in post.iteritems() if v>10]
and we get:
sage: test() [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 100)]
comment:7 Changed 7 years ago by
Ok, so this goes now beyond my knowledge. Somebody else will need to check why the univar_pd are not garbage collected.
https://github.com/sagemath/sage/blob/master/src/sage/rings/polynomial/polynomial_compiled.pyx#L402
comment:8 Changed 7 years ago by
During initialisation of a compiled polynomial, _parse_structure()
is called, which creates a sage.misc.binary_tree.BinaryTree
. Into this binary tree, a univar_pd
is inserted.
When finishing initialisation of a compiled polynomial, the binary tree gets deallocated. However, the univar_pd
does not get deallocated. I don't know why it isn't, but rather clearly that's where the leak is occurring.
comment:9 followup: ↓ 10 Changed 7 years ago by
Got it!
It seems that a binary tree is NEVER completely deallocated. When calling binary_tree_dealloc(node)
, then the left and right descendants of node
are deallocated, but not node
itself.
comment:10 in reply to: ↑ 9 ; followup: ↓ 14 Changed 7 years ago by
Replying to SimonKing:
It seems that a binary tree is NEVER completely deallocated. When calling
binary_tree_dealloc(node)
, then the left and right descendants ofnode
are deallocated, but notnode
itself.
To be precise: The pointer to node
is freed, but one should call free_binary_tree_node(node)
instead.
comment:11 Changed 7 years ago by
 Branch set to u/SimonKing/memory_leak_compiled_polynomial
comment:12 Changed 7 years ago by
 Commit set to 79923d35f59362331a5aa006f8dbc6c329acd440
 Status changed from new to needs_review
I used your test to show that the memory leak is fixed. Note, however, that the fix is in the deallocation of binary trees and has nothing to do with compiled polynomials.
New commits:
79923d3  Fix a memory leak in the deallocation of binary trees

comment:13 Changed 7 years ago by
 Cc jmantysalo added
comment:14 in reply to: ↑ 10 ; followup: ↓ 18 Changed 7 years ago by
Replying to SimonKing:
Replying to SimonKing:
It seems that a binary tree is NEVER completely deallocated. When calling
binary_tree_dealloc(node)
, then the left and right descendants ofnode
are deallocated, but notnode
itself.To be precise: The pointer to
node
is freed, but one should callfree_binary_tree_node(node)
instead.
the following looks more logical to me (diff over your patch):
diff git a/src/sage/misc/binary_tree.pyx b/src/sage/misc/binary_tree.pyx index 984ef57..c637d91 100644  a/src/sage/misc/binary_tree.pyx +++ b/src/sage/misc/binary_tree.pyx @@ 25,13 +25,11 @@ cdef void free_binary_tree_node(binary_tree_node *self): sage_free(self) cdef void binary_tree_dealloc(binary_tree_node *self):  # deallocate the descendants of self, but NOT self if self.left != NULL: binary_tree_dealloc(self.left)  free_binary_tree_node(self.left) if self.right != NULL: binary_tree_dealloc(self.right)  free_binary_tree_node(self.right) + free_binary_tree_node(self) cdef void binary_tree_insert(binary_tree_node *self, int key, object value): @@ 210,7 +208,6 @@ cdef class BinaryTree: """ if self.head != NULL: binary_tree_dealloc(self.head)  free_binary_tree_node(self.head) def insert(BinaryTree self, object key, object value = None): """
comment:15 Changed 7 years ago by
 Branch changed from u/SimonKing/memory_leak_compiled_polynomial to public/18897
 Commit changed from 79923d35f59362331a5aa006f8dbc6c329acd440 to 720de3bf96d4e72965581bbf5ad372e94fe61237
The fix proposed by Simon fixes all the way to create the bug I saw yesterday. To me it is a positive review. I added a reference to the ticket in the doctest and posted that on public/18897.
(the comment of dimpase just appeared as I was writing this comment)
New commits:
720de3b  Trac #18897: added a ref to trac # in doctest

comment:16 Changed 7 years ago by
I am now running tests with the change I proposed (which I like as it makes code shorter and more readable), just to be 100% sure.
comment:17 Changed 7 years ago by
 Summary changed from Memory leak in polynomial_compiled.univar_pd to Memory leak in sage.misc.binary_tree.pyx
comment:18 in reply to: ↑ 14 ; followups: ↓ 19 ↓ 21 Changed 7 years ago by
 Summary changed from Memory leak in sage.misc.binary_tree.pyx to Memory leak in polynomial_compiled.univar_pd
Replying to dimpase:
the following looks more logical to me (diff over your patch):
I wanted the change to be as small as possible. But I wouldn't oppose to have all checks done in binary_tree_dealloc
:
cdef void binary_tree_dealloc(binary_tree_node *self): if self == NULL: return binary_tree_dealloc(self.left) binary_tree_dealloc(self.right) free_binary_tree_node(self)
comment:19 in reply to: ↑ 18 Changed 7 years ago by
Replying to SimonKing:
Replying to dimpase:
the following looks more logical to me (diff over your patch):
I wanted the change to be as small as possible. But I wouldn't oppose to have all checks done in
binary_tree_dealloc
:
PS: And then of course BinaryTree.__dealloc__
simply becomes
def __dealloc__(self): binary_tree_dealloc(self.head)
comment:20 Changed 7 years ago by
PS: I am doing this change now. Also, I am changing __init__
into __cinit__
.
Rationale: The current __init__
just sets the pointer self.head = NULL
. But initialising cdata (pointers etc.) is the job of __cinit__
: It should initialise the cdata to such extend that __dealloc__
can not crash. With the current code, there may be circumstances under which the __init__
is not called, so that __dealloc__
will fail with a segmentation fault.
comment:21 in reply to: ↑ 18 ; followup: ↓ 24 Changed 7 years ago by
Replying to SimonKing:
Replying to dimpase:
the following looks more logical to me (diff over your patch):
I wanted the change to be as small as possible. But I wouldn't oppose to have all checks done in
binary_tree_dealloc
:cdef void binary_tree_dealloc(binary_tree_node *self): if self == NULL: return binary_tree_dealloc(self.left) binary_tree_dealloc(self.right) free_binary_tree_node(self)
or even
cdef void binary_tree_dealloc(binary_tree_node *self): if self != NULL: binary_tree_dealloc(self.left) binary_tree_dealloc(self.right) free_binary_tree_node(self)
comment:22 Changed 7 years ago by
 Commit changed from 720de3bf96d4e72965581bbf5ad372e94fe61237 to 6d340771137df00b0da8a24485a95383f111d533
Branch pushed to git repo; I updated commit sha1. New commits:
6d34077  Simplify code for deallocation of binary trees

comment:23 Changed 7 years ago by
comment:24 in reply to: ↑ 21 Changed 7 years ago by
Replying to dimpase:
or even
cdef void binary_tree_dealloc(binary_tree_node *self): if self != NULL: binary_tree_dealloc(self.left) binary_tree_dealloc(self.right) free_binary_tree_node(self)
Right. Before I change that: Should the module be moved to data_structures? After all, it is a general data structure that does not rely on sagespecific structures (i.e., not on parents and elements).
comment:25 Changed 7 years ago by
PPS: Why is the implementation of binary trees in sage.combinat.binary_tree totally orthogonal to the one in sage.misc.binary_tree?
I'll ask on sage.combinat, and I suppose moving to sage.data_structure and unification of the two implementations should be on a separate ticket. So, I'll do the additional simplification now, and everything else is for later.
comment:26 Changed 7 years ago by
 Commit changed from 6d340771137df00b0da8a24485a95383f111d533 to 80ce8765811c7ac18b921467e113630169b6aaaf
Branch pushed to git repo; I updated commit sha1. New commits:
80ce876  Further simplification

comment:27 followup: ↓ 29 Changed 7 years ago by
 Priority changed from major to critical
 Status changed from needs_review to needs_info
I just tried the example in the ticket description, both on unpatched and patched, and got the following disturbing output:
$ sage ┌────────────────────────────────────────────────────────────────────┐ │ SageMath Version 6.8.beta8, Release Date: 20150710 │ │ Type "notebook()" for the browserbased notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: def test(L, dim): import gc from collections import Counter gc.collect() pre={id(c) for c in gc.get_objects()} for _ in range(100): matrix(dim, L).eigenvalues() gc.collect() post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre) return [(k,v) for (k,v) in post.iteritems() if v>10] ....: sage: L = [1,0,0,1,0,0,1,1,0,0,0,1,2,0,0,1,0,0,2,0,0,0,0,0,1] sage: test(L, 5) [(<class 'sage.structure.dynamic_class.DynamicMetaclass'>, 11), (<type 'instance'>, 106), (<type 'function'>, 1680), (<type 'dict'>, 271), (<type 'type'>, 78), (<type 'method_descriptor'>, 195), (<type 'wrapper_descriptor'>, 403), (<type 'property'>, 37), (<type 'classobj'>, 13), (<type 'module'>, 83), (<type 'list'>, 262), (<type 'sage.misc.constant_function.ConstantFunction'>, 21), (<type 'tuple'>, 264), (<type 'getset_descriptor'>, 199), (<class 'weakref.KeyedRef'>, 64), (<class 'numpy.testing.nosetester.NoseTester'>, 19), (<type 'staticmethod'>, 50), (<type 'member_descriptor'>, 12), (<type 'builtin_function_or_method'>, 177), (<type 'weakref'>, 152), (<type 'instancemethod'>, 22), (<type 'cell'>, 40)] sage:
if I rerun stuff, it works as it should; on the patched system:
sage: test(L, 5) # as before the fix: [] sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1] sage: test(L, 5) # did not work before the fix: [] sage:
on the unpatched system:
sage: test(L, 5) [] sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1] sage: test(L, 5) [(<type 'sage.rings.polynomial.polynomial_compiled.univar_pd'>, 500)] sage:
In short: something happens on the 1st call... Perhaps it is harmless, I don't know.
comment:28 Changed 7 years ago by
perhaps matrix
leaks in other places, too; on the patched system:
$ sage ┌────────────────────────────────────────────────────────────────────┐ │ SageMath Version 6.8.beta8, Release Date: 20150710 │ │ Type "notebook()" for the browserbased notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Warning: this is a prerelease version, and it may be unstable. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ sage: matrix(5,[1]*25); sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1] sage: def test(L, dim): import gc from collections import Counter gc.collect() pre={id(c) for c in gc.get_objects()} for _ in range(100): matrix(dim, L).eigenvalues() gc.collect() post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre) return [(k,v) for (k,v) in post.iteritems() if v>10] ....: sage: test(L, 5) [(<type 'function'>, 13), (<type 'dict'>, 18), (<class 'sage.structure.dynamic_class.DynamicMetaclass'>, 11), (<type 'list'>, 34), (<type 'sage.misc.constant_function.ConstantFunction'>, 21), (<type 'tuple'>, 88), (<type 'cell'>, 24), (<class 'weakref.KeyedRef'>, 64), (<type 'staticmethod'>, 12), (<type 'weakref'>, 27)] sage: test(L, 5) [] sage:
comment:29 in reply to: ↑ 27 Changed 7 years ago by
 Status changed from needs_info to needs_review
Replying to dimpase:
In short: something happens on the 1st call... Perhaps it is harmless, I don't know.
Well, if something is only there in the first run, then it is not accumulating, and thus by definition it is not a leak, and thus not critical.
comment:30 Changed 7 years ago by
On the other hand: What happens if you are also iterating over different base rings?
comment:31 Changed 7 years ago by
sage: L = [1,1,0,1,0,1,2,1,1,0,0,1,2,0,0,1,1,0,2,0,0,0,0,0,1] sage: def test(L, dim): ....: import gc ....: from collections import Counter ....: gc.collect() ....: pre={id(c) for c in gc.get_objects()} ....: m = matrix(dim, L) ....: for p in range(2,102): ....: m.change_ring(GF(nth_prime(p))).eigenvalues() ....: gc.collect() ....: post=Counter(type(o) for o in gc.get_objects() if id(o) not in pre) ....: return [(k,v) for (k,v) in post.iteritems() if v>10] ....: sage: test(L, 5) [(<class 'sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway_with_category'>, 100), (<type 'sage.libs.ntl.ntl_ZZ_pX.ntl_ZZ_pX'>, 76), (<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>, 2494), (<class 'sage.rings.finite_rings.homset.FiniteFieldHomset_with_category'>, 76), (<type 'sage.categories.morphism.IdentityMorphism'>, 153), (<class 'sage.rings.homset.RingHomset_quo_ring_with_category'>, 100), (<type 'weakref'>, 3700), (<type 'sage.categories.map.FormalCompositeMap'>, 200), (<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>, 16), (<class 'sage.modules.free_module.FreeModule_ambient_field_with_category'>, 60), (<type 'sage.libs.ntl.ntl_ZZ_pEContext.ntl_ZZ_pEContext_class'>, 75), (<type 'sage.categories.morphism.CallMorphism'>, 197), (<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_p_with_category'>, 176), (<type 'list'>, 8080), (<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>, 523), (<type 'sage.rings.finite_rings.integer_mod.NativeIntStruct'>, 100), (<type 'sage.rings.finite_rings.integer_mod.Int_to_IntegerMod'>, 200), (<type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>, 382), (<type 'sage.misc.constant_function.ConstantFunction'>, 3050), (<class 'sage.rings.ideal.Ideal_pid'>, 100), (<type 'sage.rings.finite_rings.hom_prime_finite_field.FiniteFieldHomomorphism_prime'>, 76), (<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>, 100), (<class 'sage.structure.sequence.Sequence_generic'>, 75), (<type 'dict'>, 2034), (<type 'sage.misc.cachefunc.CachedMethodCaller'>, 123), (<class 'sage.rings.finite_rings.conway_polynomials.PseudoConwayLattice'>, 100), (<type 'staticmethod'>, 132), (<type 'cell'>, 204), (<type 'sage.structure.element.NamedBinopMethod'>, 13), (<type 'sage.rings.finite_rings.integer_mod.Integer_to_IntegerMod'>, 176), (<type 'sage.rings.finite_rings.element_givaro.Cache_givaro'>, 16), (<type 'sage.rings.polynomial.polynomial_element.PolynomialBaseringInjection'>, 200), (<type 'classobj'>, 13), (<type 'function'>, 1817), (<type 'property'>, 37), (<class 'sage.rings.finite_rings.finite_field_pari_ffelt.FiniteField_pari_ffelt_with_category'>, 60), (<class 'sage.rings.homset.RingHomset_generic_with_category'>, 100), (<class 'sage.structure.dynamic_class.DynamicMetaclass'>, 72), (<type 'frozenset'>, 33), (<type 'sage.structure.coerce_dict.MonoDictEraser'>, 2087), (<type 'sage.structure.coerce_dict.TripleDict'>, 1043), (<type 'instancemethod'>, 609), (<type 'sage.rings.finite_rings.element_pari_ffelt.FiniteFieldElement_pari_ffelt'>, 180), (<class 'sage.structure.dynamic_class.DynamicClasscallMetaclass'>, 21), (<type 'wrapper_descriptor'>, 513), (<type 'instance'>, 106), (<type 'sage.libs.ntl.ntl_ZZ_pContext.ntl_ZZ_pContext_class'>, 76), (<type 'getset_descriptor'>, 202), (<class 'sage.rings.finite_rings.homset.FiniteFieldHomset_with_category'>, 76), (<type 'sage.structure.coerce_dict.MonoDict'>, 2087), (<type 'sage.structure.coerce_maps.DefaultConvertMap_unique'>, 1090), (<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>, 21566), (<class 'weakref.KeyedRef'>, 10447), (<type 'builtin_function_or_method'>, 428), (<type 'member_descriptor'>, 12), (<class 'sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway_with_category.element_class'>, 76), (<type 'sage.rings.morphism.RingHomomorphism_cover'>, 76), (<class 'sage.categories.homset.Homset_with_category'>, 176), (<type 'method_descriptor'>, 360), (<type 'module'>, 94), (<type 'tuple'>, 2688), (<type 'sage.libs.pari.gen.gen'>, 60), (<type 'sage.structure.coerce_dict.TripleDictEraser'>, 1043), (<class 'numpy.testing.nosetester.NoseTester'>, 19), (<type 'type'>, 82), (<type 'sage.rings.morphism.RingMap_lift'>, 76)] sage: test(L, 5) []
So, that looks like a different kind of leak: Some objects are not deallocated when they aren't used (output of the first test(L, 5)
), but at least they are still available for future use (output of the second test(L, 5)
).
The patch from this ticket has fixes one leak, and I'd say that the other leak should be addressed on a different ticket.
comment:32 Changed 7 years ago by
... (<class 'sage.rings.homset.RingHomset_quo_ring_with_category'>, 100), ... (<class 'sage.rings.homset.RingHomset_generic_with_category'>, 100), ...
I guess that's the culprit.
comment:33 Changed 7 years ago by
I opened #18905 to work on the latest leaks. Otherwise, it's good to go.
comment:34 Changed 7 years ago by
Replying to dimpase:
In short: something happens on the 1st call... Perhaps it is harmless, I don't know.
Yes, I noticed the same thing yesterday. There is stuff that is there the first execution, but never after. I did not look deeper into that...
comment:35 Changed 7 years ago by
 Reviewers set to Sébastien Labbé, Dima Pasechnik
 Status changed from needs_review to positive_review
comment:36 Changed 7 years ago by
 Summary changed from Memory leak in polynomial_compiled.univar_pd to Memory leak in sage.misc.binary_tree.BinareeTree
comment:37 Changed 7 years ago by
 Branch changed from public/18897 to 80ce8765811c7ac18b921467e113630169b6aaaf
 Resolution set to fixed
 Status changed from positive_review to closed
It seems to come from the factor method applied on the charpoly after changing the ring to
AlgebraicField
.We get: